The time-dependent shortest path and vehicle routing problem

DC FieldValueLanguage
dc.contributor.authorJaballah, Rabie-
dc.contributor.authorVeenstra, Marjolein-
dc.contributor.authorCoelho, Leandro C.-
dc.contributor.authorRenaud, Jacques-
dc.coverage.spatialQuébec (Province) -- Québecfr
dc.description.abstractWe 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
dc.publisherTaylor & Francis Groupfr
dc.subjectTime-dependent vehicle routing problemfr
dc.subjectTime-dependent shortest path problemfr
dc.subjectSimulated annealingfr
dc.titleThe time-dependent shortest path and vehicle routing problemfr
dc.typeCOAR1_1::Texte::Périodique::Revue::Contribution à un journal::Article::Article de recherchefr
dcterms.bibliographicCitationINFOR. Information systems and operational research, (2021)fr
dc.subject.rvmProblèmes de tournéesfr
dc.subject.rvmRecuit simuléfr
rioxxterms.versionAccepted Manuscriptfr
rioxxterms.project.funder_nameDutch Institute for Advanced Logisticsfr
rioxxterms.project.funder_nameNatural Sciences and Engineering Research Council of Canadafr
bul.rights.periodeEmbargo12 moisfr
Collection:Articles publiés dans des revues avec comité de lecture

Files in this item:
Description SizeFormat 
3.82 MBAdobe PDF    Request a copy
All documents in CorpusUL are protected by Copyright Act of Canada.