Penyelesaian Colored Traveling Salesman Problem Menggunakan Algoritma Genetika Hill-Climbing

Abstract

Colored Traveling Salesman Problem (CTSP) adalah pengembangan dari MTSP dimana terdapat dua wilayah kerja yaitu wilayah umum yang dapat dikunjungi oleh setiap pekerja, dan wilayah pribadi yang berlaku hanya untuk pekerja yang ditugaskan di wilayah tersebut. Pada CTSP rute dari beberapa pekerja akan dibagi dengan mempertimbangkan wilayah umum dan wilayah pribadinya. Pada kajian ini, CTSP diselesaikan dengan Algoritma Genetika Hill-Climbing, yang merupakan penggabungan dari Algoritma Genetika dengan Algoritma Hill-Climbing dengan tujuan menghasilkan solusi yang lebih baik. Selanjutnya, model CTSP menggunakan Algoritma Genetika Hill-Climbing diimplementasikan pada kasus pengumpulan paket suatu perusahaan ekspedisi di Kota Bandung. Hasil dari kajian ini yaitu diperoleh rute terpendek untuk kasus pengumpulan paket suatu perusahaaan ekspedisi. Selain itu, dengan membandingkan Algoritma Genetika Hill-Climbing dengan Algoritma Genetika Klasik, diperoleh hasil bahwa Algoritma Genetika Hill-Climbing memberikan solusi dengan jarak yang lebih pendek meskipun membutuhkan waktu komputasi yang lebih lama.