集装箱码头的集卡两阶段路径优化研究

赵金楼，黄金虎，刘 馨

(1.哈尔滨工程大学经济管理学院，黑龙江 哈尔滨 150001；2.工业和信息化部电子第五研究所，广东 广州 510610)



集装箱码头的集卡两阶段路径优化研究

赵金楼1，黄金虎1，刘 馨2

(1.哈尔滨工程大学经济管理学院，黑龙江 哈尔滨 150001；2.工业和信息化部电子第五研究所，广东 广州 510610)

针对目前研究集卡路径问题的文章多数未考虑到空载对集卡运输效率的影响，且多在忽略集卡数量的情况下对路径进行优化，本文考虑集卡数量和空载距离构建了集装箱码头的集卡两阶段路径优化模型。其中，以集卡行使距离最小为目标构建了第一阶段集卡路径优化模型，解决了不考虑集卡数量时的初步路径规划及每条路径的运输量问题。基于第一阶段结果，引入集卡数量，以集卡任务间空载距离最小为目标构建了第二阶段集卡路径优化模型，通过粒子群算法解决了每辆集卡的路径任务分配及作业顺序的问题。算例结果表明，进行第二阶段优化后的集卡空载距离和空载率得到降低。

集装箱码头；集卡；两阶段路径优化；粒子群算法

1 引言

2016年上半年，全国港口货物吞吐量和集装箱吞吐量同比分别增长2.2%和2.5%。随着集装箱运输业务的不断发展，集装箱码头作为集装箱货物的中转站和装卸重要场所，其效率和管理水平越来越受到关注。集卡(集装箱卡车)是实现码头作业效率的主要水平机械，其调度水平的高低，直接影响码头运营效率[1]，而集卡路径问题是集卡调度的核心和重要环节。

对于集装箱码头的集卡路径问题，国外学者多关注于码头自动导向车(AGV)和模型求解算法。Grunow等[2]研究了在自动化程度较高的集装箱港口中多个AGV的运行路径问题。Bish[3]提出了AGV的动态调度模型以减少船舶在港时间，并采用启发式算法进行求解。Nishimura[4]通过对比集卡静态调度与动态调度，构建了集卡动态路径优化模型，并采用遗传算法进行模型求解。Amini和Moghaddam[5]在集装箱交叉堆放的情况下，面对集卡运输过程中存在拥堵等待的问题构建了多目标线性规划模型，并结合三种启发式算法进行求解。Cordeau等[6]以集卡运输和等待时间之和最小为目标，构建了集卡路径优化模型，采用局部搜索算法和仿真手段对不同时刻下的集卡运行情况进行了模拟。Kozan等[7]运用启发式算法研究集装箱码头集卡运输问题，讨论了影响集装箱码头作业效率的因素。Berghman等[8]将码头集卡作业划分为三个阶段，以时间最短为目标，参考柔性流水车间问题构建了调度模型，并引入枚举搜索树设计了拉格朗日启发式算法来求解。国内对于集卡路径优化的研究起步较晚，着重于优化模型的构建和求解。杨静蕾[9]以集卡行驶距离最小为目标提出了集装箱码头物流路径优化模型，在不考虑集卡数量以及满足集装箱堆存要求情况下获得集卡最优路径。吕品和乐美龙[10]在作业面模式下，面向两船构建了以路径最短为目标的集卡路径优化模型，并采用遗传算法来求解。魏宏磊和朱瑾[11]基于“作业面”优先策略，建立了集卡路径优化模型，用Lingo软件得到了最短路径。计明军和靳志宏[12]在单船同时装卸情况下，考虑集卡和岸桥作业时间，以时间最小为优化目标，构建了集卡线路优化模型，并利用改进的进化规划来求解。曹庆奎[13]建立了面向“作业面”的港口集卡路径成本优化模型，并设计了遗传蚁群算法并结合实例对问题求解。曾庆成[14,15]在已知装卸桥作业序列的情况下，研究了卸船的集卡调度问题，应用Q学习算法来求解，并对码头外部的集卡预约进行了优化。邢曦文和毛钧等[16]借鉴多阶段混合流水线调度问题，将卸载过程划分为三阶段，对岸桥、集卡、场桥同时进行调度优化。杨忠振和程健南[17]在出口箱随机到达码头的背景下，基于车船直取的内外集卡联合装船模式，构建了装船序列优化模型，并采用遗传算法来求解。

