← Search

New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem

Roberto Baldacci¹; Aristide Mingozzi²; Roberto Roberti³

¹ Department of Electronics, Computer Science and Systems, University of Bologna, 47521 Cesena, Italy · ² Department of Mathematics, University of Bologna, 47521 Cesena, Italy · ³ DEIS, University of Bologna, 40136 Bologna, Italy

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.

DOI

10.1287/opre.1110.0975

Volume

59 (5)

Pages

1269-1283

Language

en

Export

BibTeX

Sources

crossref