Cover Image

Arc Routing with Time-Dependent Travel Times and Paths

Q1

Saved in:
Bibliographic Details
Main Author: Vidal, Thibaut
Other Authors: Martinelli, Rafael
Format: Article
Language:English
Published: Transportation Science 2021
Online Access:https://pubsonline.informs.org/doi/10.1287/trsc.2020.1035
https://dlib.phenikaa-uni.edu.vn/handle/PNK/1771
https://doi.org/10.1287/trsc.2020.1035
Tags: Add Tag
No Tags, Be the first to tag this record!
id oai:localhost:PNK-1771
record_format dspace
spelling oai:localhost:PNK-17712022-08-17T05:54:42Z Arc Routing with Time-Dependent Travel Times and Paths Vidal, Thibaut Martinelli, Rafael Pham, Tuan Anh Hà, Minh Hoàng Q1 Vehicle routing algorithms usually reformulate the road network into a complete graph in which each arc represents the shortest path between two locations. Studies on time-dependent routing followed this model and therefore defined the speed functions on the complete graph. We argue that this model is often inadequate, in particular for arc routing problems involving services on edges of a road network. To fill this gap, we formally define the time-dependent capacitated arc routing problem (TDCARP), with travel and service speed functions given directly at the network level. Under these assumptions, the quickest path between locations can change over time, leading to a complex problem that challenges the capabilities of current solution methods. We introduce effective algorithms for preprocessing quickest paths in a closed form, efficient data structures for travel time queries during routing optimization, and heuristic and exact solution approaches for the TDCARP. Our heuristic uses the hybrid genetic search principle with tailored solution-decoding algorithms and lower bounds for filtering moves. Our branch-and-price algorithm exploits dedicated pricing routines, heuristic dominance rules, and completion bounds to find optimal solutions for problems counting up to 75 services. From these algorithms, we measure the benefits of time-dependent routing optimization for different levels of travel-speed data accuracy. 2021-06-15T04:38:36Z 2021-06-15T04:38:36Z 2021 Article Working Paper https://pubsonline.informs.org/doi/10.1287/trsc.2020.1035 https://dlib.phenikaa-uni.edu.vn/handle/PNK/1771 https://doi.org/10.1287/trsc.2020.1035 en Transportation Science
institution Digital Phenikaa
collection Digital Phenikaa
language English
description Q1
author2 Martinelli, Rafael
author_facet Martinelli, Rafael
Vidal, Thibaut
format Article
author Vidal, Thibaut
spellingShingle Vidal, Thibaut
Arc Routing with Time-Dependent Travel Times and Paths
author_sort Vidal, Thibaut
title Arc Routing with Time-Dependent Travel Times and Paths
title_short Arc Routing with Time-Dependent Travel Times and Paths
title_full Arc Routing with Time-Dependent Travel Times and Paths
title_fullStr Arc Routing with Time-Dependent Travel Times and Paths
title_full_unstemmed Arc Routing with Time-Dependent Travel Times and Paths
title_sort arc routing with time-dependent travel times and paths
publisher Transportation Science
publishDate 2021
url https://pubsonline.informs.org/doi/10.1287/trsc.2020.1035
https://dlib.phenikaa-uni.edu.vn/handle/PNK/1771
https://doi.org/10.1287/trsc.2020.1035
_version_ 1751856251682160640
score 8.881002

Similar Items