预倒出口箱区的多场桥调度优化

郑红星，王 杰，姚 琳

(大连海事大学 交通运输工程学院，辽宁 大连 116026)

0 引言

在集装箱码头中，出口集装箱堆场的作业效率直接影响整个码头的服务水平，研究该类堆场的效率改进策略是当前集装箱港口关注的核心问题之一。为此，很多码头常常在出口集装箱堆场中进行预翻作业，以减少场桥在堆场中由于翻箱作业带来的额外耗时。因此，在预倒过程中如何科学有效地安排场桥预倒作业，进而提高装船效率，是出口箱堆场研究的热点问题。

目前，针对堆场场桥调度问题，国内外已有很多学者进行了深入细致的研究。鉴于场桥作业时间因素直接影响场桥作业效率，本文将已有文献按处理时间因素的方法不同，分为以下三类：A类——不考虑场桥抓箱时间，只考虑场桥在作业过程中行走路径的时长；B类——确定翻箱次序，场桥抓取目标箱的时长等于单独提该箱的时间加上其翻箱时间；C类——根据经验翻箱，在船舶装载时按照船舶配积载图进行翻箱工作。

在A类文献中，李丽丽[1]针对现场场桥调度问题，考虑利用最短路径和动态规划求解现场场桥调度，提出了一种组合路径优化算法，建立了场桥部署优化模型，给出了基于遗传算法的求解过程。Chang等[2]研究了单个箱区内的双场桥调度问题，以场桥延迟任务数最小化为目标，建立了整数规划模型， 并设计了基于滚动时域的启发式算法。刘新[3]针对集装箱码头在不同时段的运行量，每个箱段内实时分配现场场桥问题。考虑到船舶在码头最前端的装卸作业中岸桥和堆场的工作量的平衡，以减少岸桥的等待时间优化现场桥资源配置为目标，建立场桥的多目标整数规划模型，并且计算场桥运行时间的变化和最小运行完成时间。周文杰[4]研究了任务序列下的场桥路径优化问题，考虑每个子任务和后续操作中的场桥的五个子任务，选择具有最小移动距离的贝位号，采用动态规划方法建立模型并在完成所有任务后确定场桥的贝位号顺序。韩晓龙等[5]结合装载方案研究了场桥调度优化问题，以场桥行走路径最短为目标，建立了现场桥梁调度模型。李淑娟等[6]研究了场桥作业与集卡衔接优化问题，目标使场桥和集卡之间的等待时间最短，场桥和场桥之间??的距离最短，并根据模型的特点设计了模拟退火算法。范厚明等[7]研究了出口箱箱位分配和场桥调度的分区域平衡问题，考虑了场桥间相互干涉的现实约束， 建立了现场场桥的非加载时间优化模型，平衡了每个场桥的工作量。

在B类文献中，郑红星等[8]研究了混堆箱区某一时段内的多场桥调度问题，考虑了内外集卡的场桥间不可跨越和保持安全距离、优先级等因素，构建了多场桥调度模型，同时设计了混合遗传算法用于求解，文中各目标箱的提取操作时间不尽相同。郑红星等[9]研究了箱区运营成本优化问题，以最大限度地降低可变运营成本为目标，构建了混合模式下多箱和场桥联合调度的非线性数学规划模型并设计了算法求解。张笑菊等[10]针对混堆堆场的集装箱码头装船顺序优化问题，考虑船舶一个贝位的同步装卸作业，以单台场桥在单个箱区内移动时间和翻箱时间最小为目标，构建了出口集装箱装船顺序优化模型并设计了启发式算法。范厚明等[11]研究了出口箱区场桥营运成本优化问题，考虑场桥作业量均衡和场桥间安全距离，以场桥移动成本和空闲成本之和等可变营运成本最小为目标，建立集装箱堆场箱位重分配及多场桥调度联合优化模型，设计了模拟退火遗传算法，并对箱区内不同规模的出口量进行了实验分析。郭文文等[12]研究了出口箱装船顺序及场桥行驶路径联合优化问题。以作业时间衡量装船顺序产生的倒箱量及场桥行驶路径,构建了以作业时间最短为目标的整数规划模型,设计均衡倒箱量和场桥作业时间的启发式算法对模型进行求解。高鹏等[13]研究了集装箱堆场提箱作业优化问题，在分析倒箱移动路径的基础上，通过倒箱搬运过程的优化使总作业成本最小，提出了提箱作业优化模型，并且设计了算法求解。冯媛君等[14]研究了集装箱码头堆场翻箱与外集卡提箱顺序同步优化问题，以码头的作业成本和外集卡的延误成本之和最小为目标，建立堆场翻箱与外集卡提箱顺序同步优化模型，优化外集卡的提箱顺序、龙门吊的任务分配以及翻箱方案。设计了基于动态规划的启发式算法求解模型，并利用算例对模型与算法的有效性进行了验证。

