American Journal of Traffic and Transportation Engineering

Methodology Article | | Peer-Reviewed |

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

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

Share This Article

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.

DOI 10.11648/j.ajtte.20230806.15
Published in American Journal of Traffic and Transportation Engineering (Volume 8, Issue 6, November 2023)
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
  • 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
  • Merchant Marine College, Shanghai Maritime University, Shanghai, China

  • Merchant Marine College, Shanghai Maritime University, Shanghai, China

  • Merchant Marine College, Shanghai Maritime University, Shanghai, China

  • Sections