# On path ranking in time-dependent graphs

arXiv: https://arxiv.org/abs/2009.07588 · HTML: https://mlsanity.com/paper/2009.07588/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Sep 2020.

## Built on by (most cited first, 1 of 1)

- [Learned upper bounds for the Time-Dependent Travelling Salesman Problem](https://mlsanity.com/paper/2107.13641/) (2021)

## Abstract (arXiv)

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 textitTravelling Salesman Problem and the textitRural Postman Problem show that the new findings allow to outperform state-of-the-art algorithms.