基于时间窗的自动化集装箱码头多载AGV调度研究

田吕 高燕 黄昕 祝润泽 申淑丽 廖伟东

1.广州机械科学研究院有限公司，中国·广东 广州 510700

2.国机智能科技有限公司，中国·广东 广州 510700

1 引言

随着全球经济和科学技术的快速发展，作为维系社会经济运行的基础产业——港口发展也愈加快速，港口不但提供中转、装卸和仓储等功能，而且提供客户贸易和金融等服务，同时拉动了多式联运的发展。可见目前港口已是国际市场交接点，将货流、商流、资金流、信息流进行全面的融通，特别是对国民经济和区域发展方面等起的作用越发重要。其中集装箱码头作为整个港口系统的枢纽站也正发生着从传统的运输模式向综合物流的转变，提高了码头的周转能力和港口运输的效率，使港口相关功能得以不断提升和优化。

伴随综合物流时代的到来，中国经济发展已进入沿海经济与内陆经济协同发展的新时期,江河海运一体化开始成为长江航运发展的新常态，为打造成重点突出、合理分工、层次分明的世界先进港口，通过产业集群的方式提升整个区域的竞争能力已成为必然趋势[1]，这不仅需要在硬件方面达到世界先进水平，更要求中国在集装箱软件管理方面拥有自主创新的技术[2]，因此实现AGV 联合优化调度是进一步提升码头效率的迫切需要[3]。论文重点研究动态作业面调度模式下，装卸作业并行工作，同时基于调度原则、速度设置、交通规划即路径设置对多AGV 展开全面分析，并利用遗传算法对模型进行求解，利用Matlab 软件对其进行计算与验证得出最优调度方案。

2 自动化集装箱码头多AGV 调度系统

2.1 自动化集装箱码头AGV 调度原理

在集装箱自动化码头中，中央控制室生产过程控制系统（Process Control System,简称PCS）利用无线区域网络监控着AGV 的运行状态，并进行数据判断与传输，下达正确的任务指令。由于每个码头的机械设备配置、容忍参数、利用率等性能参数的不同，导致AGV 调度方法也需相应调整，调度决策的科学性也直接影响AGV 的承载率、耗能率以及及时性，同时AGV 运输集装箱的目的不仅仅是将其运载到指定的堆存处，更需要将其时间约束、运输路径、装载成本考虑在内，因此多AGV 水平运输的调度系统主要考虑以下三个方面。

（1）合理假设避免资源浪费，论文研究的是岸桥和AGV 的联合调度，岸桥和AGV 的任务分配是改善AGV 作业效率的关键环节，因此设置过多AGV 数量造成空载会导致无效成本的增加。

（2）最大化物流协同效益和运输设备协调，因此可合理规划AGV 运输路线避免岸桥等待和AGV 阻塞现象发生，同时减少空载时间。

（3）由于AGV 重载和空载情况下其耗电不同导致行驶速度不同，因此需合理设置对象参数以优化AGV 配车数量，提高码头的作业效率。

论文研究的多AGV 调度问题为：在一个水平运输为任务送达主要辅助环节的系统中，在现有约束条件下合理调度AGV 数量完成配送，并且在最大程度上减少固定成本和运输成本。在实际的多AGV 调度系统中，并行工作行驶路径最长的那辆AGV 直接决定作业完成路径的长短、作业时间的消耗。

因此，为了实现作业时间最小，使该AGV 的行驶路径最小便可以达到优化的目的。AGV 从中控室接收到下达的指令后，需要对任务作出及时地回应，即AGV 可从当前的位置出发运行至任务起始位置，并按照系统规划的路径完成任务的装卸最终到达目的地处。同时，系统需要计算起止点之前及各个节点之间的距离，实时监控AGV 的运行状态，根据反馈信息处理AGV 将会面临的突发情况，实时更新行驶路线和任务分配任务[4]。

2.2 多AGV 调度操作方法

在对AGV 进行调度时，应考虑AGV 当前的运输状态、地理位置、待执行任务、任务紧急程度等，综合以上因素再对AGV 下达执行指令。当AGV 处于空闲状态或故障排除状态时，则首先应当根据紧急分配原则进行任务下达指令；在处理不同尺寸的集装箱时，AGV 可根据当时的运载能力进行调度优化。

2.3 多AGV 调度策略

（1）任务分配方案

