PENYELESAIAN COLORED TRAVELING SALESMAN PROBLEM MENGGUNAKAN ALGORITMA GENETIKA HILL-CLIMBING - Fakhrana Nadhilah, - (2019)
Multiple Traveling Salesman Problem (MTSP) adalah salah satu permasalahan optimisasi yang bertujuan menentukan rute perjalanan dengan jarak terpendek dari pada beberapa pekerja. Permasalahan MTSP ini dikembangkan menjadi Colored Traveling Salesman Problem (CTSP) dimana terdapat dua wilayah kerja yaitu wilayah umum dan wilayah pribadi. Wilayah umum merupakan wilayah dimana setiap pekerja dapat mengunjungi kota-kota di wilayah tersebut. Sedangkan pada wilayah pribadi hanya pekerja yang ditugaskan yang dapat mengunjungi kota-kota di wilayah tersebut. Pada CTSP rute dari beberapa pekerja akan dibagi dengan mempertimbangkan wilayah umum dan wilayah pribadinya. Salah satu metode yang dapat digunakan untuk menyesaikan CTSP adalah Algoritma Genetika Hill-Climbing. Algoritma Genetika Hill-Climbing adalah salah satu metode optimisasi yang merupakan penggabungan dari Algoritma Genetika dengan Algoritma Hill-Climbing dengan tujuan menghasilkan solusi yang lebih baik. Algoritma Hill-Climbing akan digunakan untuk memilih solusi sebelum masuk ke tahap seleksi, crossover dan mutasi. Penelitian ini akan membahas mengenai penyelesaian model CTSP dengan menggunakan Algoritma Genetika Hill-Climbing pada kasus pengumpulan paket suatu perusahaan ekspedisi di Kota Bandung. Kemudian akan dibangun pula suatu program pendukung yang dapat mempermudah dalam menyelesaikan masalah CTSP dengan menggunakan Algoritma Genetika Hill-Climbing. Hasil dari penelitian ini yaitu model CTSP dapat digunakan untuk menyelesaikan kasus pengumpulan paket dengan menggunakan Algoritma Genetika Hill-Climbing dan perbandingan Algoritma Genetika Hill-Climbing dengan Algoritma Genetika Klasik menunjukkan bahwa Algoritma Genetika Hill-Climbing memberikan solusi dengan jarak yang lebih pendek meskipun membutuhkan waktu komputasi yang lebih lama.;---Multiple Traveling Salesman Problem (MTSP) is one of optimization problem which aims to determine tours of some workers with minimal total cost. MTSP problem developed to Colored Traveling Salesman Problem (CTSP) that have two types of workspaces called shared workspace and exclusive workspace. Cities ini shared workspace can be visited by all workers, but cities in exclusive workspace only can be visited by assigning worker. The route at CTSP will be divided by considering the shared workspace and exclusive workspace. One of methods that can be used to solve CTSP is Hill-Climbing Genetic Algorithm. Hill-Climbing Genetic Algorithm is optimization methods that combining Genetic Algorithm and Hill-Climbing Algorithm with purposes to result better solution. Hill-Climbing Algorithm used for choosing the solution for Selection, Crossover and Mutation. This study will discuss the solution of CTSP using Hill-Climbing Genetic Algorithm for package collection at one of shipping company in Bandung. Afterwards a program will be built to facilitate solving CTSP using Hill-Climbing Genetic Algorithm. The result shows that CTSP with Hill-Climbing Genetic Algorithm can be used for solving package collection problem and comparison of Hill-Climbing Genetic Algorithm and Classic Genetic Algorithm shows that Hill-Climbing Genetic Algorithm resulting better solution although takes longer computing time.