چکیده (انگلیسی):

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.