基于配对/非配对协同策略的集装箱码头智能自动驾驶车辆的调度
Shahin Gelareh，Rochdi Merzouki,
KayMc Ginley ，Roisin Murray
重点
- 介绍了一种新的集装箱运输技术。
- 提出了集装箱运输调度的数学模型。
- 提出一个十分有效的具有启发式的拉格朗日分解法。
- 以都柏林利菲码头为例进行实证研究。
- 开发一个离散事件仿真平台。
摘要
在由欧盟资助的动态环境(InTraDE)项目的智能交通框架下，设计了一种新型智能自动驾驶车辆(IAVs)。在许多方面，这种类型的车辆在技术上优于现有的自动导引车辆(AGVs)。在封闭空间内进行物流作业时，它们在机动方面提供了更多的灵活性和智能。这包括使一对1-TEU(20英尺等效单位)IAVs，能够动态连接，运输1-TEU和1-FFE(40英尺等效单位)之间的任何大小的容器，并再次断开连接的配对/非配对能力。配置IAVs有助于港口运营商保持高效率，以应对港口日益增长的集装箱运输量和消除在港口非常有限的区域配置更多40英尺长的运输车辆的需要。为了适应IAVs的这一新的特点，我们对现有的AGV调度混合整数规划模型进行了回顾和扩展，以使码头起重机和堆场起重机之间运输一组不同尺寸集装箱的最大完工时间最小化。我们以都柏林利菲港码头为例进行了研究。为了解决调度模型的复杂性，我们提出了一种基于拉格朗日松弛分解的方法，该方法具有一个变量修正过程和一个原始启发式算法，以获得问题实例的高质量解决方案。
关键词：智能自主车；自动导引车；混合整数规划：调度；拉格朗日松弛法；离散事件仿真
目 录
1.绪论 1
1.1目标和贡献 3
1.2文献综述 3
2. 问题陈述 5
3. 数学模型 6
3.1 参数 6
3.2决策变量 6
3.3智能自动车辆(IAV)调度 7
3.3.1有效的不平等 9
4. 解决方法 10
4.1 IAVS的拉格朗日分解 10
4.2.1分解 13
4.2.2求解子问题的算法 14
4.3变量修正 16
4.4原始束缚 16
4.4.1初期解法 17
4.4.2邻域结构和移动策略 17
5.数值结果 19
5.1CPLEX和有效不等式的效率 19
5.2 拉格朗日松弛与局部搜索 22
5.3与当前港口实践进行比较 24
6.总结、结论及对今后工作的展望 27
致谢 28
附录A 28
参考文献 29
1.绪论
国际贸易量不断增长，其中高达90%是完全集装箱化的，要求对整个供应链网络的物流运作中出现的其他几个问题采取适当的解决方案。
大量集装箱的流通目前正在三条主要航线上进行：(1)亚欧航线；(2)跨太平洋航线；(3)跨大西洋航线。全球共有500多个港口和数十家班轮航运公司参与航运物流。
由于密集的互动和全球集装箱运输系统组成部分的空间分布，系统中各个元素(包括班轮服务提供者和港务局的观点)的低效将局部和暂时地使其负面影响传播到整个系统网络。
从班轮航运业的角度来看，需要更大的船舶来帮助服务提供者从运输日益增长的货物量的规模经济中获益。配置这些船舶是非常昂贵的(通常每天超过几百万美元)，事实上，船舶只有在航行期间，才能为船东带来利润。航线上停靠在不同港口的航次时间称为整个航次的周转时间，实际上是服务中无利可图的部分。因此，除非在长途运输中，否则规模经济不可能得到利用。这意味着班轮服务提供者(LSPs)通常不会发现沿着一个服务循环停靠太多港口是有利可图(所谓的“字符串”)。因此，一些主要的转运枢纽，也就是集散港正在发挥作用，并为他们地区的其他较小港口提供代理服务。这些港口的选择取决于几个不同的因素。其中最重要的是效率和基础设施——当然，假设一个港口有潜力成为一个枢纽港，也就是，它有足够的吃水来容纳更大的船舶，并且满足更多的生态政治标准。
从港口运营商(相当于码头运营商)的角度看，他们的竞争力本质上取决于它们在最大限度地提高港口吞吐量的同时，将船只的周转时间降至最低的能力。通过这种方式，他们可以与其他邻近港口竞争，并在这样一个高度竞争的市场中生存下来。由于竞争的动态性和规模，除非在港口的战略、战术和操作上方面进行更好的审查和处理，否则就无法实现这一目标。这包括三个主要方面::(i)布局和设备；(ii)路线决策；(iii)机器调度和资源分配。
自集装箱化和集装箱化运输开始以来，开发了几种不同类型的港口设备。这包括各种类型的起重机(码头前沿和堆场前沿)和载运工具(例如单载运工具和多载运工具，具有和不具有起重能力)，具有非常不同的物理和机械特性。
随着信息和通信技术(信通技术)的增强，自动化和半自动化基础设施的概念出现，港口当局开始逐步实现公司。 调整信通技术工具，以提高其效率。目前，欧洲集装箱码头(ECT)、新加坡港务集团港口、台湾高雄港、韩国釜山港、日本川崎港和鹿岛港、英国泰晤士港，德国布雷默哈芬港和汉堡港，以及比利时安特卫普港，都是世界上自动化程度最高的集装箱码头。
全球各地都出现了类似的趋势，有几个项目得到资助，用于开发港口新技术。其中，具有一定智能和自主性的车辆，同时，它们也利用信息和通信技术，配备了几种传感器以及地理信息系统(GIS)工具(例如见InTraDE 1)，这具有特殊的意义。
虽然枢纽港口之间存在着通过提高效率来吸引更多客户的激烈竞争，但这种竞争不仅局限于枢纽港口。 较小的港口(如我们这里的都柏林利菲码头(DFT))在当前进出口量增加的趋势下，关心的是运营效率。 当知道DFT(和该地区的许多其他港口一样)几乎不可能扩建其码头时，情况变得更加严重，原因有几个，包括政治原因以及周边土地使用和基础设施有关的原因。他建议投资于先进的技术开发，最终将导致更高效的设施(包括运输工具和码垛/拆垛机)。
智能自动车辆(IAVs)(如图1所示)是在InIraDE框架下设计的一种新型运输车，它概括了AGVs的概念。下文列出了IAVs的一些显著特点:
- 与AGVs相比，IAVs不需要遵循已签署的路段到达目的地，也不需要遵循特定的行程。 相反，它们是MIMO(多输入多输出)系统，配备多个传感器，使它们能够受益于基于地理定位系统(GPSs)的导航系统和其他几个传感器，以检测到与其他车辆的距离，等等。
- IAV的单位容量为一个TEU，对于运输1-TEU和1-FFE之间的任何集装箱尺寸，两个IAVs可以以领导者-追随者的方式耦合，从而产生40英尺的容量，能够运输相关尺寸的集装箱。在装卸作业的时间范围内，IAVs可以配对和再次配对的次数没有限制(图1a为20英尺的单IAV，图1b为40英尺的成对IAVs)。
- IAVs可以基于领导者-追随者的方式形成排，每一个IAV都可以在运行期间的任何时间点成为领导者或追随者。
- IAVs可以横向和纵向移动。与普通运输车辆(如AGVs和卡车)相反，IAVs不需要更大的空间来操纵。它的车轮提供360度旋转灵活。
- 最后，一个IAV系统应该自我调整以周围的环境。而在AGV系统中，这是必须适应它们的现有环境。
图1所示：智能和自动驾驶汽车(IAVs)
尽管全球共有数百个港口出现在班轮运输网络上，但为主要港口提供服务的LSPs却寥寥无几。因此，专业文献和学术文献而言，关于港口码头运营优化与仿真的研究已经有了较大的语料库。
1.1目标和贡献
本文利用Ng等人(2007)提出的AGVs模型(进行了进一步的技术修订，有关说明见附录A)。 并说明它可以推广到AGVs和IAVs两种情况下。 然后，我们研究了一类有效不等式对用于解决问题实例的通用求解程序的计算性能的影响。 作为大多数调度问题的一个固有特性，只有非常小的实例才能被通用的解决程序有效地解决。 因此，我们提出了一种基于拉格朗日松弛分解的方法，该方法具有变量修正和原始约束生成启发式(利用问题对偶的信息)，在合理的时间内求解高质量的实际问题。 利用拉格朗日方法，识别并松弛了若干类违反有效不等式，以加快收敛速度。 作为一个案例研究，我们将该模型应用于爱尔兰的都柏林利菲码头，爱尔兰是InTraDE的合作伙伴码头之一，IAVs正是为其设计的。
1.2文献综述
如前所述，IAVs在技术上更先进，但与AGVs非常相似。也有许多不同之处，如独立于探测地面上的标志，以便跟踪路径，车轮原地旋转90°的能力、领导者-追随者行为等方面，都与路径选择问题更为相关。然而，参与和合作执行任务的能力对调度和最大完工时间最小化是有意义的。运筹学文献对集装箱码头和制造系统中的AGVs调度方面有一些贡献。
Meersmansensp;andensp;Wagelmans(2001b)，ensp;Meersmansensp;andensp;Wagelmans(2001a)提出了一种AGV与起重机组合分配问题的启发式算法。
Grunow等人(2004)提出了一种基于优先级的在线物流操作控制方法，并与离线方法进行了比较。Grunow等人(2007)对自动化集装箱码头中的AGV进行了仿真研究，以检验不同调度策略的效率。
同样，AGV调度和堆场分配可以参考Bishensp;etensp;al.(2001)；ensp;Bish(2003)将这一工作扩展到考虑码头起重机的装卸调度计划。 Bish等人(2005)对Bish(2003)的工作进行了扩展，并对所提出的算法增加了一些分析性能研究。
Cao等人(2010)针对只考虑进口集装箱的综合堆场卡车和堆场起重机调度问题，提出了一种MIP公式。 他们开发了一个组合弯曲分解来解决他们模型的实例。
Lee等人(2010)研究了一个同时考虑装卸集装箱的转运港。虽然它经常被其他作者简化，Lee等人(2010)也考虑了堆场起重机的延迟。目的是尽量减少码头前沿作业的最大完工时间，以减少船舶的周转时间，因为只要码头起重机完成最后一项作业，船舶就可以离开码头。他们提出了一个MIP公式，但使用了两种启发式方法来解决这个问题。Lee等人(2010)的工作是基于Chen等人(2007)，但他们考虑同时装载和卸载。
Ng等人(2007)提出了一个MIP模型，该模型用于在假设车队规模为外源给定的情况下调度集装箱码头的车队。
他们比较了几种遗传算法的变体，发现它们的变体性能优于其他所有变体。
虽然必须强调的是，他们提出的MIP模型并不是他们的解决方案方法的基础(除了解决方案质量评估)，但是，如附录A使用的一个直观的例子所示，Ng(2007)等人的模型，并不总是对AGVs调度问题产生一个可行的解决方案。
集装箱码头不同设备调度的其他工作可以在Kim a
英语原文共 10 页
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
