基于Petri网的物流仓库多AGV调度方法的研究
|
摘要
针对多自动导引车(AGV)在大规模物流仓储中存在的路径规划问题,对基于时间Petri网的多AGV调度优化算法进行了研究。该算法利用时间Petri网对大规模双向车道环境下多AGV的仓库调度过程进行建模,并在分解后对AGV进行单独分析,减少了算法的时间复杂度;引入传统外点惩罚函数法构建以AGV调度时间为指标的目标函数,通过对AGV运行路径信息的依次迭代和更新解决了其在调度过程中的碰撞问题;在此基础上增加碰撞类型分析,以目标函数最优为原则对路径进行局部规划,实现调度方案最优。实验结果表明在大规模调度环境中该算法能快速收敛出无碰撞死锁的最优路径方案,并能保证多AGV在动态仓库物流调度中具有良好的实时适应性。
A scheduling optimization algorithm based on the timed Petri net is presented for solving the multi-automated guide vehicle(AGV) route planning problem in the logistics warehouse. At first, the timed Petri net is used for modeling the scheduling process of multi-AGV in the warehouses with large-scale bidirectional lanes, which greatly decreases the calculative complexity by analyzing the AGV separately; Secondly, the research structures an objective function with AGV scheduling-time as index by applying the traditional external penalty function methods, which solves collision problems by the successive iteration and update of AGV routine; Moreover, it increases the amount of analyses of collision types and local planning of paths under the principle of the best objective function, which optimizes the scheduling scheme. Finally, the results from the experiment indicate that the algorithm has the advantage of rapid convergence about gaining the optimum collision-free scheduling scheme, which could ensure that the multi-AGVs have a good timely adaptation under the dynamic logistics warehouse dispatch.
A scheduling optimization algorithm based on the timed Petri net is presented for solving the multi-automated guide vehicle(AGV) route planning problem in the logistics warehouse. At first, the timed Petri net is used for modeling the scheduling process of multi-AGV in the warehouses with large-scale bidirectional lanes, which greatly decreases the calculative complexity by analyzing the AGV separately; Secondly, the research structures an objective function with AGV scheduling-time as index by applying the traditional external penalty function methods, which solves collision problems by the successive iteration and update of AGV routine; Moreover, it increases the amount of analyses of collision types and local planning of paths under the principle of the best objective function, which optimizes the scheduling scheme. Finally, the results from the experiment indicate that the algorithm has the advantage of rapid convergence about gaining the optimum collision-free scheduling scheme, which could ensure that the multi-AGVs have a good timely adaptation under the dynamic logistics warehouse dispatch.
引文
[1] 李继明,徐震浩,顾幸生.基于混合离散粒子群优化的多时间因素作业车间调度研究[J].高技术通讯,2015,25(11-12):980-989
[2] 贺丽娜,楼佩煌,钱晓明,等.基于时间窗的自动导引车无碰撞路径规划2010全国现代制造集成技术[J].2010,16(12):2630-2634
[3] Kalinovcic L,Petrovic T,Bogdan S,et al.Modified Banker’s algorithm for scheduling in multi-AGV systems [C].In:Proceedings of the Automation Science and Engineering,Trieste,Italy,2011.351-356
[4] Li J,Meng X,Zhou M C,et al.A two-stage approach to path planning and collision avoidance of multibridge machining systems[J].IEEE Transactions on Systems Man & Cybernetics Systems,2017,47(7):1039-1049
[5] 刘志峰,廖凌浩,杨文通,等.基于自适应遗传算法的模具生产调度研究[J].高技术通讯,2011,21(9):962-966
[6] 夏田,王娜.改进蚁群算法在多AGV作业调度中的应用[J].物流技术,2015,34(23):87-89
[7] 蒋昌俊.Petri网理论与方法研究综述[J].控制与决策,1997(6):631-636
[8] Wu N Q.Necessary and sufficient conditions for deadlock-free operation in flexible manufacturing systems using a colored Petri net model [J].IEEE Transactions on Systems Man & Cybernetics Part C,1999,29(2):192-204
[9] Nishi T,Maeno R.Petri net decomposition approach to optimization of route planning problems for AGV systems[J].IEEE Transactions on Automation Science & Engineering,2010,7(3):523-537
[10] 周卫东,杨加敏,贾磊,等.一种Petri网结合遗传算法的优化方法及应用[J].山东大学学报(工学版),2005,35(4):59-63
[11] 李明,李歧强,郭庆强,等.集成启发式规则的混合整数规划调度模型[J].高技术通讯,2010,20(9):971-977
[12] Kodama A,Nishi T.General conversion of integer programming problems into optimal firing sequence problem of Petri nets [C].In:Proceedings of the IEEE International Conference on Industrial Engineering and Engineering Management,Bali,Indonesia,2016.395-399
[2] 贺丽娜,楼佩煌,钱晓明,等.基于时间窗的自动导引车无碰撞路径规划2010全国现代制造集成技术[J].2010,16(12):2630-2634
[3] Kalinovcic L,Petrovic T,Bogdan S,et al.Modified Banker’s algorithm for scheduling in multi-AGV systems [C].In:Proceedings of the Automation Science and Engineering,Trieste,Italy,2011.351-356
[4] Li J,Meng X,Zhou M C,et al.A two-stage approach to path planning and collision avoidance of multibridge machining systems[J].IEEE Transactions on Systems Man & Cybernetics Systems,2017,47(7):1039-1049
[5] 刘志峰,廖凌浩,杨文通,等.基于自适应遗传算法的模具生产调度研究[J].高技术通讯,2011,21(9):962-966
[6] 夏田,王娜.改进蚁群算法在多AGV作业调度中的应用[J].物流技术,2015,34(23):87-89
[7] 蒋昌俊.Petri网理论与方法研究综述[J].控制与决策,1997(6):631-636
[8] Wu N Q.Necessary and sufficient conditions for deadlock-free operation in flexible manufacturing systems using a colored Petri net model [J].IEEE Transactions on Systems Man & Cybernetics Part C,1999,29(2):192-204
[9] Nishi T,Maeno R.Petri net decomposition approach to optimization of route planning problems for AGV systems[J].IEEE Transactions on Automation Science & Engineering,2010,7(3):523-537
[10] 周卫东,杨加敏,贾磊,等.一种Petri网结合遗传算法的优化方法及应用[J].山东大学学报(工学版),2005,35(4):59-63
[11] 李明,李歧强,郭庆强,等.集成启发式规则的混合整数规划调度模型[J].高技术通讯,2010,20(9):971-977
[12] Kodama A,Nishi T.General conversion of integer programming problems into optimal firing sequence problem of Petri nets [C].In:Proceedings of the IEEE International Conference on Industrial Engineering and Engineering Management,Bali,Indonesia,2016.395-399