On the Concept of Opportunity Cost in Integrated Demand Management and Vehicle Routing

Integrated demand management and vehicle routing problems are characterized by a stream of customer requests arriving dynamically over a booking horizon and requesting logistical services, which are fulfilled by a given fleet of vehicles during a service horizon. Prominent examples are attended home delivery and same-day delivery problems, where customer requests commonly have heterogeneous characteristics and differ in profitability. Thus, demand management methods are integrated to steer the booking process to maximize total profit. In traditional demand management problems, this is typically done under consideration of opportunity cost as a measure for request profitability. The idea behind this is to only accept customer requests that have at least the contribution of all customer requests they displace. Consequently, the estimation of opportunity cost is an essential component of any demand management approach. In the context of integrated demand management and vehicle routing problems, such an estimation differs substantially from the estimation in traditional demand management applications. This is due to the routing component as it inhibits a clear quantification and attribution of cost, and of displaced revenue, to certain customer requests. Therefore, we formalize an opportunity cost definition specifically tailored for integrated demand management and vehicle routing problems. We define a generic Markov decision process model for which we then formally investigate and prove opportunity cost properties. Further, we discuss implications for approximation approaches and managerial insights