基于二维布局分散度的两阶段箱位指派优化

于航，葛颖恩，乐美龙，檀财茂

（1.上海海事大学a.经济管理学院；b.经济交通运输学院；c.物流研究中心，上海201306；2.上海交通大学海科院海洋航运研究所，上海200231）

基于二维布局分散度的两阶段箱位指派优化

于航1a，葛颖恩*1b，乐美龙2，檀财茂1c

（1.上海海事大学a.经济管理学院；b.经济交通运输学院；c.物流研究中心，上海201306；2.上海交通大学海科院海洋航运研究所，上海200231）

集装箱码头的资源配置优化，是集装箱装卸作业组织的核心.作为集装箱堆场空间资源配置的重要优化指标，提出布局分散度的规划概念.以集装箱码头堆场的箱位指派问题为应用背景，为提高集装箱后续作业效率，分别从堆场布局层面和箱区箱位指派层面考虑多维度布局分散度的优化意义.建立第一阶段为仿真，第二阶段为混合整数二次规划(MIQP)的两阶段优化模型.结合实际码头生产数据进行算例实验，结果缓解了堆场拥堵情况并提高了码头集装箱装卸作业效率.同时，研究也揭示了布局分散度概念在堆场资源优化配置应用中的重要意义.

水路运输;布局分散度;两阶段优化;箱位指派;混合整数二次规划

1 引言

堆场的作业优化是集装箱码头企业精细化管理的重点.以往的集装箱堆场优化较多关注集装箱堆存策略的优化和堆场设备资源的优化配置.比如Taleb-Ibrahimi等[1]针对出口集装箱堆场的堆存策略进行建模研究，讨论了堆存策略可导致的翻箱情况.Zhang Liu[2]提出了进出口集装箱及转运集装箱同箱区的混堆策略，并用整数规划的方法分两阶段对集装箱的资源配置进行优化.并由王斌[3]建立了集装箱码头堆场的两阶段动态堆存策略，利用约束规划模型对前人箱量已知条件下的堆场资源配置策略进行改进.

近年Petering等[4]通过仿真技术针对存储箱区的长度及龙门吊的分散配置两个指标进行研究，考察了这两个指标对桥吊长期作业效率的影响，揭示了堆场资源分散配置对后续集装箱作业效率的关键影响.Chen等[5]针对出口集装箱箱位分配策略，分两阶段对到场船属集装箱进行了精确指派策略的探索.在前人的基础上进一步进行探索，并取得了一定的成果[6，7]，在现阶段的成果中发现，堆场船属集装箱的分散布局对整个堆场的运作效率有重大影响，然而当前堆场堆存优化研究领域缺乏相关的研究.因此，提出资源布局分散度的概念，并将其应用到集装箱堆场的布局优化中.

2 问题描述

2.1 布局分散度的定义及应用价值

将堆场一维布局分散度定义为船只靠泊后，其对应的堆场发箱点与作业点中心的直线距离测度.如图1所示.图中斜线部分的桥吊表示船只停靠的作业线位置，分散度标尺表示了该船只的布局分散度选择范围.在常见的码头作业工艺下，船舶靠泊后，船属集装箱在堆场的堆存位置直接关系着船舶开始作业后集装箱上桥作业的合理性，过度的聚集会导致堆场作业拥堵和工作量不均，过度的分散会导致集卡运输距离增加和桥吊作业等待.

图1 堆场布局分散度示意图Fig.1 The distribution dispersion in the yard template

在一维布局分散度的定义下，将二维箱区布局分散度定义为一维布局分散度对应垂直范围内的船属集装箱指派量.该变量影响了作业线对应的集装箱发箱点数量和堆场同种集装箱的聚集密度.进而决定了堆场箱区作业的拥挤程度，影响到桥吊的装船效率.一维及二维分散度的定义决定了船属集装箱后续作业时各设备间生产节拍配合的协调性，与码头后续的装船作业效率密切相关.

2.2 两阶段优化框架

通过仿真模拟与优化建模相结合的方法分两阶段对出口箱箱位指派策略进行优化.其中，第一阶段利用仿真方法对集装箱码头的装卸作业情况进行模拟，得到一维布局分散度策略下的船属集装箱装卸作业时间估计.进而将仿真结果作为集装箱箱位指派模型的约束参数估计，输入到第二阶段考虑箱区堆存布局分散度的箱位指派模型中，综合求出考虑布局分散度和堆场作业约束的集装箱箱位指派策略.两阶段箱位指派优化框架如图2所示.研究建立在以下的假设之上：

