自动化集装箱码头起重机、车辆和存储平台集成调度优化的代理算法
摘要
在集装箱码头中，集装箱通常使用堆场起重机相互叠放在堆场中。分离平台存储/检索系统（SP-AS/RS）的发明是为了更有效地存储容器并更快地访问它们。利用以往文献中的模拟退火算法，建立并求解了SP-AS/RS码头起重机、自动导引车和装卸平台的综合调度问题。本文提出了一种更精确的遗传算法来解决这一问题。该遗传算法包括一个新的运算符，用于生成一个随机的任务字符串，观察任务之间的优先级关系。为了评价EGA的性能，采用该方案对10个小型试验箱进行了处理，并将结果与文献中的结果进行了比较。结果表明，本文提出的改进方法比现有的模拟退火算法有更好的改善效果，而且当调度中的任务数增加（如30到100个）时，该算法不能达到现有算法的要求。
本文的特色：提出了一种处理和存储设备集成调度的遗传算法。测试了遗传算法的控制参数。将所提出的遗传算法与先前开发的算法进行了比较。在大规模测试案例中，研究了集成和非集成调度方法。研究了存储平台的三种不同驻留点策略。
关键词：综合调度；遗传算法；自动导向车辆；码头起重机；分平台自动存储/检索系统
- 绪论
随着世界贸易市场每天解决更多的障碍，集装箱对于将货物从国家和大陆运输到世界任何地方变得更加重要。许多研究人员认为，在世界各地，集装箱码头面临着不断增加的运输能力激增的压力，以及快速周转船只的需求。集装箱装卸设备的自动化是对不断增加的集装箱运输量的反应。为了降低运营成本，特别是降低人工成本，并提高集装箱码头的吞吐量，引入了自动化集装箱码头（ACT）。近年来，集装箱码头的现代布局被认为是提高其性能的一种解决方案。例如，IMAI、Nishimura和Papadimitriou开发了两种新的集装箱码头布局设计，以服务大型集装箱船；Zheng、Lu 和Sun 改善了ZMPC⃝R 特别为集装箱自动装卸系统而设计的在布局中移除了车辆的一种启发式的堆场分配和装载计划算法。但是，Yu、 Cai和Zhao表示，除了实施先进的搬运和储存设备外，新的策略和调度方法还将提高ACT的性能。
在ACT中，船舶停靠在泊位上，并向船舶分配预定数量的码头起重机（QCS或简单的起重机）。在码头的另一侧，在堆场中，集装箱通常使用自动堆垛起重机（ASC）堆叠在一起，而自动导向车辆（AGV或简单的车辆）连接泊位和存储区域。陈、黄、许、图、乐等提出了专为集装箱装卸而设计的分平台自动存储/检索系统。该存储系统使用单独的平台进行高速垂直和水平移动，分别称为VPs和HPs。计算结果表明，与传统堆场相比，该堆场的占地面积利用效率更高。Hu、Huang、Chen、Hsu、Toh、Loh和Song[9]以及Vasili、Tang、Homayouni和Ismail使用三种不同的停留点策略（即停留、返回中间和返回启动策略）计算了SP-AS/R的预期旅行时间。Vasili、Tang、Homayouni和Ismail表明，与其他策略相比，停留在原地的停留点策略获得了较低的预期旅行时间。
综合调度法是近年来提高ACT性能的最新策略之一。集装箱码头两台设备的综合调度是文献中的一个共同研究领域。例如，Wu、Luo、Zhang和Dong提出了仓储作业和车辆的综合调度，Homayouni和Tang 提出了起重机和车辆综合调度的混合整数规划（MIP）模型和遗传算法，Chen、Langevin和Lu为起重机调度和堆场卡车作业开发了一种综合方法。另一方面，在文献中，三种设备的综合调度在处理和存储操作中得到较少的考虑。Meersmans和Wagelmans似乎是研究人员考虑起重机、车辆和ASC综合调度的第一人。由Chen、Xi、Cai、Bostel和Dejax制定了起重机、堆场卡车、堆场起重机综合调度的MIP模型。此外，Liang、Lu、Zhou提出了起重机、内卡和堆场起重机综合调度的MIP模型。他们认为卡车不是调度过程的瓶颈。因此，将著名的约翰逊规则应用于两个独立进程集的调度问题。Zeng和Yang 针对这个问题开发了一种混合仿真优化方法。利用神经网络算法对所提出的序列的目标函数进行预测，并将潜在的不良解过滤掉，从而减少所需的仿真时间。
在上述文献中，船舶的装卸任务是假设单独执行的。然而,Liu和Zhao表示，为了减少车辆的空行，可以根据起重机的预定任务列表，同时对船舶执行装卸任务。Liu和Zhao制定了起重机、车辆和ASC的调度计划，将起重机任务的延误以及ASC和车辆的行驶时间降到最低。首先，SP-AS/RS参与了Homayouni、Vasili、Kazemi和Tang的集装箱装卸和储存设备综合调度。他们将该问题定义为MIP模型，并开发了模拟退火算法（SAA），以最小化SP-AS/RS中平台和车辆的移动时间，以及起重机装卸任务的延迟。
本文的主要目标是提出一种遗传算法来优化起重机、车辆和SP-AS/RS平台的综合调度，该遗传算法在较低的计算时间内找到了该问题的近似最优解。对所提出的遗传算法的控制参数进行了研究，并将其性能与Homayouni、Vasili、Kazemi和Tang开发的MIP模型及其所提出的SAA的最优解进行了比较。在最后一步中，本文将研究Vasili、Tang、Homayouni和Ismail提出的停留点策略。
第2节描述了SP-AS/RS起重机、车辆和平台的综合调度。第3节专门描述了对遗传算法原理的简要回顾。此外，本文还提出了一种优化综合调度问题的遗传算法。对所提出的遗传算法中使用的参数进行了几个测试，结果在第4节中报告。此外，将所提出的遗传算法的近似最优解与文献中的近似最优解进行了比较，结果在第4节中进行了描述。除进一步研究的建议外，最后的注释和结论性评论见第5节。
- 问题定义
船舶作业主要包括卸载和装载任务。卸船任务是将集装箱从船上卸下并存放在堆场的一系列操作。在卸载任务中，起重机从其停留点移动到船舶上。起重机可以在货舱内移动集装箱，并拾起所需的集装箱。
集装箱被运上岸装上汽车。在旁边，车辆从停留点移动到起重机。一旦起重机将集装箱运送到车辆上，它就可以开始下一个分配的任务。在其第二部分行程中，车辆移动到SP-AS/RS。卸载任务中集装箱的目的地是SP-AS/RS中的一个存储单元。该单元的位置指示当前任务专用的HP。在卸载任务中，VP从其停留点移动到装载/卸载站（L/U），从车辆上接收集装箱。在运送集装箱后，车辆准备好执行其下一个分配的任务。加载的VP将移动到专用行，并将集装箱移动到HP。与此行程同时，HP从其停留点移动以接收集装箱。集装箱的最终行程由HP执行，HP将移动到预定的存储单元，并将集装箱放置在那里。在相反的方向上，装载任务是将集装箱从堆场卸下并装载到船舶上的一组操作。注意，应根据起重机任务的优先关系执行任务。例如，起重机的第二个任务不能在第一个任务完成之前执行。
Homayouni、Vasili、Kazemi和Tang将SP-AS/RS起重机、车辆和平台的综合调度问题制定为MIP模型。他们研究了三种不同的启发式规则，将车辆分配给起重机的任务，并得出结论：最早可用车辆（EAV）在三种启发式规则中获得最佳性能，因此，本文也将EAV启发式规则应用于车辆分配。调度方法的有效性对为其所做的假设非常敏感。与Homayouni、Vasili、Kazemi和Tang一致，在优化问题时，必须牢记以下最重要的假设。
bull;在SP-AS/RS和船舶中的装载和卸载任务集及其起点和目的地是预先确定的。
bull;SP-AS/RS中用于卸载任务的预定存储单元为空。
bull;打算装载上船舶的集装箱已提前放置在SP-AS/RS中的相应存储单元中。
bull;装卸起重机、车辆、HPS和VPS的运输时间相同。
bull;不考虑引导路径中车辆的拥挤。
bull;该行为中各类设备(如起重机和车辆)之间的转移时间假定为确定性的，其小到可以忽略不计。
bull;所有类型装卸设备（即起重机、HPS、VPS和车辆）的停留点策略为“原地待命”，即它们的最后一项任务已完成。
- 遗传算法
优化集装箱装卸和仓储设备的综合调度，对于保证港口管理部门充分利用集装箱装卸和仓储设备的整体能力至关重要。然而，集成调度是非确定性多项式困难问题，即，没有系统的方法来找到这个问题的最优解，特别是对于相对较大的实例。这些数学方法无法在合理的计算时间内为大规模的集成调度问题找到最优解。因此，提出了元启发式算法（即遗传算法）来寻找该问题的近似最优解。
3.1 GAs的原则
遗传算法是一种著名的遵循自然进化过程的元启发式算法。Haupt和Haupt指出，与其他任何元启发式算法一样，GAs不能保证找到最优解。GAs通过定义优化变量、目标函数和控制参数开始。通常情况下，GAs接收工作的初始群体包括由“染色体”表示的单个解,这些“染色体”是包含所有与可能的解决方案有关的基因（即变量）。“染色体”的评估基于“目标函数”，这是问题的预期目标。
在遗传算法的任何迭代中，一些当前的个体都被新生成的后代所取代。“交叉率”被定义为任何迭代产生的后代数量与种群大小的比值。从当前种群中选出一对个体作为一对后代的父母。相对于整个群体而言，高度适合的个体在下一代被选为父母的几率更高，而不太适合的个体被选为父母的几率相对较低。
最广泛使用的一种选择方案称为“偏置轮盘赌方案”，其中，种群中的每个当前字符串都有一个轮盘赌槽，其大小与适合度成比例。轮盘赌方案可以描述如下：
bull;对所有人口成员的适合度进行求和;这个结果叫做总适合度。
bull;生成介于零和总适配度之间的随机数theta;。
bull;返回第一个人口成员的累积健身大于,或等于theta;。
重复上述步骤，根据交叉运算符的需要选择尽可能多的父级。另一种流行的选择方案是“锦标赛”程序，其中随机选择两组具有n个成员的个体。选择每个集合中最好的个体作为父对象。对于交叉操作员所需的任何数量的父级，重复此过程。
突变是另一种应用于后代和父母身上的遗传算子。实现了变异算子，保证问题解空间的每一个子空间都能被选择。“突变率”是指基因总数(包括父母和子女)在人口中的百分比。在GAs中，突变算子起着至关重要的作用，首先是替换种群在选择过程中丢失的基因;第二，提供原始种群中不存在的基因。在调度文献中，遗传算法的应用常常使用交换变异算子。但是，出现的问题可以通过使用维修操作员来解决。“交叉”算子和“变异”算子被广泛应用于繁殖新的后代，它们分别负责可行解空间的探索和利用。据称，GAs的探索和开发能力是解决非确定性多项式困难问题的最基本的手段。
本文提出的遗传算法可以确定起重机的任务顺序和SP-AS/RS中的操作流程。但是，正如前面提到的，车辆是通过EAV启发式规则分配任务的。Homayouni、Vasili、Kazemi和Tang提出了建议的GA的目标函数，以最小化SP-AS/RS平台的行驶时间和起重机装载和卸载任务的车辆和延迟。图1说明了所提议的遗传算法的各种运算符。以下各节介绍了这些运算符的详细信息。 选择迭代次数作为GA的停止标准。
3.2 染色体和初始种群
该遗传算法的染色体是由起重机执行的一串可行的任务。根据起重机编号(即1到K)和每个起重机的任务编号(即1到Q)对任务进行排序。接下来，对任务进行从1到N的整数编号(由式(1)计算)，其中T是QC的第i个任务，O是SP-AS/RS的第m个机架的第N次操作。图2给出了该编码系统的一个示例。该编码系统中的染色体是起重机任务的可行序列。在这种方法中，任务按顺序编号，相同的整数表示各自的SP-AS/RS操作。参照图2，例如整数“1”表示染色体解决方案中的T和O。
起重机、车辆和存储平台综合调度的最重要约束是起重机任务之间的优先关系。因此，如果满足这个约束条件，解是可行的。以图2为例，有4台吊车，每台吊车执行5项任务，5个储物架，每台吊车执行4组作业。在该样本染色体(如父染色体1)，整数根据起重机任务的优先关系排序(如任务1在任务2之前，任务14在任务13之后，任务15之前，等等)。
为了创建遗传算法的初始种群，生成从1到N的随机数字串。由于任务优先关系的暴力，此字符串可能不可用。提出了一种任务排序的修复算法，使字符串成为一个可行的字符串。在第一步中，字符串中的所有单元格搜索任何起重机的任务。单元格的值被设置为表示各自起重机的第一个任务的整数。例如，第一个起重机的所有任务都设置为1。在接下来的步骤中，从左到右找到这些替换的初始数，并将1添加到第二个数，2添加到第三个数，以此类推，最后将Q-1添加到最后一个数。该算法的结果是一组随机可行的装卸任务随机串，观察了起重机任务之间的优先关系。图3给出了伪码生成可行染色体的算法。重复该算法直至创建与初始种群数量相同的染色体。
3.3 选择方案、交叉和变异运算符
一旦利用目标函数对所有染色体进行评估，当前种群就按升序排列。基于交叉率，一些最不合适的解被一组新的子解所取代。为了繁殖任何一对后代，从当前种群中选择一对染色体作为亲本。提出的遗传算法采用轮盘赌或锦标赛方案，在对所提出的遗传算法进行进一步分析之前，根据其性能确定最佳选择方案。
该交叉算子的设计目的是为了交配亲本，繁殖后代，并观察起重机任务的优先关系。在交叉操作中，随机选择一台起重机。然后，属于这个起重机的任务在父染色体中突出显示。将父1中此起重机的任务复制到子2的匹配位置，将父2中的相同任务复制到子1的匹配位置。子代1中其余的位置由未选择的鹤按照父代1中出现的顺序从左到右完成任务。同样的过程产生第二个后代。
在遗传算法的下一步中，使用变异算子来保证搜索空间中所有的多样性都能被搜索到，虽然集成调度问题的解空间过于粗糙，但变异算子对于避免过早收敛（收敛到局部最优）是很重要的。在本文提出的突变算子中，运用并改进了交换突变算子的基本原理，其中随机选取了一条属于当前群体的染色体。在这
英语原文共 9 页
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
