A Two-Stage Algorithm for Coastal Complex Water Route Planning Based on A* and Recursion

Dongkui Wu; Fan Yang; Lixiong Chen

doi:doi:10.11648/j.ajtte.20230806.15

Methodology Article |

| Peer-Reviewed

A Two-Stage Algorithm for Coastal Complex Water Route Planning Based on A* and Recursion

Dongkui Wu, Fan Yang, Lixiong Chen^*

Published in American Journal of Traffic and Transportation Engineering (Volume 8, Issue 6)

Received: 16 November 2023 Accepted: 6 December 2023 Published: 22 December 2023

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

Abstract

Route planning is a crucial task in maritime navigation, as it ensures the safety of navigation and reduces fuel consumption. In order to further enhance the safety of vessel navigation in complex waterways, reduce sailing distances, and improve the convenience of vessel operations, this paper addresses the shortest path problem for vessel navigation in complex waterways. This problem aims to find a route with the shortest sailing distance and the fewest number of ship turning maneuvers in a complex water area, while ensuring navigation safety from the starting point to the destination. By abstracting the actual sailing process of vessels, the paper initially divides the navigation area into grids, and then differentiates between impassable and passable grids by inflating the boundaries of navigational obstacles. An integer programming model based on grid partitioning is formulated to describe this problem, and the optimality of the routes is analyzed. A two-stage algorithm is proposed to solve this problem, wherein the first stage utilizes the A* algorithm to find the shortest path from the starting point to the destination, and the second stage uses a recursive algorithm based on the path generated in the first stage to adjust turning points and further reduce the sailing distance. Finally, a simulation platform is built using Python, and the above algorithms are employed for experimentation. The experimental results demonstrate the effectiveness of the proposed model and algorithms.

Published in	American Journal of Traffic and Transportation Engineering (Volume 8, Issue 6)
DOI	10.11648/j.ajtte.20230806.15
Page(s)	158-165
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2024. Published by Science Publishing Group

Keywords

Grid Method, A* Algorithm, Recursive Algorithm, Route Design

References

[1]	GUO D D, YIN Y, XIAO F B. Overview of intelligent ship route optimization methods [J]. Chinese Journal of Ship Research, 2023, 18(4): 151–161
[2]	YAN X P, WANG S W, MA F. Review and prospect for intelligent cargo ships [J]. Chinese Journal of Ship Research, 2021
[3]	Lv Chao, Hu Qinyou, Xiang Zhe, Zhou Jia. Algorithm and Implementation of Recommended Routes for Major Coastal Ports in China [J]. Journal of Shanghai Maritime University, 2015.
[4]	DU Zhixiao GUO Kun MA Shuo WANG Yuxi. Design of an Intelligent Navigation Shore-based Meteorological Service System [J]. Ship Electronic Engineering, 2019.
[5]	Zhou Yinfei, Zhang Lihua, Jia Shuaidong, Dai Zeyuan, Dong Jian, Ma Mengkai. Autonomous Navigation Route Planning Method of Unmanned Ship Based on Bessel Curves Constrained by Maximum Navigable Window Sequence [J]. Geomatics and Information Science of Wuhan University, 2022.
[6]	Pan Mingyang, Liu Yisai, Li Qi, Li Chao, and Chen Zhitai. Inland Waterway Route Planning and Application based on Improved A* Algorithm [J]. "Journal of Shanghai Maritime University" 2020.
[7]	Cui Kangjing, Zheng Yuanzhou, Chen Guocheng, Hu Weidong. Optimization Design of Ship Meteorological Routes in Heavy Wind and Wave Environments [J/OL]. Journal of Wuhan University of Technology (Transportation Science and Engineering Edition), 2022.
[8]	Chen Xiao, Dai Ran, Zhao Yanpeng, Zhang Chaoyue. Design of Ship Shallow Avoidance Route Based on Fish Swarm Algorithm [J]. China Navigation, 2019.
[9]	Liu Zhifang. Application of Genetic Algorithm in Ship Route Adaptive Controller [J]. Ship Science and Technology, 2017.
[10]	Chen Xiao, Dai Ran, Chen Changyuan. Route Planning Based on Maklink Graph and Ant Colony Algorithm [J]. China Navigation, 2017.
[11]	Zhu Qing, Research on Ship Route Design Method Based on Ant Colony Algorithm [D]. Harbin Engineering University, 2011.
[12]	Yao Xiaoxiao, Hu Qinyou, Yang Chun. Ship Route Planning Based on Ant Colony Algorithm and Massive AIS Data [J]. Transportation Information and Safety, 2019.
[13]	Xie Xinlian, He Ping, He Ao, Xin Jianying. Collision Avoidance Path Planning of Ships in Complicated Water Areas [J]. Journal of Chongqing Jiaotong University (Natural Science), 2019.
[14]	Yu Bixiu, Chu Xiumin, Liu Chenguang, Zhang Hao, Mao Qingzhou. A Path Planning Method for Unmanned Waterway Survey Ships Based on Improved A* Algorithm [J]. Geomatics and Information Science of Wuhan University, 2019.
[15]	Wang Lipeng, Zhang Zhi, Ma Shan, Wang Xuewu. Improved Genetic Algorithm for Route Planning Considering Ship Maneuverability Constraints [J]. Journal of Harbin Engineering University, 2021.
[16]	Tong Bangyu, Hu Jiankun. Ship Route Planning in Ice-Covered Areas Based on Improved Ant Colony Algorithm [J]. Navigation of China, 2020."

