A discrete state transition algorithm for generalized traveling salesman problem

DOI10.1007/978-3-319-08377-3_15MaRDI QIDQ2942467zbMATH OpenOpenAlexFDO

Authors Xiaolin Tang, Xiaojun Zhou, Chunhua Yang, Weihua Gui

Publication date 11 September 2015

Published in Springer Proceedings in Mathematics & Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.7607

zbMATH Keywords

discrete state transition algorithmdouble R-probabilitygeneralized traveling salesman problemK-circle

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Abstract: Generalized traveling salesman problem (GTSP) is an extension of classical traveling salesman problem (TSP), which is a combinatorial optimization problem and an NP-hard problem. In this paper, an efficient discrete state transition algorithm (DSTA) for GTSP is proposed, where a new local search operator named extit{K-circle}, directed by neighborhood information in space, has been introduced to DSTA to shrink search space and strengthen search ability. A novel robust update mechanism, restore in probability and risk in probability (Double R-Probability), is used in our work to escape from local minima. The proposed algorithm is tested on a set of GTSP instances. Compared with other heuristics, experimental results have demonstrated the effectiveness and strong adaptability of DSTA and also show that DSTA has better search ability than its competitors.

Recommendations

• Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem
• An efficient hybrid ant colony system for the Generalized Traveling Salesman Problem
• A memetic algorithm for the generalized traveling salesman problem
• A memetic algorithm with a large neighborhood crossover operator for the generalized traveling salesman problem
• The Generalized Traveling Salesman Problem: A New Genetic Algorithm Approach

Cites work

• A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem
• A memetic algorithm for the generalized traveling salesman problem
• A memetic algorithm with a large neighborhood crossover operator for the generalized traveling salesman problem
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• scientific article; zbMATH DE number 1933055 (Why is no real title available?)
• Lin-Kernighan heuristic adaptations for the generalized traveling salesman problem
• State transition algorithm
• The symmetric generalized traveling salesman polytope

Cited in

(1)

• An ensemble of discrete differential evolution algorithms for solving the generalized traveling salesman problem

Describes a project that uses

Uses Software

• GTSP Instances Library

This page was built for publication: A discrete state transition algorithm for generalized traveling salesman problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2942467)