集装箱码头岸桥与集卡集成调度问题研究

余孟齐，韩晓龙

(上海海事大学物流研究中心， 上海201306)



集装箱码头岸桥与集卡集成调度问题研究

余孟齐，韩晓龙

(上海海事大学物流研究中心， 上海201306)

摘要：岸桥与集卡是集装箱码头的重要资源。为了提高码头的装卸效率，针对集装箱码头岸桥和集卡的集成调度问题，以完工时间最小为优化目标，考虑集装箱之间优先关系和岸桥安全边际的实际约束，建立混合整数线性规划模型，利用改进粒子群算法(IPSO)对模型进行求解, 制定了粒子编码和解码规则，设计了一种新的速度更新策略来改进解的质量。实验表明，将改进算法的结果与优化软件CPLEX所求得的最优解比较，IPSO算法求得12组数值算例的平均偏差为 0.582%，且CPLEX计算时间的跨度随着计算规模的扩大从2.92 s到1 h，而IPSO的求解时间控制在50 s之内，并得到最优解，证明了该模型和算法可以快速有效地解决岸桥与集卡的集成调度问题。

关键词：岸桥;集卡;集成调度;粒子群算法

0引言

由于集装箱运输量的增加，集装箱码头已经成为海陆运输间的重要接口。在这个竞争日益激烈的行业，码头必须提高各种资源的运作效率。图1显示了集装箱码头的典型布局。如图1所示，码头中存在三个主要的集装箱处理设备：岸桥，集卡和场桥。岸桥负责从船上卸载集装箱和将集装箱装载到船上，场桥负责堆叠进口箱和从堆场检索出口箱，集卡负责在岸桥和堆场之间运输集装箱。这三种设备作业紧密相连，需要良好的协调来避免由于互相等待造成的效率损失。

图1集装箱码头典型布局

Fig.1Typical layout of a container terminal

国内外学者对集装箱码头装卸设备调度已有一定研究。对于岸桥调度问题，Kim等[1]为船舶贝位中的多任务岸桥调度问题建立了一个混合整数规划模型，并设计启发式搜算法来解决问题。Lee等[2]考虑岸桥间的干扰，通过遗传算法为船上任务找到了一组岸桥分配序列。董良才等[3]采用遗传算法求解带时间窗的岸桥调度混合整数规划模型。靳志宏等[4]为码头岸桥调度问题构建非线性整数规划模型，并设计基于任务排序的遗传算法对模型进行求解。

对于集卡调度问题，尚晶等[5]提出具有集卡实时调度规则的动态仿真模型，并利用WITNESS仿真软件进行仿真实验分析。Bish[6]通过启发式算法求解集卡动态调度模型，其目标是为了最小化船舶周转的时间。Nishimura等[7]提出集卡动态路径的调度方法，并采用遗传算法进行求解。康志敏等[8]通过集装箱码头物流系统有色 Petri 网建模的基本构架来求解集卡调度问题。

近年来，学者们已经对岸桥和集卡的集成调度问题进行研究。Chen等[9]将岸桥、集卡和场桥的集成调度问题制定为约束规划模型并提出三阶段算法来求解模型。Lau等[10]对相同问题进行深入研究，其目标函数是最小化场桥行走的时间、集卡运输的时间与岸桥空闲的时间。Kaveshgar等[11]为卸载入境集装箱的岸桥与集卡集成调度问题制定了混合整数规划模型，并使用遗传算法求解。张笑等[12]提出基于岸桥作业和集卡运输总时间最小的岸桥与集卡协作优化模型，并通过Gurobi实现集卡路径优化。马超等[13]等在同时考虑进出口集装箱的情况下，采用多层遗传算法求解岸桥和集卡的协同调度问题。秦天保等[14]提出带任务顺序约束的岸桥集卡集成调度约束规划模型，并设计新的下界求法评价解的质量。邢曦文等[15]建立了基于三阶段混合流水作业的码头装卸作业集成调度优化模型，采用两阶段启发式算法求解。

但目前已有研究大都是针对岸桥与集卡单向作业集成调度，对于双向作业集成调度研究较少。本文在考虑集装箱之间的优先关系以及岸桥安全边际的实际约束的基础上，研究岸桥与集卡双向作业集成调度问题，提出基于改进粒子群算法(IPSO)求解调度优化模型，并通过数值实验对算法可行性和实用进行了分析。

1问题描述

在传统码头作业中，岸桥通常被安排来处理到达的船舶，然后集卡被分配来服务特定的岸桥。在这种方法中，每台岸桥与一组固定的集卡合作。岸桥和集卡可能经常互相等待。以卸载过程为例，如果一个集装箱被岸桥卸载，但是没有集卡到达，岸桥必须保留集装箱并等待集卡到达。反之，如果当集卡到达时岸桥没有完成集装箱的卸载，集卡必须等待。这样就会降低集卡的利用率。如图2所示，两条船停泊在码头。岸桥1和岸桥2分别分配给船舶1和船舶2。集卡1和集卡2都分配给岸桥1用于运输集装箱到堆场；集卡3被分配给岸桥2。当没有可用的集卡运送由岸桥2卸载的集装箱时，岸桥2必须持有集装箱并等待集卡。与此同时，被分配到岸桥1的集卡1和集卡2都必须排队等待来运输由岸桥1卸载的集装箱。为了避免这样的情况，在本文中，我们通过岸桥和集卡的集成调度，以减少船舶的周转时间，如图3所示，集卡1转为服务于岸桥2。因此，岸桥2不需要等待，从而提集装箱码头的总生产率。

图2岸桥与集卡单独调度

Fig.2Schedule quay cranes and yard trucks separately

图3岸桥与集卡集成调度

Fig.3Schedule quay cranes and yard trucks jointly

我们问题的决策包括岸桥和集卡的分配以及分配给岸桥和集卡的装卸作业的顺序。

2模型的建立

环境假设：①集装箱之间存在优先关系。②不考虑岸桥间的相互干扰。③场桥有足够的装卸能力，集卡不需要在堆场等待。④每个集装箱在船上和堆场中的位置都是已知的。⑤岸桥和集卡每次只能处理一个集装箱。

目标函数：

(1)

约束条件：

(2)

(3)

(4)

(5)

Fh≥Ci1i∈Ah,h∈B,

(6)

Fh-Sh′+Yhh′M≥0h,h′∈B,

(7)

Fh-Sh′-(1-Yhh′)M≤0h,h′∈B,

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

(25)

(26)

(27)

(28)

(29)

(30)

(31)

3基于粒子群算法的岸桥-集卡集成调度问题求解

粒子群算法(PSO)是一种基于种群的优化算法，在每次迭代中，每个粒子代表具有位置和速度的解。位置反映解的质量，速度决定在下一次迭代中粒子的移动位置。速度和位置的普通更新公式如下：

(32)

(33)

3.1解的表示

本文的调度问题必须决定岸桥和集卡的分配以及集装箱被岸桥和集卡装卸的顺序。因为这个问题有由岸桥卸载作业和集卡运输作业两个阶段，对每台岸桥的分配和集装箱顺序编码，然后根据岸桥的调度顺序将集卡分配给集装箱。

表1　粒子编码

表2　粒子解码

3.2速度更新策略

粒子群算法一个主要优点是它收敛速度很快，但这容易导致其陷入局部最优解。这是因为每个粒子总是倾向于朝着它曾经达到的最优位置和迄今为止整个粒子群全局最优位置飞行。在本文的算法中，适应值等于目标值。为了克服陷入局部最优的缺点，当一个粒子适应值不大于粒子群中所有粒子的平均适应值时，我们提出修改的速度更新公式如下：

(34)

3.3粒子群优化算法步骤

解决多个岸桥和集卡调度问题的粒子群算法执行步骤如图4所示。

图4　粒子群算法步骤

4数值实验与结果分析

为了评估IPSO算法的性能，我们随机生成3种类型的问题——6个小规模问题、3个中等规模问题以及3个大规模问题。将提出的IPSO算法的结果与使用优化软件(CPLEX)求解混合整数线性规划模型得到的最优解相比较。

4.1试验设计

问题的实验数据产生如下：

①作业时间(以s为单位)从下面的均匀分布中生成：岸桥作业U(105，161)；集卡移动U(60,130)。

②进口(出口)箱的原始(目标位置)考虑船舶布局随机生成，进口(出口)箱的目标(原始)位置基于集装箱码头的实际布局产生。

考虑算法参数设置的不同同样会影响算法性能，所以选择试算后各算法的最优参数进行运算。IPSO算法中，对于所有数值实验，最大迭代次数gen=500，种群规模pop_size=30，c1=c2=2，c3=1。

所有实验都是在4 GB内存和2.80 GHz处理器的计算机上进行的。该算法是用Matlab编写，并且所述模型使用CPLEX解决。

4.2试验结果分析与评价

为测试IPSO算法的性能，本文设计12组算例(如表3所示)，其中目标值显示是 CPLEX 和IPSO算法的计算结果。设置CPLEX 最大运行时间为60 min，即如果运算60 min 也无法取得最优解，就停止运算。

表3中的数据是基于Kaveshgar等[11]论文第五部分数值实验和讨论中的数据，包括岸桥数量、集卡数量以及集装箱数量来设计的算例规模。

从表3中可以看出，IPSO算法对于三种规模问题可以得到令人满意的解，算法求解12个算例的平均偏差为0.582%。对于中小规模问题，CPLEX求得的解优于IPSO算法，如算例1到算例9，CPLEX都获得了最优解。但对于大规模问题，由IPSO算法得到的3个解中有2个比CPLEX好。IPSO算法在计算时间方面明显优于CPLEX。对于小规模问题，CPLEX的平均计算时间大约是1.65 min，而IPSO平均仅用0.27 s。然而CPLEX求解模型优化的计算时间随着问题规模增大迅速增加，例如算例7到算例10，CPLEX计算时间跨度从213.2 s 到接近1 h，而IPSO算法求解时间的跨度是从3.43 s到8.50 s；算例11与算例12，CPLEX已无法在1 h内求出解，而IPSO算法分别只需要24.76 s和41.57 s。这表明IPSO算法对岸桥和集卡集成调度问题是有效的。

表3　CPLEX与改进的粒子群算法(IPSO)对比结果

1.相对偏差=(IPSO的目标值-CPLEX的目标值)/CPLEX的目标值×100%。

下面以算例6为例，解释运用IPSO算法得到的最优装卸计划，如表4所示。表4中的数据是通过MATLAB软件计算算例6得到的。表4借鉴马超等[13]论文第四部分图表而设计的。

算例6的问题有2台岸桥，4辆集卡，16个集装箱。总完工时间为1 240 s。其中，U代表卸载计划，L代表装载，数字为集装箱编号。以岸桥1为例，U1代表卸载集装箱1，L15代表装载集装箱15，以此类推。

表4　算例6中的岸桥和集卡的装卸计划

4.3讨论

通过对12个算例实验的分析，可以看出提出的IPSO算法在得到问题解的质量和计算时间上都优于软件CPLEX，这表明IPSO算法对岸桥和集卡集成调度问题是有效的。

本文在考虑我国集装箱码头现实情况下的作业约束，如集装箱之间的优先关系以及岸桥安全边际的实际约束的基础上，研究岸桥与集卡双向作业集成调度问题，集卡可以运输两个方向的集装箱，减少空驶，使岸桥一集卡调度更加系统化、合理化，对提高我国集装箱码头作业效率具有实际意义。

5结论

本文考虑集装箱之间存在优先关系时岸桥和集卡集成调度问题的完工时间最小化，并提出了基于IPSO算法求解的混合整数线性规划模型，旨在提高集装箱码头运作效率。实验表明，将改进算法的结果与CPLEX软件所求得的最优解比较，IPSO算法求得12组数值算例的平均偏差为 0.582%，且随着问题规模的不断扩大，CPLEX计算时间的跨度从2.92 s到1 h，已经无法在有效时间内求出解；而IPSO的求解时间控制在50 s之内，能够很好的在有限时间内找到最优解，证明了其有效性。将本文提出的模型和其求解算法应用到港口实际调度中，能够有效提高码头资源的利用率，具有一定使用价值。接下来的研究可以考虑将场桥加入集成调度，开发集成范围更大的调度模型。

参考文献:

[1]KIM K H, PARK Y M.A crane scheduling method for port container terminals [J]. European Journal of Operational Research, 2004, 156: 752-768.

[2]LEE D H, WANG H Q, MIAO L X.Quay crane scheduling with non-interference constraints in port container terminals [J]. Transportation Research Part E, 2008, 44(1): 124-135.