由于AGV 的调度问题即为合理安排AGV 和任务的分配关系及其顺序关系，因此对其进行合理安排可以有效对紧急任务作出及时反应和调整，可根据按时分配、就近分配、紧急分配等原则系统规划任务执行顺序[5]。

（2）交通规划策略

由于AGV 任务下达主要依据其位置、状态等信息，因此AGV 在运输道路上的交通规则便起到至关重要的作用。合理的交通规则不仅可以提高物流运输的效率，同时可对AGV进行优化指派数量、缩短周转时间、有效处理紧急故障、避免碰撞及死锁等保障作用。因此，论文对AGV 实行以下交通规则。

①AGV 在场地运输通道上行驶并进行集装箱装卸，道路上所有点称为节点，其中AGV 的起止点和中转点为作业节点，所经过的道路交叉口为路口节点。

②AGV 的可通行道路分为主干道和次干道。其中主干道上的交通流在经过交叉口时不受限制,两辆AGV 之间必须时刻保持安全距离，避免在转弯时出现死锁现象。然而次干道上的交通流必须根据AGV 是否具有安全时间间隔才被允许进入，若不具备则将发生小车的等待。

③赋予场地内所有AGV 所装卸集装箱的优先级，并用数字编号以示区分。当两辆AGV 同时出现在同一路口节点时，优先级高的先通过路口，且规定在系统中道路节点处至多有两辆AGV 会面临碰撞现象[6]。

在AGV 所负责的任务集里，小车进行连续作业且保持匀速状态，因此当两辆小车在同一干道上行驶时，必须保证两者距离不得少于安全距离，避免出现急停造成交通事故，同时系统也自动避免设备故障的发生。

（3）速度设置策略

论文重点研究的是基于时间窗的多载AGV 调度，因此不重点研究在交叉口通过速度的调节来保持物流系统的高效与稳定，通过假定路口发生冲突时，AGV 进行等待或者先行来设置AGV 的速度参数。安排方法同交通规划策略相似，在同一道路上，AGV 在保证安全距离的基础上保持匀速行驶，当前小车转弯或急停时，后小车则在合理的时间范围内停止通行进行等待。当在交叉口处需综合考虑小车道路的优先级、运载货物的紧急情况与未通行路径长度，作为继续通行还是停车等待的标准，且不考虑其速度改变过程的时间。

2.4 路径规划策略

在综合考虑最短路径、最大运载量、最短排队列长、最小等待时间的情况下，论文AGV 路径规划策略大致可描述为：通过赋予岸桥时间窗，从而安排AGV 按照设定的先后排列次序开展任务活动，避免碰撞与死锁现象，并且利用时间定义道路优先级增强AGV 的动态适应性。以下因素是影响路径优化的重要条件。

（1）作业节点性质：它是AGV 工作的起止点或中转点，由于AGV 自身不具备提升功能，因此该节点是岸桥或场桥与AGV 进行任务交接的场地。论文以成本最小作为目标函数，利用时间窗模型和惩罚函数对作业节点进行任务约束。

（2）集装箱承载量：作为港口吞吐量的重要换算单位，目前AGV 的装载容量为40 英尺标准箱，但是在大多研究论文中当AGV 运载一个20 英尺的集装箱时，其工作能力仅仅为50%，随着集装箱量的不断扩大必然会造成经济损失、资源浪费，因此论文将集装箱的尺寸加以区分最大程度上减少AGV 运载的次数。

（3）任务约束条件：论文主要从AGV 的容量和时间两个方面进行考虑，并且每次进行多任务运输时只有一个入口和一个出口，前后任务时间上也存在客观正确的逻辑关系。

（4）目标函数：通过对AGV 加以交通规则、速度控制及路径规划等约束，使系统安排的集装箱任务能在规定的时间范围内完成，并且在有限的AGV 数量下实现最小化运输次数和运输路径以实现最小化成本的目标。

由于以上因素相互作用、相互促进，因此集装箱的运输作业不仅仅是单一的水平运输过程，还需要各个方面的整体优化最终实现目标的完成与优化，防止岸桥等待时间过长造成船舶非正常停靠的情况发生、路径选择不经济、AGV 配置数量过多等情况的发生[7]。

3 基于时间窗的多载AGV 模型

3.1 多载AGV 调度模型

3.1.1 水平运输系统

对于自动化集装箱码头水平运输系统，其效率的高低直接代表了整个码头运作的工作水平。AGV 通常为可承载40英尺集装箱，若被指派装卸20 英尺集装箱时，则导致一半装载容量被浪费，因此为达到最小化等待时间和行驶路径的目标，多载AGV 不仅需要考虑其分配任务，还需要从自身容量出发对任务顺序进行优化处理，使多载AGV 的调度任务格外复杂与困难[8]。

