基于惩罚-PSO的群桥水域多约束航路规划

邹春明， 赵俊超， 杨 柯， 徐言民， 高如江， 金 城， 陈 敏

(武汉理工大学 内河航运技术湖北省重点实验室， 武汉 430063)

ZOU Chunming， ZHAO Junchao, YANG Ke， XU Yanmin， GAO Rujiang， JIN Cheng， CHEN Min

基于惩罚-PSO的群桥水域多约束航路规划

邹春明， 赵俊超， 杨 柯， 徐言民， 高如江， 金 城， 陈 敏

(武汉理工大学 内河航运技术湖北省重点实验室， 武汉 430063)

为保障群桥水域通航安全和桥梁自身安全，以长江武汉段桥梁为研究对象，分析群桥水域通航环境特征，得出群桥水域具有桥梁间距小、通航孔交错分布、桥梁轴线不平行和交通流复杂等结论。在此基础上，建立群桥水域通航环境模型，以航路长度代价、碍航物碍航代价和航路平滑代价为目标建立群桥水域航路规划代价模型，从船舶操纵性角度分析群桥水域船舶航路规划的约束条件，分别采用内罚-PSO和外罚-PSO方法实现群桥水域多约束航路规划，规划出船舶在给定条件下的最优航路。通过对比分析发现，内罚-PSO算法无论是在求解精度上还是收敛速度上均略优于外罚-PSO算法，可很好地应用于群桥水域航路规划研究中。

水路运输；群桥水域；环境建模；航路规划；内罚-PSO；外罚-PSO

ZOUChunming，ZHAOJunchao,YANGKe，XUYanmin，GAORujiang，JINCheng，CHENMin

Abstract: For navigation safety in multi-bridge waters and the safety of the bridges, as the illustrative example, the Wuhan section of the Yangtze River are investigated, which reveals the characteristics of the area: small bridge interval, zigzag distribution of bridge navigation holes, unparallel bridge axis and complex traffic flow. The environment model of the multi-bridge area is built and the route cost model is established factoring in the costs associated with the route length, the hinder degree and the smoothness of the path. The multi constraints of the route planning are set based on maneuverability of the ship. The algorithms for interior penalty PSO and exterior penalty PSO are used to solve the route planning cost model respectively. The results show that either penalty PSO algorithm works but the interior penalty PSO has better performance than exterior penalty PSO in both calculation precision and convergence speed.

Keywords: waterway transportation; multi-bridge water area; environment modeling; route planning; interior penalty PSO; exterior penalty PSO

随着我国沿江省市经济高速发展，大量跨江桥梁呈集群化建设，以近距离多桥梁为特征的群桥河段已在多个水域形成。目前船撞桥事故时有发生，研究群桥水域通航安全问题的必要性日益凸显。由于桥梁集群建设的情况是近几年才出现的，且群桥水域正在形成，因此在国内外针对桥区通航安全的研究[1-3]中，有关群桥水域通航安全的研究尚未系统化，有关航路规划的研究主要集中在机器人[4]和无人机[5]方面，而有关船舶航路规划[6]，尤其是限制水域航路规划的研究相对较少。随着自动控制技术不断发展，对桥梁船舶自主航行理论体系进行研究是提高桥区船舶通航安全的关键。对此，结合群桥水域通航环境特点，开展群桥水域航路规划研究，为实现群桥水域船舶自主航行提供理论支撑。

1 航路规划建模

1.1群桥水域通航环境特征分析

群桥水域最突出的特征是桥梁与桥梁的间隔较小。桥梁通航孔交错也是群桥水域的一个重要特点。由于不同桥梁所处的地理位置、水文等要素、建造年份及设计理念不同，群桥水域桥梁通航孔跨度不尽相同，通航孔交错现象十分明显；受长江水流方向变化、水文条件变化、深泓变化、两岸地理条件及交通规划等因素影响，不同桥梁轴线一般不会在同一个方向上。此外，群桥河段交通流量较大，航道内可能会存在礁石、沉船等障碍物，客观上增大了群桥水域船舶航行的难度。

1.2群桥水域环境建模

为简化计算，对长度和距离等变量进行无量纲化处理。在计算过程中，可将距离和长度等变量除以船长实现无量纲化，因此需要选取适当的船型作为无量纲化基准。这里选取内河3 000吨级船舶为代表船型，其长度L为110 m。选择长江武汉段4座桥梁进行建模，并在模型中设置2处沉船，其安全半径取2L。结合研究目的，暂时不考虑群桥水域交通流影响。群桥水域船舶通航环境模型见图1。

图1 群桥水域船舶通航环境模型

2 航路规划代价函数建模

2.1代价函数选取

船舶航行时需考虑燃油和障碍物等信息，航路规划的主要任务是寻找一条从起始点(xs,ys)到目标点(xf,yf)的航程最短且与障碍物无碰撞的路径。

2.1.1航路长度代价

为方便计算，首先将航路规划问题转化为求多维函数极值问题，将原坐标转换为以航路规划起始点和目标点连线为横轴的新坐标系x′Oy′，θ为原坐标系xOy与新坐标系x′Oy′的夹角。转换关系为

