PENYELESAIAN TRAVELLING SALESMAN PROBLEM (TSP) ASIMETRISDENGAN ALGORITMA GENETIK COMMONALITY

Abstract

Travelling Salesman Problem (TSP) adalah suatu pencarian rute perjalanan n kota dengan biaya termurah dengan mengunjungi semua kota hanya satu kali. Biaya dapat diasumsikan sebagai jarak, waktu, bahan bakar, dan sebagainya. Berdasarkan biaya, permasalahan TSP dapat dibagi menjadi dua, yaitu TSP-simetris dan TSPasimetris.

Pada TSP-simetris, biaya dari kota 1 ke kota 2 adalah sama dengan biaya dari kota 2 ke kota 1. Sedangkan pada TSP-asimetris, biaya dari kota 1 ke kota 2 tidak sama dengan biaya dari kota 2 ke kota 1. Algoritma Genetik Commonality merupakan suatu pengembangan dari algoritma Genetika. Jika dalam algoritma genetika baku, proses reproduksi dilakukan melalui operator tukar silang dan mutasi. Setiap kromosom dievaluasi dengan menggunakan fungsi fitness. Sedangkan pada algoritma genetik commonality, operasi tukar silang didefinisikan kembali dalam dua tahap (Chen & Stephen, 1999) : 1) memelihara common schema maksimal dari dua induk, dan 2) melengkapi solusi dengan construction heuristic. Karena keturunan yang dihasilkan akan lebih baik dibandingkan dengan kedua induknya, maka evolusi akan terjadi tanpa menyatakan seleksi alam secara eksplisit. Dengan kata lain, evolusi terjadi tanpa melibatkan fungsi fitness. Penelitian dilakukan dengan beberapa langkah. Langkah pertama membangkitkan populasi awal (rute awal) menggunakan construction heuristic dengan metode AI (Arbitrary Insertion). Langkah kedua melakukan reproduksi solusi baru dengan operasi tukar silang. Langkah ketiga membentuk populasi baru (kumpulan rute). Berdasarkan penelitian yang telah dilakukan, didapatkan hasil bahwa jarak perjalanan terpendeknya sepanjang 1007 km dengan rute 1-13-24-7-20-23-22-19-1621-25-4-11-9-15-18-14-2-17-8-10-12-5-3-6 dan diperoleh kesimpulan dapat dihasilkan jarak yang sama dengan rute yang berbeda disebabkan adanya proses penyisipan kota-kota yang tidak terdapat pada Graf Partial Order menggunakan metode AI.