Optimasi Vehicle Routing Problem (Vrp) Dengan Metode Saving Matrix dan Branch And Bound Untuk Menentukan Rute Terpendek Distribusi Lpg 3 KG Pada PT Dwi Putera Kencana Bhakti Jember

Abstract

Pengolahan dan pengelolaan LPG dilaksanakan oleh PT Pertamina yang merupakan Badan Usaha Milik Negara dan disalurkan melalui agen dan pangkalan resmi yang tersebar di seluruh Indonesia. PT Dwi Putera Kencana Bhakti adalah agen LPG 3 kg resmi di Kabupaten Jember dengan pangkalan resmi berjumlah 39 pangkalan. Pembagian rute distribusi LPG pada PT Dwi Putera Kencana Bhakti dilakukan dengan alokasi satu armada pick-up untuk satu pangkalan dengan kapasitas maksimal 200 tabung, dan satu armada truck untuk 2 sampai 3 pangkalan degan mempertimbangkan kapasitas maksimal sebesar 560 tabung. Sistem pengiriman tabung LPG dengan pick-up kurang efisien dilakukan karena kapasitas 1 pick-up dapat mengangkut permintaan LPG untuk 2 pangkalan pada rute tertentu. Jika hal tersebut dilakukan, maka pick-up tidak perlu kembali ke gudang sekali lagi untuk mengisi tabung, sehingga akan didapat penghematan jarak distribusi. Analisis rute distribusi dibutuhkan untuk mendapatkan penghematan jarak distribusi secara maksimal. Permasalahan mengenai jarak dan rute distribusi terpendek disebut sebagai Vehicle Routing Problem (VRP), yaitu masalah rute transportasi yang bertujuan untuk menemukan rute dengan biaya minimal dengan cara menemukan jalur terpendek, minimasi jumlah kendaraan dan lain-lain, sehingga semua permintaan pada titik simpul dapat terpenuhi (Belfiore et al., 2008). Metode yang akan digunakan untuk menyelesaikan VRP adalah metode saving matrix dan branch and bound. Metode saving matrix menghasilkan jadwal dan rute distribusi, dan metode branch and bound digunakan untuk menghasilkan urutan pengiriman ke pangkalan berdasarkan jarak terpendek. Kombinasi metode saving matrix dan branch and bound menghasilkan jarak yang lebih efisien. Hasil analisis dengan metode saving matrix dan branch ad bound pada PT Dwi Putera Kencana Bhakti, menghasilkan penghematan jarak 200,2 km atau sebesar 7,28%, dan penghematan biaya Rp 106.695,00 atau sebesar 2,39%.