A solution of TSP based on the ant colony algorithm improved by particle swarm optimization

Miao Yu

doi:10.3934/dcdss.2019066

Article Contents

2019, Volume 12, Issue 4&5: 979-987. Doi: 10.3934/dcdss.2019066 open access

This issue Previous Article Retraction: Xiao-Qian Jiang and Lun-Chuan Zhang, A pricing option approach based on backward stochastic differential equation theory Next Article Environmental game modeling with uncertainties

A solution of TSP based on the ant colony algorithm improved by particle swarm optimization

Miao Yu^,

China University of Political Science and Law, Beijing, China

* Corresponding author: Miao Yu.
* Corresponding author: Miao Yu.

Received: May 31, 2017

Revised: October 31, 2017

Published: March 2019

The first author is supported by Training and Supporting Project for Young or Middle-aged Teachers of China University of Political Science and Law, College Scientific Research Project of China University of Political Science and Law (Grant No. 17ZFG63001) and NSF of China (Grant No. L1422009)

Abstract Full Text(HTML) Figure(3) / Table(1) Related Papers Cited by

Abstract

TSP is a classic problem in the field of logistics, and ant colony algorithm is an important way to solve the problem. However, the ant colony algorithm has some shortcomings in practical application. In this paper, the ant colony algorithm is improved by particle swarm optimization algorithm, and the ant colony algorithm is obtained by giving the ant colony a certain ''particle property''. Finally, an example is given to demonstrate the effectiveness of the improved ant colony algorithm.

Keywords:

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

Citation:

FullText(HTML)

Figure 1. The flow chart of improved ant colony algorithm

Download: Full-size image PowerPoint slide

Figure 2. The simulation results of the basic ant colony algorithm

Download: Full-size image PowerPoint slide

Figure 3. The simulation results of the improved ant colony algorithm

Download: Full-size image PowerPoint slide

Table 1. Observations' latitude and longitude

