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.

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.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2017030
Classification : 90B06
Mots-clés : Routing, transportation, dynamic travel times, diversion, time windows
Respen, Jean 1 ; Zufferey, Nicolas 1 ; Potvin, Jean-Yves 1

1 
@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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ro/2017030/

[1] R. Bent and P. Van Hentenryck, 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.

[2] F. Ferrucci and S. Bock, A General Approach for Controlling Vehicle En-Route Diversions in Dynamic Vehicle Routing Problems. Transp. Res. – Part B 77 (2015) 76–87.

[3] B. Fleischmann, S. Gnutzmann and E. Sandvoß, Dynamic Vehicle Routing based on Online Traffic Information. Trans. Sci. 38 (2004) 420–433.

[4] M. Gendreau, F. Guertin, J.-Y. Potvin and R. Séguin, Neighborhood Search Heuristics for a Dynamic Vehicle Dispatching Problem with Pickups and Deliveries. Transportation Research Part C: Emerging Technologies 14 (2006) 157–174.

[5] M. Gendreau, F. Guertin, J.-Y. Potvin and É. Taillard, Parallel Tabu Search for Real-Time Vehicle Routing and Dispatching. Trans. Sci. 33 (1999) 381–390. | Zbl

[6] M. Gendreau and J.-Y. Potvin, Dynamic Vehicle Routing and Dispatching. In Fleet Management and Logistics. Edited by T.G. Crainic and G. Laporte. Kluwer (1998) 115–126. | Zbl

[7] G. Ghiani, E. Manni and B.W. Thomas, A Comparison of Anticipatory Algorithms for the Dynamic and Stochastic Traveling Salesman Problem. Trans. Sci. 46 (2012) 374–387.

[8] S. Ichoua, M. Gendreau and J.-Y. Potvin, Diversion Issues in Real-Time Vehicle Dispatching. Transp. Sci. 34 (2000) 426–438. | Zbl

[9] S. Ichoua, M. Gendreau and J.-Y. Potvin, Vehicle Dispatching with Time-Dependent Travel Times. Eur. J. Operat. Res. 144 (2003) 379–396. | Zbl

[10] S. Ichoua, M. Gendreau and J.-Y. Potvin, Exploiting Knowledge about Future Demands for Real-Time Vehicle Dispatching. Trans. Sci. 40 (2006) 211–225.

[11] A. Larsen, O.B.G. Madsen, M.M. Solomon, Recent Developments in Dynamic Vehicle Routing Systems. In The Vehicle Routing Problem: Latest Advances and New Challenges, Edited by B. Golden, S. Raghavan, E. Wasil. In Vol. 42 of Operations Research/Computer Science Interfaces. Springer (2008) 199–218. | Zbl

[12] S. Lorini, J.-Y. Potvin and N. Zufferey, Online Vehicle Routing and Scheduling with Dynamic Travel Times. Comput. Oper. Res. 38 (2011) 1086–1090. | Zbl

[13] K. Lund, O.B.G. Madsen and J.M. Rygaard, Vehicle Routing Problems with Varying Degrees of Dynamism. Technical Report IMM-REP-1996-1, Technical University of Denmark (1996).

[14] S. Mitrović-Minić, R. Krishnamurti and G. Laporte, Double-Horizon Based Heuristics for the Dynamic Pickup and Delivery Problem with Time Windows. Trans. Res. Part B: Methodological 38 (2004) 669–685.

[15] V. Pillac, M. Gendreau, C. Guéret and A.L. Medaglia, A Review of Dynamic Vehicle Routing Problems. Eur. J. Oper. Res. 225 (2013) 1–11. | Zbl

[16] J.-Y. Potvin, Y. Xu and I. Benyahia, Vehicle Routing and Scheduling with Dynamic Travel Times. Comput. Oper. Res. 33 (2006) 1129–1137. | Zbl

[17] H.N. Psaraftis, Dynamic Vehicle Routing: Status and Prospects. Ann. Oper. Res. 61 (1995) 143–164. | Zbl

[18] H.N. Psaraftis, M. Wen and C.A. Kontovas, Dynamic Vehicle Routing Problems: Three Decades and Counting. Networks 67 (2016) 3–31.

[19] J. Respen, N. Zufferey and J.-Y. PotvinOnline Vehicle Routing and Scheduling with Continuous Vehicle Tracking. In Proc. of the ROADEF 2014, Bordeaux, France. February 26 to 28 (2014).

[20] M.M. Solomon, Algorithms for the Vehicle Routing and Scheduling Problem with Time Window Constraints. Oper. Res. 35 (1987) 254–265. | Zbl

[21] É. Taillard, P. Badeau, M. Gendreau, F. Guertin and J.-Y. Potvin, A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows. Trans. Sci. 31 (1997) 170–186. | Zbl

[22] N. Zufferey, B.Y. Cho and R. Glardon, 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).

Cité par Sources :