计算机科学 ›› 2019, Vol. 46 ›› Issue (7): 308-314.doi: 10.11896/j.issn.1002-137X.2019.07.047
仲美稣,杨勇生,周亚民
ZHONG Mei-su,YANG Yong-sheng,ZHOU Ya-min
摘要: 随着劳动力成本的上升,提高码头效率成为港口发展的关键。自动引导车(AGV)是自动化码头水平运输的主要设备,但其作业过程中的冲突、拥堵、等待等问题日益突出,降低了码头的运作效率。以最小化AGV在岸桥和场桥之间的行驶距离为目标建模,选择最优行驶路径。通过检测AGV的重叠率和冲突时间,遵循先到先服务的原则,采用速度控制策略,实现AGV无冲突路径规划。仿真实验表明,该方法能有效降低 AGV 冲突的概率,减少岸桥和场桥设备的等待时间,提高AGV 的作业效率,实现作业成本的最小化。
中图分类号:
[1]FAZLOLLAHTABAR H,SAIDI-MEHRABAD M.Autono- mous Guided Vehicles:Methods and Models for Optimal Path Planning[M].Springer Publishing Company,Incorporated,2015.<br /> [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.<br /> [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.<br /> [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)<br /> 霍凯歌,张亚琦,胡志华.自动化集装箱码头多载AGV调度问题研究[J].大连理工大学学报,2016,56(3):244-251.<br /> [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.<br /> [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.<br /> [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.<br /> [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)<br /> 钟建琳,MASLOWSKI A.制造环境中AGV运输子系统的路径规划[J].机械设计与制造,2010,48(2):237-239.<br /> [9]LI W G,SU X.AGV path planning based on improved A<sup>*</sup> algorithm [J].Modern Manufacturing Engineering,2015,38 (10):33-36.(in Chinese)<br /> 李伟光,苏霞.基于改进A<sup>*</sup>算法的AGV路径规划[J].现代制造工程,2015,38(10):33-36.<br /> [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.<br /> [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)<br /> 泰应鹏,邢科新,林叶贵,等.多AGV路径规划方法研究[J].计算机科学,2017,44(S2):84-87.<br /> [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)<br /> 朱龙彪,王辉,王景良,等.基于动态时间窗的泊车系统路径规划研究[J].工程设计学报,2017,24(4):440-448.<br /> [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)<br /> 王辉,朱龙彪,朱天成,等.基于粒子群遗传算法的泊车系统路径规划研究[J].工程设计学报,2016,23(2):195-200.<br /> [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.<br /> [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.<br /> [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)<br /> 李惠光,贾建成,冷春辉.基于分步控制算法的多AGV路径规划[J].控制工程,2010,17(S2):93-96.<br /> [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)<br /> 苏霞,李伟光.FMS中自动导引车路径规划[J].机械设计与制造,2015,53(1):201-203.<br /> [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)<br /> 吴鸿敏,苏满佳,管贻生,等.动态调整操作序列的多机器人无碰运动规划[J].机器人,2016,38(6):651-658.<br /> [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.<br /> [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)<br /> 柯佳佳,胡建中.基于Manhattan距离与随机邻域嵌入的故障特征提取算法[J].计算机应用研究,2015,32(10):2992-2995.<br /> [21]CHEN F W,ZHAO X H,ZHOU J Z.Euler formula[D].Mathe- matical Journal,2005,25(4):355-357.(in Chinese)<br /> 陈方维,赵雪华,周家足.类拟的Euler公式[J].数学杂志,2005,25(4):355-357.<br /> [22]王海英.图论算法及其MATLAB实现[M].北京:北京航空航天大学出版社,2010.<br /> [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)<br /> 耿杰,蔡伯根,王剑,等.基于深度优先搜索的铁路站场遍历算法研究[J].铁道学报,2012,34(4):51-56.<br /> [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)<br /> 刘建美,马寿峰,马帅奇.基于改进的Dijkstra算法的动态最短路计算方法[J].系统工程理论与实践,2011,31(6):1153-1157. |
[1] | 王兵, 吴洪亮, 牛新征. 基于改进势场法的机器人路径规划 Robot Path Planning Based on Improved Potential Field Method 计算机科学, 2022, 49(7): 196-203. https://doi.org/10.11896/jsjkx.210500020 |
[2] | 谭任深, 徐龙博, 周冰, 荆朝霞, 黄向生. 海上风电场通用运维路径规划模型优化及仿真 Optimization and Simulation of General Operation and Maintenance Path Planning Model for Offshore Wind Farms 计算机科学, 2022, 49(6A): 795-801. https://doi.org/10.11896/jsjkx.210400300 |
[3] | 杨浩雄, 高晶, 邵恩露. 考虑一单多品的外卖订单配送时间的带时间窗的车辆路径问题 Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery 计算机科学, 2022, 49(6A): 191-198. https://doi.org/10.11896/jsjkx.210400005 |
[4] | 尹宏俊, 邓楠, 程亚迪. 基于加速度模糊控制的六足机器人遥操作 Teleoperation Method for Hexapod Robot Based on Acceleration Fuzzy Control 计算机科学, 2022, 49(6A): 714-722. https://doi.org/10.11896/jsjkx.210300076 |
[5] | 沈彪, 沈立炜, 李弋. 空间众包任务的路径动态调度方法 Dynamic Task Scheduling Method for Space Crowdsourcing 计算机科学, 2022, 49(2): 231-240. https://doi.org/10.11896/jsjkx.210400249 |
[6] | 陈镜宇, 郭志军, 尹亚昆. 基于混合算法的智能割草机全遍历路径规划及其系统设计 Full Traversal Path Planning and System Design of Intelligent Lawn Mower Based on Hybrid Algorithm 计算机科学, 2021, 48(6A): 633-637. https://doi.org/10.11896/jsjkx.201100002 |
[7] | 杜婉茹, 王潇茵, 田涛, 张越. 面向未知环境及动态障碍的人工势场路径规划算法 Artificial Potential Field Path Planning Algorithm for Unknown Environment and Dynamic Obstacles 计算机科学, 2021, 48(2): 250-256. https://doi.org/10.11896/jsjkx.191100170 |
[8] | 郭启程, 杜晓玉, 张延宇, 周毅. 基于改进鲸鱼算法的无人机三维路径规划 Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm 计算机科学, 2021, 48(12): 304-311. https://doi.org/10.11896/jsjkx.201000021 |
[9] | 赵杨, 倪志伟, 朱旭辉, 刘浩, 冉家敏. 基于改进狮群进化算法的面向空间众包平台的多工作者多任务路径规划方法 Multi-worker and Multi-task Path Planning Based on Improved Lion Evolutionary Algorithm forSpatial Crowdsourcing Platform 计算机科学, 2021, 48(11A): 30-38. https://doi.org/10.11896/jsjkx.201200085 |
[10] | 曹波, 陈锋, 成静, 李华, 李永乐. 基于全向路口模型的非结构化道路重复节点路径规划 Route Planning of Unstructured Road Including Repeat Node Based on Bidirectional Search 计算机科学, 2021, 48(11A): 77-80. https://doi.org/10.11896/jsjkx.201200193 |
[11] | 陈继清, 谭成志, 莫荣现, 王志奎, 吴家华, 赵超阳. 基于人工势场的A*算法的移动机器人路径规划 Path Planning of Mobile Robot with A* Algorithm Based on Artificial Potential Field 计算机科学, 2021, 48(11): 327-333. https://doi.org/10.11896/jsjkx.200900170 |
[12] | 赵晓薇, 朱小军, 韩周卿. 面向定位应用的无人机的悬停位置和飞行路径优化 Hover Location Selection and Flight Path Optimization for UAV for Localization Applications 计算机科学, 2021, 48(11): 345-355. https://doi.org/10.11896/jsjkx.201000105 |
[13] | 王梓强, 胡晓光, 李晓筱, 杜卓群. 移动机器人全局路径规划算法综述 Overview of Global Path Planning Algorithms for Mobile Robots 计算机科学, 2021, 48(10): 19-29. https://doi.org/10.11896/jsjkx.200700114 |
[14] | 杨德成, 李凤岐, 王祎, 王胜法, 殷慧殊. 智能3D打印路径规划算法 Intelligent 3D Printing Path Planning Algorithm 计算机科学, 2020, 47(8): 267-271. https://doi.org/10.11896/jsjkx.190700184 |
[15] | 姜辰凯, 李智, 盘书宝, 王勇军. 基于改进Dijkstra算法的AGVs无碰撞路径规划 Collision-free Path Planning of AGVs Based on Improved Dijkstra Algorithm 计算机科学, 2020, 47(8): 272-277. https://doi.org/10.11896/jsjkx.190700138 |
|