To search, Click below search items. |
| All Published Papers Search Service |
|
|
|
Title |
An Exact Algorithm for the Single-Depot Multiple Travelling Salesman Problem |
|
Author |
Zakir Hussain Ahmed and Ibrahim Al-Dayel |
| Citation |
Vol. 20 No. 9 pp. 65-75 |
|
Abstract |
We consider the single-depot multiple travelling salesman Problem (MTSP) that is a generalization of the benchmark travelling salesman problem (TSP). The problem outlines that there are multiple salesmen m who should visit n cities so that each salesman must start from and end at single depot. The objective of the problem is to obtain the lowest total distance covered by all salesmen so that each city is visited only once by one salesman only. It is NP-hard, and it has numerous real-life applications. Though exact solutions can be found for small sized problem instances, yet there are certain circumstances where exact solutions are very essential. Hence, we propose to develop a lexisearch algorithm that uses path representation for a tour to find exact solution to the MTSP. The usefulness of the proposed exact algorithm is shown by comparing with an existing exact algorithm on various sized asymmetric instances from TSPLIB website with various number of salesmen. Experimental study shows the usefulness of the proposed algorithm. Finally, solutions to some symmetric TSPLIB instances are presented. |
|
Keywords |
Multiple travelling salesman problem; NP-hard; Optimal; Exact; Bound; Lexisearch algorithm. |
|
URL |
