PERBANDINGAN ALGORITMA CHEAPEST INSERTION HEURISTIC DAN NEAREST NEIGHBOR DALAM MENYELESAIKAN TRAVELING SALESMAN PROBLEM

Pokok permasalahan Traveling Salesman Problem adalah perjalanan seorang salesman menuju ke beberapa tempat yang akan dituju dengan jarak yang diketahui lalu kembali ke tempat semula dengan menggunakan rute terpendek dari perjalananya, dan semua tempat yang dituju oleh salesman hanya boleh satu kali.Penelitian ini focus pada masalah pendistribusian barang di PT. Jalur Nugraha Ekakurir (JNE) Medan dengan tujuan alamat pengiriman di wilayah medan.Algoritma Cheapest Insertion Heuristic merupakan suatu algoritma yang digunakan untuk membentuk tur (perjalanan) dengan cara secara bertahap membangun rute jalur terpendek dengan bobot minimal, dengan menambahkan titik-titik baru satu per satu.Algoritma Nearest Neighbor merupakan Algoritma yang sederhana dan cepat untuk membangun panjang tur awal yang layak dari TSP dimana teknik mengambil jarak yang paling dekat dari posisi awal tanpa memperhatikan jarak yang lain. Penelitian ini menghasilkan kesimpulan yaitu penerapan algoritma cheapest insertion heuristic dan nearest neighbor dalam hal pencarian jarak pada masalah pengiriman barang di PT. Jalur Nugraha Ekakurir (JNE) Medan dimulai dengan mencari jarak antar alamat dengan bantuan goggle maps, kemudian dilanjutkan dengan bantuan software WinQSB. Berdasarkan hasi penelitian yang diperoleh menggunakan algoritma cheapest insertion heuristic dan nearest neighbor diperoleh pencarian jarak rute terpendek pengiriman barang di PT. Jalur Nugraha Ekakurir (JNE) Medan yang lebih kecil dihasilkan algoritma nearest neighbor.Hal ini menunjukan algoritma nearest neighbor lebih efektif dalam hal pencarian jarak traveling pada persoalan Traveling Salesman Problem pengiriman barang di PT. Jalur Nugraha Ekakurir (JNE) Medan