张新宇， 林 俊， 郭子坚， 陈 向

(1.大连海事大学 航海动态仿真与控制交通部重点实验室，辽宁 大连 116026；2.大连理工大学 水利工程学院，辽宁 大连 116024； 3.龙岩学院 机电工程学院， 福建 龙岩 364012)

基于模拟退火多种群遗传算法的港口船舶调度优化

张新宇1,2， 林 俊3， 郭子坚2， 陈 向1

(1.大连海事大学 航海动态仿真与控制交通部重点实验室，辽宁 大连 116026；2.大连理工大学 水利工程学院，辽宁 大连 116024； 3.龙岩学院 机电工程学院， 福建 龙岩 364012)

为协调港口航道与泊位资源，提高港口船舶调度效率，从单向航道出发，根据先后调度的2艘船舶的进出港方向和所停靠泊位的远近区分两船间的相对关系，建立以总等待时间最少为目标的调度优化数学模型。设计适用于港口船舶调度优化的模拟退火多种群遗传算法(Simulated Annealing and Multiple Polulation Genetic Algorithm,SAMPGA)，模拟某港口不同调度规模的船舶进行仿真试验，与先到先服务规则(First Come First Served,FCFS)和简单遗传算法(Simple Genetic Algorithm,SGA)进行比较，证明SAMPGA在解决航道和泊位协调调度问题上的适用性。结果表明：在现有的调度规则下对航道和泊位进行协调调度能减少船舶的等待时间和总调度时间，但实际调度规则需要考虑的限制因素更多，需对模型作进一步优化。

水路运输;单向航道；协调调度；船舶调度优化；模拟退火多种群遗传算法

Abstract: In order to improve the operation efficiency of the vessels and ports a mathematical model is established reflecting the relation between the vessel scheduling and the channel-berth allocation on the assumption of one-way channel. After determining the positional relationship between two successive vessels based on their sailing directions and the distances to the berths, this model solves the problem by means of the Simulated Annealing and Multiple Population Genetic Algorithm (SAMPGA) with the objective of minimum total waiting time. Simulation tests with vessels of different scales are conducted. The results indicate that the SAMPGA is more effective in coordinating channel and berth resources than the Simple Genetic Algorithm (SGA) or the "First-come, First-served" principle.

Keywords: waterway transportation; One-way channel; coordinated scheduling; vessel scheduling optimization; SAMPGA

随着船舶逐渐大型化和港口吞吐量不断提升，港口船舶调度问题备受有关部门和学者的关注。相关研究主要集中在以下几个方面。

1) 航道通过能力方面：刘敬贤等[1]从港口航道系统特征和船舶交通流特征出发建立基于船舶行为特征的港口航道通过能力模型；代君等[2]从船舶领域出发提出一种受限航道通过能力计算方法；宋向群等[3]研究通航历时对沿海散货港区航道通过能力的影响，结果表明单线航道通过能力与通航历时呈负指数关系，双线航道通过能力不受通航历时的影响。以上研究对港口建设有一定的指导意义。

2) 航道使用效率方面：王小平等[4]以船闸调度为研究对象建立三峡-葛洲坝水利枢纽联合调度模型，但没有考虑船舶通过航道的时间，不适用于一般航道的船舶调度；徐国裕等[5]在船舶调度中引入优先级理论，根据船舶种类、吨位、吃水、装载状况及泊位距离推定综合权重，运用工作排序理论建立单向航道船舶进出港最佳排序模式，该模式在提高通航效率方面优于人工排序模式。

3) 泊位分配与其他港口资源协调调度方面：ETSUKO等[6]和IMAI等[7-8]对公共码头、集装箱码头中的泊位分配问题进行研究，探讨泊位分配中的服务优先权问题；HAN等[9]建立基于不连续泊位的具有不同服务优先权的整数规划模型，解决船舶到达时刻和装卸作业时间不确定情况下的泊位与岸桥协调调度问题；JIN等[10]基于集装箱码头泊位调度问题研究岸桥动态优化调度问题；王中华[11]在泊位调度模型的基础上建立基于动态船舶作业时间和船舶加权在港时间的船舶调度模型，并设计改进遗传算法进行求解，得到船舶调度近似最优解；王冠儒[12]基于泊位分配问题建立船舶调度数学模型，利用遗传算法(Simple Genetic Algorithm,SGA)实现船舶的自动分配，生成合理的船舶调度序列。上述研究仅针对泊位及其他码头资源的调度，忽略了船舶密集到港时航道对船舶调度的影响。

