EUVIMEDOpdag EUVIMED
Open access · CC BY 4.0

A scenario‐based heuristic for a car patrolling problem with time windows and stochastic alarms

Victor Hugo Vidigal Corrêa, André Gustavo dos Santos, Giorgio Zucchi, Thiago Alves de Queiroz

International Transactions in Operational Research · 2026-11-17

DOI: 10.1111/itor.70298 ↗

At a glance

Journal article in International Transactions in Operational Research, published online on 2026-11-17. Written by Victor Hugo Vidigal Corrêa and 3 co-authors. 48 references. The full text is freely available (open access, CC BY 4.0).

AbstractBibliografiske oplysningerCiteRelated studies

Abstract (original language)

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.

Cite

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}
}
Start for free →