集装箱码头考虑集卡能耗的岸桥集卡协调调度

严南南，杨 莹

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

集装箱码头考虑集卡能耗的岸桥集卡协调调度

严南南，杨 莹

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

随着环境污染和资源紧缺的加剧，绿色港口逐渐成为未来港口发展的必然趋势。因此针对岸桥集卡协调调度，建立了一个考虑集卡能耗和岸桥集卡作业时间的多目标数学模型。由于岸桥和集卡作业时间及集卡能耗这两个目标既有联系，又有一定程度的冲突，因而使用多目标优化的方法平衡这两个目标，并且采用遗传算法结合Matlab数学软件求解模型。算例结果表明:考虑集卡能耗的调度比不考虑集卡能耗的调度更节约调度成本，从而验证了模型和算法的有效性。

集装箱码头；岸桥集卡协调调度；集卡能耗；绿色港口；遗传算法；Matlab

0 引 言

随着交通运输中二氧化碳的大量排放，对环境和全球气候变暖产生重大威胁，所以要处理好资源消耗问题，特别是能源问题，例如石油、天然气和煤炭资源的消耗。因此，绿色交通也逐渐成为交通产业的目标之一。集装箱码头作为整个交通产业的重要组成部分，也是环境污染的主要来源之一。因此，加强码头绿化建设是当前绿色交通的必然选择。

岸桥、集卡作为集装箱码头的重要设备，其作业能力直接影响集装箱码头整体作业能力。岸桥将集装箱从船上卸下后，再由集卡运送到堆场。在堆场中，场桥将集装箱从集卡上卸下存入堆场或将其从堆场中拾起。这样，集卡就成了岸桥端和场桥端的重要连接设备。因此，加强岸桥和集卡的协调调度是提高集装箱码头作业效率的关键。

集装箱码头在岸桥方面的研究,秦天保等[1]提出一个约束规划模型，并考虑到了岸桥冲突、任务优先级等约束来求解大规模集装箱码头调度问题，并与启发式算法进行比较。秦进等[2]针对集装箱码头多船舶的岸桥调度及卸船任务分配建立了一个混合整数规划模型，并通过设计限制任务路径进行邻域搜索结合双层模拟退火算法求解模型。董良才等[3]对于岸桥调度问题，综合考虑了岸桥干扰和作业优先级约束，以最小化船舶及岸桥作业时间为目标，并用改进萤火虫算法求解模型。AL-DHAHERI等[4]针对不确定岸桥调度问题，建立了随机混合整数规划模型，并通过基于仿真的遗传算法进行求解。UNSAL等[5]提出了岸桥调度约束规划模型及基于时间窗下的整合岸桥分配及调度问题研究。

集装箱码头在集卡方面的研究,王军等[6]在作业面模式下，建立时间最短的集卡调度模型，在装船、卸船同时进行前提下的集卡作业路径选择。NG等[7]通过使用遗传算法，并引用其中的交叉方案来求解集卡调度模型，以使得最大完工时间最小化。AMINI等[8]对于集卡调度交叉对接时可能产生的故障而提出了一个双目标集卡调度，并使用响应面法结合元启发式算法求解。

集装箱码头在岸桥集卡协调调度方面的研究，韩晓龙等[9]针对岸桥集卡协调调度，考虑到集卡作业时的不确定性到达，建立了集卡与岸桥作业的协同调度数学模型，并用CHC算法求解。梁承姬等[10]考虑了岸桥干扰和集装箱优先级等约束，构建了将最大完工时间最小化的数学模型，通过对比GA算法和PSO算法，得出GA算法(遗传算法)的有效性。TANG等[11]在只考虑岸桥、集卡单向移动及卸船情况下，以最小化最大完工时间为目标，建立混合整数线性规划模型，并用改进的粒子群算法求解模型。KAVESHGAR等[12]考虑了实际操作中集装箱优先级、阻塞、岸桥干扰及岸桥间安全距离等约束，建立了整合调度模型，并将遗传算法和改进贪婪算法相结合对模型进行求解。

