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

Michael Saint-Guillain, Célia Paquay and Sabine Limbourg

European Journal of Operational Research, 2021, vol. 292, issue 3, 869-885

Abstract: 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.

Keywords: Routing; Stochastic programming; On-demand transportation; Optimization under uncertainty; Recourse strategies (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722172030953X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:292:y:2021:i:3:p:869-885

DOI: 10.1016/j.ejor.2020.11.007

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().