New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem
Top Cited Papers
- 1 October 2011
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 59 (5), 1269-1283
- https://doi.org/10.1287/opre.1110.0975
Abstract
In this paper, we describe an effective exact method for solving both the capacitated vehicle routing problem (cvrp) and the vehicle routing problem with time windows (vrptw) that improves the method proposed by Baldacci et al. [Baldacci, R., N. Christofides, A. Mingozzi. 2008. An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Math. Programming 115(2) 351–385] for the cvrp. The proposed algorithm is based on the set partitioning (SP) formulation of the problem. We introduce a new route relaxation called ng-route, used by different dual ascent heuristics to find near-optimal dual solutions of the LP-relaxation of the SP model. We describe a column-and-cut generation algorithm strengthened by valid inequalities that uses a new strategy for solving the pricing problem. The new ng-route relaxation and the different dual solutions achieved allow us to generate a reduced SP problem containing all routes of any optimal solution that is finally solved by an integer programming solver. The proposed method solves four of the five open Solomon's vrptw instances and significantly improves the running times of state-of-the-art algorithms for both vrptw and cvrp.Keywords
This publication has 21 references indexed in Scilit:
- An exact solution framework for a broad class of vehicle routing problemsComputational Management Science, 2010
- A dual ascent procedure for the set partitioning problemDiscrete Optimization, 2008
- New dynamic programming algorithms for the resource constrained elementary shortest path problemNetworks, 2007
- An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cutsMathematical Programming, 2007
- A general heuristic for vehicle routing problemsComputers & Operations Research, 2007
- Vehicle Routing Problem with elementary shortest path based column generationComputers & Operations Research, 2006
- The multiple disposal facilities and multiple inventory locations rollon–rolloff vehicle routing problemComputers & Operations Research, 2006
- An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problemsNetworks, 2004
- A new branch-and-cut algorithm for the capacitated vehicle routing problemMathematical Programming, 2004
- Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxationsMathematical Programming, 1981