August & September  2019, 12(4&5): 979-987. 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, 2019, 12 (4&5) : 979-987. 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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

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]

Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005

[2]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

[3]

Gongbao Li, Tao Yang. Improved Sobolev inequalities involving weighted Morrey norms and the existence of nontrivial solutions to doubly critical elliptic systems involving fractional Laplacian and Hardy terms. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020469

[4]

Min Xi, Wenyu Sun, Jun Chen. Survey of derivative-free optimization. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 537-555. doi: 10.3934/naco.2020050

[5]

Cheng Peng, Zhaohui Tang, Weihua Gui, Qing Chen, Jing He. A bidirectional weighted boundary distance algorithm for time series similarity computation based on optimized sliding window size. Journal of Industrial & Management Optimization, 2021, 17 (1) : 205-220. doi: 10.3934/jimo.2019107

[6]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115

[7]

Xinpeng Wang, Bingo Wing-Kuen Ling, Wei-Chao Kuang, Zhijing Yang. Orthogonal intrinsic mode functions via optimization approach. Journal of Industrial & Management Optimization, 2021, 17 (1) : 51-66. doi: 10.3934/jimo.2019098

[8]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031

[9]

Yi An, Bo Li, Lei Wang, Chao Zhang, Xiaoli Zhou. Calibration of a 3D laser rangefinder and a camera based on optimization solution. Journal of Industrial & Management Optimization, 2021, 17 (1) : 427-445. doi: 10.3934/jimo.2019119

[10]

Haodong Yu, Jie Sun. Robust stochastic optimization with convex risk measures: A discretized subgradient scheme. Journal of Industrial & Management Optimization, 2021, 17 (1) : 81-99. doi: 10.3934/jimo.2019100

[11]

Ripeng Huang, Shaojian Qu, Xiaoguang Yang, Zhimin Liu. Multi-stage distributionally robust optimization with risk aversion. Journal of Industrial & Management Optimization, 2021, 17 (1) : 233-259. doi: 10.3934/jimo.2019109

[12]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102

[13]

Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117

[14]

M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014

2019 Impact Factor: 1.233

Metrics

  • PDF downloads (245)
  • HTML views (501)
  • Cited by (2)

Other articles
by authors

[Back to Top]