An exact approach for a vehicle routing problem with common carrier selection

Abstract

The tariff calculations of transport requests by carriers often depend on distance, load, and/or time. In case external carriers are used for shipping, these different calculations can be used to minimize the shipper's costs. A selection of multiple carriers during an optimization process can gain cost savings compared to the planning of only single carriers. Therefore, this paper proposes an exact formulation of carrier selection between different carriers for the vehicle routing problem with time windows using additional valid inequalities, which are added in a branch-and-cut algorithm. We show that the respective tariff calculation has an impact on the solution structure and that these differences can be used to generate synergies and achieve better results than the separate consideration of single carriers.