Time-dependent stochastic vehicle routing problem with random requests: Application to online police patrol management in Brussels

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.