OPTIMIZING MULTIPLE TRAVELLING SALESMAN PROBLEM CONSIDERING THE ROAD CAPACITY
- 1 Hindustan Univertsity, India
Copyright: © 2020 Ranjana Ponraj and George Amalanathan. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
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
- Multiple Travelling Salesmen
- Road Capacity
- Shortest Path