基于时空网络的自动化集装箱码头自动化导引车路径规划
发布时间：2021-10-24 07:03
针对自动化集装箱码头水平搬运作业中自动化导引车路径冲突问题,提出一种基于时空网络的路径优化方法。对于单个运输需求,首先,将路网离散化为网格网络,设计依据时间可更新的时空网络;其次,以任务完工时间最短为目标,基于时空网络下可用路段集合来建立车辆路径优化模型;最后,在时空网络上运用最短路径算法求解得最短路径。对于多个运输需求,为避免路径冲突,根据当前运输需求的路径规划结果更新下一个运输需求的时空网络,并通过迭代最终获得满足规避碰撞和缓解拥堵条件的路径规划。计算实验中,与基本最短路径求解策略（求解算法P）相比,所提方法的碰撞次数降低为0并且最小相对距离始终大于安全距离;与停车等待求解策略（求解算法SP）相比,所提方法最多减少任务总延误时间24 s,且明显降低延误任务占比以及路网平均拥堵度,最大降低程度分别为2. 25%和0. 68%。实验结果表明,所提方法能够有效求解大规模冲突规避的路径规划问题,并显著提高自动化导引车的作业效率。
【文章来源】：计算机应用. 2020,40(07)北大核心CSCD
【文章页数】：9 页
【部分图文】：
自动化集装箱码头布局
通常，将一辆AGV从任务的O点到D点的行驶路径设为两点之间的最短路径，并且假定该最短路径上的所有路段都是通畅可行的[23]，然而该做法没有考虑AGV在实际路段中的运行轨迹以及运行过程中的实时动态干涉，导致AGV根据规划路径进行作业时产生冲突。路径冲突情况包括碰撞和拥堵，在图2中，举例说明AGV冲突问题。任务1和任务2同为进口箱作业，任务1和任务2的OD点分别为O1D1、O2D2，实线表示小车实际经过的路线，虚线表示计划行驶但未行驶的路线。图2(a）展示了碰撞的发生情况，执行任务1的AGV与执行任务2的AGV在不同时刻出发却在同一时刻到达点A，发生碰撞导致任务执行失败。图2(b）展示了拥堵的发生情况，执行任务1和执行任务2的2辆AGV会在同一时刻到达A点，但为避免碰撞，执行任务2的AGV行驶到缓冲区B点时停车等待，造成拥堵现象。AGV发生碰撞将直接导致设备损坏，大幅度增加成本，设备停留在路段中占用路段资源，可能与即将行驶进路网的AGV发生二次碰撞，并且处理碰撞事故所需时间和人力成本较高；等待是避免碰撞的常用手段，但AGV减速及加速过程所消耗的电力成本较高，并且AGV等待减少了可用的道路资源，道路会因为AGV的等待而出现拥堵，严重时会导致整个路网瘫痪导致ACT被迫停止运作。所以，当路段本身成为临界资源时，AGV对路段具有独占性，因此，考虑AGV在不同时刻在路网上的状态是判别碰撞和拥堵的前提条件。在AGV的行驶过程中，从当前时刻的位置出发，下一时刻可选的到达位置通常有多个；在各个不同位置上的下一个可能到达的位置又是不同的，因此，建立在道路网络背景下随时间演变的时空网络。利用AGV在不同时刻可能到达的不同位置，从而刻画出AGV从任务起点出发的一个可行的带有时间和位置标签的网络，路径规划则是在该网络中选择一条完工时间最短的路径。本文在ACT背景下建立AGV时空网络，在时空网络中规划AGV最短路径，以任务完工时间最短为目标，建立数学模型并设计时空网络算法，使规划路径规避碰撞并缓解拥堵。
基于以上的概念和模型，设计基于时空网络的算法——TS-SP(Tempo-Spatial Shortest Path),TS-SP算法由算法1和算法2组成。其中，算法1通过生成时空网络，更新时空网络，以及调用M2计算最短路径获得给定一个OD的AGV路径；算法2调用算法1，通过迭代策略求解OD任务序列中的所有O和D配对的路径。算法2根据已获得的路径更新不可用节点集合-NT（步骤5）以实时检测冲突，而算法1则利用不可用节点集合更新时空网络（步骤2）以实时规避冲突并进行一次路径规划（步骤3），因此针对多个OD任务，在时空网络上运用最短路径算法，根据路径结果更新时空网络，并通过迭代最终获得满足避碰和缓解拥堵条件的路径规划，而M2的求解过程能够通过拓展基本最短路径算法（如Dijkstra算法）实现。时空网络算法流程如图3所示。算法开始，依据时间顺序从任务集中选取任务执行。针对每一个当前任务，首先生成时空网络，并依据当前的不可用节点集合更新时空网络，接着在更新后的时空网络中采用Dijkstra算法计算任务最短路径，并依据当前任务的最短路径结果更新不可用节点集合。判断任务集是否为空：任务集不为空则选择下一个任务执行；任务集为空则说明已完成所有任务，算法结束。算法1单个OD任务最短路径优化算法（Single＿OD＿SP）。
【参考文献】：
期刊论文
[1]融合多目标与速度控制的AGV全局路径规划[J]. 郭兴海,计明军,张卫丹. 控制与决策. 2020(06)
[2]基于蚁群算法及博弈论的多Agent路径规划算法[J]. 郑延斌,王林林,席鹏雪,樊文鑫,韩梦云. 计算机应用. 2019(03)
[3]多自动导引车路径规划的诱导蚁群粒子群算法[J]. 李军军,许波桅,杨勇生,吴华锋. 计算机集成制造系统. 2017(12)
[4]基于改进遗传算法的自动导引小车动态路径规划及其实现[J]. 刘二辉,姚锡凡,蓝宏宇,金鸿. 计算机集成制造系统. 2018(06)
本文编号：3454814
【文章来源】：计算机应用. 2020,40(07)北大核心CSCD
【文章页数】：9 页
【部分图文】：
自动化集装箱码头布局
通常，将一辆AGV从任务的O点到D点的行驶路径设为两点之间的最短路径，并且假定该最短路径上的所有路段都是通畅可行的[23]，然而该做法没有考虑AGV在实际路段中的运行轨迹以及运行过程中的实时动态干涉，导致AGV根据规划路径进行作业时产生冲突。路径冲突情况包括碰撞和拥堵，在图2中，举例说明AGV冲突问题。任务1和任务2同为进口箱作业，任务1和任务2的OD点分别为O1D1、O2D2，实线表示小车实际经过的路线，虚线表示计划行驶但未行驶的路线。图2(a）展示了碰撞的发生情况，执行任务1的AGV与执行任务2的AGV在不同时刻出发却在同一时刻到达点A，发生碰撞导致任务执行失败。图2(b）展示了拥堵的发生情况，执行任务1和执行任务2的2辆AGV会在同一时刻到达A点，但为避免碰撞，执行任务2的AGV行驶到缓冲区B点时停车等待，造成拥堵现象。AGV发生碰撞将直接导致设备损坏，大幅度增加成本，设备停留在路段中占用路段资源，可能与即将行驶进路网的AGV发生二次碰撞，并且处理碰撞事故所需时间和人力成本较高；等待是避免碰撞的常用手段，但AGV减速及加速过程所消耗的电力成本较高，并且AGV等待减少了可用的道路资源，道路会因为AGV的等待而出现拥堵，严重时会导致整个路网瘫痪导致ACT被迫停止运作。所以，当路段本身成为临界资源时，AGV对路段具有独占性，因此，考虑AGV在不同时刻在路网上的状态是判别碰撞和拥堵的前提条件。在AGV的行驶过程中，从当前时刻的位置出发，下一时刻可选的到达位置通常有多个；在各个不同位置上的下一个可能到达的位置又是不同的，因此，建立在道路网络背景下随时间演变的时空网络。利用AGV在不同时刻可能到达的不同位置，从而刻画出AGV从任务起点出发的一个可行的带有时间和位置标签的网络，路径规划则是在该网络中选择一条完工时间最短的路径。本文在ACT背景下建立AGV时空网络，在时空网络中规划AGV最短路径，以任务完工时间最短为目标，建立数学模型并设计时空网络算法，使规划路径规避碰撞并缓解拥堵。
基于以上的概念和模型，设计基于时空网络的算法——TS-SP(Tempo-Spatial Shortest Path),TS-SP算法由算法1和算法2组成。其中，算法1通过生成时空网络，更新时空网络，以及调用M2计算最短路径获得给定一个OD的AGV路径；算法2调用算法1，通过迭代策略求解OD任务序列中的所有O和D配对的路径。算法2根据已获得的路径更新不可用节点集合-NT（步骤5）以实时检测冲突，而算法1则利用不可用节点集合更新时空网络（步骤2）以实时规避冲突并进行一次路径规划（步骤3），因此针对多个OD任务，在时空网络上运用最短路径算法，根据路径结果更新时空网络，并通过迭代最终获得满足避碰和缓解拥堵条件的路径规划，而M2的求解过程能够通过拓展基本最短路径算法（如Dijkstra算法）实现。时空网络算法流程如图3所示。算法开始，依据时间顺序从任务集中选取任务执行。针对每一个当前任务，首先生成时空网络，并依据当前的不可用节点集合更新时空网络，接着在更新后的时空网络中采用Dijkstra算法计算任务最短路径，并依据当前任务的最短路径结果更新不可用节点集合。判断任务集是否为空：任务集不为空则选择下一个任务执行；任务集为空则说明已完成所有任务，算法结束。算法1单个OD任务最短路径优化算法（Single＿OD＿SP）。
【参考文献】：
期刊论文
[1]融合多目标与速度控制的AGV全局路径规划[J]. 郭兴海,计明军,张卫丹. 控制与决策. 2020(06)
[2]基于蚁群算法及博弈论的多Agent路径规划算法[J]. 郑延斌,王林林,席鹏雪,樊文鑫,韩梦云. 计算机应用. 2019(03)
[3]多自动导引车路径规划的诱导蚁群粒子群算法[J]. 李军军,许波桅,杨勇生,吴华锋. 计算机集成制造系统. 2017(12)
[4]基于改进遗传算法的自动导引小车动态路径规划及其实现[J]. 刘二辉,姚锡凡,蓝宏宇,金鸿. 计算机集成制造系统. 2018(06)
本文编号：3454814
本文链接：https://www.wllwen.com/kejilunwen/jiaotonggongchenglunwen/3454814.html
