×

A heuristic approach for cluster TSP. (English) Zbl 1436.90126

Castillo, Oscar (ed.) et al., Recent advances in intelligent information systems and applied mathematics. Selected papers based on the presentations at the 2nd international conference on information technology and applied mathematics, ICITAM 2019, Haldia Institute of Technology, Haldia, India, March 7–9, 2019. Cham: Springer. Stud. Comput. Intell. 863, 43-52 (2020).
Summary: 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.
For the entire collection see [Zbl 1436.68020].

MSC:

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahmed, Z.H.: An exact algorithm for the clustered traveling salesman problem. Opsearch 50(2), 215-228 (2013) · Zbl 1353.90124 · doi:10.1007/s12597-012-0107-0
[2] Ahmed, Z.H.: The ordered clustered travelling salesman problem: a hybrid genetic algorithm. Sci. World J. 2014, 13 (2014). Article ID 258207
[3] Pop, P.C., et al.: A novel two-level optimization approach for clustered vehicle routing problem. Comput. Ind. Eng. 115, 304-318 (2018) · doi:10.1016/j.cie.2017.11.018
[4] Chisman, J.A.: The clustered traveling salesman problem. Comput. Oper. Res. 2(2), 115-119 (1975) · doi:10.1016/0305-0548(75)90015-5
[5] Helsgaun, K.: Solving the clustered traveling salesman problem using the Lin-Kernighan-Helsgaun algorithm, May 2014 · Zbl 1327.90259
[6] Laporte, G., Palekar, U.: Some applications of the clustered travelling salesman problem. J. Oper. Res. Soc. 53(9), 972-976 (2002) · Zbl 1139.90425 · doi:10.1057/palgrave.jors.2601420
[7] Lokin, F.C.J.: Procedures for travelling salesman problems with additional constraints. Eur. J. Oper. Res. 3(2), 135-141 (1979) · Zbl 0396.90099 · doi:10.1016/0377-2217(79)90099-7
[8] Hertz, A., Gendreau, M., Laporte, G.: The traveling salesman problem with backhauls. Comput. Oper. Res. 23(5), 501-508 (1996) · Zbl 0847.90135 · doi:10.1016/0305-0548(95)00036-4
[9] Roy, A., Maity, S., Maiti, M.: An intelligent hybrid algorithm for 4-dimensional TSP. J. Ind. Inf. Integr. 5, 39-50 (2017)
[10] Mestria, M.: Heuristic methods using variable neighborhood random local search for the clustered traveling salesman problem. Revista Produo Online 14 (2014). https://doi.org/10.14488/1676-1901.v14i4.1721 · doi:10.14488/1676-1901.v14i4.1721
[11] Mestria, M.: New hybrid heuristic algorithm for the clustered traveling salesman problem. Comput. Ind. Eng. 116 (2017). https://doi.org/10.1016/j.cie.2017.12.018. · doi:10.1016/j.cie.2017.12.018
[12] Phuong, H.N., et al.: Solving the clustered traveling salesman problem with d-relaxed priority rule, October 2018
[13] Reinelt, G.: TSPLIBA traveling salesman problem library. ORSA J. Comput. 3, 376-384 (1991). ISSN 0899-1499 · Zbl 0775.90293 · doi:10.1287/ijoc.3.4.376
[14] Zhang, F., Zhang, Y.F., Nee, A.Y.C.: Using genetic algorithms in process planning for job shop machining. IEEE Trans. Evol. Comput. 1(4), 278-289 (1997) · doi:10.1109/4235.687888
[15] Zhang, · Zbl 1391.90540 · doi:10.1016/j.cor.2017.07.008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.