Genetic Algorithm Untuk Memperbaiki Rute Travelling Salesman Problem Yang Dihasilkan Dari Nearest Neighbour

Abstract

Travelling Salesman Problem merupakan permasalahan penentuan rute terpendek yang diawali dari titik start untuk mengunjungi sekumpulan titik tepat sekali dan diakhiri dengan kembali ke titik start. Jika sebuah TSP mempunyai banyak titik, maka akan menjadi sebuah NP-Hard Problem. Algoritma yang bekerja berdasarkan heuristic dan metaheuristic dapat menjadi sebuah solusi utuk menyelesaikan NP-Hard Problem. Nearest Neighbour (NN) merupakan salah satu algoritma yang bekerja berdasarkan heuristic. Dikarenakan algoritma ini bekerja berdasarkan heuristic tentunya solusi yang dihasilkan belum tentu solusi yang terbaik, oleh karena itu diharapkan solusi yang dihasilkan masih dapat diperbaiki sehingga diperoleh solusi yang lebih baik. Genetic Algorithm (GA) merupakan sebuah metaheuristic yang dapat diaplikasikan pada berbagai permasalahan optimasi, termasuk TSP. Dalam tulisan ini akan dibahas mengenai GA untuk memperbaiki rute TSP yang dihasilkan dari NN. Pada pengujian terhadap 10 instance, dapat diketahui bahwa algoritma berdasarkan GA dapat memperbaiki rute TSP yang dihasilkan dari NN