Cite This Article

Plain Text BibTeX RIS

APA Style

Wu, D., Yang, F., Chen, L. (2023). A Two-Stage Algorithm for Coastal Complex Water Route Planning Based on A* and Recursion. American Journal of Traffic and Transportation Engineering, 8(6), 158-165. https://doi.org/10.11648/j.ajtte.20230806.15

Copy | Download

ACS Style

Wu, D.; Yang, F.; Chen, L. A Two-Stage Algorithm for Coastal Complex Water Route Planning Based on A* and Recursion. Am. J. Traffic Transp. Eng. 2023, 8(6), 158-165. doi: 10.11648/j.ajtte.20230806.15

Copy | Download

AMA Style

Wu D, Yang F, Chen L. A Two-Stage Algorithm for Coastal Complex Water Route Planning Based on A* and Recursion. Am J Traffic Transp Eng. 2023;8(6):158-165. doi: 10.11648/j.ajtte.20230806.15

Copy | Download

@article{10.11648/j.ajtte.20230806.15,
  author = {Dongkui Wu and Fan Yang and Lixiong Chen},
  title = {A Two-Stage Algorithm for Coastal Complex Water Route Planning Based on A* and Recursion},
  journal = {American Journal of Traffic and Transportation Engineering},
  volume = {8},
  number = {6},
  pages = {158-165},
  doi = {10.11648/j.ajtte.20230806.15},
  url = {https://doi.org/10.11648/j.ajtte.20230806.15},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajtte.20230806.15},
  abstract = {Route planning is a crucial task in maritime navigation, as it ensures the safety of navigation and reduces fuel consumption. In order to further enhance the safety of vessel navigation in complex waterways, reduce sailing distances, and improve the convenience of vessel operations, this paper addresses the shortest path problem for vessel navigation in complex waterways. This problem aims to find a route with the shortest sailing distance and the fewest number of ship turning maneuvers in a complex water area, while ensuring navigation safety from the starting point to the destination. By abstracting the actual sailing process of vessels, the paper initially divides the navigation area into grids, and then differentiates between impassable and passable grids by inflating the boundaries of navigational obstacles. An integer programming model based on grid partitioning is formulated to describe this problem, and the optimality of the routes is analyzed. A two-stage algorithm is proposed to solve this problem, wherein the first stage utilizes the A* algorithm to find the shortest path from the starting point to the destination, and the second stage uses a recursive algorithm based on the path generated in the first stage to adjust turning points and further reduce the sailing distance. Finally, a simulation platform is built using Python, and the above algorithms are employed for experimentation. The experimental results demonstrate the effectiveness of the proposed model and algorithms.
},
 year = {2023}
}

Copy | Download

TY  - JOUR
T1  - A Two-Stage Algorithm for Coastal Complex Water Route Planning Based on A* and Recursion
AU  - Dongkui Wu
AU  - Fan Yang
AU  - Lixiong Chen
Y1  - 2023/12/22
PY  - 2023
N1  - https://doi.org/10.11648/j.ajtte.20230806.15
DO  - 10.11648/j.ajtte.20230806.15
T2  - American Journal of Traffic and Transportation Engineering
JF  - American Journal of Traffic and Transportation Engineering
JO  - American Journal of Traffic and Transportation Engineering
SP  - 158
EP  - 165
PB  - Science Publishing Group
SN  - 2578-8604
UR  - https://doi.org/10.11648/j.ajtte.20230806.15
AB  - Route planning is a crucial task in maritime navigation, as it ensures the safety of navigation and reduces fuel consumption. In order to further enhance the safety of vessel navigation in complex waterways, reduce sailing distances, and improve the convenience of vessel operations, this paper addresses the shortest path problem for vessel navigation in complex waterways. This problem aims to find a route with the shortest sailing distance and the fewest number of ship turning maneuvers in a complex water area, while ensuring navigation safety from the starting point to the destination. By abstracting the actual sailing process of vessels, the paper initially divides the navigation area into grids, and then differentiates between impassable and passable grids by inflating the boundaries of navigational obstacles. An integer programming model based on grid partitioning is formulated to describe this problem, and the optimality of the routes is analyzed. A two-stage algorithm is proposed to solve this problem, wherein the first stage utilizes the A* algorithm to find the shortest path from the starting point to the destination, and the second stage uses a recursive algorithm based on the path generated in the first stage to adjust turning points and further reduce the sailing distance. Finally, a simulation platform is built using Python, and the above algorithms are employed for experimentation. The experimental results demonstrate the effectiveness of the proposed model and algorithms.

VL  - 8
IS  - 6
ER  -

Copy | Download

Author Information

Dongkui Wu

Merchant Marine College, Shanghai Maritime University, Shanghai, China

Contact Email
Fan Yang

Merchant Marine College, Shanghai Maritime University, Shanghai, China

Contact Email
Lixiong Chen

Merchant Marine College, Shanghai Maritime University, Shanghai, China

Contact Email

Download PDF

Sections

Plain Text BibTeX RIS

APA Style

Wu, D., Yang, F., Chen, L. (2023). A Two-Stage Algorithm for Coastal Complex Water Route Planning Based on A* and Recursion. American Journal of Traffic and Transportation Engineering, 8(6), 158-165. https://doi.org/10.11648/j.ajtte.20230806.15

Copy | Download

ACS Style

Wu, D.; Yang, F.; Chen, L. A Two-Stage Algorithm for Coastal Complex Water Route Planning Based on A* and Recursion. Am. J. Traffic Transp. Eng. 2023, 8(6), 158-165. doi: 10.11648/j.ajtte.20230806.15

Copy | Download

AMA Style

Wu D, Yang F, Chen L. A Two-Stage Algorithm for Coastal Complex Water Route Planning Based on A* and Recursion. Am J Traffic Transp Eng. 2023;8(6):158-165. doi: 10.11648/j.ajtte.20230806.15

Copy | Download

@article{10.11648/j.ajtte.20230806.15,
  author = {Dongkui Wu and Fan Yang and Lixiong Chen},
  title = {A Two-Stage Algorithm for Coastal Complex Water Route Planning Based on A* and Recursion},
  journal = {American Journal of Traffic and Transportation Engineering},
  volume = {8},
  number = {6},
  pages = {158-165},
  doi = {10.11648/j.ajtte.20230806.15},
  url = {https://doi.org/10.11648/j.ajtte.20230806.15},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajtte.20230806.15},
  abstract = {Route planning is a crucial task in maritime navigation, as it ensures the safety of navigation and reduces fuel consumption. In order to further enhance the safety of vessel navigation in complex waterways, reduce sailing distances, and improve the convenience of vessel operations, this paper addresses the shortest path problem for vessel navigation in complex waterways. This problem aims to find a route with the shortest sailing distance and the fewest number of ship turning maneuvers in a complex water area, while ensuring navigation safety from the starting point to the destination. By abstracting the actual sailing process of vessels, the paper initially divides the navigation area into grids, and then differentiates between impassable and passable grids by inflating the boundaries of navigational obstacles. An integer programming model based on grid partitioning is formulated to describe this problem, and the optimality of the routes is analyzed. A two-stage algorithm is proposed to solve this problem, wherein the first stage utilizes the A* algorithm to find the shortest path from the starting point to the destination, and the second stage uses a recursive algorithm based on the path generated in the first stage to adjust turning points and further reduce the sailing distance. Finally, a simulation platform is built using Python, and the above algorithms are employed for experimentation. The experimental results demonstrate the effectiveness of the proposed model and algorithms.
},
 year = {2023}
}

Copy | Download

TY  - JOUR
T1  - A Two-Stage Algorithm for Coastal Complex Water Route Planning Based on A* and Recursion
AU  - Dongkui Wu
AU  - Fan Yang
AU  - Lixiong Chen
Y1  - 2023/12/22
PY  - 2023
N1  - https://doi.org/10.11648/j.ajtte.20230806.15
DO  - 10.11648/j.ajtte.20230806.15
T2  - American Journal of Traffic and Transportation Engineering
JF  - American Journal of Traffic and Transportation Engineering
JO  - American Journal of Traffic and Transportation Engineering
SP  - 158
EP  - 165
PB  - Science Publishing Group
SN  - 2578-8604
UR  - https://doi.org/10.11648/j.ajtte.20230806.15
AB  - Route planning is a crucial task in maritime navigation, as it ensures the safety of navigation and reduces fuel consumption. In order to further enhance the safety of vessel navigation in complex waterways, reduce sailing distances, and improve the convenience of vessel operations, this paper addresses the shortest path problem for vessel navigation in complex waterways. This problem aims to find a route with the shortest sailing distance and the fewest number of ship turning maneuvers in a complex water area, while ensuring navigation safety from the starting point to the destination. By abstracting the actual sailing process of vessels, the paper initially divides the navigation area into grids, and then differentiates between impassable and passable grids by inflating the boundaries of navigational obstacles. An integer programming model based on grid partitioning is formulated to describe this problem, and the optimality of the routes is analyzed. A two-stage algorithm is proposed to solve this problem, wherein the first stage utilizes the A* algorithm to find the shortest path from the starting point to the destination, and the second stage uses a recursive algorithm based on the path generated in the first stage to adjust turning points and further reduce the sailing distance. Finally, a simulation platform is built using Python, and the above algorithms are employed for experimentation. The experimental results demonstrate the effectiveness of the proposed model and algorithms.

VL  - 8
IS  - 6
ER  -

Copy | Download