一种集装箱港口集卡的动态调度方法

马慧娟，杜玉越

(山东科技大学 信息科学与工程学院，山东 青岛 266590)



一种集装箱港口集卡的动态调度方法

马慧娟，杜玉越

(山东科技大学 信息科学与工程学院，山东 青岛 266590)

摘要：在集装箱港口中，设备的配置和调度对港口的运作效率有着较大影响。为了研究集装箱港口岸桥与集卡的调度，在混合交叉作业模式下，基于集卡运输时间和集卡排队等待时间的权重系数考虑，建立了以总作业时间最小为目标的集卡动态调度模型，实现了不同船舶装船作业和卸船作业同时进行的集卡动态分配。最后，通过对集装箱港口实际作业流程的建模仿真，例证了本文模型的有效性和实用性。

关键词：集装箱港口；混合交叉作业；集卡动态调度；仿真模型

现代集装箱港口是陆运与海运两种运输方式间集装箱转运的中转枢纽，在全球综合运输体系中发挥着日益重要的作用。在贸易规模与日俱增的繁荣期，如何在现有的港口规模下，挖掘潜力，改进管理水平，研究港口装卸工艺流程和资源调度，进一步优化利用现有的资源来改善港口的吞吐能力，降低运营成本，是港口提高自身竞争力的重点。

由于集装箱港口生产作业的复杂性，目前较常见的优化方法是将港口作业系统分为若干子系统，分层次进行优化。具体地可以分为泊位调度分配[1]、岸桥调度[2]、水平搬运设备等的调度配置[3-4]、堆场内场桥等设备的资源调度[5-6]以及不同装卸工艺[7-8]等。在集卡路线优化方面，杨静蕾[9]以集卡行驶距离最短为目标，建立集卡路径优化模型，求解集卡最优行驶路径；CAO等[10]考虑了集卡资源有限制下的集卡调度模型，建立了以集卡运输时间和等待时间加权和最小为目标函数的模型，设计了改进算法来求解模型。但前者只考虑集卡行驶路径最短，没有考虑集卡的行驶时间，而后者的优化目标考虑因素不够全面。

针对岸桥与集卡联合调度问题，本文在混合交叉作业模式下，基于集卡运输时间和集卡排队等待时间的权益系数，将岸桥作业时间、集卡排队等待时间和集卡行驶路径多种因素考虑在内，提出一种以作业时间最少为目标的集卡动态调度算法。最后以青岛某集装箱港口的一个时段为案例，通过建模仿真方式例证了本文方法的正确性和有效性。

1问题描述

1.1港口装卸作业流程

集装箱港口的作业流程，是集装箱从卸船到离港，从进港到装船的搬运过程中，采用的工艺流程、装卸搬运机械类型及其相互配合的作业方式[11]。船舶进港后先给其分配泊位，然后根据船舶的装卸量制定相应的装载和卸载计划，对岸桥、场桥和集卡进行分配和调度，堆场根据堆存策略安排集装箱的位置。

1.2不同装卸模式分析

独立装卸作业模式，是指给某一艘船舶配备一定数量的岸桥和集卡的装卸模式[12]，如图1所示。在卸船过程中，集卡在泊位a搭载一个进口集装箱运送到进口箱区i，然后空载返回泊位a去卸载另一个进口集装箱；在装船过程中，集卡在出口箱区j装载一个集装箱运送到泊位b，然后空载返回堆场去装载另一个出口集装箱。

图1　独立装卸作业模式示意图

图2　混合交叉作业模式示意图

混合交叉作业模式，是指基于作业面的调度模式下，集卡池的集卡不再单独服务于一艘船，而是按照整体优化思想来完成集装箱的装载和卸载任务[12]，如图2所示。混合交叉作业模式下，集卡在装卸作业时，可有多种选择：

1) 单程卸载：集卡从进口泊位a重载至进口箱区i，然后空车返回泊位a；

2) 单程装载：集卡从出口箱区j重载至出口泊位b，然后空车返回箱区j；

3) 同步装卸：集卡从进口泊位a重载至进口箱区i，空驶至出口箱区j，再重载至出口泊位b，然后空驶至泊位a。

1.3集卡调度的数学模型

