Variants of 2-opt Approach for the Generalized Traveling Salesman Problem
Journal: International Journal of Science and Research (IJSR) (Vol.9, No. 5)Publication Date: 2020-05-05
Authors : Luu Van Thanh;
Page : 1554-1565
Keywords : Combinatorial optimization; generalized traveling salesman problem; heuristics; local search;
Abstract
Generalized Traveling Salesman Problem (GTSP) is a well-known NP-hard problem. In a symmetric GTSP, the salesman must pass through a number of predefined subsets of customers, determining the order in which the subsets should be visited, and visiting exactly one customer in each subset while minimizing the sum of traveling costs of a completed undirected graph. This paper introduces a metaheuristic approach for solving this problem. The proposed algorithm is composed of two stages: (1) the constructive algorithm using the nearest neighbor heuristics (NN) ; and (2) the local improved algorithms consisting of combination of the well-known 2-opt search (2-opt classic), the adaptation of 2-opt with the NN (2-opt-NN), and the shortest path approach using Dijkstra’s algorithm (2-opt-SP). The computational results on thirty-six TSPLIB problems with up to 442 nodes are presented wherein the problems up to 300 nodes have been solved with computational time shorter than previous results cited in the literature.
Other Latest Articles
- Learner Support Services as a Factor of Students Performance in Open and Distance Learning Centres at Institute of Adult Education
- Perceptions and Barriers to Contraceptive Access among the Adolescents
- A Study of Academic Resilience among Students of Secondary and Higher Secondary Schools
- Perceived Benefits and Challenges regarding Online Teaching Strategies among the Students in Relation to COVID-19 Pandemic: A Review
- Early Experience with Minimally Invasive Oncologic Surgery at a Peripheral Cancer Centre in North East India
Last modified: 2021-06-28 17:06:43