集装箱码头在能耗方面的研究还比较少，大多数的文献还只是宏观层面上的，且大部分是国外文献，国内文献还很少。郭婵婵[13]通过采用流水车间思想来构建岸桥、集卡和场桥的多目标调度模型，以实现装卸作业时间最小和机械能耗最小的目标。GOLIAS等[14]提出了最小化船舶延迟离港时间目标，通过这一目标可以间接降低船舶闲置时所产生的能耗排放量。GOLIAS等[15]在之前的最小化船舶延迟离港时间这一目标基础上，同时考虑了所有船舶能耗排放总量最小化的双目标问题。CHANG等[16]在泊位岸桥分配模型中提出了能耗优化目标。HUANG等[17]提出了多个码头间共享内集卡的整数规划模型，模型中集卡交通能耗最小化也是目标之一。

相对于已有文献，本文的创新在于对岸桥集卡协调调度问题考虑了能耗因素。目前，我国集装箱码头设备作业时考虑能耗因素的情况较少，为了达到节约能耗的目的，将集卡能耗模型考虑进去，以最小化岸桥、集卡作业时间及集卡总能耗为目标，建立相应模型，并应用遗传算法求解模型。

1 问题描述

随着环境污染和能源压力的加剧,节能也逐渐成为码头运营的目标之一。在岸桥集卡协调调度总能耗中，集卡所产生的能耗占了较大比重。因此，本文将集卡总能耗最小化作为本文的目标之一。本文考虑多船、多岸桥、多集卡装卸及运输情况。船上集装箱根据贝位划分为多个区域，通常情况下，各个区域分配一台岸桥；一台岸桥由某组固定的集卡服务，本文称之为一条作业线。整个作业过程就是岸桥将进口集装箱从船上卸载到集卡上，由集卡运输进口集装箱到堆场指定箱区，再由场桥将进口集装箱从集卡上卸下，集卡再从堆场出口箱区运输一个出口集装箱到出口船舶指定位置。目标是实现岸桥集卡总的作业时间最小化及集卡总能耗最小化。

模型假设：①岸桥为某一船舶贝位服务时，要将该船舶贝位上的所有集装箱服务完成后才能服务于其他贝位的集装箱。②岸桥移动方向为单向(从左向右移动)。③各集装箱被服务顺序具有优先级关系，例如：岸桥必须作业完上层集装箱才能作业下层集装箱。④不考虑岸桥等集卡及场桥等集卡的情况。

2 模型建立

在模型方面，本文建立了一个多目标函数，因为多目标优化相比于单目标优化可以更准确地对实际问题进行建模，因此具有更广泛的适用性。而利用多目标优化对岸桥集卡协调调度问题进行建模的现有文献较少。同时本文考虑了进口箱和出口箱两种情况下的装卸，而以往很多文献多是考虑一种情况下的装卸。此外在约束条件上考虑了实际作业情况，如岸桥、集卡对集装箱装卸顺序的考虑。

目标函数：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

约束条件：

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

aqi,cqi,ayi,cyi,Rqam,Zaqm≥0,

(24)

(25)

式(8)～式(11)每一集装箱仅由一个岸桥或集卡作业。式(12)～式(15)当岸桥与集卡对集装箱作业时，每一集装箱的前序或后序作业最多只有一个。式(16)对同一集卡的进口集装箱任务作业顺序的约束。式(17)对同一集卡的出口集装箱任务作业顺序的约束。式(18)对集装箱任务对进行约束，如果进口箱i和出口箱j为一任务对，则i和j需由同一集卡运输。式(19)某一船舶待卸集装箱数等于卸到各对应进口箱区的集装箱数。式(20)集卡从各出口箱区运送集装箱到对应岸桥的次数等于某一船舶的待装集装箱数。式(21)集卡运输出口集装箱之和小于等于出口集装箱总数量。式(22)集卡从岸桥端运送进口集装箱到进口箱区的次数(也为集卡运送进口集装箱数量)不能超过对应进口箱区的最大容量。式(23)指某一船舶的操作箱量与该船的待装量及待卸量的和相等。式(24)和式(25)是决策变量约束。

3 遗传算法

遗传算法(GA)是一种随机性搜索算法，它借鉴生物界自然选择及遗传机制，通过模拟自然进化过程来搜索最优解，对于解决大规模复杂网络路径优化问题具有较好的适用性。遗传算法也是计算机科学人工智能领域中用于解决最优化问题的一种启发式进化算法，并且一般用来产生新的解决策略以达到优化解的目的。

3.1 染色体编码

