路径规划是自动导引运输车（automated guided vehicle,AGV)系统任务键，其中动态路径规划由于考虑了系统中多台AGV车辆之间的协作，并能根据系统实时的路径数据、车辆数据和任务情况，规划出满足系统实时要求的路径，成为当下AGV系统理论研究的热点。路径规划问题根据AGV检测到的周围环境信息的差异，可分为局部和全局路径规划，其中，全局路径规划以现有的环境信息构建相应的模型并使用A*等最优搜索算法得到最优搜索路径。此类问题多从AGV协同工作的角度开展研究，如：对于多AGV的路径规划，Rajotia等结合使用了时间窗算法与拉格朗日松弛启发式算法以解决问题。当车辆在路径上遇到死锁问题时，Shao Shengjun等回则采用限制某区域只能单车运行的方法去解决该问题。为得到最优路径和避免车辆间的冲突，Digani等在系统的运行过程中，对任务优先级进行动态调节。为优化车辆的空闲时间使其最短，Miyamoto等提出了基于遗传算法的路径规划算法。另外，林清岩在AGV的路径规划基础研究中提出了关于多目标最优路径的智能算法。孟凡伟就带时间窗的AGV车辆蜂群调度优化问题分析了多种车辆分派策略的路径规划问题。蓝志坤、赵东雄等就AGV系统中多台车辆的路径规划也开展了相关研究。上述研究虽然在某一情况下实现了有效的路径规划，如Dijkstra算法虽能够搜索到全局最优路径，但有一定盲目性，当节点增多，其搜索到的节点过多捋使得效率太低。遗传算法在寻找全局最优解的随机搜索过程中，当节点增多时易出现早熟现象且搜索时间较长。启发式搜索算法A*算法搜索有方向性，效
率高且易实现。
在实际工厂仓储系统中，对于双向单车道的AGV系统作业场景，直接应用上述研究并不现实，本文在上述研究基础上，以优化的A*算法为基础对双向单车道的AGV系统作业场景，以最小运行代价和优先级相结合为任务生成策略，建立基于时间窗的AGV系统动态路径规划优化模型及其算法流程，为运行总成本最小约束下智能物流和自动化仓储系统中多台AGV协同作业的动态路径规划问题提供有效方法。
1 AGV系统路径规划的时间窗
为了避免双向单车道AGV系统中出现冲突和死锁现象，需要确定每辆运行AGV车对路段占有的时间段，也即是AGV系统路径规划的时间窗，其真实含义是指AGV车辆从进入某路径到离开该路径的时间段，在该时间段内车辆被赋予该路径某个方向的使用权。在AGV路径规划中，由于实现简单和实用性强，时间窗算法被大量应用。
时间窗模型的假设条件：
（a）每条路径的通行能力固定，不得超过路径的上限交通流量，车辆可在每条路径上双向行驶；
（b）在路径上某一状态下，车辆匀速行驶；
（c）某一路径上同向行驶的车辆间有一定安全距离，这一安全距离通过安装的避障设备实现；
（d）车辆同一时刻只占据一条路径，每条路径上可容纳不少于一台AGV车辆；
（e）不考虑车辆行进至交叉口处时的减速时间和通过交叉口后的加速时间；
（f）不考虑车辆从等待站点回到路径上的时间；
（g）不考虑车辆在任务过程中的卸载货物和装载货物时间；
（h）管理员可预先设置任务的优先级，其默认优先级设置顺序为任务产生的时间顺序口。
在上述假设基础上，AGV系统路径规划的时间窗模型如下：
时间窗模型的核心是AGV车进入路段的起始时间点和离开路段的终止时间点，为此捋路段分成线段和转弯段，AGV车辆分为空载和负载，分别给出其计算公式。
空车直线路段的时间窗计算公式：
负载直线路段的时间窗计算公式：
空车转弯路段的时间窗计算公式：
负载转弯路段的时间窗计算公式：
其中：R为转弯路径上的转弯半径，取2m；Vl0为车辆在直行路径上的空载运行速度，通常取2m/s；Vl为车辆在直行路径上的负载运行速度，通常取1.5m/s；Vc0为车辆在转弯路径上的空载运行速度，通常取1m/s；Vc为车辆在转弯路径上的负载运行速度，通常取0.5m/s；Lv0为车辆空载时的车身长度，取2m；Lv为车辆带负载时的车身长度，取5m；Ljk0为jk段路径的直线距离；tjkm为路径k第m个时间窗口；tjkms为路径k第m个时间窗口的开始时刻；jkmc为路径jk第m个时间窗口的结束时刻；k、j为交叉口序号，k、j≤p，k≠j;p为系统地图中交叉口总数量。
2 AGV系统路径动态规划优化模型
2.1 模型建立
考虑到AGV系统运行效率不能简单以搬运的最短路径来定义，基于上述避免冲突和死锁的时间窗模型，系统路径规划的优化目标为完成系统任务所有AGV车辆作业的总时间，目标函数如下：
约束条件为：
其中：n为系统内车辆数；tti为第i辆车完成搬运任务所用最短时间；tci为系统中第i台车辆从任务产生时刻到车辆执行搬运任务时刻的最短时间；Njkjktm为在tjkm时间窗内在交叉口j到k的路径上的AGV数；Nkjjktm为在tjkm时间窗内在交叉口k到j的路径上的AGV数。
约束条件中公式所具有的意义：式（7）指任务中的车辆数不大于系统内车辆总数；式（8）和（9）计算在tjkm时间窗内在交叉口j到k的路径上的AGV数量；式（10）和（11）表示在tjkm时间窗内在交叉口j到k的路径上的车辆数不应大于路径中可容纳的最大车辆数；式（12)指系统中车辆总数目应小于路径总数（可以不存在）；式（13）是在t选时间窗内在交叉口j到k的路径上不存在对向行驶的车辆。
2.2 算法流程
为了获得所建立的AGV系统路径规划模型的规划结果，系统按照任务的时间顺序节点进行规划，每当有新任务产生时，对系统已存在的任务和新任务进行总体路径规划，模型的算法流程如下：
a）接收到新任务请求需求。
b）先计算系统中所有可使用车辆到达目标任务站点的最优路径时间成本，选择所有车辆中时间成本最小的车辆分配新任务。
c）运用改进后的A*算法为新任务寻找到自任务起点到任务终点用时最少的路径。
d）利用步骤b）中得到的最优路径计算时间窗。
e）查看时间窗中是否会出现冲突，若出现冲突则确定其类型，如果无冲突出现，转至步骤i）。
f）如果是路径同向冲突，计算其时间窗口内的交通量是否在路径最大道路容量范围内。
g）若是交叉口段的一般冲突，可利用延迟时间窗口的方法进行解决。
h）如果是交叉口或者路径的相向冲突。先利用推迟时间窗的方法，计算出避免所有冲突中所需延迟的时间窗，取延迟时间最小值。接着按照任务优先级顺序，由低到高，对路径进行重新规划，找出可避免冲突的次最优路径。最后取2种方法中时间成本较小的方案。
i）结束全局路径规划，生成路径规划结果。
j）当系统收到新任务，或AGV车辆更新了路径规划时间窗时，转入a）。
3 AGV系统路径规划优化模型的验证
3.1 验证案例描述
AGV系统作业的路网结构和作业站点见图1。
task1、task2和task3为系统在不同时间下所产生的3个不同的任务，具体任务为：task1起始点为11，目标点为37；task2起始点为13，目标点为38；task3起始点为18，目标点为33。其中空闲无任务的车辆共有3辆，AGV1、AGV2和AGV3，分别停靠在9、8和15号站点。为了有效检验静态全局规划算法，假设在任务生成时这3台车辆均处于空闲状态，且能够被每一任务调用。任务生成时间：task1的生成时刻为t=0s，task2的生成时刻为t=10s，task3的生成时刻为t=30s，优先级按照任务生成的先后顺序设置，即task1优先级设为3，task2优先级设为2，task3优先级设为1，在运行过程中优先级可变。
3.2 验证案例计算
3.2.1作业车辆分配和搬运路径的确定
采用传统的A*算法，分别计算了系统中可用AGV车辆运行至任务站点（空载）的最短运行时间和对应的最短时间路径。在该过程中，确定了某一时刻的AGV车后，运用最优路径A*算法，得出该任务的最少执行时间，用于计算在某个新任务的呼叫系统内执行任务车辆的时间成本。各自计算t=0s时刻task1、t=10s时刻task2和t=30s时刻task3调用3辆不同车辆到达它们各个任务开始阶段的路径与时间成本，如表1所示。
当使用AGV1计算task2的时间成本时，AGV1已执行task1，故需用到从该时刻到task1任务完成的时间，task2的任务完成时间采用单车规划算法计算得出，取其最低的时间成本。同样地，task3在调AGV1和AGV2时，它们分别执行各自的任务，也需要等待被调用，直至车辆当前执行任务完成。在结果中，选出每一任务某时刻时间成本最低的车辆以分配任务：task1选择AGV1完成任务，其空载状态下的运行路径是9-10-11，task2选择AGV2，task3选择AGV3，它们在空车时的运行路径分别为8-14-13和15-14-18。图1是经过计算后所得的多任务情况下3辆AGV车辆的最优运输路径和车辆分配路径。
进行全局规划后的结果为：task1的运输路径：11-12-13-14-18-23-28-34-37；task2的运输路径：13-12-19-21-29-32-38；task3的运输路径：18-23-28-34-33。
3.2.2确定时间窗
根据全局规划后的结果计算出系统的时间窗，运算结果见表2、3、4。
3.2.3分析并解决路径冲突问题
由时间窗表可知，原始的路径规划发生了以下冲突：
2种方法可用于解决系统内路径冲突问题：重新规划路径和推迟时间窗，在选择哪种方法解决问题时，需要计算并比较2种方案的运行时间成本，选择时间成本较小的方案。
3.2.3.1推迟时间窗
运用该方法解决规划任务中task1与task2间对向冲突的问题，需满足12-13-14路径上无对向冲突的条件，如taskl的t112,13的时间窗向后移动，至少需要推迟的时间是：
经过对比选择推迟时间最短的方案，即选择使task1的t112,13时间窗推迟62.95s，
3.2.3.2重新规划路径
对于12-13-14路径的冲突，可针对task1或task2实施实时单一车辆的路径规划来解决冲突问题。在2个任务中选出实时路径规划任务，遵照以下原则进行选择：判断任务的优先级高低，按照从低到高的顺序进行选择，优先级高的任务如果重新规划后的路径比原始规划的路径增加路段，则不选择当前任务进行重新路径规划，选择次优先级的任务进行重新路径规划，避免重新路径规划中出现增加路段的情况，因为增加一个路段带来的时间成本要远大于各种转弯情况带来的时间成本。
在本文算例中，因task2优先级更低，先选择task2进行再次路径规划，规划后发现task2无次优路径，则寻找次优先级的任务进行路径规划，此例中次优先级任务为task1，所以选择task1进行再次路径规划，结果如下：task1运输路径是11-12-19-21-22-23-28-34-37；task2运输路径是13-12-19一21-29-32-38；task3运输路径是18-23-28-34-33。经过对比可以看出，经过再次路径规划后，可以成功避免12-13-14路径上的对向冲突，但因增加了task1的转弯次数伴随着时间成本增加。
在解决了冲突后，task1的时间窗口如表5所示。
可得，重新规划后路径仅有同一方向上的路径有重合的问题，但是这些路径上的实时流量都在路径的可容纳交通量的范围内，且在3个任务中，仅task1时间成本增加，具体数值为：378.32-362.42=15.9s
通过比较2种方法所需增加的时间成本，重新规划路径增加的15.9s远小于推迟时间窗的62.95s，故本例最终使用重新规划路径的方法来避免冲突。
4 结语
本文就智能物流和自动化仓储系统中多辆AGV协同作业的动态路径规划问题进行研究，并通过一个简单的案例验证文中所建立的基于时间窗的AGV系统动态路径规划优化模型及其算法流程的有效性，为运行总成本最小约束下确定什么时间由哪辆AGV通过哪条路径完成哪个任务的多AGV调度作业提供了新的方法，后续研究将进一步考虑AGV车辆实际运行中客观存在的速度波动，以及开发基于数字电子地图的路径规划软件。对于更加细化的问题，如单辆AGV的最长作业时间，可增加目标函数的约束函数进行验证，后续可深入研究。对于3辆（甚至多辆）AGV车在同一交叉口出现的情况，后续可针对AGV系统作业过程中多路径交叉口的安全避障.
暂无评论内容