Branch-Price-and-Cut for the Vehicle Routing Problem With Simultaneous Delivery and Pickup, Time Windows, and Load-Dependent Cost

The vehicle routing problem with load-dependent cost is an extension of the classical capacitated vehicle routing problem in which the cost of traveling along an arc is dependent on the load carried by the vehicle. For the benefit of generalization, this work considers the vehicle routing problem with simultaneous delivery and pickup, time windows, and load-dependent cost (VRPSDPTW-LDC). We utilize both continuous and discontinuous monotonically non-decreasing load-dependent cost functions. These cost structures are justified by real-life applications: First and foremost, transportation cost rises in load due to increasing fuel cost. In addition, cost functions may also show discontinuities due to toll-by-weight schemes, weight restricted passage, and lift axles that may be raised when the vehicle is empty or lightly loaded, therefore decreasing tire wear. We employ a fully equipped branch-price-and-cut algorithm to solve the VRPSDPTW-LDC. A major complication in its development is the consistent handling of the load-dependent cost in the column generation subproblem when solved by bidirectional labeling algorithms. Indeed, in the VRPSDPTW-LDC, the precise load on board is not known when a partial path is constructed. We provide a unifying description of the associated resource extension function for forward and backward labeling. In several computational experiments, we analyze algorithmic components of the branch-price-and-cut algorithm, and give managerial insights on the impact of the cost structure on key metrics such as total cost, the number of routes, and the average load carried in an optimal solution.