(1)

将起始点与目标点的连线分为d+1份，在每个等分点处作横轴的垂线，从起始点到目标点按顺序取各垂线上的任意一点组成一个船舶航路序列点，根据航路点纵坐标组成的向量y=(ys，y1，y2，…，yd，yf)即可确定一条唯一的路径。

当船舶沿着航路Lij航行时，船舶的航路长度代价J1的计算模型为

(2)

2.1.2碍航物碍航代价

当障碍物中心与该段航路距离大于安全半径时，N个障碍物对其产生的总碍航代价J2为

(3)

式(2)中：点(x,y)为障碍物(xs,ys)在相邻路径点上的投影；式中分母为障碍物中心与当前航路段间的距离。

若障碍物中心与该边的距离小于安全半径，则再将各段航路分10段，取相应的点计算产生的碍航代价。障碍物碍航代价示意见图2。

图2 障碍物碍航代价示意

碍航代价的计算式为

(4)

式(4)中：Lij为连接点i与j间的距离；d0.1,k为Lij边上的1/10分点与第k个障碍物中心间的距离。

2.1.3航路平滑代价

2.2约束条件分析

船舶在桥区航行时会受到航道条件、气象水文条件、船舶操纵性和交通流条件等条件限制，群桥水域船舶航路规划的约束条件应有多种。由于气象水文条件和交通流条件属于动态变量，因此这里只考虑可航水域边界和船舶操纵性等静态约束条件。

2.2.1可航水域边界

在航船舶受水动力影响会产生一定的下沉量，因此除考虑本船的吃水情况以外，还须考虑留有一定的富余水深。由于内河水域的等深线均为不规则曲线，因此很难找到精确的可航水域边界。这里将可航水域边界简化为2条直线，直线中间的区域即为船舶可航水域。各航路规划点的纵坐标所对应的边界值分别记作ylb和yup。

2.2.2转向角

由于船舶自身惯性较大，因此其在受限水域一旦开始转向将很难及时停止。转向角过大会导致船舶不得不通过操较大的舵角来控制该局面，而内河可航水域范围相对较小，一旦所操舵角过大而又回舵不及时，将导致船舶驶出航道或造成其他危险。因此，在航路规划时应保证规划航路的转向角限制在一定的范围内。这里将转向角临界值记为θ0。

2.2.3相邻转向点距离

船舶对舵令的响应速度受其追随性影响，追随性越差，船舶在操舵后开始变向所需的时间和转向后停止转向所需的时间越长；此外，船舶从左舵转为右舵时，其转艏角速度方向变化会滞后于舵角变化。因此，船舶相邻转向点间的距离应存在一个临界值，该临界值能保证船舶刚好从第1个转向点顺利地转到第2个转向点。这里将该临界值记为L0。

2.3航路代价建模

航路规划目标函数包括航路长度、碍航和航路光滑代价函数，该问题严格来讲属于多目标优化问题。目前求解多目标优化问题的方法主要分为基于单目标的多目标优化和基于启发式方法的多目标方法2类[7-8]，其中基于单目标的多目标优化方法主要通过应用某些已知的知识将多目标转化为单目标，通过求解转化后的单目标问题得到一个多目标最优解，常见的方法有加权法、约束法、目标规划法和极大极小法等。这里结合所研究的目标，选择加权法处理航路规划问题。若将航路长度代价权重记作k1，将碍航代价权重记作k2，则相邻航段夹角标准差在目标函数中所占的比重为1-(k1+k2)，优化后的群桥水域航路规划目标函数为

minJ=k1J1+k2J2+(1-k1-k2)σ

(5)

根据以上模型求解所得的最小值即为航路规划的最优值，该最优值表示沿当前航路航行时船舶和经过障碍物的最近距离的倒数与航程之和最小，且航路最光滑。在安全的基础上，该值越小表示航路越优。

3 PF-PSO航路规划

内点惩罚函数法和外点惩罚函数法[9-10]是目前常用的2种约束处理方法。这里可航水域边界上限由点(5，20)与(69，40)之间的线段确定，可航水域边界下限由点(5，10)与(69，30)之间的线段确定，船舶转向角临界值设为30°；将>10°的相邻航段夹角的顶点看作船舶的转向点，相邻转向点间的临界距离设定为8倍船长。为简便，分别将2种处理方法简称为内罚-PSO算法和外罚-PSO算法。

3.1内罚-PSO航路规划

内点惩罚函数主要通过逐步缩小惩罚因子系数使目标函数中惩罚项随迭代次数增加对整个目标函数的影响程度逐渐减小，函数逐渐收敛于最优解。采用内点惩罚函数的方法对多约束群桥水域航路规划目标函数进行处理，构造惩罚函数为

minPF=k1J1+(1-k1)J2+(1-k1-k2)σ+

(6)

