Please use this identifier to cite or link to this item: http://hdl.handle.net/10603/13431
Title: A new approach to solve multiple traveling salesman problems
Researcher: Nallusamy R
Guide(s): Duraiswamy, K.
Keywords: Multiple Traveling Salesman Problems(mTSPs), Artificial Intelligence, AI-heuristics, k-means clustering algorithm
Upload Date: 28-Nov-2013
University: Anna University
Completed Date: 
Abstract: Shortest Path (SP) problem can be used to solve many real world oriented problems such as routing in telecommunication networks, vehicle routing in logistics management and pickup and delivery systems. The SP based multiple traveling salesman problems (mTSPs) are complex and Nondeterministic Polynomial-time hard (NP-hard) combinatorial optimization problems. The nature inspired algorithms such as Artificial Intelligence (AI) heuristics are suitable to such type of problems. This research focuses on solving the mTSPs by using hybrid AI-heuristics techniques. The existing algorithms for Traveling Salesman Problem (TSP) have some limitations. Most of the researchers have solved simple Traveling Salesman Problems (TSPs) by using various approximation algorithms. This research proposes a two/three phase hybrid AI-heuristics for city allocation to salespersons and finding a suitable sequence of different cities through which a salesperson can travel. The main aim is to solve the large sized mTSPs by converting them into simple TSPs using hybrid AI-heuristics. Initially, two stage AI-heuristics is applied and then, three stage AI-heuristics is applied to solve the problem. In the first stage, a well-known k-means clustering algorithm is used to allot different cities to a particular salesperson, where k is the number of clusters or salespersons. The results have proved that the simple clustering like k-means clustering proves to be effective as it is able to group the nodes as clusters in an intelligent manner with reduced convergence time. It is known from the results of mTSP that the three phase hybrid GA provides suitable solutions for large scale problems and hybrid ACO provides suitable solutions for small sized problems. The results indicate that the hybrid nature inspired algorithms are able to solve the mTSPs quite efficiently. Consequently, with the practical application, they can significantly improve the operational efficiency of an organization in its application domain. newline newline newline
Pagination: xiii, 114
URI: http://hdl.handle.net/10603/13431
Appears in Departments:Faculty of Information and Communication Engineering

Files in This Item:
File Description SizeFormat 
01_title.pdfAttached File49.58 kBAdobe PDFView/Open
02_certificates.pdf1.13 MBAdobe PDFView/Open
03_abstract.pdf14.02 kBAdobe PDFView/Open
04_acknowledgement.pdf14.65 kBAdobe PDFView/Open
05_contents.pdf35.62 kBAdobe PDFView/Open
06_chapter 1.pdf107.08 kBAdobe PDFView/Open
07_chapter 2.pdf977.99 kBAdobe PDFView/Open
08_chapter 3.pdf328.66 kBAdobe PDFView/Open
09_chapter 4.pdf14.62 kBAdobe PDFView/Open
10_references.pdf27.61 kBAdobe PDFView/Open
11_publications.pdf16.68 kBAdobe PDFView/Open
12_vitae.pdf13.15 kBAdobe PDFView/Open


Items in Shodhganga are protected by copyright, with all rights reserved, unless otherwise indicated.