Method of routing search groups on a fixed network for effective sweeping of populated areas and searching for armed criminals
DOI:
https://doi.org/10.33405/2078-7480/2026/96/1(96)/363052Keywords:
area coverag, search teams, multi-agent system, routing, network-based object, weighted undirected (directed) graph, extreme paths, optimization criterion, methodAbstract
The method proposed in this article addresses the problem of inefficient coverage of a given urban area by search teams, which is critical for the execution of search, rescue, and monitoring tasks in crisis-affected regions of various origins. The method employs the concept of dynamic programming, which consists in the successive decomposition of the initial structure of the urban transportation network into a set of substructures. Within each substructure, an edge-simple longest/shortest path (depending on the selected strategy) between a pair of specified vertices is determined. The collection of the identified extreme paths forms a Routing Plan for the search teams, which, in a certain sense, systematizes the sweep of the urban area.
The method significantly reduces the labor and computational effort required to generate a rational variant of search operations and is intended for use by the military command and control bodies of the National Guard of Ukraine.
References
Zakon Ukrainy "Pro Natsionalnu hvardiiu Ukrainy" № 876-VII [Law of Ukraine about the National Guard of Ukraine activity no. 876-VII]. (2014, March 13). Retrieved from: https://surl.li/mzyjbr (accessed 23 January 2025) [in Ukrainian].
Morkvin D. A., Batsamut V. M., Hokh I. M. (2024). Prohnozovani vyklyky, shcho stoiatymut pered derzhavoiu u pisliavoiennyi period: zavdannia NHU iz zabezpechennia derzhavnoi bezpeky ta vykonannia pravookhoronnykh funktsii [Predicted challenges facing the state in the post-war period: tasks of the National Security Service to ensure state security and perform law enforcement functions]. Bezpeka derzhavy, no. 1, pp. 90‒98 DOI: https://doi.org/10.33405/2786-8613/2024/1/3/309959 [in Ukrainian].
Kozalietov V. V., Batsamut V. М. (2025). Problemni pytannia u diialnosti orhaniv upravlinnia Syl bezpeky pid chas planuvannia poshukovykh dii u naselenykh punktakh na deokupovanii terytorii Ukrainy: shliakhy vyrishennia [Problematic issues in the activities of security forces management bodies in planning search operations in settlements on the deoccupied areas of Ukraine: solutions]. Bezpeka derzhavy, vol. 1, no. 5, pp. 47‒55 DOI: https://doi.org/10. 33405/2786-8613/2025/1/5/336712 [in Ukrainian].
Karger D., Motwani R., Ramkumar G.D.S. (1997). On approximating the longest path in a graph. Algorithmica, 18, pp. 82‒98. DOI: https://doi.org/10.1007/BF02523689 [in English].
Feder T., Motwani R. (2005). Finding large cycles in Hamiltonian graphs. Proc. of the 16th annual ACM-SIAM Symp. on Discrete Algorithms (SODA), ACM, pp. 166‒175. DOI: https://doi.org/10.1016/j.dam.2009.12.006 [in English].
Gabow H., Nie S. (2008). Finding long paths, cycles and circuits. Proc. of the 19th annual International Symp. on Algorithms and Computation (ISAAC). LNCS 5369, pp. 752‒763. DOI: https://doi.org/10.1007/978-3-540-92182-0_66 [in English].
Zhang Z., Li H. (2007). Algorithms for long paths in graphs. Theoret. Comput. Sci, 377, pp. 25‒34. DOI: https://doi.org/10.1016/j.tcs.2007.02.012 [in English].
Bulterman R., van der Sommen F., Zwaan G., Verhoeff T. et al. (2002). On computing a longest path in a tree. Inform. Proc. Lett, 81, pp. 93‒96. DOI: https://doi.org/10.1016/S0020-0190(01)00198-3 [in English].
Uehara R., Uno Y. (2004). Efficient algorithms for the longest path problem. Proc. of the 15th annual International Symp. on Algorithms and Computation (ISAAC). LNCS 3341, pp. 871‒883. DOI: https://doi.org/10.1007/978-3-540-30551-4_74 [in English].
Uehara R., Valiente G. (2007). Linear structure of bipartite permutation graphs and the longest path problem. Inform. Proc. Lett, 103, pp. 71‒77. DOI: https://doi.org/10.1016/j.ipl.2007.02.010 [in English].
Takahara Y., Teramoto S., Uehara R. (2008). Longest path problems on ptolemaic graphs. IEICE Trans. Inf. and Syst, 91-D, pp. 170‒177. DOI: https://doi.org/10.1093/ietisy/e91-d.2.170 [in English].
Ioannidou K., Mertzios G., Nikolopoulos S. (2011). The Longest Path Problem has a Polynomial Solution on Interval Graphs. Algorithmica, vol. 61, pp. 320‒341. DOI: https://doi.org/10.1007/s00453-010-9411-3 [in English].
Mertzios G. B., Corneil D. G. (2012). A Simple Polynomial Algorithm for the Longest Path Problem on Coco Graphs. SIAM Journal on Discrete Mathematics, pp. 940‒963. DOI: https://doi.org/10.1137/100793529 [in English].
Arthur B. Kahn (1962). Topological sorting of large networks. Communications of the ACM, 5 (11), pp. 558–562. DOI: https://doi.org/10.1145/368996. 369025 [in English].
Dijkstra E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, vol. 1, iss. 1, pp. 269‒271. DOI: https://doi.org/10.1007/BF01386390 [in English].
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2026 Honor and Law
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
