Multi-point path planning based on the algorithm of colony-particle swarm optimization

Lijue LIU; Shuning LUO; Yan GAO; Meifei CHEN

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

您当前的位置：

首页 >

文章列表页 >

Multi-point path planning based on the algorithm of colony-particle swarm optimization

Papers | 更新时间：2024-06-05

- Multi-point path planning based on the algorithm of colony-particle swarm optimization
- Journal on Communications Vol. 40, Issue 2, Pages: 102-110(2019)
- 作者机构：
  
  中南大学信息科学与工程学院，湖南长沙 410083
- 作者简介：
- 基金信息：
  
  National Science and Technology Major Project(2013FY110800);Planned Science and Technology Project of Changsha(kq1606004)
- DOI：10.11959/j.issn.1000-436x.2019039
  CLC： TP399
- Online First：2019-02，
  
  Published：25 February 2019
- 稿件说明：
移动端阅览
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：

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 .

Views

2674

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

QoE-aware video distribution mechanism in FiWi

Power short-term load forecasting based on big data and optimization neural network

Hierarchical data grid resource allocation based on quotient space theory

Related Author

Ruyan WANG

Yan YANG

Dapeng WU

Xin JIN

Long-wei LI

Jia-nan JI

Zhi-qi LI

Yu HU

Related Institution

Key Laboratory of Optical Communication and Networks,Chongqing University of Posts and Telecommunications

School of Information, Central University of Finance and Economics

Personnel Testing Center,Ministry of Human Resources and Social Security

Beijing State Power Communication Network Technology Company

Liaoning Power Supply Company ICT Branch of State Grid Corporation

AI问答

⁰