Penyelesaian Travelling Salesman Problem menggunakan algoritma Hungaria dan algoritma Hill Climbing (HC)

Penelitian ini dilatarbelakangi oleh Travelling Salesman Problem (TSP) yang merupakan salah satu bagian dari pemrograman linear yang sering dijumpai di kehidupan sehari-hari. Pada umumnya, masalah ini memetakan penjual dalam menjajakan barang dagangannya untuk mengunjungi setiap kota tepat satu kali dan kembali ke kota awal, dengan memperhatikan biaya atau jarak atau waktu perjalanan minimum. Algoritma Hungaria dan Algoritma Hill Climbing merupakan contoh algoritma yang dapat digunakan untuk menyelesaikan masalah tersebut. Tujuan dari penelitian ini adalah untuk dapat mengoptimalkan urutan perjalanan dari satu kota ke kota yang lain sehingga dapat meminimalkan total biaya atau jarak atau waktu yang ditempuh oleh seorang penjual. Algoritma Hungaria merupakan algoritma untuk menemukan solusi optimal dengan cara mengurangi entri terkecil dari setiap baris dan kolom dari semua entri baris dan kolom, lalu menarik garis seminimal mungkin untuk menutupi entri nol. Sedangkan Algoritma Hill Climbing merupakan algoritma untuk menemukan solusi optimal dengan cara membentuk lintasan awal sebagai keadaan awal (initial state), kemudian dilakukan pengujian dari keadaan awal tersebut, lalu dilakukan kombinasi pertukaran dua kota hingga mencapai kondisi goal. Kondisi goal terjadi saat panjang jalur baru < panjang jalur lama. Pada penelitian ini digunakan versi Simple Hill Climbing dan Steepest-Ascent Hill Climbing. Terdapat tiga contoh kasus data yang diperiksa oleh Algoritma Hungaria dan Algoritma Hill Climbing, yaitu data berukuran 10x10, 12x12 dan 16x16. Pada contoh kasus 10x10 dan 12x12 dihasilkan solusi optimal dengan nilai yang lebih kecil pada Algoritma Hill Climbing. Hasilnya diperoleh bahwa Algoritma Hill Climbing lebih baik dibandingkan dengan Algoritma Hungaria dalam menentukan solusi optimal dari Travelling Salesman Problem