连续泊位—岸桥—集卡调度模型构建及应用

，，， ，

(浙江工业大学 机械工程学院，浙江 杭州 310014)

由于受成本、场地和装卸设备技术参数及投资规模的制约，有效地对港口各种资源，如泊位、岸桥和集卡等进行集成调度才是提高集装箱码头作业效率的重要途径[1].国内外研究学者对港口物流资源调度做了深入研究.其中，关于泊位分配的研究：Kim等[2]对大型集装箱船舶的泊位分配物流资源调度做了深入研究，设计了模拟退火算法对所构建的混合整数规划模型进行求解.Imai等[3]针对连续型泊位的分配问题建立了以集装箱船舶的等待时间和作业时间最小为目标的数学模型，并采用拉格朗日松驰系数算法进行求解.关于岸桥分配的研究：禹美凤[4]以最小化船舶总在港时间、集装箱港口生产成本以及惩罚成本作为优化目标,建立多船到达情况的不确定优先权的柔性靠泊方式下的泊位—岸桥调度多目标数学模型.Zhu等[5]在研究岸桥调度过程中，考虑了外界的干扰约束，并先后使用了模拟退火法、遗传算法和贪婪算法进行求解.关于集卡调度的研究：Nishimura等[6]以车辆路径规划的视角研究了集卡的动态作业调度问题.Ng等[7]以集卡完成任务的总作业时间最短为目标，研究了集卡分配和运输路径问题.近年来，越来越多学者把多种资源进行联合调度研究：李娜等[8]研究了连续泊位与岸桥的联合调度问题，构建了混合整数规划模型，并使用新的启发式算法进行求解.刘慧莲[9]考虑船舶到港时间的不确定性，建立了泊位与岸桥联合调度的鲁棒优化模型，并用分支定界算法求解，得到了鲁棒模型的最优解.刘桂云等[10]针对连续泊位与岸桥联合调度问题，以最小化惩罚为优化目标建立数学模型，设计嵌套式遗传算法并求得船舶的靠、离泊时间和位置及最优装卸序列.

通过对文献的系统研究，对港口码头物流资源只进行单独的泊位分配、岸桥作业规划、集卡调度研究或考虑两个因素的联合调度研究存在一定的缺陷和不足.而为了实现集装箱港口码头作业效率的最优，必须将其视为一个完整的作业系统，从系统的角度出发，对泊位、岸桥和集卡进行集成调度研究.

1 问题描述

集装箱码头前沿作业系统中3 个重要因素就是泊位、岸桥和集卡.它们是集装箱港口码头的重要资源.船舶到港后，由于泊位资源限制会产生一定的候泊时间.靠泊之后，根据靠泊船舶的集装箱数量，指派一定数量的岸桥给船舶.在完成岸桥的指派工作后，需要为每一岸桥指派一定数量的集卡为其服务，并且集卡以作业组的形式进行装卸集装箱任务.在这个过程中，到港船舶的等待时间、在港作业时间以及集卡运输集装箱的作业时间等构成了码头主要的生产运作时间.所以，船舶依次到港后,如何根据现有有限的泊位资源,科学合理地为船舶指派泊位,会有效减少船舶的靠泊时间同时也会缩短其他船舶的待泊时间.此外,对于已经靠泊的船舶,如何科学合理地分配岸桥数量和为岸桥服务的集卡数量,也会在一定程度上影响船舶的靠泊时间进而影响整体的生产效率.与此同时，泊位分配的位置以及船舶本身的偏好靠泊位置都会影响集卡的运输距离，进而影响集卡的运输作业时间.那么把集卡的运输距离控制在一个合适的范围内，将会提高码头的整体生产效率.因此，这3 种资源的独立研究或是两者之间联合调度，都不能达到整体作业流程最优的结果，需要将泊位、岸桥和集卡这三者进行联合研究才能达到集装箱码头前沿作业的整体最优.

2 模型构建

2.1 模型假设

模型建立在调度前提前收到来自船舶代理公司相关资料的基础上，因此，船舶的靠泊偏好位置、装卸作业量和各个集装箱的存储位置已知.此外，模型还假设泊位是连续型，不考虑水深潮汐等其他物理条件的限制；忽略拖轮对船舶进出泊位时间的影响；码头堆场的进口箱区的各个箱区与出口箱区的各个箱区之间的距离相同；不考虑船舶的移泊和装卸过程中的平衡问题；每个岸桥的移动速度、工作效率相同；所有集卡作业效率相同，每辆集卡每次只能运1 个集装箱；集卡以作业组的形式指派给船舶，并共同服务于为船舶服务的所有岸桥；集卡到各个箱区的平均作业时间相同.

2.2 模型建立