综上，已有的船舶调度研究主要针对的是单一的航道或泊位，而港口船舶调度是一个连续的过程，应通过协调航道与泊位资源来解决船舶在港作业时航道和泊位使用冲突。这里在现有航道与泊位分配研究的基础上，基于单向航道对港口船舶优化问题进行研究。

1 港口船舶调度模型

实际的船舶进出港是一个连续、受多种因素影响的过程，而船舶调度是港口管理中的重要环节，可在满足港口管理规则的前提下提高船舶的通航效率、保证船舶安全航行。船舶调度与泊位是否空闲、船舶到达时刻及船舶当前位置与航道间的距离等诸多因素有关。目前船舶泊位作业计划是由码头公司制定的，而船舶交通管理(Vessel Traffic Service，VTS)中心则负责指挥船舶进出航道、锚泊和靠离泊。因此，船舶调度作业主要由这2个部门协调完成，其中：VTS中心主要负责船舶在航道航行期间的安全；而码头公司则主要考虑船舶在港作业的效率。对此，建立基于航道和泊位资源协调的船舶调度模型，其关键在于对进出港船舶进行排序，确定船舶进出港的时机，在保证船舶安全航行的前提下使其尽快完成作业计划。

1.1模型假设

对模型作以下假设:有多个锚地，且锚地容量无限;航道水深满足船舶进出港的要求;引航员和拖船可随时到位;码头已制定好靠泊作业计划;其他人为因素和环境因素均不对调度过程产生影响。

1.2模型建立

建立的调度模型示意图见图1。

1) 船舶向VTS中心发送预计抵港报告，码头公司根据抵达报告的时间安排船舶靠泊。

2) 当船舶到达VTS监控水域时，VTS根据航道和泊位此时的状态安排船舶进港靠泊或在锚地抛锚等待，直到进港船舶完成靠泊作业或出港船舶离开港口水域为止。

该模型的核心在于根据船舶的到港顺序合理安排船舶进出航道，减少单向航道的进出转换时间，在保证安全的前提下使尽可能多的船舶在较短的时间内完成港口作业计划。模型中各变量的含义分别为：Numberv为调度船舶总数;Numberb为泊位数;ta为船舶到达时刻;ts为调度开始时刻;t0为靠泊时间;tc1为上航道时间;tc2为下航道时间;d为锚地与航道起点间距离;c1为航道长度;tgap0为同向安全时间间隔;tgap1为反向安全时间间隔;tf为调度完成时刻;L为船舶长度;V为在港航行平均速度;S为航道终点到泊位的距离;M为极大值。

模型中的决策变量如下。

1) 决策变量IO表示船舶进出港方向。IOi=0表示船舶进港；IOi=1表示船舶出港。

2) 决策变量R表示泊位远近的关系。Ri(i-1)=1表示第i艘船舶停靠的泊位较上一艘调度船舶(i-1)停靠的泊位远；Ri(i-1)=0表示第i艘船舶停靠的泊位较上一艘调度船舶(i-1)停靠的泊位近。

3) 决策变量kij表示船舶i停靠泊位j。kij=1表示泊位空闲；kij=0表示泊位正在使用。

调度数学模型为

(1)

Subject to.

tgap0=6Li/vi-1

(2)

tgap1=6max{Li-1,Li}/vi-1

(3)

tc1i=tsi+(IOi)di/vi+(1-IOi)si/vi

(4)

tc2i=tc1i+cl/vi

(5)

tfi=tc2i+(IOi)si/vi

(6)

(7)

(8)

tc2i-1+tgap1≤tc1i

(9)

(10)

tai≤tsi

(11)

