The time-dependent shortest path and vehicle routing problem

Auteur(s): Jaballah, Rabie; Veenstra, Marjolein; Coelho, Leandro C.Renaud, Jacques
Résumé: We introduce the time-dependent shortest path and vehicle routing problem. In this problem, a set of homogeneous vehicles is used to visit a set of customer locations dispersed over a very large network where the travel times are time-dependent and therefore the shortest path between two locations may change over time. The aim of the problem is to simultaneously determine the sequence in which the customer locations are visited and the arcs traveled on the paths between each pair of consecutively visited customers, such that the total travel time is minimized. We are the first to formally define and solve this fully integrated problem, providing tight bounds to it. We then propose a dynamic time-dependent shortest path algorithm embedded within a simulated annealing metaheuristic to efficiently solve the problem. We also propose a variant of the algorithm where some time-dependent shortest paths are precomputed. We test our formulations and algorithms on a set of real-life instances generated from a dataset of the road network in Québec City, Canada. Our results indicate that the resulting models are too large to be solved even for small instances. However, the obtained bounds show that the developed simulated annealing heuristic performs very well. We also demonstrate that neglecting time-dependent information on traffic leads to imprecise estimation of the traveling time. Moreover, the results show the importance of solving the shortest paths and routing problems simultaneously, as using a set of precomputed shortest paths leads to slightly worse solutions. This work adds new research avenues to city logistics and congestion studies.
Type de document: Article de recherche
Date de publication: 11 septembre 2021
Date de la mise en libre accès: 11 septembre 2022
Version du document: AM
Lien permanent:
Ce document a été publié dans: INFOR. Information systems and operational research, (2021)
Taylor & Francis Group
Autre version disponible: 10.1080/03155986.2021.1973785
Collection :Articles publiés dans des revues avec comité de lecture

Fichier(s) :
Description TailleFormat 
3.82 MBAdobe PDF    Demander une copie
Tous les documents dans CorpusUL sont protégés par la Loi sur le droit d'auteur du Canada.