Cost Allocation in Vehicle Routing Problems with Time Windows

Abstract

The estimation of costs allocated to each customer when serving them in a collaborative logistic operation is a complex problem whose solution is computationally very expensive. In this work the case of central horizontal collaboration for vehicle routing problems with time windows and a central depot is studied. An approximation to the Shapley value method via structured random sampling is used to calculate the cost associated with customers in Solomon instances. Such costs are regressed to a linear model with a set of defined features. The results show that cost can be predicted with considerable accuracy with few features. Moreover, the extent to which vehicles’ capacity, customers’ demand and distance, the degree of customer clustering and time window horizons affect cost and potential savings from carriers in collaboration is assessed. Additionally, individual regression models of different set of instances show how various pricing strategies for customers can be fitted to their classification when grouping them.

Keywords: collaborative vehicle routing; cost allocation; Shapley value method; structured random sampling; time windows