An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems
NetworksPublished 12 August 2004
Dominique Feillet, Pierre Dejax, Michel Gendreau, Cyrille Gueguen
Citations665
SJR quartileQ1
SJR score0.87
SNIP1.24
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An exact solution procedure is proposed for the ESPPRC, which extends the classical label correcting algorithm originally developed for the relaxed (nonelementary) path version of this problem.
Abstract
Abstract In this article, we propose a solution procedure for the Elementary Shortest Path Problem with Resource Constraints (ESPPRC). A relaxed version of this problem in which the path does not have to be elementary has been the backbone of a number of solution procedures based on column generation for several important problems, such as vehicle routing and crew pairing. In many cases relaxing the restriction of an elementary path resulted in optimal solutions in a reasonable computation time. However, for a number of other problems, the elementary path restriction has too much impact on the solution to be relaxed or might even be necessary. We propose an exact solution procedure for the ESPPRC, which extends the classical label correcting algorithm originally developed for the relaxed (nonelementary) path version of this problem. We present computational experiments of this algorithm for our specific problem and embedded in a column generation scheme for the classical Vehicle Routing Problem with Time Windows. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(3), 216–229 2004
Keywords
EngineeringBusiness, Management and Accounting
Operations ResearchScheduling of Vehicles from a Central Depot to a Number of Delivery Points
3,846 Citations1964Graham Clarke, J. W. Wright
An iterative procedure is developed that enables the rapid selection of an optimum or near-optimum route and has been programmed for a digital computer but is also suitable for hand computation.
Operations ResearchA New Optimization Algorithm for the Vehicle Routing Problem with Time Windows
1,180 Citations1992Martin Desrochers, Jacques Desrosiers +1 more
This paper presents a new optimization algorithm capable of optimally solving 100-customer problems of the vehicle routing problem with time windows VRPTW and indicates that this algorithm proved to be successful on a variety of practical sized benchmark VRPTw test problems.
Operations ResearchSelected Topics in Column Generation
1,084 Citations2005Marco E. Lübbecke, Jacques Desrosiers
The growing understanding of the dual point of view is emphasized, which has brought considerable progress to the column generation theory and practice, and is an ever recurring concept in "selected topics."
Transportation ScienceTraveling Salesman Problems with Profits
617 Citations2005Dominique Feillet, Pierre Dejax +1 more
A classification of TSPs with profits is proposed, and the existing literature is surveyed, and different classes of applications, modeling approaches, and exact or heuristic solution techniques are identified and compared.
NetworksThe prize collecting traveling salesman problem
564 Citations1989Egon Balas
This paper identifies several families of facet defining inequalities for this polytope, the convex hull of solutions to the PCTSP, and uses these inequalities either as cutting planes or as ingredients of a Lagrangean optimand.
Management ScienceSolving Airline Crew Scheduling Problems by Branch-and-Cut
540 Citations1993Karla Hoffman, Manfred Padberg
NetworksA dual algorithm for the constrained shortest path problem
454 Citations1980Gabriel Y. Handler, Israël Zang
A Lagrangian relaxation algorithm is developed for the problem of finding a shortest path between two nodes in a network, subject to a knapsack-type constraint, which indicates orders of magnitude savings when the approach is applied to large networks.
Discrete Applied MathematicsThe selective travelling salesman problem
412 Citations1990Gilbert Laporte, Silvano Martello
Transportation Science2-Path Cuts for the Vehicle Routing Problem with Time Windows
339 Citations1999Niklas Kohl, Jacques Desrosiers +3 more
A strong valid inequality, the 2-path cut, is introduced to produce better lower bounds for the vehicle routing problem with time windows and an effective separation algorithm to find such inequalities is developed.
Operations ResearchApproximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
324 Citations1987A. R. Warburton
It is shown how approximation methods may be applied to yield fully polynomial approximation schemes for a variety of NP-complete, single-objective problems.
Operations ResearchNote on the Complexity of the Shortest Path Models for Column Generation in VRPTW
319 Citations1994Moshe Dror
It is proved that the relaxation approach in designing the subproblem of pricing out only the feasible routes for the set partition formulation of the VRPTW is justified on complexity grounds, and the first dynamic programming model presented in M. Desrochers, J. Desrosiers and M. Solomon 1992 is NP-hard in the strong sense.
NetworksAn algorithm for the resource constrained shortest path problem
317 Citations1989J. E. Beasley, N.D. Christofides
A lagrangean relaxation of the integer programming formulation of the resource constrained shortest path problem into a minimum cost network flow problem is developed which provides a lower bound for use in a tree search procedure.
CERN Document Server (European Organization for Nuclear Research)Graphes et algorithmes
294 Citations1995Michel Gondran, Michel Minoux
European Journal of Operational ResearchA new approach for crew pairing problems by column generation with an application to air transportation
204 Citations1988Sylvie Lavoie, Michel Minoux +1 more
NetworksImproved preprocessing, labeling and scaling algorithms for the Weight‐Constrained Shortest Path Problem
197 Citations2003Irina Dumitrescu, Natashia Boland
It is shown that integrating information obtained in preprocessing within the label‐setting method can lead to very substantial improvements in both memory required and run time, in some cases, by orders of magnitude.
European Journal of Operational ResearchMultiobjective transportation network design and routing problems: Taxonomy and annotation
145 Citations1993John Current, Michael T. Marsh
This paper updates an earlier review of multiobjective network design and routing problems and addresses the variety of problems addressed, which reflects the importance and complexity of transportation network analysis.
Management ScienceFlight Crew Scheduling
131 Citations1993Glenn W. Graves, Richard D. McBride +3 more
A new crew scheduling optimization system has been developed for United Airlines to permit quick response to schedule changes and to reduce crew scheduling costs.
Annals of Operations ResearchA new branching strategy for time constrained routing problems with application to backhauling
117 Citations1995Sylvie Gélinas, Martin Desrochers +2 more
A new branching strategy for branch-and-bound approaches based on column generation for the vehicle routing problems with time windows that produced an average cost decrease when backhauling was permitted as compared to the cost involved when the client and the distributor routes were distinct.
Parallelization of the Vehicle Routing Problem with Time Windows
109 Citations1999Jesper Larsen
Operations research, computer science. Interface seriesAccelerating Strategies in Column Generation Methods for Vehicle Routing and Crew Scheduling Problems
101 Citations2002Guy Desaulniers, Jacques Desrosiers +1 more
This paper presents recent methods directed at the integer programming aspect of the approach that were instrumental in substantially reducing the integrality gap found in certain applications, thereby helping to efficiently produce excellent quality solutions.
Rice University's digital scholarship archive (Rice University)A Parallel Cutting-Plane Algorithm for the Vehicle Routing Problem with Time Windows
93 Citations1999William J. Cook, Jennifer Lynn Rich
SciDok (Saarland University and State Library)Constrained shortest paths and related problems
70 Citations2001Mark Ziegelmann
NetworksThe prize collecting traveling salesman problem: II. Polyhedral results
55 Citations1995Egon Balas
The facial structure of the PCTS polytope, the convex hull of solutions to the PctS problem, is addressed and a general method for deriving a facet defining inequality for the P CTSpolytope from any facet defining equality for the Asymmetric Traveling SalesmanPolytope is given.
Méthodes de résolution exacte pour les problèmes de tournées de véhicules
28 Citations1999Cyrille Gueguen