计算机科学 ›› 2019, Vol. 46 ›› Issue (11A): 134-137.
李珊珊, 刘福江, 林伟华
LI Shan-shan, LIU Fu-jiang, LIN Wei-hua
摘要: 针对多起点、多待救援点、多出口的联合应急救援实时路径规划问题,提出了改进蚁群算法(IACA),设计了一种组合优化的路径构造方法。为了提高蚁群算法的收敛性,实时更新两位置节点间的当量距离,改进信息素更新规则,自适应地动态调整信息素挥发度参数,构造了一种与蚁群算法有效结合的局部搜索算法,提高了算法快速寻优的能力。为了解决传统路径规划的单一应急救援的局限性问题,文中提出一种组合优化蚁群算法的路径构造方法。仿真结果表明:所提方法能够实时、快速地找到一种从多个起点到多个待救援点再回到多个出口之间的最佳组合优化路径,且收敛速度和最短路径较传统算法更优,可以较好地提高在大型应急救援路径规划中的速率和优化程度。
中图分类号:
[1]公安部消防局.中国消防年鉴2015[M].昆明:云南人民出版社,2015. [2]公安部消防局.中国消防年鉴2014[M].昆明:云南人民出版社,2014. [3]公安部消防局.中国消防年鉴2013[M].昆明:云南人民出版社,2013. [4]公安部消防局.中国消防年鉴2012[M].昆明:云南人民出版社,2012. [5]公安部消防局.中国消防年鉴2011[M].昆明:云南人民出版社,2011. [6]公安部消防局.中国消防年鉴2010[M].昆明:云南人民出版社,2010. [7]DORIGO M.Optimization,learning and natural algorithms[D].Milano:Politecnico di Milano,1992. [8]YANG J,SHI M,HAN Z.Research Intelligent Fire Evacuation System Based on Ant Colony Algorithm and MapX[C]∥Se-venth International Symposium on Computational Intelligence and Design.IEEE,2015:100-103. [9]尹克强,郭勇,王丹.WSN在地铁车辆车载设备火灾预警中应用[J].仪表技术与传感器,2014,3(5):87-89. [10]刘笑笑,汪云甲,毕京学,等.矿井火灾逃生路径规划及其三维仿真研究[J].中国安全科学学报,2017,27(10):26-31. [11]ADHIKARI J,PATIL S.Double threshold energy aware load balancing in cloud computing [C]∥2013 Fourth Internat lal Conference on Computing,Communications and Networking Technologies (ICCCNT).IEEE,2013:1-6. [12]NING J,ZHANG Q,ZHANG C,et al.A best-path-updating information-guided ant colony optimization algorithm[J].Information Sciences,2018,433-434:142-162. [13]VISERAS A,LOSADA R O,MERINO L.Planning with ants:Efficient path planning with rapidly exploring random trees and ant colony optimization[J].Int J of Advanced Robotic Systems,2016,13(5):1-16. [14]周锦龙,易永华.基于蚁群算法的矿井救援最短路径研究[J].煤炭技术,2015,34(11):196-197. [15]中华人民共和国国家标准.GB 50016-2014.建筑设计防火规范[S].北京:中国计划出版社,2014. [16]JIAO Z,MA K,RONG Y,et al.A path planning method using adaptive polymorphic ant colony algorithm for smart wheelchairs[J].Journal of Computational Science,2018,25:50-57. [17]MUKHOPADHYAY A,MAULIK U,BBANDYOPADHYA-YS,et al.Survey of Multiobjective Evolutionary Algorithms for Data BANDYOPADHYAY:Part II [J].IEEE Transactions on Evolutionary Computation,2014,18(1):20-35. [18]王晓燕,杨乐,张宇,等.基于改进势场蚁群算法的机器人路径规划[J].控制与决策,2018,33(10):775-1781. [19]杜鹏桢,唐振民,陆建峰,等.不确定环境下基于改进萤火虫算法的地面自主车辆全局路径规划方法[J].电子学报,2014,42(3):616-624. [20]PANDA R K,CHOUDHURY B B.An effective path planning of mobile robot using genetic algorithm[C]∥IEEE Int Conf on Computational Intelligence & Communication Technology.Ghaziabad,2015:287-291. |
[1] | 王兵, 吴洪亮, 牛新征. 基于改进势场法的机器人路径规划 Robot Path Planning Based on Improved Potential Field Method 计算机科学, 2022, 49(7): 196-203. https://doi.org/10.11896/jsjkx.210500020 |
[2] | 杨浩雄, 高晶, 邵恩露. 考虑一单多品的外卖订单配送时间的带时间窗的车辆路径问题 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 |
[3] | 谭任深, 徐龙博, 周冰, 荆朝霞, 黄向生. 海上风电场通用运维路径规划模型优化及仿真 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 |
[4] | 沈彪, 沈立炜, 李弋. 空间众包任务的路径动态调度方法 Dynamic Task Scheduling Method for Space Crowdsourcing 计算机科学, 2022, 49(2): 231-240. https://doi.org/10.11896/jsjkx.210400249 |
[5] | 陈镜宇, 郭志军, 尹亚昆. 基于混合算法的智能割草机全遍历路径规划及其系统设计 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 |
[6] | 杜婉茹, 王潇茵, 田涛, 张越. 面向未知环境及动态障碍的人工势场路径规划算法 Artificial Potential Field Path Planning Algorithm for Unknown Environment and Dynamic Obstacles 计算机科学, 2021, 48(2): 250-256. https://doi.org/10.11896/jsjkx.191100170 |
[7] | 郭启程, 杜晓玉, 张延宇, 周毅. 基于改进鲸鱼算法的无人机三维路径规划 Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm 计算机科学, 2021, 48(12): 304-311. https://doi.org/10.11896/jsjkx.201000021 |
[8] | 赵杨, 倪志伟, 朱旭辉, 刘浩, 冉家敏. 基于改进狮群进化算法的面向空间众包平台的多工作者多任务路径规划方法 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 |
[9] | 曹波, 陈锋, 成静, 李华, 李永乐. 基于全向路口模型的非结构化道路重复节点路径规划 Route Planning of Unstructured Road Including Repeat Node Based on Bidirectional Search 计算机科学, 2021, 48(11A): 77-80. https://doi.org/10.11896/jsjkx.201200193 |
[10] | 陈继清, 谭成志, 莫荣现, 王志奎, 吴家华, 赵超阳. 基于人工势场的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 |
[11] | 赵晓薇, 朱小军, 韩周卿. 面向定位应用的无人机的悬停位置和飞行路径优化 Hover Location Selection and Flight Path Optimization for UAV for Localization Applications 计算机科学, 2021, 48(11): 345-355. https://doi.org/10.11896/jsjkx.201000105 |
[12] | 王梓强, 胡晓光, 李晓筱, 杜卓群. 移动机器人全局路径规划算法综述 Overview of Global Path Planning Algorithms for Mobile Robots 计算机科学, 2021, 48(10): 19-29. https://doi.org/10.11896/jsjkx.200700114 |
[13] | 杨德成, 李凤岐, 王祎, 王胜法, 殷慧殊. 智能3D打印路径规划算法 Intelligent 3D Printing Path Planning Algorithm 计算机科学, 2020, 47(8): 267-271. https://doi.org/10.11896/jsjkx.190700184 |
[14] | 姜辰凯, 李智, 盘书宝, 王勇军. 基于改进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 |
[15] | 曾伟良, 吴淼森, 孙为军, 谢胜利. 自动驾驶出租车调度系统研究综述 Comprehensive Review of Autonomous Taxi Dispatching Systems 计算机科学, 2020, 47(5): 181-189. https://doi.org/10.11896/jsjkx.190400031 |
|