Vehicle Routing Problem

Vehicle Routing Problem | Vehicle Routing Problem (VRP) yang diperkenalkan pertama kali oleh Dantzig dan Ramzer pada tahun 1959 memegang peranan penting dalam pengaturan distribusi dan menjadi salah satu masalah yang dipelajari secara luas. Vehicle Routing Problem merupakan perhitungan formulasi dengan mempertimbangkan masalah jumlah kendaraan dan rute yang akan dilalui.

Secara khusus, solusi dari permasalahan Vehicle Routing Problem adalah menentukan sekelompok rute perjalanan di mana suatu rute dilewati oleh sebuah kendaraan yang bermula dan berakhir pada depot, sehingga semua permintaan customer dan seluruh kendala operasionalnya dapat teratasi dengan biaya seminimal mungkin.

Permasalahan terjadi ketika ada satu atau lebih customer  dengan beberapa tempat untuk dikunjungi dalam proses distribusi dengan jumlah dan jenis barang yang berbeda-beda. Proses distribusi itu sendiri menggunakan kendaraan dengan kapasitas yang terbatas. Secara garis besar dasar dari VRP yaitu:

  1. Setiap rute berawal dan berakhir pada distribution center.
  2. Setiap customer dikunjungi hanya oleh 1 kendaraan saja.
  3. Total permintaan dari masing-masing rute tidak boleh melebihi kapasitas kendaraan rute tersebut.
  4. Total waktu yang dihabiskan kendaraan (mencangkup waktu perjalanan dan waktu pelayanan) tidak boleh melebihi batas yang ditentukan.
  5. Total biaya yang dihasilkan minimum.

 Beberapa komponen penting yang terdapat pada VRP, yaitu vehicle, customer, depot, driver, dan faktor-faktor lain :

Vehicle (kendaraan)

Kendaraan memiliki beberapa karakteristik sebagai berikut :

  1. Tiap kendaraan mempunyai batasan kapasitas (berat dan volume) dalam mengangkut barang/produk.
  2. Tiap kendaraan mempunyai total waktu kerja dari awal keberangkatan sampa kedatangan kembali ke depot sesuai ketentuan yang berlaku.
  3. Tiap kendaraan mempunyai sejumlah periode waktu yang tidak ikut diperhitungkan (waktu istirahat pengemudi).
  4. Tiap kendaraan memerlukan biaya untuk melakukan pengiriman.

Customer

Customer memiliki karakteristik sebagai berikut :

  1. Tiap customer mempunyai demand tertentu yang harus dipenuhi tepat waktu, dimana kadang-kadang jumlah pesanan tersebut sudah diketahui dengan pasti (kasus deterministik), namun terkadang ada juga yang jumlahnya tidak pasti (kasus stokastik)
  2. Tiap customer memiliki periode waktu tertentu untuk melakukan penerimaan barang (time window), contohnya jam kerja kantor customer hanya memungkinkan untuk melakukan penerimaan barang antara pukul 9.00 hingga 17.00, periode waktu tersebut adalah time window customer

Depot

Depot merupakan titik awal suatu rute perjalanan dalam transportasi, dimana rute yang akan dilewati oleh kendaraan untuk melakukan pengiriman barang ke customer bisa berawal dan berakhir pada satu depot atau lebih.

Driver (pengemudi)

Pengemudi yang mengoperasikan kendaraan harus memenuhi semua ketentuan yang ditetapkan, misalnya : jam kerja atau total waktu istirahat yang diizinkan oleh perusahaan selama bekerja.

Faktor – faktor lain

Beberapa faktor lain yang ada dalam VRP

  1. Multiple trips : dilakukan oleh suatu kendaraan yang sama dalam satu hari, dimana kendaraan sudah kembali ke depot dan kemudian berangkat lagi untuk melakukan pengiriman berikutnya.
  2. Perjalanan dilakukan oleh kendaraan selama lebih dari satu hari.
  3. Pengelompokan kendaraan dengan berbagai macam tipe produk untuk dikirim.
  4. Ada lebih dari satu depot, sehingga kendaraan berangkat, melewati, dan kembali pada depot yang berbeda.

Model VRP yang sudah dibahas di atas adalah VRP klasik, dimana batasan yang diperhatikan hanya pada pengaturan rute saja. Pada kondisi riil, model VRP ini tidak dapat selalu digunakan untuk mengambil keputusan yang optimal, karena masih ada batasan lain yang mempengaruhi keputusan di dalamnya. Sejak diperkenalkan oleh Dantzig dan Ramser (1959), perhatian telah dikhususkan untuk varian yang lebih kompleks dari VRP yang menyesuaikan dengan kehidupan nyata seperti time window, multiple vehicle, dan backhauls.