Solving open travelling salesman subset-tour problem through a hybrid genetic algorithm

Abstract: In open travelling salesman subset-tour problem (OTSSP), the salesman needs to traverse a set of k (≤n) out of n cities and after visiting the last city, the salesman does not necessarily return to the central depot. The goal is to minimize the overall traversal distance of covering k cities. The OTSSP model comprises two types of problems such as subset selection and permutation of the cities. Firstly, the problem of selection takes place as the salesman’s tours do not contain all the cities. On the other hand, the next problem is about to determine the optimal sequence of the cities from the selected subset of cities. To deal with this problem efficiently, a hybrid nearest neighbor technique based crossover-free Genetic algorithm (GA) with complex mutation strategies is proposed. To the best of the author’s knowledge, this is the first hybrid GA for the OTSSP. As there are no existing studies on OTSSP yet, benchmark instances are not available for OTSSP. For computational experiments, a set of test instances is created by using TSPLIB. The extensive computational results show that the proposed algorithm is having great potential in achieving better results for the OTSSP. Our proposed GA being the first evolutionary-based algorithm that will help as the baseline for future research on OTSSP.

How to cite this paper

 Singamsetty, P., Thenepalle, J & Uruturu, B. (2021). Solving open travelling salesman subset-tour problem through a hybrid genetic algorithm.Journal of Project Management, 6(4), 209-222.

Refrences

Ausiello, G., Bonifaci, V., Leonardi, S., Marchetti-Spaccamela, A., & Gonzalez, T. F. (2018). Prize Collecting Traveling Salesman and Related Problems.
Bahaabadi, M.R., Mohaymany, A.S., & Babaei, M. (2012). An Efficient crossover operator for travelling salesman prob-lem. International Journal of Optimization in Civil Engineering 2(4), 607–619.
Balas, E. (1989). The prize collecting traveling salesman problem. Networks, 19(6), 621-636.
Chieng, H. H., & Wahid, N. (2014). A performance comparison of genetic algorithm’s mutation operators in n-cities open loop travelling salesman problem. In Recent Advances on Soft Computing and Data Mining (pp. 89-97). Springer, Cham.
Gensch, D. H. (1978). An industrial application of the traveling salesman's subtour problem. AIIE Transactions, 10(4), 362-370.
Giardini, G., & Kalmar-Nagy, T. (2011). Genetic algorithm for combinatorial path planning: the subtour problem. Mathe-matical Problems in Engineering, 2011.
Goldenberg, D. E. (1989). Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Newyork.
Hussain, A., Muhammad, Y. S., Nauman Sajid, M., Hussain, I., Mohamd Shoukry, A., & Gani, S. (2017). Genetic algo-rithm for traveling salesman problem with modified cycle crossover operator. Computational intelligence and neuro-science, 2017.
Ibaraki, T. (1973). Algorithms for obtaining shortest paths visiting specified nodes. Siam Review, 15(2), 309-317.
Laporte, G., Mercure, H., & Norbert, Y. (1984). Optimal tour planning with specified nodes. RAIRO-Operations Research-Recherche Opérationnelle, 18(3), 203-210.
Liu, C., & Kroll, A. (2016). Performance impact of mutation operators of a subpopulation-based genetic algorithm for multi-robot task allocation problems. SpringerPlus, 5(1), 1361.
Maredia, A., & Pepper, R. (2010). History, Analysis, and Implementation of Traveling Salesman Problem (TSP) and Re-lated Problems. Department of Computer and Mathematical Sciences, University of Houston-Downtown.
Matai, R., Singh, S. P., & Mittal, M. L. (2010). Traveling salesman problem: an overview of applications, formulations, and solution approaches. Traveling salesman problem, theory and applications, 1.
Mittenthal, J., & Noon, C. E. (1992). An insert/delete heuristic for the travelling salesman subset-tour problem with one additional constraint. Journal of the Operational Research Society, 43(3), 277-283.
Pandiri, V., & Singh, A. (2020). Two multi-start heuristics for the k-traveling salesman problem. OPSEARCH, 57(4), 1164-1204.
Saksena, J. P., & Kumar, S. (1966). The routing problem with “K” specified nodes. Operations Research, 14(5), 909-913.
Stetsyuk, P. I. (2016). Problem statements for k-node shortest path and k-node shortest cycle in a complete graph. Cyber-netics and Systems Analysis, 52(1), 71-75.
Venkatesh, P., Srivastava, G., & Singh, A. (2018). A general variable neighborhood search algorithm for the k-traveling salesman problem. Procedia computer science, 143, 189-196.
Verweij, B., & Aardal, K. (2003). The merchant subtour problem. Mathematical programming, 94(2-3), 295-322.
Westerlund, A., Göthe-Lundgren, M., & Larsson, T. (2006). A stabilized column generation scheme for the traveling salesman subtour problem. Discrete Applied Mathematics, 154(15), 2212-2238.

Journals

JPM Volumes

Keywords

Authors

Countries

Journal of Project Management

Solving open travelling salesman subset-tour problem through a hybrid genetic algorithm Pages 209-222 Download PDF

Add Reviews