Research Article Open Access

OPTIMIZING MULTIPLE TRAVELLING SALESMAN PROBLEM CONSIDERING THE ROAD CAPACITY

Ranjana Ponraj1 and George Amalanathan1
  • 1 Hindustan Univertsity, India
Journal of Computer Science
Volume 10 No. 4, 2014, 680-688

DOI: https://doi.org/10.3844/jcssp.2014.680.688

Submitted On: 7 October 2013 Published On: 23 December 2013

How to Cite: Ponraj, R. & Amalanathan, G. (2014). OPTIMIZING MULTIPLE TRAVELLING SALESMAN PROBLEM CONSIDERING THE ROAD CAPACITY. Journal of Computer Science, 10(4), 680-688. https://doi.org/10.3844/jcssp.2014.680.688

Abstract

The Multiple Travelling Salesman Problems (MTSP) can be used in a wide range of discrete optimization problems. As the solution to this problem has wide applicability in many practical fields, this NP Hard problem highly raises the need for an efficient solution. The problem is determining a set of routes for the salesmen that jointly visit a set of given cities which are facing difficulty because of road congestion. Selection of proper route is based on the road capacity, which is the deciding factor in the opt vehicle usage. The objective of the study is to optimize the vehicle utilization and minimize the time of travel by salesman based on the road capacity. The solution to this problem is achieved in 3 steps; the first step is by assigning addresses to cities by Ad-assignment algorithm. The second step is by assigning cities and vehicles to salesman by Sl-assignment algorithm. The third step is by using Parallel Shortest Path Multiple Salesman (PSPMS) algorithms to obtain the shortest path. The PSPMS algorithm runs in parallel for each salesman. The solutions to the problem are known to possess an exponential time complexity. From the result we observe that PSPMS is one of the best approximate algorithms used to solve MTSP.

  • 938 Views
  • 2,207 Downloads
  • 3 Citations

Download

Keywords

  • Multiple Travelling Salesmen
  • Road Capacity
  • Shortest Path