Implementation of clustered ant colony optimization in solving fixed destination multiple depot multiple traveling salesman problem

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Citations (Scopus)

Abstract

The multiple-depot multi-traveling salesman problem is a generalization of the traveling salesman problem, in which the objective is to determine the shortest route for m salesmen with n depots to reach every other node exactly once before returning to the initial depot. In this paper, we will perform clustering on any nodes traversed, allowing MMTSP to be simplified to an MTSP (multiple traveling salesman problem) or a TSP for each cluster. The clustering algorithms that will be used are agglomerative clustering and K-means clustering, while ant colony optimization is used when determining the shortest route for each cluster. The solution of MMTSP is calculated from the sum of the shortest routes for these clusters. We will use data samples from TSPLIB for our implementation. The results of the simulation show that agglomerative clustering ACO algorithms take longer to compute than K-means clustering ACO and standalone ACO algorithms; on the other hand, they yield superior results than the other two. These results will also be compared with results obtained from prior research.

Original languageEnglish
Title of host publicationProceedings - 2017 1st International Conference on Informatics and Computational Sciences, ICICoS 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages137-140
Number of pages4
ISBN (Electronic)9781538609033
DOIs
Publication statusPublished - 1 Oct 2017
Event1st International Conference on Informatics and Computational Sciences, ICICoS 2017 - Semarang, Indonesia
Duration: 15 Nov 201716 Nov 2017

Publication series

NameProceedings - 2017 1st International Conference on Informatics and Computational Sciences, ICICoS 2017
Volume2018-January

Conference

Conference1st International Conference on Informatics and Computational Sciences, ICICoS 2017
Country/TerritoryIndonesia
CitySemarang
Period15/11/1716/11/17

Keywords

  • MMTSP
  • ant-colony optimization
  • clustering

Fingerprint

Dive into the research topics of 'Implementation of clustered ant colony optimization in solving fixed destination multiple depot multiple traveling salesman problem'. Together they form a unique fingerprint.

Cite this