A dynamic programming framework for optimal delivery time slot pricing

Denis Lebedev, Paul Goulart and Kostas Margellos

@article{LGM:2021b,
  author = {Denis Lebedev and Paul Goulart and Kostas Margellos},
  title = {A dynamic programming framework for optimal delivery time slot pricing},
  journal = {European Journal of Operational Research},
  year = {2021},
  volume = {292},
  number = {2},
  pages = {456-468},
  url = {https://www.sciencedirect.com/science/article/pii/S0377221720309565},
  doi = {10.1016/j.ejor.2020.11.010}
}

We study the dynamic programming approach to revenue management in the context of attended home delivery. We draw on results from dynamic programming theory for Markov decision problems to show that the underlying Bellman operator has a unique fixed point. We then provide a closed-form expression for the resulting fixed point and show that it admits a natural interpretation. Moreover, we also 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. Furthermore, we derive results on the monotonicity of prices with respect to the number of orders placed in our setting. These results open the road for achieving scalable implementations of the proposed formulation, as it allows making informed choices of basis functions in an approximate dynamic programming context. We illustrate our findings on a low-dimensional and an industry-sized numerical example using real-world data, for which we derive an approximately optimal pricing policy based on our theoretical results.