关于集装箱转运中心集卡的调度算法

摘要：

本文在考虑岸桥、场桥的作业能力情况下，解决了集装箱转运中心集卡的调度问题。本文的目标是使岸边作业完成时间最小化。这个问题对于那些能够通过信息技术充分利用数据做出科学决策的港口尤其重要。本文提出一个混合整数规划模型来解决该问题。现有的解决方案不能在合理的时间内解决混合整数规划模型，因此，本文提出了两个启发式算法来解决该问题。第一个方法是基于邻域搜索的网络模型，第二个是基于遗传算法和最小成本流的网络模型。不像通常用任务序列代表染色体的传统遗传算法，本文使用任务的开始时间代表染色体，最小成本流模型用于解码染色体并且决定集卡的工作序列。本实验结果显示了基于最小成本流的遗传算法优于邻域搜索算法。

关键词：转运 集卡调度 完工时间 遗传算法

1介绍

海上运输一直是支持全球贸易的主心骨，因为80%的国际贸易都是通过海上进行运输。随着世界贸易的不断增长，主要港口之间的竞争也越来越激烈。因此，对港口操作者来说，选择不同的决策工具和优化算法来提高港口的效益和增加其竞争力是非常必要的。

典型的集装箱港口主要资源有岸边起重机（简称岸桥）、堆场起重机（简称场桥）、集装箱卡车（简称集卡），为了提高码头的生产效率，在码头内协调分配给这些设备的任务，保证集装箱流的无缝衔接是非常必要的。

当船舶到达港口时，岸桥将进口和转运的集装箱从船上卸到集卡上，通过集卡将它们运到堆场相应的堆放位置。在堆场方面，场桥将这些集装箱从集卡上卸下到指定的对方位置。从堆场向船上装载进口和转运集装箱的过程与上述过程类似。码头前沿和堆场之间的运输对码头的生产效率起很决定性作用，因为当集卡没有准时到达或者到的太早引起交通拥挤，会导致岸桥或场桥操作延迟。实际上，因交通拥挤、交通延迟、设备故障和其他港口动态不确定性导致各种设备之间在操作方面协调的复杂性，使得优化这类调度问题变得充满挑战性。因此，需要一个信息技术平台收集操作上的实时信息，然后决策支持系统能够充分利用这些信息，进而提供快速、智能的方案来指导港口内集卡的调度及路径规划。本文旨在通过为集卡调度设计算法来提高转运中心码头前沿港口操作效率，以此解决上述问题。

在过去，多数研究集中在改进集卡的时间表。有许多文章研究自动港口无人搬运车（AGV）调度问题。Meersmans 和Wagelmans（2001a，b）对于AGV和起重机选址问题设计了定向搜索算法。Bose等人（2002）使用基于任务或基于集卡的方法找到初始解决方案，同时，利用进化算法进行改善。Van der Meer（2000）研究了集装箱自动码头中自动搬运车的控制。Hartmann（2004）为港口各类操作设备的调度和人力资源设计了遗传算法。Grunow等（2004）研究了多负载自动搬运车调度问题，为在线物流控制系统设计了灵活性优先的方法，利用混合整数线性规划模型对在线策略进行评估，并且分多种情况对优先规则的绩效和混合整数线性规划模型进行分析。Grunow等（2006）对集装箱自动码头的自动搬运车调度策略进行仿真研究，并用可扩展仿真模型对提出的仿真策略进行评估。Kim和Bae（2004）利用Kim和Bae（1999）提出的混合整数模型给自动搬运车调度设计了拓展算法，该算法与本文研究类似，该文章讨论了在有未来任务位置和时间的退出信息情况下，如何调度自动搬运车使得岸桥总等待时间和总移动时间最小化的问题。这篇文章还考虑了多岸桥和自动搬运车双循环操作的联合调度策略。Nguyen和Kim（2009）进一步研究了Kim和Bae（2004）发表文章的主要思想，设计了解决自己能从地面上起升集装箱的自动起升车调度问题的启发式算法。

集卡调度也被考虑在传统卡车和拖车系统中。Bish等（2001）研究了集卡调度的NP-hard问题，根据最小化完工时间给每一个卸载集装箱分配了堆场位置。Bish（2003）提出了一个启发式算法以解决集卡的调度问题，当编制岸桥装卸时间表的时候，确定每一集装箱卸往堆场储存位置。Bish等（2005）是Bish（2003）问题的延伸，两者都解决该问题提出了简单的可实施的启发式算法，并且算出了所提出算法最坏情况绝对性能比和渐进性能比。Nishimura等（2005）研究了动态拖车路径问题，在该篇文章中，拖车分配给制定岸桥，并且车辆可能是单拖车或是双拖车。Zhang等（2005）提出了三个关于集装箱码头集卡调度问题的混合整数规划模型，任务的开始时间和集卡的工作序列需要确定，这些模型只考虑了一个泊位一条船舶的卸载阶段，并且只有一台特定的岸桥服务船舶。Ng和Mak（2004）设计了一个算法给运输出口集装箱的卡车进入工作车道顺序进行排序。Ng等（2007）使用遗传算法研究了集装箱码头一队集卡执行一系列运输任务的时间表问题，他们集中研究完工时间最小化的情况下卡车任务顺序的时间表。Chen等（2007）将调度问题转换为一个带有优先约束和阻塞限制的混合流水车间调度问题，并运用基于禁忌搜索的算法来解决该问题，结果显示拥有一个较优初始方案很重要。

