A Comparative Study of Genetic Algorithms, Simulated Annealing and Tabu Search for Non-Fixed Destination Multi-Depot Multiple Traveling Salesmen Problem

Freydoun Adbesh, Kamran Kardel

Research output: Contribution to conferencePresentation

Abstract

The non-fixed destination multi depot multiple traveling salesmen problem (MmTSP) in which more than one salesmen depart from several starting cities (depots) and having returned to the one of starting city (depot) that the number of cities in each depot remain the same at the end as it was in the beginning, form tours so that each city is visited with exactly one salesman and the tour lengths stay within certain limits. This problem is of a great complexity and few investigations have been done on it before. In this paper we apply three meta-heuristics algorithms as genetic algorithms (GAs), tabu search (TS) and simulated annealing (SA) for this problem and compare the theoretical properties and computational performance of these algorithms with the optimal answers obtained by solving the problems by Lingo 8. Computational analysis shows that the SA and TS have results very close to optimal solution in medium size and large/very large-sized problems respectively.
Original languageAmerican English
DOIs
StatePublished - Dec 2010
EventInternational Conference on Optimization: Techniques and Applications (ICOTA) - Shanghai, China
Duration: Dec 1 2010 → …

Conference

ConferenceInternational Conference on Optimization: Techniques and Applications (ICOTA)
Period12/1/10 → …

Keywords

  • Comparative study
  • Genetic algorithms
  • Multi-depot
  • Multiple traveling salesmen problem
  • Non-fixed destination
  • Simulated annealing
  • Tabu search

DC Disciplines

  • Manufacturing

Fingerprint

Dive into the research topics of 'A Comparative Study of Genetic Algorithms, Simulated Annealing and Tabu Search for Non-Fixed Destination Multi-Depot Multiple Traveling Salesmen Problem'. Together they form a unique fingerprint.

Cite this