PENENTUAN RUTE TERPENDEK DENGAN MENGGUNAKAN ALGORITMA CHEAPEST INSERTION HEURISTIC (STUDI KASUS: PT. Wicaksana Overseas International Tbk. Cabang Pontianak)

Abstract

Algoritma Cheapest Insertion Heuristic (CIH) adalah algoritma yang membangun suatu  tour (perjalanan) dengan membuat rute terpendek dengan bobot minimal dan secara berturut-turut ditambah dengan tempat baru. Tahapan pertama yaitu menentukan titik awal dan akhir. Setelah itu yang dilakukan adalah membangun subtour antara dua lokasi tersebut. Subtour merupakan perjalanan dari lokasi pertama dan berakhir di lokasi pertama juga. Setelah itu yang dilakukan adalah membangun subtour antara dua lokasi tersebut. Setelah itu ganti salah satu arah busur dari dua lokasi dengan kombinasi dua busur, yaitu busur (i,j) dengan busur (i,k) dan busur (k,j), dengan k diambil dari lokasi yang belum masuk subtour dan dengan sisipan terkecil. Penentuan sisipan dengan cara: C_{ik +} C_{kj -} C_ij dengan artian C_ik adalah jarak dari lokasi i ke lokasi k, C_kj adalah jarak dari lokasi k ke lokasi j dan C_ij adalah jarak dari lokasi i ke lokasi j. Jika seluruh lokasi sudah masuk ke dalam subtour maka pengerjaan mencari rute terpendek sudah selesai. Tujuan dari penelitian ini adalah mengkaji algoritma CIH, menentukan rute terpendek dengan algoritma CIH dan membuat model graf dari rute terpendek dari algoritma CIH. PT. Wicaksana Overseas International Tbk. cabang Pontianak adalah perusahaan yang mendistribusikan beberapa produk terkenal seperti Aqua, White Oat, Gaga, Susu Bendera, Mie 100, Tulipe, Teh Keris, Delident, Jet Star dan Dynex yang didistribusikan ke sembilan swalayan di daerah Kota Pontianak. Dalam penelitian ini diperoleh rute terpendek yaitu PT.Wicaksana Overseas International Tbk → Citra Jeruju → Mitra Mart → Garuda Mitra → Mitra Anda → Kaisar → Harum Manis → Ramayana → Ligo Mitra → Mitra Mart → PT.Wicaksana Overseas International Tbk dengan jarak tempuh dalam sekali perjalanan adalah sebesar 11.593 meter.

Kata Kunci : Cheapest Insertion Heuristic, Rute terpendek