Title | ||
---|---|---|
Branch-and-price-and-cut for the Split-collection Vehicle Routing Problem with Time Windows and Linear Weight-related Cost. |
Abstract | ||
---|---|---|
This paper addresses a new vehicle routing problem that simultaneously involves time windows, split collection and linear weight-related cost, which is a generalization of the split delivery vehicle routing problem with time windows (SDVRPTW). This problem consists of determining least-cost vehicle routes to serve a set of 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 a exact branch-and-price-and-cut algorithm, where the pricing subproblem is a resource-constrained elementary least-cost path problem. We first prove that at least an optimal solution to the pricing subproblem is associated with an extreme collection pattern, and then design a tailored and novel label-setting algorithm to solve it. Computational results show that our proposed algorithm can handle both the SDVRPTW and our problem effectively. |
Year | Venue | Field |
---|---|---|
2014 | CoRR | Mathematical optimization,Vehicle routing problem,Shortest path problem,Branch and price,Linear function,Operations management,Mathematics |
DocType | Volume | Citations |
Journal | abs/1401.6483 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Zhixing Luo | 1 | 0 | 0.34 |
Hu Qin | 2 | 201 | 16.49 |
Wenbin Zhu | 3 | 214 | 15.34 |
Andrew Lim | 4 | 937 | 89.78 |