A memetic algorithm for the generalized traveling salesman problem

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

Full description

Saved in:
Bibliographic Details
Published in:Natural computing 2010-03, Vol.9 (1), p.47-60
Main Authors: Gutin, Gregory, Karapetyan, Daniel
Format: Article
Language:English
Subjects:
Algorithms
Artificial Intelligence
Complex Systems
Computer Science
Evolutionary Biology
Genetic algorithms
Processor Architectures
Theory of Computation
Traveling salesman problem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c347t-ab3ffb33d8b3a9474a97d7e8658ace47552f88ad2745b771ea6c15da0b223a863
cites cdi_FETCH-LOGICAL-c347t-ab3ffb33d8b3a9474a97d7e8658ace47552f88ad2745b771ea6c15da0b223a863
container_end_page 60
container_issue 1
container_start_page 47
container_title Natural computing
container_volume 9
creator Gutin, Gregory
Karapetyan, Daniel
description 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.
doi_str_mv 10.1007/s11047-009-9111-6
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_743604108</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>1987318191</sourcerecordid><originalsourceid>FETCH-LOGICAL-c347t-ab3ffb33d8b3a9474a97d7e8658ace47552f88ad2745b771ea6c15da0b223a863</originalsourceid><addsrcrecordid>eNp1kE1LxDAQhoMouK7-AG_Bi6dovpMe18UvWPCi55C2026XtF2TrqC_3pYKguBp5vC87wwPQpeM3jBKzW1ijEpDKM1Ixhgj-ggtmDKcZCbTx9OuDTGW2VN0ltKOUs6UYgt0t8IttDA0Bfah7mMzbFtc9REPW8A1dBB9aL6gxEP0HxCarsbJB0it7_A-9nmA9hydVD4kuPiZS_T2cP-6fiKbl8fn9WpDCiHNQHwuqioXorS58Jk00memNGC1sr4AaZTilbW-5Eaq3BgGXhdMlZ7mnAtvtVii67l3vPt-gDS4tkkFhOA76A_JGSk0lYzakbz6Q-76Q-zG5xyn0mqpMzFCbIaK2KcUoXL72LQ-fjpG3eTUzU7d6NRNTt30Ap8zaWS7GuJv8f-hbyAnePA</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>204864693</pqid></control><display><type>article</type><title>A memetic algorithm for the generalized traveling salesman problem</title><source>Springer Link</source><creator>Gutin, Gregory ; Karapetyan, Daniel</creator><creatorcontrib>Gutin, Gregory ; Karapetyan, Daniel</creatorcontrib><description>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.</description><identifier>ISSN: 1567-7818</identifier><identifier>EISSN: 1572-9796</identifier><identifier>DOI: 10.1007/s11047-009-9111-6</identifier><language>eng</language><publisher>Dordrecht: Springer Netherlands</publisher><subject>Algorithms ; Artificial Intelligence ; Complex Systems ; Computer Science ; Evolutionary Biology ; Genetic algorithms ; Processor Architectures ; Theory of Computation ; Traveling salesman problem</subject><ispartof>Natural computing, 2010-03, Vol.9 (1), p.47-60</ispartof><rights>Springer Science+Business Media B.V. 2009</rights><rights>Springer Science+Business Media B.V. 2010</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c347t-ab3ffb33d8b3a9474a97d7e8658ace47552f88ad2745b771ea6c15da0b223a863</citedby><cites>FETCH-LOGICAL-c347t-ab3ffb33d8b3a9474a97d7e8658ace47552f88ad2745b771ea6c15da0b223a863</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,777,781,27905,27906</link.rule.ids></links><search><creatorcontrib>Gutin, Gregory</creatorcontrib><creatorcontrib>Karapetyan, Daniel</creatorcontrib><title>A memetic algorithm for the generalized traveling salesman problem</title><title>Natural computing</title><addtitle>Nat Comput</addtitle><description>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.</description><subject>Algorithms</subject><subject>Artificial Intelligence</subject><subject>Complex Systems</subject><subject>Computer Science</subject><subject>Evolutionary Biology</subject><subject>Genetic algorithms</subject><subject>Processor Architectures</subject><subject>Theory of Computation</subject><subject>Traveling salesman problem</subject><issn>1567-7818</issn><issn>1572-9796</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2010</creationdate><recordtype>article</recordtype><recordid>eNp1kE1LxDAQhoMouK7-AG_Bi6dovpMe18UvWPCi55C2026XtF2TrqC_3pYKguBp5vC87wwPQpeM3jBKzW1ijEpDKM1Ixhgj-ggtmDKcZCbTx9OuDTGW2VN0ltKOUs6UYgt0t8IttDA0Bfah7mMzbFtc9REPW8A1dBB9aL6gxEP0HxCarsbJB0it7_A-9nmA9hydVD4kuPiZS_T2cP-6fiKbl8fn9WpDCiHNQHwuqioXorS58Jk00memNGC1sr4AaZTilbW-5Eaq3BgGXhdMlZ7mnAtvtVii67l3vPt-gDS4tkkFhOA76A_JGSk0lYzakbz6Q-76Q-zG5xyn0mqpMzFCbIaK2KcUoXL72LQ-fjpG3eTUzU7d6NRNTt30Ap8zaWS7GuJv8f-hbyAnePA</recordid><startdate>20100301</startdate><enddate>20100301</enddate><creator>Gutin, Gregory</creator><creator>Karapetyan, Daniel</creator><general>Springer Netherlands</general><general>Springer Nature B.V</general><scope>AAYXX</scope><scope>CITATION</scope><scope>3V.</scope><scope>7SC</scope><scope>7XB</scope><scope>88I</scope><scope>8AL</scope><scope>8AO</scope><scope>8FD</scope><scope>8FE</scope><scope>8FG</scope><scope>8FK</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>GNUQQ</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K7-</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><scope>M0N</scope><scope>M2P</scope><scope>P5Z</scope><scope>P62</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PRINS</scope><scope>Q9U</scope></search><sort><creationdate>20100301</creationdate><title>A memetic algorithm for the generalized traveling salesman problem</title><author>Gutin, Gregory ; Karapetyan, Daniel</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c347t-ab3ffb33d8b3a9474a97d7e8658ace47552f88ad2745b771ea6c15da0b223a863</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2010</creationdate><topic>Algorithms</topic><topic>Artificial Intelligence</topic><topic>Complex Systems</topic><topic>Computer Science</topic><topic>Evolutionary Biology</topic><topic>Genetic algorithms</topic><topic>Processor Architectures</topic><topic>Theory of Computation</topic><topic>Traveling salesman problem</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Gutin, Gregory</creatorcontrib><creatorcontrib>Karapetyan, Daniel</creatorcontrib><collection>CrossRef</collection><collection>ProQuest Central (Corporate)</collection><collection>Computer and Information Systems Abstracts</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>Science Database (Alumni Edition)</collection><collection>Computing Database (Alumni Edition)</collection><collection>ProQuest Pharma Collection</collection><collection>Technology Research Database</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies &amp; Aerospace Database‎ (1962 - current)</collection><collection>ProQuest Central Essentials</collection><collection>ProQuest Central</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central</collection><collection>ProQuest Central Student</collection><collection>SciTech Premium Collection (Proquest) (PQ_SDU_P3)</collection><collection>ProQuest Computer Science Collection</collection><collection>Computer Science Database</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><collection>Computing Database</collection><collection>Science Database</collection><collection>Advanced Technologies &amp; Aerospace Database</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ProQuest Central China</collection><collection>ProQuest Central Basic</collection><jtitle>Natural computing</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Gutin, Gregory</au><au>Karapetyan, Daniel</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>A memetic algorithm for the generalized traveling salesman problem</atitle><jtitle>Natural computing</jtitle><stitle>Nat Comput</stitle><date>2010-03-01</date><risdate>2010</risdate><volume>9</volume><issue>1</issue><spage>47</spage><epage>60</epage><pages>47-60</pages><issn>1567-7818</issn><eissn>1572-9796</eissn><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.</abstract><cop>Dordrecht</cop><pub>Springer Netherlands</pub><doi>10.1007/s11047-009-9111-6</doi><tpages>14</tpages></addata></record>
fulltext fulltext
identifier ISSN: 1567-7818
ispartof Natural computing, 2010-03, Vol.9 (1), p.47-60
issn 1567-7818
1572-9796
language eng
recordid cdi_proquest_miscellaneous_743604108
source Springer Link
subjects Algorithms
Artificial Intelligence
Complex Systems
Computer Science
Evolutionary Biology
Genetic algorithms
Processor Architectures
Theory of Computation
Traveling salesman problem
title A memetic algorithm for the generalized traveling salesman problem
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-20T13%3A19%3A46IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=A%20memetic%20algorithm%20for%20the%20generalized%20traveling%20salesman%20problem&rft.jtitle=Natural%20computing&rft.au=Gutin,%20Gregory&rft.date=2010-03-01&rft.volume=9&rft.issue=1&rft.spage=47&rft.epage=60&rft.pages=47-60&rft.issn=1567-7818&rft.eissn=1572-9796&rft_id=info:doi/10.1007/s11047-009-9111-6&rft_dat=%3Cproquest_cross%3E1987318191%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c347t-ab3ffb33d8b3a9474a97d7e8658ace47552f88ad2745b771ea6c15da0b223a863%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=204864693&rft_id=info:pmid/&rfr_iscdi=true