We consider a timing problem arising from a vehicle routing context: it consists of optimally inserting rest periods of given duration into drivers’ schedules, when the sequence of customers to visit is given, time windows are associated with customers and an upper limit is imposed on the driving time with no rest periods. We illustrate some properties that allow reformulating the problem in simpler terms, and provide the basis to design a very efficient exact optimization algorithm whose worst-case time complexity is O(nlogn), where n is the number of customers to be visited.
An Efficient Timing Algorithm for Drivers with Rest Periods / G. Righini, M. Trubian (LECTURE NOTES IN COMPUTER SCIENCE). - In: ISCO Combinatorial optimization / [a cura di] A. Basu, A. R. Mahjoub, J. J. Salazar González. - [s.l] : Springer, 2024. - ISBN 9783031609237. - pp. 376-387 (( Intervento presentato al 8. convegno International Symposium on Combinatorial Optimization : 22 through 24 May tenutosi a Tenerife nel 2024 [10.1007/978-3-031-60924-4_28].
An Efficient Timing Algorithm for Drivers with Rest Periods
G. RighiniPrimo
;M. TrubianUltimo
2024
Abstract
We consider a timing problem arising from a vehicle routing context: it consists of optimally inserting rest periods of given duration into drivers’ schedules, when the sequence of customers to visit is given, time windows are associated with customers and an upper limit is imposed on the driving time with no rest periods. We illustrate some properties that allow reformulating the problem in simpler terms, and provide the basis to design a very efficient exact optimization algorithm whose worst-case time complexity is O(nlogn), where n is the number of customers to be visited.File | Dimensione | Formato | |
---|---|---|---|
RighiniTrubianISCO24 v2 final.pdf
embargo fino al 22/05/2025
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
109.18 kB
Formato
Adobe PDF
|
109.18 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
978-3-031-60924-4_28.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
377.14 kB
Formato
Adobe PDF
|
377.14 kB | 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.