英语原文共 16 页，剩余内容已隐藏，支付完成后下载完整资料
使用遗传算法在集装箱码头调度卡车
卡车是大多数超级终端中最受欢迎的运输设备，并且安排它们以尽量减少完工时间是本文所要解决和尝试解决的挑战。具体而言，研究了调度一组卡车执行一系列具有序列相关处理时间和不同就绪时间的运输工作的问题，并且提出了使用遗传算法（GA）来解决调度问题。调度问题被公式化为一个混合整数程序。值得注意的是，调度问题是NP难题，解决小规模测试问题所需的计算量也非常大。针对所提出的遗传算法开发了交叉计划。使用六种流行的交叉方案进行计算实验，以比较所提出的遗传算法与遗传算法的性能。计算结果表明，所提出的遗传算法性能最好，其解决方案平均比其他六个遗传算法找到的最佳解决方案好4.05％。
关键词：货车调度; 集装箱码头; 遗传算法
- 简介
面对快速的贸易全球化，海运业已经被推到了一个越来越重要的位置，因此增加了责任。 港口集装箱码头对运营效率的需求更大，其中最重要的是码头周转时间或船舶停留在码头的平均时间。 为了制定缩短码头周转时间的方法，有必要详细研究集装箱码头的运作流程。
在一个港口集装箱码头，一些船只经常停靠在一起，每艘船只由多台码头起重机支撑，并由大量的码头起重机支撑。 当一艘船到达码头时，集装箱通常从船上卸下，通过码头起重机安装在卡车上，然后由各个场所的堆场起重机卸下来存放。 在装货作业中，由院子里的堆场起重机装载到卡车上的出口集装箱在码头卸载并通过码头起重机装载到船上。 设备的调度和调度在卸货和装货操作中都至关重要，并且为码头规划者提出了关键的规划挑战。
在典型的装卸作业中，码头起重机的搬运工作为货车的运输工作和堆场起重机的集装箱处理工作产生作用。通过语音通信或无线计算机网络将运输工作实时派发给高度移动的卡车。卡车进行的运输工作中涉及的典型活动如下：（i）当运输工作被派遣到闲置卡车时，它从其上一个工作的集装箱下落位置运行到集装箱接收位置派遣工作并等待起重机（码头/码头起重机）为其服务; （ii）在由起重机装载集装箱之后，卡车行驶到集装箱卸货位置并等待起重机（堆场/码头起重机）卸载集装箱; （iii）一旦集装箱被卸载，卡车可用于执行另一运输工作。处理运输工作的时间取决于起重机上下集装箱的时间，以及卡车从上一个工作的集装箱下落位置到达下一份工作。因此，作业的处理时间取决于派送给它的卡车的作业处理顺序。
为了协调终端的运行，控制系统首先确定每台起重机何时可用于处理新的工作，然后根据起重机的可用性计算每个集装箱提货位置处的期望的卡车到达时间。 卡车在工作地点的预计到达时间称为工作准备时间。 比他们派遣工作的就业准备时间早到达的卡车将不得不等待起重机。
显然，高效的卡车运行可以加快集装箱处理流程，平滑集装箱流量，从而提高码头性能。 因此，需要开发一个有效的卡车调度算法来增加集装箱进出船舶的流量，从而缩短码头周转时间。
物流系统中常常出现与调度和调度车辆和装卸设备有关的问题（Bramel和Simchi-Levi 1997）。这些问题已经在运筹学/管理科学文献中被广泛研究。不幸的是，大多数研究文献报道的结果不能直接应用于港口集装箱码头运营，因为所研究问题的特点与港口集装箱码头不同。
由于海运系统日益重要，港口集装箱码头作业特有的问题越来越受到关注。虽然大多数早期的集装箱码头研究集中在战略问题上，比如确定码头中码头起重机，卡车和起重机的数量（Edmond 1975，Hammesfahr and Clayton 1983，Easa 1987，Daganzo 1990）最近被指导研究集装箱码头的运营计划问题。 Kim和Kim（1999a）研究了为了支持装载操作而布置堆场起重机的问题，以尽量减少总处理时间。 Kim和Kim（1999b）研究了将一个单跨运输船（具有集装箱处理能力的运输设备）运输到一个装载船的出口集装箱的问题。 Ng和Mak（2005a，b）研究了调度堆场起重机以执行一系列准备时间不同的加卸载作业的问题，并提出了不同的有效算法来解决调度问题。 Ng（2005）开发了一种基于动态规划的启发式算法，以解决在具有起重机间干扰的场区内多个起重机的调度问题。
Bish等人（2001）研究了调度卡车和确定每个卸货集装箱的存储位置以最小化完工时间的问题。结果表明，这个问题是NP难题。 Bish（2003）扩展了这项研究，以检查确定每个卸货集装箱的存储位置，调度车辆到集装箱的问题，以及安排码头起重机的卸货和装货作业，以尽量减少服务给定船舶所需的最大时间。该问题表现为NP难度，并提出了启发式算法来解决这个问题。 Bish等人（2005）针对Bish（2003）研究的问题开发了容易实现的启发式算法，并推导出这些启发式的绝对和渐近最差情况性能比。上面提到的三项卡车调度研究没有考虑调度决策中的工作准备时间。
本文详细分析了安排一组卡车执行一系列具有序列相关处理时间和不同就绪时间以减少所有工作完成时间的运输工作的问题。在第2节中，提出了一个调度问题的整数规划模型，该问题表现为NP难。第3节讨论解决调度问题的遗传算法。第4节介绍计算实验的结果，第5节总结本文。
- 数学模型
在本节中，安排一队卡车执行一系列具有序列相关处理时间和不同就绪时间以最小化完工时间的一组运输工作的问题被制定为一个整数程序。
在目前的规划阶段，有几艘船舶装载或卸载集装箱，并由同一批货车服务。假设M是具有单位承载能力的相同卡车的数量，并且设N（Ngt; M）为当前M卡车运输的集装箱的数量。将集装箱从其提货地点运送到其卸货地点称为卡车工作。假设卡车m在当前的L m和r m时间可用于处理它的第一份工作。每个工作为i，i= 1，2，hellip;，N具有相关的拾取位置P 1和丢弃位置D 1。每个作业的接送位置都是已知的，并由其（x，y）坐标唯一标识。每项工作都涉及从装货地点到卸货地点的装货卡车旅程。卡车旅行时间在终端的任何一对位置之间都是已知的，并且对于装载和空载旅行都是相同的。设tlrsquo;l，lrsquo; = L1，L2，... LM，P1，P2，... PN，D1，D2，... DN, l rsquo; rsquo; =P1，P2，... PN，D1，D2，... DN表示沿着两个位置之间的最短路径从位置lrsquo;到位置lrsquo; rsquo;的卡车行驶时间。假定旅行时间是不对称的，即tlrsquo;lne;tllrsquo;。将工作i的持续时间Ti定义为从派遣工作的卡车到达Pi（工作i的接送位置）到开始离开Di的时刻（该工作的下班地点）工作i）。假定Ti是已知常数。类似地，将工作i的处理时间定义为从卡车开始从当前位置移动到Pi到卡车开始离开Di的那一刻为止的时间（工作i的下落位置。作为卡车通常需要在两次连续的装载行程之间进行空行程，作业i的处理时间有两个组成部分：空行程到达行程的行程时间和行程的持续时间。空行程到行程的行程时间取决于哪个行程卡车被派往工作，而这又取决于Pi和卡车之前处理的工作的下班地点之间的旅行时间一致 。因此，每个作业的处理时间是依赖于序列的。为了减少卡车等待时间和起重机闲置时间，通常使用终端操作控制系统来确定卡车在每个作业的拾取位置的期望到达时间。在这项研究中，所需的卡车工作到达时间的到达时间被认为是工作的准备时间;工作的准备时间我用ai表示。 N个工作以aile;ai 1的方式编制索引。
以下附加标记用于说明数学模型：
X ijm 一个二元变量，如果卡车m（m = 1,2，...，M）处理作业j，则取值为1（i = 1,2，...，N），其中作业N 1是一个虚拟作业（j = 1,2，...，N 1）当工作i是处理的最后一项工作时，用于方便表示案例卡车m。
Y im 一个二进制变量，如果卡车m（m = 1,2，...，M）处理工作i（i=1,2,hellip;,N），则其值为1
Ci 工作完成时间i（i = 1,2，...，N）。
W N个工作的完成时间。
用X表示X ijm的集合，用Y表示Y im的集合，用C表示Ci的集合
卡车调度问题可以用数学方法表述如下：
最小化W
受制于
Cile; W i = 1, 2, . . . , N (1)
Y im = 1 i = 1, 2, . . . , N (2)
X ijmle;Y im i = 1, 2, . . . , N (3)
X ijmle;Yjm j = 1, 2, . . . , N (4)
1 ge; X ijm X jim ge; Y im Yjm minus; 1 i, j = 1, 2, . . . , N 且 i = j ;
m = 1, 2, . . . , M (5)
Ci tDi ,Pj Tj le; K (1 minus; X ijm) Cj i, j = 1, 2, . . . , N 且 i = j ;
m = 1, 2, . . . , M (6)
ai Ti le; Ci i = 1, 2, . . . , N (7)
rm tLm ,Pi Ti le; Ci i = 1, 2, . . . , N ; m = 1, 2, . . . , M (8)
X ijm Y imisin;{0, 1} i = 0, 1, . . . , N minus; 1; j = 1, 2, . . . , N ; m = 1, 2, . . . , M (9)
Cj和W ge; 0 j = 1, 2, . . . , N (10)
其中K是一个很大的正数。
卡车调度问题的目标是最小化N个工作的完成时间。约束（1）给出了完工时间。约束条件（2）确保每个作业仅由一辆卡车处理。约束条件（3） - （5）给出了由同一辆卡车处理的工作的X和Y之间的关系。约束（3）确保如果卡车m在工作i之后处理工作，Yim = 1。约束（4）确保如果卡车m在工作之前处理工作i，Yim = 1。约束（5）确保如果Yim Yj m = 2，卡车m在工作i之前处理工作j之前的工作i或工作j。约束条件（6）给出了工作完成时间与其后继者的完成时间之间的关系。约束（7）陈述完成时间，准备时间和作业持续时间之间的关系。约束条件（8）给出了作业的持续时间和完成时间，卡车准备时间以及卡车从其起始位置到接送位置的行驶时间之间的关系。约束条件（9）和（10）是定义X，Y，C和W值的范围的简单约束。
卡车调度问题等同于调度M个机器（卡车）以处理N个非抢先工作的问题，这些工作具有依赖于序列的处理时间和不同的准备时间以最小化完工时间。 即使卡车调度问题通过在单个机器上将不同工作准备时间划分为M个子问题来简化，从而最小化完工时间，但是注意到每个子问题都是NP难的（Garey and Johnson 1979）。 因此卡车调度问题也是NP难题。 据我们所知，具有这种特征的卡车调度问题尚未在文献中研究。
进行了计算实验，以评估寻找问题实际情况的最佳时间表的可能性。 运行在具有2.4 GHz CPU的PC上的CPLEX解决了计划三辆卡车处理九个作业的十个小规模随机生成测试问题。 从计算结果中发现，即使对于这些问题，找到最佳时间表所需的平均计算时间大约为40分钟，所需的最大时间超过4小时。
鉴于难以找到真实终端操作的最佳时间表，在下一节中提出了一种用于解决卡车调度问题的启发式算法。
- 遗传算法
由Holland（1975）开发的遗传算法（GA）是用于解决困难的离散优化问题的自然启发元启发式算法之一。 GA是一种基于自然选择和适者生存机制的启发式搜索技术。它是一种功能强大且广泛适用的随机搜索技术，适用于许多传统技术难以解决的问题。遗传算法是一种有效而灵活的工具，可为难以解决的大规模组合问题提供近乎最佳的解决方案。由遗传算法得到的解决方案通常优于使用其他启发式算法获得的解决方案，因为它具有逃离局部最优解的固有特征以及找到接近最优解的能力。在过去的三十年中，遗传算法已经被许多研究人员完善，并且正在成为解决集装箱码头运行问题的一种越来越受欢迎的方法（Kozan和Preston，1999; Nishimura等2001，Preston和Kozan 2001，Dubrovsky等2002年，Hartmann 2004，Jula等2005）。以下部分详细介绍了本文中提出的GA。
3.1表示
由Carter和Ragsdale（2005）设计的两部分染色体结构被用作本研究中提出的遗传算法的表示方案。 图1显示了一个示例染色体，用于表示使用两部分染色体结构调度三辆卡车（N
全文共19651字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[14944]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
