Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Computer Based Stylometric Analysis of Texts in Polish Language Read chapter Read first chapter

2017 | OriginalPaper | Chapter

A DSS Based on Hybrid Ant Colony Optimization Algorithm for the TSP

Authors : Islem Kaabachi, Dorra Jriji, Saoussen Krichen

Published in: Artificial Intelligence and Soft Computing

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The traveling salesman problem (TSP) is one of the most studied problems in combinatorial optimization due to its importance and NP-hard numerous approximation methods were proposed to solve it. In this paper, we propose a new hybrid approach which combines local search with the ant colony optimization algorithm (ACO) for solving the TSP. The performance of the proposed algorithm is highlighted through the implementation of a Decision Support System (DSS). Some benchmark problems are selected to test the performance of the proposed hybrid method. We compare the ability of our algorithm with the classical ACO and against some well-known methods. The experiments show that the proposed hybrid method can efficiently improve the quality of solutions than the classical ACO algorithm, and distinctly speed up computing time. Our approach is also better than the performance of compared algorithms in most cases in terms of solution quality and robustness.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Convolutional Neural Networks for Time Series Classification
next chapter Comparing Strategies for Search Space Boundaries Violation in PSO
Literature
1.
Lawler, E.L., Lenstra, J.K., Kan Rinnooy, A.H.G., Shmoys, D.B.: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, vol. 11, pp. 201–209. Wiley, Chichester (1985)
2.
Johnson, D.S., McGeoch, L.A.: The Travelling Salesman Problem: A Case Study in Local Optimization. In: Aarts, E.H.L., Lenstra, J.K. (eds.) Local Search in Combinatorial Optimization, pp. 215–310. Wiley (1997)
3.
Reinelt, G.: The Traveling Salesman: Computational Solutions for TSP Applications. LNCS, vol. 840. Springer, Heidelberg (1994)MATH
4.
Applegate, D.L., Bixby, R.E., Chvatal, V., Cook, W.J.: The Traveling Salesman Problem: A Computational Study. Princeton University Press, USA (2007)MATH
5.
Arananayakgi, A.: Reduce total distance and time using genetic algorithm in Traveling Salesman Problem. Int. J. Comput. Sci. Eng. Technol. 5(08) (2014). ISSN 2229–3345
6.
Zhong, W.L., Zhang, J., Chen, W.N.: A novel discrete particle swarm optimization to solve traveling salesman problem. In: IEEE Congress on Evolutionary Computation, pp. 3283–3287 (2007)
7.
Knox, J.: Tabu search performance on the symmetric traveling salesman problem. Comput. Oper. Res. 21, 867–876 (1994)CrossRefMATH
8.
Gendreau, M., Laporte, G., Semet, F.: A tabu search heuristic for the undirected selective travelling salesman problem. Eur. J. Oper. Res. 106, 539–545 (1998)CrossRefMATH
9.
Allwright, J.R.A., Carpenter, D.B.: A distributed implementation of simulated annealing for the traveling salesman problem. Parallel Comput. 10, 335–338 (1989)MathSciNetCrossRefMATH
10.
Geng, X., Chen, Z., Yang, W., Shi, D., Zhao, K.: Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search. Appl. Soft Comput. 11, 3680–3689 (2011)CrossRef
11.
Ghaziri, H., Osman, I.H.: A neural network algorithm for the traveling salesman problem with backhauls. Comput. Ind. Eng. 44, 267–281 (2003)CrossRef
12.
Leung, K.S., Jin, H.D., Xu, Z.B.: An expanding self-organizing neural network for the traveling salesman problem. Neurocomputing 62, 267–292 (2004)CrossRef
13.
Pang, W., Wang, K.P., Zhou, C.G., Dong, L.J., Liu, M., Zhang, H.Y., Wang, J.Y.: Modified particle swarm optimization based on space transformation for solving traveling salesman problem. In: Proceedings of the 33rd International Conference on Machine Learning and Cybernetics, pp. 2342–2346 (2004)
14.
Wang, C., Zhang, J., Yang, J., Hu, C., Liu, J.: A modified particle swarm optimization algorithm and its application for solving traveling salesman problem. In: International Conference on Neural Networks and Brain, vol. 2, pp. 689–694 (2005)
15.
Shi, X.H., Liang, Y.C., Lee, H.P., Lu, C., Wang, Q.X.: Particle swarm optimization based algorithms for TSP and generalized TSP. Inf. Process. Lett. 103, 169–176 (2007)MathSciNetCrossRefMATH
16.
Stutzle, T., Hoos, H.H.: Improvements on the ant system: introducing the MAX-MIN ant system. In Albrecht, R.F., Smith, G.D., Steele, N.C. (eds.) Artificial Neural Networks and Genetic Algorithms, pp. 245–249. Springer, Wien (1998)
17.
Gambardella L. and M. Dorigo. Ant-Q: A Reinforcement Learning approach to the traveling salesman problem. In: Prieditis, A., Russell, S. (eds.) Proceedings of Twelfth International Conference on Machine Learning, ML 1995, Tahoe City, CA, pp. 252–260. Morgan Kaufmann (1995)
18.
Dorigo, M., Gambardella, L.M.: Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans. Evol. Comput. 1(1), 53–66 (1997)CrossRef
19.
Dorigo, M., Maniezzo, V., Colorni, A.: Ant system: optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern. Part B 26(1), 1–13 (1996)CrossRef
20.
Peker, M., Sen, B., Kumru, P.Y.: An efficient solving of the traveling salesman problem: the ant colony system having parameters optimized by the Taguchi method. Turk. J. Electr. Eng. Comput. 21, 2015–2036 (2013)CrossRef
21.
Gunduz, M., Kiran, M.S., Ozceylan, E.: A hierarchic approach based on swarm intelligence to solve traveling salesman problem. Turk. J. Electr. Eng. Comput. Sci. (2014). doi:10.​3906/​elk-1210-147
22.
Masutti, T.A.S., de Castro, L.N.: A self-organizing neural network using ideas from the immune system to solve the traveling salesman problem. Inf. Sci. 179, 1454–1468 (2009)MathSciNetCrossRef
23.
Jun-man, K., Yi, Z.: Application of an improved ant colony optimization on generalized traveling salesman problem. Energy Proc. 17, 319–325 (2012)CrossRef
24.
Garcia-Martinez, C., Cordon, O., Herrera, F.: A taxonomy and an empirical analysis of multiple objective ant colony optimization algorithms for the bi-criteria TSP. Eur. J. Oper. Res. 180(1), 116–148 (2007)CrossRefMATH
25.
Tavares, J., Pereira, F.B.: Evolving strategies for updating pheromone trails: a case study with the TSP. In: Schaefer, R., Cotta, C., Kołodziej, J., Rudolph, G. (eds.) PPSN 2010. LNCS, vol. 6239, pp. 523–532. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-15871-1_​53
26.
Pour, H.D., Nosraty, M.: Solving the facility layout and location problem by ant-colony optimization-meta heuristic. Int. J. Prod. Res. 44, 5187–5196 (2006)CrossRefMATH
27.
Bouhafs, L., hajjam, A., Koukam, A.: A combination of simulated annealing and ant colony system for the capacitated location-routing problem. In: Gabrys, B., Howlett, R.J., Jain, L.C. (eds.) KES 2006. LNCS, vol. 4251, pp. 409–416. Springer, Heidelberg (2006). doi:10.​1007/​11892960_​50 CrossRef
28.
Altiparmak, F., Karaoglan, I.: A genetic ant colony optimization approach for concave cost transportation problems. In: IEEE Congress on Evolutionary Computation, CEC 2007, pp. 1685–1692 (2007)
29.
Metadata
Title
A DSS Based on Hybrid Ant Colony Optimization Algorithm for the TSP
Authors
Islem Kaabachi
Dorra Jriji
Saoussen Krichen
Copyright Year
2017
Book
Artificial Intelligence and Soft Computing

Print ISBN: 978-3-319-59059-2

Electronic ISBN: 978-3-319-59060-8

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-59060-8_58

Premium Partner

    Image Credits