根据岸桥、场桥作业时间和集卡的运输时间，在“作业面”作业模式下，建立了集卡调度模型[13]。模型参数和变量定义如下：tai表示集卡从进口泊位a行驶到进口箱区i的时间(集卡从进口箱区i行驶到进口泊位a的时间也为tai)；tij表示集卡从进口箱区i行驶到出口箱区j的时间；tjb表示集卡从出口箱区j行驶到出口泊位b的时间(集卡从出口泊位b行驶到出口箱区j的时间也为tjb)；tba表示空载的集卡从出口泊位b行驶到进口泊位a的时间；t1表示岸桥装、卸集装箱作业时间；t2表示场桥装、卸集装箱作业时间；m表示进口箱区的数量；n表示出口箱区的数量；k表示进口泊位的数量；l表示出口泊位的数量；Di表示计划从进口泊位卸到进口箱区i的进口集装箱数量；Lj表示计划从出口箱区j运输到出口泊位的出口集装箱数量；Da表示从进口泊位a进口的集装箱总量；Lb表示从出口泊位b出口的集装箱总量；xaijb表示集卡从进口泊位a重载至进口箱区i，卸载后集卡空驶至出口箱区j装箱后再重载至出口泊位b的次数；xai表示集卡从进口泊位a重载至进口箱区i再空车返回到泊位a的次数；xjb表示集卡从出口箱区j重载至出口泊位b再空车返回到箱区j的次数。

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

(1)

(2)

(3)

(4)

(5)

式(1)是目标函数，表示集卡完成所有进出口集装箱所用的运输时间与岸桥、场桥作业时间之和最小；式(2)表示计划堆存在进口箱区i的集装箱由集卡从进口泊位全部运送到进口箱区i；式(3)表示计划从出口箱区j运送到出口泊位的集装箱由集卡从出口箱区j全部运送到出口泊位；式(4)表示集卡从进口泊位a运输到各个进口箱区的集装箱总数等于计划从进口泊位a进口的集装箱总数；式(5)表示集卡从各个出口箱区运输到出口泊位b的集装箱总数等于计划从出口泊位b出口的集装箱总数。

2集卡动态调度算法

集卡动态调度是在装载计划和卸载计划已知的前提下，根据岸桥装卸任务给岸桥动态分配集卡的过程。本节设计一个集卡动态调度算法来实现混合装卸模式下给岸桥动态分配集卡的问题，以期获得比传统的给泊位配备固定集卡的方法更短的作业时间，减少集卡的行驶距离，提高岸桥的利用率。算法设计的详细流程如图3所示。

算法1：集卡动态调度算法

Step1：设置需要分配集卡的岸桥编号为i，i=(1,…,Nc)(Nc为需要分配集卡的岸桥的数量)。

Step2：定义树节点Ldi和Lli，其中Ldi用于存储一个给定岸桥i未完成的卸载列表，Lli用于存储一个给定岸桥i未完成的装载列表。如果岸桥i的卸载列表Ldi和装载列表Lli都不存在，则转Step18；否则，返回Ldi中集装箱数量Ncdi和Lli中集装箱数量Ncli。

Step4：如果目前被派往岸桥i卸载的集卡总数与被派往岸桥i装载的集卡总数之和大于等于Nti(，即Ntdi+Ntli≥Nti′，则转到Step18，其中Ntdi包括前往岸桥i和在岸桥i处等待的集卡，Ntli包括前往岸桥i和在岸桥i处等待的集卡。

Step5：如果Ncdi>0，则岸桥i的初始卸载积分Sdi=0；否则转Step9。

Step6：如果当前集卡没在堆场并且已经分配给了岸桥i做卸载操作，则岸桥i的卸载积分Sdi1=Sdi+Sd，Sd为岸桥一次卸载操作积分；否则，该岸桥卸载积分Sdi1=Sdi+w1×di，其中w1为集卡行驶单位距离的权重，di为集卡到达目的地岸桥i需要行驶的距离。

Step8：如果Sdi2>S0，S0为一个初始值，则S0=Sdi2，把当前集卡分配给岸桥i，岸桥i卸载Ldi中第Ncdi个集装箱。

Step9：如果Ncli>0，则装载积分Sli=0；否则转Step18。

图3　集卡动态调度算法流程

Step11：如果当前集卡在堆场，岸桥i装载积分Sli2=Sli1+SL，SL为场桥一次装载操作积分；

否则，Sli2=Sli1。

Step12：设置需要装载的集装箱编号为j，j=(1，…，Ncli)。

Step13：返回装载计划列表中第j个集装箱所在箱区的信息，第j个集装箱所在箱区中的要装载集装箱数量NbL= 指定的调度任务序列。

Step14：临时装载积分Sli3=Sli2+w2×NbL，w2为多个集卡行驶到同一个箱区的权值，NbL为集装箱数量。

Step15：岸桥i临时装载积分Sli4=Sli3+w1×d，d为集卡到达目的箱区需要行驶的距离。

Step16：如果Sli4>S0，S0为初始值，则S0=Sli4，把当前集卡分配给岸桥i，装载Lli中第j个集装箱。

Step17：j=j+1，判断是否j≤Ncli，如果j≤Ncli，转到Step13。

Step18：i=i+1，判断是否i≤Nc，如果i≤Nc，转到Step2。

Step19：判断Ncdi和Ncli是否大于0，若Ncdi>0或者Ncli>0，转到Step1；否则，结束。

在该算法中，集卡不再固定服务于某一岸桥或者某一艘船舶，而是根据待装卸集装箱在堆场箱区的实际位置，进行动态调配。集卡在完成一次作业后，控制系统以总作业时间最小为目标，根据集卡在岸桥排队等待时间和运输时间给集卡分配下一个任务，集卡在任意时刻根据岸桥的需求以及路径距离的远近被选用，为岸桥、场桥共享，集卡服务的对象动态地与整个港口的作业面进行搭配。

3仿真模型运行及结果分析

3.1仿真假设

利用FlexTerm仿真软件对集装箱港口的实际问题进行建模仿真。考虑到在集装箱港口实际运作环境中，各作业环节比较繁琐，本文在建立仿真模型时，基于以下假设条件进行简化：

1) 集卡每次只能装载一个集装箱；

