The shortest-path problem with resource constraints and k-cycle elimination for k ≥ 3
- Publikationstyp:
- Zeitschriftenaufsatz
- Metadaten:
-
- Autoren
- Stefan Irnich
- Daniel Villeneuve
- Autoren-URL
- https://www.webofscience.com/api/gateway?GWVersion=2&SrcApp=fis-test-1&SrcAuth=WosAPI&KeyUT=WOS:000240375700010&DestLinkType=FullRecord&DestApp=WOS_CPL
- DOI
- 10.1287/ijoc.1040.0117
- eISSN
- 1526-5528
- Externe Identifier
- Clarivate Analytics Document Solution ID: 082GW
- ISSN
- 1091-9856
- Ausgabe der Veröffentlichung
- 3
- Zeitschrift
- INFORMS JOURNAL ON COMPUTING
- Schlüsselwörter
- shortest paths
- cycle elimination
- column generation
- vehicle routing
- Paginierung
- 391 - 406
- Datum der Veröffentlichung
- 2006
- Status
- Published
- Titel
- The shortest-path problem with resource constraints and <i>k</i>-cycle elimination for <i>k</i> ≥ 3
- Sub types
- Article
- Ausgabe der Zeitschrift
- 18
Datenquelle: Web of Science (Lite)
- Andere Metadatenquellen:
-
- Abstract
- <jats:p> 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. </jats:p>
- Autoren
- Stefan Irnich
- Daniel Villeneuve
- DOI
- 10.1287/ijoc.1040.0117
- eISSN
- 1526-5528
- ISSN
- 1091-9856
- Ausgabe der Veröffentlichung
- 3
- Zeitschrift
- INFORMS Journal on Computing
- Sprache
- en
- Paginierung
- 391 - 406
- Datum der Veröffentlichung
- 2006
- Status
- Published
- Herausgeber
- Institute for Operations Research and the Management Sciences (INFORMS)
- Herausgeber URL
- http://dx.doi.org/10.1287/ijoc.1040.0117
- Datum der Datenerfassung
- 2023
- Titel
- The Shortest-Path Problem with Resource Constraints and <i>k</i>-Cycle Elimination for <i>k</i> ≥ 3
- Ausgabe der Zeitschrift
- 18
Datenquelle: Crossref
- Autoren
- Stefan Irnich
- Daniel Villeneuve
- DOI
- 10.1287/ijoc.1040.0117
- Zeitschrift
- INFORMS J. Comput.
- Artikelnummer
- 3
- Paginierung
- 391 - 406
- Datum der Veröffentlichung
- 2006
- Titel
- The Shortest-Path Problem with Resource Constraints and k-Cycle Elimination for k 3.
- Ausgabe der Zeitschrift
- 18
Datenquelle: DBLP
- Beziehungen:
- Eigentum von