Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Computer Based Stylometric Analysis of Texts in Polish Language Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

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

verfasst von : Islem Kaabachi, Dorra Jriji, Saoussen Krichen

Erschienen in: Artificial Intelligence and Soft Computing

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Convolutional Neural Networks for Time Series Classification
Nächstes Kapitel Comparing Strategies for Search Space Boundaries Violation in PSO
Literatur
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.
Metadaten
Titel
A DSS Based on Hybrid Ant Colony Optimization Algorithm for the TSP
verfasst von
Islem Kaabachi
Dorra Jriji
Saoussen Krichen
Copyright-Jahr
2017
Buch
Artificial Intelligence and Soft Computing

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

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

Copyright-Jahr: 2017

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

Premium Partner

    Bildnachweise