Submit

Login Login

Register Register

Home / Journals / CMC / Online First / doi:10.32604/cmc.2024.050612
Journal Menu
Special Issues
Table of Content

All issues

Online First

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

Open Access

ARTICLE

An Improved Iterated Greedy Algorithm for Solving Rescue Robot Path Planning Problem with Limited Survival Time

Xiaoqing Wang1, Peng Duan1,*, Leilei Meng1,*, Kaidong Yang2
1 School of Computer Science, Liaocheng University, Liaocheng, 252000, China
2 Shandong Key Laboratory of Optical Communication Science and Technology, School of Physics Science and Information Technology, Liaocheng University, Liaocheng, 252059, China
* Corresponding Author: Peng Duan. Email: email; Leilei Meng. Email: email
(This article belongs to the Special Issue: Recent Advances in Ensemble Framework of Meta-heuristics and Machine Learning: Methods and Applications)

Computers, Materials & Continua https://doi.org/10.32604/cmc.2024.050612

Received 12 February 2024; Accepted 28 May 2024; Published online 28 June 2024

Abstract

Effective path planning is crucial for mobile robots to quickly reach rescue destination and complete rescue tasks in a post-disaster scenario. In this study, we investigated the post-disaster rescue path planning problem and modeled this problem as a variant of the travel salesman problem (TSP) with life-strength constraints. To address this problem, we proposed an improved iterated greedy (IIG) algorithm. First, a push-forward insertion heuristic (PFIH) strategy was employed to generate a high-quality initial solution. Second, a greedy-based insertion strategy was designed and used in the destruction-construction stage to increase the algorithm’s exploration ability. Furthermore, three problem-specific swap operators were developed to improve the algorithm’s exploitation ability. Additionally, an improved simulated annealing (SA) strategy was used as an acceptance criterion to effectively prevent the algorithm from falling into local optima. To verify the effectiveness of the proposed algorithm, the Solomon dataset was extended to generate 27 instances for simulation. Finally, the proposed IIG was compared with five state-of-the-art algorithms. The parameter analysis was conducted using the design of experiments (DOE) Taguchi method, and the effectiveness analysis of each component has been verified one by one. Simulation results indicate that IIG outperforms the compared algorithms in terms of the number of rescue survivors and convergence speed, proving the effectiveness of the proposed algorithm.

Keywords

Rescue robot; path planning; life strength; improved iterative greedy algorithm; problem-specific swap operators

  • 130

    View

  • 23

    Download

  • 3

    Like

Related articles
Copyright© 2024 Tech Science Press
© 1997-2024 TSP (Henderson, USA) unless otherwise stated

Share Link