在C类文献中，邵乾虔[15]为解决集卡预约模式的问题，首先提出了 “动态优先行李箱概率” 的定义并给出了其推导过程； 在此基础上以行李箱积存最少为目标，构建了行李箱路径的动态优化模型，开发了动态行李箱启发式算法。邵乾虔等[16]针对出口箱预翻箱问题，结合出口箱堆场作业时间，建立了以最小化预翻箱量和场桥堆存作业移动距离为目标的数学模型，并给出了求解算法。王伟[17]研究多场桥调度优化问题，考虑到箱间隔中场桥过渡的问题和反向箱因子的影响，以最小化内置卡与惩罚因子的时间偏差为目标，构造了一种非线性规划模型，并设计了算法求解。初良勇等[18]研究集装箱码头调度问题，据典型集装箱的实际数据，以码头调度效率最高为目标，设计并验证了基于遗传算法的模型求解策略。董小妹等[19]研究了集装箱翻箱优化问题，以贝位利用率最大为目标，建立了集装箱堆场异贝之间翻箱问题的数学模型，并选择采用杂合启发式算法构造算法求解流程，寻求满意解。

综上，国内外对多场桥调度的文献中，A类文献最多，而B类研究次之，C类文献最少；但近年来C类文献逐年增多，是当前相关研究的焦点之一。就研究方法而言，A类文献以考虑场桥在作业过程中行走路径时长最短为优化目标，并设计相应的启发式算法求解；但考虑经验翻箱影响的文献较少，很多都未提及作业场桥的具体任务序列；而在实际装船作业中，由于出口堆场箱区中压箱的实际限制，且提箱需按照固定次序，多场桥协调工作时可能需在作业过程中翻箱，故翻箱的耗时对装船的效率影响很大，很少有文献在研究场桥调度时集成考虑该因素。B类文献在考虑经验倒箱的前提下，当船舶装载时按照配积载图进行倒箱工作，一般以倒箱操作时间最短为优化总目标构建数学模型，并设计启发式算法求解，但大多数文献仅仅考虑单台场桥的作业，研究多场桥调度的文献较少。C类文献不考虑场桥抓箱时间，只以场桥在作业过程中行走路径最短为优化目标来确定倒箱次序，并设计启发式算法进行求解，但大多数忽略了操作过程中的翻箱作业时间与场桥抓箱时间。因此，本文以一初始出口集装箱箱区为研究对象，为减少装船时必需翻箱的耗时，在获知配载图后，研究如何调度多台场桥将待装船的集装箱预倒至一空闲箱区效率最高，兼顾作业过程中的翻箱和落位。

另经烟台港、大连港和天津港等地的实际调研，为安全起见，堆场翻箱一般遵循如下经验规则，即：

(1)在不压下一个待提箱的前提下，必翻箱应先放至该贝位层高最低的箱位；

(2)若该贝位最低层高不唯一，优先向排数最高的箱位翻倒，即6排>5排>…>1排；