上述许多研究除了Chen等（2007）都没有考虑堆场的延迟情况，它们都在必要的时候假设场桥数量总是足够的，当场桥不存在拥挤情况或是场桥数量足够的时候这个，该假设是合理的，但是事实并不总是如此，尤其是当交通量很大的时候。另外，大多数文章局限于任务为出口集装箱或进口集装箱港口。

本文将考虑堆场处的延迟，并同时考虑集装箱的装卸过程，这是在集装箱转运港口最常见的情况。另外，集卡可服务于任何岸桥，而不是指定给某一特定岸桥。我们寻求在考虑所有设备的情况下，完成给定数量的集装箱任务使码头前沿完工时间最短的一种有效率集卡调度方法。我们将这个作为目标的原因是我们想要加速船舶的周转时间，其他的目标，像岸桥等待时间、船舶周转时间我们的模型中也考虑到了。

我们为解决该问题，提出了一个混合整数规划模型，数值试验表明现有的解器不能直接求解该混合整数规划问题，因此，我们提出了两个启发式算法来解决这个问题。第一个方法是领域搜索法，对于第二种方法我们将最小成本流网络模型与遗传算法结合在一起，在遗传算法此方法中，我们根据任务的开始时间编码染色体，而不是直接用集卡任务序列。这种方法是创新的，并且能够利用遗传算法和最小成本流的优点。在给定的开始时间下，最小成本流旨在找到能使最小成本流模型目标最小的集卡时间表。本文证明了最小成本流能够将染色体解码，并得出最优集卡工作时间表。当染色体编码拥有良好的领域结构，遗传算法在设计空间上进行局部和整体的搜索都具有优势。在这种情况下，我们能发现由于交叉算子执行时，开始时间的领域结构被保存，用开始时间对染色体进行编码会比用工作序列更好。

我们考虑了堆场的延迟即增加了问题难度的一个维度，所以研究内容与现有的大多数研究不同。Chen等（2007）解决了类似的问题，但是我们同时考了了转运中心的装卸过程，另外，我们使用的是遗传算法和最小成本流，而他们使用的是禁忌搜索法。

本文其他部分结构如下所示：第二部分提出了混合整数规划模型，第三部分描述了解决该问题的两种启发式算法，第四部分展示了数值试验的结果，最后，第五部分我们给出了结论还有未来研究方向。

2数学模型

本文研究的是几条船舶在一给定时间段内同时进行装卸，每一个集装箱的堆场位置对集卡来说是已知的，主要的操作决策就是确定集卡的任务顺序。实际上，大多数港口都直接将一定数量的集卡通过启发式算法分配给制定的某一岸桥，例如，最近的任务优先。当这种贪婪方法很容易实施时，可能会给出较差的解决方法。因此，设计一个同时考虑所有的设备的模型是很重要的。在这个部分，我们将为这个集卡调度问题提出一个混合整数规划模型。

假设如下所示：

1.每一个岸桥的任务序列、任务类型都已知，并且岸桥必须严格按照岸桥序列清单上执行；

2.每一任务的堆场位置已知；

3.两个处理地点之间的位置已知；

4.集卡服务于所有岸桥；

5.集装箱任务、岸桥、场桥、集卡的数量已知；

6.集卡一次只能运载一个集装箱；

7.场桥的行驶时间计入操作时间；

8.不考虑集卡的交通拥挤；

符号参数：

K岸桥的集合

M集卡的集合

R场桥的集合

N_k岸桥k工作列表的工作数量

L装箱任务的集合

D卸箱任务的集合

H所有任务的集合，H=Lcup;D

N集装箱任务的总数，包括装卸任务，N= = ;

（i，alpha;）任务索引，任务（i，alpha;）表示岸桥alpha;工作列表中的第i个任务；

（S，D）虚拟开始任务；

（E，D）虚拟结束任务；

Ｊ集装箱任务的集合，包括虚拟开始任务和虚拟结束任务，；

包括虚拟开始任务的所有集装箱任务，；

包括虚拟开始任务的所有集装箱任务，；

使用场桥ｒ的任务；