目前对集卡路径问题的研究虽然较多，但国外研究多集中于AGV自动导向车，而我国目前多数码头自动化水平尚未达到该标准。国内学者在研究集装箱码头的集卡路径优化时体现出两点不足：一是多数模型并未考虑集卡数量，仅做出了初步的路径规划，没有将路径优化执行方案落实到具体集卡。二是在优化目标方面，目前的研究多以最小化集卡行驶距离或时间为目标函数，少有文章考虑空载对于集卡运输效率的影响。实际上，空载距离和空载率的降低有利于减少集卡油耗和提高集卡运输效率。

针对上述两点，本文在前人研究的基础上，考虑了集卡数量和空载距离，构建了集卡两阶段路径优化模型，通过第二阶段模型的建立丰富了现有的集卡路径优化研究。首先，本文不考虑集卡数量，以集卡行驶距离最小为优化目标，构建了第一阶段集卡路径优化模型，来解决初步的集卡运输路径问题。然后，基于第一阶段的路径优化结果，引入集卡数量，将每条路径的一次运输过程视为一项任务，以集卡任务间空载距离最小为目标，构建了第二阶段集卡路径优化模型，通过粒子群算法对模型进行求解，对集卡进行路径任务分配以及执行顺序的安排。最后，通过算例对模型进行数值计算。

2 问题描述

本文基于作业面模式来进行集卡路径优化，较多文献指出该模式能够有效提高集卡运输效率，是目前较为常见的作业方式[9-11]。该模式下集卡作业过程如图1所示，作业路径如图2所示。在图1中，待卸船舶和待装船舶分别停靠于泊位1和泊位2。进口集装箱从待卸船舶被卸到集卡上，由集卡运输至进口箱区进行卸载，然后集卡运行至出口箱区，装载相应出口集装箱运输至待装船舶。码头堆场内存在若干进出口箱区，各个箱区之间以及箱区与泊位之间形成了若干条可行路径，集卡路径优化即在这些路径中选择最佳路径，以达到既定目标的要求。图2反映了一次装卸作业时的集卡路径，即：泊位1进口箱区出口箱区泊位2。假设每辆集卡每次只能运送1个40英尺集装箱(FEU)。要解决集卡的路径优化问题，即解决在每一次运输过程中要经过哪些进出口箱区的问题。而集卡每次只能运送一个集装箱，故沿某路径的运行次数也就反映了运输的集装箱数量。

考虑到装卸不平衡情况下，待卸集装箱数量与待装集装箱数量不一定相等，除了图2反映的装卸作业路径外，可能存在泊位与箱区之间的单独装载或卸载路径。如果待卸进口箱数量大于待装出口箱数量，则集卡还需要在待卸船舶与进口箱区之间往返运输进口箱。反之需要在待装船舶与出口箱区之间往返运输出口箱。

图1 作业面模式下的码头集卡作业过程

图2 一次装卸作业路径

本文对集卡的路径优化分两个阶段展开，第一阶段在不考虑集卡数量的情况下对集卡运输路径进行初步规划，即集卡在每一次运输过程中要经过哪些进出口箱区。在第一阶段基础上，第二阶段在已知集卡数量的情况下，将初步得到的路径规划结果落实到每辆集卡，对各辆集卡进行路径任务的分配，并对相应路径任务的执行顺序进行安排。与此对应，本文建立了集卡两阶段路径优化模型来实现上述过程。

3 集卡两阶段路径优化模型

3.1 第一阶段集卡路径优化模型

3.1.1 参数与变量

(1)已知参数

H：待卸船舶集装箱数量；

h：待装船舶集装箱数量；

L：进口箱区的集合，共有l个箱区；用i表示进口箱区的序号，i=1,2,…,l；

B：出口箱区的集合，共有m个箱区；用j表示出口箱区的序号，j=1,2,…,m；

do,i：集卡在泊位1与进口箱区i之间的往返行驶距离；

do,j：集卡在泊位2与出口箱区j之间的往返行驶距离；

di,j：集卡沿路径“泊位1进口箱区i出口箱区j泊位2”的行驶距离；

Qi：第i个进口箱区的容量；

Ej：第j个出口箱区的已堆存集装箱数量；

(2)决策变量

Xi,j：集卡沿路径 “泊位1进口箱区i出口箱区j泊位2”的行驶次数；

Yo,i：集卡在泊位1与进口箱区i之间的往返行驶次数；

Zo,j：集卡在泊位2与出口箱区j之间的往返行驶次数；

3.1.2 第一阶段集卡路径优化的数学模型

假设集卡一次只能运输一个集装箱(FEU)。基于上述参数与决策变量，以集卡总行驶距离最小为目标，建立集卡路径优化的数学模型如下：