(3)若所提目标箱位为满垛3层高(所有排都放满三层)，则不向第1排和目标箱位指令相邻的排翻倒。

区别已有文献，本文研究的问题具有以下显著特点：(1)考虑翻箱经验规则对多场桥调度的影响；(2)深入场桥调度细节，即不仅给出每台场桥在各时间窗服务的总时长，并给出对应的具体作业贝位。(3)梳理场桥分配、目标箱优先级和场桥调度之间的反馈关系，进而构建相应的线性规划模型，并设计了分支定价算法进行求解。

1 问题与模型

1.1 问题描述

在集装箱码头装船作业中，由于出口集装箱的初始堆垛次序与船舶装载的次序不同，且很多港口一般采用船到即卸装的作业方式，因此常常导致大量的翻箱作业，在很大程度上影响了码头的装船效率。为此，堆场时常会选择在适当的时机对出口箱区进行预倒，即将待出口箱提前倒至一空闲箱区，该箱区的堆垛方式为船舶配载图的倒序；但由于码头作业繁忙，预倒箱区的作业效率至关重要。基于此，针对某一初始出口箱区，如何在最短的作业时间内完成待装船箱的预倒作业，是提高码头装船效率的有效手段。

在码头预倒箱作业中，初始出口箱堆场的场桥调度计划至关重要，其既要保证预倒箱作业的快速高效，又要确保场桥作业过程中的安全。为此，在预倒箱作业过程中，为确保未来装船时不再翻箱，需按固定的提箱次序将待装船的集装箱倒至另一箱区，既要使作业场桥行走的路径最短，又要严格遵循经验翻箱规则。

对于箱区中的次目标箱即压箱的最终位置状态，本文不予考虑。因为本文以场桥作业总行走时间最小为优化目标建立模型，只要翻箱作业满足经验规则，场桥行走时间就只与次目标箱的个数呈正相关，具有比例关系。综上本文不予考虑。

因此，本文问题可描述为：在固定的计划期内，某出口箱堆场箱区提箱的配载计划已知，将待提箱提前翻倒至一空闲箱区，使其装船前以船舶配载图的倒序堆垛。考虑两台场桥同时作业过程中始终保持一定的距离并且不得交叉作业的现实约束，在满足作业过程中多场桥调度需遵循经验翻箱规则，确定场桥作业过程中的贝位号序列和在相对应贝位上所需要提取的目标箱时间以及所需提取的目标箱，目标是使场桥在完成所有任务时总的行走时间最短。本文将需要进行调度的集装箱称为目标箱，其中，待提箱称为主目标箱，将主目标箱上的压箱称为该箱的次目标箱。

以某箱区为例，其贝位展开图如图1示：

图1 贝位展开图

已知局部船舶配载图如下所示。

图2 船舶配载图侧视图

图3 船舶配载图

经倒箱后翻倒至一空闲箱区，使其装船前以船舶配载图的倒序堆垛，如下所示：

图4 装船前堆垛图

1.2 模型假设

基于上述的问题描述及特征分析，下面将建立问题的整数规划模型，模型满足如下假设条件。

假设1贝位1为场桥1的始发节点，贝位9为场桥2始发节点。场桥可选择任意1条从始发节点到终到节点的可达路径，包括重复路线路径以及翻箱作业路径。

假设2两台场桥同时作业时场桥间不可跨越且保持一定安全距离，假设作业安全距离3贝。

假设3场桥在进行抓箱，移动等操作时，间隔时间紧邻，无空余。

1.3 数学模型构建

常量说明:Q为可直接提箱的所有目标箱的集合；Nh为第h个需要翻箱的所有节点的集合；Wj为j箱的作业时间；F为所有节点集合；P为场桥节点集合；R为子目标箱节点集合；R′为主目标箱节点集合；FZ为虚拟终点集合；m为场桥数；L为需要翻箱的个数；n为目标箱总数；Sij为场桥间安全距离；Dt为场桥间行走距离D所用的时间；M为充分大整数；M0为移动速度；Nhv为第h个需要翻箱的第v个节点集合；Dhv为第h个需要翻箱的第v个节点集合所对应到达边数。

状态变量说明:Pwi表示i箱所在贝位，不为箱节点则为0；Ri表示第i号节点若为主目标箱则取1，否则为0；Fti表示i箱对应场桥就绪时刻，若为非主目标箱则为M；LTik表示第k号场桥作业i箱的完成时间，若不为箱节点则取非负；Xijk表示若k号场桥由节点i移至节点j则取1，否则取0；Cijkk′表示若LTik′>LTik成立则其值取1，否则取0；Eijkk′表示若场桥k′作业i箱，同时k作业j箱发生冲突，则其值取1，否则取0；Gijkk′表示若场桥k’作业i箱，同时k作业j箱发生冲突，不足安全距离，则其值取1，否则取0；Pijkk′表示若场桥k’作业i箱，同时k作业j箱发生冲突，若k’优先于k，则其值取1，否则取0；Bhv表示若第h个需要翻箱的第v个节点集合被遍历，则其值取1，否则取0；xij表示若从节点i到节点j路线被占用则其值取1，否则取0。

决策变量说明:TTi为i箱对应场桥在各时间窗服务的总时长。

采用上述定义的参数和变量，问题的整数规划模型可如下表示：

目标函数：

约束条件：

LTik≥Sij×Xijk+LTik-(1-Xijk)×Wj

(1)

(2)

Xijk=0,i∈F;k∈P

(3)

(4)

(5)

(6)

(7)

(8)

j∈Dhv,h∈L,v∈Q,i∈R,k∈P

(9)

(10)

(11)

(12)

(13)

i,j∈R,k,k′∈P

(14)

u,i,j∈R,k,k′∈P

(15)

Pwi

M+(1-Eijkk′)×M,i,j∈F,k,k′∈P

(16)

Pwi>Pwj+D-Gijkk′×M-(1-Eijkk′)×M,i,j∈F,k,k′∈P

(17)

LTik>LTik′+Wj-Cijkk′×M-Eijkk′×M,i,j∈F,k,k′∈P

(18)

LTik′=LTik-Wj-Cijkk′×

M-(1-Eijkk′)×M,i,j∈F,k,k′∈P

(19)

LTik>LTik′-Cijkk′×M,i,j∈F,k,k′∈P

(20)

LTik′=LTik-Wj-Cijkk′×M-Eijkk′×M,i,j∈F,k,k′∈P

(21)

LTik>LTik′-Wi+Wj-(1-Pijkk′)×

M-(1-Gijkk′)×M,i,j∈F,k,k′∈P

(22)

LTik

M+(1-Gijkk′)×M,i,j∈F,k,k′∈P

(23)

(24)

TTi≥0,FTi≥0,i∈F

(25)

其中：目标函数为场桥在完成任务时总的行走时间，包含装载时间与翻箱时间；公式(1)～(3)使得场桥对目标箱的提箱作业在对应集卡就绪后进行，同时保证各台场桥依次顺序作业各目标箱的完成时刻大小关系；公式(4)～(6)满足需要翻箱的贝位所有的主目标箱全部被场桥作业至少一次；公式(7)～(10)满足需要倒箱的贝位所有的次目标箱全部被场桥作业至少一次；公式(11)～(13)满足各个场桥均以其对应的场桥节点为起点；公式(14)～(15)满足各栈位的目标箱通过场桥从上至下依次完成作业；公式(16)～(23)保证各场桥间不发生冲突，并且场桥之间不能跨越，提箱次序固定；公式(24)为目标函数的运算公式；公式(25)保证变量的取值范围。

2 求解算法

以上述大型码头堆场为例，考虑码头对场内有16个贝位，共有2个场桥对堆场内集装箱进行操作。其中场桥堆场基本信息如下：跨距 6 栈，堆垛高度 5 层，移动时间 0.1 分/贝，装载任务 3 分，倒箱需 2 分。21个目标箱，其中11个集装箱存在压箱现象。因此，该模型包括约2000个0-1变量，25000个约束，是一个大规模整数规划模型，很难在有效的时间内直接求得最优解甚至可行解。因此，需要在研究问题结构特征的基础上，设计更加高效的求解算法。

本文采用状态参量标记目标箱，即在所有图中，目标箱i都有各自的状态，文中设为(S，G，T，i)，各个元素矢量的解释如下：

S为路径元素：用来记录场桥访问过的子路径的顶点集合。S={0,S1,S2,Si,…,SN,d},0与d为目标箱所在的位置与其堆场，路径矢量为m+2位，为0-1变量；其中，若Sn为1时，表示此路径被访问过，否则为0。

G为所提箱型，所提箱分为主目标箱与次目标箱两种类型,每种箱型有3个优先级。

T为总时间：用于记录所提箱的总时长，即定价子问题的目标函数值。

i表示目标箱：作为目标箱的标签由于标记目标箱。

针对上文的模型进行分析，发现约束(1)～(13)与约束(14)～(23)完全无关，因此该模型可视为一个线性规划问题。由于多场桥可选路径数量是非常巨大的，无法一一枚举，因此采用分支定价算法定价生成新的线性子问题，并依次求解，包含的资源约束主要是场桥的位置约束。

2.1 分支定价算法求解

本文通过Danzig-Wolfe分解原理(以下称为“D-W分解原理”),把这两种约束分解开，即利用凸组合定理把原来的问题转化为主规划问题(以下称为“MP问题”),和若干个子问题。

通过运用D-W分解原理，可将原问题转变为原问题的MP问题。在目标函数已知,且上述函数的总时长与等待时长呈正相关性的情况下，满载、翻箱时间自可知；最终时长与场桥等待时间有直接关系，并由场桥等待时间决定。因此，由目标函数

MinimizeΣi∈R′TTi

(26)

依下列规则进行转化。

规则为将模型转变为集划分模型后，采用列生成法求解。采用以下规则进行剪枝，即表示一个顶点自然状态的标签时刻都在变化，其内部的每一个元素都将发生变化，只有所有状态满足所有的约束均最优，才可视为有效的标签并保留，否则将其删除。

例如针对同一个目标箱，其状态时时发生变化，可能同时多个状态满足上述约束，如(S,G,T,i)，(S′,G′,T′,i)等；因此，本文规定：若条件(1)S≤S′，(2)T≤T′两个条件同时成立且至少一个严格满足，则认为状态(S,G,T,i)优化于状态(S′,G′,T′,i)，删除状态(S′,G′,T′,i)；若存在多种状态，则进行多次比较，直至找出最优的一个状态代入树节点。

定义如下参数：

可得到新的子约束如下:

(27)

xij=Σt∈Txijt×Ut,∀i,j∈F

(28)

(29)

将公式(27)带入公式(28)可得:

xij=Σt∈Txijt×Ut=Σt∈TΣk∈Pxijt×Ut

(30)

TTi=xij×(Dt+Bj)

(31)

将公式(30)带入公式(31)可得:

Σi∈R′TTi=Σi∈R′xij×(Dt+Bj)

=Σi,j∈R′(Dt+Bj)×

(32)

再定义Qt=Σt∈TΣk∈P(Dt+Bj)×xijt并代入公式(32)可得:

ΣΣi,j∈F(Dt+Bj)×xijt

=Σt∈TΣk∈PQt×xijt=Σt∈TQt×Ut

(33)

至此原问题完全转化为MP问题。

(34)

令∂it=Σj∈Fxijt，代入公式(34)可得:

(35)

最终原问题的MP问题如下:

minΣt∈TQt×Ut

(36)

s.t.Σt∈T∂it×Ut=1,∀i∈F

(37)

(38)

(39)