（1）船属的集装箱装卸数量是已知且不变的.班轮的集装箱装卸作业船图一般会在集装箱开始作业前拿到，虽然在实际的作业中有部分集装箱因为各种因素无法按计划信息作业，但这部分集装箱所占比重较小且对整体布局影响不大.

（2）不考虑堆场设备紧缺的限制.集装箱箱位指派策略将影响堆场设备的调度，进而决定装卸作业的效率.研究的重点是堆场箱位指派策略的优化，先于设备的调度，因此不考虑堆场设备资源限制对生产的影响.

图2 两阶段箱位指派优化框架Fig.2 The structure of the two-stage optimization for container assignment

3 第一阶段仿真模拟

3.1 仿真系统事件

针对码头装卸作业的特点，仿真主要划分为5类事件：

（1）Loading事件.

用来描述桥吊从集卡上卸载出口箱的动作，同时也包括了龙门吊向集卡上装载出口箱的动作.

（2）Unloading事件.

用来描述桥吊向集卡上卸载进口箱的动作，同时也包括了龙门吊从集卡上提取进口箱的动作.

（3）Dual-Loading事件.

用来描述桥吊装卸同步操作的动作，装卸同步工艺近几年在大型码头中的应用比例逐渐上升，该工艺要求桥吊在完成一个集卡的装载任务之后立刻为该集卡安排一个卸载箱的运输任务.

（4）Traveling事件.

用来描述集卡运输集装箱在堆场与其他设备间来往的动作.

（5）Waiting事件.

用来描述集卡等待桥吊和龙门吊前一动作完毕的动作.

3.2 仿真系统流程

第一阶段的集装箱装卸作业模拟系统流程如图3所示，主要对以下两点进行说明：

（1）在船舶装卸操作开始后，桥吊及龙门吊空闲时间所占比例较小.因此仿真不考虑集卡已经派出后，桥吊及龙门吊等待集卡的时间.等待时间以设备阻塞导致的集卡等待时间为主，其他设备等待时间仅考虑桥吊开始作业时作业线对应集卡池的配置时间.

（2）在第一阶段的仿真模拟中，研究将根据堆场箱区情况、作业泊位的分配及靠泊船只的装卸箱信息进行布局分散度所对应作业效率的仿真模拟.

4 第二阶段指派模型

（1）集合说明.

S={i|i=1,2,…,n}——作业船舶的集合；

D={j|j=1,2,…,n}——堆场对应的布局分散度值的集合，代表了堆场堆存范围的选择；

B={k|k=1,2,…,n}——堆场箱区的集合.

（2）参数说明.

Ck——k箱区的最大存量，k∈B;

Vk——k箱区的实际集装箱存量，k∈B;

Wi——i船的集装箱作业量，i∈S;

βi,j,k——i船在布局分散度为j时对应在箱区k的单位箱平均作业时间估计，i∈S,j∈D,k∈B;

αi,j——i船在布局分散度为j条件下的装卸作业完成时间估计，i∈S,j∈D;——α水平下i船在布局分散度为ji,j时对应的箱区k的箱位分配量估计值，i∈S,j∈D,k∈B;

Δt——箱区k的存量超过（小于）X'i,j,k时单位操作时间的惩罚（奖励）因子；

μ——箱区容积率，表示了集装箱存储所占箱区存量的比例；

M——极大正值常数.

（3）决策变量.

Xi,j,k——连续整形变量，表示i船以布局分散度j在箱区k的集装箱存量，i∈S,j∈D,k∈B; Yi,j∈{}

0,1——1代表i船以布局分散度j进行箱位指派，否则取0，i∈S,j∈D.

图3 第一阶段集装箱作业仿真系统流程Fig.3 The simulation process of the container handling in the first stage

（4）目标函数.

目标函数由两部分构成，第一部分基础函数可表示为

该部分函数表示集装箱在仿真估计作业时间下的系统整体作业时间.

第二部分函数表示为

αi,jYi,j代表了各船舶选择不同一维布局分散度策略的作业时间估计.因此对不同堆场一维布局分散度策略下的码头整体作业时间水平进行了描述.

综合可得到基本目标