(1)

(2)

(3)

(4)

(5)

Xi,j≥0,i∈L,j∈B

(6)

Yo,i≥0,i∈L

(7)

Zo,j≥0,j∈B

(8)

其中，目标函数(1)表示集卡完成所有装卸任务的总行驶距离最短，式中第1项表示装卸协同作业下集卡沿路径“泊位1→进口箱区i出口箱区j泊位2”在两泊位之间的总行驶距离。第2项表示在泊位1与进口箱区之间往返的行驶距离，第3项表示在泊位2与出口箱区之间往返的行驶距离。式(2)保证所有待卸集装箱都能卸载完毕。式(3)保证所有待装集装箱都能装载完毕。式(4)保证运送到进口箱区的集装箱总数不超过该进口箱区的容量。式(5)保证出口箱区的已堆存集装箱都能装船。式(6)至式(8)表明了决策变量取值范围。

3.2 第二阶段集卡路径优化模型

3.2.1 参数与变量

(1)已知参数

根据上述集卡路径优化模型，可得到集卡的行驶路径以及每条路径的行驶次数，把它作为已知参数，以集卡沿一条路径的一次运输过程作为一项任务，具体参数如下：

I：任务集合，共有p项任务；用s/r表示任务的序号，s,r=1,2,…,p；

N：集装箱卡车的集合，共有n辆集卡；用k表示集卡的序号，k=1,2,…,n；

cs,r：任务s与r之间的空载距离，与路径“泊位1进口箱区i出口箱区j泊位2”对应的任务，空载距离为两泊位间的距离。对于单独装载或者卸载任务，空载距离即为泊位与箱区的距离；

(2)决策变量

3.2.2 第二阶段集卡路径优化的数学模型

基于上述参数与决策变量，以集卡任务间空载距离最小为目标，建立集卡路径任务分配的数学模型如下：

(9)

(10)

(11)

(12)

Ws,r,k∈{0,1},s∈I,r∈I,k∈N

(13)

Gk,s∈{0,1},s∈I,k∈N

(14)

Gk,r∈{0,1},r∈I,k∈N

(15)

其中，目标函数(9)表示所有集卡执行完任务的空载距离最短。式(10)表示每个任务有且仅有1辆集卡执行；式(11)、(12)给出了决策变量间的关系。式(13)至式(15)表明了决策变量的取值，是0-1变量。

4 模型求解

根据模型的特点，对于第一阶段集卡路径优化模型，将采用Lingo软件直接求解。对于第二阶段集卡路径优化模型，本文将使用带惯性权重的粒子群算法来进行求解。集卡路径问题属于车辆路径问题(Vehicle Routing Problem，简称VRP)的一种，Salman为VRP问题提出了一种较好的编码方法，第二阶段采用Salman的编码思想来进行算法设计[18]。算法实现过程如下[19]：

步骤1：初始化粒子群。

(1)基于编码将粒子群分成若干两两相互重叠的子群。具体设置两个位置向量Xv和Xr，分别表示执行每项任务的集卡以及该任务在集卡中的执行顺序。对应设置两个速度向量Vv和Vr。

(2)每个粒子位置向量Xv的每一维随机取1至n(车辆数)之间的整数，Xr的每一维随机取1至p(任务数)之间的实数。

(3)每个速度向量Vv的每一维取-(n-1)至(n-1)之间的整数，Vr的每一维取-(p-1)至(p-1)之间的实数。

(4)对于相同的Xv，将得到的Xr按从小到大的顺序分别赋予整数值，以代表作业顺序。

根据步骤(1)至(4)，编码操作过程见表1。表中第一行表示全部任务，第二行表示各任务对应的执行集卡，在该示意表格中任务1由集卡1执行，任务2、3、4、5由集卡2执行，任务6由集卡3执行。第三行的数字反映同一集卡的作业先后顺序，以集卡2为例，根据所执行任务对应的Xr大小顺序，分别给第二辆集卡的序列赋值3、4、1、2，表示任务2排在集卡2作业序列的第3位执行，任务3排在第4位，任务4排在第1位，任务5排在第2位。

表1 编码过程示意

(5)评价每个粒子适应度，即所有集卡的空载距离之和。

(6)将初始位置作为个体历史最优解，寻找各子群内的最优解Pl和总群体的最优解Pg。

步骤2：设置迭代终止条件。

步骤3：重复以下步骤，直到满足终止条件。

