Analisis Metode Heuristik Pengolahan Data Travelling Salesman Problem Terhadap Jumlah Titik

摘要

Penelitian ini dimaksudkan untuk menentukan metode heuristik pengolahanuddata Travelling Salesman Problem yang efektif dalam jarak tempuh yang minimumuddan efesien dalam waktu proses pengolahan data. Persoalan rute merupakanudsebuah persoalan yang klasik dan sering dijumpai, masalah penentuan ruteudberkaitan dengan masalah meminimumkan jarak tempuh. Untuk dapat menentukanudurutan kota yang akan dilalui diperlukan data jarak antara masing-masing kotaudsehingga dapat diolah dengan metode heuristik. Namun, persoalan rute iniudtermasuk dalam kelas NP-hard dimana terdapat banyak alternatif rute yangudmeningkat secara ekponensial seiring banyaknya jumlah kota yang akanuddikunjungi. Oleh karena itu, diperlukan sebuah perangkat lunak yang dapatudmemproses data matriks jarak sehingga dapat mengefisienkan waktu prosesudpengolahan data. udNearest Neighbour, Saving Algorithm, Nearest Insertion, CheapestudInsertion, dan Farthest Insertion merupakan metode heuristik yang dapatuddigunakan dalam pengolahan data Travelling Salesman Problem. Metode heuristikudtersebut diterjemahkan kedalam bahasa pemrograman untuk dirancang sebuahudperangkat lunak yang dapat membantu dalam pengolahan data disertakan fungsiudyang dapat menampilkan waktu proses pengolahan data. Pengumpulan dataudmerupakan data sekunder TSPLib yang berupa titik koordinat sehingga diperlukanudpengolahan data menjadi data matriks jarak. udDari hasil pengolahan data sekunder dapat disimpulkan bahwa metodeudyang efektif dalam pengolahan data matriks jarak adalah metode NearestudNeighbour karena pada delapan kali percobaan pengolahan data metode tersebutuddapat menyelesaikan lima persoalan dengan hasil yang minimum, dan metode yangudefisien dalam pengolahan data matriks jarak adalah metode Saving Algorithmudkarena pada waktu proses pengolahan data secara keseluruhan metode tersebutudmempunyai waktu proses yang paling minimum.