A double-loop hybrid algorithm for the traveling salesman problem with arbitrary neighbourhoods

Zhao Yang, Ming-Qing Xiao, Ya-Wei Ge, De-Long Feng, Lei Zhang, Hai-Fang Song and Xi-Lang Tang

European Journal of Operational Research, 2018, vol. 265, issue 1, 65-80

Abstract: This paper addresses the traveling salesman problem with arbitrary neighbourhoods, which is an NP-hard problem in combinatorial optimization and is important in operations research and theoretical computer science. Existing methods based on neighbourhood predigestion and discretization are impractical in cases in which the neighbourhoods are arbitrary. In this paper, the neighbourhoods of the traveling salesman problem are generalized to arbitrarily connected regions in planar Euclidean space. A novel approach to solving this problem is proposed, including a boundary-based encoding scheme and a double-loop hybrid algorithm based on particle swarm optimization and genetic algorithm. In the hybrid algorithm, linear descending inertia weight particle swarm optimization is adopted to search continuous visiting positions in the outer loop, and the genetic algorithm is used to optimize the discrete visiting sequence in the inner loop. The boundary-based encoding scheme can reduce the search space significantly without degrading the solution quality, and the hybrid algorithm can find a high-quality solution in a reasonable time. The computational results on both small and large instances demonstrate that the proposed approach can guarantee a high-quality solution in a reasonable time, compared with three other state-of-the-art algorithms: iterative algorithm, branch-and-bound algorithm, and upper and lower bound algorithm. Moreover, the proposed approach works efficiently in a real-world application that cannot be solved by existing algorithms.

Keywords: Traveling salesman problem; Arbitrary neighbourhoods; Boundary-based encoding scheme; Hybrid algorithm; Close-enough (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221717306513
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:265:y:2018:i:1:p:65-80

DOI: 10.1016/j.ejor.2017.07.024

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().