(1)对每一个粒子，按位置和速度公式进行更新，超过边界范围时按边界取值。

(2)用适应度函数(目标函数)评价所有粒子。

(3)若某个粒子的当前适应度优于历史最优适应度，则记当前适应度为历史最优适应度。同时记下此时的粒子位置为该粒子的历史最优位置。

(4)寻找当前各粒子群内的最优解和总群体最优解，若优于历史最优解则更新Pl和Pg。

5 算例

5.1 第一阶段集卡路径优化模型求解

码头堆场有5个进口箱区和5个出口箱区用于堆放集装箱。堆场箱区间的距离、箱区至泊位的距离、泊位之间的距离见表2，各进口箱容量见表3，出口箱堆放的待装集装箱数量见表4。待卸集装箱数量为500，待装集装箱数量为450。涉及到集装箱容量或数量均按40英尺集装箱(FEU)算，涉及到距离的均以米为单位。使用Lingo软件对第一阶段集卡路径优化模型进行求解，结果见表5，集卡行驶距离为2300000米。

表2 堆场箱区间的距离

表3 进口箱区容量

表4 出口箱区堆存量

表5 集卡运输路径及装卸箱量

5.2 第二阶段集卡路径优化模型求解

基于第一阶段路径优化模型的求解结果，将一条路径的一次运输过程作为一项任务，则共有500项任务，从路径1的任务开始依次编号。实际上，后450个任务具有相同的起点和终点，任务间空载距离相同，执行顺序并不影响目标函数值。故只要确定前50项任务的集卡配置，余下的任务由任何集卡在剩下的序列位置执行即可。假设集卡数量为10。粒子群算法中，迭代次数设为100，种群规模设为80，学习因子均设为1.4，初始惯性权重值设为0.95，最终惯性权重值设为0.1。采用粒子群算法计算10次，取最优结果见表6和表7。表6列出了前50项任务的执行集卡序号以及在该集卡作业序列中的执行顺序。以任务1为例，它由第5辆集卡执行，排在第5辆集卡作业序列的第10位。表7列出了各集卡的执行任务的数量。前50项任务按表6的规划执行，其余450项任务根据表6和表7在剩下的序列位置中执行即可。优化后总空载距离为420200米。

表6 前50项任务的集卡配置

表7 各集卡执行任务数量

5.3 结果分析

基于第一阶段集卡路径优化模型的求解结果可知，集卡总行驶路径为2300000米。在未经第二阶段路径优化之前，按各个路径依次执行的方式，计算空载距离为430000米。空载率为18.70%。进行第二阶段集卡路径优化之后，根据上述结果空载距离为420200米，空载率为18.35%，空载率得到降低。

对于不同集卡数量，基于第二阶段优化模型，空载率情况见图3。可见集卡数量的增加有利于降低空载率，但在实际决策过程中需要考虑集卡数量增加带来的成本。

图3 集卡数量对空载率的影响

6 结语

针对传统文献仅对集卡路径做了初步优化而未考虑集卡数量和作业顺序的问题，本文从两个阶段对集装箱码头的集卡路径优化问题展开了研究。第一阶段研究了集卡路径初步规划问题，考虑到集卡行使距离影响运输时间从而影响整个码头的作业效率，第一阶段以集卡总行驶距离最小为目标函数，建立了集卡路径优化模型，得到了各条路径以及每条路径运输的集装箱数量。在上述基础上，将第一阶段模型求解结果作为已知输入，把每条路径的一次运输过程当成一项任务。同时考虑到集卡的空载距离影响集卡单位运输成本与运输效率，以集卡任务间空载距离最小为目标，建立了第二阶段集卡路径优化模型。并采用粒子群算法进行求解，得到了每辆集卡的行走路径以及作业顺序。结果显示，经过第二阶段集卡路径优化之后集卡空载率得到降低，并且集卡数量的增加有利于降低空载率。

[1] 计明军,刘丰硕,李郭记,等. 基于装卸协同作业的集装箱码头集卡调度及配置优化[J]. 大连海事大学学报,2010,36(1):47-50.

[2] Grunow M, Günther H O, Lehmann M. Dispatching multi-load AGVs in highly automated seaport container terminals[M]. Berlin Heidelberg： Springer, 2005.

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

[4] Nishimura E.Yard trailer routing at a maritime container terminal[J].Transportation Research Part E,2005,41(1):53-76.

[5] Amini A, Tavakkoli-Moghaddam R. A bi-objective truck scheduling problem in a cross-docking center with probability of breakdown for trucks[J]. Computers & Industrial Engineering, 2016, 96:180-191.

