Skip to Main content Skip to Navigation
Conference papers

Probe Machine Based Consecutive Route Filtering Approach to Symmetric Travelling Salesman Problem

Abstract : The travelling salesman problem (TSP) is one of the NPC combinatorial optimization problems and still now it remains as an interesting and challenging problem in the field of combinatorial optimization. In this paper, we propose a consecutive route filtering approach to solving the symmetric TSP with the help of probe concept such that the worse routes are filtered out step by step by using a rigorous predesigned step proportion. In this way, it is important to set up a reasonable value of the step proportion which is needed in each step during the filtering process. Actually, our proposed algorithm is implemented on the set of symmetric TSP benchmarks with both small and large numbers of cities from the TSPLIB dataset. It is demonstrated by the experimental results that our proposed algorithm can obtain the best results in some cases and generally get the approximation results close to the best known solutions.
Document type :
Conference papers
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/hal-02118813
Contributor : Hal Ifip <>
Submitted on : Friday, May 3, 2019 - 1:25:22 PM
Last modification on : Friday, May 3, 2019 - 3:34:15 PM

File

474230_1_En_41_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Md. Rahman, Jinwen Ma. Probe Machine Based Consecutive Route Filtering Approach to Symmetric Travelling Salesman Problem. 2nd International Conference on Intelligence Science (ICIS), Nov 2018, Beijing, China. pp.378-387, ⟨10.1007/978-3-030-01313-4_41⟩. ⟨hal-02118813⟩

Share

Metrics

Record views

45

Files downloads

6