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. Righini
Primo
;
M. Trubian
Ultimo
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.
Time window constraints; Timing problem;
Settore MATH-06/A - Ricerca operativa
2024
Book Part (author)
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/1121879
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact