集装箱码头集卡动态调度模型优化

徐远琴，韩晓龙

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

集卡是连接船舶和堆场的水平运输工具，在港口运作中起着至关重要的作用。随着我国港口货物吞吐量的迅速增加，如何提高集装箱码头作业效率、减少集卡作业时间已经成为港口面临的重要问题。集卡动态调度可以减少其运作时间，提高码头作业的效率。

目前国内外许多专家学者对集卡动态调度问题进行了研究。徐承军等［1］分析了传统集卡调度模式的不足，提出了一种新的面向作业面的动态集卡调度模式，并且运用多目标模糊决策算法和层次分析法对单集卡多作业路径问题进行了研究。曾庆成等［2］针对集卡调度问题建立了集卡等待时间最小的调度动态模型，设计了Q 学习算法来求解模型。葛盼盼等［3］分析了集装箱码头作业流程及其传统作业工艺，建立了以集卡到达目的地距离最短为目标的优化模型，并使用蚁群算法求解。王军等［4］对不同船舶装船作业和卸船作业同时进行的前提下集装箱码头集卡作业路径选择问题进行了分析，建立了基于时间最短的集卡调度模型，并进行了数值仿真。康志敏等［5］通过对两种调度模式的比较，总结了现代集卡调度系统的优点，并提出了集装箱码头物流系统有色Petri 网建模的基本构架和一种新的遗传算法调度编码方式。乐美龙［6］等同时考虑龙门吊与集卡的协同调度，首次对实际作业中存在的一些约束，如多台龙门吊在同一箱区作业时由于共享一个双向轨道而存在的龙门吊不能相互跨越的约束等，建立了以集卡与龙门吊联合调度完工时间最短为目标函数的优化模型。CAO 等［7］研究分析了集卡调度与配置问题，并由此建立了集卡等待时间最短的整数规划模型，分别使用遗传算法和启发式算法求解优化模型，最后得出启发式算法更适合求解所建模型的结论。CAO 等［8］建立的集卡与场桥集成调度混合整数规划模型，以集卡与场桥同步化完工时间最小为目标函数，分别用Cplex 及传统的Benders 分支法和新组合的Benders 分支法求解模型，比较各自优劣。

笔者主要研究集卡的动态调度问题，首先对该问题进行了描述，建立了集卡动态调度模型，求出集卡的最小运作时间，最后验证了模型的有效性。笔者的创新之处在对模型约束进行创新的基础上，考虑了特定集装箱卸载到特定的箱区和从船舶到箱区运行路径上的集卡数量限制等现实约束，使得模型更具有现实意义。

1 问题描述

集卡是连通船舶和堆场的枢纽，如果集卡的运输能够快速有效地组织，将会极大提高码头的装卸作业效率。集卡作业过程如下:船舶到达泊位，通过装卸桥卸箱到集卡，集卡运箱到堆场，然后返回泊位或者到下一个堆场取箱返回泊位，此过程构成一个集卡行走路径。如何使得集卡行走时间最短就是集卡调度优化问题。

动态调度方式是指集卡并不固定地服务于一台装卸桥，而是按照整体优化调度的结果来完成集装箱的装卸任务。动态调度模型基于以下假设:

(1)集卡能够及时服务于装卸桥、龙门吊且不出现交通拥堵情况，这一状态即为理想状态，在这种状态下，需限定船舶贝位u 与箱区e 间最多能同时运行的集卡数，以减少和避免交通拥堵。同时，为了堆场内各箱区堆箱分派均匀合理，需限定贝位u 与箱区e 作业路线上最多作业次数。

(2)集卡每次可以装载一个集装箱。

(3)集卡独立运行，不相互干扰。

2 模型建立

2.1 符号

为了便于建模，引入以下符号:

(1)集合。U 为船舶待卸贝位集合，u∈U;V为船舶待装贝位集合，v∈V;E 为堆场箱区集合，e∈E;O 为船舶集合，o∈O。

(2)参数。Ou为船舶待卸贝位要卸载的集装箱数，u∈U;Cv为船舶待装贝位的容量，v∈V;Pe为箱区要被装船的箱量，e∈E;Ce为箱区的容量，e∈E;Ωue为船舶待卸贝位上的集装箱必须卸到指定箱区的数量，u∈U，e∈E;Rev为出口集装箱必须卸到指定贝位的数量，e∈E，v∈V;Mue为从船舶贝位u 到箱区e 最多同时运输的集卡数，u∈U，e∈E;Nue为从贝位u 到箱区e 作业路线上最多作业次数，u∈U，e∈E;Mev为从箱区e 到贝位v 最多同时运输的集卡数，e∈E，v∈V;Nev为从箱区e 到贝位v 作业路线上最多作业次数，e∈E，v∈V;tue为集卡从贝位u 装箱运输到箱区e 的运输时间，u∈U，e∈E;tev为集卡从箱区e 装箱运输到贝位v 的运输时间，e∈E，v∈V;tef为集卡在箱区间的空载运输时间，e、f∈E 且e≠f;toe为集卡船舶o 与箱区e 之间空载运输时间，e∈E，o∈O。

