Cargando…

The Ordered Clustered Travelling Salesman Problem: A Hybrid Genetic Algorithm

The ordered clustered travelling salesman problem is a variation of the usual travelling salesman problem in which a set of vertices (except the starting vertex) of the network is divided into some prespecified clusters. The objective is to find the least cost Hamiltonian tour in which vertices of a...

Descripción completa

Detalles Bibliográficos
Autor principal: Ahmed, Zakir Hussain
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Hindawi Publishing Corporation 2014
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3950363/
https://www.ncbi.nlm.nih.gov/pubmed/24701148
http://dx.doi.org/10.1155/2014/258207
_version_ 1782306971223851008
author Ahmed, Zakir Hussain
author_facet Ahmed, Zakir Hussain
author_sort Ahmed, Zakir Hussain
collection PubMed
description The ordered clustered travelling salesman problem is a variation of the usual travelling salesman problem in which a set of vertices (except the starting vertex) of the network is divided into some prespecified clusters. The objective is to find the least cost Hamiltonian tour in which vertices of any cluster are visited contiguously and the clusters are visited in the prespecified order. The problem is NP-hard, and it arises in practical transportation and sequencing problems. This paper develops a hybrid genetic algorithm using sequential constructive crossover, 2-opt search, and a local search for obtaining heuristic solution to the problem. The efficiency of the algorithm has been examined against two existing algorithms for some asymmetric and symmetric TSPLIB instances of various sizes. The computational results show that the proposed algorithm is very effective in terms of solution quality and computational time. Finally, we present solution to some more symmetric TSPLIB instances.
format Online
Article
Text
id pubmed-3950363
institution National Center for Biotechnology Information
language English
publishDate 2014
publisher Hindawi Publishing Corporation
record_format MEDLINE/PubMed
spelling pubmed-39503632014-04-03 The Ordered Clustered Travelling Salesman Problem: A Hybrid Genetic Algorithm Ahmed, Zakir Hussain ScientificWorldJournal Research Article The ordered clustered travelling salesman problem is a variation of the usual travelling salesman problem in which a set of vertices (except the starting vertex) of the network is divided into some prespecified clusters. The objective is to find the least cost Hamiltonian tour in which vertices of any cluster are visited contiguously and the clusters are visited in the prespecified order. The problem is NP-hard, and it arises in practical transportation and sequencing problems. This paper develops a hybrid genetic algorithm using sequential constructive crossover, 2-opt search, and a local search for obtaining heuristic solution to the problem. The efficiency of the algorithm has been examined against two existing algorithms for some asymmetric and symmetric TSPLIB instances of various sizes. The computational results show that the proposed algorithm is very effective in terms of solution quality and computational time. Finally, we present solution to some more symmetric TSPLIB instances. Hindawi Publishing Corporation 2014-02-19 /pmc/articles/PMC3950363/ /pubmed/24701148 http://dx.doi.org/10.1155/2014/258207 Text en Copyright © 2014 Zakir Hussain Ahmed. https://creativecommons.org/licenses/by/3.0/ This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
spellingShingle Research Article
Ahmed, Zakir Hussain
The Ordered Clustered Travelling Salesman Problem: A Hybrid Genetic Algorithm
title The Ordered Clustered Travelling Salesman Problem: A Hybrid Genetic Algorithm
title_full The Ordered Clustered Travelling Salesman Problem: A Hybrid Genetic Algorithm
title_fullStr The Ordered Clustered Travelling Salesman Problem: A Hybrid Genetic Algorithm
title_full_unstemmed The Ordered Clustered Travelling Salesman Problem: A Hybrid Genetic Algorithm
title_short The Ordered Clustered Travelling Salesman Problem: A Hybrid Genetic Algorithm
title_sort ordered clustered travelling salesman problem: a hybrid genetic algorithm
topic Research Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3950363/
https://www.ncbi.nlm.nih.gov/pubmed/24701148
http://dx.doi.org/10.1155/2014/258207
work_keys_str_mv AT ahmedzakirhussain theorderedclusteredtravellingsalesmanproblemahybridgeneticalgorithm
AT ahmedzakirhussain orderedclusteredtravellingsalesmanproblemahybridgeneticalgorithm