Graph coarsening for fugitive interception
Abstract 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 calculati...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
SpringerOpen
2025-01-01
|
| Series: | Applied Network Science |
| Subjects: | |
| Online Access: | https://doi.org/10.1007/s41109-024-00689-1 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832594902530129920 |
|---|---|
| author | Irene S. van Droffelaar Jan H. Kwakkel Jelte P. Mense Alexander Verbraeck |
| author_facet | Irene S. van Droffelaar Jan H. Kwakkel Jelte P. Mense Alexander Verbraeck |
| author_sort | Irene S. van Droffelaar |
| collection | DOAJ |
| description | Abstract 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. |
| format | Article |
| id | doaj-art-5fb91647ac7c455386012ab81873a808 |
| institution | Kabale University |
| issn | 2364-8228 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | SpringerOpen |
| record_format | Article |
| series | Applied Network Science |
| spelling | doaj-art-5fb91647ac7c455386012ab81873a8082025-01-19T12:14:01ZengSpringerOpenApplied Network Science2364-82282025-01-0110112310.1007/s41109-024-00689-1Graph coarsening for fugitive interceptionIrene S. van Droffelaar0Jan H. Kwakkel1Jelte P. Mense2Alexander Verbraeck3Policy Analysis, Delft University of TechnologyPolicy Analysis, Delft University of TechnologyModel-Driven Decisions Lab, Delft University of TechnologyPolicy Analysis, Delft University of TechnologyAbstract 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.https://doi.org/10.1007/s41109-024-00689-1Graph coarseningNetwork topologyFugitive interceptionSearch problemReal-time optimization |
| spellingShingle | Irene S. van Droffelaar Jan H. Kwakkel Jelte P. Mense Alexander Verbraeck Graph coarsening for fugitive interception Applied Network Science Graph coarsening Network topology Fugitive interception Search problem Real-time optimization |
| title | Graph coarsening for fugitive interception |
| title_full | Graph coarsening for fugitive interception |
| title_fullStr | Graph coarsening for fugitive interception |
| title_full_unstemmed | Graph coarsening for fugitive interception |
| title_short | Graph coarsening for fugitive interception |
| title_sort | graph coarsening for fugitive interception |
| topic | Graph coarsening Network topology Fugitive interception Search problem Real-time optimization |
| url | https://doi.org/10.1007/s41109-024-00689-1 |
| work_keys_str_mv | AT irenesvandroffelaar graphcoarseningforfugitiveinterception AT janhkwakkel graphcoarseningforfugitiveinterception AT jeltepmense graphcoarseningforfugitiveinterception AT alexanderverbraeck graphcoarseningforfugitiveinterception |