Probe Machine Based Consecutive Route Filtering Approach to Symmetric Travelling Salesman Problem - Intelligence Science II Third IFIP TC 12 International Conference, ICIS 2018 Access content directly
Conference Papers Year : 2018

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

Md. Azizur Rahman
  • Function : Author
  • PersonId : 1046625
Jinwen Ma
  • Function : Author
  • PersonId : 1046618

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.
Fichier principal
Vignette du fichier
474230_1_En_41_Chapter.pdf (413.19 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-02118813 , version 1 (03-05-2019)

Licence

Attribution

Identifiers

Cite

Md. Azizur 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⟩
26 View
65 Download

Altmetric

Share

Gmail Facebook X LinkedIn More