基于改进蚁群算法的船舶多约束最优航线设计

陈立家+黄立文+崔梅

摘要：为提高船舶航线经济性，基于电子海图显示与信息系统（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）来体现这个时间约束对最优航线设计的影响：endprint

2 多元约束及其参数

按照航线影响因素的不同，有静态权值和动态权值。静态权值是用船舶航行距离衡量航线权重以达到最短距离的目标，动态权值是用经济效益衡量航线权重以获得航行时燃料消耗最少的目标。

航行费用E=E1+E2+E3，其中E1表示燃料消耗所产生的费用，E2表示航行时间价值所产生的费用（隐形的费用），E3表示航行过程中所缴纳的费用。这很明显地体现出一些经济因素，比如将航行距离和航行时间都折算为费用。

航行质量指航线能满足人们需求的程度。对影响航行质量的一切性能指标进行综合评价，得到航线质量权值：M=σ1T+σ2D+σ3Q，σ1+σ2+σ3=1

（3）式中：T是船舶在航线上的平均行程时间；D是航行过程中所消耗的燃料；Q是航线的舒适度；σ1，σ2和σ3为权重因数，分别体现了T，D和Q在航线质量中所占的权重。

在多约束条件下的航线权值计算方法：根据水文气象资料，得知在某时间段内船舶在可航区域各航段的海况信息、风浪信息和水深信息，以及船舶在风浪中的临界速度。

V=1T+2W+3S， 1+2+3=1

（4）

式中：T是基于静态因素的船舶在航线上的平均行程时间（=航程/基本航行速度）；W是关于风的信息值，包含风的大小和方向；S是关于浪的信息值；1，2和3分别表示T，W和S所占的权重。另外，当风浪超过一定级别时，船舶航速会发生变化，此时用确定好的临界速度来计算T。

3 在多约束条件下最优航线设计算法

3.1 基本思想

本文提出一种在多约束条件下航行综合成本最低的最优航线生成算法（an optimal route generation algorithm based on the minimum integrated navigation cost under multiple constraints，ORGA）。当两港口之间有多条航线可供选择时，可应用Dijkstra算法求得最短航线。根据各种环境因素对航线的影响，用改进的蚁群算法使生成的航线达到最优。改进的蚁群算法的基本思想为：（1）在每只蚂蚁完成一遍搜索后，在信息素浓度更新之前，对所有蚂蚁按照其所走过的路径的长度由短到长进行排序；在信息素浓度更新时，对挑选出来的前h只蚂蚁，适当增加其所走过的路径的信息素量，对后面的m-h只蚂蚁，适当减少其所走过的路径的信息素量，这样就拉开了优、劣蚂蚁所走过的路径之间的差距，从而提高找到最优路径的速度。（2）为削弱上述策略引起的蚁群陷入早熟的局限，采用MMAX优化思想，将各路径上的信息素浓度限制在[τmin，τmax]内，若某路径上的信息素浓度超过这个范围，则按就近原则将其设为τmin或τmax，这就避免了算法过早收敛并陷入局部最优解的问题，也避免了搜索过程中的停滞现象。（3）因为在ORGA中对路径上的信息素浓度进行了人为控制，导致了各路径上的信息素浓度两级分化比较严重，所以将路径上信息素的残留系数设得较低。为有助于增加初始阶段蚂蚁的搜索能力，将各路径上的信息素浓度初始值设为τmax。

3.2 算法实现

通过释放人工蚂蚁来创建基于蚂蚁算法的网络模型。

算法涉及的函数和变量如下：ηij=1/（dij（1+Rij（1+Wij）+Cij））

（5）式中：ηij为启发函数；dij为相邻两节点间的距离；Rij为风浪状况因子；Wij为天气情况因子；Cij为海况因子。各因子都是非负的。对蚂蚁k而言，该启发函数表示它从节点i转移到节点j的期望程度。各因子都是通过观测得到的。

