Routing; stochastic programming; on-demand transportation; optimization under uncertainty; recourse strategies
Résumé :
[en] The Static and Stochastic Vehicle Routing Problem with Random Requests (SS-VRP-R) describes
realistic operational contexts in which a fleet of vehicles has to serve customer requests appearing dynamically. Based on a probabilistic knowledge about the appearance of requests, the SS-VRP-R seeks a priori sequences of vehicle relocations, optimizing the expected responsiveness to the requests. In this paper, an existing computational framework, based on recourse strategies, is adapted to meet the objectives of the SS-VRP-R. The resulting models are applied to a real case study of the management of police units in Brussels. In this context, the expected average response time is minimized. To cope with the reality of the urban context, a time-dependent variant is also studied (TD-SS-VRP-R) in which the travel time between two locations is a function that depends on the departure time at the first location. Experiments confirm the contribution and the adaptability of the recourse strategies to a real-life, complex operational context. Provided an adequate solution method, simulation-based results show the high quality of the a priori solutions designed, even when compared to those designed by field experts. Finally, the experiments provide evidence that there is no potential gain in considering time-dependency in such an operational context.
Ahn, B.-H., Shin, J.-Y., Vehicle-routeing with time windows and time-varying congestion. Journal of the Operational Research Society 42:5 (1991), 393–400.
Bent, R.W., Van Hentenryck, P., Waiting and relocation strategies in online stochastic vehicle routing. Proceedings of the IJCAI, 2007, 1816–1821.
Bertsimas, D.J., A vehicle routing problem with stochastic demand. Operations Research 40:3 (1992), 574–585.
Boland, N.L., Savelsbergh, M.W., Perspectives on integer programming for time-dependent models. Top 27:2 (2019), 147–173.
Braga, A.A., Turchan, B.S., Papachristos, A.V., Hureau, D.M., Hot spots policing and crime reduction: An update of an ongoing systematic review and meta-analysis. Journal of Experimental Criminology 15:3 (2019), 289–311.
Brotcorne, L., Laporte, G., Semet, F., Ambulance location and relocation models. European Journal of Operational Research 147:3 (2003), 451–463.
Bélanger, V., Ruiz, A., Soriano, P., Recent optimization models and trends in location, relocation, and dispatching of emergency medical vehicles. European Journal of Operational Research 272:1 (2019), 1–23.
Chainey, S. P. (2013). Examining the influence of cell size and bandwidth size on kernel density estimation crime hotspot maps for predicting spatial patterns of crime.
Dewinter, M., Vandeviver, C., Vander Beken, T., Witlox, F., Analysing the police patrol routing problem: A review. ISPRS International Journal of Geo-Information, 9(3), 2020, 157, 10.3390/ijgi9030157.
Eglese, R.W., Maden, W., Slater, A., A road timetableTM to aid vehicle routing and scheduling. Computers & Operations Research 33:12 (2006), 3508–3519.
Fleischmann, B., Gnutzmann, S., Elke, S., Sandvoß, E., Dynamic vehicle routing based on online traffic information. Transportation Science 38:4 (2004), 420–433.
Gendreau, M., Ghiani, G., Guerriero, E., Time-dependent routing problems: A review. Computers & operations research 64 (2015), 189–197.
Gendreau, M., Jabali, O., Rei, W., Gendreau, M., Jabali, O., Future research directions in stochastic vehicle routing. Transportation Science 50:4 (2016), 1163–1173.
Gendreau, M., Laporte, G., Séguin, R., Stochastic vehicle routing. European Journal of Operational Research 88:1 (1996), 3–12.
Gendreau, M., Laporte, G., Semet, F., A dynamic model and parallel tabu search heuristic for real-time ambulance relocation. Parallel Computing 27:12 (2001), 1641–1653, 10.1016/S0167-8191(01)00103-X.
Ghiani, G., Manni, E., Quaranta, A., Triki, C., Anticipatory algorithms for same-day courier dispatching. Transportation Research Part E: Logistics and Transportation Review 45:1 (2009), 96–106, 10.1016/j.tre.2008.08.003.
Haghani, A., Yang, S., Real-time emergency response fleet deployment: Concepts, systems, simulation & case studies. 2007, SpringerLink, 133–162, 10.1007/978-0-387-71722-7_7.
Ichoua, S., Gendreau, M., Potvin, J.-Y., Vehicle dispatching with time-dependent travel times. European Journal of Operational Research 144:2 (2003), 379–396.
Ichoua, S., Gendreau, M., Potvin, J.-Y., Exploiting knowledge about future demands for real-time vehicle dispatching. Transportation Science 40:2 (2006), 211–225.
Kindervater, G.A.P., Savelsbergh, M.W.P., Vehicle routing: Handling edge exchanges. Local Search in Combinatorial Optimization, 1997, 337–360.
Kok, A.L., Hans, E.W., Schutten, J.M., Vehicle routing under time-dependent travel times: The impact of congestion avoidance. Computers & Operations Research 39:5 (2012), 910–918, 10.1016/j.cor.2011.05.027.
Li, S.R., Keskin, B.B., Bi-criteria dynamic location-routing problem for patrol coverage. Journal of the Operational Research Society 65:11 (2014), 1711–1725.
Maxwell, M.S., Restrepo, M., Henderson, S.G., Topaloglu, H., Approximate dynamic programming for ambulance redeployment. INFORMS Journal on Computing 22:2 (2010), 266–281.
Mitrović-Minić, S., Laporte, G., Waiting strategies for the dynamic pickup and delivery problem with time windows. Transportation Research Part B: Methodological 38:7 (2004), 635–655.
Naoum-Sawaya, J., Elhedhli, S., A stochastic optimization model for real-time ambulance redeployment. Computers & Operations Research 40:8 (2013), 1972–1978.
Pillac, V., Gendreau, M., Guéret, C., Medaglia, A.L., A review of dynamic vehicle routing problems. European Journal of Operational Research 225:1 (2013), 1–11.
Potvin, J.-Y., Xu, Y., Benyahia, I., Vehicle routing and scheduling with dynamic travel times. Computers & Operations Research 33:4 (2006), 1129–1137.
Psaraftis, H.N., Wen, M., Kontovas, C.A., Dynamic vehicle routing problems: Three decades and counting. Networks 67:1 (2016), 3–31.
Pureza, V., Laporte, G., Waiting and buffering strategies for the dynamic pickup and delivery problem with time windows. INFOR: Information Systems and Operational Research 46:3 (2008), 165–175, 10.3138/infor.46.3.165.
Ritzinger, U., Puchinger, J., Hartl, R.F., A survey on dynamic and stochastic vehicle routing problems. International Journal of Production Research 54:1 (2016), 215–231.
Saint-Guillain, M., Models and algorithms for online stochastic vehicle routing problems, 2019, Université catholique de Louvain (UCLouvain, Belgium); INSA Lyon (France) Ph.D. thesis.
Saint-Guillain, M., Deville, Y., Solnon, C., A multistage stochastic programming approach to the dynamic and stochastic VRPTW. Proceedings of the 12th international conference on integration of ai and or techniques in constraint programming (CPAIOR 2015), 2015, Springer International Publishing, 357–374.
Saint-Guillain, M., Solnon, C., Deville, Y., The static and stochastic vehicle routing problem with both random customers and reveal times. Proceedings of the European conference on the applications of evolutionary computation, 2, 2017, 110–127.
Schmid, V., Solving the dynamic ambulance relocation and dispatching problem using approximate dynamic programming. European Journal of Operational Research 219:3 (2012), 611–621.
Sherman, L.W., Weisburd, D., General deterrent effects of police patrol in crime “hot spots”: A randomized, controlled trial. Justice Quarterly 12:4 (1995), 625–648.
Simpson, N.C., Hancock, P.G., Fifty years of operational research and emergency response. Journal of the Operational Research Society 60:sup1 (2009), S126–S139.
Taillard, É., Badeau, P., Gendreau, M., Guertin, F., Potvin, J.-Y., A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation Science 31:2 (1997), 170–186.
Toth, P., Vigo, D., Vehicle routing: Problems, methods, and applications. 18, 2014, SIAM.
Verweij, B., Ahmed, S., Kleywegt, A.J., Nemhauser, G., Shapiro, A., The sample average approximation method applied to stochastic routing problems: a computational study. Computational Optimization and Applications 24:2–3 (2003), 289–333.