初始惩罚因子通常可取0.1和0.01等值，经试验，初始惩罚因子取0.1和0.01时算法的求解精度和收敛代数并未出现显著变化。这里初始惩罚因子选择0.1，运用PSO算法对模型进行求解，航路规划结果和收敛情况分别见图3和图4。

图3 内罚函数航路规划结果

图4 内罚函数航路规划迭代曲线

由图3可知，运用内罚-PSO算法求得的全局最优值为42.48，算法大约在130次迭代之后即进入稳定收敛，收敛速度较快。

3.2外罚-PSO航路规划

外点惩罚函数主要通过逐步扩大惩罚因子系数使目标函数中的惩罚部分随迭代次数增加对不符合约束条件解的惩罚作用越来越大，在迭代中逐步被淘汰，函数迭代所求解逐步向最优解靠拢。对群桥水域多约束航路规划目标函数进行处理，当所求解满足约束条件时，目标函数由式(4)计算；当不满约束条件时，目标函数为

minPF=k1J1+(1-k1)J2+(1-k1-k2)×

(7)

经多次验证，初始惩罚因子暂取2。运用PSO算法求解，航路规划结果和收敛情况分别见图5和图6。

图5 外罚函数航路结果

图6 外罚函数航路规划迭代曲线

由图5可知，运用外罚-PSO算法求得的全局最优值为42.697，算法约在145次迭代之后进入稳定收敛，收敛速度和求解精度均能满足计算要求。

3.3惩罚函数PSO航路规划结果分析

由算例可知，内罚-PSO算法和外罚-PSO算法均可搜寻到多种约束条件下的船舶最优航路。由于最优航路是通过求解代价函数的最小值得到的，因此求解所得值越小，认为其求解精度越高。内罚-PSO算法平均在110～130次迭代之后即进入稳定收敛，平均全局最优值为42.39；6次运行中外罚-PSO算法平均在120～150次迭代之后即进入稳定收敛，平均全局最优值为42.56。2种处理方法的运行时间几乎相等，内罚-PSO算法的平均收敛代数及所求最优值略小于外罚-PSO算法，其无论是在收敛速度上还是求解精度上的表现均略优于外罚-PSO算法。

4 结束语

以提高群桥水域通航安全为目标，以航路规划为切入点，分析群桥水域通航环境特征，建立群桥水域航路代价模型，并从船舶操纵性角度分析群桥水域船舶航路规划的约束条件，建立多约束群桥水域航路规划代价函数。分别采用内罚-PSO和外罚-PSO算法实现群桥水域多约束航路规划，并对所求解进行对比分析，得出内罚-PSO算法无论是在求解精度上还是收敛速度上均略优于外罚-PSO算法的结论。此外，暂未考虑群桥水域内交通流对规划航路的影响，后期可考虑开展动态环境群桥水域航路规划的研究。

[1] 邱野. 顺直及弯曲河道条件下桥群合理间距的分析[D]. 长沙：长沙理工大学, 2011.

[2] 陈明. 山区河流桥群河段桥梁跨度与间距对通航影响的研究[D]. 重庆：重庆交通大学, 2010.

[3] 林巧. 重庆菜园坝桥群河段桥梁间距与通航条件研究[D]. 重庆：重庆交通大学, 2010.

[4] ASADI S, AZIMIRAD V, ESUAMI, et al. Immune-Wavelet Optimization for Path Planning of Large-Scale Robots[J]. Robotica, 2014, 32(1): 77-95.

[5] ALTMANN A, NIENDORF M, BEDNAR M, et al. Improved 3D Interpolation-Based Path Planning for a Fixed-Wing Unmanned Aircraft[J]. Theory and Applications, 2013，76(1): 185-191.

[6] KUCZKOWSKI L, SMIERZCHALSKI R. Comparison of Single and Multi-Population Evolutionary Algorithm for Path Planning in Navigation Situation[J]. Solid State Phenomena, 2014，210: 166-177.

[7] 刘慧慧. 一种改进的粒子群多目标优化算法研究[J]. 计算机技术与发展, 2015(1): 87-90.

[8] 厍向阳, 蔡院强, 董立红. 新的基于多目标优化的推荐算法[J]. 计算机应用, 2015，35(1): 162-166.

[9] 司呈勇, 兰天, 胡俊杰，等. 关于惩罚函数中惩罚系数的讨论[J]. 控制与决策, 2014，29(9): 1707-1710.

[10] 李宜萱, 金治群, 程军蕊，等. 一种基于AEA算法的改进的惩罚函数法[J]. 计算机与应用化学, 2014，31(12): 1479-1484.

RoutePlanninginMulti-BridgeWaterAreaUnderMultiConstraintsBasedonPenalty-PSO

(Hubei Inland Shipping Technology Key Laboratory, Wuhan University of Technology, Wuhan 430063, China)

U612.1

A

2016-02-26

国家自然科学基金(51109173)；中央高校基本科研业务费专项资金(2013-Ⅱ-019)

邹春明(1969—)，男，湖北云梦人，船长，主要从事智能航海相关研究工作。E-mail:1842645227@qq.com

1000-4653(2016)02-0067-04