Explaining the performance impact of opportunity costs approximation in integrated demand management and vehicle routing

Abstract

The widespread adoption of digital distribution channels both enables and forces more and more logistics service providers to manage booking processes actively to maintain competitiveness. As a result, their operational planning is no longer limited to solving vehicle routing problems. Instead, demand management decisions and vehicle routing decisions are optimized integratively with the aim of maximizing revenue and minimizing fulfillment cost. The resulting integrated demand management and vehicle routing problems (i-DMVRPs) can be formulated as Markov decision process models and, theoretically, can be solved via the well-known Bellman equation. Unfortunately, the Bellman equation is intractable for realistic-sized instances. Thus, in the literature, i-DMVRPs are often addressed via decomposition-based solution approaches involving an opportunity costs approximation as a key component. Despite its importance, to the best of our knowledge, there is no technique to systematically analyze how the accuracy of the opportunity costs approximation affects the performance, e.g., the profit, the revenue, the number of accepted customers, or the cost of the overall logistics system, which is represented by a vehicle routing problem, nor are there general guidelines on when to apply which class of approximation approach. In this work, we address this research gap by proposing an explainability technique that quantifies and visualizes the magnitude of approximation errors, their immediate impact on the underlying vehicle routing problem and its profitability, and the relevance of approximation errors in specific regions of the state space. Exploiting reward decomposition, it further yields a characterization of different types of approximation errors. Applying the technique to a generic i-DMVRP in a full-factorial computational study and comparing the results with observations in existing literature, we show that the technique contributes to better explaining algorithmic performance and provides guidance for the algorithm selection and development process. • 1st explainability technique for decomposition-based solution approaches for i-DMVRPs. • Identification of fundamental OC approximation error types. • Guidance for algorithm development.