This paper addresses a new vehicle routing problem that simultaneously involves time windows, split delivery, and linear weight-related cost. This problem is a generalization of the split delivery vehicle routing problem with time windows (SDVRPTW), which consists of determining a set of least-cost vehicle routes to serve all customers while respecting the restrictions of vehicle capacity and time windows. The travel cost per unit distance is a linear function of the vehicle weight and the customer demand can be fulfilled by multiple vehicles. To solve this problem, we propose an exact branch-and-price-and-cut algorithm, where the pricing subproblem is a variant of the resource-constrained elementary shortest path problem. We first prove that at least one optimal solution to the pricing subproblem is associated with an extreme delivery pattern, and then we design a tailored and novel label-setting algorithm to solve the pricing subproblem. Computational results show that our proposed algorithm can handle both the SDVRPTW and our new problem effectively.
Branch and Price and Cut for the Split-Delivery Vehicle Routing Problem with Time Windows and Linear Weight-Related Cost
Transportation science ; 51 , 2
2017
Aufsatz (Zeitschrift)
Englisch
Lokalklassifikation TIB: | 770/1935/7000 | |
BKL: | 55.80 / 55.80 Verkehrswesen, Transportwesen: Allgemeines |
British Library Online Contents | 2017
|Branch and Price for the Time-Dependent Vehicle Routing Problem with Time Windows
Online Contents | 2013
|Branch and Price for the Time-Dependent Vehicle Routing Problem with Time Windows
British Library Online Contents | 2013
|