Reduced Complexity Divide and Conquer Algorithm for Large Scale TSPs
Journal Title: International Journal of Advanced Computer Science & Applications - Year 2014, Vol 5, Issue 1
Abstract
The Traveling Salesman Problem (TSP) is the problem of finding the shortest path passing through all given cities while only passing by each city once and finishing at the same starting city. This problem has NP-hard complexity making it extremely impractical to get the most optimal path even for problems as small as 20 cities since the number of permutations becomes too high. Many heuristic methods have been devised to reach “good” solutions in reasonable time. In this paper, we present the idea of utilizing a spatial “geographical” Divide and Conquer technique in conjunction with heuristic TSP algorithms specifically the Nearest Neighbor 2-opt algorithm. We have found that the proposed algorithm has lower complexity than algorithms published in the literature. This comes at a lower accuracy expense of around 9%. It is our belief that the presented approach will be welcomed to the community especially for large problems where a reasonable solution could be reached in a fraction of the time.
Authors and Affiliations
Hoda Darwish, Ihab Talkhan
Keywords
Related Articles
- EP ID EP88339
- DOI 10.14569/IJACSA.2014.050110
- Views 82
- Downloads 0
Brain-Controlled for Changing Modular Robot Configuration by Employing Neurosky’s Headset
Currently, the Brain Computer Interfaces (BCI) system was designed mostly to be implemented for control purpose or navigation which are mostly being employed for mobile robot, manipulator robot and humanoid robot by usin...
Analysis of Coauthorship Network in Political Science using Centrality Measures
In recent era, networks of data are growing massively and forming a shape of complex structure. Data scientists try to analyze different complex networks and utilize these networks to understand the complex structure of...
Establishing Standard Rules for Choosing Best KPIs for an E-Commerce Business based on Google Analytics and Machine Learning Technique
The predictable values that indicate the performance of any company and determine that how well they are performing in order to achieve their objective is referred by the term called as “key performance indicators”. The...
The Impact of E-Media on Customer Purchase Intention
In this research paper, authors investigated the social media (e-discussion, websites, online chat, email etc) parameters that have effect over the customers buying decisions. The research focused on the development of...
Impact of Distributed Generation on the Reliability of Local Distribution System
With the growth of distributed generation (DG) and renewable energy resources the power sector is becoming more sophisticated, distributed generation technologies with its diverse impacts on power system is becoming attr...