Penyelesaian Colored Traveling Salesman Problem Menggunakan Algoritma Genetika Hill-Climbing

Abstract

The Colored Traveling Salesman Problem (CTSP) is an extension of the Multiple Traveling Salesman Problem (mTSP) involving two types of working areas: a common area that can be visited by any worker, and private areas that are accessible only to the workers assigned to those specific regions. In CTSP, the routes for several workers are divided by considering both these common and private areas. In this study, the CTSP is solved using a Genetic Hill-Climbing Algorithm, which is a hybrid of the Genetic Algorithm and the Hill-Climbing Algorithm aimed at producing superior solutions. Furthermore, the CTSP model using the Genetic Hill-Climbing Algorithm is implemented in a case study of package collection for an express delivery company in Bandung. The results of this study provide the shortest routes for the company's package collection. Additionally, by comparing the Genetic Hill-Climbing Algorithm with the Classical Genetic Algorithm, it was found that the Genetic Hill-Climbing Algorithm provides solutions with shorter distances, although it requires longer computational time.

Keywords: Genetic Algorithm, Hill-Climbing, Multiple Traveling Salesman Problem (mTSP)

ABSTRAK

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.