3.1.2 调度方案

论文以成本最小为原则，当岸桥处有需要进行卸载的集装箱时，根据紧急原则或就近原则对空载AGV 进行搜索并下达任务安排，随后AGV 将执行任务满足请求。由于论文研究的AGV 容量为40 英尺集装箱，因此当AGV 此时承载一个20 英尺集装箱，在满足的时间窗条件下还可以允许该集装箱承载另一个20 英尺的集装箱，随后将其各自运送回目的地处完成任务交付，结束此次调度活动后中控室便为AGV 更新任务分配。若不满足时间窗范围，则需利用惩罚函数找出问题的最优解。

3.2 多载AGV 调度优化模型的建立

3.2.1 模型假设

论文是在带时间窗的车辆调度问题上展开的自动化集装箱码头多载AGV 调度研究，根据实际情况考虑到AGV 和集装箱的实际尺寸和码头的停泊时间，因此以下是确定的基于时间窗约束的多载AGV 调度研究。

假设条件：

（1）已知岸桥被分配的集装箱任务集合。

（2）场桥为两个，各自各组出口箱和进口箱。

（3）理论不能出现岸桥停滞等待AGV 的情况，超过时间窗便带来成本的损失。

（4）AGV 数量充足，不能出现AGV 等待场桥的情况，且AGV 可行驶路径为已知。

3.2.2 参数设置

i：运输任务(1、2、3...n)

K：场地AGV 的集合

i：任务i 的起始点；

n+i：任务i 的交付点；

P：起始点的集合，其中P={1,2,3…,n}

D：交付点的集合，其中D={n+1,n+2,n+3…,n}

N：所有起始点和交付点的集合，其中N=P∪D

di：任务i 所执行的运输个数,若任务i 从i 点运输di个至n+i 点，则Li= di，Ln+i=−di

o(k)：AGVk所有任务集合的起始点

d(k)：AGVk所有任务集合的停靠点

Nk：AGVk的所有任务集合，其中Nk=Pk∪Dk

Vk：AGVk所有任务点与AGVk的起始点和停靠点的集合，其中

Ak：AGVk所有通行路径的连接的弧，其中Ak∈Vk×Vk

Gk：AGVk的路径形成的通行网路，其中Gk=（Vk,Ak）

Ck：AGVk的最大负载能力，为固定值

ti,j,k：AGVk从i到j的通行所需时间，其中i,j∈Vk

ci,j,k：AGVk从i到j的通行所需费用，其中i,j∈Vk

Ce：AGVk早到的惩罚成本

Cl：AGVk迟到的惩罚成本

si：任务i的执行时间

[ao,bo]：船舶停靠的时间窗，为最大一个时间范围

[ai,bi]：硬时间窗，指代是点i 的计划时间窗，其中i∈C

针对场地中任意AGVk，其运行路径为：收到起始点o(k)的任务后便开始运行，行驶路线为Gk中的最优路径，到达任务停靠点d(k)便进行任务装卸，并其中要求AGV 到达被分配岸桥的时间必须在时间窗 [ai',bi']内，如果AGV早到或者延时都将被惩罚。其中，多载AGV 在运输中并不是每次都为多载，是在能减少运输数量并满足容量条件的情况下才为多载，否则仍为单载AGV。

3.2.3 变量定义

（1）若AGVk行驶路径（i,j）∈Ak，则xi,j,k=1，否则xi,j,k=0。

（2）Ti,k为AGVk在起始点i 开始运行的时间，其中i∈kV。

（3）Li,k为AGVk在起始点i 完成装卸后的荷载。

3.2.4 模型建立

目标函数：

约束条件：

其中（3）～（5）表示AGVk有一个起始点o(k)并且最后停靠在终止点d(k)，经过的入口点数目等于出口点的数目。（6）（7）表示每个装卸任务只能被运输一次，任意一个集装箱的装卸必须为一辆AGVk完成。（8）～（10）表示当xi,j,k=1，AGVk执行任务j 的时间Tj,k大于等于AGVk执行i 的起始时间Ti,k、任务i 执行过程的时间si与AGVk从i 点运行到j 点的时间之和。（11）～（16）为AGV 装载和在起始点o(k)和终止点d(k)的负载约束。

4 求解算法

4.1 求解思路

