英语原文共 15 页
基于多代理系统的海港汽车码头车辆转运规划
T. Fischer , H. Gehring
摘要
提出一种支持进口成品车辆通过海港转运规划的多代理系统。重点是存储分配，即分配用于临时存储车辆的停车区域，以及部署调度，即将必须在码头区域移动的车辆分配给司机。这些计划任务实际上通常由不同的操作员执行，被分配给两种不同的代理类型。另一个代理，协调代理，负责将本地子计划组合成一个总体计划，以使计划期间对驾驶员的需求最小化和平衡。使用随机生成的问题实例来测试质量体系，这些问题实例在车辆流中具有不同的制造商份额分布。这些测试验证了MAS在问题数据变化方面的一定稳健性，特别是在长期雇佣的司机数量和雇佣司机的成本附加费方面。此外，调查结果显示，司机的最低总体(相对)成本取决于长期雇用司机的数量和雇用司机的成本附加费水平。
关键词：物流；供应链管理；多代理系统；遗传算法；启发式；车辆转运；海港汽车码头
1、介绍和问题描述
大多数进口到欧洲的成品车辆都是通过海港汽车码头处理的。这些码头有大型铺面停车场存放进入车辆的区域，直到车辆交付给承运人或运输公司。作为强化转运过程的结果，插槽瓶颈越来越频繁地出现。此外，可以看到进口车辆储存期延长的明显趋势。这给已经受限的存储位置增加了额外的负载。
通过海运到达的车辆在码头区卸货，然后存放在码头停车区，最后从仓库中取出来卸货。卸载、插入存储器、从存储器中取出和装载到载体上的任务受到相应的时间限制。严格遵守时间窗保证了车辆的连续流动。码头区通常必须在相对较短的时间内清理干净。一旦所有铺好的常规停车场都被填满，多余的车辆就会被存放在一个辅助停车场，该停车场的表面加固程度较低，而且比常规停车场离码头更远。在终点站，车辆由成群结队的司机驾驶。因此，终端操作成本非常高。终端自己的驱动器是根据班次使用的。在人员瓶颈的情况下，可以通过轮班雇佣的额外司机或全港口劳动力库中的小时雇佣的额外司机来补充永久司机。在这种情况下，每辆车的转运成本增加的方式与在辅助停车场储存车辆的方式相同。从终端运营商的角度来看，终端运营的效率是最高的优先级。目标是最大限度地减少和平衡计划期间轮班所需的驾驶员人数。
所描述的车辆转运问题具有高度复杂性的特点。因此，现代规划方法和工具会有所帮助。基于马特菲尔德和科普夫建议的方法(参见[8)，车辆转运问题最初被表述为一个计划问题，包括子问题、码头管理、储存分配和部署调度(参见[3-5))。码头管理问题是一个独立的子问题，旨在使卸货车辆尽快通过码头区。相比之下，存储分配和部署调度紧密交织在一起。因此，它们构成了本文的重点，本文引入了一个多代理系统来综合处理这两个子问题。为了明确重点，下面概述了与车辆处理相关的任务链，并阐述了集成存储分配和部署调度的问题。
图1示出了在交付之后，车辆被卸载到输入缓冲存储器中，从那里被带到终端停车区，临时存储在那里，被移动到输出缓冲存储器，并且最终被装载到用于运输到最终目的地的载体上。沿着这个所谓的任务链，车辆被分组处理。一个组由同一制造商生产的相同或相似类型的车辆组成，并且可能满足附加的分组标准，例如，一个组的所有车辆将交付给同一汽车贸易商。
图1 海港汽车码头车辆装卸任务链。
此外，车辆组的形成简化了车辆转运和操作任务的规划。成组搬运车辆的概念意味着车辆组存储在停车区域的互连部分。如果空载车辆组没有足够容量的自由互联区域，则尝试扩展其中一个自由区域。扩展可以通过重新定位来实现，即通过将存储在该自由区域的紧邻区域中的车辆组转移到其他自由区域之一。如果试验失败，车辆组必须存放在辅助停车场。因此，车辆总共可以通过三种类型的任务链:
任务链类型1：卸载-插入仓库-从仓库移除-装载；
任务链类型2：卸载-插入仓库-重新定位-从仓库移除-装载；
任务链类型3：卸载-插入辅助停车场-从辅助停车场移除-装载。
任务链上的操作受到上述时间窗口的限制。卸货的时间窗受到相应船只停靠和航行时间的限制。插入存储的时间窗口受下一艘要卸载到同一港口缓冲区的船只的到达限制，因为只有当缓冲区(部分)为空时，也就是说，如果从当前船只卸载的所有车辆都已进入存储区，下一艘船只才能在到达后立即卸载。经过更短或更长的存储期后，车辆将在受相应交付承运人到达限制的时间窗口内从存储区移走。承运人竞争对手的最后期限通常由货运代理人或客户确定。装货时间窗口受相应承运人的到达和货代或客户交货期限的限制。
对于每组进入的车辆，存储分配和部署计划包括一系列决策。这些决定涉及停车区和缓冲区的选择、任务卸载和插入的开始时间的确定等。，并确定执行这些任务的驱动程序数量。以下细节适用：
（1）用于空载车辆组的港口缓冲区在前面的码头平面图中确定。另一方面，输出缓冲器由承运人或客户固定。因此，存储分配仅限于选择用于插入存储和重新定位的停车区域，而不考虑缓冲区的选择。
（2）一组车辆的每一项移动任务(卸载、插入存储区、重新定位、从存储区移除和装载)都必须由指定的驾驶员执行，并在可行的八小时轮班之一内完成。如果一项任务的执行不限于一个班次，那么该任务必须由其他驾驶员在下一个可行的班次中完成。然而，改变驱动因素需要额外的规划和协调努力。必须将其他驱动程序分配给任务，并将任务的执行状态传递给这些驱动程序。可行的转移是那些完全或足够程度上位于各自时间窗口内的转移。“有效范围”是指班次和时间窗口之间的重叠足够长，足以完成任务。重叠的最小长度可以通过将移动各个组的所有车辆所需的总时间除以驾驶员组的最大成员数来计算。在重新安置的情况下，不可能事先设定可行的转移。规划过程显示了搬迁必须进行的转变。
（3）处理车辆组的顺序主要由车辆组卸载到端口缓冲区的顺序决定。该序列也应用于车辆组到存储器的插入，因为这样便于控制车辆流和清除端口缓冲区。
（4）为了计划和控制终端操作，移动任务所涵盖的工作量通常以所谓的驾驶员时间周期来衡量。让术语司机时间周期表示给定长度时间单位，例如15分钟。那么一个驾驶员时间周期就是一个驾驶员在15分钟内移动一辆车所需要投入的工作量。至于在不同停车区和缓冲区之间将车辆实际插入存储器、重新定位和从存储器中取出所需的时间，可以获得以分钟为单位的经验值。经验值也可用于将一组车辆从船上卸载到港口缓冲器上，这些值包括例如船上一组车辆的不同位置。类似的经验值可用于从输出缓冲器加载传送载波。
（5）移动任务包含的驾驶员时间周期数可以用图形表示为矩形区域，这里称为驾驶员时间周期区域。驾驶员时间周期区域一侧的长度与分配的驾驶员数量成比例，另一侧的长度由底层任务的运行时间给出。虽然一项任务的工作量是固定的，但相关驾驶员-时间周期区域的形状可能会根据驾驶员和车辆之间的关系逐步变化。驾驶员可以移动一、二、三等。任务执行期间的车辆。假设每个驾驶员同时移动相同数量的车辆，那么移动两个、三个等的操作时间。车辆有两辆、三辆等。是一对一关系的两倍。
（6）出于组织上的原因，用固定数量的司机来完成一项任务是可行的。实际上，司机通常被分成5到50名司机组成的团伙。为了限制操作时间，这里至少由两个驾驶员执行一项任务。因此，此处计划的驾驶员时间周期区域在驾驶员维度中的边长为2或更大。
集成存储分配和部署调度的问题现在可以用如下方式来表示(也参见[3-5])：假设有一组车辆组i，iisin;I。它们必须在给定的计划周期内处理，考虑到条件，该计划周期被细分为八小时轮班选项和上面显示的约束。假设c1i，i，iisin;I，是在执行任务链类型1时驾驶员处理第i车辆组的时间周期成本，c2ii，iisin;I，是在任务链类型2的情况下的相应成本，c3i，i，iisin;I，是任务链类型3的成本。假设x1i、x2i和x3i是二进制决策变量，如果为第i车辆组执行任务链类型1、2或3，则取值1，否则取值0。因为只能实现三个任务链中的一个，所以处理第i车辆组的成本ci= x1i *c1i x2i* c2i x3i* C3I （1）
其中x1i x2i x3i = 1， iisin;I。
目标函数是最小化驾驶员时间循环的总数TN，在计划期间必须计划转运第一组车辆组：最小TN=sum;ci，iisin;I （2）
此外，第二个优先事项旨在平衡规划期间轮班所需的司机人数。假设T是连续八小时轮班的次数，t = 1，...，T。在计划期间。此外，让^f t为第t班次中部署的最大和平均驾驶员人数。第二个目标函数是所有班次的最大驾驶员人数和平均驾驶员人数之间偏差平方的最小化。
最小SD=sum; （^f t- f t） （3）
本文的其余部分组织如下:第2节介绍了一个支持集成存储分配和部署调度的多代理系统。在第3节中，使用随机生成的测试实例对建议的多代理系统进行评估，在第4节中总结了本文。
2、用于集成存储分配和部署调度的多代理系统
实际上，存储分配和部署调度的子问题通常是分配给两个不同的决策者来协调他们的双边计划。决策能力的类似分布可用于本文考虑的综合规划问题的决策支持系统中。在过去几年中，多代理系统被推荐用于支持复杂的决策问题，这些决策问题可以分解为相互依赖的子问题(例如，[1，6，7])。在文献中，MAS应用于从生产和运输计划(参见[2，12)到业务流程管理(参见[7)的各个领域。然而，文献中还没有提出一种基于多智能体的方法来解决本文所考虑的问题。由于问题结构不同，斯特鲁维(参见[10)所描述的软件公司中用于支持人员部署计划的多智能体不能转移到给定的位置。下面将分两步介绍为支持集成存储分配和部署规划而开发的MAS。在第一步中描述了质量管理系统的体系结构，在第二步中指定了质量管理系统的操作。
2.1、多代理系统的体系结构
上述决策能力的分配是通过为存储分配和部署调度的每个问题分配特定类型的代理来实现的。虽然存储分配可以在整个规划期间由一个代理管理，即所谓的区域代理导入(AAI)，但基于班次的部署调度需要分散决策。因此，部署调度分布在多个所谓的轮班代理(SAs，s = 1，...，S)。轮班代理总是接管一个班次的计划。同时活动的轮班代理的数量取决于当前的计划情况。
在目标函数(2)和(3)的意义上，个体代理的本地规划的协调由规划协调代理(PCA)接管。常设仲裁院的任务取决于要协调的代理类型。AAI的规划能力仅限于优化
存储分配。因此，常设仲裁法院和AAI之间的协调关系被简化为一种客户/服务器概念。作为客户，主控制机构将每个车辆组的具体存储alloca问题提交给AAI，AAI将解决方案返回给主控制机构。相反，在车辆组的部署调度的情况下，相关联的任务链的每个任务通常可以在不同的班次中执行。因此，基于合同网络协议(参见[9)的拍卖机制似乎适合于选择轮班代理。此处使用的合同网络协议面向Zelewski引入的协调器变体模型，用于消除分散形式协调时出现的协调缺陷(参见[11)。因此，常设仲裁院承担了中央协调员的角色，为了管理车辆组的流动，中央协调员与停车场提供者AAI和驾驶能力提供者轮班代理人签订合同。MAS的最终结构如图2所示。
图2所示的体系结构显示了质量体系的三个中心特征(参见[3-5])。首先，规划问题的自然分散结构是以现实为模型的。其次，这里介绍的代理类型是追求不同目标的自治代理。第三，有一个机制，在此嵌入常设仲裁院，用于协调地方规划进程。MAS操作的后续描述规定了这些特征的概念和程序实现。
图2 用于存储分配和部署调度的多代理系统的体系结构。
2.2、多代理系统的操作
根据图3，可以区分MAS的大约六个活动阶段。初始化(阶段(1))和评估(阶段(6))之间的阶段重复执行，直到处理完所有车辆组。
在阶段(1)中，主成分分析用计划问题初始化。为此，一组用于中间存储的车辆组ⅰ连同相关联的时间窗口和分配的端口缓冲器一起提交给主控制器。
阶段(2)中车辆组的部署调度(粗粒度调度)是在单个任务的级别上进行的。应用的合同网络协议的三个交互步骤针对每个任务执行:邀请投标、提交报价和订单。在图3中，这些是与阶段(4)相关的步骤(2.1)、(2.2)和(2.3)。
图3 多代理系统的工作流序列。
(1)初始化主成分分析(车辆组集合、组特定时间窗等)。)。
(2)车辆组的部署调度(粗粒度调度):对于相应链中的每个任务，执行三个步骤:
(2.1)主成分分析确定可行的轮班代理并转移时间窗口的任务交给他们，
(2.2)主成分分析通行证接触的轮班代理向主成分分析提供，
(2.3)主成分分析选择最有利的轮班。
(3)车辆组的存储分配:
(3.1)PCA向AAI提交存储分配问题，
(3.2)AAI解决存储分配问题并返回解决方案回到PCA。
(4)车辆组的每个任务的部署调度(细粒度调度):主成分分析向所选最受欢迎班次的值班代理提交订单(见(2.3))，值班代理执行任务的调度。
(5)如有必要，常设仲裁院委托AAI更新停车场预订清单。lt;
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