[3]董良才, 丁以中, 宓为建.基于时间窗的集装箱装卸桥调度[J]. 上海海事大学学报, 2011, 32(1): 1-7.

[4]靳志宏,李娜.基于泊位计划的集装箱码头岸桥动态调度优化[J]. 交通运输系统工程与信息, 2011, 11(3):58-64.

[5]尚晶,陶德馨.集装箱码头集卡调度策略的仿真研究[J]. 武汉理工大学学报: 交通科学与工程版, 2006, 30(5): 827-830.

[6]BISH E K.A multiple-crane-constrained scheduling problem in a container terminal [J]. European Journal of Operational Research, 2003, 144: 83-107.

[7]NISHIMURA E, IMAI A, PAPADIMITRIOU S.Yard trailer routing at a maritime container terminal [J]. Transportation Research: Part E, 2005, 41(1): 53-76.

[8]康志敏, 吴洪明.港口集装箱码头集卡优化调度研究[J]. 物流工程与管理, 2011, 33(2): 59-61.

[9]CHEN L, LANGEVIN A, LU Z Q.Integrated scheduling of crane handling and truck transportation in a maritime container terminal [J]. European Journal of Operational Research, 2013, 225: 142-152.

[10]LAU H Y K，ZHAO Y.Integrated scheduling of handling equipment at automated container terminals[J]. International Journal of Production Economics, 2008, 12(2): 665-682.

[11]KAVESHGAR N, HUYNH N.Integrated quay crane and yard truck scheduling for unloading inbound containers [J]. International Journal of Production Economics, 2015, 159: 168-177.

[12]张笑, 韩晓龙.集装箱码头岸桥与集卡装卸协作优化[J]. 水运工程, 2013(3): 124-128.

[13]马超, 梁承姬.集装箱码头岸桥分配与集卡调度整合问题研究[J]. 广西大学学报(自然科学版), 2015, 40(3): 643-650.

[14]秦天保，彭嘉瑶，沙梅.带任务顺序约束的岸桥集卡集成调度约束规划模型[J]. 上海海事大学学报, 2013,34(3): 1-7.

[15]邢曦文, 毛钧, 靳志宏, 等.基于混合流水作业组织的集装箱码头装卸作业集成调度优化[J]. 中国管理科学, 2014, 22(10): 97-105.

(责任编辑梁健)

收稿日期：2016-03-01；

修订日期：2016-05-25

基金项目：国家自然科学基金资助项目(7130110)；上海市科委工程中心能力提升项目(14DZ2280200)

通讯作者：韩晓龙(1980—)，男，上海市人，上海海事大学副教授，博士;E-mail:superhxl@163.com。

doi:10.13624/j.cnki.issn.1001-7445.2016.0745

中图分类号：U169.6; U691.3

文献标识码：A

文章编号：1001-7445(2016)03-0745-09

Integrated scheduling of quay crane and yard truck in container terminals

YU Meng-qi, HAN Xiao-long

(Logistics Research Center, Shanghai Maritime University, Shanghai 201306, China)

Abstract:Quay crane and yard truck are the important resources in container terminals. To improve the handing efficiency of the container terminal, the integrated quay-crane and yard truck scheduling problem is solved by formulating a mixed integer linear programming model to minimize the makespan with real-word operational constraints such as precedence relationships between containers and quay crane safety margin. The improved particle swarm optimization (IPSO) algorithm is used to solve the new model, and a new velocity updating strategy is devised to improve the solution quality via formulating the rules of particles encoding and decoding. The results of the IPSO are compared with the optimal solutions obtained by CPLEX software. The experiment demonstrates that the average gap of 12 cases of IPSO is less 0.582%. Along with the increase of the scale，the time span of the CPLEX solutions differs from 2.92 seconds to 1 hour，but the solving time of IPSO algorithm is controlled in 50 seconds to solve the problem and to obtain optimal solution. Numerical experiments result shows that the proposed model and the improved algorithm can effectively solve such problem.

Key words:quay crane; yard truck; integrated scheduling; particle swarm optimization algorithm

引文格式：余孟齐，韩晓龙.集装箱码头岸桥与集卡集成调度问题研究[J].广西大学学报(自然科学版)，2016，41(3)：745-753.