复杂水网中船舶航行路径多目标规划模型

周春辉，陈铭章，何义才，徐周华，文元桥

(1.武汉理工大学 航运学院，武汉 430063；2.湖北省内河航运技术重点实验室，武汉 430079；3.武汉大学 测绘学院，武汉 430070)

复杂水网中船舶航行路径多目标规划模型

周春辉1,2，陈铭章1,2，何义才1,3，徐周华1，文元桥1

(1.武汉理工大学 航运学院，武汉 430063；2.湖北省内河航运技术重点实验室，武汉 430079；3.武汉大学 测绘学院，武汉 430070)

在深入研究船舶交通流理论的基础上，结合内河复杂水网独有的特性，构建复杂水网条件下的船舶航行路径多目标规划模型；运用层次分析法获取多目标规划模型各子目标的权重；利用线性加权法和Floyd算法求解得到综合最优航行路径。该模型不仅综合考虑了影响航行路径选择的各种因素，而且对其进行了合理的量化，并通过算例证明了模型的合理性和有效性。

复杂水网；船舶交通流；最优航行路径；多目标规划；线性加权法；Floyd算法

近年来，随着水上通航需求不断上升，国内部分通航条件受限的河段(尤其是江苏、浙江一带的水网区域)拥挤堵塞状况日益严重。无论是从船舶自主航行路径选择的角度还是从内河航运管理部门调度需要的角度考虑，都迫切需要整个水网层面的航行路径规划方案。目前国内外相关学者已在这方面进行一些初步研究。

李文欢[1]对集装箱班轮运输的航线网络优化问题进行深入研究，提出利用图论中的旅行商问题模型及整数规划等方法求解集装箱船最优航行路径，并依据长江中下游集装箱班轮运输航线网络的统计信息设计优化算法，对模型进行验证。刘建秋[2]从系统总收益最大化的角度出发，综合考虑模糊变量和随机变量，建立不确定环境下的支线集装箱班轮优化网络模型，并以长三角某运输公司为例，采用蚁群算法求取网络运输路径。PFLIEGL[3]针对内河水网中河道及船闸通航条件的动态变化使调度变得困难，提出在澳大利亚Danube河上建立内河信息服务系统，以促进水网中船舶的调度与管理。

总的来说，目前水网层面上的船舶航行路径选择和船舶联合调度尚处在研究探索阶段，主要以信息共享为前提，一定程度上运用预调度协调机制来提高航道的利用率，尚没有实用的调度和路径规划模型，且相关研究主要集中在涉及船闸的船舶调度方面，很少涉及复杂水网条件下的船舶调度和航行路径规划。因此，研究复杂水网中船舶航行路径多目标规划模型不仅对船舶自主航行路径选择的研究具有一定的指导意义，而且对内河船舶管理调度部门管理调度船舶具有一定的参考价值。

1 航行路径选择的多目标规划模型

1.1问题分析

影响船舶航行路径选择的因素可分为主因素观和客观因素2类，其中：主观因素主要包括驾驶员的驾驶经验、驾驶路径选择偏好及航行目的等；客观因素主要包括航行总路程、总时间、拥挤程度及通行费用等。因此，最优航行路径选择是一个各种因素交互作用的多目标规划问题。[4]

1.2目标函数

根据对最优航行路径选择影响因素的分析，选择总路程最小化、航道综合时间阻抗最小化、拥挤程度最小化和通行费用最小化作为模型子目标。

1.2.1总路程最小化

(1)

1.2.2航道综合时间阻抗最小化

与道路交通中的交通阻抗不同，内河航道的交通时间阻抗由航道基本段和船闸时间阻抗2部分组成。根据水网交通分配路径的选择理论，水网时间阻抗函数模型[5]为

(2)

文献[5]基于船舶交通流理论，结合交通流特性中的流量、速度和密度等3个参数提出3个参数间的关系模型，其中速度-流量的关系为

(3)

式(3)中：q为船舶流流量，艘/h；v为船舶流航行速度，km/h；vf为自由流速度，km/h；k为船舶流密度，艘/km；kf为自由流状态下航道中的最大船舶密度，艘/km；kj为阻塞密度，艘/km；ρ为波速系数，0≤ρ≤1。

基于船舶交通流理论，假设航道段a上船舶的平均航行时间Ra(q)与航道长度la及船舶航行的平均速度va(q)有关，即

