Scientific Program > Talks by Speaker > Ulmer Marlin

We consider a dynamic customer acceptance problem motivated by home delivery applications. During a capture phase, customers request delivery. The dispatcher must decide whether or not to accept the request given the limits on driver working hours and vehicle capacities. Accepted deliveries made during a delivery phase. The objective is to maximize the expected revenue. To solve this stochastic, dynamic decision problem, we introduce a novel method of value function approximation (VFA). VFAs are offline methods that seek to approximate a reward-to-go given a problem's state. Conventionally, VFAs are either parametric or non-parametric. Parametric VFAs (P-VFAs) approximate the functional form of a value function based on a set of state features. Non-parametric VFAs (N-VFAs) approximate individual values for each feature setting without assuming a functional form. Both types of VFAs have advantages and shortcomings. While P-VFAs provide fast and reliable approximation, the approximation is often inaccurate due to the choice of functional form. N-VFAs allow an accurate approximation, but require significant computational effort. Further, N-VFAs may provide unreliable approximation due to the curses of dimensionality. To combine the advantages and to alleviate the shortcomings of the two forms of VFA, we present a novel method, meso-parametric value function approximation (M-VFA). This method adaptively combines P-VFA and N-VFA. For a variety of instance settings based on data of Iowa City, Iowa, USA, we show how M-VFA is able to combine the advantages and alleviate the shortcomings of P-VFA and N-VFAs leading to accurate but reliable approximation and excellent policies.