The Multiple Travelling Salesman Problems (MTSP) can be used in a wide range of discrete optimization problems. As the solution to this prob lem has wide applicability in many practical fields , this NP Hard problem highly raises the need for an efficient solution. The problem is determining a se t of routes for the salesmen that jointly visit a set of given cities which are facing difficulty becaus e 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 i s to optimize the vehicle utilization and minimize the time of travel by salesman based on the road capaci ty. 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) al gorithms to obtain the shortest path. The PSPMS algorithm runs in parallel for each salesman. The s olutions to the problem are known to possess an exponential time complexity. From the result we obs erve that PSPMS is one of the best approximate algorithms used to solve MTSP.