τij（t）为t时刻在边（i，j）上的信息素浓度；tij为船舶从i行驶到j的时间，用权值cij表示；tij，l=til+tij，tij，r=tir+tij；α为期望启发因子，表示轨迹的相对重要度；β为能见度的相对重要度；ψ为时间约束因子，表示时间约束的相对重要度；q为一个取值范围为[0，1]的变量，它决定选择下一个城市的概率；q0为一个给定的[0，1]间的常数，其值越小表示蚂蚁随机选择下一个节点的概率越大；Ak（k=1，2，…，m）为蚂蚁k已走过的节点集合，即为禁忌表；m为蚂蚁的数量；Bk为允许蚂蚁k下一步选择的节点集合；Q为每只蚂蚁所持有的信息素总量；Lk为节点i与j之间的路径长度。

3.3 算法具体步骤

ORGA的具体步骤如下：

步骤1 将各控制参数初始化：时间t=0；循环次数Nc=0；每条航段（i，j）的初始化信息素浓度τij（0）=τmax；最大循环次数为Nc，max；全局最优解为Lg。

步驟2 将m只蚂蚁置于起点，建立候选节点列表M。

步骤3 对蚂蚁k（k=1，2，…，m），在候选节点列表中找出其未走过的节点（M-Ak），并在这些节点中根据式（6）（状态转移规则）选择该蚂蚁访问的下一个节点，直到所有的节点都被访问为止。

步骤4 判断已完成搜索的蚂蚁数量是否为m，是则执行步骤5，否（即还有蚂蚁未完成搜索）则返回步骤3，直到所有蚂蚁都完成搜索为止。

步骤5 计算每只蚂蚁的搜索路径长度Lk（k=1，2，…，m），并且对蚂蚁按照其所走过的路径长度由短到长的顺序进行排序。对于排名前h的蚂蚁，设置本次路径Llocal为本次最优路径，Llocal=hk=1Lk，同时保存最优路径表。

步骤6 对所有路径上的信息素浓度按式（8）进行全局更新，在本次循环中对排名前h的蚂蚁所经过的路径上的信息素浓度按该蚂蚁所在的名次进行增加。信息素浓度更新的同时，按照式（7）来优化替换，以便蚂蚁产生新的搜索路线。

步骤7 将本次最优路径Llocal与全局最优解Lg比较，较小的值存入Lg，并更新全局最优路径表。endprint

步骤8 若每只蚂蚁的路径都收敛于同一条路径，则算法结束。判断Nc与Nc，max是否相等，若相等，则流程结束；否则，清空禁忌表Ak，转至步骤3。4 算法检验

4.1 复杂度分析

假设航线网络结构中有N个节点，采用传统的Dijkstra算法，需要的时间为N（N-1）=N2-N，该算法的时间复杂度为O（N2）。ORGA是针对传统Dijkstra算法搜索时间过长和基本的蚁群算法存在早熟和停滞现象而提出来的，它适当地改进蚁群算法，对一次循环完成后的所有蚂蚁按照路径长短排序，虽然增加了空间复杂度，但让蚂蚁能够更快地找到最优路径，从而提高了算法的执行效率。

4.2 收敛性分析

ORGA是以航线网络图为基础，并以蚁群算法为基本思想的最优航线生成算法。Gutjahr W J已经在理论上对图搜素蚂蚁系统（graph-based ant system，GBAS）的收敛性进行了证明，在符合一些前提条件时，GBAS可以以接近于1的概率收敛于最优解，而ORGA也满足GBAS的4个条件：

（1）經过仿真试验并按照经验，可以将参数α取值为1。

（2）设计航线时，一般从起点到终点的最优航线与从终点到起点的最优航线是不一致的，这是因为各种环境因素的影响等都不尽相同，并且还伴随着顺流逆流问题的存在，所以最优路径也是唯一的。

（3）根据式（5），期望因子ηij>0。

（4）信息素浓度更新使用的是全局更新策略，只是对前h只蚂蚁所走过的路径适当增加额外的信息素量。

5 仿真试验

5.1 仿真环境

实验采用OpenCPNSDK，它是对OpenCPN进行封装后，提供给电子海图应用系统开发商进行二次开发的组件包，可提供COM组件和C+ +动态库两种形式封装，支持WINDOWS，WINCE和LINUX平台。利用OpenCPNSDK，用户可开发出自己的支持S57和S52标准的电子海图系统，并与雷达、AIS等系统结合，开发出多种船用或岸上应用系统。OpenCPNSDK可根据用户的应用需求提供灵活的、有针对性的封装，从而最大程度地帮助用户增强系统功能，提高系统性能，缩短开发周期和减少开发成本。在Visual Studio 2008平台下，基于组件包OpenCPNSDK采用VC+ +语言进行系统开发。

