OPTIMASI RUTE TRAVELLING SALESMAN PROBLEM DENGAN ALGORITMA A* (A-STAR)

Abstract

Travelling Salesman Problem (TSP) merupakan persoalan yang penting dalam sistem distribusi. Secara umum TSP digambarkan sebagai suatu kasus perjalanan seorang sales yang berangkat dari kota asal mengunjungi sejumlah kota tepat satu kali dan kembali lagi ke kota asalnya tersebut. Banyak penerapan TSP yang muncul dalam kehidupan sehari-hari, salah satunya adalah permasalahan rute pedagang pupuk dan obat-obat pertanian. Banyaknya kios yang akan dituju tentunya membuat seorang sales menginginkan untuk dapat mendistribusikan pupuk dan obatobat

pertanian ke beberapa kios dengan melewati rute terpendek sehingga dapat meminimalkan waktu dan biaya. Oleh karena itu, dalam skripsi ini dibahas penyelesaian TSP dengan algoritma A* untuk memperoleh rute terpendek dari TSP. Tujuan penelitian adalah untuk mengaplikasikan algoritma A* pada TSP dan membuat program algoritma A* untuk menyelesaikan TSP dengan Visual Basic 6.0. Hasil penelitian diharapkan dapat memberikan alternatif metode penyelesaian TSP kepada pengguna. Penelitian dilakukan melalui beberapa langkah, yaitu mengidentifikasi tiaptiap kios sebagai titik dan jarak antar kios sebagai sisi kemudian direpresentasikan ke

dalam

graf berbobot. Selanjutnya membuat algoritma pemrograman dari masalah TSP menggunakan algoritma A* dan membuat program berdasarkan algoritma pemrograman tersebut dengan Visual Basic 6.0 dan yang terakhir adalah mencari rute terpendek TSP dengan algoritma A* menggunakan program yang telah dibuat.

Algoritma A* dapat digunakan untuk menyelesaikan persoalan TSP, sehingga dapat menghasilkan rute perjalanan sales di UD. Tani Lumintu dengan total jarak minimal. Rute minimal yang dihasilkan adalah UD. Tani Lumintu  Sari bumi  Toko Krisna Makmur  UD. Hasil Tani  Mbah Jenggot  UD. Wasilah  Kios Subur  Al-Ikhlas Mitra Tani  UD. Panorama Mbah Taujan  Rizki Abadi  Sumber Abadi  Tani Gemilang  Anisa Jaya  UD. Mitra Amanah  Jaya Tani  Abdi Tani  Mitra Tani  Sumber Rejeki (1)  Usaha Tani  Sahabat Tani  Sinar Tani (1)  Tani Lumintu 3  Sri Rejeki  Cahaya Tani  UD. Tani Mulyo  Toko Rizki  Witanto  Sinar Tani (2)  sumber Rejeki (2)  Muncar Tani  Sampoerna  UD. Tani Lumintu atau sebaliknya dengan total jarak 151,2 km. Hasil tersebut diperoleh dari program yang telah dibuat menggunakan algoritma A* dengan bantuan Visual Basic 6.0 dimana input berupa banyaknya titik yang akan digunakan dan data jarak antar titik, sedangkan output berupa hasil rute minimal beserta total jaraknya sekaligus visualisasi gambar dari rute minimal tersebut. Program tersebut dapat mempermudah perhitungan TSP terutama untuk jumlah titik yang relatif besar.