In this paper we study a property of time-dependent graphs, dubbed "path ranking invariance". Broadly speaking, a time-dependent graph is "path ranking invariant" if the ordering of its paths (w.r.t. travel time) is independent of the start time. In this paper we show that, if a graph is path ranking invariant, the solution of a large class of time-dependent vehicle routing problems can be obtained by solving suitably defined (and simpler) time-independent routing problems. We also show how this property can be checked by solving a linear program. If the check fails, the solution of the linear program can be used to determine a tight lower bound. In order to assess the value of these insights, the lower bounds have been embedded into an enumerative scheme. Computational results on the time-dependent versions of the Travelling Salesman Problem and the Rural Postman Problem show that the new findings enable to outperform state-of-the-art algorithms.

On path ranking in time-dependent graphs

Adamo, T.;Ghiani, G.;Guerriero, E.
2021-01-01

Abstract

In this paper we study a property of time-dependent graphs, dubbed "path ranking invariance". Broadly speaking, a time-dependent graph is "path ranking invariant" if the ordering of its paths (w.r.t. travel time) is independent of the start time. In this paper we show that, if a graph is path ranking invariant, the solution of a large class of time-dependent vehicle routing problems can be obtained by solving suitably defined (and simpler) time-independent routing problems. We also show how this property can be checked by solving a linear program. If the check fails, the solution of the linear program can be used to determine a tight lower bound. In order to assess the value of these insights, the lower bounds have been embedded into an enumerative scheme. Computational results on the time-dependent versions of the Travelling Salesman Problem and the Rural Postman Problem show that the new findings enable to outperform state-of-the-art algorithms.
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0305054821002008-main.pdf

solo utenti autorizzati

Descrizione: Articolo
Tipologia: Versione editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 828.07 kB
Formato Adobe PDF
828.07 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/11587/513206
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 3
social impact