New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem

Roberto Baldacci, Aristide Mingozzi, Roberto Roberti

Research output: Contribution to journalJournal articleResearchpeer-review

993 Downloads (Pure)

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.
Original languageEnglish
Journal4 O R
Volume59
Issue number5
Pages (from-to)1269-1283
Number of pages15
ISSN1619-4500
DOIs
Publication statusPublished - 2011
Externally publishedYes

Keywords

  • Computer Science Applications
  • Management Science and Operations Research
  • Capacitated vehicle routing problem
  • Dual solutions
  • Exact algorithms
  • Exact methods
  • Generation algorithm
  • LP-relaxation
  • New strategy
  • Optimal solutions
  • Pricing problems
  • Pricing strategy
  • Running time
  • Set partitioning
  • State-of-the-art algorithms
  • Subject classification
  • Time windows
  • Valid inequality
  • Vehicle routing problem with time windows
  • Vehicle Routing Problems
  • Algorithms
  • Integer programming
  • Network routing
  • Optimization
  • Routing algorithms
  • Vehicle routing
  • Vehicles
  • Problem solving
  • VEHICLE routing problem
  • OPERATIONS
  • MANAGEMENT
  • SHORTEST-PATH PROBLEM
  • TIME WINDOWS
  • EXACT ALGORITHM
  • OPTIMIZATION ALGORITHM
  • RESOURCE CONSTRAINTS
  • TABU SEARCH
  • INEQUALITIES
  • FORMULATION
  • CUTS

Fingerprint Dive into the research topics of 'New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem'. Together they form a unique fingerprint.

Cite this