白响恩　周俊杰　肖英杰　徐笑锋　戚玉玲　沈建华　徐元　任鸿翔　曾建峰

摘要：

针对滴水湖新建无人船测试场的应急保障问题，建立基于Maklink图论和Dijkstra算法的多终点航道规划模型。通过环境建模确定障碍物大小和位置;受PNPoly算法启发，引入剔除函数进行模型改进;利用Dijkstra算法在无向网络图中搜索从起点至终点的最短应急航道，并利用蚁群算法对最短应急航道集合进行优化。结果分析显示，最终规划的航道高效、安全，规划结果可以为滴水湖管理工作和无人船测试场应急保障提供参考。

关键词：

滴水湖; 无人船测试场; 应急保障; 航道规划; Maklink图论; Dijkstra算法

中图分类号：  U612.1; U697.1

文献标志码：  A

收稿日期： 2020-09-08

修回日期： 2020-11-22

基金项目：

国家自然科学基金（51909155）;上海市科学技术委员会项目（14170501600）

作者简介：

白响恩（1984—），女，上海人，副教授，博士，研究方向为船舶交通管理，（E-mail）xebai@shmtu.edu.cn

Emergency support channel planning for unmanned ship

test site in Dishui Lake

BAI Xiangen1a，1b， ZHOU Junjie1a，1b， XIAO Yingjie1a，1b， XU Xiaofeng1a，1b，

QI Yuling1a，1b， SHEN Jianhua2， XU Yuan3， REN Hongxiang4， ZENG Jianfeng3

（1.a.Merchant Marine College; b.Engineering Research Center of Shipping Simulation， Ministry of Education，

Shanghai Maritime University， Shanghai 201306， China; 2.Shanghai Pilot Station， Shanghai 200080， China;

3.Shanghai Waterway Engineering Design and Consulting Co.， Ltd.， Shanghai 200120， China;

4.Navigation College， Dalian Maritime University， Dalian 116026， Liaoning， China）

Abstract：

In view of the problem of emergency support for the new built unmanned ship test site in Dishui Lake， a multi terminal channel planning model is established based on Maklink graph theory and Dijkstra algorithm. The size and location of obstacles are determined by environmental modeling. The model is improved by introducing the elimination function inspired by PNPoly algorithm. Dijkstra algorithm is used to search the shortest emergency channels from the starting point to the terminals in the undirected network diagram， and the ant colony algorithm is used to optimize the set of the shortest emergency channels. The analysis of the result shows that the final planned channel is of high efficiency and safety， and the planning result can provide reference for the management of Dishui Lake and the emergency support of the unmanned ship test site.

Key words：

Dishui Lake; unmanned ship test site; emergency support; channel planning; Maklink graph theory; Dijkstra algorithm

0 引 言

隨着近年来物联网、大数据、云计算、人工智能等新理念、新技术的发展，无人船开始兴起，船舶不断向智能化过渡。相较于陆地环境和空中环境，水域环境的限制条件更多、安全风险更大，因此对水域进行航道规划十分必要。水域环境尤其是具备一定观光旅游条件的湖区，具有自身的独特性，为保障观光旅游的安全和可持续发展，在航道规划中需要纳入应急保障因素。航道规划的本质是路径规划，其实现离不开算法的支持。这些算法根据其实现原理可分为非进化型算法（如A*算法、人工势场法、Floyd算法等）和进化型算法（如TS算法、粒子群算法、遗传算法等）两类[1]。……