An Improvement to the 2-Opt Heuristic Algorithm for Approximation of Optimal TSP Tour
The travelling salesman problem (TSP) is perhaps the most researched problem in the field of Computer Science and Operations. It is a known NP-hard problem and has significant practical applications in a variety of areas, such as logistics, planning, and scheduling. Route optimisation not only impro...
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-06-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/13/12/7339 |
| _version_ | 1797596159415418880 |
|---|---|
| author | Fakhar Uddin Naveed Riaz Abdul Manan Imran Mahmood Oh-Young Song Arif Jamal Malik Aaqif Afzaal Abbasi |
| author_facet | Fakhar Uddin Naveed Riaz Abdul Manan Imran Mahmood Oh-Young Song Arif Jamal Malik Aaqif Afzaal Abbasi |
| author_sort | Fakhar Uddin |
| collection | DOAJ |
| description | The travelling salesman problem (TSP) is perhaps the most researched problem in the field of Computer Science and Operations. It is a known NP-hard problem and has significant practical applications in a variety of areas, such as logistics, planning, and scheduling. Route optimisation not only improves the overall profitability of a logistic centre but also reduces greenhouse gas emissions by minimising the distance travelled. In this article, we propose a simple and improved heuristic algorithm named 2-Opt++, which solves symmetric TSP problems using an enhanced 2-Opt local search technique, to generate better results. As with 2-Opt, our proposed method can also be applied to the Vehicle Routing Problem (VRP), with minor modifications. We have compared our technique with six existing algorithms, namely ruin and recreate, nearest neighbour, genetic algorithm, simulated annealing, Tabu search, and ant colony optimisation. Furthermore, to allow for the complexity of larger TSP instances, we have used a graph compression/candidate list technique that helps in reducing the computational complexity and time. The comprehensive empirical evaluation carried out for this research work shows the efficacy of the 2-Opt++ algorithm as it outperforms the other well-known algorithms in terms of the error margin, execution time, and time of convergence. |
| first_indexed | 2024-03-11T02:47:35Z |
| format | Article |
| id | doaj.art-4862e445687440a081b43ee608f5ba0a |
| institution | Directory Open Access Journal |
| issn | 2076-3417 |
| language | English |
| last_indexed | 2024-03-11T02:47:35Z |
| publishDate | 2023-06-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj.art-4862e445687440a081b43ee608f5ba0a2023-11-18T09:12:26ZengMDPI AGApplied Sciences2076-34172023-06-011312733910.3390/app13127339An Improvement to the 2-Opt Heuristic Algorithm for Approximation of Optimal TSP TourFakhar Uddin0Naveed Riaz1Abdul Manan2Imran Mahmood3Oh-Young Song4Arif Jamal Malik5Aaqif Afzaal Abbasi6School of Electrical Engineering and Computer Science (SEECS), National University of Sciences and Technology (NUST), Islamabad 44000, PakistanSchool of Electrical Engineering and Computer Science (SEECS), National University of Sciences and Technology (NUST), Islamabad 44000, PakistanDepartment of Mathematics, University of Gujrat, Gujrat 50700, PakistanSchool of Electrical Engineering and Computer Science (SEECS), National University of Sciences and Technology (NUST), Islamabad 44000, PakistanSoftware Department, Sejong University, Seoul 05006, Republic of KoreaDepartment of Software Engineering, Foundation University Islamabad, Islamabad 46000, PakistanDepartment of Software Engineering, Foundation University Islamabad, Islamabad 46000, PakistanThe travelling salesman problem (TSP) is perhaps the most researched problem in the field of Computer Science and Operations. It is a known NP-hard problem and has significant practical applications in a variety of areas, such as logistics, planning, and scheduling. Route optimisation not only improves the overall profitability of a logistic centre but also reduces greenhouse gas emissions by minimising the distance travelled. In this article, we propose a simple and improved heuristic algorithm named 2-Opt++, which solves symmetric TSP problems using an enhanced 2-Opt local search technique, to generate better results. As with 2-Opt, our proposed method can also be applied to the Vehicle Routing Problem (VRP), with minor modifications. We have compared our technique with six existing algorithms, namely ruin and recreate, nearest neighbour, genetic algorithm, simulated annealing, Tabu search, and ant colony optimisation. Furthermore, to allow for the complexity of larger TSP instances, we have used a graph compression/candidate list technique that helps in reducing the computational complexity and time. The comprehensive empirical evaluation carried out for this research work shows the efficacy of the 2-Opt++ algorithm as it outperforms the other well-known algorithms in terms of the error margin, execution time, and time of convergence.https://www.mdpi.com/2076-3417/13/12/7339travelling salesman problemcombinatorial optimisationVRProute optimisationheuristic algorithmsTSPLIB |
| spellingShingle | Fakhar Uddin Naveed Riaz Abdul Manan Imran Mahmood Oh-Young Song Arif Jamal Malik Aaqif Afzaal Abbasi An Improvement to the 2-Opt Heuristic Algorithm for Approximation of Optimal TSP Tour Applied Sciences travelling salesman problem combinatorial optimisation VRP route optimisation heuristic algorithms TSPLIB |
| title | An Improvement to the 2-Opt Heuristic Algorithm for Approximation of Optimal TSP Tour |
| title_full | An Improvement to the 2-Opt Heuristic Algorithm for Approximation of Optimal TSP Tour |
| title_fullStr | An Improvement to the 2-Opt Heuristic Algorithm for Approximation of Optimal TSP Tour |
| title_full_unstemmed | An Improvement to the 2-Opt Heuristic Algorithm for Approximation of Optimal TSP Tour |
| title_short | An Improvement to the 2-Opt Heuristic Algorithm for Approximation of Optimal TSP Tour |
| title_sort | improvement to the 2 opt heuristic algorithm for approximation of optimal tsp tour |
| topic | travelling salesman problem combinatorial optimisation VRP route optimisation heuristic algorithms TSPLIB |
| url | https://www.mdpi.com/2076-3417/13/12/7339 |
| work_keys_str_mv | AT fakharuddin animprovementtothe2optheuristicalgorithmforapproximationofoptimaltsptour AT naveedriaz animprovementtothe2optheuristicalgorithmforapproximationofoptimaltsptour AT abdulmanan animprovementtothe2optheuristicalgorithmforapproximationofoptimaltsptour AT imranmahmood animprovementtothe2optheuristicalgorithmforapproximationofoptimaltsptour AT ohyoungsong animprovementtothe2optheuristicalgorithmforapproximationofoptimaltsptour AT arifjamalmalik animprovementtothe2optheuristicalgorithmforapproximationofoptimaltsptour AT aaqifafzaalabbasi animprovementtothe2optheuristicalgorithmforapproximationofoptimaltsptour AT fakharuddin improvementtothe2optheuristicalgorithmforapproximationofoptimaltsptour AT naveedriaz improvementtothe2optheuristicalgorithmforapproximationofoptimaltsptour AT abdulmanan improvementtothe2optheuristicalgorithmforapproximationofoptimaltsptour AT imranmahmood improvementtothe2optheuristicalgorithmforapproximationofoptimaltsptour AT ohyoungsong improvementtothe2optheuristicalgorithmforapproximationofoptimaltsptour AT arifjamalmalik improvementtothe2optheuristicalgorithmforapproximationofoptimaltsptour AT aaqifafzaalabbasi improvementtothe2optheuristicalgorithmforapproximationofoptimaltsptour |