From approximation error to optimality gap -- Explaining the performance impact of opportunity cost approximation in integrated demand management and vehicle routing

Prominent examples of these services are attended home delivery (AHD), same-day delivery (SDD), or mobility-on-demand (MOD). These business models have in common that customers expect a very high service level, e.g., in terms of the deviation from their desired service time (Amorim et al. (2024)). Meeting these expectations makes demand consolidation challenging, which entails high fulfillment cost (Ulmer (2020)). To still operate profitably, operational planning for these business models has evolved: Instead of optimizing the associated vehicle routing alone, providers additionally apply demand management to achieve efficient fulfillment operations. The resulting integrated demand management and vehicle routing problems (i-DMVRPs) are stochastic and dynamic with two types of integrated decisions: For each dynamically arriving customer request, the provider integratively makes a demand control decision and a vehicle routing decision with the overall objective of maximizing the expected profit, i.e., revenue net of operational fulfillment cost. Such an i-DMVRP can be modeled as a Markov decision process (MDP) and, theoretically, be solved by evaluating the well-known Bellman equation (Puterman (2014)). Practically, however, i-DMVRPs suffer from the curses of dimensionality ((Powell (2011)) such that this is not tractable for realistic-sized instances. Consequently, in literature, demand control decisions for i-DMVRPs are often optimized with a decomposition-based solution approach. More precisely, two subproblems are solved sequentially for every incoming customer request (Fleckenstein, Klein, and Steinhardt (2023), Ulmer (2020), Gallego and Topaloglu (2019), p. 25, Klein et al. (2018)): 1.) Approximating opportunity cost (OC) for each potential fulfillment option (e.g., different time windows) to measure the expected profit impact assuming the current customer chooses the respective option, given the state of the system.