2) 集卡独立运行，且互不干扰；

3) 所有设备均不考虑故障与维护，处于连续工作状态；

4) 不考虑集装箱的分类，认为所有的集装箱都一样。

3.2案例设计

利用青岛某集装箱港口的案例来分析上述集卡动态调度方法。该港口某时段一艘深海船舶需要卸载集装箱800个，另一艘深海船舶需要装载集装箱800个，根据港口现有泊位、岸桥和集装箱船舶技术参数设计案例，从船舶靠港到离开，对两艘船的装卸作业进行连续仿真。岸桥单装或者单卸一个集装箱的平均时间为1.5 min，集卡的平均速度为18 km/h，这一时段内涉及岸桥数量为4，各个箱区的装卸箱量如表1所示。

表1　各箱区进出口集装箱数量

岸桥和场桥的作业过程包括装载、卸载和移动等活动，集卡搬运过程包括装载、卸载、等待和卡车搬运等活动。模型的初始状态是集卡在等候场地待命。作业过程中，所有从船上卸下的进口集装箱都由集卡运至进口箱区，所有要装船的出口集装箱都由集卡从出口箱区运至出口船舶。

3.3仿真结果分析

通过仿真得到不同集卡数量下，集卡动态调度作业与集卡独立调度作业船舶在港时间(如表2所示)。

表2　不同集卡数量下船舶在港时间

可以看出，整体来说，不同集卡数量下，集卡动态调度模型船舶在港时间比独立作业模式下都要短一些，尤其是在集卡资源较少时，动态调度作业比独立装卸作业完成装卸任务更快。随着集卡数量的增加，装卸作业时间迅速减少，当集卡达到8辆时，随着集卡的增加，无论是集卡动态调度还是独立装卸，船舶在港时间下降趋势都不断减缓，所以配置8辆集卡是比较合理的。

配置8辆集卡时两种调度方式的岸桥利用率如图4所示。数据表明，采用集卡动态调度的方法，对集卡运输的过程进行综合调度，岸桥利用率提高了5%～10%，能有效减少船舶在港时间。

图4　两种调度方式的岸桥利用率

求解集卡动态调度运输路径和箱量如表3所示。表中O1代表进口船舶，O2代表出口船舶，O1→5→4→O2代表从进口船舶O1到箱区5卸箱再到箱区4装箱运输到出口船舶O2。从表中看出，集卡装卸作业绝大部分是在箱区之间进行的，这样的动态调度使集卡双向重载行驶，集卡行驶总里程为595.7 km，与独立调度时的948.5 km相比减少了37%。

表3　集卡的运输路线和装卸箱量

4结语

本文以总作业时间最小为目标，综合考虑岸桥作业时间、集卡排队等待时间和集卡行驶路径多种因素，给出了一种集装箱港口集卡动态调度方法，并通过仿真的方式，以实际集装箱港口作业流程为原型进行案例分析。案例结果显示，本文提出的模型和算法是合理可行的，对减少船舶在港时间和集卡总行驶距离、提高岸桥利用率有明显的作用。本文主要考虑的是集卡的调度问题，没有考虑堆场场桥的数量以及堆放策略，这是本课题组下一步的研究内容。

参考文献：

[1]陈超,王海燕.集装箱码头泊位生产运作优化模型[J].大连海事大学学报,2009,35(4):52-58.