其定价子问题的约束实为对场桥行走路径的约束，可通过其约束求等待时间。定义(36)参数如下：定义yi为目标箱i的路径标记，若目标箱i被此路径使用则为1，否则为0；C为此场桥所对应的检验数；λ1为公式(37)的对偶变量；λ2为公式(38)的对偶变量，则:c=Σi∈FTTi-Σi∈Fλiyi-λ0求解(36)最小值问题时，需找出其定价子问题检验数(c)为负的列，依次代入原问题，并将这些检验数为负的列一一加入其主问题模型，且作为树节点加入，反复添加，直至所有的检验数小于0为止。最终得到如下函数:

minc=Σi∈FTi-Σi∈Fλiyi-λ0

(40)

s.t.Σj∈Fxij=yi,∀i∈F

(41)

Σj∈Fxji=yj,∀i∈F

(42)

Σj∈Fxij=1,∀i∈F

(43)

Σj∈Fxj0=1

(44)

xij∈{0,1},∀i,j∈P,i≠j

(45)

yi∈{0,1},∀∈P

(46)

目标函数(40)表示为原问题目标所求得的检验数最小的列，其定价子问题为许多个结构基本相同，参数基变量有所区别的定价子问题所组成的。

为满足经验翻箱规则，将以下目标规划函数并入原问题中作为目标约束：

Ghl表示某个贝位中的目标箱，h表示其层数，l表示其排数，h′，l′表示变更后的层数排数，若此层此排存在箱子，则Ghl=1， 见如下目标函数作为约束并入原问题:

(47)

(48)

l′≠l-1,h,l≤3,h,l∈P

(49)

其中(48)满足在不压下一个目标箱的前提下，翻倒指令应先放至该贝位层高最低的箱位；若该贝位最低层高不唯一，优先向排数最高的箱位翻到，即6排>5排>…>1排；

其中(49)满足若所提目标箱位为满垛3层高(所有排都放满三层)，则不向第1排和目标箱位指令相邻的排翻倒。

2.2 上下界的选取

本文设计贪婪算法确定上界，将所有提箱，倒箱时间依次进行排序，优先选择时间较短的作业；若时间相同，则选择相隔贝位较远的作业，将所有目标箱提出后的时间总和作为上界。

本文设计近似衡量算法确定下界，考虑主目标箱均可在集卡就绪后直接进行提箱作业(不考虑压箱)。将解空间进行放大，保证同贝同栈情况被合理转化，并且转化后作业全部箱所需的总时间变少或不变，求得时间总和即为下界。

下界的解空间是原问题解空间的子集，使得下界最优值必位于原问题最优解之下或与之相同；同贝同栈情况下，适当原问题减少约束条件，保证转化后作业全部箱所需的总时间变少或不变，因此本文给出的下界一定是原问题下界。

2.3 算法流程

分支定价法外部是分支定界法，内部是列生成法，把大型的线性规划问题分解为MP问题，再求解有范围的MP问题(称为“RMP问题”)。通过求解RMP问题产生的新的子列，进而求解大型的线性规划问题以下列出了分支定价法的流程：

Step1初始化搜索树，加入根节点，在计算过程中选取根节点用此根节点的信息对RMP问题进行初始化，然后通过列生成法解决RMP问题得到对偶变量，转到step1。

Step2根据对偶变量解决定价子问题，检查检验数是否小于0，如果是，则重新选择新的节点并删去此节点，否则，再检查RMP问题的解是否为整数如果为整数，转到step2。

Step3把RMP问题的解与上界对比若比上界小则更新上界，并进行剪枝操作，否则进行分支并把当前节点从搜索树中删去，把子节点加入搜索树，转到step3。

Step4再检验搜索树是否为空，如果为空，则结束，如果不为空，则在搜索树上选取节点，重新操作，回到step1。

具体步骤图如下所示：

图5 算法步骤

3 算例分析

3.1 方案求解

