The police control room determines where to send available police units to intercept a fleeing fugitive. Models can support the police with decision-making for fugitive interception. The police have, at most, a few minutes to determine an interception strategy. Therefore, a timely calculation of the interception positions is essential to support police interception operations. The number of nodes in the network, each being a crossing where routes of the fleeing suspect can split, greatly contributes to the computation time. Graph coarsening is a promising approach to reduce the complexity of the network, and therefore the computation time. We compare four graph coarsening algorithms on five road networks and assess their impact on computation time and solution quality for the fugitive interception problem. Based on the comparison, we propose and test a new method specifically for fugitive interception. This method, Search Space Representation, improves the quality of the best solutions obtained by the optimization algorithm with up to 12%, improves the reliability of the optimization to find high-quality solutions, and decreases the number of function evaluations required to obtain high-quality solutions to 5000–10,000 depending on the size and complexity of the road network, which is feasible for real-time decision-making. Search Space Representation can be applied to reduce the computation time of other network-based optimization problems.

@en

Fugitive interception is a challenging task, requiring the police control room to decide in a matter of minutes on the optimal positions of police units to intercept a fleeing suspect. Models can support the police by suggesting interception positions. This dissertation addresses four barriers to using models for decision support in fugitive interception: timely simulation-optimization, effective representation of the search space, simulation of fugitive behavior, and adaptation to information updates.@en

Simulation–optimization models are well-suited for real-time decision-support to the control room for search and interception of fugitives by Police on a road network, due to their ability to encode complex behavior while still optimizing the interception. The typical simulation–optimization configuration is simulation model optimization, where the simulation model describes the system to be optimized, and the optimizer attempts to find the combination of decision variables that maximizes the interception probability. However, the repeated evaluation of the simulation model leads to high computation time, thus rendering it inadequate for time-constrained decision contexts. To support police interception operations in real-time, timely calculation of the solution is essential. Sequential simulation–optimization, where the simulation model, with its rich behavior, constructs (part of) the constraints of an optimization problem, could decrease the computation time. We compare the computation time for two configurations of simulation–optimization (typical simulation model optimization and sequential simulation–optimization) for various problem instances of the fugitive interception problem. We show that sequential simulation–optimization reduces the computation time of large instances of the fugitive interception case study ten-fold. This result illustrates the potential of sequential simulation–optimization to mitigate the expensive optimization of simulation models.

@en