Arc Routing with Time-Dependent Travel Times and Paths

Thibaut Vidal (), Rafael Martinelli (), Tuan Anh Pham () and Minh Hoàng Hà ()
Additional contact information
Thibaut Vidal: Departamento de Informática, Pontifícia Universidade Católica do Rio de Janeiro, 22541-900 Gávea, Rio de Janeiro, Brazil
Rafael Martinelli: Departamento de Engenharia Industrial, Pontifícia Universidade Católica do Rio de Janeiro, 22451-900 Gávea, Rio de Janeiro, Brazil
Tuan Anh Pham: ORLab, VNU University of Engineering and Technology, Hanoi 100000, Vietnam; Military Logistics Research Center, Military Logistics Academy, Hanoi 100000, Vietnam
Minh Hoàng Hà: ORLab, Faculty of Computer Science, Phenikaa University, Hanoi 100000, Vietnam

Transportation Science, 2021, vol. 55, issue 3, 706-724

Abstract: 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.

Keywords: arc routing problem; time-dependent travel times; combinatorial optimization (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2020.1035 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:55:y:2021:i:3:p:706-724

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().