[6] Cordeau J F, Legato P, Mazza R M, et al. Simulation-based optimization for housekeeping in a container transshipment terminal[J]. Computers & Operations Research, 2015, 53: 81-95.

[7] Kozan E. Optimising container transfers at multimodal terminals[J]. Mathematical and Computer Modelling, 2000, 31(10): 235-243.

[8] Berghman L, Leus R. A Lagrangian heuristic for a dock assignment problem with trailer transportation[C]//Proceedings of 2010 IEEE International Conference on, Industrial Engineering and Engineering Management, (IEEM), 2010.

[9] 杨静蕾. 集装箱码头物流路径优化研究[J]. 水运工程,2006,(1):32-35.

[10] 吕品,乐美龙. 基于作业面的集装箱港口集卡路径及成本优化[J]. 青岛科技大学学报(自然科学版),2015,36(3):327- 332.

[11] 魏宏磊,朱瑾. 基于“作业面”优先策略的集装箱港口集卡路径优化研究[J]. 中国水运(下半月), 2012,12(1):70-72.

[12] 计明军, 靳志宏. 集装箱码头集卡与岸桥协调调度优化[J]. 复旦学报: 自然科学版, 2008,46(4):60-64+72.

[13] 曹庆奎, 赵斐. 基于遗传蚁群算法的港口集卡路径优化[J]. 系统工程理论与实践, 2013, 33(7): 1820-1828.

[14] 曾庆成, 杨忠振. 集装箱码头集卡调度模型与 Q 学习算法[J]. 哈尔滨工程大学学报, 2008, 29(1): 1-4.

[15] 曾庆成, 陈文浩, 胡祥培. 集装箱码头外部集卡预约优化模型与算法[J]. 中国管理科学, 2015, 23(10): 125-130.

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

[17] 杨忠振, 程健南. 基于出口箱随机到达码头的车船直取装船作业优化[J]. 大连海事大学学报, 2016, 42(4):97-104.

[18] Salman A, Ahmad I, Al-Madani S. Particle swarm optimization for task assignment problem[J]. Microprocessors and Microsystems, 2002, 26(8): 363-371.

[19] 纪震, 廖惠连, 吴青华. 粒子群算法及其应用[M]. 北京：科学出版社, 2009.

Two-stage Optimization for Yard Trailers Routing In Container Terminals

ZHAO Jin-lou1, HUANG Jin-hu1, LIU Xin2

(1. School of Management and Economics, Harbin Engineering University, Harbin 150001, China；2.CEPREI, Guangzhou 510610, China)

With the continuous development of container transportation business, the efficiency and management level of container terminal is more and more important. At the same time, the problem of yard trailers routing receives more attention because yard trailers work as the main machine to carry containers in the horizontal direction at terminals. However, most current research on yard trailers routing problem did not consider the influence of no-load distance on trailers’ transport efficiency, and a large part of current research just made routing optimization for singer yard trailers ignoring the condition of different trailers. Under the above background, a two-stage routing optimization model which consisting of two relevant models for yard trailers is proposed to solve the routing problem based on pool strategy. This strategy means loading and unloading operations are performed during one work route instead of doing loading and unloading operations separately. On the first stage, a routing optimization model is given to minimize the route distance without considering the number of yard trailers. This model is used to determine which import and export blocks to go through. On the second stage, for the purpose of minimizing no-load distance, the other routing optimization model which considers the number of trailers is constructed based on the result of the first model. According to the characteristics of two models, the software of Lingo is used to solve the first model, and particle swarm optimization method is utilized to solve the second model which involves route assignment and job order for every trailer. The results show that the no-load distance and no-load rate are decreased after the optimization on the second stage. In addition, with the second stage model, it is found that increasing the number of trailers is helpful to reduce the no-load rate. By proposing the two-stage routing optimization model, both the no-load distance and the number of yard trailers are taken into account and improves the existing research.

container terminals; yard trailers; two-stage routing optimization; particle swarm optimization

2015-06-03；

2016-05-26

工信部高技术船舶科研项目；中央高校基本科研业务费专项资金重点项目(HEUCFD1505)；国家自然科学基金面上项目(71271062)

刘馨(1992-)，女(汉族)，湖南衡阳人，工业和信息化部电子第五研究所标准与信息研究中心，助理工程师，研究方向：产业分析、优化理论与方法，E-mail: liuxin421001@163. com.

1003-207(2017)04-0152-06

10.16381/j.cnki.issn1003-207x.2017.04.018

U691；C931

A