针对岸桥集卡协调调度数学模型，本文采用矩阵式编码，如图1所示，s1代表船舶1上集装箱被岸桥、集卡服务的顺序，s2代表船舶2上集装箱被岸桥、集卡服务的顺序、并依此类推。每一染色体基因有6行编码，第一行指进口集装箱编号，第二行指出口集装箱编号，第三行指岸桥服务集装箱顺序，第四行指集卡服务集装箱顺序，第五行指进口箱区编号，第六行指出口箱区编号。从图1可知，对于进口集装箱，岸桥1要先服务进口集装箱6再服务进口集装箱11、4、12、14和1；对于出口集装箱，岸桥1要先服务出口集装箱17再服务出口集装箱16、5、7、3和10。岸桥2要先服务进口集装箱22再服务进口集装箱5、10和19；对于出口集装箱，岸桥2要先服务出口集装箱25再服务出口集装箱21、6和15。集卡11要先服务进口集装箱22再服务进口集装箱5；对于出口集装箱，集卡11要先服务出口集装箱25再服务出口集装箱21。关于堆场箱区，进口集装箱6、12和1要被集卡运输到进口箱区编号为2的箱区，同理，出口集装箱17、7和10分别要被集卡从出口箱区编号为5、6和5的箱区运出。

图1 染色体编码Fig.1 Chromosome coding

3.2 种群初始化

本文通过采用随机生成方法产生种群，目的是为了确保种群的多样性。由于相同贝位的集装箱需要由同一个岸桥作业，并且岸桥服务集装箱具有一定的先后顺序(即优先级约束要求)。通过随机生成方法产生的初始解，由于其随机性可能不满足上述约束条件，因此需对初始解中的不可行解进行修复。

例如：对于岸桥调度，假设进口集装箱25,12,32,40属于一个相同贝位，进口集装箱5,28,34,19,38,13属于另一个相同贝位；出口集装箱36,39,34,26属于一个相同贝位，出口集装箱48,27,33,16,47,31属于另一个相同贝位。如图2所示。

图2 修复前的岸桥调度Fig.2 Before the repair of QCs’ scheduling

图2是随机产生的一个染色体，这个染色体违反了相同贝位应由相同岸桥服务的约束，需进行修复，将进口集装箱40和出口集装箱26对应的贝位变为1，进口集装箱19和出口集装箱16对应的贝位变为3。如图3为修复后的岸桥调度。

图3 修复后的岸桥调度Fig.3 Repaired QCs’ scheduling

3.3 适应度函数

本文直接用目标函数作为适应度值，并通过适应度值对各个可行解的优劣进行判断。

F=1/(f1+f2)。

(26)

3.4 遗传操作

3.4.1 选择

使用轮盘赌选择操作[18]，具体步骤如下所示：

Step 1: 计算种群的所有适应度值;

Step 2: 计算每个个体的选择概率;

Step 3: 计算每个个体的累积概率;

Step 4: 产生一个随机数r∈(0,1],如果Ci-1

3.4.2 交叉

本文通过交叉算子来寻找一个更广阔的搜索空间和更优解。随机选择两个父代，且使用两点交叉法，分别在两个父代中随机选择两个基因位，然后再交换这两个基因位上相对应的值，如图4所示。

3.4.3 变异

本文中，交换变异算子被用于所有子染色体的操作序列。在父代中随机选择两个基因位，并交换这两个基因位上的值，如图5所示。

图5 染色体变异操作Fig.5 Chromosome mutation operation

4 算例分析

为了评估所提出的模型和算法的有效性，通过Matlab对以下算例进行验证。本文在遗传算法中设置最大迭代数为250、交叉概率0.7、变异概率0.03、种群规模为 50个。

4.1 试验参数设计

设有2艘船舶，4台岸桥，24辆集卡，50个进口集装箱和50个出口集装箱任务。如表1为码头设备的试验参数，表2、表3分别为进、出口箱区和泊位间的距离，表4为堆场进口箱区和出口箱区之间的距离，表5为堆场进、出口箱区的卸箱数和装箱数。

表1 集装箱码头设备试验参数
Tab.1 Test parameters of container terminal equipment

参数名称参数值每岸桥卸载一个进口集装箱的时间/s180每岸桥装载一个出口集装箱的时间/s170每场桥卸/装载一个集装箱的时间/s120每个集卡的运行速度/(m·s-1)083每个空载集卡单位距离燃油消耗量/(L·m-1)00008每个装载集卡单位距离燃油消耗量/(L·m-1)00012每个集卡单位时间内等待能耗/(L·h-1)000125集卡燃油市场价/(元·L-1)545每台岸桥单位使用成本/[元·(台·h)-1]882每辆集卡单位使用成本/[元·(辆·h)-1]52

