Probe Machine Based Consecutive Route Filtering Approach to Symmetric Travelling Salesman Problem - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2018

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

Md. Azizur Rahman
  • Fonction : Auteur
  • PersonId : 1046625
Jinwen Ma
  • Fonction : Auteur
  • PersonId : 1046618

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Licence

Paternité

Identifiants

Citer

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 Consultations
65 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More