Approximate Dynamic Programming for Delivery Time Slot Pricing: a Sensitivity Analysis

D. Lebedev, K. Margellos and P. J. Goulart

August 2020.
BibTeX  Preprint 

@article{LMG:2020,
  author = {D. Lebedev and K. Margellos and P. J. Goulart},
  title = {Approximate Dynamic Programming for Delivery Time Slot Pricing: a Sensitivity Analysis},
  year = {2020}
}

We consider the revenue management problem of finding profit-maximising prices for delivery time slots in the context of attended home delivery. This multi-stage optimal control problem admits a dynamic programming formulation that is intractable for realistic problem sizes due to the so-called “curse of dimensionality”. Therefore, we study three approximate dynamic programming algorithms both from a control-theoretical perspective and in a parametric numerical case study. Our numerical analysis is 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 theoretical analysis and numerical benchmark tests show that one of these algorithms, namely gradient-bounded dynamic programming, dominates the others with respect to computation time and profit-generation capabilities of the delivery slot pricing policies that it generates. Finally, we show that uncertainty in the estimates of the model parameters further increases the profit-generation dominance of this approach.