表2 进口箱区与泊位间的距离Tab.2 Distance between the import box area and berth m

表3 出口箱区与泊位间的距离Tab.3 Distance between the export box area and the berth m

表4 堆场进口箱区和出口箱区间的距离Tab.4 Distance between the import and export area of the yard m

表5 堆场进出口箱区的卸箱数和装箱数Tab.5 Number of import and export container’s unloading and loading boxes TEU

4.2 算例结果

对于岸桥调度，表6为岸桥调度的一个满意解：岸桥对集装箱作业时具有优先级顺序，例如岸桥1对进口集装箱的作业顺序为20→24→23→10→8→22→15→6→14,对出口集装箱的作业顺序为1→15→3→11→25→6→17→16→9。岸桥2对进口集装箱的作业顺序为16→17→9→2→5→19→7→4→3→12→13→21→25→11→1→18, 对出口集装箱的作业顺序为18→7→24→13→8→21→14→20→10→23→4→19→12→5→2→22。对于集卡调度，表7为集卡调度的一个满意解：集卡所分配的集装箱任务总体上较均匀，集卡不再服务于固定岸桥，这样可以减少集卡等待岸桥的时间。图6显示集卡运行总距离收敛图，遗传算法在接近于50代时开始收敛，收敛于51 370 m。

表6 岸桥调度结果
Tab.6 Result of quay crane scheduling

岸桥进口集装箱处理顺序出口集装箱处理顺序120，24，23，10，8，22，15，6，141，15，3，11，25，6，17，16，9216，17，9，2，5，19，7，4，3，12，13，21，25，11，1，1818，7，24，13，8，21，14，20，10，23，4，19，12，5，2，22341，28，40，50，37，48，43，46，47，35，45，4237，46，44，34，47，32，43，48，42，28，27，36432，38，34，39，27，31，30，44，26，33，49，29，3641，30，38，33，31，29，39，49，26，45，50，35，40

表7 集卡调度结果
Tab.7 Result of internal truck scheduling

集卡进口集装箱处理顺序出口集装箱处理顺序124，21，4415，19，49216，4，4118，20，3732，11，48，4313，5，32，4341223540，3544，28610，26，3311，26，457714817，25，347，12，3891，472，42105034116，3616，401238301322，196，21144950159，13，14，4524，4，9，271623，3，303，10，391727311828461946，3148，2920393321201228，3225，41234236245，15，18，37，298，17，22，47，35

图6 遗传算法收敛图
Fig.6 Convergence graph of Genetic Algorithm

4.3 集卡能耗结果

对于集卡能耗，从表8可知：考虑能耗目标要比不考虑能耗目标多出4.17 min的作业时间，但在集卡能耗上可获得11.48 L的燃油节省，在总调度成本上节省了45.34元的成本。图7为考虑集卡能耗与不考虑集卡能耗成本对比结果图。

表8 考虑集卡能耗与不考虑集卡能耗成本对比结果
Tab.8 Cost comparison of considering internal truck energy consumption and without considering internal truck energy consumption

目标函数值集卡燃油消耗/L作业时间/min集卡能耗成本/元时间成本/元总调度成本/元未考虑集卡能耗目标的结果79313876743219524102567321考虑集卡能耗目标的结果678213918436962525825562787

图7 考虑集卡能耗与不考虑集卡能耗成本对比图
Fig.7 Energy cost comparison of internal truck between considering and without considering the energy consumption

5 结 语

本文提出了考虑集卡能耗和岸桥集卡作业时间的多目标协调调度问题，给出了多目标优化的数学模型，并且通过使用遗传算法结合Matlab数学工具求出了模型的近似解。从算例结果可知，考虑集卡能耗的调度结果在总调度成本上更节约成本，遗传算法求解的多目标优化结果尽管不能达到单目标结果的最大化，但是可以在一个目标稍作牺牲的前提下，实现整体目标的性能。因此，考虑集卡能耗相对于不考虑集卡能耗的岸桥集卡协调调度更能适应作业成本最小化及码头绿色物流的发展趋势。

[1] 秦天保，沙梅.基于约束规划建模求解岸桥调度问题[J]. 计算机集成制造系统，2013，19(1)：181-186.

