Citation: Hu, S.; Wang, B.; Zhang, A.;
Deng, Y. Genetic Algorithm and
Greedy Strategy-Based
Multi-Mission-Point Route Planning
for Heavy-Duty Semi-Rigid Airship.
Sensors 2022, 22, 4954. https://
doi.org/10.3390/s22134954
Academic Editors: Jaroslaw Pytka,
Andrzej Łukaszewicz, Zbigniew
Kulesza, Wojciech Giernacki and
Andriy Holovatyy
Received: 20 April 2022
Accepted: 26 June 2022
Published: 30 June 2022
Publisher’s Note: MDPI stays neutral
with regard to jurisdictional claims in
published maps and institutional affil-
iations.
Copyright: © 2022 by the authors.
Licensee MDPI, Basel, Switzerland.
This article is an open access article
distributed under the terms and
conditions of the Creative Commons
Attribution (CC BY) license (https://
creativecommons.org/licenses/by/
4.0/).
Article
Genetic Algorithm and Greedy Strategy-Based
Multi-Mission-Point Route Planning for Heavy-Duty
Semi-Rigid Airship
Shaoxing Hu
1,
*, Bingke Wang
1
, Aiwu Zhang
2,3,
* and Yiming Deng
4
1
School of Mechanical Engineering and Automation, Beihang University, Beijing 100191, China;
1920wangbk@buaa.edu.cn
2
Key Laboratory of 3D Information Acquisition and Application, Ministry of Education,
Capital Normal University, Beijing 100048, China
3
Center for Geographic Environment Research and Education, Capital Normal University,
Beijing 100048, China
4
Nondestructive Evaluation Laboratory, Department of Electrical and Computer Engineering of the College of
Engineering, Michigan State University, East Lansing, MI 48824, USA; dengyimi@egr.msu.edu
* Correspondence: husx@buaa.edu.cn (S.H.); zhangaiwu@cnu.edu.cn (A.Z.)
Abstract:
The large volume and windward area of the heavy-duty semi-rigid airship (HSA) result in a
large turning radius when the HSA passes through every mission point. In this study, a multi-mission-
point route planning method for HSA based on the genetic algorithm and greedy strategy is proposed
to direct the HSA maneuver through every mission point along the optimal route. Firstly, according
to the minimum flight speed and the maximum turning slope angle of the HSA during turning, the
minimum turning radius of the HSA near each mission point is determined. Secondly, the genetic
algorithm is used to determine the optimal flight sequence of the HSA from the take-off point through
all the mission points to the landing point. Thirdly, based on the optimal flight sequence, the shortest
route between every two adjacent mission points is obtained by using the route planning method
based on the greedy strategy. By determining the optimal flight sequence and the shortest route, the
optimal route for the HSA to pass through all mission points can be obtained. The experimental
results show that the method proposed in this study can generate the optimal route with various
conditions of the mission points using simulation studies. This method reduces the total voyage
distance of the optimal route by 18.60% on average and improves the flight efficiency of the HSA.
Keywords:
multi-mission-point; route planning; minimum turning radius; optimal flight sequence;
shortest route
1. Introduction
The heavy-duty semi-rigid airship (HSA) is different from ordinary aerial photography
unmanned airships as the HSA has a large volume and can carry a heavy load for a long
voyage [
1
,
2
]. As a result, many HSAs have been widely used to perform observation,
transportation, and other missions across multiple cities or regions [
3
–
5
], such as Germany
Zeppelin NT airship [
6
], American ML866 airship [
7
], and China ASQ-HAA380 [
8
], to name
a few. The HSAs are also different from airplanes due to their large volume and windward
area, which result in a larger turning radius when performing flight missions. Therefore, in
the HSA route planning, the shortest route between two mission points is not a straight
line but a curve. How to obtain the optimal route so that HSAs can accurately pass through
all mission points, e.g., cities or regions, in sequence with the shortest flight route identified
to improve flight efficiency is critically important, however, multi-mission-point route
planning remains challenging.
The multi-mission-point route planning problem of the HSA can actually be reduced to
a traveling salesman problem (TSP) to solve [
9
], which is a famous combinatorial optimiza-
Sensors 2022, 22, 4954. https://doi.org/10.3390/s22134954 https://www.mdpi.com/journal/sensors
