doi: 10.3934/dcdss.2019066

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

China University of Political Science and Law, Beijing, China

* Corresponding author: Miao Yu.

Received  June 2017 Revised  November 2017 Published  November 2018

Fund Project: 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)

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.

Citation: Miao Yu. A solution of TSP based on the ant colony algorithm improved by particle swarm optimization. Discrete & Continuous Dynamical Systems - S, doi: 10.3934/dcdss.2019066
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. Kirkpatrick1C. 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.

show all references

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. Kirkpatrick1C. 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.

Figure 1.  The flow chart of improved ant colony algorithm
Figure 2.  The simulation results of the basic ant colony algorithm
Figure 3.  The simulation results of the improved ant colony algorithm
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
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
[1]

Min Zhang, Gang Li. Multi-objective optimization algorithm based on improved particle swarm in cloud computing environment. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 1413-1426. doi: 10.3934/dcdss.2019097

[2]

Mingyong Lai, Xiaojiao Tong. A metaheuristic method for vehicle routing problem based on improved ant colony optimization and Tabu search. Journal of Industrial & Management Optimization, 2012, 8 (2) : 469-484. doi: 10.3934/jimo.2012.8.469

[3]

Jean-Paul Arnaout, Georges Arnaout, John El Khoury. Simulation and optimization of ant colony optimization algorithm for the stochastic uncapacitated location-allocation problem. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1215-1225. doi: 10.3934/jimo.2016.12.1215

[4]

Qifeng Cheng, Xue Han, Tingting Zhao, V S Sarma Yadavalli. Improved particle swarm optimization and neighborhood field optimization by introducing the re-sampling step of particle filter. Journal of Industrial & Management Optimization, 2019, 15 (1) : 177-198. doi: 10.3934/jimo.2018038

[5]

Mohamed A. Tawhid, Kevin B. Dsouza. Hybrid binary dragonfly enhanced particle swarm optimization algorithm for solving feature selection problems. Mathematical Foundations of Computing, 2018, 1 (2) : 181-200. doi: 10.3934/mfc.2018009

[6]

Pikkala Vijaya Laxmi, Singuluri Indira, Kanithi Jyothsna. Ant colony optimization for optimum service times in a Bernoulli schedule vacation interruption queue with balking and reneging. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1199-1214. doi: 10.3934/jimo.2016.12.1199

[7]

A. Zeblah, Y. Massim, S. Hadjeri, A. Benaissa, H. Hamdaoui. Optimization for series-parallel continuous power systems with buffers under reliability constraints using ant colony. Journal of Industrial & Management Optimization, 2006, 2 (4) : 467-479. doi: 10.3934/jimo.2006.2.467

[8]

Junyuan Lin, Timothy A. Lucas. A particle swarm optimization model of emergency airplane evacuations with emotion. Networks & Heterogeneous Media, 2015, 10 (3) : 631-646. doi: 10.3934/nhm.2015.10.631

[9]

Tao Zhang, Yue-Jie Zhang, Qipeng P. Zheng, P. M. Pardalos. A hybrid particle swarm optimization and tabu search algorithm for order planning problems of steel factories based on the Make-To-Stock and Make-To-Order management architecture. Journal of Industrial & Management Optimization, 2011, 7 (1) : 31-51. doi: 10.3934/jimo.2011.7.31

[10]

Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2018142

[11]

Ning Lu, Ying Liu. Application of support vector machine model in wind power prediction based on particle swarm optimization. Discrete & Continuous Dynamical Systems - S, 2015, 8 (6) : 1267-1276. doi: 10.3934/dcdss.2015.8.1267

[12]

Xia Zhao, Jianping Dou. Bi-objective integrated supply chain design with transportation choices: A multi-objective particle swarm optimization. Journal of Industrial & Management Optimization, 2018, 13 (5) : 1-26. doi: 10.3934/jimo.2018095

[13]

Harish Garg. Solving structural engineering design optimization problems using an artificial bee colony algorithm. Journal of Industrial & Management Optimization, 2014, 10 (3) : 777-794. doi: 10.3934/jimo.2014.10.777

[14]

Jiao-Yan Li, Xiao Hu, Zhong Wan. An integrated bi-objective optimization model and improved genetic algorithm for vehicle routing problems with temporal and spatial constraints. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-18. doi: 10.3934/jimo.2018200

[15]

Guangzhou Chen, Guijian Liu, Jiaquan Wang, Ruzhong Li. Identification of water quality model parameters using artificial bee colony algorithm. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 157-165. doi: 10.3934/naco.2012.2.157

[16]

Mingfang Ding, Yanqun Liu, John Anthony Gear. An improved targeted climbing algorithm for linear programs. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 399-405. doi: 10.3934/naco.2011.1.399

[17]

Honggang Yu. An efficient face recognition algorithm using the improved convolutional neural network. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 901-914. doi: 10.3934/dcdss.2019060

[18]

Xiangyu Gao, Yong Sun. A new heuristic algorithm for laser antimissile strategy optimization. Journal of Industrial & Management Optimization, 2012, 8 (2) : 457-468. doi: 10.3934/jimo.2012.8.457

[19]

Adil Bagirov, Sona Taheri, Soodabeh Asadi. A difference of convex optimization algorithm for piecewise linear regression. Journal of Industrial & Management Optimization, 2018, 13 (5) : 1-24. doi: 10.3934/jimo.2018077

[20]

Yong Wang, Wanquan Liu, Guanglu Zhou. An efficient algorithm for non-convex sparse optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2018134

2017 Impact Factor: 0.561

Metrics

  • PDF downloads (6)
  • HTML views (72)
  • Cited by (0)

Other articles
by authors

[Back to Top]