PENYELESAIAN MULTI-DEPOT MULTIPLE TRAVELING SALESMAN PROBLEM MENGGUNAKAN K-MEANS DAN ANT COLONY OPTIMIZATION

Olief Ilmandira Ratu Farisi, Gulpi Qorik Oktagalu Pratamasunu

Abstract


Multi-Depot Multiple Traveling Salesman Problem (MmTSP) merupakan masalah pencarian rute terpendek oleh beberapa salesman yang berangkat dari kota yang berbeda-beda, disebut depot, dan kembali ke depotnya masing-masing dengan setiap kota harus dikunjungi tepat satu kali. ACO merupakan algoritma yang didesain untuk menyelesaikan TSP. Untuk menyelesaikan MmTSP, pada penelitian ini diusulkan metode K-Means ACO. K-Means digunakan untuk mencari pembagian kota yang optimal. Pembagian ini dilakukan sesuai dengan banyak depot pada permasalahan. Hasil setiap cluster ini menjadi kota-kota yang akan dikunjungi oleh setiap salesman. Setiap cluster hasil dari K-Means dicari rute terpendeknya menggunakan ACO. Gabungan hasil rute terpendek dari setiap cluster tersebut menjadi penyelesaian MmTSP. Hasil penelitian menunjukkan bahwa metode K-Means ACO dapat mencari rute yang mendekati optimal dengan waktu yang singkat.


References


M. Dorigo, V. Maniezzo, dan A. Colorni, “The Ant System: Optimization

by a Colony of Cooperating Agents,” IEEE Transactions on System,

Man, And Cybernetics-Part B: Cybernetics, Vol. 26, No. 1, hal.

-41, 1996.

S. Ghafurian dan N. Javadian, “An Ant Colony Algorithm for Solving

Fixed Destination Multi-Depot Multiple Traveling Salesman Problems,”

Applied Soft Computing, vol. 11, hal. 1256-1262, 2011.

P. Jinjie dan W. Dingwei, “An Ant Colony Optimization Algorithm for

Multiple Travelling Salesman Problem,” dalam Proc. ICICIC, 2006,

hal. 210-213.

I. Kara dan T. Bektas, “Integer Linear Programming Formulations of

Multiple Salesman Problems and Its Variations,” Europe Journal of

Operation Research, vol. 174, hal. 1449-1458, 2006.

K. Kim dan H. Ahn, “A recommender system using GA K-means clustering

in an online shopping market,” Expert Systems with Applications,

vol. 34, hal. 1200-1209, Februari 2008.

O.I.R. Farisi, “Penyelesaian Multi-Depot Multiple Traveling Salesman

Problem Menggunakan Hybrid Firefly Algorithm – Ant Colony Optimization,” tesis magister, Jurusan Matematika, Institut Teknologi Sepuluh

Nopember, Surabaya, Indonesia, 2015.




DOI: http://dx.doi.org/10.36564/njca.v1i2.12

Refbacks

  • There are currently no refbacks.


Copyright (c) 2017 Olief Ilmandira Ratu Farisi, Gulpi Qorik Oktagalu Pratamasunu


Creative Commons License
 
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

NJCA(Nusantara Journal of Computers and Its Applications)
Published by Computer Society of Nahdlatul Ulama, Indonesia.