对式（3）进行改进，考虑码头在具体箱区箱量指派中的第二维布局分散度策略，考虑仿真作业时间水平αi,j下i船在布局分散度为j时对应的箱区k的箱位分配量估计值对指派产生的影响.改进模型讨论了Xi,j,k与的关系.当≥0时，可令t表示由于装卸阻塞导致的单位作业时间增加.相反≤0时，可令[Δt表示由于作业流顺畅促进的箱区集装箱单位作业时间缩短幅度.进而可知代表了在仿真估计存储量基础上建立的箱区集装箱单位作业时间估计.综上可知代表了在堆场整体及箱区箱位指派两个维度考虑布局分散度策略的集装箱作业总时间估计.

改进的目标可表示为

式（5）代表了对变量Vk的约束，该变量代表了箱区实际的箱位指派情况.式（6）表示了Vk的值应小于箱区合理存储量μCk.式（7）保证了为船舶在各箱区指派的箱位与船舶的集装箱作业量相同.式（8）保证了船舶只能同时在一种堆场布局分散度策略下进行集装箱堆存.式（9）保证了船只分散度布局策略和箱位安排关系的平衡.式（10）和式（11）是对决策变量Xi,j,k和Yi,j∈{0,1}取值范围的约束.综合目标函数和约束条件可以看出，第二阶段的基本指派模型为典型的线性规划模型，改进的箱位指派模型为混合整数二次规划模型(MIQP).并通过ilog-cplex求解器尝试对模型进行求解.

5 算例实验

（1）第一阶段仿真模拟.

参考洋山深水港的实际作业数据进行算例实验，选取一期岸线中的4个深水泊位，2 000 m的岸线及6个前方堆存大区进行模拟.同时，从船期表中选取连续靠港的4艘船只进行装卸作业的仿真，已知数据信息和第一层仿真的参数设置如表1所示.

表1 已知数据及仿真参数设置Table 1The parameters used in the simulation and the model

研究利用Flexterm仿真平台对第一阶段码头装卸情况进行仿真，仿真模型如图4所示.

通过仿真模拟可以从第一阶段得到各船只在不同堆场分散度策略水平下的箱区平均作业时间和箱量指派估计值.组成每艘船作业时间估计和指派量估计的参数组合(βi,j,k,.本算例中i=1,2,3,4分别代表了展明，以星，聪河和三井四艘船.所得的参数矩阵(βi,j,通过仿真实验输出，如表2和表3所示.

图4 码头装卸作业仿真模型Fig.4 The simulation model of the upper level built in Flexterm

表2 1号和2号船的仿真输出参数矩阵Table 2The output parameters from the simulation of No.1 and No.2 ship（min，TEU）

表3 3号和4号船的仿真输出参数矩阵Table 3The output parameters from the simulation of No.3 and No.4 ship（min，TEU）

除此以外，不同布局分散度水平下船舶整体作业时间水平αi,j输出汇总如表4所示.

表4 四艘船舶的整体作业完成时间估计Table 4The estimation of total handling time of all four ships

（2）第二阶段箱位指派求解.

把上述由第一阶段仿真得到的参数估计值输入第二阶段模型，在Intel(R)Core(TM)i7-3537U CPU@2.00GHz处理器的支持下，利用ilog-cplex对第二阶段的线性规划及混合整数二次规划模型进行求解，其中基础目标值求得为12 721.混合整数二次规划模型通过8 772 s的求解，在MIP相对容差0.01%的条件下求得了最优目标值11085.

6 结果分析

通过对基本目标和改进目标的求解可以得到两种分配方案.结果如表5所示.其中第二种方案考虑了在堆存范围和箱区两个维度上考虑了布局分散度的优化意义，结果如表6所示.

表5 基本求解结果Table 5The solution of the basic problem

表6 改进求解结果Table 6The solution of the improved problem

表5和表6中分散度值代表了堆场布局层面的布局分散度最优值，该值反映了箱位指派时的船属箱区指派范围，是第一维的布局分散度指标. Xi,j,k值反映了集装箱在第一阶段堆场布局分散度范围约束下的具体箱区布局分散度策略，是第二维的布局分散度指标.通过上述结果，可以看出在堆场和箱区两个层面均考虑布局分散度策略的箱位指派优化方案，优于仅考虑堆场布局分散度的箱位指派方案.在整体作业时间上，由于改进方案缓解了箱区因过度堆存相同作业线集装箱导致的作业压力，整体作业时间缩短明显.通过改进的指派方案，箱区内的集装箱布局分散度得到优化，基本指派方案和改进指派方案在各箱区的堆存情况汇总如图5和图6所示.

图5 基本的指派方案Fig.5 The basic assignment method

图6 改进的指派方案Fig.6 The improved assignment method

通过图5和图6可以看出，基本指派方案使船属同一作业线下的集装箱分配较集中，造成箱区作业压力增大，阻塞增强，进而导致作业时间增长.改进后的指派策略有效地分散了同一作业线下集装箱的堆场分布情况，缓解了船属同一作业线下集装箱的作业压力，从而减少阻塞，促进总体作业时间的缩短.结合表6可以看出，下划线标记的箱区箱量指派较其他箱区分配量明显增大，箱量分配的增大均发生在距船舶泊位较远的1号和6号箱区.结合第一阶段的仿真模型可以看出，这种现象是因集装箱会先在距离船舶较近的位置进行堆存导致的，即首先在2，3，4，5号箱区进行堆存.当这些箱区存满后，再在边缘箱区进行存储.在制定二维布局分散度策略的时候，研究考虑了边缘箱区堆存对整体策略选择的影响，给出以布局分散度为主要规划指标的堆场最优布局方案如表7所示.

根据所给策略，船舶应在一维布局分散度约束的箱区范围内，按照二维布局分散度的箱量进行各箱区的箱位指派.在两个维度均考虑布局分散度策略的箱位分配策略，使得箱区内不同作业线的集装箱实现了错峰作业，减少了同一作业线集装箱作业时阻塞情况的出现.也为堆场箱区箱位调度和移箱管理提供了更大的调整空间.

表7 布局分散度参考Table 7The distribution dispersion result in different dimension

7 研究结论

本文的创新和关注重点是从布局分散度的角度对传统的船属集装箱分配问题进行优化.建立了仿真和建模相结合的两阶段箱位优化配置方法.以集装箱码头箱位分配问题为应用背景，揭示了布局分散度对生产作业整体优化的重要意义.未来研究应着力将基于布局分散度的资源优化方法理论化，进一步的挖掘布局分散度在不同生产制造领域的应用意义.

[1]Taleb-Ibrahimi M,B de Castilho,C F Daganzo.Storage space vs handling work in container terminals[J]. Transportation Research Part B:Methodological,1993. 27(1):13-32.

[2]Zhang C,J Liu,Y-w Wan,et al.Storage space allocation in container terminals[J].Transportation Research Part B:Methodological,2003.37(10):883-903.

[3]王斌.集装箱码头堆场的一种动态随机堆存方法[J].系统工程理论与实践,2007,27(4):147-153.[WANG B.Dynamic and stochastic storage model in a container yard[J].Journal of Systems Science and Information, 2007.27(4):147-153.]

[4]Petering M E,K G Murty.Effect of block length and yard crane deployment systems on overall performance at a seaport container transshipment terminal[J].Computers &Operations Research,2009,36(5):1711-1725.

[5]Chen L,Z Lu.The storage location assignment problem for outbound containers in a maritime terminal[J]. International Journal of Production Economics,2012, 135(1):73-80.

[6]Le M,H Yu.The RHSA strategy for the allocation of outboundcontainersbasedonthehybridgenetic algorithm[J].Journal of Marine Science and Application, 2013,12(3):344-350.

[7]乐美龙，于航.考虑箱区利用率的出口箱资源配置启发式算法[J].计算机工程与应用,2013,49(8):231-235.[LE M L,YU H.A heuristic algorithm for outbound container allocation considering the different utilization betweenblocks[J].ComputerEngineeringand Applications,2013,49(8):231-235.]

Two-stage Optimization of Container Assignment Based on Distribution Dispersion

YU Hang1a,GE Yin-gen1b,LE Mei-long2,TAN Cai-mao1c
(1a.School of Economics&Management;1b.College of Transport and Communication;1c.Logistics Research Center, Shanghai Maritime University,Shanghai 201306,China;2.Ocean&Shipping Institute,Shanghai Jiaotong University,Shanghai 200231,China)

The optimization of resource scheduling for the container terminal is the key point of container handling.A new index called the distribution dispersion as the indicator of the optimization for the space scheduling of the production resources is touched,which is related to the container assignment model in the container terminal to improve the efficiency of the following works.The distribution dispersion is discussed both in the yard template scheduling and the block assignment in different dimensions.A two-stage optimization model which the first is a simulation model of the operations and the second stage is a mixed integer quadratic programming(MIQP)model is built to find the best assignment solution.A series of real production data are used to carry out the two-stage optimization.An improvement of the handling and ease of the congestion are shown from the result.The profound meanings of the distribution dispersion are obvious in the scheduling of the resource from our research.

waterwaytransportation;distributiondispersion;two-stageoptimization;container assignment;mixed integer quadratic programming

1009-6744（2015）05-0223-08

U691.3

A

2015-04-24

2015-06-25录用日期：2015-07-06

国家自然科学基金项目（51409157，61304203）；上海市自然科学基金(12ZR1444800)；上海海事大学优秀博士学位论文培育项目（2015BXLP003）；上海市自然科学基金创新行动计划项目(10190502500).

于航(1989-)，男，江苏徐州人，博士生. ＊

yege@shmtu.edu.cn