(4)

根据交通流理论，假设航道上船舶的到达分布符合泊松分布[6]，λb为船闸b处船舶的到达率，E(T)为过闸服务时间，Var[T]为服务时间的方差，得到服务强度ρb=λb∘E(T)。由Pollaczck-Khintchine公式可得M/G/1模型系统内船闸b的平均排队等待船舶数Nb为

(5)

(6)

综上所述，假设船舶倾向于选择航行总阻抗最小的路径，最优航行路径选择的目标函数为T2，则联立式(2)～式(6)可得

(7)

1.2.3拥挤程度最小化

拥挤程度S[7]可用航道中交通流的饱和度来衡量。假设航道段a上的设计通行能力为ca，实际交通流量为fa，则饱和度sa=fa/ca。假设船舶倾向于选择从起点到终点拥挤程度最小的航行路径，则最优航行路径选择的目标函数T3为

(8)

1.2.4通行费用最小化

船舶的通行费用主要包括燃料费和过闸费2部分。由于船舶在内河中航行时周围环境稳定，风浪影响几乎可以忽略不计，因此在船舶载重不变的情况下可假设航行所消耗的燃料费与航程成正比。由此，在通行费用最小化的目标下，最优航行路径选择的目标函数T4为

(9)

1.3航行路径选择的多目标规划模型

联立式(1)、式(7)～式(9)得最优航行路径选择的多目标规划模型为

(10)

1.4模型求解

对于多目标规划问题，可用线性加权法、约束法、效用系数法和评价函数法等方法进行求解。根据所建立的多目标规划模型和各分目标的特点，采取线性加权法进行求解。考虑到上述多目标规划模型的4个子目标的量纲不同，采用极差化法对变量进行无量纲化处理。[8]

(11)

(12)

利用线性加权法对多目标规划模型进行求解，得

(13)

式(13)中：λ1，λ2，λ3，λ4分别为4个子目标的权重系数，既可采用层次分析法求取，也可根据船舶对各个子目标的偏好程度或船舶调度者的调度意愿来主观确定。

2 算例分析

2.1层次分析法确定权重

由于建立的多目标规划模型有4个子目标，而每个子目标的重要性无论是对调度者还是对船舶驾驶员而言都是不同的，因此根据层次分析法[9]确定4个子目标的权重系数λ1，λ2，λ3和λ4的值。

2.1.1建立评价体系

根据层析分析法评价体系构建规则，构建最优航行路径评价体系(见图1)。

图1 航行路径选择评价体系

2.1.2确定准则层判断矩阵

利用表1所示的1～9标度法对准则层中的4个因素(总航程B1，综合时间阻抗B2，拥挤程度B3，通行费用B4)进行成对比较。

表1 1～9标度法的意义

2.1.3最大特征根与一致性检验

求解可得最大特征根λmax=4.12，特征向量(权重系数)λi=(0.05，0.57，0.26，0.12)。一致性指标计算式为

(14)

查找Saaty给出的平均随机一致性指标RI[9]，计算一致性比例可得

(15)

由于0.043<0.1，因此判断矩阵的一致性是可以接受的，权重系数λi=(0.05，0.57，0.26，0.12)。

2.2确定邻近点之间的“距离”

由式(13)可得4个子目标的取值对于船舶或船舶调度者来说均是越小越好，因此式(13)的取值可认为是“距离”。根据Floyd算法[10]的求解条件，需先确定邻近点之间的距离。在能获得数据和确定λ1～λ4的情况下，邻近点之间的“距离”容易求取。假设模型4个子目标的值计入4个数组(t1,t2,t3,t4)中，则多目标规划模型的值(即邻近点之间的“距离”)计入数组t中，t=λ1t1+λ2t2+λ3t3+λ4t4。

2.3计算结果与分析

假设两点之间没有直接连接或没有连接，则两点之间的距离定义为无穷大，通过确定t1,t2,t3,t4的值，并取λi=(0.05，0.57，0.26，0.12)，得邻近点之间的“距离”t(即赋权图的权矩阵，见图2)。

图2 水网示意及邻近点之间的“距离”

利用Floyd算法进行求解，上述t即为赋权图的权矩阵，得到水网中任意两点最短路径的长度d(i,j)和第i个点到第j个点最短路径中第i个点后继点的编号path(i,j)，见表2。

表2 i点到j点的最短路径中i点后继点编号

