IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v11y2023i1p223-d1022582.html
   My bibliography  Save this article

Graph-Clustering Method for Construction of the Optimal Movement Trajectory under the Terrain Patrolling

Author

Listed:
  • Boris V. Rumiantsev

    (Federal Research Centre “Fundamentals of Biotechnology” of the Russian Academy of Sciences, Leninsky Prospect, 33, Build. 2, 119071 Moscow, Russian Federation)

  • Rasul A. Kochkarov

    (Department of Data Analysis and Machine Learning, Faculty of Information Technology and Big Data Analysis, Financial University under the Government of the Russian Federation, Leningradsky Prospekt, 49/2, 125167 Moscow, Russian Federation)

  • Azret A. Kochkarov

    (Federal Research Centre “Fundamentals of Biotechnology” of the Russian Academy of Sciences, Leninsky Prospect, 33, Build. 2, 119071 Moscow, Russian Federation
    Department of Data Analysis and Machine Learning, Faculty of Information Technology and Big Data Analysis, Financial University under the Government of the Russian Federation, Leningradsky Prospekt, 49/2, 125167 Moscow, Russian Federation)

Abstract

The method of the optimal movement trajectory construction in the terrain patrolling tasks is proposed. The method is based on the search of the Hamiltonian circuit on the graph of the terrain map and allows automatic construction of the optimal closed path for arbitrary terrain map. The distinguishing feature of the method is the use of the modified algorithm for the Hamiltonian circuit search. The algorithm can be scaled for the maps corresponding to the graphs with a large (more than 100) number of the vertices, for which the standard brute-force algorithm of the Hamiltonian circuit search requires significantly higher execution time than the proposed algorithm. It is demonstrated that the utilized algorithm possesses 17 times less constant of the time complexity growth than the standard brute-force algorithm. It allows more than one order of magnitude (from 30 to 500 vertices, i.e., approximately to the 17 times) increase of the graph vertices that is used for the Hamiltonian circuit search in the real time (0.1–100 s) regime.

Suggested Citation

  • Boris V. Rumiantsev & Rasul A. Kochkarov & Azret A. Kochkarov, 2023. "Graph-Clustering Method for Construction of the Optimal Movement Trajectory under the Terrain Patrolling," Mathematics, MDPI, vol. 11(1), pages 1-13, January.
    • Handle: RePEc:gam:jmathe:v:11:y:2023:i:1:p:223-:d:1022582
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/11/1/223/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/11/1/223/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Joonyup Eun & Byung Duk Song & Sangbok Lee & Dae-Eun Lim, 2019. "Mathematical Investigation on the Sustainability of UAV Logistics," Sustainability, MDPI, vol. 11(21), pages 1-15, October.
    2. Gyanendra Prasad Joshi & Fayadh Alenezi & Gopalakrishnan Thirumoorthy & Ashit Kumar Dutta & Jinsang You, 2021. "Ensemble of Deep Learning-Based Multimodal Remote Sensing Image Classification Model on Unmanned Aerial Vehicle Networks," Mathematics, MDPI, vol. 9(22), pages 1-17, November.
    3. Caraballo, Luis E. & Díaz-Báñez, José M. & Fabila-Monroy, Ruy & Hidalgo-Toscano, Carlos, 2022. "Stochastic strategies for patrolling a terrain with a synchronized multi-robot system," European Journal of Operational Research, Elsevier, vol. 301(3), pages 1099-1116.
    4. Jeng-Shyang Pan & Pei-Cheng Song & Shu-Chuan Chu & Yan-Jun Peng, 2020. "Improved Compact Cuckoo Search Algorithm Applied to Location of Drone Logistics Hub," Mathematics, MDPI, vol. 8(3), pages 1-19, March.
    5. Rasul Kochkarov & Azret Kochkarov, 2022. "Introduction to the Class of Prefractal Graphs," Mathematics, MDPI, vol. 10(14), pages 1-17, July.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Abhijeet Ainapure & Shahin Siahpour & Xiang Li & Faray Majid & Jay Lee, 2022. "Intelligent Robust Cross-Domain Fault Diagnostic Method for Rotating Machines Using Noisy Condition Labels," Mathematics, MDPI, vol. 10(3), pages 1-17, January.
    2. Yifan Da & Zhiyuan Ji & Yongsheng Zhou, 2022. "Building Damage Assessment Based on Siamese Hierarchical Transformer Framework," Mathematics, MDPI, vol. 10(11), pages 1-23, June.
    3. David Álvarez Gutiérrez & Fernando Sánchez Lasheras & Vicente Martín Sánchez & Sergio Luis Suárez Gómez & Víctor Moreno & Ferrán Moratalla-Navarro & Antonio José Molina de la Torre, 2022. "A New Algorithm for Multivariate Genome Wide Association Studies Based on Differential Evolution and Extreme Learning Machines," Mathematics, MDPI, vol. 10(7), pages 1-21, March.
    4. Dukkanci, Okan & Campbell, James F. & Kara, Bahar Y., 2024. "Facility location decisions for drone delivery: A literature review," European Journal of Operational Research, Elsevier, vol. 316(2), pages 397-418.
    5. Wang, Hong-Jiang & Pan, Jeng-Shyang & Nguyen, Trong-The & Weng, Shaowei, 2022. "Distribution network reconfiguration with distributed generation based on parallel slime mould algorithm," Energy, Elsevier, vol. 244(PB).
    6. Iftikhar Ahmad & Abdul Qayyum & Brij B. Gupta & Madini O. Alassafi & Rayed A. AlGhamdi, 2022. "Ensemble of 2D Residual Neural Networks Integrated with Atrous Spatial Pyramid Pooling Module for Myocardium Segmentation of Left Ventricle Cardiac MRI," Mathematics, MDPI, vol. 10(4), pages 1-23, February.
    7. Yi Li & Min Liu & Dandan Jiang, 2022. "Application of Unmanned Aerial Vehicles in Logistics: A Literature Review," Sustainability, MDPI, vol. 14(21), pages 1-18, November.
    8. Young Dae Ko & Byung Duk Song, 2021. "Complementary Cooperation of CCTV and UAV Systems for Tourism Security and Sustainability," Sustainability, MDPI, vol. 13(19), pages 1-15, September.
    9. Kaiping Wang & Mingzhu Song & Meng Li, 2021. "Cooperative Multi-UAV Conflict Avoidance Planning in a Complex Urban Environment," Sustainability, MDPI, vol. 13(12), pages 1-21, June.
    10. Bo Peng & Lifan Wu & Yuxin Yi & Xiding Chen, 2020. "Solving the Multi-Depot Green Vehicle Routing Problem by a Hybrid Evolutionary Algorithm," Sustainability, MDPI, vol. 12(5), pages 1-19, March.
    11. Michael Dienstknecht & Nils Boysen & Dirk Briskorn, 2022. "The traveling salesman problem with drone resupply," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(4), pages 1045-1086, December.
    12. Nils Boysen & Stefan Fedtke & Stefan Schwerdfeger, 2021. "Last-mile delivery concepts: a survey from an operational research perspective," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(1), pages 1-58, March.
    13. Jianxun Li & Hao Liu & Kin Keung Lai & Bhagwat Ram, 2022. "Vehicle and UAV Collaborative Delivery Path Optimization Model," Mathematics, MDPI, vol. 10(20), pages 1-22, October.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:11:y:2023:i:1:p:223-:d:1022582. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.