Approximate dynamic programming for revenue management in attended home delivery

Thesis

We consider the problem of finding profit-maximising prices for delivery time slots in the context of attended home delivery. This is a multi-stage optimal control problem that admits a dynamic programming formulation. However, this formulation is intractable for realistic problem sizes due to the so-called "curse of dimensionality''. To facilitate an approximation of this problem, we characterise some mathematical properties of the dynamic program: We show that the underlying Bellman operator has a unique fixed point and provide a closed-form expression for it. Moreover, we show that – under certain technical assumptions – the value function, which has a discrete domain and a continuous codomain, admits a continuous extension, which is a finite-valued, concave function of its state variables, at every time step. Motivated by these results, we develop an approximate dynamic programming algorithm for a more general class of problems, characterised by value functions that are concave extensible and submodular in their state-space. Our new algorithm computes deterministic upper and stochastic lower bounds of the value function in the realm of dual dynamic programming. We show that the proposed algorithm terminates after a finite number of iterations. Moreover, we also derive probabilistic guarantees on the value accumulated under the associated policy for a single realisation of the dynamic program and for its expected value. Furthermore, we compare our algorithm with two other approximate dynamic programming solutions proposed in the literature. Our analysis entails a theoretical examination from a control-theoretical perspective and a parametric numerical case study. Our experiments are based on real-world data, from which we generate multiple scenarios to stress-test the robustness of the pricing policies to errors in model parameter estimates. Our analysis shows that the proposed algorithm dominates the others with respect to computation time and profit-generation capabilities of the delivery slot pricing policies that it generates.

Authors: Lebedev, D

• DOI: 10.5287/ora-4rxxor45k
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: dynamic pricing; approximate dynamic programming; revenue management
• Subjects: Revenue management; Delivery of goods; Pricing; Approximate computing; Electronic commerce