Number	City	Longitude	latitude
1	Zhengzhou	113.63E	34.75N
2	Anyang	114.4E	36.1N
3	Hebi	114.3E	35.75N
4	Jiaozuo	113.25E	35.22N
5	Kaifeng	114.32E	34.8N
6	Luohe	114.02E	33.59N
7	Luoyang	112.46E	34.63N
8	Nanyang	112.54E	33N
9	Pingdingshan	113.2E	33.77N
10	Puyang	115.04E	35.77N
11	Sanmenxia	111.21E	34.78N
12	Shangqiu	115.66E	34.42N
13	Xinxiang	113.93E	35.31N
14	Xinyang	114.1E	32.15N
15	Xuchang	113.86E	34.04N
16	Zhoukou	114.7E	33.63N
17	Zhumadian	113.03E	33.02N

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	Y. An, Application of linear programming theory to strengthen the cost control of engineering project Railway engineering cost management, 2013.
[2]	G. Barbarosoglu and D. Ozgur, A tabu seacrh algorithm for the vehiciel routing problem, Computers & Operations Reseacrh, 26 (1999), 255-270. doi: 10.1016/S0305-0548(98)00047-1.
[3]	M. L. Bech and E. Atalay, The topology of the federal funds market, Physica A: Statistical Mechanics and its Applications, 389 (2010), 5223-5246. https://www.sciencedirect.com/science/article/pii/S0378437110004887.
[4]	I. Ciornei and E. Kyriakides, Hybrid ant colony-genetic algorithm (GAAPI) for global continuous optimization, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 42 (2012), 234-245. https://ieeexplore.ieee.org/document/6008671.
[5]	M. Dorigo, V. Maniezzo and A. Colorni, Positive feedback as a Search Strategy, Technical Report, 1991, 91-106. https://www.researchgate.net/publication/2573263_Positive_Feedback_as_a_Search_Strategy.
[6]	M. Dorigo and L. M. Gambardella, Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation 1997, 1(1): 53-66. https://ieeexplore.ieee.org/abstract/document/585892.
[7]	H. Hernández and C. Blum, Foundations of antcycle: Self-synchronized duty-cycling in mobile sensor networks, Computer Journal, 54 (2011), 1427-1448. https://ieeexplore.ieee.org/document/8130483.
[8]	S. Kirkpatrick1, C. D. Gelatt Jr. and M. P. Vecchi, Optimization by simulated annealing, Science, 220 (1983), 671-680. doi: 10.1126/science.220.4598.671.
[9]	F. Liu, S. Zhao, M. Weng and Y. Liu, Fire risk assessment for large-scale commercial buildings based on structure entropy weight method, Safety Sci., 94 (2017), 26-40. https://www.sciencedirect.com/science/article/pii/S0925753516306531?via.
[10]	Y. Z. Liu and Z. P. Fan, Multiple attribute decision making considering attribute aspirations: A method based on prospect theory, Kongzhi Yu Juece/control & Decision, 30 (2015), 91-97. http://en.cnki.com.cn/Article_en/CJFDTOTAL-KZYC201501017.htm.
[11]	L. Liu, T. Zhang and B. Ru, A flying qualities assessment model based on multiparameter integration, Computer Engineering and Science, 38 (2016), 1262-1268. https://www.sciencedirect.com/science/article/pii/S1389041718302365.
[12]	S. C. Nicolis and J. L. Deneubourg, Emerging patterns and food recruitment in ants: An analytical study, Journal of Theoretical Biology, 198 (1999), 575-592. https://www.sciencedirect.com/science/article/pii/S0022519399909347.
[13]	M. W. P. Savelsbergh, Local search in routing problems with time windows, Annals of Operations Research, 4 (1985), 285-305. doi: 10.1007/BF02022044.
[14]	L. Santos, J. Coutinho-Rodrigues and J. R. Current, An improved ant colony optimization based algorithm for the capacitated arc routing problem, Transportation Research Part B: Methodological, 44 2010,246-266. https://www.sciencedirect.com/science/article/pii/S0191261509000836.
[15]	T. Stützle and H. H. Hoos, MAX-MIN ant system, Future Generation Computer Systems, 16 (2000), 889-914. https://www.sciencedirect.com/science/article/pii/S0167739X00000431.
[16]	M. Yu, S. Li, M Kong, J. Song and G. Ren, Comparison of advantages and disadvantages among various algorithms in logisticspath designTaking H-group as an example, Cognitive Systems Research, 52(2018) 843-852. https://www.sciencedirect.com/science/article/pii/S1389041718302365. doi: 10.1016/j.cogsys.2018.08.014.
[17]	M. Yu, J. Song, D. Zhao and G. Ren, Management of expressway service area based on integrated optimization, Cognitive Systems Research, 52 (2018) 875-881. https://www.sciencedirect.com/science/article/pii/S1389041718302390. doi: 10.1016/j.cogsys.2018.08.013.
[18]	Z. Zhang, Y. Shi and G. Gao, A rough set-based multiple criteria linear programming approach for the medical diagnosis and prognosis, Expert Systems with Applications, 36 (2009), 8932-8937.https://www.semanticscholar.org/paper/A-rough-set-based-multiple-criteria-linear-approach-Zhang-Shi/73209c1d7bc7051a4cd64c059d0edf2cfad86840. doi: 10.1016/j.eswa.2008.11.007.
[19]	S. Zhou, C. Hu and X. Qiao, et al., A forecasting method for Chinese civil planes attendance rate based on vague sets. Chaos Solitons & Fractals the Interdisciplinary Journal of Nonlinear Science & Nonequilibrium & Complex Phenomena, 89 (2016), 518-526. https://www.sciencedirect.com/science/article/pii/S0960077916300649?via.
[20]	S. Zhou, W. Liu and W. Chang, An improved TOPSIS with weighted hesitant vague information, Chaos Solitons & Fractals the Interdisciplinary Journal of Nonlinear Science & Nonequilibrium & Complex Phenomena, 89 (2016), 47-53. https://www.sciencedirect.com/science/article/pii/S0960077915002970.