英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料
改进的集装箱岸桥调度作业遗传算法
S.H. Chung ， K.L. Choy
工业及系统工程学，香港理工大学，红磡，九龙区
摘要
由于全球化步伐加快，过去20年来海运的需求显着增加。码头管理人员面临挑战，制定适当的码头起重机计划，以实现船舶最早的起飞时间并提供有效的服务。在一般情况下，码头起重机时间表问题包括两个主要问题（1）码头起重机处理卸货和装货作业的分配，以及（2）每个码头起重机的船舶中的船坞的服务顺序。传统上，码头规划人员根据他们的经验和自己的判断来确定码头起重机的时间表。此外，起重机之间的干扰和船舶尺寸的增加进一步显着地增加了其难度。因此，本文提出了一种改进的遗传算法来处理这个问题。为了测试所提出的算法的优化可靠性，解决了一组众所周知的基准标记问题，并将所得结果与其他已知的现有算法进行比较。该比较表明，所提出的算法性能与许多现有算法一样好，并且在某些情况下获得比最知名算法更好的解决方案。此外，所需的计算时间明显小得多，使其更适用于实际情况。
关键词：集装箱码头；集装箱岸桥；调度；遗传算法
1.背景介绍
全球化的迅速步伐显着推动了各国之间的贸易，并因此推动了全球经济的发展。集装箱港口在当今全球物流网络中扮演着不可或缺的角色。 2008年全球集装箱吞吐量为5.34亿标准箱（相当于20英尺单位）（Drewry Shipping Consultants Limited，2010）。尽管由于金融海啸导致全球集装箱吞吐量降至4.64亿TEU，但全球经济仍将反弹并预见2010-2014年集装箱吞吐量的可持续增长仍然乐观。此外，港口内的地理位置接近，尤其是欧洲和亚洲，对港口之间的竞争构成了直接挑战。终端经理致力于持续提供高质量的服务，提高现有设施的效率，以保持与现有客户的良好关系，吸引潜在客户并提高运营生产力。
在过去的十年中，港口业务的主要发展集中在先进技术发展（Guuml;nther＆Kim 2005; Zaffalon，Rizzoli，Gambardella，＆Mastrolilli，1998）。由于资源分配直接决定了港口运营的成功和效率（Bierwirth＆Meisel 2010; Meisel＆Bierwirth 2006; Steenken，Vos＆Stahlbock，2004），港口在开发各种支持技术决策以加强其资源规划系统方面付出了很大努力）。它包括泊位分配计划，船舶装卸计划，集装箱堆场的堆场计划以及通过大门的进出口集装箱计划（Lim，Rodrigues，Xiao，＆Zhu，2004; Park＆Kim，2003）。由于如果船只不能按时出港，将会产生罚款成本，所有这些活动的主要目的是确保船只能够通过最小化船只的周转时间来准时出发。所有这些计划都作为终端操作系统紧密联系和整合。如果其中一个计划未能实现其目标，可能会对其他计划的运作产生负面影响。
码头起重机调度问题（QCSP）首先由Daganzo（1989）描述。 Daganzo（1990）以及Daganzo和Peterkof-sky（1990）定义船舶可以根据船舶的尺寸纵向分隔成多个船舱。船舶的周转时间取决于如何安排每个码头起重机服务于哪个船舱以及每个船舱的处理时间。积载计划由装载和卸载计划组成。船舱的工作量取决于需要处理的集装箱的数量，包括甲板和舱内的装卸作业。任务之间的先验关系涉及卸货和装货作业。尽管它们可以在不同的时间和不同的起重机上进行处理，但卸载操作必须先于装载操作。在同一个船舱，甲板上的任务必须在舱内任务开始卸货之前完成。相反，舱内的任务必须在甲板上的任务开始于同一船位的装载操作之前执行。因此，一些任务必须先于其他任务执行，否则即使其他起重机也不能同时执行（Bierwirth＆Meisel 2009）。
由于码头起重机的尺寸很大，每个船贝一次只能由一台码头起重机。 此外，由于所有的码头起重机都在同一条轨道上行驶，所以码头起重机只能在没有越过其他船舶的情况下进行下一个船舱。 如果需要起重机越过其他起重机，则必须等到另一台起重机完成任务并移开。 本文的目的是提出一种遗传算法来处理QCSP。 本文将分为以下几部分。 第2部分将作为文献回顾。 第3节将描述问题描述和表述。 第4部分将介绍所提出的方法。 第5部分将测试所提出算法的优化可靠性并讨论所得结果。 本文将在第6节结束时进行总结。
2.文献综述
一般来说，QCSP指的是（1）码头起重机处理卸货和装货作业的分配，以及（2）每个码头起重机船舶的船舱的服务顺序（Daganzo 1989）。该积载计划是指（1）该计划表明船只的每个船舱中排放的集装箱的位置，以及（2）关于船只的每个船舱中装载的集装箱的位置的优选计划，基于容器的目的地，重量和类型。
由于其复杂性和实用性，终端业务领域的运筹学被称为最具挑战性的课题之一。在过去的几十年中，已经进行了大量的研究。 Daganzo（1989）研究的第一个QCSP是确定多艘船的出发时间。后来，Daganzo和Peterkofsky（1990）提出了一个分支定界算法来处理类似假设下的问题，其中一个任务在一个船湾执行。该研究旨在确定多艘船舶的起飞时间和在特定时间段内分配给单个船舶的起重机数量，研究的目的是尽量减少延迟成本的总和。
一些研究人员指出QCSP可以模拟为平行机器调度问题（Guinet，1993; Lee＆Pinedo，1997）和车辆路径问题（Sammarra，Cordeau，Laporte和Monaco，2007）。 Sammarra等人（2007）通过将问题分为两部分来解决QCSP问题，即路由问题和调度问题。定义路由问题以确定每台起重机上的任务顺序，并且定义调度问题以确定属于每个顺序路线的任务的起始处理时间。研究的意义在于确定了任务间的优先约束和码头起重机的无干扰约束。 Kim和Kim（1999）指出，由于码头起重机在同一轨道上行驶，所以起重机之间可能出现阻塞情况。起重机只能前往船舱并在不受干扰的情况下执行任务。这项研究的目的是解决在安排多个码头起重机执行卸载和装载操作以及尽量减少操作完工时间方面的问题。后来，Kim和Park（2004）和Moccia，Cordeau，Gaudioso和Laporte（2006）也研究了QCSP，其中操作的预先限制和起重机之间的无干扰约束。而Lim等人（2004）假定QCSP是具有综合空间约束的任务 - 起重机分配问题，包括起重机之间的非干扰约束和邻域约束。作者还假定某些任务不能同时执行，因为为了避免车道中的拖车拥堵，必须及时分开执行为同一个场所执行的任务。提出了一个概率禁忌搜索和一个“吱吱声轮”优化启发式算法来解决这个问题，而动态编程算法被用来求解简化变量。
在解决QCSP中，Lee，Wang和Miao（2006）首先证明QCSP是NP完全的。许多研究人员提出了许多不同的启发式方法（Gambardella，Rizzoli，＆Zaffalon 1998; Vacca，Bierlaire，＆Salani 2007; Wang，Chen，＆Wang 2009）。 Kim和Park（2004）在混合整数线性模型中提出了问题，并采用分支定界（B＆B）方法和贪心随机自适应搜索程序（GRASP）进行求解。他们认为该船被划分为多个船舱，与同一船舶舱相关的卸货和装载作业分为不同的任务。目标是尽量减少操作的完成时间。研究结果表明，B＆B方法只适用于小型问题，一旦任务数量和码头数量分别增加到20和3，B＆B方法的计算时间迅速增加。 GRASP在合理的时间范围内确定了可行的解决方案，这些解决方案的中期规模问题没有超过最佳的10％以上。因此，研究建议GRASP解决实际的QCSP而不是B＆B方法。
后来，Moccia等人。 （2006）已经用Kim和Park（2004）给出的相同假设研究了QCSP，并对模型进行了修改，以巩固完成时间的下限和上限。提供有效的不等式来处理切割平面法。他们提出了一个分支和切割（B＆C）算法来解决这个问题。引入预处理技术来减小问题的大小，并引入分离启发式方法来识别违规不等式。在这项研究中，Kim和Park（2004）研究的问题集用于测试解，并且比较了使用B＆B方法和B＆C算法得到的结果。结果表明，B＆C方法优于B＆B方法，该算法能够处理实际问题的规模。
最近，Sammarra等人（2007）进一步研究了Kim和Park（2004）和Moccia等人研究的QCSP模型。 （2006）根据相同的假设提出。他们通过将问题分为两部分来解决QCSP问题，即路由问题和调度问题。路由问题被定义为确定每个起重机上任务的顺序，并且定义调度问题以确定属于每个顺序路线的任务的起始处理时间。他们提出了一种低级搜索算法来解决调度子问题和一种用于路由问题的禁忌搜索（TS）算法。通过使用与Kim和Park（2004）和Moccia等人研究的目标相同的目标。 （2006年），TS的结果与他们进行比较。与GRASP相比，TS的性能非常出色，但对B＆C方法的影响更大。 TS可以在合理的计算时间内获得中等尺寸问题的近似最优解。
3.问题描述和制定
本研究中所研究的码头起重机调度问题（QCSP）由K个码头起重机组成，用于服务| X | 任务数量，包括甲板上或舱内的装卸作业。 所研究的模型基于Kim和Park（2004）开发的模型以及Moccia等人所做的修改。（2006年）。
以下符号用于描述整篇论文中研究的问题：
相关指数
i，j任务索引，按照其相对位置的升序排列，以增加船贝数量。
K码头的索引，其中k = 1... K，安排在一个在他们的相对位置的升序增加船贝数量的方向。
pi任务i所需的处理时间。
rk码头起重机k的最早可用时间。
li由船湾表达的任务i的位置数。
0码头起重机k的起始位置由a表示
lk船贝编号。
T码头k的最终位置由船舶表示
lk船号码。
T连续两个托架之间的旅行时间。
tij码头起重机离开位置所需的行驶时间
任务i（li）到任务j（lj）的位置，tij = t | lj lj |。码头起重机k从初始位置到第一任务位置lj所需的行驶时间，tk0j = t jl0k ljj。码头起重机k从初始位置到第一任务位置lj所需的行驶时间，tkiT = t jli lTk j（tkiT = 0; 8i 2 X;表示完成最终任务后的旅行时间不是考虑）。
M足够大的常数。
a1分配给完工时间的加权（最大值
完成时间）在目标函数中。
a2赋予目标函数中完成时间总和的权重。
一套指数
X 所有任务的集合。
W 不能同时执行的一组任务。 我和j不能完成的任务
同时进行，eth;i; j）2 W。
U 有优先关系的一组有序任务。 任务i必须在任务j之前，eth;i; j）2 U。
决策变量
= 1，否则，如果码头k在执行任务i = 0后立即执行任务j。
码头起重机k的完工时间。 任务i的完成时间。
= 1，否则，如果任务j比任务i = 0的完成时间晚启动。
W完成分配的最终任务。
问题是如何确定如何分配起重机来完成任务，以尽量缩短完工时间，这是所有码头起重机中最大的完工时间。 在所有码头起重机完成分配给他们的工作后，船只才能离港。 目标函数如方程（1）。 问题描述与Kim和Park（2004）的模拟相似，如下所示。
组件包括完工时间和码头起重机完工时间的总和。 正如研究人员通常所采用的那样，a1通常设置为比a2大得多，这意味着完工时间是主要关心的问题。 此外，它的目标是在具有相同完工时间的解决方案池中找到码头起重机完成时间总和最小的解决方案。 码头起重机完工时间（Yk）包括空闲时间，行驶时间和处理时间。 任务处理时间固定，但空闲时间和行驶时间会影响码头起重机的完工时间。 因此，预计将选择码头起重机完成时间的最小总和的时间表，因为可以使更多的码头起重机尽快分配到其他船上工作。
问题约束
该问题受以下限制：
约束（2）确保完工时间等于码头起重机中最大的完工时间。 约束条件（3）确保每个码头起重机将分配一项初始任务。 约束条件（4）确保每艘码头起重机将分配最终任务。 约束条件（5）确保每个任务仅由一台码头起重机完成。 约束条件（6）确保每台起重机中每项任务的流量平衡，以便按照明确的顺序执行任务。 约束（7）确保任务j的完成时间应该大于任务i加上其在每个起重机中的处理时间和行驶时间。 约束（8）en-sure任务i应该在任务j之前完成。 约束（9）确保任务j的完成时间应该大于任务i加上其处理时间。 约束（10）确保每项任务和每台起重机的流量平衡。 限制（11）确保避免码头起重机之间的干扰。 约束（12）确保完成时间。每台岸桥相当于最终任务的完成时间加上到达最终位置的行驶时间。 约束（13）确保第二个任务的完成时间大于初始任务的完成时间加上其在每个码头起重机中的处理时间和行驶时间。 约束（14）和（15）将变量定义为二进制数。 约束（16）定义了非负性约束。 Kim和Park（2004）和Moccia等人发现了一个很好的约束解释。（2006年）。
图1提出的改进遗传算法的概要。
染色体编码
<t
全文共12189字，剩余内容已隐藏，支付完成后下载完整资料</t
资料编号：[15968]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
|
第一部分 |
第二部分 |
|||||||||||||||||||
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
