Resolving Travelling Salesman Problem Using Modified Clustering Technique

Abstract

Abstract

Travelling Salesman Problem (TSP) is a quotidian stumbling block in the field of Computer Science and operation research designed to seek out the shortest pathway amid the given targets viz. cities where each target is considered only once. Many solutions to this setback like Ant Colony Optimization. Brute-Force approach, Genetic Algorithm, Fruit Fly Optimization etc. are available in literature. The main objective of these solutions is to minimize the time complexity and to search an optimized path that covers the entire region; however the urge of finding shortest path in minimum time still persists. This research work is an attempt to solve the above problem using clustering technique. Generally, for N cities the number of permutations conventionally considered are (N-1); for the proposed research work the permutations contemplated are reduced by the factor m. The results exhibit that the proposed method can effectively improve time complexity and search ability for achieving higher accuracy and optimal results. TSP discerns its application in X-Ray crystallography, the order-picking problem in warehouses, drilling of Printed Circuit Boards (PCB), mission planning problem etc. so an exigency for an optimum solution is requisite.

Keywords: Brute-Force, lexicographic ordering, non-deterministic polynomial (NP) hard problem

Cite this Article

Hardik Dhingra, Gagan Deep Dhand, Rashmi Chawla, Shailende Gupta, Samarth Mittal. Resolving Travelling Salesman Problem Using Modified Clustering Technique. Research & Reviews: Discrete Mathematical Structures. 2019; 6(1):
22–31p.