英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料
自动化集装箱码头不确定性条件下的自主跨运车大规模任务分配的再调度
作者：蔡炳煌，黄守东，刘帝凯，Gamini Dissanayake
中心的自治系统（CAS），工程和信息技术（FEIT），悉尼科技（UTS）的大学，邮政信箱123，百老汇，新南威尔士州2007年，澳大利亚学院
重点：
1，我们提出了在不确定条件下跨运车RNJ＆RCJ重新规划策略。
2，我们对每个短期规划使用精确的BBCG和近似的拍卖算法。
3，结果表明RCJ策略与RNJ策略相比的优越性。
4，长期测试表明需要为每个规划改进的解算法
文章信息：
文章历史：2012年9月3日收到
2013年12月8日收到修订的表格
2013年12月13日接受
2013年12月25日在线提供
关键词：
重新安排策略，不确定，优化任务分配，自主跨运车，自动化集装箱码头
摘要：
本文研究了在自动化集装箱码头的自主跨运车（SC）的集装箱运输任务分配的重新规划策略。该策略解决了不确定性（特别是与意外事件相关的不确定性，例如新任务的到达）的大规模调度的问题。在新工作到达的不确定性下，针对长期自主SC调度（ASCS）提出和比较了两个重新安排策略 - 重新安排新到任工作（RNJ）策略和重新安排新的和未执行工作（RCJ）策略的组合。使用多目标成本函数来评估两个重新安排策略的长期性能（即，SC运行成本，SC等待成本和完成高优先级作业延迟的总和）。该评估是基于两种不同的ASCS求解算法 - 精确算法（即，具有列生成的分支和绑定（BBCG）算法）和近似算法（即，拍卖算法） - 来获得每个短期策略的长期规划。基于实际全自动化的地图集装箱码头，模拟和比较结果表明RCJ策略的质量优势与RNJ策略相比，用于不确定性下自主跨越运输车辆的任务分配。长期测试结果还表明，尽管拍卖算法比实际应用的BBCG算法效率高得多，但是即使在上级RCJ策略中使用，也不足以在集装箱实现高质量的自主SC调度终端。
1，介绍
在过去几十年里，到达集装箱码头的集装箱船的容量和频率由于集装箱化和世界贸易的增加而稳步增加。相应地，集装箱码头需要尽可能快地转载运载更多集装箱的大型船舶，以提高生产率并降低码头运营成本。因此，终端具有多种不同类型的堆场资源以协助容器的移动，包括例如堆场车辆（用于在不同的堆场区域周围运输容器）和堆场起重机（用于在固定的小区域中运输容器在终端）。对现代集装箱码头来说，这些码头资源被有效地用于装载，卸载和在转运过程中。
堆场车辆在集装箱运输中起着非常重要的作用，因为它们比庭院式起重机更灵活，能够在堆场内自由移动。自主材料搬运车辆和机器人的快速发展促进了用于集装箱终端的自动化设备的开发和部署，诸如自动引导车辆（AGV）和自动起重车辆（ALV）作为堆场车辆。与人工操作的车辆相比，这些自动化材料处理机器人需要高度协调和高效率。自动化车辆车辆的有效操作因此成为一个基本问题，已经由机器人和物流的研究人员和工程师研究。已经提出了许多方法和方法，包括例如两个启发式方法 ,一个基于用于在高度自动化的集装箱终端处的AGV分派的灵活优先级规则，另一个基于用于派遣小队列的混合整数规划模型 ALV。研究了自动化集装箱码头的多个自主车辆操作的不同方法，如模拟退火算法，蚁群算法，竞争算法，作业分组和列生成。
图1：帕特里克·马特斯特拉德集装箱码头
帕特里克·马特斯特拉德集装箱码头（图1所示的全自动集装箱码头）使用一种称为自主跨运车（SC）的ALV。自主SC的操作在使集装箱运输增加终端的转运生产率方面发挥关键作用。SC操作的一个根本问题是SC任务分配。这被称为自主跨运车调度（ASCS）：为跨运车寻找可行和有效的调度以完成集装箱运输作业的列表。发现的时间表应该满足堆场车辆，转运工作和海港环境的关系和约束，以及满足终端操作的性能要求。由于大量的作业，大量的SC和复杂的终端环境，ASCS问题很难解决。已经开发并使用了调度算法来解决这样的问题，并且这些算法中的一些（例如，由作者开发的遗传算法和作业分组）已经或正在帕特里克·马特斯特拉德集装箱码头的实际操作系统中实现。这些方法基于近似方法，其可以得到可行的解，但可能不是最优的。注意，最佳调度可以大大降低集装箱码头的操作成本。已经为ASCS问题提出了基于列生成的精确算法以获得最优时间表。然而，这种基于列生成的算法对于大规模问题比近似方法更耗时。因此，为了提高算法效率和解决方案质量，仍然需要研究解决大规模ASCS问题的方法。
自主SC的任务分配问题的一个重要方面是自主SC的操作受到由于与真实世界的交互而发生的不确定性（自主车辆可以停止，延迟或面临诸如新工作到达的问题），因此工作和车辆计划需要重新计划。在动态容器处理环境中重建自主SC对于在面临意外事件时保持高生产力是必不可少的。因此，ASCS问题应该以能够对这种不确定性作出反应的方式来解决。最常见和最有效的方法之一是不时地使用基于作业的变化和SC的状态的更新信息来制定和解决小规模ASCS问题。在某种程度上，这类似于制造系统中的作业车间重新安排。已经调查了不同的策略和策略，例如新的工作重新路由，完整的重新路由，周期性重新安排和事件驱动的重新安排，以用于工作车间重新安排。动态重新计划方法已经由机器人和物流研究人员在集装箱码头重新布置堆场起重机和码头车辆进行了研究和开发。然而，它们的效率和有效性仍需要改进长期操作性能，特别是对于在不确定性下的自主SC任务分配中的应用。
本文重点研究在新工作到达的不确定性以及为自动化集装箱码头的操作提供相关指导方针的情况下，研究大规模ASCS问题的重新计划策略。开发了两个事件驱动的重新安排策略，并比较自主跨运车的长期任务分配以处理新的工作到达的意外事件：重新安排新工作（RNJ）策略（解决ASCS问题，新的到达工作只在每个计划）和重新安排新的和未执行的工作（RCJ）策略（解决与以前计划的计划中的所有新工作和未执行的工作的ASCS问题）的组合。为了评估两个策略的性能，以结合SC移动，SC等待的成本和通过加权因子完成高优先级作业的延迟的形式使用多目标成本函数。对于每个重新调度策略，可选地采用分支和边界列与列生成（BBCG）算法和简单的拍卖算法来在每个小规模规划中获得调度。基于帕特里克集装箱码头的实用地图进行模拟。这些证明了与用于大规模SC调度的RNJ策略相比RCJ策略的优越性能。他们进一步证明需要改进的拍卖算法来辅助大规模SC调度的优化，特别是在长时间水平。
本文的其余部分分为五个部分。第2节描述了不确定性下的大规模ASCS问题。第3节解释RNJ和RCJ重新安排策略。每个规划中的ASCS子问题的数学模型及其解算法在第4节中提供。模拟和比较结果在第5节中给出。第6节结束本文的最后说明。
图2：静态海港环境的示意图
- 不确定性下的大规模ASCS问题
帕特里克·马特斯特拉德集装箱码头（具有图1所示的卫星视图）是位于澳大利亚布里斯班的代表性自动化集装箱码头。图2示出了静态海港环境的示意图。海港可以被建模为具有18个380个位置节点和83155个预定义链路的堆场环境地图。能够独立地提升集装箱，从集装箱位置转移集装箱并且在目的地设置集装箱的自动SC机队在实际港口环境内操作，用于在不同的场区之间的集装箱运输。
ASCS问题被定义为将集装箱运输作业分配给跨运车，使得可以满足SC和作业约束，并且可以优化客观成本。对于每个作业，SC应该从一个位置拾取容器并将其传送到另一个位置 放下。如果需要，拾取和卸载操作应在给定的时间窗口内启动。在ASCS问题的解决方案中，不同的作业序列被分配给不同的SC，并且给定的作业仅被分配给一个SC。对于目标成本，可以在ASCS问题求解和SC运行性能评估中考虑不同核心资源的成本总和，如SC利用成本和高优先级任务的延迟成本。对于长期绩效，主要关注的是实际效益和成本，目标应该是最大化经济效益。因此，堆场资源的所有成本的单位需要相同（例如美元）。
在SC任务分配的现实中，通常有许多作业要分配给许多SC，因此ASCS问题总是大规模的。由于作业和SC的组合的大搜索空间，调度将非常困难或甚至不可能获得（特别是在实现最优解决方案的情况下）。根据，最佳地解决ASCS问题是整数规划问题，其是NPhard（非确定性多项式时间硬）问题。精确算法（例如，BBCG算法）只能有效地解决小规模ASCS问题，例如具有10个工作和3个车辆的问题。对于大规模ASCS问题，BBCG算法非常耗时，并且可能不能应用于实时操作情况。例如，花费2个多小时来获得40工作9车辆ASCS问题的最优解，这可能不满足在几分钟内解决实际SC操作的问题的要求。一般来说，精确（或甚至接近最优）解算法（例如，BBCG算法）对于自动化集装箱终端处的大规模SC任务分配问题可能不够有效。
除了大规模，自动化集装箱码头的SC操作的另一个特点是新任务的间歇性和意外到达。在规划开始时，可以在ASCS问题中考虑预期的新任务（例如，从船只或卡车卸载的运输集装箱）。然而，许多新来的工作是意外的任务，并且关于这些工作的信息是未知的，并且在计划开始时不能被考虑为ASCS问题。在这个意义上，ASCS问题不能一开始就解决。然而，注意，从问题的角度来看，新的工作到达不改变ASCS问题，并且不增加解决ASCS问题的难度。相比之下，从运营的角度来看，新工作确实影响到运营，需要以不同的方式处理。
重新安排通常并且有效地用于处理大型ASCS问题和用于大型跨运车队的操作的动态新作业到达。大规模ASCS问题可以分为小规模子问题，用于根据作业到达时间进行规划。在每个规划中，可以制定和解决小规模ASCS子问题，显着减少计算时间并有效处理大规模SC任务分配的新作业到达的不确定性。此外，在自动化集装箱终端的操作中，长期操作性能（例如操作成本和生产率）是评估多SC系统的操作的功效的关键。由于未预测的事件，尤其是新的工作到达，频繁地发生，在实际实施的跨运车系统中使用简单的重新计划策略。但是，当重新计划应当被触发时，哪个重新制定策略执行得更好，并且重新计划策略在长时间范围内可以执行的程度仍然需要确定。
- 重新安排策略
为了解决上述问题，提出了两种事件驱动的重新安排策略，并在自动化集装箱码头的作业到达不确定性下比较自动跨运车的大规模任务分配。这两个重新安排策略是重新安排新工作（RNJ）策略和重新安排新的和未执行的工作（RCJ）策略的组合，下面给出详细的描述。
3.1 RNJ策略
在新工作到达时，RNJ策略仅解决新到达作业的ASCS问题，并保持计划的时间表不变。假设n新的新作业在时间t到达，RNJ策略将用新的作业数n = nnew来解决ASCS子问题（在下一部分中建模）。注意，由于在本文中在整个调度操作期间考虑相同的SC组，所以SC s m的数目在重新调度中不变。在新的ASCS子问题中，SC v的初始位置被更新为先前计划表中的SC v的最终位置，即，分配给先前表中的SC的最后作业的下降位置;而SC可用时间被更新为分配给SC v的先前计划进度的结束时间，即在分配给先前进度表中的SC v的最后作业的下降位置处的SC v的服务时间。可以基于新到达作业的信息来更新用于新ASCS子问题的其他参数（例如，操作时间窗口和SC旅行时间）。然后，可以通过解算法（例如，将在下一部分中开发的BBCG算法或拍卖算法）来求解新的ASCS子问题，以获得新作业的新调度。
3.2 RCJ策略
在新作业到达时，RCJ策略利用来自先前计划时间表的新到达作业和未执行作业来解决ASCS子问题，并且正在执行的作业（即，在新作业到达时执行的作业）将保持不变，不会在新的重新计划中考虑。假设nnew个新作业在时间t到达，并且在时间t的计划时间表中还没有执行nunexecuted个作业，则RCJ策略将使用新的作业数n = n new n unexecuted来解决ASCS子问题。在新规划的新ASCS子问题中，SC初始位置（SC可用时间）是SC在先前计划时间表中正在执行的作业的准备位置（完成时间），或者是如果SC已经完成了所有分配的作业，则将上一作业分配给上一个计划中的SC。可以基于新到达作业和未执行作业的信息来更新用于新ASCS子问题的其他参数（例如，操作时间窗口和SC旅行时间）。然后，可以通过用于新的和未执行的作业的ASCS解算法（例如，BBCG算法或拍卖算法）来解决新的ASCS子问题。
总之，RNJ策略是简单地修复已经计划的时间表，并且仅利用可用的跨运车计划新到达的任务（未调度的任务）。RCJ策略是固定已经执行的任务并且不变地执行，并且与新到的任务（未调度的任务）一起重新安排所有未执行的任务（在先前计划中安排的）。正在执行的工作将保持不变，并且不会在新的重新安排中考虑。对于RNJ策略，我们可以说，当前调度留在执行的地方，并且使用可用资源（即，跨运车）重新调度新到达作业。对于RCJ策略，先前调度中的未执行的作业将与当前调度中的新作业一起重新调度，这是一种回溯。值得一提的是，在实践中，跨运车的调度是实时操作的。一旦跨运车正在执行作业，它将无法更改作业，并且在作业完成之前它不会是空闲的。因此，目前正在执行的工作在两种策略中保持不变。此外，两个重新调度策略都是由新任务到达的事件触发的。将应用BBCG算法和拍卖算法来获得用于每个规划（即，ASCS子问题）中的确定性任务分配问题的最优解。此外，当新任务持续长时间到达时，将使用多个目标成本函数，SC运行，SC等待的成本和高优先级任务的延迟一起用于评估所呈现的策略的长期性能。注意，用于新调度的资源（即，跨运车）可以在当前时间以及稍后的时间可用。在下一节中的ASC
全文共17448字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[144181]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