[2] 秦进，倪玲霖，王承娜，等.集装箱码头岸桥调度优化模型及算法[J]. 西南交通大学学报，2013，48(1)：184-192.

[3] 董良才，孙思韵.用改进萤火虫算法求解岸桥调度模型[J]. 上海海事大学学报，2016，37(1)：32-37+48.

[4] AL-DHAHERI N, DIABAT A.The Quay Crane Scheduling Problem[J]. Journal of Manufacturing Systems, 2015,36：87-94.

[5] UNSAL O, OGUZ C.Constraint programming approach to quay crane scheduling problem[J]. Transportation Research Part E,2013,59：108-122.

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

[7] NG W C, MA K L, ZHANG Y X.Scheduling trucks in container terminals using a genetic algorithm[J]. Engineering Optimization，2007，39: 33-47.

[8] 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.

[9]韩晓龙，牟少莉.基于CHC算法的集卡与岸桥协调调度优化问题[J]. 武汉理工大学学报 (信息与管理工程版)，2014，36(2)：233-236+245.

[10]梁承姬，沈佳杰.考虑装卸顺序的岸桥与集卡协调调度问题研究[J]. 计算机应用研究，2016，33.

[11]TANG Li-xin, ZHAO Jiao, LIU Ji-yin. Modeling and solution of the joint quay crane and truck scheduling problem[J]. European Journal of Operational Research, 2014, 236：978-990.

[12]KAVESHGAR N, HUYNH N. Integrated quay crane and yard truck scheduling for unloading inbound containers[J]. Int J Production Economics,2015, 159：168-177.

[13]郭婵婵.考虑能耗的集装箱码头核心资源调度研究[D]. 辽宁：大连海事大学，2014.

[14]GOLIAS M M, SAHARIDIS G K, BOILE M, et al. The berth allocation problem: Optimizing vessel arrival time[J]. Maritime Economics&Logistics,2009,11(4)：358-377.

[15]GOLIAS M M, BOILE M, THEOFANIS M, et al. Theofanis,Sotiris,Efstathiou,Christos.the berth scheduling problem: Maximizing berth productivity and minimizing fuel consumption and emissions production[J]. Transportation Research Record: Journal of the Transportation Research Board,2010,2166：20-27.

[16]CHANG D F, JIANG Z H, YAN W, et al. Integrating berth allocation and quay crane assignments[J]. Transportation Research Part E: Logistics and Transportation Review,2010,46(6)：975-990.

[17]HE J L, ZHANG W M, HUANG Y F, et al. A simulation optimization method for internal trucks sharing assignment among multiple container terminals[J]. Advanced Engineering Informatics,2013,27(4)：598-614.

[18]GOLDBERG D E.Genetic algorithms in search, optimization and machine learning[M]. New York: Addison-Wesley,1989.

(责任编辑 梁碧芬)

Integrated quay crane and internal truck scheduling in a container terminal considering internal truck energy consumption

YAN Nan-nan, YANG Ying

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

As environmental pollution and resource shortage intensifies, green port is becoming inevitable trend of port development in the future. Aiming quay crane and internal truck coordinated scheduling, a multi-objective mathematical model is established, considering internal truck energy consumption and quay crane together with internal truck work time. The work time of quay crane together with internal truck is related to the internal truck energy consumption, but there is a certain degree of conflict between these two objectives. Therefore, the method of multi-objective optimization is used to balance the two objectives. A genetic algorithm combined with Matlab mathematical software is to solve the mathematical model. Example results show that the cost of scheduling strategy considering the energy consumption of the internal truck is less than that of the scheduling strategy without taking the energy consumption of the internal truck into account, which validates the effectiveness of the model and the algorithm.

container terminal; integrated quay crane and internal truck scheduling; internal truck energy consumption; green port; Genetic algorithm; Matlab

2016-07-22；

2016-09-01

国家自然科学基金资助项目(71071093)

严南南(1968—)，女，湖北鄂州人，上海海事大学副教授，博士; E-mail：nnyan68@163.com。

严南南，杨莹.集装箱码头考虑集卡能耗的岸桥集卡协调调度[J].广西大学学报(自然科学版)，2016，41(6)：1949-1959.

10.13624/j.cnki.issn.1001-7445.2016.1949

TP301.6

A

1001-7445(2016)06-1949-11