A scenario‐based heuristic for a car patrolling problem with time windows and stochastic alarms
International Transactions in Operational Research · 17.11.2026
DOI: 10.1111/itor.70298 ↗Kurz gefasst
Fachartikel in der Zeitschrift International Transactions in Operational Research, online erschienen am 17.11.2026. Verfasst von Victor Hugo Vidigal Corrêa und 3 weiteren Autor:innen. Die Arbeit nennt 48 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
This paper addresses a stochastic variant of the car patrolling problem, in which unexpected alarms introduce uncertainty into route planning for private security services provided by a large Italian company. Each customer has different weekly demands (i.e., services), which can be optional or mandatory. Some services (i.e., alarms) are not known in advance and are thus treated as stochastic information. The company is concerned about providing an immediate response to alarms triggered during a patrol. The objective is to determine a set of patrol routes, one per day, that comply with several operational constraints, including hard time windows, maximum riding time, the minimum number of services performed, and the uncertainty regarding alarm triggers. Since our interest is in solving real‐world instances, we propose a scenario‐based iterated local search heuristic. It incorporates diverse operators, along with a local search and recourse function, to guide the search toward robust solutions. Computational experiments demonstrate that solutions that ignore unexpected alarms frequently deteriorate under stochastic evaluation, with losses exceeding 16% in some cases. In contrast, the proposed heuristic improves both robustness and solution quality, resulting in gains of up to 7% and reducing service cancellations. Further analysis demonstrates the sensitivity of solution performance to scenario diversity and sample size, highlighting the importance of carefully selecting scenarios that reflect alarm occurrences.
Zitieren
APA
Corrêa, V. H. V., Santos, A. G. D., Zucchi, G., & Queiroz, T. A. D. (2026). A scenario‐based heuristic for a car patrolling problem with time windows and stochastic alarms. International Transactions in Operational Research. https://doi.org/10.1111/itor.70298
Vancouver
Corrêa VHV, Santos AGD, Zucchi G, Queiroz TAD. A scenario‐based heuristic for a car patrolling problem with time windows and stochastic alarms. International Transactions in Operational Research. 2026. doi:10.1111/itor.70298
BibTeX
@article{Corra2026,
author = {Corrêa, Victor Hugo Vidigal and Santos, André Gustavo dos and Zucchi, Giorgio and Queiroz, Thiago Alves de},
title = {A scenario‐based heuristic for a car patrolling problem with time windows and stochastic alarms},
journal = {International Transactions in Operational Research},
year = {2026},
doi = {10.1111/itor.70298}
}
EUVIMED