Combining Parametric and Non-Parametric Value Function Approximation for Dynamic Customer Acceptances in Home Delivery
Marlin Ulmer  1@  , Barrett Thomas  2@  
1 : Technische Universität Braunschweig
2 : University of Iowa (Iowa City, Iowa, USA)

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.


Online user: 1 RSS Feed