International Journal of Science and Research (IJSR)

International Journal of Science and Research (IJSR)
Since Year 2012 | Open Access | Fully Refereed | Peer Reviewed

ISSN: 2319-7064




Downloads: 121 | Weekly Hits: ⮙1 | Monthly Hits: ⮙1

Research Paper | Industrial Engineering | Vietnam | Volume 9 Issue 5, May 2020


Variants of 2-opt Approach for the Generalized Traveling Salesman Problem

Luu Van Thanh


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.


Keywords: Combinatorial optimization, generalized traveling salesman problem, heuristics, local search


Edition: Volume 9 Issue 5, May 2020,


Pages: 1554 - 1565

Variants of 2-opt Approach for the Generalized Traveling Salesman Problem


How to Cite this Article?

Luu Van Thanh, "Variants of 2-opt Approach for the Generalized Traveling Salesman Problem", International Journal of Science and Research (IJSR), https://www.ijsr.net/get_abstract.php?paper_id=SR20524133242, Volume 9 Issue 5, May 2020, 1554 - 1565, #ijsrnet

How to Share this Article?

Enter Your Email Address


Click below to Watch Video Lecture of Above Article

Share this Video Lecture


Similar Articles with Keyword 'optimization'

Downloads: 29

Research Paper, Industrial Engineering, Bangladesh, Volume 10 Issue 2, February 2021

Pages: 987 - 992

A Green Vehicle Routing Problem with Simultaneous Delivery and Pickup with Time Windows for Cost Optimization

Mst. Anjuman Ara

Share this Article

Downloads: 90

Research Paper, Industrial Engineering, India, Volume 4 Issue 9, September 2015

Pages: 1681 - 1684

Intelligent Approach for Optimizing Resources in Supply Chain System using RFID

N. Nandakumar | M. Arularasu

Share this Article


Top