考虑到泊位占用、岸桥与集卡的使用以及岸桥和集卡的相互等待的单位时间成本的差异，将集装箱船舶的每个作业环节都以费用支出和惩罚成本的形式表示.通过对泊位、岸桥和集卡这3 项资源的优化配置来实现计划期内所有的到港船舶总费用最少.目标函数为

(1)

约束条件分别为

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

xt(c+1)k-xtck+xt(c-1)k=-1，0，1， ∀t∈T，∀k∈V

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

3 算法步骤

遗传算法在搜索优化问题的全局或是接近全局最优解上有着良好的优势条件，模型得到的是相对最优下的调度方案，所以模型采用遗传算法进行模型求解.在经典的遗传算法上作了部分改进来求解上述模型[11].

Step1染色体编码和种群初始生产，计算种群的适应度函数值.

Step2设计迭代的终止条件，满足终止条件即终止; 否则，执行Step 3.

Step3对子代个体进行交叉变异操作，计算其当代的最优解.

Step4更新整体最优解.对当代最优解与存储单元解进行比较，若当代最优解更优，则更新; 若存储单元解更优，则存储单元解保持不变，返回Step 2.

3.1 染色体编码和种群初始化

根据数学模型的特点，构建一维染色体编码，如图1所示.染色体的长度是集装箱船舶数目N的4 倍，每一段染色体长度为集装箱船舶的数目，其中第一段(1～N)依次表示每一艘集装箱船舶的到港时间；第二段(N+1～2N)依次表示每一艘集装箱船舶的靠泊位置；第三段(2N+1～3N)依次表示每一艘集装箱船舶所分配的岸桥数目；第四段(3N+1～4N)依次表示每一艘集装箱船舶所分配的集卡数目.

12345123451234512345251617258402070503221610911814船舶的靠泊时间船舶的靠泊位置船舶分配的岸桥数船舶分配的集卡数

图1染色体编码

Fig.1Chromosomecoding

在生成初始种群的每个个体前，需要对集装箱港口码头的相关资源进行初始化.首先默认岸桥最初位置是均匀分布在码头岸线上，然后对每艘集装箱船舶进行资源配置，依次设置生成集装箱船舶的靠泊时间、靠泊位置、岸桥数目、集卡数目、实际开始装卸时间、实际离港时间、使用的岸桥编号和使用的集卡编号.然后根据其实际开始装卸时间和实际离港时间对岸线、岸桥和集卡资源的状态进行更新；根据集装箱船舶的靠泊位置对岸桥的位置进行更新.当完成所有集装箱船舶的相应参数的生成，才进入下一个初始解生成的重复过程.随机生成初始种群，初始种群的个体数设置为300 个.初始解的规模需要满足种群的合适规模才能结束初始解生成的循环过程.

3.2 适应度设计

适应度的值用于表示每一个个体的优劣性.适应度函数通常是根据模型的目标函数转换而成，根据目标函数的特点，取目标函数的倒数作为适应度函数.

3.3 选择操作的设计

根据染色体编码的特点以及所构建模型的特殊性，采用最佳保留策略和均匀排序相结合的选择方式[12]进行操作.

具体的操作过程如下：

1) 根据每个个体的适应度大小对新一代的个体进行降序排序.

2) 将排序中最前面两个，即复制保存最优的两个个体直接作为下一代个体.

3) 随机产生一个整数，按照上述的排列方式，去掉排序中的随机数个适应度值低的个体.

4) 下一代个体的的父代将从第3 步操作后剩余的个体中随机产生.每次随机选择两个个体作为进行下一步的交叉等过程的个体，随机选择多次直到达到足够的个体数目要求为止.

3.4 交叉操作的设计

算法采用两种交叉策略进行交叉操作.在染色体的第一段采用单点交叉策略；在染色体的第二至四段采用算术交叉策略.具体的线性组合为

子代1号=λ×父代1号+(1-λ)×父代2号

(22)

子代2号=λ×父代2号+(1-λ)×父代1号

(23)

式中λ为0到1的随机数.在交叉操作后，为了保证子代可行性，对子代基因值进行四舍五入.

3.5 变异操作的设计

为了保持子代在迭代过程中的多样性需要对交叉操作之后的个体进行相应的变异操作.在染色体上的第一段基因与第二段基因变异操作式为

(24)

式中：λ为0到1的随机数；G为当前迭代代数；P为最大迭代代数；S为变异步长参数；Δ为变动范围.

4 案例分析

4.1 基础数据

以某集装箱码头为例，该集装箱码头的岸线长为1 700 m，共有22 台岸桥，120 辆集卡可供服务.所有岸桥的初始状态设定：从左到右依次均匀地分布在岸线上；集卡则是在船舶靠泊之前，提前到达岸线区域进行等待.算例随机选取连续的28 艘到港船舶的数据作为原始数据，进行集装箱码头连续泊位—岸桥—集卡调度研究.到港时刻以第一艘集装箱船舶到港时刻的0点为基准，所有船舶的原始数据见表1.通过分析处理原始数据，得到集装箱船舶的最大、最小岸桥数以及船舶的偏好靠泊位置.