至此，即求出图1网络中任意两点之间的最短路径及其最短“距离”。例如，从表2中可查到点1到点8的最短路径path(1,8)为1—4—7—8。但是，该结果不是唯一的，会随着各种因素的变化而变化。例如:船舶的偏好或船舶调度者的意愿不同而使得λ1，λ2，λ3及λ4的取值不同；航道改道会导致总航程发生变化；航行时间及紧张程度不同会导致理解阻抗不同；随着时间的推移，船舶密度发生变化会导致拥挤程度不同；油价或过闸费用的变化导致通行费用上升。

3 结束语

针对最优航行路径选择问题的多样性特点，将该问题转化成一个具有4个子目标的多目标规划模型，并利用线性加权法和Floyd算法进行求解。通过分析，在获取航道资料、过闸费用、油价、水网中船舶的实时分布、船舶本身航行时间的紧迫度及航行目的等信息的条件下，可根据建立的多目标规划模型及其求解算法求得船舶的最优航行路径，实现复杂水网条件下船舶的自主航行路径选择和调度部门对船舶的宏观调度。

但是，运用建立的复杂水网条件下船舶联合调度多目标规划模型的前提是获得内河航运调度部门提供的航道信息和船舶交通流量信息，除了考虑航行路径路程、航行路径阻抗、航行路径拥挤程度及航行费用等4项评价指标之外，还可考虑服务水平、上水与下水等因素。此外，建立一个更加适合复杂、动态变化的水网交通调度模型是进一步研究的方向。

[1] 李文欢.集装箱班轮运输的航线网络优化研究[D].上海:上海海事大学,2007.

[2] 刘建秋.不确定环境下支线集装箱班轮网络优化研究 [D].大连:大连海事大学,2010.

[3] PFLIEGL R.Innovative Application for Dynamic Navigational Support and Transport Management on Inland Waterways:Experience from a Research Project on the Danube River[J].Journal of Transportation Research Board,2001,1763:85-89.

[4] 宗传苓,李相勇,王英涛.出行前路径选择的多目标规划模型[J].交通运输系统工程与信息,2005,5(6):58-61.

[5] 朱俊.基于船舶流的交通时间阻抗模型[J].武汉理工大学学报(交通科学与工程版),2010,34(3):591-594.

[6] 孙荣恒,李建平.排队论基础[M].北京:科学出版社,2002.

[7] 达庆东,张国伍.交通拥挤定量分析方法[J].交通运输系统工程信息,2002,2(4):45-48.

[8] 吕宝军.机动车出行路线选择及软件实现[D].天津:天津大学,2012：45-48.

[9] 司守奎,孙玺菁.数学建模算法与应用[M].北京:国防工业出版社,2011：167-171.

[10] 张秀兰,林峰.数学建模与实验[M].北京:化学工业出版社,2013：101-108.

Multi-ObjectiveProgrammingModelofShipSailingPathforComplexWaterNetwork

ZHOUChunhui1,2，CHENMingzhang1,2，HEYicai1,3，XUZhouhua1，WENYuanqiao1

(1.School of Navigation,Wuhan University of Technology,Wuhan 430063,China;2.Hubei Inland Shipping Technology Key Laboratory,Wuhan 430070,China;3.School of Geodesy and Geomatics,Wuhan University,Wuhan 430079,China)

On the basis of the vessel traffic flow theory,taking the unique characteristics of the inland water net,the multi-objective programming model of ship sailing path is established under the condition of complex water network,and the AHP is used to get the weights of each sub-goal of the multi-objective programming model.By means of the linear weighting method and Floyd algorithm the overall optimal sailing path is decided.This model,taking the factors that affect the sailing path selection into account quantitatively,is verified by a numerical example.

complex water network; ship traffic flow; optimal sailing path; multi-objective programming; linear weighting; Floyd algorithm

U697.1

A

2017-01-11

国家自然科学基金(51209166；51679180);湖北省交通厅科技计划项目(2014-721-4-2);武汉理工大学自主创新研究基金(2017-HY-B1-07)

周春辉(1978—)，男，湖北松滋人，博士，副教授，从事交通安全仿真方面研究。E-mail:chunhui@whut.edu.cn

陈铭章(1996—)，男，湖北黄冈人，学士,从事水路交通运输研究。E-mail:984393738@qq.com

1000-4653(2016)04-0078-05