Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2506.10017 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911025574445056 |
|---|---|
| author | Samanta, Sukanya |
| author_facet | Samanta, Sukanya |
| contents | Intercepting a criminal using limited police resources presents a significant challenge in dynamic crime environments, where the criminal's location continuously changes over time. The complexity is further heightened by the vastness of the transportation network. To tackle this problem, we propose a layered graph representation, in which each time step is associated with a duplicate of the transportation network. For any given set of attacker strategies, a near-optimal defender strategy is computed using the A-Star heuristic algorithm applied to the layered graph. The defender's goal is to maximize the probability of successful interdiction. We evaluate the performance of the proposed method by comparing it with a Mixed-Integer Linear Programming (MILP) approach used for the defender. The comparison considers both computational efficiency and solution quality. The results demonstrate that our approach effectively addresses the complexity of the problem and delivers high-quality solutions within a short computation time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_10017 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Design of A* based heuristic algorithm for efficient interdiction in multi-Layer networks Samanta, Sukanya Social and Information Networks Multiagent Systems Optimization and Control Intercepting a criminal using limited police resources presents a significant challenge in dynamic crime environments, where the criminal's location continuously changes over time. The complexity is further heightened by the vastness of the transportation network. To tackle this problem, we propose a layered graph representation, in which each time step is associated with a duplicate of the transportation network. For any given set of attacker strategies, a near-optimal defender strategy is computed using the A-Star heuristic algorithm applied to the layered graph. The defender's goal is to maximize the probability of successful interdiction. We evaluate the performance of the proposed method by comparing it with a Mixed-Integer Linear Programming (MILP) approach used for the defender. The comparison considers both computational efficiency and solution quality. The results demonstrate that our approach effectively addresses the complexity of the problem and delivers high-quality solutions within a short computation time. |
| title | Design of A* based heuristic algorithm for efficient interdiction in multi-Layer networks |
| topic | Social and Information Networks Multiagent Systems Optimization and Control |
| url | https://arxiv.org/abs/2506.10017 |