表1 集装箱船舶原始数据表Table 1 The raw data Table of container ships

4.2 求 解

图2 个体适应度的波动图Fig.2 The volatility of the individual fitness

4.2.1 最优调度方案

经过遗传算法优化求解得到最优调度方案，如表2所示.

表2 泊位—岸桥—集卡的最优调度方案Table 2 The optimal scheduling scheme of berth-crane-trailer

4.2.2 泊位分配方案

通过算法得到岸桥的泊位分配方案，如图3所示.由图3可见：每艘船舶相互之间在港时间和靠泊位置上不存在交叉，证明方案的可行性.

图3 泊位分配方案Fig.3 The scheme of berth allocation

4.2.3 岸桥作业甘特图

图4表示每一个岸桥在这段时间内为每一艘集装箱船舶服务的开始作业时刻和作业完成时刻.图4中：方框中的编号为集装箱船舶的编号；方框的右侧正对的横坐标为该集装箱船舶结束装卸任务的时刻；方框中间正对的纵坐标表示相应岸桥的编号.

由图4可知：这个计划期内总的被使用的岸桥数只有19 台，而编号为20，21，22的这几台岸桥一直是处于闲置状态.对于集装箱港口码头来说，岸边的装卸设备的购置费用、维修费用巨大，若是能够通过模型事先确定集装箱码头的岸桥设备的所需数目，在一定程度上可以为集装箱码头节省大量的资金.

4.2.4 集卡作业甘特图

装箱码头的集卡数目达到了120 辆，因此选取其中的前20 辆(即编号1～20的集卡)和后24辆(即编号97～120的集卡)为例进行表示，其中表示方法与岸桥甘特图相同，如图5所示.

图4 岸桥的作业甘特图Fig.4 Gantt chart about cranes

图5 集卡的作业甘特图Fig.5 Gantt chart about trailers

从集卡的作业甘特图中可以发现：109～120这一段编号的集卡处于闲置状态，因此就目前计划期的装卸需求而言，并不需要配置120 辆的集卡，不仅浪费了集装箱码头的空间资源，也是码头资金的一种浪费.因此若是集装箱码头采用该模型，则可以为码头的设备资源购置提供相应决策资料.

5 结 论

在数值实例中，结合所建立数学模型和设计的遗传算法，对其进行求解得到了最优的调度方案，包括集装箱船舶的泊位分配、岸桥分配以及集卡的指派情况，并绘制了岸桥和集卡的作业甘特图.结果证明：所设计的调度模型不仅能为集装箱码头提供泊位分配、岸桥分配以及集卡指派决策方案，减少集装箱的总在港时间成本，生产成本和船舶延期所带来的惩罚成本的总体费用，也可以为码头相关设备的购置提供相应的决策支持.

[1] 蒋美仙,张晓,冯定忠,等.基于Poisson过程的港口码头集卡预约调度优化[J].浙江工业大学学报，2016，44(3):292-299.

[2] KIM K H, MOON K C. Berth scheduling by simulated annealing[J]. Transportation research part B: methodological,

2003, 37(2): 541-560.

[3] IMAI A,SUN X, NISHMURA E. Berth allocation in a container port: using a continuous location space approach[J]. Transportation research part B: methodological, 2005, 39(3): 199-221.

[4] 禹美凤.基于柔性靠泊的集装箱港口泊位和岸桥的调度优化[D].杭州：浙江工业大学,2013.

[5] ZHU Y,LIM A. Crane scheduling with non-crossing constraint[J]. Journal of the operational research society, 2006, 57(12): 1464-1471.

[6] NISHIMURA E, IMAI A. Berth allocation planning in the public berth system by genetic algorithms[J]. European journal of operational research, 2001, 131(2): 282-292.

[7] NG W C, MAK K L, ZHANG Y X. Scheduling trucks in container terminals using a genetic algorithm[J]. Engineering optimization, 2007, 39(1): 33-47.

[8] 李娜,靳志宏.连续泊位调度与岸桥配置协同优化[J].中国航海,2011,34(2):86-90.

[9] 刘慧莲.不确定性条件下的集装箱码头泊位分配与岸桥调度问题的研究[D].呼和浩特：内蒙古大学,2016.

[10] 刘桂云,陈珊珊,张小莉,等.基于惩罚函数的集装箱码头连续泊位-岸桥联合调度[J].中国航海,2016(1):115-119.

[11] 王卫红,李文琼.基于改进遗传算法的高中走班制排课算法[J].浙江工业大学学报，2016，44(6):601-607.

[12] 陈勇,章金红,鲁建厦.基于GA-TS混合算法的多装配线调度建模[J].浙江工业大学学报，2013，41(4):355-358.