Perpustakaan Digital ITB

Menurut teori Graf, penentuan rute terpendek merupakan suatu persoalan mencari lintasan antara dua buah simpul pada graf berbobot untuk mendapatkan jumlah bobot yang paling minimum. Oleh karena itu, perrmasalahan penentuan rute terpendek disebut juga masalah optimasi untuk penentuan lintasan dari titik asal ke titik tujuan dengan meminimumkan biaya. Beberapa algoritma telah dikembangkan dalam pemecahan masalah ini. Setiap algoritma memiliki cara yang berbeda dalam menyelesaikan suatu permasalahan tertentu. Pada penelitian ini, dilakukan pengembangan algoritma untuk menentukan lintasan kritis dari titik asal ke titik tujuan pada suatu jaringan untuk pengiriman produk yang mengalami deteriorasi dan dibatasi jendela waktu dengan meminimumkan total biaya sekaligus pemilihan kendaraan yang akan digunakan untuk pemecahan masalah. Algoritma yang dikembangkan adalah algoritma Dijkstra.Tahapan awal pengembangan algoritma adalah memodifikasi jaringan dari masalah yang diteliti. Modifikasi jaringan dilakukan dengan cara membuat replikasi jaringan. Tahapan kedua adalah membuat langkah-langkah pemecahan masalah untuk meminimumkan total biaya yang terdiri dari biaya tetap kendaraan, biaya variabel kendaraan, biaya pergantian kendaraaan, biaya deteriorasi dan biaya tunggu dengan modifikasi algoritma Dijkstra. Modifikasi Dijkstra dilakukan karena permasalahan yang diteliti tidak bisa dimodelkan secara matematis. Untuk menguji algoritma yang dikembangkan digunakan data hipotetik. Contoh numerik yang diberikan dalam penelitian ini adalah penentuan rute terpendek dengan jendela waktu dan penentuan rute terpendek tanpa jendela waktu dengan fungsi deteriorasi non linier.