Managing in real-time a vehicle routing plan with time-dependent travel times on a road network. (November 2021)

• Record Type: Journal Article
• Authors: Gmira, Maha; Gendreau, Michel; Lodi, Andrea; Potvin, Jean-Yves
• Is Part Of: Transportation research. Volume 132(2021)
• Publication Date: 2021-11
• Subjects: Vehicle routing -- Road network -- Dynamic travel times -- Metaheuristics -- Tabu search; Transportation -- Periodicals; Transportation -- Technological innovations -- Periodicals; 388.011
• DOI: 10.1016/j.trc.2021.103379
• Languages: English
• ISSNs: 0968-090X

Abstract

Abstract: Geographic information systems, global positioning systems, traffic flow sensors and cellular phones are sources of real-time traffic data in road networks. However, many vehicle routing algorithms do not account for this real-time information. In this paper, we consider the problem of adjusting in real-time a time-dependent delivery plan to respond to dynamic changes in travel times. We also consider a variant of the problem in which some customer requests can be canceled. The goal is to minimize disruption by maintaining as much as possible the current planned routes, although without compromising too much solution quality. Computational results obtained by solving instances with up to 500 customers are reported and compared with a strategy that maintains the planned routes, whatever the cost. Highlights: A vehicle routing problem is defined in a real urban road network. The travel times are time-dependent and are derived from real historical data. Dynamic perturbations to the time-dependent travel times are accounted for. The proposed methodology adjusts the routing plan when dynamic perturbations occur. Both solution stability and solution quality are taken into account.