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

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

Authors

Institutions

Publication Details

Journal
International Transactions in Operational Research
Published
2026-11-17
DOI
https://doi.org/10.1111/itor.70298
Primary Topic
Vehicle Routing Optimization Methods
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

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

Giorgio Zucchi, Thiago Alves de Queiroz, Victor Hugo Vidigal Corrêa, André Gustavo dos Santos
International Transactions in Operational Research
Vehicle Routing Optimization Methods
article

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

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

Abstract

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

International Transactions in Operational Research
University of Modena and Reggio Emilia (IT), Universidade Federal de Viçosa (BR), Re Lab (Italy) (IT), Universidade Federal de Goiás (BR)
Vehicle Routing Optimization Methods
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon