英文论文翻译-关于集装箱转运中心集卡调度算法

1、关于集装箱转运中心集卡的调度算法作者：Loo Hay Lee·Ek Peng Chew·Kok Choon Tan·Yuan Wang摘要：本文在考虑岸桥、场桥的作业能力情况下，解决了集装箱转运中心集卡的调度问题.本文的目标是使岸边作业完成时间最小化.这个问题对于那些能够通过信息技术充分利用数据做出科学决策的港口尤其重要.本文提出一个混合整数规划模型来解决该问题.现有的解决方案不能在合理的时间内解决混合整数规划模型，因此，本文提出了两个启发式算法来解决该问题.第一个方法是基于邻域搜索的网络模型，第二个是基于遗传算法和最小成本流的网络模型.不像通常用任务序列代表染色

2、体的传统遗传算法，本文使用任务的开始时间代表染色体，最小成本流模型用于解码染色体并且决定集卡的工作序列.本实验结果显示了基于最小成本流的遗传算法优于邻域搜索算法.关键词：转运·集卡调度·完工时间·遗传算法1介绍 海上运输一直是支持全球贸易的主心骨，因为80%的国际贸易都是通过海上进行运输.随着世界贸易的不断增长，主要港口之间的竞争也越来越激烈.因此，对港口操作者来说，选择不同的决策工具和优化算法来提高港口的效益和增加其竞争力是非常必要的. 典型的集装箱港口主要资源有岸边起重机（简称岸桥）、堆场起重机（简称场桥）、集装箱卡车（简称集卡），为了提高码头的生产效率，在码

3、头内协调分配给这些设备的任务，保证集装箱流的无缝衔接是非常必要的. 当船舶到达港口时，岸桥将进口和转运的集装箱从船上卸到集卡上，通过集卡将它们运到堆场相应的堆放位置.在堆场方面，场桥将这些集装箱从集卡上卸下到指定的对方位置.从堆场向船上装载进口和转运集装箱的过程与上述过程类似.码头前沿和堆场之间的运输对码头的生产效率起很决定性作用，因为当集卡没有准时到达或者到的太早引起交通拥挤，会导致岸桥或场桥操作延迟.实际上，因交通拥挤、交通延迟、设备故障和其他港口动态不确定性导致各种设备之间在操作方面协调的复杂性，使得优化这类调度问题变得充满挑战性.因此，需要一个信息技术平台收集操作上的实时信息，然后决策

4、支持系统能够充分利用这些信息，进而提供快速、智能的方案来指导港口内集卡的调度及路径规划.本文旨在通过为集卡调度设计算法来提高转运中心码头前沿港口操作效率，以此解决上述问题. 在过去，多数研究集中在改进集卡的时间表.有许多文章研究自动港口无人搬运车（AGV）调度问题.Meersmans 和Wagelmans（2001a，b）对于AGV和起重机选址问题设计了定向搜索算法.Bose等人（2002）使用基于任务或基于集卡的方法找到初始解决方案，同时，利用进化算法进行改善.Van der Meer（2000）研究了集装箱自动码头中自动搬运车的控制.Hartmann（2004）为港口各类操作设备的调度和人

5、力资源设计了遗传算法.Grunow等（2004）研究了多负载自动搬运车调度问题，为在线物流控制系统设计了灵活性优先的方法，利用混合整数线性规划模型对在线策略进行评估，并且分多种情况对优先规则的绩效和混合整数线性规划模型进行分析.Grunow等（2006）对集装箱自动码头的自动搬运车调度策略进行仿真研究，并用可扩展仿真模型对提出的仿真策略进行评估.Kim和Bae（2004）利用Kim和Bae（1999）提出的混合整数模型给自动搬运车调度设计了拓展算法，该算法与本文研究类似，该文章讨论了在有未来任务位置和时间的退出信息情况下，如何调度自动搬运车使得岸桥总等待时间和总移动时间最小化的问题.这篇文章还

6、考虑了多岸桥和自动搬运车双循环操作的联合调度策略.Nguyen和Kim（2009）进一步研究了Kim和Bae（2004）发表文章的主要思想，设计了解决自己能从地面上起升集装箱的自动起升车调度问题的启发式算法. 集卡调度也被考虑在传统卡车和拖车系统中.Bish等（2001）研究了集卡调度的NP-hard问题，根据最小化完工时间给每一个卸载集装箱分配了堆场位置.Bish（2003）提出了一个启发式算法以解决集卡的调度问题，当编制岸桥装卸时间表的时候，确定每一集装箱卸往堆场储存位置.Bish等（2005）是Bish（2003）问题的延伸，两者都解决该问题提出了简单的可实施的启发式算法，并且算出了所提

7、出算法最坏情况绝对性能比和渐进性能比.Nishimura等（2005）研究了动态拖车路径问题，在该篇文章中，拖车分配给制定岸桥，并且车辆可能是单拖车或是双拖车.Zhang等（2005）提出了三个关于集装箱码头集卡调度问题的混合整数规划模型，任务的开始时间和集卡的工作序列需要确定，这些模型只考虑了一个泊位一条船舶的卸载阶段，并且只有一台特定的岸桥服务船舶.Ng和Mak（2004）设计了一个算法给运输出口集装箱的卡车进入工作车道顺序进行排序.Ng等（2007）使用遗传算法研究了集装箱码头一队集卡执行一系列运输任务的时间表问题，他们集中研究完工时间最小化的情况下卡车任务顺序的时间表.Chen等（20

8、07）将调度问题转换为一个带有优先约束和阻塞限制的混合流水车间调度问题，并运用基于禁忌搜索的算法来解决该问题，结果显示拥有一个较优初始方案很重要. 上述许多研究除了Chen等（2007）都没有考虑堆场的延迟情况，它们都在必要的时候假设场桥数量总是足够的，当场桥不存在拥挤情况或是场桥数量足够的时候这个，该假设是合理的，但是事实并不总是如此，尤其是当交通量很大的时候.另外，大多数文章局限于任务为出口集装箱或进口集装箱港口. 本文将考虑堆场处的延迟，并同时考虑集装箱的装卸过程，这是在集装箱转运港口最常见的情况.另外，集卡可服务于任何岸桥，而不是指定给某一特定岸桥.我们寻求在考虑所有设备的情况下，完成

9、给定数量的集装箱任务使码头前沿完工时间最短的一种有效率集卡调度方法.我们将这个作为目标的原因是我们想要加速船舶的周转时间，其他的目标，像岸桥等待时间、船舶周转时间我们的模型中也考虑到了. 我们为解决该问题，提出了一个混合整数规划模型，数值试验表明现有的解器不能直接求解该混合整数规划问题，因此，我们提出了两个启发式算法来解决这个问题.第一个方法是领域搜索法，对于第二种方法我们将最小成本流网络模型与遗传算法结合在一起，在遗传算法此方法中，我们根据任务的开始时间编码染色体，而不是直接用集卡任务序列.这种方法是创新的，并且能够利用遗传算法和最小成本流的优点.在给定的开始时间下，最小成本流旨在找到能使最

10、小成本流模型目标最小的集卡时间表.本文证明了最小成本流能够将染色体解码，并得出最优集卡工作时间表.当染色体编码拥有良好的领域结构，遗传算法在设计空间上进行局部和整体的搜索都具有优势.在这种情况下，我们能发现由于交叉算子执行时，开始时间的领域结构被保存，用开始时间对染色体进行编码会比用工作序列更好. 我们考虑了堆场的延迟即增加了问题难度的一个维度，所以研究内容与现有的大多数研究不同.Chen等（2007）解决了类似的问题，但是我们同时考了了转运中心的装卸过程，另外，我们使用的是遗传算法和最小成本流，而他们使用的是禁忌搜索法.本文其他部分结构如下所示：第二部分提出了混合整数规划模型，第三部分描述了

11、解决该问题的两种启发式算法，第四部分展示了数值试验的结果，最后，第五部分我们给出了结论还有未来研究方向.2数学模型 本文研究的是几条船舶在一给定时间段内同时进行装卸，每一个集装箱的堆场位置对集卡来说是已知的，主要的操作决策就是确定集卡的任务顺序.实际上，大多数港口都直接将一定数量的集卡通过启发式算法分配给制定的某一岸桥，例如，最近的任务优先.当这种贪婪方法很容易实施时，可能会给出较差的解决方法.因此，设计一个同时考虑所有的设备的模型是很重要的.在这个部分，我们将为这个集卡调度问题提出一个混合整数规划模型.假设如下所示：1.每一个岸桥的任务序列、任务类型都已知，并且岸桥必须严格按照岸桥序列清单上

12、执行；2.每一任务的堆场位置已知；3.两个处理地点之间的位置已知；4.集卡服务于所有岸桥；5.集装箱任务、岸桥、场桥、集卡的数量已知；6.集卡一次只能运载一个集装箱；7.场桥的行驶时间计入操作时间；8.不考虑集卡的交通拥挤；符号参数K岸桥的集合M集卡的集合R场桥的集合Nk岸桥k工作列表的工作数量L装箱任务的集合D卸箱任务的集合H所有任务的集合，H=LDN集装箱任务的总数，包括装卸任务，N= = ;（i，）任务索引，任务（i，）表示岸桥工作列表中的第i个任务；（S，D）虚拟开始任务；（E，D）虚拟结束任务；集装箱任务的集合，包括虚拟开始任务和虚拟结束任务，；包括虚拟开始任务的所有集装箱任务，；包

13、括虚拟开始任务的所有集装箱任务，；使用场桥的任务；一个很大额常熟岸桥处理任务（装或卸）的操作时间；场桥处理任务（装或卸）的操作时间；集卡从任务起始地到其预设目的地的运输时间；集卡从任务结束地到其下一任务起始地的空载时间；变量，当集卡结束任务后驶向下一任务的起始位置；否则.，当场桥结束任务后开始下一任务的起始位置；否则.岸桥处理任务的开始时刻；相应场桥处理任务的开始时刻；所有任务都为装载任务或卸载任务，因此，为了方便建立模型，我们有必要对这两种任务的活动时间进行分析.·卸载任务的活动时间轴（图一）下面的卸载任务活动时间轴描述了集卡完成装卸任务所需时间，深色区域表示每一个集卡在码头前沿或

14、堆场的可能等待时间.对卸载任务来说，表示岸桥将它的第i个集装箱卸载到集卡的开始时刻；表示岸桥卸载集装箱到集卡上的操作时间.图1.卸载任务的活动时间轴图.卸载任务活动时间轴图.装载任务活动时间轴图2.卸载任务的活动时间轴目标函数：约束条件：·资源约束·给定任务的时间约束·不同资源的顺序依赖时间岸桥：由同一岸桥处理的两个集装箱任务必须要隔至少一个操作时间.集卡：由同一集卡处理的两个集装箱任务必须要隔至少一个操作时间.场桥：由同一场桥处理的两个集装箱任务必须要隔至少一个操作时间. 目标函数（1）表示码头前沿基于当前设备配置情况，完成给定的一系列任务的完工时间最小. 约束

15、条件（2-10）为资源约束，在这些约束条件总，（2-6）是关于码头前沿的，其余的是关于堆场的. 约束条件（2）和（3）表示集合H内每一个集装箱任务都有前序任务和后续任务，并且只有一辆集卡完成，约束条件（4）保证了每一辆集卡路径的连续性.约束条件（5）、（6）定义了集卡序列的虚拟起始点和虚拟结束点，关于堆场的约束条件（7-10）几乎与码头前沿的一致. 约束条件（11、12）是时间约束，限定了岸桥和场桥来时任务时刻必须由集卡在岸桥和场桥之间的移动时间和操作时间. 约束条件（13-18）是不同资源的顺序依赖时间约束与具有优先限制的多旅行商问题和平行机排程问题相类似，表示了由同一岸桥/场桥/集卡所执行

16、的两个任务之间必须隔至少一个操作时间.约束（14-17）表示集卡的顺序依赖时间限制取决于两个任务的类型，如卸卸，装装，装卸，卸装.约束（19-21）为非负和整数约束.3提出的启发式算法 分提出的调度模型将决定集卡和场桥的工作顺序，我们以2台岸桥，3台场桥，2辆集卡为例进行数值试验，对该模型的效率进行检测，该模型利用CPLEX进行求解，并由程序执行.我们发现当任务数量从增加到时，求解该混合整数规划模型的运行时间更长.图.求解混合指数规划模型用时 由于解决小规模问题所需时间过长（如图），因此该混合整数规划模型不适合解决实际码头的问题，我们提出了一个如图所示的解决方案框架来解决这类问题，该框架的主要

17、构思就是搜索集卡序列，得到给定集卡序列后评价模型再给出场桥序列，最后，我们希望该框架能找到较优的集卡序列.初始集卡序列方案集卡方案群评价模型搜索方法图.所提算法的框架 现在，我们讨论框架的概念，首先，我们产生一个初始集卡序列，这个序列既可以为随机给出的，也可以通过基于像最小成本流网络模型的启发式算法得出，基于该序列，我们创造一群新序列，并通过考虑不同场桥序列对这些集卡序列进行评估，为了提高解的质量，将运用一些搜索方法来产生新序列群，重复该过程直至达到停止标准. 对于该评估模块，我们需要在考虑码头前沿和堆场的延迟情况下，计算对于一给定集卡序列，完成码头前沿活动的完工时间，我们提出两种方法，第一个

18、是基于简化的混合整数规划模型，第二个是基于先到先服务的仿真方法，该简化混合整数规划模型实质上就是第部分所提出的，不同的是，此处集卡序列是给定的，这意味着所有的值是固定的，因为混合整数规划模型的规模已经大大减小了，所以该简化混合整数规划模型解决这类小规模问题效率很高，但是因为它仍是一个混合整数规划模型，所以当任务数量变大了之后，运行情况就变得不好了. 对于基于先到先服务的仿真模型，我们假设场桥根据集卡到达场桥时间，按先到先服务规则进行作业.集卡序列已知，通过先到先服务规则，可以使用集散事件调度方法确定集卡在码头前沿和堆场完成活动的时间，因为不需要求解任务优化模型，相比简化混合整数规划模型，该方法

19、计算速度更快，在数值试验中，我们得知仿真方案和简化混合整数规划模型的效果差不多，由于仿真方法计算的效率高，我们使用它来解决规模大的问题. 对于搜索方法，我们采用两种不同的方法来产生新的集卡任务序列：一个是可变邻域搜索法，另一个是基于遗传算法和最小成本流的网络模型方法. 在接下来的部分，我们将详细得讨论最小成本流、可变邻域搜索法和基于遗传算法和最小成本流的网络模型.3.最小成本流模型 Cheng等（2005）文章中提到最小成本流模型的目标是找到一个使延迟最小、集卡利用率最大的集卡序列.而在我们的研究中，打算运用最小成本流作为产生集卡序列的一种方法.Vis等（2001,2005）和potvin等（

20、1992,1993）的研究中有关于最小成本流网络模型的详细介绍. 本文用到的最小成本流模型中，我们假设任务的开始时间已知，并且由集卡的顺序无关，场桥充足即在堆场不存在等待时间. 该模型寻求与任务开始时间最小差值最小的集卡序列，不考虑延迟、设备之间的干扰、工作序列，我们提出的最小成本流模型中使用的开始时间不是实际操作的开始时间，换言之，这些开始时间可以看成是虚拟开始时间，通过确定这些时间可以帮助找到集卡序列. 在后续的讨论中，我们将用符号i,j表示集装箱任务，S,D分别表示虚拟开始任务、虚拟结束任务，我们的模型可以看做的有向图，表示点的集合，表示弧的集合，集合中所有集装箱任务都为中的点，用有向的

21、弧链接被同一集卡执行的两个任务，当辆集卡执行集合中任务是，需要确定从到的条路径，弧的值表示与开始时间的差值，目标是全网络成本最低. 让为决策变量，当同一集卡在结束任务后立即执行任务时取，为集卡结束任务后执行任务开始时间差值的成本参数.模型如下：最小成本流模型 等式（）表示目标函数为整个成本流最小化.约束条件（）是对个集卡流的守恒.约束条件（）和（）保证了从点到点集合中的吗条路径要执行集合中任务，约束条件（）和（）规定每个任务只能有一条路径服务（即一辆集卡）.约束条件（）限制了流量小于. 该模型提供二进制的解决方案，因此问题能有有效率地解决，接下来我们将讨论如何计算.从虚拟节点到所有集装箱任务节

22、点的弧、所有集装箱任务节点到虚拟节点的弧都为成本.为了计算两个集装箱任务节点间的弧，我们需要知道两任务在各自岸桥处的开始时间、行程时间和操作时间.让为岸桥卸载或装载集装箱任务的开始时间.表示当集卡在岸桥处开始任务与在集卡处结束任务之间的间隔时间，因此，为集卡到达操作任务的岸桥处的时间，在结束任务后开始任务的时间差值，如下所示：是大于的常数.是在过早或过早的一个相关权重参数，过晚的话会导致岸桥过早的等待，不仅使集卡等待而且会产生由岸桥序列混乱导致的不可行性.当数值试验运行时，我们需要调整参数.的计算取决于任务对的类型，如卸卸，装装，装卸，卸装（见图）.对于卸装任务，包括任务i的岸桥操作时间，从岸

23、桥到场桥的行驶时间，场桥的操作时间，从任务i场桥目的地到任务j场桥起始地的行驶时间，场桥操作任务j的时间，从场桥到岸桥的行驶时间，因此，对iD，jL有：同样，我们可以得出其他几种情况下的定义：图.四种情况下的组成 当所有任务的开始时间已知，任务之间的已知时，该模型的优点是能高效率地解决调度问题，而缺点是假设场桥是充足的，也就是说不考虑堆场的等待时间，另外，通过确定开始时间，我们直接假设集卡总是能在开始时间在岸桥处开始任务，忽略岸桥和集卡的等待时间. 最小成本流模型不排斥任务的子方案，由于某些开始时间可能会给出不可行的集卡序列，所以，选择合适的开始时间是很重要的，幸运的是，由于成本系数的定义，我

24、们模型中的子方案都是劣解，为了得带更好的解，按照到达的顺序，任务的开始时间都是给递减的，这样选择的所有都是小的，然而，如果解中存在子方案，意味着由于违背非递减性，至少存在一个较大，存在能提供好的甚至是最优集卡序列的开始时间.定理1表示存在一系列可得到最优集卡序列的开始时间. 表示使码头前沿完工时间最小的集卡序列，MCF（t）表示在给定开始时间t的情况下，t为表示所有任务开始时间的矢量，通过求解最小成本流模型得到的最优集卡序列.定理1 对所有任务最优开始时间，存在=MCF（）证明 已知中一个最优集卡序列，将第一个任务的开始时间设为0，用下面公式对序列任务按顺序进行设置准备时间，在最优集卡序列中，

25、集卡完成任务i后立即开始任务j，任务i的开始时间为，则任务j的开始时间=+，用这种方法设置开始时间会使得接下来最优序列中的任务对的=0.因此，当开始时间为时，在最小成本流模型中的目标函数值为0.定理1表明当我们在开始时间的设计空间内搜索时不会丢失最优解，我们所设计的启发式算法中，以两种不同方法用到了最小成本流模型：第一种是在所有任务初始开始时间已知情况下，产生初始集卡序列，第二种是作为以开始时间编码染色体的遗传算法的解码器.3.2可变邻域搜索法 Mladenovic and Hansen（1997）提到可变邻域搜索法（VNS）是用于求解足额和和全局最优问题的一种启发式算法，是使邻域有一个系统改

26、变的简单有效的搜索方法.Garcia-Lopez等（2002）讲解了其基本步骤，首先找到一个初始解，两个嵌套的圈，中心的圈通过称为“环裂”、“局部搜索”的两个主要功能改变、探索.当内圈进行主要的局部搜索时，外圈反复更新内圈，只要解有所改进便进行迭代，直到满足停止标准，环裂功能使解变得多样化. 在该遗传算法中，VNS用于更新由MCF方法得到的初始解，该更新步骤已知重复直至满足停止标准，VNS的伪代码如图6所示，体现了我们整数调度问题的VNS法解决方法.图6.VNS解决方法 由得到的初始解，我们令，通过环裂程序产生从中大小为的邻域内得带随机解，通过局部搜索技术，从该随机解找到一个新解，为了强化该随

27、机解的邻域搜索，局部搜索重复次.若所得解优于当前解，则采纳新解，并将邻域大小设为.若在次尝试后，当前解未得到改进，将邻域大小增加，当超过的最大限度时停止算法. 基于交换片段方式的两集卡任务序列的局部优化（如图所示）.下面讨论基于启发式算法的步骤.步骤：（） 初始化：找到初试方案，令.进行评估是否交换？交换两条片段随机选两条集卡路径在第一条路径中随机选一片段在第二条路径中随机选一片段可行？在该集卡序列队停止？停止选择集卡序列队？停止搜索图.法的局部搜索步骤（2）环裂过程：从中大小为的邻域内随机选出.（3）局部搜索：从解中随机选出两个集卡序列片段.（）从第一个序列中连续任务命令任意基数的片段是随机