(3)决策变量定义。xue为集卡从待卸船贝位u 装箱重载运输到箱区e 的次数，u∈U，e∈E;yev为集卡从箱区e 重载回到待装船贝位v 的次数，e∈E，v∈V;zef为集卡从箱区e 运输到箱区f 的次数，e、f∈E 且e≠f;xoe为集卡从船舶o 空载至箱区e 进行装船任务的次数，e∈E，o∈O;yeo为集卡从箱区e 空箱返回至船舶o 的次数，e∈E，o∈O。

2.2 集卡动态调度模型

基于集卡调度优化的考虑，建立以集卡运输时间最小为目标的集卡调度模型。

上式中，式(1)代表集卡的运输时间最小;约束条件式(2)表示集卡从贝位装箱然后运输到各个箱区的次数和等于该贝位的卸箱量;式(3)表示集卡从各个贝位装箱然后运输到箱区的次数和不能超过该箱区的容量;式(4)表示集卡从箱区装箱然后运输到待装船各个贝位的次数和等于该箱区的装箱量;式(5)表示集卡从箱区装箱然后运输到待装船各个贝位的次数和不能超过该贝位的容量;式(6)表示集卡在船舶与箱区之间运行的次数关系;式(7)表示集卡在船舶与箱区之间空载运输次数可同时为0 或有且仅有一个为0;式(8)、式(9)表示特定的集装箱必须卸到特定的箱区，特定的集装箱必须装往特定的贝位;式(10)、式(11)为作业任务次数约束。

3 数值试验

在某一时间段内集装箱码头有110 个进口集装箱需要进行卸船作业，100 个出口集装箱需要进行装船作业［9］，有4 个箱区可供其堆存。Ω31=34，表示从待卸船舶贝位3 上必须卸载34 个集装箱到箱区1。集卡每次只能运送一个集装箱且其作业开始时均位于岸边。具体数据如表1 ～表12 所示。

表1 待卸船舶各贝位的卸箱量国际标准箱

表2 待装船舶各贝位的容量 国际标准箱

表3 各个箱区容量 国际标准箱

表4 各个箱区装箱量 国际标准箱

表5 从各个贝位到各个箱区的运输时间 min

表6 从各个箱区到各个贝位的运输时间 min

表7 从箱区e 到箱区f 集卡的运输时间 min

表8 船舶与箱区间的运输时间 min

表9 从各个贝位到箱区的Mue 个

表10 从各个贝位到箱区的Nue 次

表11 从各个箱区到贝位的Mev 个

表12 从各个箱区到贝位的Nev 次

把以上数据代入所建模型中，利用遗传算法思想及Lingo 求解工具［10］，可求出最小运输时间及集卡行走优化路线，如表13 所示。

表13 优化路线

数据结果表明，所提出的模型能够为集卡运输提供最优线路，节省集卡运输时间。

4 结论

集卡调度优化直接影响集装箱码头的作业效率。笔者据此建立了集卡动态调度优化模型，对特定集装箱卸载到特定箱区的问题，从船舶到箱区运行路径上的集卡数量有限等现实约束方面考虑，并首次将集卡任务次数的限制加以研究。建立了以集卡运输时间最短为目标的动态调度优化模型，利用遗传算法求得了最优解，算例结果表明了该模型的有效性和实用性。

［1］ 徐承军，陶德馨. 基于多目标模糊决策的集卡动态调度方法研究［J］.武汉理工大学学报:信息与管理工程版，2007，29(4):57－59.

［2］ 曾庆成，杨忠振.集装箱码头集卡调度模型与Q 学习算法［J］.哈尔滨工程大学学报，2008，29(1):1－4.

［3］ 葛盼盼，王继荣，李军，等.基于蚁群算法的码头集装箱卡车路径优化研究［J］. 物流科技，2008(12):26－28.

［4］ 王军，许晓雷. 集装箱码头集卡作业的路径选择［J］.大连海事大学学报，2011，37(2):25－34.

［5］ 康志敏，吴洪明. 港口集装箱码头集卡优化调度研究［J］.物流工程与管理，2011，33(2):59－61.

［6］ 乐美龙，包节，范志强.龙门吊与集卡协调调度问题研究［J］.计算机工程与应用，2012，48(14):241－248.

［7］ CAO J X，SHI Q X，LEE D H. A decision support method for truck scheduling and storage allocation problem at container［J］. Tsinghua Science and Technology，2008，13(10):211－216.

［8］ CAO J X，LEE D H，CHEN J H，et al. The integrated yard truck and yard crane scheduling problem:benders' decomposition－based methods ［J］. Transportation Research Part E，2010(46):344－353.

［9］ 郭燕，赵谨. 基于概率统计的集装箱龙门起重机生产率研究［J］.武汉理工大学学报:信息与管理工程版，2009，31(1):161－164.

［10］王里付，朱新平.基于Petri 网和遗传算法的飞行训练计划优化编排［J］.武汉理工大学学报:信息与管理工程版，2012，34(2):197－201.