Penyelesaian Travelling Salesman Problem (TSP) Menggunakan Algoritma Semut dan Algoritma Cheapest Insertion Heuristic (CIH);

Abstract

Travelling Salesman Problem (TSP) adalah permasalahan perjalanan seorang salesman yang harus mengunjungi n buah titik dengan aturan salesman harus mengunjungi setiap titik tepat satu kali dan pada akhirnya harus kembali ke titik asalnya. Salesman juga harus meminimalisasi biaya perjalanan. Salah satu permasalahan yang dapat dimodelkan dengan TSP adalah masalah pencarian rute pengisian mesin-mesin ATM di wilayah Jember dan Bondowoso, dimana titik adalah lokasi mesin-mesin ATM di wilayah Jember dan Bondowoso. Sedangkan biaya perjalanan adalah total jarak perjalanan petugas pengisi mesin ATM yang merupakan jarak total yang ditempuh petugas dari mesin ATM ke mesin ATM yang lain. TSP dapat diselesaikan dengan menggunakan metode heuristik salah satunya adalah algoritma CIH. Tujuan yang ingin dicapai dalam penulisan skripsi ini adalah mendapatkan solusi dari TSP dengan menggunakan algoritma CIH pada rute pengisian mesin ATM di wilayah Jember dan Bondowoso dan membuat program untuk penyelesaian masalah tersebut serta membandingkan hasil dari algoritma CIH dengan algoritma semut dalam menyelesaikan TSP. Hasil penelitian ini diharapkan dapat memberikan alternatif metode penyelesaian TSP menggunakan algoritma CIH pada rute pengisian mesin ATM dan dengan pembuatan programnya, dapat mempermudah penyelesaian TSP. Data yang digunakan adalah data lokasi mesin ATM di wilayah Jember dan Bondowoso beserta jarak antar mesin ATM. Penelitian dilaksanakan dalam 6 tahap, yaitu identifikasi lokasi mesin-mesin ATM di Wilayah Kabupaten Jember dan Bondowoso, merepresentasikan data dalam viii graf lengkap dan berbobot, mengolah data menggunakan algoritma CIH dan algoritma semut, membuat algoritma pemrograman dari masalah tersebut, membuat program menggunakan software Delphi 7.0. Hasilnya berupa rute perjalanan petugas pengisi mesin ATM sehingga total perjalanan petugas pengisi mesin ATM di wilayah Jember dan Bondowoso minimal. Hasil tersebut didapatkan dari program yang telah dibuat untuk menyelesaikan TSP dengan algoritma CIH dan algoritma semut. Dari hasil program tersebut, didapatkan bahwa untuk jumlah titik yang banyak algoritma semut memberikan rute yang lebih minimum daripada algoritma CIH, berdasarkan waktu eksekusi program algoritma CIH membutuhkan waktu yang lebih cepat daripada algoritma semut sedangkan dari iterasi yang digunakan untuk memperoleh rute optimal, algoritma semut menghasilkan iterasi yang lebih sedikit daripada algoritma CIH. Program tersebut dapat digunakan untuk data yang berbeda pada semua permasalahan TSP. Input dari program tersebut adalah matriks jarak, banyak kota, parameter α, β, dan , sedangkan output dari program tersebut berupa rute optimal, panjang rute optimal dan gambar rute optimal.