基于回溯蚁群-粒子群混合算法的多点路径规划

刘丽珏; 罗舒宁; 高琰; 陈美妃

doi:10.11959/j.issn.1000-436x.2019039

您当前的位置：

首页 >

文章列表页 >

基于回溯蚁群-粒子群混合算法的多点路径规划

学术论文 | 更新时间：2024-06-05

- 基于回溯蚁群-粒子群混合算法的多点路径规划
- Multi-point path planning based on the algorithm of colony-particle swarm optimization
- 通信学报 2019年40卷第2期页码：102-110
- 作者机构：
  
  中南大学信息科学与工程学院，湖南长沙 410083
- 作者简介：
  
  [ "刘丽珏（1973- ），女，湖南长沙人，博士，中南大学副教授，主要研究方向为智能计算、人工智能、机器学习。" ]
  [ "罗舒宁（1993- ），女，山东泰安人，中南大学硕士生，主要研究方向为多点路径规划。" ]
  [ "高琰（1973- ），女，湖南长沙人，博士，中南大学副教授，主要研究方向为智能信息处理。" ]
  [ "陈美妃（1998- ），女，广西壮族自治区，主要研究方向为大数据、云计算。" ]
- 基金信息：
  
  国家科技重大专项基金资助项目(2013FY110800);长沙计划科技基金资助项目(kq1606004)
- DOI：10.11959/j.issn.1000-436x.2019039
  中图分类号： TP399
- 网络出版日期：2019-02，
  
  纸质出版日期：2019-02-25
- 稿件说明：
移动端阅览
刘丽珏, 罗舒宁, 高琰, 等. 基于回溯蚁群-粒子群混合算法的多点路径规划[J]. 通信学报, 2019,40(2):102-110.

Lijue LIU, Shuning LUO, Yan GAO, et al. Multi-point path planning based on the algorithm of colony-particle swarm optimization[J]. Journal on communications, 2019, 40(2): 102-110.
刘丽珏, 罗舒宁, 高琰, 等. 基于回溯蚁群-粒子群混合算法的多点路径规划[J]. 通信学报, 2019,40(2):102-110. DOI： 10.11959/j.issn.1000-436x.2019039.

Lijue LIU, Shuning LUO, Yan GAO, et al. Multi-point path planning based on the algorithm of colony-particle swarm optimization[J]. Journal on communications, 2019, 40(2): 102-110. DOI： 10.11959/j.issn.1000-436x.2019039.

摘要

景区多点路径规划问题是一个NP-hard问题，相当于寻找经过起始点和特定节点的最短路径。针对多点路径规划问题，提出了回溯蚁群-粒子群混合算法，该算法运用弗洛伊德（Floyd-Warshall）算法将图进行转换并且结合了蚁群算法和粒子群算法寻找最短路径。实验结果表明，此算法可以在小规模数据下快速找到精确解，同时，在较大规模数据量下，可以得到比最大最小蚁群算法和遗传算法更好的结果。

Abstract

The problem of multi-point path planning is a NP-hard problem

which is equivalent to finding the shortest path of a starting point and some specific node.Aiming at the problem of multi-point path planning

a retrospective ant colony-particle swarm optimization algorithm was proposed.This algorithm used Floyd-Warshall to transform the graph and combined ant colony algorithm and particle swarm algorithm to find the shortest path.The experimental results show that this algorithm can find the precise solution under small data

at the same time

under a large amount of data

can be better than the maximum minimum ant colony algorithm and genetic algorithm.

关键词

Keywords

references

朱庆 , 王烨萍 , 张骏骁 , 等 . 综合导航网格模型及其在智慧旅游寻径中的应用 [J ] . 西南交通大学学报 , 2017 , 52 ( 1 ): 195 - 201 .

ZHU Q , WANG Y P , ZHANG J X , et al . Integrated navigation grid model and its applications in smart tourism routing [J ] . Journal of Southwest Jiaotong University , 2017 , 52 ( 1 ): 195 - 201 .

吕琼艺 . 基于改进的 Dijkstra算法的旅游规划线路研究与实践 [J ] . 柳州职业技术学院学报 , 2017 , 17 ( 2 ): 32 - 36 .

LV Q Y . Research and practice of tourism planning line based on improved Dijkstra algorithm [J ] . Journal of Liuzhou Vocational ＆Technical College , 2017 , 17 ( 2 ): 32 - 36 .

胡军国 , 祁亨年 , 董峰 , 等 . 一种改进蚁群算法研究和旅游景区路径规划问题求解 [J ] . 计算机应用研究 , 2011 , 28 ( 5 ): 1647 - 1650 .

HU J G , QI H N , DONG F , et al . Improved ant colony algorithm for path planning of tourist scenic are [J ] . Application Research of Computers , 2011 , 28 ( 5 ): 1647 - 1650 .

蒋仲安 , 王明 , 陈雅 . 基于地理坐标和轨迹数据的路径推荐方法 [J ] . 通信学报 , 2017 , 38 ( 5 ): 165 - 171 .

JIANG Z A , WANG M , CHEN Y . Path recommendation based on geographic coordinates and trajectory data [J ] . Journal on Communications , 2017 , 38 ( 5 ): 165 - 171 .

STÜTZLE T , HOOS H H . Max-min ant system [J ] . Future Generation Computer Systems , 2000 , 16 ( 08 ): 889 - 914

EBERHART R C , KENNEDY J . A new optimizer using particle swarm theory [C ] // The 6th International Symposium on Micro Machine And Human Science , 1995 : 39 - 43 .

FLOYD R W . Algorithm 97:shortest path [J ] . Communications of the ACM , 1962 , 5 ( 6 ):345.

LETCHFORD A N , NASIRI S D , THEIS D O . Compact formulations of the Steiner traveling salesman problem and related problems [J ] . European Journal of Operational Research , 2013 , 228 ( 01 ): 83 - 92

JEPSEN M K , PETERSEN B , SPOORENDONK S . A branch-and-cut algorithm for the capacitated profitable tour problem [J ] . Discrete Optimization , 2014 , 14 ( C ): 78 - 96 .

ROSTAMI B , MALUCELLI F , BELOTTI P . Lower bounding procedure for the asymmetric quadratic traveling salesman problem [J ] . European Journal of Operational Research , 2016 , 253 ( 03 ): 584 - 592

普兴成 , 李俊杰 , 吴慧超 , 等 . 基于改进粒子群算法的移动机器人多目标点路径规划 [J ] . 智能系统学报 , 2017 , 12 ( 3 ): 301 - 309 .

PU X C , LI J J , WU H C , et al . Mobile robot multi-goal path planning using improved particle swarm optimization [J ] . CAAI Transactions on Intelligent Systems , 2017 , 12 ( 3 ): 301 - 309 .

郑继明 , 杨坤 , 柳慧鹏 , 等 . 基于0-1线性规划的多点路由规划模型研究 [J ] . 通信技术 , 2017 , 50 ( 7 ): 1443 - 1446 .

ZHENG J M , YANG K , LIU H P , et al . Multicast routing model based on 0-1 linear programming [J ] . Communications Technology , 2017 , 50 ( 07 ): 1443 - 1446 .

浏览量

885

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

QoE感知的FiWi视频分发机制

基于大数据和优化神经网络短期电力负荷预测

基于商空间的层次式数据网格资源调度算法