28、选取的； 连续命令的片段长度可以任意地为1、2、3，为了不破坏原始序列，将片段的基数小于3.（）从第二个序列中连续任务命令任意基数的片段是随机选取的； （）交换两条选取的片段（如图所示）. 其中一个集卡序列片段插入另外一集卡序列片段移出的位置. （）可行性检验：检测在给定岸桥序列下，两个新的集卡序列是否可行. 在交换后，应该检测两个集卡序列的可行性，以任务、为例，假设任务、都在同一岸桥的工作清单内，工作顺序为先任务后任务，则在集卡序列中，任务不能出现在任务之前，否则，该交换不可行.若两个新集卡序列可行，进入评估步骤.交换之后的两条随机选择片段交换之前的两条随机选择片段 图8.两条片段的交换形式

29、 否则，返回（）在每一个集卡序列中选一片断，最多取次，若在次之后， 没找到可行解，为了避免不必要的搜索返回（）环裂，选择另一对集卡序列.（4）评估：用简化模型或基于仿真的方法对新解进行评估，得到目标值，若更优，接受新解，令，.否则保留当前解，返回，进行次局部搜索，令，返回（）选择另外一个解，直到达到的限制.3.3基于最小成本流网络模型的遗传算法 遗传算法是常见的元启发式算法，源于生物的自然进化，能够同时运算一群解.本文选择遗传算法原因如下：首先，遗传算法是常见的元启发式算法，并且它的求解效率已被许多问题所证实.第二相比较于领域搜索算法，我们需要一个像遗传算法一样的基于种群的方法以便更好地搜索解

30、空间.遗传算法的步骤如图9所示，相比较于其他传统遗传算法的设置，本文使用开始时间对染色体进行编码，求解最小成本流模型来得到集卡序列.3.3.1染色体编码 我们用开始时间对染色体进行编码，相比于用集卡序列编码的好处在于交叉操作后，邻域结构更容易被保留，而且，岸桥的序列也易得出.此外，本文在定理1处通过谨慎选择开始时间，能够得到最优集卡序列. 本文用个指定岸桥序列中各任务开始时间来编码染色体，而不是直接用开始时间，为任务i在岸桥处的开始时间，为岸桥下一个任务的开始时间，. 染色体根据进行编码，用这种编码可以保证任务的开始时间遵循岸桥序列，遗传算法对进行搜索，很容易得到.3.3.2父代的选择 父代的

31、选择策略意味着如何在能产生下一代的当前群体中选择染色体，通常来说，当前群体中解越优被选为生成子代的父代概论越大，这种方法是更好的.因此本文使用二元竞标赛选择法，二元竞标赛选择法随机选出两个个体，赢的一方成为父代，在交叉操作中，将会重复该过程直到选出父代，为了保证最优个体能够存活到下一代，本文使用精英策略使最优解一直留在群体中.3.3.3交叉本文使用算术交叉算子来探索解空间，新的子代与父代成线性关系.为0.5到1之间的任意数.3.3.4突变 突变算子的主要任务是在子代中维持种群的多样性并探索解空间.对每一个体，先选0到1之间认得任意数与突变概论相比较，因为突变发生的概论实在太小（通常=0.001

32、），若该数小于（概论相当低），则对该个体执行突变.突变步骤为交换两条任意选中基因的值.3.3.5子代的选择 采用拟贪婪策略的形式接受由遗传算子产生的子代，在该策略中，如果子代的适应度小于它父辈的平均值，则作为新一代接受.3.3.6停止标准 为了减少计算时间，我们采用两个标准作为停止规则：（1）生成子代数达到最大值，（2）当前种群染色体适应度的标准差小于某个很小的值.4试验 为了检测算法的求解效率和所得解的质量，我们进行试验，所有试验都2GB RAM的2.4GHZ PC执行，启发式算法由C+运行，MIP模型由线性求解器进行求解.每一个算例都由邻域搜索法和遗传算法求解次，并记录完工时间（目标值）.通过两组