A heuristic approach for cluster TSP

Apurba Manna; Samir Maity; Arindam Roy

doi:10.1007/978-3-030-34152-7_4

A heuristic approach for cluster TSP

Apurba Manna, Samir Maity, Arindam Roy^*

^*Kontaktforfatter

Publikation: Bidrag til bog/antologi/rapport/konference proceeding › Konferenceartikel i proceeding › Forskning › peer review

Abstract

This investigation took an attempt to solve the cluster traveling salesman problem (CTSP) by the heuristic approach. In this problem, nodes are clustered with given a set of vertices (nodes). Given the set of vertices is divided into a prespecified number of clusters. The size of each cluster is also pre-specified. The main aim is to find the least cost Hamiltonian tour based on the given vertices. Here vertices of each cluster visited contiguously, and the clusters are visited in a specific order. Standard GA is used to find a Hamiltonian path for each cluster. The performance of the algorithm has been examined against two existing algorithms for some symmetric TSPLIB instances of various sizes. The computational results show the proposed algorithm works well among the studied metaheuristics regarding the best result and computational time.

Originalsprog	Engelsk
Titel	Recent Advances in Intelligent Information Systems and Applied Mathematics, ICITAM 2019
Redaktører	Oscar Castillo, Dipak Kumar Jana, Arif Ahmed, Debasis Giri
Antal sider	10
Forlag	Springer VS
Publikationsdato	2020
Sider	43-52
ISBN (Trykt)	9783030341510
DOI	https://doi.org/10.1007/978-3-030-34152-7_4
Status	Udgivet - 2020
Begivenhed	2nd International Conference on Information Technology and Applied Mathematics, ICITAM 2019 - Haldia, Indien Varighed: 7 mar. 2019 → 9 mar. 2019

Konference

Konference	2nd International Conference on Information Technology and Applied Mathematics, ICITAM 2019
Land/Område	Indien
By	Haldia
Periode	07/03/2019 → 09/03/2019

Navn	Studies in Computational Intelligence
Vol/bind	863 SCI
ISSN	1860-949X

Bibliografisk note

Publisher Copyright:
© Springer Nature Switzerland AG 2020.

Adgang til dokumentet

10.1007/978-3-030-34152-7_4

AUB Link

Søg efter materialet i Aalborg Universitetsbiblioteks søgemaskine

Andre filer og links

Link to publication in Scopus

Citationsformater

@inproceedings{cdf17c1969b14db6b89629bceebbd0ea,

title = "A heuristic approach for cluster TSP",

abstract = "This investigation took an attempt to solve the cluster traveling salesman problem (CTSP) by the heuristic approach. In this problem, nodes are clustered with given a set of vertices (nodes). Given the set of vertices is divided into a prespecified number of clusters. The size of each cluster is also pre-specified. The main aim is to find the least cost Hamiltonian tour based on the given vertices. Here vertices of each cluster visited contiguously, and the clusters are visited in a specific order. Standard GA is used to find a Hamiltonian path for each cluster. The performance of the algorithm has been examined against two existing algorithms for some symmetric TSPLIB instances of various sizes. The computational results show the proposed algorithm works well among the studied metaheuristics regarding the best result and computational time.",

keywords = "Cluster TSP, GA, Heuristic",

author = "Apurba Manna and Samir Maity and Arindam Roy",

note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2020.; 2nd International Conference on Information Technology and Applied Mathematics, ICITAM 2019 ; Conference date: 07-03-2019 Through 09-03-2019",

year = "2020",

doi = "10.1007/978-3-030-34152-7_4",

language = "English",

isbn = "9783030341510",

series = "Studies in Computational Intelligence",

publisher = "Springer VS",

pages = "43--52",

editor = "Oscar Castillo and Jana, {Dipak Kumar} and Arif Ahmed and Debasis Giri",

booktitle = "Recent Advances in Intelligent Information Systems and Applied Mathematics, ICITAM 2019",

}

Manna, A, Maity, S & Roy, A 2020, A heuristic approach for cluster TSP. i O Castillo, DK Jana, A Ahmed & D Giri (red), Recent Advances in Intelligent Information Systems and Applied Mathematics, ICITAM 2019. Springer VS, Studies in Computational Intelligence, bind 863 SCI, s. 43-52, 2nd International Conference on Information Technology and Applied Mathematics, ICITAM 2019, Haldia, Indien, 07/03/2019. https://doi.org/10.1007/978-3-030-34152-7_4

A heuristic approach for cluster TSP. / Manna, Apurba; Maity, Samir; Roy, Arindam.
Recent Advances in Intelligent Information Systems and Applied Mathematics, ICITAM 2019. red. / Oscar Castillo; Dipak Kumar Jana; Arif Ahmed; Debasis Giri. Springer VS, 2020. s. 43-52 (Studies in Computational Intelligence, Bind 863 SCI).

Publikation: Bidrag til bog/antologi/rapport/konference proceeding › Konferenceartikel i proceeding › Forskning › peer review

TY - GEN

T1 - A heuristic approach for cluster TSP

AU - Manna, Apurba

AU - Maity, Samir

AU - Roy, Arindam

N1 - Publisher Copyright: © Springer Nature Switzerland AG 2020.

PY - 2020

Y1 - 2020

N2 - This investigation took an attempt to solve the cluster traveling salesman problem (CTSP) by the heuristic approach. In this problem, nodes are clustered with given a set of vertices (nodes). Given the set of vertices is divided into a prespecified number of clusters. The size of each cluster is also pre-specified. The main aim is to find the least cost Hamiltonian tour based on the given vertices. Here vertices of each cluster visited contiguously, and the clusters are visited in a specific order. Standard GA is used to find a Hamiltonian path for each cluster. The performance of the algorithm has been examined against two existing algorithms for some symmetric TSPLIB instances of various sizes. The computational results show the proposed algorithm works well among the studied metaheuristics regarding the best result and computational time.

AB - This investigation took an attempt to solve the cluster traveling salesman problem (CTSP) by the heuristic approach. In this problem, nodes are clustered with given a set of vertices (nodes). Given the set of vertices is divided into a prespecified number of clusters. The size of each cluster is also pre-specified. The main aim is to find the least cost Hamiltonian tour based on the given vertices. Here vertices of each cluster visited contiguously, and the clusters are visited in a specific order. Standard GA is used to find a Hamiltonian path for each cluster. The performance of the algorithm has been examined against two existing algorithms for some symmetric TSPLIB instances of various sizes. The computational results show the proposed algorithm works well among the studied metaheuristics regarding the best result and computational time.

KW - Cluster TSP

KW - GA

KW - Heuristic

UR - http://www.scopus.com/inward/record.url?scp=85080946947&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-34152-7_4

DO - 10.1007/978-3-030-34152-7_4

M3 - Article in proceeding

AN - SCOPUS:85080946947

SN - 9783030341510

T3 - Studies in Computational Intelligence

SP - 43

EP - 52

BT - Recent Advances in Intelligent Information Systems and Applied Mathematics, ICITAM 2019

A2 - Castillo, Oscar

A2 - Jana, Dipak Kumar

A2 - Ahmed, Arif

A2 - Giri, Debasis

PB - Springer VS

T2 - 2nd International Conference on Information Technology and Applied Mathematics, ICITAM 2019

Y2 - 7 March 2019 through 9 March 2019

ER -

A heuristic approach for cluster TSP

Abstract

Konference

Bibliografisk note

Adgang til dokumentet

AUB Link

Andre filer og links

Fingeraftryk

Citationsformater