中国对于集装箱码头的分析主要集中于AGV局部调度，任亚东[9]探讨了 AGV 调度系统的原理、原则以及影响因素，随后分析了“作业线”和“作业面”调度模型各自的优缺点，以无效作业时间最小为原则建立了数学模型，基于 Netlogo平台进行仿真模拟，对比分析不同环境下AGV 的等待率，得出了最佳的车道和岸桥以及AGV 的最佳参数配比。汪先超[10]研究了根据实时调度的方法，解决了多AGV 基于静态调度、实时调度、出现故障三种条件下的调度问题。

Confessore G 等将AGV 调度问题视为最小流问题，构建了最小流模型，通过贪婪算法和单纯形算法进行计算并展开分析。Kumaran 和 Richard 等人针对AGV 死锁问题展开了分析，将场地划分为不同的矩形区域，根据判断该区域是否存在其余AGV 从而避免死锁的发生。Kusiak 和 Cyrus 从时间最短为原则，最小化AGV 闲置的时间 ，在算法设计上采用了遗传算法。Golden 等验证了多载AGV 调度问题为NPhard 问题，论文用遗传算法来进行问题的求解。

4.2 算法设计

4.2.1 编码

遗传算法的编码一般有浮点编码和二进制编码两种，论文采用二进制编码方式。若第i 个任务由AGVk完成，则第i 个位置的编码为k，染色体长度为岸桥被分配的任务数量，对应的编码分别为1～7 的整数，表示场地上有7 辆AGV。

4.2.2 解码

由于解码的目的是为了将二进制数据还原为十进制，根据公式可得出：

4.2.3 交配

交配运算为单点或多点进行交叉的算子，首先选定随机数产生一个或多个交配点的位置，然后在两个父代个体交配的位置上交换部分基因形成两个新的个体，随后根据适应度函数来筛选子代染色体，并重复更换基因组和筛选对的过程最终得到一个最优的子代染色体。

4.2.4 突变

突变即在基因位上进行基因突变，为了避免过早出现算法的收敛，对于二进制基因码组成的个体种群，实行基因码的小几率翻转。

4.2.5 倒位

除了交配和突变，对于个别复杂问题可能需要应用倒位，是指一个染色体某区域的正常排序进180°翻转，已致DNA序列进行重新排列，其中包括臂内倒位和臂间倒位两种方式。倒位纯合体不影响个体的生活率，但改变了染色体上相邻的基因位置，使某些表现型发生顺序更改，同时也改变了与相邻基因的交换值。

4.2.6 个体适应度评估

遗传算法中根据与个体适应度成正比的几率决定当前种群中个体是否能遗传到下一代，适应度大的将更容易被遗传到下一代，因此通常把求目标函数最优解问题当做检测个体适应度大小的函数。

4.2.7 复制

若设种群中个体总数为N，个体i 的适应度为fi，则个体i 被选取的几率为：

个体被复制后再产生[0,1]区间的均匀随机数来决定哪些个体参与复制，被选取的几率和个体适应度成正比例关系，个体的遗传基因会因此扩散或者被逐渐淘汰。

根据算法设计得出以下结论：

（1）多载AGV 相对于单载AGV 的空载率、空载次数和运输费用都低。

（2）随着集装箱量的增加，码头机械设备的参数不断进行更改，多载AGV 的运输费用始终比单载AGV 低。

5 结语

论文通过对集装箱自动化码头主要业务的分析，提出一种基于软时间窗的策略，该策略主要考虑了船舶靠泊时间会影响整个码头作业产生的系列费用，以及集装箱尺寸会影响AGV 调度的作业次序以及次数，因此通过配置最优交通规则、速度控制及路径规划等要素力求得出最优的AGV 调度方案。此外，为了实现AGV 能及时响应岸桥，因此论文在算法设计中讨论了硬时间窗和软时间窗两种情况，适用于不同特点的码头。

论文通过对AGV 调度的原则、方法及目标等的分析，针对AGV 容量限制建立了费用最小为目标函数的优化模型，采用遗传算法进行模型的求解，并在求解过程中设置相关对比组进行方案分析，基于码头实际情况不断对AGV 分配比例进行优化改进，同时考虑到码头集装箱量在不断增加，因此在设置任务数量时需要进行多组对照，以便得出多载AGV在理论中优于单载AGV 的结果。此外，论文利用了时间窗和惩罚函数，通过采集大量码头真实数据及实验结果进行验证分析，不断调整得到合理的时间窗区间范围。