TRAVELLING SALESMAN PROBLEM (TSP) UNTUK MENENTUKAN RUTE TERPENDEK BAGI KURIR KOTA KENDARI MENGGUNAKAN ALGORITMA GREEDY BERBASIS ANDROID

Abstract

Kurir pelayanan delivery order Kota Kendari seringkali mengalami kesulitan untuk menentukan lintasan terpendek dalam pengantaran barang karena banyaknya alternatif jalan yang ada. Tidak jarang pula, kurir tidak mengenal dengan baik alamat yang dituju sehingga tidak dapat memperhitungkan jarak alamat tersebut dan bisa jadi melewati titik yang sama berulangkali sehingga lintasan yang dilewati tidak efisien. Untuk itu diperlukan suatu sistem yang dapat membantu kurir dalam menentukan lintasan terpendek dan dapat merepresentasikan data yang ada. Data tersebut dapat disimpan, diolah, dan disajikan dalam bentuk yang lebih sederhana serta terkomputerisasi sehingga memudahkan dalam penentuan lintasan terpendek.Travelling Salesman Problem (TSP) adalah pencarian rute terpendek atau jarak minimum oleh seorang salesman dari suatu kota ke n-kota tepat satu kali dan kembali ke kota awal keberangkatan. TSP dapat diterapkan pada graph komplit berbobot yang memiliki total bobot sisi minimum, dimana bobot pada sisi adalah jarak. Rute TSP ini memuat semua titik pada graph tersebut tepat satu kali. Proses optimalisasi ini dilakukan dengan memperhitungkan fungsi heuristik yang akan mempersempit ruang pencarian. Hasil dari aplikasi ini berupa urutan alamat yang akan dikunjungi oleh kurir beserta lintasan terpendek antar alamat pada peta Kota Kendari.Algoritma Greedy adalah algoritma yang memecahkan masalah langkah demi langkah dan merupakan salah satu metode dalam masalah optimasi. Pendekatan yang dilakukan dalam Algoritma Greedy adalah membuat pilihan yang terlihat memberikan perolehan terbaik yaitu dengan membuat pilihan optimum local pada setiap langkah dan diharapkan akan mendapatkan solution optimum global.Kata kunci— Android, Ponsel, Rute Terpendek, Travelling Salesman Problem, SP, Kurir, Algoritma Greedy.