APLIKASI SIMULATED ANNEALING UNTUK MENYELESAIKAN TRAVELLING SALESMAN PROBLEM

Abstract

Travelling Salesman Problem (TSP) merupakan salah satu permasalahan optimasi kombinatorial yang penyelesaian akhirnya bertujuan untuk mendapatkan solusi optimal yaitu menemukan rute perjalanan yang paling minimum. Pada kenyataannya, TSP bukan hanya masalah rute terpendek saja melainkan juga masalah biaya dan waktu perjalanan yang optimal. Untuk menyelesaikan dan menemukan solusi dari permasalahan tersebut salah satu algoritma yang bisa digunakan adalah Simulated Annealing (SA). SA merupakan analogi dari proses pendinginan cairan logam yang disebut annealing. Pada penelitian ini dilakukan analogi dan pengembangan algoritma SA sehingga mampu digunakan untuk menyelesaikan TSP dengan beberapa fungsi objektif. Tujuan dari penelitian ini adalah mengaplikasikan SA untuk menyelesaikan TSP. Langkah pertama yang dilakukan adalah rute awal ditentukan secara random dan dihitung biaya, jarak dan waktu perjalanan salesman. Langkah selanjutnya ditentukan rute baru dengan cara menukarkan tetangga berikutnya dan evaluasi rute baru tersebut. Hasil perhitungan diperoleh minimum biaya perjalanan salesman PT. XX yang diberikan sebesar Rp. 77.000, jarak tempuh perjalanan 39 km dan waktu perjalanan 2 jam 37 menit dengan rute 0 "“ 3 "“ 4 "“ 5 "“ 2 "“ 1 "“ 0.

Kata kunci: Simulated Annealing, Travelling Salesman Problem, graf