research-article

A hybrid heuristic approach for solving the generalized traveling salesman problem

Authors:

Petrica C. Pop,

Serban IordacheAuthors Info & Claims

GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

Pages 481 - 488

https://doi.org/10.1145/2001576.2001643

Published: 12 July 2011 Publication History

Abstract

The generalized traveling salesman problem (GTSP) is an NP-hard problem that extends the classical traveling salesman problem by partitioning the nodes into clusters and looking for a minimum Hamiltonian tour visiting exactly one node from each cluster. In this paper, we combine the consultant-guided search technique with a local-global approach in order to solve efficiently the generalized traveling salesman problem. We use candidate lists in order to reduce the search space and we introduce efficient variants of 2-opt and 3-opt local search in order to improve the solutions. The resulting algorithm is applied to Euclidean GTSP instances derived from the TSPLIB library. The experimental results show that our algorithm is able to compete with the best existing algorithms in terms of solution quality and running time.

References

[1]

Bontoux, B., Artigues, C. and Feillet, D. A Memetic Algorithm with a large neighborhood crossover operator for the Generalized Traveling Salesman Problem. Computers & Operations Research, 37 (11), 2010, 1844--1852.

Digital Library

[2]

Dorigo, M. and Stützle, T.: Ant Colony Optimization. MIT Press, Cambridge, 2004.

Digital Library

[3]

Fischetti, M. A Branch-and-Cut Algorithm for the Symmetric Generalized Travelling Salesman Problem. Operations Research, 45 (3), 1997, 378--394.

Digital Library

[4]

Gutin, G. and Karapetyan, D. A memetic algorithm for the generalized traveling salesman problem. Natural Computing, vol. 9, 2010, 47--60.

Digital Library

[5]

Hu, B. and Raidl, G. Effective neighborhood structures for the generalized traveling salesman problem. In: Proc. of Evolutionary Computation in Combinatorial Optimisation - EvoCOP 2008, LNCS, Vol. 4972, Naples, Italy, 2008, 36--47.

Digital Library

[6]

Hutter, F., Hoos, H.H., Leyton-Brown, K. and Stützle, T. ParamILS: An Automatic Algorithm Configuration Framework. Journal of Artificial Intelligence Research (JAIR), vol. 36, October 2009, 267--306.

Digital Library

[7]

Iordache, S. Consultant-Guided Search - A New Metaheuristic for Combinatorial Optimization Problems. In: GECCO 2010: Proceedings of the 12th Genetic and Evolutionary Computation Conference. ACM Press, 2010.

Digital Library

[8]

Iordache, S. Consultant-Guided Search Algorithms with Local Search for the Traveling Salesman Problem. In: PPSN XI - International Conference Parallel Problem Solving from Nature. LNCS 6239, Krakow, Poland, Springer, 2010, 81--90.

Digital Library

[9]

Iordache, S. Consultant-Guided Search Algorithms for the Quadratic Assignment. In: Hybrid Metaheuristics - 7th International Workshop, HM 2010. LNCS 6373, Vienna, Austria. Springer, 2010, 148--159.

Digital Library

[10]

Johnson, D.S. and McGeoch, L. Experimental Analysis of Heuristics for STSP. In: Gutin, G., Punnen, A. (eds) The Traveling Salesman Problem and its Variations. Kluwer, Dordrecht, 2002.

[11]

Pop, P.C. The generalized minimum spanning tree problem. Twente University Press, The Netherlands, 2002.

[12]

Reinelt, G. TSPLIB - A Traveling Salesman Problem Library, ORSA Journal on Computing, vol. 3, no. 4, 1991, 376--384.

[13]

Silberholz, J. and Golden, B. The Generalized Traveling Salesman Problem: a new Genetic Algorithm approach. Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies, 2007, 165--181.

[14]

Snyder, L.V. and Daskin, M.S. A random-key genetic algorithm for the generalized traveling salesman problem. European Journal of Operational Research 174, 2006, 38--53.

[15]

Tasgetiren, M.F., Suganthan, P.N. and Pan, Q.-K. A discrete particle swarm optimization algorithm for the generalized traveling salesman problem. GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation, 2007, 158--167.

Digital Library

Cited By

Cosma OPop PCosma L(2024)A novel memetic algorithm for solving the generalized traveling salesman problemLogic Journal of the IGPL10.1093/jigpal/jzae01932:4(576-588)Online publication date: 24-Mar-2024
https://doi.org/10.1093/jigpal/jzae019
Cosma OPop PCosma L(2021)An Effective Hybrid Genetic Algorithm for Solving the Generalized Traveling Salesman ProblemHybrid Artificial Intelligent Systems10.1007/978-3-030-86271-8_10(113-123)Online publication date: 15-Sep-2021
https://doi.org/10.1007/978-3-030-86271-8_10
Pylyavskyy YKheiri AAhmed L(2020)A Reinforcement Learning Hyper-heuristic for the optimisation of Flight Connections2020 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC48606.2020.9185803(1-8)Online publication date: Jul-2020
https://doi.org/10.1109/CEC48606.2020.9185803
Show More Cited By