5.2 结果

Dijkstra算法中两节点之间的权值大小按照式（4）进行设置，设定1=0.4，2=0.3，3=0.3。ORGA中的各参数设置如下：α=1，β=5，ρ=0.2，m=60，w=m/2。式（5）中：dij和Rij范围均为[0，10]；Wij的范围为[0，5]（阴晴用0表示；小雨或小雪在[0.1，0.2）内取值；中雨或中雪在[0.2，0.5）内取值；大雨或大雪在[0.5，1）内取值；暴风雨在[1，3）内取值；大雾在[3，5]内取值）；Cij，海况正常用0表示，有暴浪致使不能航行的情况用∞表示。以下是航行起点为宁波-舟山港虾峙门的进口灯船，终点为金塘港，航线规划经过虾峙门航道和螺头航道，使用Dijkstra算法和ORGA生成的最短距离航线分别见图1和2。图1中所得最优航线的里程为45.6 n mile，转向点数为18；图2中所得最优航线的里程为42.8 n mile，转向点数为6。

由试验可知：ORGA克服了Dijkstra算法对复杂碍航区处理不完备的问题，进一步优化了航线绕行碍航区的策略；ORGA耗时2.450 s，而Dijkstra算法耗时4.556 s，故ORGA相对Dijkstra算法在时间上有明显优势。

6 结束语

分析了各种环境因素对航线设计的影响，简述了各种影响因素的来源和确定方法，提出了在电子海图显示与信息系统（ECDIS）中以航行综合成本最低为目标的航线设计算法。重点讨论了基于电子海图的最优航线算法的设计，并且对所提出的算法进行了仿真试验分析，达到了预期的效果。

参考文献：

[1] 李源惠， 孙少鹏. 电子海图中计划航线可行性的自动判别[J]. 大连海事大学学报， 2000， 26（2）： 40-43.

[2] CHANG K Y， JAN G E， PARBERRY I. A method for searching optimal routes with collision avoidance on raster charts[J]. The Journal of Navigation， 2003， 56（3）： 371-384.

[3] RAFAL S. A new method of ship routing on raster grids， with turn penalties and collision avoidance[J]. The Journal of Navigation， 2006， 59（1）： 371-384.

[4] 叶清， 郁振伟. 改进最短路径算法在最佳航线选择中的应用[J]. 中国航海， 2003， 55（2）： 15-17.

[5] 王德春， 陈利敏， 张孝芳. 基于A*算法的舰船最佳选择[J]. 青岛大学学报（自然科学版）， 2005， 18（4）： 10-13.

[6] 王科. 基于电子海图的航线设计研究[D]. 大连： 海军大连舰艇学院， 2004.

[7] 聂皓冰， 王胜正， 胡志武， 等. 航线动态优化算法在海上搜救中的应用[J]. 上海海事大学学报， 2011， 32（4）： 1-6.

[8] 陈宝文. 蚁群优化算法在车辆路径问题中的应用研究[D]. 哈尔滨： 哈尔滨工业大学， 2009.

[9] 朱青. 基于蚁群算法的船舶航行设计方法的研究[D]. 哈尔滨： 哈尔滨工程大学， 2011.

[10] 何立居， 李启华. 基于蚁群算法的航线自动生成研究[J]. 中国航海， 2009， 32（3）： 71-75.

[11] BIJLSMA S J. On the applications of the principle of optimal evolution in ship routing[J]. Journal of the Institute of Navigation， 2004， 51（2）： 93-100.

[12] 马荣贵， 崔华， 薛世焦. 改进蚁群算法的多约束质量最优路径选择[J]. 西安电子科技大学学报（自然科学版）， 2016， 43（3）： 185-189.

[13] 汤青慧， 唐旭， 崔晓晖. 基于动态通达网络模型的最优航程规划方法[J]. 武汉大学学报（信息科学版）， 2015， 40（4）： 521-526.

[14] 李松江， 张异， 龚跃.基于蚁群算法的智能交通最优路径研究[J]. 长春理工大学学报（自然科学版）， 2015， 38（4）： 122-126.

（编辑 赵勉）endprint