基于改进蚁群算法的船舶多约束最优航线设计
时间：2020-12-16 16:01:39 来源：雅意学习网 本文已影响 人 
摘要：为提高船舶航线经济性，基于电子海图显示与信息系统（electronic chart display and information system，ECDIS），分析影响航线设计的各种因素，建立航线设计网络模型。将改进蚁群算法的基本原理应用于船舶航行路径搜索中，提出一种多约束条件下航行综合成本最低的最优航线生成算法。仿真试验证明，该算法是可行的，且具有动态寻优的特点，将其应用于多约束条件下的最优航线设计是合理的。
关键词： 电子海图显示与信息系统（ECDIS）； 多约束； 船舶航线设计； 蚁群算法
中图分类号： U692.33 文献标志码： A
Abstract： In order to improve the economy of ship route， based on the electronic chart display and information system （ECDIS）， the various factors influencing route planning are analyzed， and a route planning network model is established. The basic principle of the improved ant colony algorithm is applied to ship path search. An optimal route generation algorithm under multiple constraints is proposed for the minimum integrated navigation cost. The simulation test shows that， the algorithm is feasible and of the characteristic of dynamic optimization， and it is reasonable to apply the algorithm to the optimal route planning under multiple constraints.
Key words： electronic chart display and information system （ECDIS）； multi-constraint； ship route planning； ant colony algorithm
0 引 言
随着智能航海技术的发展，实时航路规划已成为利用电子海图显示与信息系统（electronic chart display and information system，ECDIS）进行研究的最新方向之一。李源惠等[1]根据电子海图数据库特有的性质，结合碍航物的判别标准和船舶的航行状态，提出了基于电子海图的自动判别计划航线可行性的方法。CHANG等[2]依靠栅格电子海图平台，对迷宫算法进行适当改进，提出了解决最短航线距离问题的方法。RAFAL[3]采用分析避碰和转向条件的策略优化航线。叶清等[4]利用某个港口与多个港口之间的船舶交通网络图，提出了找到一条最佳航线的方法。王德春等[5]通过构建航运网络图，利用A*启发式搜索算法，提出了找到船舶最佳航线的方法。此外，王科[6]依据Dijkstra算法的基本思想对军事航线的最优化问题进行了研究。
蚁群算法具有很好的鲁棒性，被广泛地应用于求解船舶航行的最短路径问题。聂皓冰等[7]引入空间数据索引结构来实现航行信息的快速检索，提出了基于航行信息空间连通矩阵的改进蚁群算法。陈宝文[8]根据舰船路径规划的技术特点，提出了一种基于邻域变异的改进微分进化算法。朱青[9]针对船舶航行环境的特点，采用MAKLINK法建立海洋环境模型，提出了基于蚁群算法的全局路线搜索模型。何立居等[10]基于蚁群算法进行了航线自动生成的研究，在电子海图中通过案例证明了蚁群算法用于航线自动生成的可行性。然而，这些研究都主要集中在算法改良上，路径选择主要满足路径最短这一目标，即在一个约束条件下的最优路径问题。
在水上交通中，在多约束条件下的最优航线设计问题是在给定的带有多个约束的网络拓扑结构中寻找一条或多条满足限定条件的路径的问题，其约束条件可以为水深、路径长度、与障碍物距离等。本文以电子海图为基础，对多约束条件下船舶航行路径最短问题进行研究。
1 航线设计问题描述
在多约束条件下船舶最优航线选择是，某船舶在满足给定的约束条件的情况下，在起始港口与目的港口之间找到一条成本最小或者达到特定的服务水平的航线。两个港口之间有任意多条可供船舶航行的航线，它们经过不同的港口和锚地，同时存在多种约束和一些点、线、面的碍航物，这组成了一张航线网络图。在电子海图中根据相关约束条件来确定碍航区，在起始港口与目的港口之间的可航区域内，按照一定间隔依次遍历每一个水深点，若符合预先规定的约束条件要求，则将该航路点抽象为一个节点，同时将要经过的港口也当作节点抽象出来，节点之间的距离为广义上的航行距离，这样就抽象出一张带权网络图[9，11]。
寻找从起始港口到目的港口的最短路径问题[12-14]，可以转化成在带权网络图中对单源节点最短路径问题的分析，故在航线网络图上寻找最短路径问题就转化为图论中的最短路径问题。节点、弧、权值三要素组成了带权网络图。节点为航路点、港口、交叉点以及断点；弧为两节点间的有向弧段；权值为航段某个或者某些特性的量化值。因此，带权航线网络图就转化为一个带权有向图，并且权值的获取是基于时间段的。假设网络中有N个节点，船舶可通过第i个节點的时间段为[til，tir]，实际通过该节点的时刻为ti。这样，节点就增加了时间约束：til≤ti≤tir（1≤i≤N）。设置约束函数Qi（ti）来体现这个时间约束对最优航线设计的影响：
