Penyelesaian Travelling Salesman Problem (TSP) Dengan Evolutionary Algorithm & Excel Solver (Studi Kasus: AK-47-TSP Instance)

Abstract

Travelling Salesman Problem (TSP) merupakan permasalahan penentuan rute terpendek yang diawali dari titik start untuk mengunjungi sekumpulan titik tepat sekali dan diakhiri dengan kembali ke titik start. Evolutionary Algorithm (EA) merupakan sebuah metaheuristic yang dapat diaplikasikan pada berbagai permasalahan optimasi, termasuk TSP. Solver merupakan Excel Add-In untuk menyelesaikan permasalahan optimasi. Solver menggunakan tiga algoritma, yaitu LP Simplex, GRG Nonlinear, dan EA. Dengan adanya kemampuan EA untuk menyelesaikan TSP dan Solver yang mampu menjalankan EA, maka dapat disimpulkan bahwa penyelesaian TSP dapat dilakukan dengan memanfaatkan Solver. Untuk membuktikan kemampuan tersebut maka diperlukan sebuah TSP Instance yang akan diselesaikan oleh EA dan Solver. AK-47-TSP Instance merupakan salah satu TSP Instance yang terdapat pada Russian TSP Instances. Dengan menggunakan EA & Solver, panjang rute terpendek dari AK-47-TSP Instance adalah 20.998 Km.