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

Olief Ilmandira Ratu Farisi (Jurusan Teknik Informatika, Sekolah Tinggi Teknologi Nurul Jadid)
Gulpi Qorik Oktagalu Pratamasunu (Jurusan Teknik Informatika, Sekolah Tinggi Teknologi Nurul Jadid)

Nusantara Journal of Computers and its Applications
Vol 1, No 2 (2016): Desember 2016

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.