Penyelesaian Multiple Travelling Salesman Problem dengan Improved K-Means Clustering dan Genetic Algorithm

Abstract

Multiple Travelling Salesman Problem (MTSP) bertujuan meminimalkan total jarak tempuh dengan tetap mempertimbangkan keseimbangan beban kerja antar-salesman. Penelitian ini menyelesaikan MTSP melalui pendekatan cluster-first route-second menggunakan algoritme Improved k-Means dan Genetic Algorithm (GA). Improved k-Means digunakan untuk membentuk klaster kota yang seimbang, sementara GA dengan berbagai operator genetik mencari rute near-optimal pada setiap klaster. Hasil penelitian menunjukkan Improved k-Means berhasil mendistribusikan beban kerja secara proporsional. GA terbukti menghasilkan rute konvergen, menunjukkan tingkat akurasi yang tergolong near-optimal terhadap solusi eksak (MILP). Analisis variasi salesman menunjukkan bahwa penambahan jumlah salesman cenderung meningkatkan total jarak global, tetapi pengaruhnya terhadap makespan dan keseimbangan beban kerja tidak selalu linear. Selain itu, peningkatan parameter GA tidak selalu signifikan mengurangi jarak tetapi tetap menambah waktu komputasi. Dengan demikian, kombinasi kedua algoritme ini terbukti efektif dalam menyelesaikan MTSP.

The Multiple Travelling Salesman Problem (MTSP) aims to minimize the total distance traveled while considering the balance of workload between salesman. This study solves the MTSP through a cluster-first route-second approach using the Improved k-Means algorithm and Genetic Algorithm (GA). Improved k-Means is used to form balanced city clusters, while GA with various genetic operators searches for near-optimal routes in each cluster. The results show that Improved k-Means successfully distributes the workload proportionally. GA is proven to produce convergent routes, showing a near-optimal level of accuracy compared to the exact solution (MILP). Analysis of salesman variation shows that increasing the number of salesman tends to increase the total global distance, while its effect on makespan and workload balance is not always linear. Furthermore, increasing the GA parameters did not always significantly reduce the distance but still increased the computation time. Thus, the combination of these two algorithms proved to be effective in solving the MTSP.