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.
Resource-Window Reduction by Reduced Costs in Path-Based Formulations for Routing and Scheduling Problems / N. Bianchessi, T. Gschwind, S. Irnich. - In: INFORMS JOURNAL ON COMPUTING. - ISSN 1091-9856. - 36:1(2024 Feb), pp. 224-244. [10.1287/ijoc.2022.0214]
Resource-Window Reduction by Reduced Costs in Path-Based Formulations for Routing and Scheduling Problems
N. Bianchessi
Primo
;
2024
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
main-internalreport-2022-07-15.pdf
accesso aperto
Descrizione: Article - pre-print
Tipologia:
Pre-print (manoscritto inviato all'editore)
Dimensione
680.31 kB
Formato
Adobe PDF
|
680.31 kB | Adobe PDF | Visualizza/Apri |
main-submission_2023_07_06.pdf
accesso aperto
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
882.6 kB
Formato
Adobe PDF
|
882.6 kB | Adobe PDF | Visualizza/Apri |
bianchessi-et-al-2023-final.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
3.17 MB
Formato
Adobe PDF
|
3.17 MB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.