nach oben

Natural Computing

Erschienen in:

01.03.2010

A memetic algorithm for the generalized traveling salesman problem

verfasst von: Gregory Gutin, Daniel Karapetyan

Erschienen in: Natural Computing | Ausgabe 1/2010

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The generalized traveling salesman problem (GTSP) is an extension of the well-known traveling salesman problem. In GTSP, we are given a partition of cities into groups and we are required to find a minimum length tour that includes exactly one city from each group. The recent studies on this subject consider different variations of a memetic algorithm approach to the GTSP. The aim of this paper is to present a new memetic algorithm for GTSP with a powerful local search procedure. The experiments show that the proposed algorithm clearly outperforms all of the known heuristics with respect to both solution quality and running time. While the other memetic algorithms were designed only for the symmetric GTSP, our algorithm can solve both symmetric and asymmetric instances.

Vorheriger Artikel Discrete Particle Swarm Optimization for the minimum labelling Steiner tree problem

Nächster Artikel Hybrid Functional Petri Nets as MP systems

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

We assume that s _i+M = s _i for the solution (s ₁ s ₂ ... s _M) and for any 1 ≤ i ≤ M.

Bang-Jensen J, Gutin G (2000) Digraphs: theory, algorithms and applications. Springer-Verlag, London, 754 pp

Ben-Arieh D, Gutin G, Penn M, Yeo A, Zverovitch A (2003) Transformations of generalized ATSP into ATSP. Oper Res Lett 31:357–365MATHCrossRefMathSciNet

Davis L (1985) Applying adaptive algorithms to epistatic domains. In: Proceeding of the international joint conference on artificial intelligence, pp 162–164

Fischetti M, Salazar-González JJ, Toth P (1997) A branch-and-cut algorithm for the symmetric generalized traveling salesman problem. Oper Res 45 (3):378–394MATHCrossRefMathSciNet

Fischetti M, Salazar-González JJ, Toth P (2002) The generalized traveling salesman and orientering problems. In: Gutin G , Punnen A (eds) The traveling salesman problem and its variations. Kluwer, Dordrecht

Gutin G (2003) Traveling salesman problems. In: Gross J, Yellen J (eds) Handbook of Graph theory. CRC Press, Boca Raton

Gutin G, Punnen AP (eds) (2002) Traveling salesman problem and its variations. Kluwer, DordrechtMATH

Gutin G, Yeo A (2003) Assignment problem based algorithms are impractical for the generalized TSP. Ausralas J Combinatorics 27:149–154MATHMathSciNet

Hart WE, Krasnogor N, Smith JE (eds) (2004) Recent advances in memetic algorithms. Studies in fuzzyness and soft computing, vol 166. Springer, Berlin

Johnson DS, McGeoch L (2002) Experimental analysis of heuristics for STSP. In: Gutin G, Punnen A (eds) The traveling salesman problem and its variations. Kluwer, Dordrecht

Johnson DS, Gutin G, McGeoch L, Yeo A, Zhang X, Zverovitch A (2002) Experimental analysis of heuristics for ATSP. In: Gutin G, Punnen A (eds) The traveling salesman problem and its variations. Kluwer, Dordrecht

Krasnogor N, Smith J (2005) A tutorial for competent memetic algorithms: model, taxonomy and design issues. IEEE Trans Evol Comput 9:474–488CrossRef

Laporte G, Asef-Vaziri A, Sriskandarajah C (1996) Some applications of the generalized travelling salesman problem. J Oper Res Soc 47(12):1461–1467MATH

Lawler EL, Lenstra JK, Rinooy Kan AHG, Shmoys DB (eds) (1985) Travelling salesman problem: a guided tour of combinatorial optimization. Wiley, Chichester

Moscato P (1999) Memetic algorithms: a short introduction. In: Corne D, Glover F, Dorigo M (eds) New ideas in optimization. McGraw-Hill, New York

Reinelt G (1991) TSPLIB—a traveling salesman problem library. ORSA J Comput 3:376–384. http://www.crpc.rice.edu/softlib/tsplib/

Silberholz J, Golden B (2007) The generalized traveling salesman problem: a new genetic algorithm approach. In: Baker et al. (eds) Extending the horizons: advances in computing, optimization, and decision technologies, vol 37. Springer, Heidelberg, pp 165–181

Snyder LV, Daskin MS (2006) A random-key genetic algorithm for the generalized traveling salesman problem. Eur J Oper Res 174:38–53MATHCrossRefMathSciNet

Tasgetiren MF, Suganthan PN, Pan Q-K (2007) A discrete particle swarm optimization algorithm for the generalized traveling salesman problem. In: GECCO ’07: proceedings of the 9th annual conference on genetic and evolutionary computation, pp 158–167

Tsai H-K, Yang J-M, Tsai Y-F, Kao C-Y (2004) An evolutionary algorithms for large traveling salesman problems. IEEE Trans SMC B 34:1718–1729

Titel: A memetic algorithm for the generalized traveling salesman problem
verfasst von: Gregory Gutin
Daniel Karapetyan
Publikationsdatum: 01.03.2010
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 1/2010
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-009-9111-6

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2010

When to use bit-wise neutrality

Special issue on Nature Inspired Cooperative Strategies for Optimisation (NICSO)

Evolutionary swarm cooperative optimization in dynamic environments

Honey Bees Mating Optimization algorithm for large scale vehicle routing problems

Self-assembly of discrete self-similar fractals

Experimental validation and optimization of signal dependent operation in whiplash PCR