基于速度控制的自动化码头AGV无冲突路径规划
|
摘要
随着劳动力成本的上升,提高码头效率成为港口发展的关键。自动引导车(AGV)是自动化码头水平运输的主要设备,但其作业过程中的冲突、拥堵、等待等问题日益突出,降低了码头的运作效率。以最小化AGV在岸桥和场桥之间的行驶距离为目标建模,选择最优行驶路径。通过检测AGV的重叠率和冲突时间,遵循先到先服务的原则,采用速度控制策略,实现AGV无冲突路径规划。仿真实验表明,该方法能有效降低AGV冲突的概率,减少岸桥和场桥设备的等待时间,提高AGV的作业效率,实现作业成本的最小化。
With the increase of labor cost,improving the efficiency of terminalshas been the key in development of ports.Automatic guided Vehicles(AGV),as the main equipmentof automatedterminalsin horizontal transportation,the problems of conflict,congestion and waiting have been more serious,which greatly reducing the operation efficiency of the terminals.This paper modeled with the minimum driving distance of AGV between the QCs and YCs,to choose the optimal path.By testing the overlapping rate and the conflict time,and using the speed control strategy,which follow the rule of first come first service,the path planning of free-conflict AGV is achieved.The simulation results show that this method can reduce the probability of AGV conflicteffectively,decrease the waiting time of QCs and YCs,improve the operationefficiency of AGV,and minimize the totalcost of operation.
With the increase of labor cost,improving the efficiency of terminalshas been the key in development of ports.Automatic guided Vehicles(AGV),as the main equipmentof automatedterminalsin horizontal transportation,the problems of conflict,congestion and waiting have been more serious,which greatly reducing the operation efficiency of the terminals.This paper modeled with the minimum driving distance of AGV between the QCs and YCs,to choose the optimal path.By testing the overlapping rate and the conflict time,and using the speed control strategy,which follow the rule of first come first service,the path planning of free-conflict AGV is achieved.The simulation results show that this method can reduce the probability of AGV conflicteffectively,decrease the waiting time of QCs and YCs,improve the operationefficiency of AGV,and minimize the totalcost of operation.
引文
[1] FAZLOLLAHTABAR H,SAIDI-MEHRABAD M.Autono- mous Guided Vehicles:Methods and Models for Optimal Path Planning[M].Springer Publishing Company,Incorporated,2015.
[2] WU Y,LUO J,ZHANG D,et al.An integrated programming model for storage management and vehicle scheduling at container terminals[J].Research in Transportation Economics,2013,42(1):13-27.
[3] LUO J,WU Y.Modelling of dual-cycle strategy for container storage and vehicle scheduling problems at automated container terminals[J].Transportation Research Part E Logistics & Transportation Review,2015,79(7):49-64.
[4] HUO K G,ZHANG Y Q,HU Z H.Research on multi-load AGV scheduling of automated container terminals [J].Journal of Dalian University of Technology,2016,56(3):244-251.(in Chinese)霍凯歌,张亚琦,胡志华.自动化集装箱码头多载AGV调度问题研究[J].大连理工大学学报,2016,56(3):244-251.
[5] GHASEMZADEH H,BEHRANGI E,AZGOMI M A.Conflict-free scheduling and routing of automated guided vehicles in mesh topologies[J].Robotics & Autonomous Systems,2009,57(6/7):738-748.
[6] CHIEW K,QIN S.Scheduling and Routing of AMOs in an In- telligent Transport System[J].IEEE Transactions on Intelligent Transportation Systems,2009,10(3):547-552.
[7] GAWRILOW E,KLIMM M,M?HRING R H,et al.Conflict-free vehicle routing[J].Euro Journal on Transportation & Logistics,2012,1(1/2):87-111.
[8] ZHONG J L,MASLOWSKI A.Path planning of AGV transportation subsystem in manufacturing environment [J].Mechanical Design and Manufacturing,2010,48 (2):237-239.(in Chinese)钟建琳,MASLOWSKI A.制造环境中AGV运输子系统的路径规划[J].机械设计与制造,2010,48(2):237-239.
[9] LI W G,SU X.AGV path planning based on improved A* algorithm [J].Modern Manufacturing Engineering,2015,38 (10):33-36.(in Chinese)李伟光,苏霞.基于改进A*算法的AGV路径规划[J].现代制造工程,2015,38(10):33-36.
[10] NISHI T,HIRANAKA Y,GROSSMANN I E.A bilevel decomposition algorithm for simultaneous production scheduling and conflict-free routing for automated guided vehicles[J].Compu-ters & Operations Research,2011,38(5):876-888.
[11] TAI Y P,XING K X,LIN Y G,et al.Research on multi-AGV path planning methods [J].Computer Science,2017,44(S2):84-87.(in Chinese)泰应鹏,邢科新,林叶贵,等.多AGV路径规划方法研究[J].计算机科学,2017,44(S2):84-87.
[12] ZHU L B,WANG H,WANG J L,et al.Research on parking system path planning based on dynamic time window [J].Journal of Engineering Design,2017,24(4):440-448.(in Chinese)朱龙彪,王辉,王景良,等.基于动态时间窗的泊车系统路径规划研究[J].工程设计学报,2017,24(4):440-448.
[13] WANG H,ZHU L B,ZHU T C,et al.Research on parking system path planning based on particle swarm genetic algorithm [J].Journal of Engineering Design,2016,23(2):195-200.(in Chinese)王辉,朱龙彪,朱天成,等.基于粒子群遗传算法的泊车系统路径规划研究[J].工程设计学报,2016,23(2):195-200.
[14] UMAR U A,ARIFFIN M K A,ISMAIL N,et al.Priority-Based Genetic Algorithm for Conflict-Free Automated Guided Vehicle Routing [J].Procedia Engineering,2012,50(9):732-739.
[15] LIU D K,WU X,KULATUNGA A K,et al.Motion Coordination of Multiple Autonomous Vehicles in Dynamic and Strictly Constrained Environments[C]//2006 IEEE Conference on Cybernetics and Intelligent Systems.IEEE,2006:1-6.
[16] LI H G,JIA J C,LENG C H.Multi-AGV path planning based on step control algorithm [J].Control Engineering,2010,17(S2):93-96.(in Chinese)李惠光,贾建成,冷春辉.基于分步控制算法的多AGV路径规划[J].控制工程,2010,17(S2):93-96.
[17] SU X,LI W G.Path planning of automatic pilot vehicle in FMS [J].Mechanical Design and Manufacturing,2015,53(1):201-203.(in Chinese)苏霞,李伟光.FMS中自动导引车路径规划[J].机械设计与制造,2015,53(1):201-203.
[18] WU H M,SU M J,GUAN Y S,et al.Noncollision motion planning for multi-robot with dynamic operation sequence adjustment [J].Robot,2016,38(6):651-658.(in Chinese)吴鸿敏,苏满佳,管贻生,等.动态调整操作序列的多机器人无碰运动规划[J].机器人,2016,38(6):651-658.
[19] BAR-YEHUDA R,MORAN S.On approximation problems related to the independent set and vertex cover problems[J].Discrete Applied Mathematics,1984,9(1):1-10.
[20] KE J J,HU J Z.Fault feature extraction algorithm based on Manhattan distance and random neighborhood embedding [J].Computer Application Research,2015,32(10):2992-2995.(in Chinese)柯佳佳,胡建中.基于Manhattan距离与随机邻域嵌入的故障特征提取算法[J].计算机应用研究,2015,32(10):2992-2995.
[21] CHEN F W,ZHAO X H,ZHOU J Z.Euler formula[D].Mathe- matical Journal,2005,25(4):355-357.(in Chinese)陈方维,赵雪华,周家足.类拟的Euler公式[J].数学杂志,2005,25(4):355-357.
[22] 王海英.图论算法及其MATLAB实现[M].北京:北京航空航天大学出版社,2010.
[23] GENG J,CAI B G,WANG J,et al.Research on the traversal algorithm of railway station yard based on deep priority search [J].Journal of Railway Science,2012,34(4):51-56.(in Chinese)耿杰,蔡伯根,王剑,等.基于深度优先搜索的铁路站场遍历算法研究[J].铁道学报,2012,34(4):51-56.
[24] LIU J M,MA S F,MA S Q.Dynamic shortest circuit calculation method based on improved Dijkstra algorithm [J].Systems Engineering Theory and Practice,2011,31(6):1153-1157.(in Chinese)刘建美,马寿峰,马帅奇.基于改进的Dijkstra算法的动态最短路计算方法[J].系统工程理论与实践,2011,31(6):1153-1157.
[2] WU Y,LUO J,ZHANG D,et al.An integrated programming model for storage management and vehicle scheduling at container terminals[J].Research in Transportation Economics,2013,42(1):13-27.
[3] LUO J,WU Y.Modelling of dual-cycle strategy for container storage and vehicle scheduling problems at automated container terminals[J].Transportation Research Part E Logistics & Transportation Review,2015,79(7):49-64.
[4] HUO K G,ZHANG Y Q,HU Z H.Research on multi-load AGV scheduling of automated container terminals [J].Journal of Dalian University of Technology,2016,56(3):244-251.(in Chinese)霍凯歌,张亚琦,胡志华.自动化集装箱码头多载AGV调度问题研究[J].大连理工大学学报,2016,56(3):244-251.
[5] GHASEMZADEH H,BEHRANGI E,AZGOMI M A.Conflict-free scheduling and routing of automated guided vehicles in mesh topologies[J].Robotics & Autonomous Systems,2009,57(6/7):738-748.
[6] CHIEW K,QIN S.Scheduling and Routing of AMOs in an In- telligent Transport System[J].IEEE Transactions on Intelligent Transportation Systems,2009,10(3):547-552.
[7] GAWRILOW E,KLIMM M,M?HRING R H,et al.Conflict-free vehicle routing[J].Euro Journal on Transportation & Logistics,2012,1(1/2):87-111.
[8] ZHONG J L,MASLOWSKI A.Path planning of AGV transportation subsystem in manufacturing environment [J].Mechanical Design and Manufacturing,2010,48 (2):237-239.(in Chinese)钟建琳,MASLOWSKI A.制造环境中AGV运输子系统的路径规划[J].机械设计与制造,2010,48(2):237-239.
[9] LI W G,SU X.AGV path planning based on improved A* algorithm [J].Modern Manufacturing Engineering,2015,38 (10):33-36.(in Chinese)李伟光,苏霞.基于改进A*算法的AGV路径规划[J].现代制造工程,2015,38(10):33-36.
[10] NISHI T,HIRANAKA Y,GROSSMANN I E.A bilevel decomposition algorithm for simultaneous production scheduling and conflict-free routing for automated guided vehicles[J].Compu-ters & Operations Research,2011,38(5):876-888.
[11] TAI Y P,XING K X,LIN Y G,et al.Research on multi-AGV path planning methods [J].Computer Science,2017,44(S2):84-87.(in Chinese)泰应鹏,邢科新,林叶贵,等.多AGV路径规划方法研究[J].计算机科学,2017,44(S2):84-87.
[12] ZHU L B,WANG H,WANG J L,et al.Research on parking system path planning based on dynamic time window [J].Journal of Engineering Design,2017,24(4):440-448.(in Chinese)朱龙彪,王辉,王景良,等.基于动态时间窗的泊车系统路径规划研究[J].工程设计学报,2017,24(4):440-448.
[13] WANG H,ZHU L B,ZHU T C,et al.Research on parking system path planning based on particle swarm genetic algorithm [J].Journal of Engineering Design,2016,23(2):195-200.(in Chinese)王辉,朱龙彪,朱天成,等.基于粒子群遗传算法的泊车系统路径规划研究[J].工程设计学报,2016,23(2):195-200.
[14] UMAR U A,ARIFFIN M K A,ISMAIL N,et al.Priority-Based Genetic Algorithm for Conflict-Free Automated Guided Vehicle Routing [J].Procedia Engineering,2012,50(9):732-739.
[15] LIU D K,WU X,KULATUNGA A K,et al.Motion Coordination of Multiple Autonomous Vehicles in Dynamic and Strictly Constrained Environments[C]//2006 IEEE Conference on Cybernetics and Intelligent Systems.IEEE,2006:1-6.
[16] LI H G,JIA J C,LENG C H.Multi-AGV path planning based on step control algorithm [J].Control Engineering,2010,17(S2):93-96.(in Chinese)李惠光,贾建成,冷春辉.基于分步控制算法的多AGV路径规划[J].控制工程,2010,17(S2):93-96.
[17] SU X,LI W G.Path planning of automatic pilot vehicle in FMS [J].Mechanical Design and Manufacturing,2015,53(1):201-203.(in Chinese)苏霞,李伟光.FMS中自动导引车路径规划[J].机械设计与制造,2015,53(1):201-203.
[18] WU H M,SU M J,GUAN Y S,et al.Noncollision motion planning for multi-robot with dynamic operation sequence adjustment [J].Robot,2016,38(6):651-658.(in Chinese)吴鸿敏,苏满佳,管贻生,等.动态调整操作序列的多机器人无碰运动规划[J].机器人,2016,38(6):651-658.
[19] BAR-YEHUDA R,MORAN S.On approximation problems related to the independent set and vertex cover problems[J].Discrete Applied Mathematics,1984,9(1):1-10.
[20] KE J J,HU J Z.Fault feature extraction algorithm based on Manhattan distance and random neighborhood embedding [J].Computer Application Research,2015,32(10):2992-2995.(in Chinese)柯佳佳,胡建中.基于Manhattan距离与随机邻域嵌入的故障特征提取算法[J].计算机应用研究,2015,32(10):2992-2995.
[21] CHEN F W,ZHAO X H,ZHOU J Z.Euler formula[D].Mathe- matical Journal,2005,25(4):355-357.(in Chinese)陈方维,赵雪华,周家足.类拟的Euler公式[J].数学杂志,2005,25(4):355-357.
[22] 王海英.图论算法及其MATLAB实现[M].北京:北京航空航天大学出版社,2010.
[23] GENG J,CAI B G,WANG J,et al.Research on the traversal algorithm of railway station yard based on deep priority search [J].Journal of Railway Science,2012,34(4):51-56.(in Chinese)耿杰,蔡伯根,王剑,等.基于深度优先搜索的铁路站场遍历算法研究[J].铁道学报,2012,34(4):51-56.
[24] LIU J M,MA S F,MA S Q.Dynamic shortest circuit calculation method based on improved Dijkstra algorithm [J].Systems Engineering Theory and Practice,2011,31(6):1153-1157.(in Chinese)刘建美,马寿峰,马帅奇.基于改进的Dijkstra算法的动态最短路计算方法[J].系统工程理论与实践,2011,31(6):1153-1157.