STUDI TENTANG PENYELAMATAN TRAVELING SALESMAN DENGAN MENGGUNAKAN METODE REDUKSI PADA TEORI GRAF (Studi Kasus : Perusahaan Kimia Farma)

Abstract

Traveling Salesman Problem adalah perjalanan seorang salesman dalam mengunjungi sekumpulan kota, sedemikian rupa sehingga setiap kota dikunjungi tepat satu kali dan kembali ke kota asal dengan jarak yang minimum. Traveling Salesman Problem berupa graf yang dapat direpresentasikan dengan matriks ketetanggan (matriks adjacency). Terdapat bebrapa metode dalam Traveling Salesman Problem untuk menentukan jarak yang minimum. Antara lain metode Heuristik, City Swap dan Metode Reduksi. Dengan menggunakan metode Reduksi, yaitu dengan mempermudah pencarian lintasan terpendek pada seorang salesman. Dalam hal ini seorang salesman berangkat dari kota T1 mengunjungi (n-1) kota lainnya yaitu T1, T2,….Tn dengan ketentuan bahwa tiap-tiap kota(lokasi) hanya dikunjungi satu kali dan kemuadian kembali ke kota T1. Metode reduksi adalah mencari nilai terpendek pada sebuah graf yang di representasikan ke dalam matriks adjacency.

Kata Kunci :Traveling Salesman Problem, Graf, Adjacency Matriks, Metode Reduksi