This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Irnich, S. Articles by Villeneuve, D. Search for Related Content

The Shortest-Path Problem with Resource Constraints and k-Cycle Elimination for k 3

RWTH Aachen University, Deutsche Post Lehrstuhl für Optimierung von Distributionsnetzwerken, Templergraben 64, 52062 Aachen, Germany
Kronos Altitude Division, 3535 Queen Mary, Suite 650, Montréal, Québec, Canada H3V 1H8
sirnich{at}or.rwth-aachen.de
dvilleneuve{at}kronos.com

The elementary shortest-path problem with resource constraints (ESPPRC) is a widely used modeling tool in formulating vehicle-routing and crew-scheduling applications. The ESPPRC often occurs as a subproblem of an enclosing problem, where it is used to generate implicitly the set of all feasible routes or schedules, as in the column-generation formulation of the vehicle-routing problem with time windows (VRPTW). As the ESPPRC problem is NP-hard in the strong sense, classical solution approaches are based on the corresponding nonelementary shortest-path problem with resource constraints (SPPRC), which can be solved using a pseudo-polynomial labeling algorithm. While solving the enclosing problem by branch and price, this subproblem relaxation leads to weak lower bounds and sometimes impractically large branch-and-bound trees. A compromise between solving ESPPRC and SPPRC is to forbid cycles of small length. In the SPPRC with k-cycle elimination (SPPRC-k-cyc), paths with cycles are allowed only if cycles have length at least k + 1. The case k = 2 forbids sequences of the form i – j – i and has been successfully used to reduce integrality gaps. We propose a new definition of the dominance rule among labels for dealing with arbitrary values of k 2. The numerical experiments on the linear relaxation of some hard VRPTW instances from Solomon’s benchmark show that k-cycle elimination with k 3 can substantially improve the lower bounds of vehicle-routing problems with side constraints. The new algorithm has proven to be a key ingredient for getting exact integer solutions for well-known hard problems from the literature.

Key words: shortest paths; cycle elimination; column generation; vehicle routing
History: received August 2003; revised May 2004; accepted August 2004.

This article has been cited by other articles:

				G. Desaulniers, F. Lessard, and A. Hadjar Tabu Search, Partial Elementarity, and Generalized k-Path Inequalities for the Vehicle Routing Problem with Time Windows Transportation Science, August 1, 2008; 42(3): 387 - 404. [Abstract] [PDF]

				M. Jepsen, B. Petersen, S. Spoorendonk, and D. Pisinger Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows Operations Research, March 1, 2008; 56(2): 497 - 511. [Abstract] [PDF]