在出口箱堆场某箱区中，已知计划期内(据天津港等地的实地调查数据可知，场桥作业计划约1h滚动一次，故本文取计划期为1h)。结合港口实地调查数据以及适应度评价公式的特点，本文所有的实验都运行在3.10GHz Intel Core 2 CPU和4GB内存的双核计算机上，采用Python 3.6.5进行编码。经计算本文所运用的分支定价算法结果如表1所示：

表1 实验结果

场桥路径为：场桥1:贝位5→贝位1→贝位5→贝位2→贝位8→贝位3→贝位4→贝位7→贝位4→贝位5

场桥2:贝位12→贝位9→贝位10→贝位11→贝位12→贝位13→贝位16→贝位15→贝位14

最终总等待时长为74分钟

3.2 方案对比

为验证本文方法得到场桥作业方案的有效性，分别同采用先到先服务方案和不考虑实时预翻箱的文献[9]中方案进行对比分析，如表2所示。可以看出，FCFS方案的目标值最大，场桥作业总等待时间最长；不考虑实时预翻箱的RHA方案效果居中，较FCFS方案好，但是改进有限；本文给出的分支定价方案效果最好，总等待时间较RHA方案降低10.4%。

表2 方案对比

分支定价算法求解中规模算例的实验结果：

表3 方案评价

本文加大问题规模以证明算法的可行性。将贝位数加大分别为16、20、24、28个，将场桥数分别增加为2、3、4、5个，求得实验结果并观察运算速度如表3所示。

随着问题规模的加大，分支节点增多，计算时间也有所增加。主要由于大规模的算例限制主问题和价格子问题的规模也变大，因而更难求解。

不同压箱量的算例实验如表4所示：

表4 实验评价

从表4可以看出，在10个算例中，目标函数值和求解耗时都随着压箱量的增加而增加，且对于总时间的影响因素较大。目标值于压箱量从32到34时有一个突增点，这是由于在压箱量为34时，随着主目标箱及提箱时刻分布的不同，场桥的运作超过极限，全部处于忙碌状态。而求解耗时增加较为平缓，表明算法求解时间相对稳定，没有随压箱量的增加而成指数型增长。

单贝位压箱量对实验结果的影响如表5所示：

表5 实验评价

从表5可以看出，单贝位的压箱数的增加对于总时间影响因素较小；在压箱数为4时突增，这是由于目标箱压于最底层，翻箱次数较多引起的。

4 结语

(1)针对预翻出口箱区的多场桥调度优化问题，构建了以场桥作业总行走时间最小为优化目标的线性规划模型，以实施预翻作业的某一出口箱区为研究对象，在待提箱作业次序已知的前提下，考虑作业场桥间保持安全距离且不可跨越，以及满足翻箱经验规则等现实约束，侧重作业过程中实时翻箱，揭示了多场桥调度优化对堆场翻倒操作系统作业效率的巨大影响，有助于缩短预倒作业时间，进而提高装船效率。

(2)针对模型规模较大的特点，设计了分支定价算法进行求解：首先利用列生成法和D-W分解原理通过剪枝来获得满足约束条件的节点，然后将原问题转变为等价的主问题和若干子问题，最后采用贪婪算法与近似衡量算法确定上下界；相较于其它文献的启发式算法，该算法在时间上有较大的优势，且其改进策略具有较强的适用性，可为其他类似问题的求解提供参考。

(3)算例实验结果表明，随着贝位数的增多，调度的总时间呈正增长趋势；随着场桥数的增多，调度的总时呈负增长趋势，但下降趋势较慢；随着压箱数量的增加，调度总时间明显增加，且上升趋势较快，目标箱均在最底层时，时间最长；贝位分布越紧密，增加场桥数可明显提高效率，但场桥数量不宜超过3台。因此，在码头堆场实际作业中，为更有效的进行预倒箱作业，可在集港时尽量将等待装载到一艘船的集装箱集中放置，尽可能避免将其堆放于底层，且每个待预倒箱区配置2～3台场桥为宜。

在未来的研究中，本算法可用于研究内集卡、场桥和岸桥集成调度的实时预翻箱优化问题。