New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem

Roberto Baldacci (), Aristide Mingozzi () and Roberto Roberti ()
Additional contact information
Roberto Baldacci: Department of Electronics, Computer Science and Systems, University of Bologna, 47521 Cesena, Italy
Aristide Mingozzi: Department of Mathematics, University of Bologna, 47521 Cesena, Italy
Roberto Roberti: DEIS, University of Bologna, 40136 Bologna, Italy

Operations Research, 2011, vol. 59, issue 5, 1269-1283

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: vehicle routing; time windows; dual ascent heuristic; column-and-cut generation (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (173)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1110.0975 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:59:y:2011:i:5:p:1269-1283

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().