Ｃ一个很大额常熟

岸桥处理任务（装或卸）的操作时间；

场桥处理任务（装或卸）的操作时间；

集卡从任务起始地到其预设目的地的运输时间；

集卡从任务结束地到其下一任务起始地的空载时间；

变量

＝１，当集卡ｍ结束任务后驶向下一任务的起始位置；否则＝０。

＝１，当场桥ｒ结束任务后开始下一任务的起始位置；否则＝０。

岸桥alpha;处理任务的开始时刻；

相应场桥处理任务的开始时刻；

所有任务都为装载任务或卸载任务，因此，为了方便建立模型，我们有必要对这两种任务的活动时间进行分析。

·卸载任务的活动时间轴（图一）

下面的卸载任务活动时间轴描述了集卡完成装卸任务所需时间，深色区域表示每一个集卡在码头前沿或堆场的可能等待时间。

对卸载任务来说，表示岸桥alpha;将它的第i个集装箱卸载到集卡的开始时刻；表示岸桥卸载集装箱到集卡上的操作时间。

图1卸载任务的活动时间轴

图2装载任务的活动时间轴

目标函数：

约束条件：

资源约束

·给定任务的时间约束

·不同资源的顺序依赖时间

岸桥：由同一岸桥处理的两个集装箱任务必须要隔至少一个操作时间。

集卡：由同一集卡处理的两个集装箱任务必须要隔至少一个操作时间。

场桥：由同一场桥处理的两个集装箱任务必须要隔至少一个操作时间。

目标函数（1）表示码头前沿基于当前设备配置情况，完成给定的一系列任务的完工时间最小。

约束条件（2-10）为资源约束，在这些约束条件总，（2-6）是关于码头前沿的，其余的是关于堆场的。约束条件（2）和（3）表示集合H内每一个集装箱任务都有前序任务和后续任务，并且只有一辆集卡完成，约束条件（4）保证了每一辆集卡路径的连续性。约束条件（5）、（6）定义了集卡序列的虚拟起始点和虚拟结束点，关于堆场的约束条件（7-10）几乎与码头前沿的一致。

约束条件（11、12）是时间约束，限定了岸桥和场桥来时任务时刻必须由集卡在岸桥和场桥之间的移动时间和操作时间。

约束条件（13-18）是不同资源的顺序依赖时间约束与具有优先限制的多旅行商问题和平行机排程问题相类似，表示了由同一岸桥/场桥/集卡所执行的两个任务之间必须隔至少一个操作时间。约束（14-17）表示集卡的顺序依赖时间限制取决于两个任务的类型，如卸——卸，装——装，装——卸，卸——装。约束（19-21）为非负和整数约束。

3提出的启发式算法

提出的调度模型将决定集卡和场桥的工作顺序，我们以2台岸桥，3台场桥，2辆集卡为例进行数值试验，对该模型的效率进行检测，该模型利用CPLEX进行求解，并由Ｃ 程序执行。我们发现当任务数量从6增加到16时，求解该混合整数规划模型的运行时间更长。

图3求解混合指数规划模型CPU用时

现在，我们讨论框架的概念，首先，我们产生一个初始集卡序列，这个序列既可以为随机给出的，也可以通过基于像最小成本流网络模型的启发式算法得出，基于该序列，我们创造一群新序列，并通过考虑不同场桥序列对这些集卡序列进行评估，为了提高解的质量，将运用一些搜索方法来产生新序列群，重复该过程直至达到停止标准。

对于该评估模块，我们需要在考虑码头前沿和堆场的延迟情况下，计算对于一给定集卡序列，完成码头前沿活动的完工时间，我们提出两种方法，第一个是基于简化的混合整数规划模型，第二个是基于先到先服务的仿真方法，该简化混合整数规划模型实质上就是第2部分所提出的，不同的是，此处集卡序列是给定的，这意味着所有的值是固定的，因为混合整数规划模型的规模已经大大减小了，所以该简化混合整数规划模型解决这类小规模问题效率很高，但是因为它仍是一个混合整数规划模型，所以当任务数量变大了之后，运行情况就变得不好了。

对于基于先到先服务的仿真模型，我们假设场桥根据集卡到达场桥时间，按先到先服务规则进行作业。集卡序列已知，通过先到先服务规则，可以使用集散事件调度方法确定集卡在码头前沿和堆场完成活动的时间，因为不需要求解任务优化模型，相比简化混合整数规划模型，该方法计算速度更快，在数值试验中，我们得知仿真方案和简化混合整数规划模型的效果差不多，由于仿真方法计算的效率高，我们使用它来解决规模大的问题。

对于搜索方法

剩余内容已隐藏，支付完成后下载完整资料

---

英语原文共 23 页，剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[140260]，资料为PDF文档或Word文档，PDF文档可免费转换为Word