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

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

Abstract

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.

Key words: NP-hard problem, max-min ant system, Floyd-Warshall, particle swarm algorithm

CLC Number:

TP399

Lijue LIU,Shuning LUO,Yan GAO,Meifei CHEN. Multi-point path planning based on the algorithm of colony-particle swarm optimization[J]. Journal on Communications, 2019, 40(2): 102-110.

Figures/Tables 8

References 12

[1]	朱庆, 王烨萍, 张骏骁 ,等. 综合导航网格模型及其在智慧旅游寻径中的应用[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.
[2]	吕琼艺 . 基于改进的 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.
[3]	胡军国, 祁亨年, 董峰 ,等. 一种改进蚁群算法研究和旅游景区路径规划问题求解[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.
[4]	蒋仲安, 王明, 陈雅 . 基于地理坐标和轨迹数据的路径推荐方法[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.
[5]	STüTZLE T , HOOS H H . Max-min ant system[J]. Future Generation Computer Systems, 2000,16(08): 889-914
[6]	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.
[7]	FLOYD R W . Algorithm 97:shortest path[J]. Communications of the ACM, 1962,5(6):345.
[8]	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
[9]	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.
[10]	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
[11]	普兴成, 李俊杰, 吴慧超 ,等. 基于改进粒子群算法的移动机器人多目标点路径规划[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.
[12]	郑继明, 杨坤, 柳慧鹏 ,等. 基于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.

Metrics

Recommended 0

No Suggested Reading articles found!

名称	参数值
蚁群大小	m=city
起始信息素	τ₀=τ_min
信息素相关参数	α= 1
启发因子相关参数	β= 5
信息素削减因子	ρ=0.98
用于τ_min的参数	p_best=0.005
参数ω	ω=0.000 1

数据	各算法间比较
	BAPM算法			MMAS算法			GA算法
	平均偏差	max	min	平均偏差	max	min	平均偏差	max	min
ft17	0.0%	39	39	0.0%	39	39	0.0%	39	39
ft53	1.9%	7 344	6 905	3.2%	7 344	6 905	4.1%	7 372	6 095
ft70	1.0%	39 102	38 673	2.9%	40 109	38 673	3.3%	40 109	38 673
ftv33	0.0%	1 286	1 286	0.0%	1 286	1 286	0.0%	1 286	1 286
ftv35	0.0%	1 473	1 473	0.02%	1 477	1 473	0.0%	1 473	1 473
ftv38	0.0%	1 530	1 530	0.05%	1 549	1 530	0.0%	1 530	1 530
ftv44	0.0%	1 613	1 613	0.01%	1 615	1 613	0.0%	1 613	1 613
ftv47	0.4%	1 791	1 776	0.8%	1 791	1 791	0.4%	1 791	1 776
ftv55	0.1%	1 613	1 608	1.0%	1 643	1 608	0.7%	1 631	1 608
ftv64	0.2%	1 844	1 839	1.6%	1 893	1 844	0.2%	1 844	1 844
ftv70	1.9%	2 078	1 950	7.5%	2 114	1 950	6.2%	2 078	2 078
kro124	3.4%	37 693	37 287	3.5%	37 739	37 287	4.2%	37 804	37 739
p43	0.0%	5 620	5 620	0.1%	5 647	5 620	0.2%	5 647	5 620
ry48p	0.4%	14 507	14 459	1.1%	14 603	14 570	0.8%	14 603	14 459

景点序号	景点名称	经度	纬度
1	问天台*	112.966 631°	28.171 271°
2	指点江山石碑*	112.966 793°	28.171 637°
3	望江亭 *	112.966 811°	28.171 796°
4	毛泽东青年艺术雕像*	112.966 802°	28.173 412°
5	沁园春诗词碑*	112.968 028°	28.187 983°
6	长株潭两型社会展览馆	112.966 938°	28.178 382°
7	竹园	112.967 779°	28.179 878°
8	朱张渡	112.966 456°	28.180 764°
9	唐生智公馆旧址站点	112.966 919°	28.183 873°
10	潇湘名人旧址	112.967 835°	28.183 717°
11	江神庙	112.969 802°	28.204 733°
12	桃园	112.967 844°	28.184 935°
13	桂园	112.968 208°	28.186 169°
14	桂园诗词碑	112.968 033°	28.187 964°
15	九州龙骧码	112.967 482°	28.189 632°
16	百米高喷	112.967 913°	28.190 228°
17	婚庆园#	112.968 614°	28.199 179°
18	美孚洋行旧址#	112.968 347°	28.193 838°
19	枕江亭观光车售票处*#	112.968 865°	28.196 559°
20	财神古殿#	112.967 534°	28.196 197°
22	橘子洲古董钢琴博物馆	112.968 69°	28.196 961°
23	橘子洲入口	112.969 148°	28.197 757°
24	橘子洲人行入口#	112.968 542°	28.197 793°
25	橘子洲西大门#	112.967 535°	28.198 004°
26	原长沙海关旧址#	112.968 614°	28.199 179°
27	地铁站西站口#	112.967 998°	28.200 396°

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 12

Related Articles 5

Metrics

Recommended 0

[1]	Ruyan WANG,Yan YANG,Dapeng WU. QoE-aware video distribution mechanism in FiWi [J]. Journal on Communications, 2018, 39(1): 1-13.
[2]	Xin JIN,Long-wei LI,Jia-nan JI,Zhi-qi LI,Yu HU,Yong-bin ZHAO. Power short-term load forecasting based on big data and optimization neural network [J]. Journal on Communications, 2016, 37(Z1): 36-42.
[3]	Yan-hang ZHAO,Zhi-hong QIAN,Xiao-hang SHANG,Chao CHENG. PSO localization algorithm for WSN nodes based on modifying average hop distances [J]. Journal on Communications, 2013, 34(9): 105-114.
[4]	. Hierarchical data grid resource allocation based on quotient space theory [J]. Journal on Communications, 2013, 34(6): 18-155.
[5]	Chun-zhong XIA,Shun-lin SONG. Hierarchical data grid resource allocation based on quotient space theory [J]. Journal on Communications, 2013, 34(6): 146-155.