CHEN Chao,WANG Haiyan.An optimal model of container quay berth production operation[J].Journal of Dalian Maritime University,2009,35(4):52-58.

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

[3]张莉,霍佳震.基于单船装卸运输模型的集卡配置仿真研究[J].系统仿真学报,2006,18(12):3532-3535.

ZHANG Li,HUO Jiazhen.Configuring container truck optimization based on simulation model of single ship handling and transportation on container terminal[J].Journal of System Simulation,2006,18(12):3532-3535.

[4]王涛,黄有方,严伟.多集装箱码头内集卡调度方法[J].大连海事大学学报,2015,41(1):69-76.

WANG Tao,HUANG Youwei,YAN Wei.Internal trucks dispatching method among multiple container terminals[J].Journal of Dalian Maritime University,2015,41(1):69-76.

[5]严伟,宓为建,苌道方.一种基于最佳优先搜索算法的集装箱堆场场桥调度策略[J].中国工程机械学报,2008,6(1):95-100.

YAN Wei,MI Weijian,CHANG Daofang.Investigation into yard crane scheduling using BFS algorithm[J].Chinese Journal of Construction Machinery,2008,6(1):95-100.

[6]秦天保,刘兰辉,沙梅.集装箱码头堆场道路交叉口车流仿真研究[J].系统仿真学报,2014,26(5):430-434.

QIN Tianbao,LIU Lanhui,SHA Mei.Research on road intersection simulation of container terminal yard[J]. Journal of System Simulation, 2014,26(2):430-434.

[7]韩晓龙,张少凯,于航.基于仿真的集装箱港口装卸工艺对比研究[J].系统仿真学报,2014,26(5):1170-1175.

HAN Xiaolong,ZHANG Shaokai,YU Hang.Comparative research of handling technologies based on simulation in container terminal[J].Journal of System Simulation,2014,26(5):1170-1175.

[8]张睿,靳志宏,刑曦文.同贝同步模式下的集装箱装卸作业调度优化[J].系统工程学报,2014,29(6):833-844.

ZHANG Rui,JIN Zhihong,XING Xiwen.Optimization of container scheduling on integrated loading and unloading operations in same ship-bay[J].Journal of Systems Engineering,2014,29(6):833-844.

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

YANG Jinglei.Logistics routing optimization of container terminals[J].Port & Waterway Engineering,2006(1):32-35.

[10]CAO J X,SHI Q X,LEE D H.Integrated quay crane and yard truck schedule problem in container terminals.Tsinghua Science and Technology,2010,15(4):467-474.

[11]田亮.基于同步装卸的岸桥与集卡协同作业优化研究[D].大连:大连海事大学,2013:6-20.

[12]王伟飞.基于混合交叉作业的集装箱码头集卡优化调度研究[D].大连:大连海事大学,2011:14-17.

[13]王军,许晓雷.集装箱码头集卡作业路径的选择[J].大连海事大学学报,2011,37(2):25-27,34.

WANG Jun,XU Xiaolei.Route selection of container trucks in container terminal[J].Journal of Dalian Maritime University,2011,37(2):25-27,34.

(责任编辑：傅游)

收稿日期：2016-01-25

基金项目：国家自然科学基金项目(61170078,61472228);山东省泰山学者攀登计划建设项目；山东省自然科学基金项目(ZR2014FM009)

作者简介：马慧娟(1990-)，女，山东菏泽人，硕士研究生，主要从事港口调度与仿真研究. 杜玉越(1960-)，男，山东聊城人，教授，博士生导师，主要从事Petri网、工作流、过程挖掘等方面的研究，本文通信作者.E-mail:yydu001@163.com

中图分类号：U691.3

文献标志码：A

文章编号：1672-3767(2016)04-0099-07

A Dynamic Scheduling Method of Truck in Container Terminal

MA Huijuan,DU Yuyue

(College of Information Science and Engineering,Shandong University of Science and Technology,Qingdao,Shandong 266590,China)

Abstract:In the container terminal, the configuration and scheduling of equipment affect the operational efficiency significantly of a container terminal. In order to study the Scheduling of quay cranes and trucks in the container terminal, With the consideration of weight parameters among the truck’s transportation time and the truck’s waiting time,a dynamic scheduling model isformulated in the mixed cross-operation mode,whose objective is to minimize total time. The model enables dynamic allocation of truck for the loading and unloading operation simultaneously of different ship. Finally, the container terminal simulation experiments are given to illustrate the effectiveness and practicality of the model.

Key words:container terminal; mixed cross-operation;truck dynamic scheduling; simulation model