Resource-Window Reduction by Reduced Costs in Path-Based Formulations for Routing and Scheduling Problems

Publikationstyp:
Zeitschriftenaufsatz
Metadaten:
Autoren
  • Nicola Bianchessi
  • Timo Gschwind
  • Stefan Irnichb
Autoren-URL
https://www.webofscience.com/api/gateway?GWVersion=2&SrcApp=fis-test-1&SrcAuth=WosAPI&KeyUT=WOS:001068819400001&DestLinkType=FullRecord&DestApp=WOS_CPL
DOI
10.1287/ijoc.2022.0214
eISSN
1526-5528
Externe Identifier
  • Clarivate Analytics Document Solution ID: JR3K4
ISSN
1091-9856
Ausgabe der Veröffentlichung
1
Zeitschrift
INFORMS JOURNAL ON COMPUTING
Schlüsselwörter
  • integer programming
  • column generation
  • variable fixing
  • resource windows reduction
  • vehicle routing
Datum der Veröffentlichung
2024
Status
Published
Titel
Resource-Window Reduction by Reduced Costs in Path-Based Formulations for Routing and Scheduling Problems
Sub types
  • Article
Ausgabe der Zeitschrift
36

Datenquelle: Web of Science (Lite)

Andere Metadatenquellen:
Abstract
<jats:p> Many routing and scheduling problems are modeled through variables that represent paths (routes, schedules, etc.). For such extensive formulations, branch-price-and-cut (BPC) algorithms nowadays constitute the leading exact solution technique, and most of the time, the pricing problem is a shortest-path problem with resource constraints that can be solved by a dynamic-programming labeling algorithm. For this setting, variable fixing techniques based on the reduced costs of the paths have been proposed with the aim of eliminating arcs from the underlying network and speeding up the solution process of the pricing problem as well as of the overall BPC algorithm. For an efficient variable fixation, bidirectional labeling must be possible. We move one step forward and show how the reduced costs of paths can also be exploited to reduce the resource windows for many types of resources, including the time resource and a load-related resource. This can be achieved without modifying the pricing problem network and altering the structure of the pricing problem itself. Moreover, different resources can be considered simultaneously. A straightforward reduction of the resource windows associated with the vertices of the network can tighten them, but this reduction does not translate into savings in computation times. On the contrary, the reduction of the resource windows is effective when distinct forward and backward resource windows are defined for each arc and reduced independently based on the traversal direction of the arc itself. Moreover, an arc can be eliminated when one of its arc-specific resource windows becomes empty, and the explicit use of variable fixing techniques can be avoided. Computational results obtained for benchmark instances of the vehicle-routing problem with time windows show that the overall computation times of the BPC algorithm can be significantly reduced compared with a fully fledged BPC algorithm using variable fixing techniques. </jats:p><jats:p> History: Accepted by Andrea Lodi, Area Editor for Design &amp; Analysis of Algorithms – Discrete. </jats:p><jats:p> Funding: This research was supported by the Deutsche Forschungsgemeinschaft (DFG) [Grants GS 83/1-1 and IR 122/10-1] of Project 418727865. This support is gratefully acknowledged. </jats:p>
Autoren
  • Nicola Bianchessi
  • Timo Gschwind
  • Stefan Irnich
DOI
10.1287/ijoc.2022.0214
eISSN
1526-5528
ISSN
1091-9856
Ausgabe der Veröffentlichung
1
Zeitschrift
INFORMS Journal on Computing
Sprache
en
Paginierung
224 - 244
Datum der Veröffentlichung
2024
Status
Published
Herausgeber
Institute for Operations Research and the Management Sciences (INFORMS)
Herausgeber URL
http://dx.doi.org/10.1287/ijoc.2022.0214
Datum der Datenerfassung
2024
Titel
Resource-Window Reduction by Reduced Costs in Path-Based Formulations for Routing and Scheduling Problems
Ausgabe der Zeitschrift
36

Datenquelle: Crossref

Beziehungen:
Eigentum von

Werkzeuge