This paper evaluates the benefits of data obtained via modern information technologies, such as global positioning systems, when solving a vehicle routing problem with dynamic customer requests and dynamic travel times. It is empirically demonstrated that substantial improvements are achieved over a previously reported model which does not assume the availability of such information. We also analyze how the system handles dynamic perturbations to the travel times that lead to earliness or lateness in the planned schedule.
Accepté le :
DOI : 10.1051/ro/2017030
Mots-clés : Routing, transportation, dynamic travel times, diversion, time windows
@article{RO_2019__53_2_401_0, author = {Respen, Jean and Zufferey, Nicolas and Potvin, Jean-Yves}, title = {Impact of vehicle tracking on a routing problem with dynamic travel times}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {401--414}, publisher = {EDP-Sciences}, volume = {53}, number = {2}, year = {2019}, doi = {10.1051/ro/2017030}, zbl = {1423.90022}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ro/2017030/} }
TY - JOUR AU - Respen, Jean AU - Zufferey, Nicolas AU - Potvin, Jean-Yves TI - Impact of vehicle tracking on a routing problem with dynamic travel times JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2019 SP - 401 EP - 414 VL - 53 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2017030/ DO - 10.1051/ro/2017030 LA - en ID - RO_2019__53_2_401_0 ER -
%0 Journal Article %A Respen, Jean %A Zufferey, Nicolas %A Potvin, Jean-Yves %T Impact of vehicle tracking on a routing problem with dynamic travel times %J RAIRO - Operations Research - Recherche Opérationnelle %D 2019 %P 401-414 %V 53 %N 2 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2017030/ %R 10.1051/ro/2017030 %G en %F RO_2019__53_2_401_0
Respen, Jean; Zufferey, Nicolas; Potvin, Jean-Yves. Impact of vehicle tracking on a routing problem with dynamic travel times. RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 2, pp. 401-414. doi : 10.1051/ro/2017030. http://www.numdam.org/articles/10.1051/ro/2017030/
[1] Waiting and Relocation Strategies in Online Stochastic Vehicle Routing. In IJCAI’07 Proc. of the 20th international joint conference on Artifical intelligence (2007) 1816–1821.
and ,[2] A General Approach for Controlling Vehicle En-Route Diversions in Dynamic Vehicle Routing Problems. Transp. Res. – Part B 77 (2015) 76–87.
and ,[3] Dynamic Vehicle Routing based on Online Traffic Information. Trans. Sci. 38 (2004) 420–433.
, and ,[4] Neighborhood Search Heuristics for a Dynamic Vehicle Dispatching Problem with Pickups and Deliveries. Transportation Research Part C: Emerging Technologies 14 (2006) 157–174.
, , and ,[5] Parallel Tabu Search for Real-Time Vehicle Routing and Dispatching. Trans. Sci. 33 (1999) 381–390. | Zbl
, , and ,[6] Dynamic Vehicle Routing and Dispatching. In Fleet Management and Logistics. Edited by and . Kluwer (1998) 115–126. | Zbl
and ,[7] A Comparison of Anticipatory Algorithms for the Dynamic and Stochastic Traveling Salesman Problem. Trans. Sci. 46 (2012) 374–387.
, and ,[8] Diversion Issues in Real-Time Vehicle Dispatching. Transp. Sci. 34 (2000) 426–438. | Zbl
, and ,[9] Vehicle Dispatching with Time-Dependent Travel Times. Eur. J. Operat. Res. 144 (2003) 379–396. | Zbl
, and ,[10] Exploiting Knowledge about Future Demands for Real-Time Vehicle Dispatching. Trans. Sci. 40 (2006) 211–225.
, and ,[11] Recent Developments in Dynamic Vehicle Routing Systems. In The Vehicle Routing Problem: Latest Advances and New Challenges, Edited by , , . In Vol. 42 of Operations Research/Computer Science Interfaces. Springer (2008) 199–218. | Zbl
, , ,[12] Online Vehicle Routing and Scheduling with Dynamic Travel Times. Comput. Oper. Res. 38 (2011) 1086–1090. | Zbl
, and ,[13] Vehicle Routing Problems with Varying Degrees of Dynamism. Technical Report IMM-REP-1996-1, Technical University of Denmark (1996).
, and ,[14] Double-Horizon Based Heuristics for the Dynamic Pickup and Delivery Problem with Time Windows. Trans. Res. Part B: Methodological 38 (2004) 669–685.
, and ,[15] A Review of Dynamic Vehicle Routing Problems. Eur. J. Oper. Res. 225 (2013) 1–11. | Zbl
, , and ,[16] Vehicle Routing and Scheduling with Dynamic Travel Times. Comput. Oper. Res. 33 (2006) 1129–1137. | Zbl
, and ,[17] Dynamic Vehicle Routing: Status and Prospects. Ann. Oper. Res. 61 (1995) 143–164. | Zbl
,[18] Dynamic Vehicle Routing Problems: Three Decades and Counting. Networks 67 (2016) 3–31.
, and ,[19] Online Vehicle Routing and Scheduling with Continuous Vehicle Tracking. In Proc. of the ROADEF 2014, Bordeaux, France. February 26 to 28 (2014).
, and[20] Algorithms for the Vehicle Routing and Scheduling Problem with Time Window Constraints. Oper. Res. 35 (1987) 254–265. | Zbl
,[21] A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows. Trans. Sci. 31 (1997) 170–186. | Zbl
, , , and ,[22] Dynamic Multi-Trip Vehicle Routing with Unusual Time-Windows for the Pick-Up of Blood Samples and Delivery of Medical Material. In Proc. of the 5th International Conference on Operations Research and Enterprise Systems (ICORES 2016), Rome, Italy (2016).
, and ,Cité par Sources :