Ahmed Zakir Hussain
Department of Computer Science, Al Imam Mohammad Ibn Saud Islamic University (IMSIU), P.O. Box 5701, Riyadh 11432, Saudi Arabia.
ScientificWorldJournal. 2014 Feb 19;2014:258207. doi: 10.1155/2014/258207. eCollection 2014.
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.
有序聚类旅行商问题是常规旅行商问题的一种变体，其中网络的一组顶点（起始顶点除外）被划分为一些预先指定的聚类。目标是找到成本最小的哈密顿回路，其中任何聚类的顶点都被连续访问，并且聚类按预先指定的顺序被访问。该问题是NP难问题，它出现在实际的运输和排序问题中。本文开发了一种混合遗传算法，该算法使用顺序构造交叉、2-opt搜索和局部搜索来获得该问题的启发式解。针对两种现有算法，在一些不同规模的非对称和对称TSPLIB实例上检验了该算法的效率。计算结果表明，所提出的算法在解质量和计算时间方面非常有效。最后，我们给出了一些更多对称TSPLIB实例的解。