式(1)为目标函数，表示所有船舶的总等待时间最少；式(2)为同向航行时两船间安全航行的时间间隔，根据港口航行规则要求，同向航行的两船在空间上必须保证6倍于前船船长的安全间距，转化为时间约束即为两船之间的时间间隔；式(3)为反向航行时两船间的安全时间间隔；式(4)为船舶i上航道时刻，即船舶到达航道起点的时刻；式(5)为船舶i下航道时刻，即船舶到达航道终点的时刻；式(6)为调度结束时刻，即船舶靠上泊位或离开港口航道的时刻；式(7)为先后进港的两船之间的安全约束；式(8)为先后出港的两船之间的安全约束；式(9)为出港船舶先调度、进港船舶后调度时的安全约束，即反向航行的两船在航道起点处相遇且出港船舶(i-1)先调度、进港船舶后调度，在航道起点保持反向的安全间距；式(10)为进港船舶先调度、出港船舶后调度时的安全约束，即反向航行的两艘船在港池处相遇且进港船舶(i-1)先调度、出港船舶后调度，两船在靠近泊位处保持反向的安全间距；式(11)表示船舶调度开始时刻不早于船舶到达时刻。

2 协调航道与泊位的船舶调度

2.1算法设计

遗传算法具有很强的并行计算和全局搜索能力，适于求解各种复杂的问题，已在很多领域得到应用。为解决遗传算法容易陷入局部最优及后期收敛较慢的问题，采用多种群遗传算法并加入退火机制，即模拟退火多种群遗传算法(Simulated Annealing and Multiple Population Genetic Algorithm,SAMPGA)。由于其前期搜索空间较大、退火温度高、适应度值的变化范围大，因此可保证算法不会陷入局部最优的情况；随着温度不断下降，搜索空间会急剧缩小，算法后期可发挥遗传算法局部搜索的能力，从而保证最终结果收敛到最优解的区间。在SAMPGA中，为使每次搜索都能达到理想状态，其退火速度必须足够慢，因此冷却系数最好取接近于1的值。

2.2仿真试验

由于没有直接可用的数据来验证模型和算法，因此模拟某港口航道的船舶调度数据进行验证，具体为：第1锚地(A1)距离航道起点6 n mile，第2锚地(A2)距离航道起点8 n mile，航道长度cl为6 n mile，共18个泊位。船舶到港时间间隔服从负指数分布，其参数λ取20，时间段为09:00-10:00。为衔接每个时间段，还需考虑初始状态航道上是否有船。假设初始状态航道上有船，船舶初始状态基本信息见表1。泊位信息及初始忙闲状态见表2，其中距离指口门与泊位间的距离，n mile。本阶段调度船舶的信息见表3。

将上述数据读入程序中进行计算，算法的基本参数为：种群大小250，代沟0.9，交叉概率0.9，变异概率0.05，最大遗传代数500，退火初始温度为100 °C，冷却系数0.9。最优调度方案见表4,算法收敛结果见图2。

表1 船舶初始状态信息

表2 泊位信息及初始忙闲状态

表3 调度船舶的信息

表4 最优解调度方案

3 结果分析

从以上优化结果看，当泊位资源有限时，整体上停靠同一泊位的船舶先出后进，局部范围内调度趋于先快后慢，出港船舶按照泊位先近后远的规律，进港船舶按照泊位先远后近的规律，符合实际的港口调度流程。将SAMPGA与SGA进行比较，结果如图2所示。从图2中可看出，SAMPGA有多个种群同时搜索，110代左右收敛；SGA仅有1个种群搜索，经过250代搜索后仍未找到最优解；相对而言，SAMPGA收敛较快。从表5和图3中可看出，SAMPGA的优化效果较SGA和先到先服务规则(First Come First Served,FCFS)好，总等待时间为1 188 min，较后者分别下降86%和31%；总调度时间为325 min，与FCFS和SGA相比分别下降69%和21%，且最长等待时间为176 min。SAMPGA的调度优化效果明显优于FCFS和SGA。从算法的角度看，SAMPGA能在较短的时间内完成调度优化作业，但其数学模型是在一定简化基础上得出的，纵然对实际港口的作业具有参考和辅助决策的作用，但就实际需要的调度系统来说还有很多需要完善的地方。

图2 仿真结果

表5 SAMPGA调度优化、SGA调度优化与FCFS调度结果

图3 3种调度方法用时对比

4 结束语

从单向航道出发协调航道与泊位资源，根据先后调度的2艘船舶的进出港方向和泊位远近区分二者之间的相对关系，建立以总等待时间最少为目标的调度优化数学模型。设计适用于港口船舶调度优化的模拟退火多种群遗传算法，主要设计顺序编码算子和染色体修复算子等。模拟某港口不同调度规模的船舶,进行相关试验，结果表明：依靠该模型和算法能大幅度减少船舶总调度时间和总等待时间，有效提高港口船舶调度效率。与先到先服务规则和简单遗传算法相比，该模型和算法趋于先出后进、先快后慢，出港船舶按照泊位先近后远的规律，进港船舶按照泊位先远后近的规律。

[1] 刘敬贤,文元桥. 基于船舶行为特征的港口航道通过能力仿真[J]. 大连海事大学学报, 2009,35(2): 31-33.

[2] 代君,王当利,刘克中. 基于船舶领域模型的港口受限航道通过能力计算方法[J]. 武汉理工大学学报:交通科学与工程版, 2009,33(4):679-682.

[3] 宋向群,张静,郭子坚,等. 通航历时对沿海散货港区航道通过能力的影响分析[J]. 港工技术, 2010,47(2):18-20.

[4] 王小平,齐欢,肖恒辉，等. 基于串联排队网络的三峡-葛洲坝水利枢纽联合调度模型[J]. 交通运输工程学报,2006,6(3):82-86.

[5] 徐国裕,郭涂城,吴兆麟. 单向水道船舶进出港最佳排序模式[J]. 大连海事大学学报, 2008,34(4):150-153.

[6] ETSUKO N, IMAI A, PAPADIMITRIOU S. Berth Allocation Planning in the Public Berth System by Genetic Algorithms[J]. European Journal of Operational Research,2001(131):282-292.

[7] IMAI A, NISHIMURA E, PAPADIMITRIOU S. Berth Allocation with Service Priority[J]. Transportation Research Part B, 2003,37:437-457.

[8] IMAI A, SUN X, NISHIMURA E,etal. Berth Allocation in a Container Port: Using a Continuous Location Space Approach[J]. Transportation Research Part B, 2005,39:199-221.

[9] HAN Xiaole, LU Zhiqiang, XI Lifeng. A Proactive Approach for Simultaneous Berth and Quaycrane Scheduling Problem with Stochastic Arrival and Handling Time[J]. European Journal of Operational Research, 2010,207: 1327-1340.

[10] JIN Zhihong, LI Na. Optimization of Quay Crane Dynamic Scheduling Based on Berth Schedules in Container Terminal[J]. Journal of Transportation System Enginering and Information Technology, 2011, 11(3):58-64.

[11] 王中华. 基于遗传算法的港口船舶调度优化问题研究[D]. 上海:上海海事大学, 2007.

[12] 王冠儒. 基于遗传算法的VTS船舶调度的设计与实现[D]. 大连:大连海事大学, 2012.

VesselSchedulingOptimizationBasedonSimulatedAnnealingandMultiplePopulationGeneticAlgorithm

ZHANGXinyu1,2,LINJun3，GUOZijian2,CHENXiang1

(1. Key Laboratory of Maritime Dynamic Simulation and Control of Ministry of Transportation, Dalian Maritime University, Dalian 116026, China; 2. School of Hydraulic Engineering, Dalian University of Technology, Dalian 116024, China; 3. School of Mechanical and Electrical Engineering, Longyan University, Longyan 364012,China)

2015-11-18

国家自然科学基金(51309043)；中国博士后科学基金(2014M551095)；辽宁省高校杰出青年学者成长计划(LJQ2014052)；辽宁省教育厅重点实验室基础研究项目(LZ2015009)

张新宇(1978—)，男，吉林长春人，副教授，博士生，研究方向为交通信息工程及控制。E-mail:41544391@qq.com

1000-4653(2016)01-0026-05

U692.43

A