Index Terms

A hybrid heuristic approach for solving the generalized traveling salesman problem
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction

Recommendations

A discrete particle swarm optimization algorithm for the generalized traveling salesman problem
GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

Dividing the set of nodes into clusters in the well-known traveling salesman problem results in the generalized traveling salesman problem which seeking a tour with minimum cost passing through only a single node from each cluster. In this paper, a ...
The Generalized Covering Salesman Problem

Given a graph G = (N, E), the covering salesman problem (CSP) is to identify the minimum length tour “covering” all the nodes. More specifically, it seeks the minimum-length tour visiting a subset of the nodes in N such that each node i not on the tour ...
A multistart heuristic for the equality generalized traveling salesman problem

We study the equality generalized traveling salesman problem (E-GTSP), which is a variant of the well-known traveling salesman problem. We are given an undirected graph G = (V,E), with set of vertices V and set of edges E, each with an associated cost. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

July 2011

2140 pages

ISBN:9781450305570

DOI:10.1145/2001576

Editor:
Natalio Krasnogor
University of Nottingham, UK
,
General Chair:
Pier Luca Lanzi
Politecnico di Milano, Italy

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '11

Sponsor:

SIGEVO

GECCO '11: Genetic and Evolutionary Computation Conference

July 12 - 16, 2011

Dublin, Ireland

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
315
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)0

Reflects downloads up to 29 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cosma OPop PCosma L(2024)A novel memetic algorithm for solving the generalized traveling salesman problemLogic Journal of the IGPL10.1093/jigpal/jzae01932:4(576-588)Online publication date: 24-Mar-2024
https://doi.org/10.1093/jigpal/jzae019
Cosma OPop PCosma L(2021)An Effective Hybrid Genetic Algorithm for Solving the Generalized Traveling Salesman ProblemHybrid Artificial Intelligent Systems10.1007/978-3-030-86271-8_10(113-123)Online publication date: 15-Sep-2021
https://doi.org/10.1007/978-3-030-86271-8_10
Pylyavskyy YKheiri AAhmed L(2020)A Reinforcement Learning Hyper-heuristic for the optimisation of Flight Connections2020 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC48606.2020.9185803(1-8)Online publication date: Jul-2020
https://doi.org/10.1109/CEC48606.2020.9185803
Derya TDinler EKeçeci B(2020)Selective generalized travelling salesman problemMathematical and Computer Modelling of Dynamical Systems10.1080/13873954.2019.1705496(1-39)Online publication date: 3-Jan-2020
https://doi.org/10.1080/13873954.2019.1705496
Sabry ABenhra JBacha A(2018)ASIF Approach to Solve the Green Traveling Salesman ProblemInternational Journal of Operations Research and Information Systems10.4018/IJORIS.20180101059:1(81-95)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.4018/IJORIS.2018010105
Pop PMatei OPintea CTakadama K(2018)A two-level diploid genetic based algorithm for solving the family traveling salesman problemProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205545(340-346)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205545
Jafarzadeh HMoradinasab NElyasi M(2017)An Enhanced Genetic Algorithm for the Generalized Traveling Salesman ProblemEngineering, Technology & Applied Science Research10.48084/etasr.15707:6(2260-2265)Online publication date: 18-Dec-2017
https://doi.org/10.48084/etasr.1570
Ueda YEbara HNakayama KIida S(2017)Parallel Consultant-Guided Search with CrossoverThe Review of Socionetwork Strategies10.1007/s12626-017-0016-z11:2(185-200)Online publication date: 20-Nov-2017
https://doi.org/10.1007/s12626-017-0016-z
Pop POliviu MSabo C(2017)A Hybrid Diploid Genetic Based Algorithm for Solving the Generalized Traveling Salesman ProblemHybrid Artificial Intelligent Systems10.1007/978-3-319-59650-1_13(149-160)Online publication date: 2-Jun-2017
https://doi.org/10.1007/978-3-319-59650-1_13
Pourhassan MNeumann FEsparcia-Alcázar A(2015)On the Impact of Local Search Operators and Variable Neighbourhood Search for the Generalized Travelling Salesperson ProblemProceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation10.1145/2739480.2754656(465-472)Online publication date: 11-Jul-2015
https://dl.acm.org/doi/10.1145/2739480.2754656
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents