Vehicle Routing Problem
Kelompok 6
UNIVERSITAS NEGERI GORONTALO
Desember 2018
Kelompok 6 Riset Operasi
Definisi Vehicle Routing Problem (VRP)
Dalam pendistribusian barang atau jasa dibutuhkan
penentuan rute kendaraan yang optimal untuk mendukung
kelancaran pelayanan barang atau jasa. Masalah ini dikenal dengan
istilah Vehicle Routing Problem (VRP). VRP merupakan masalah
pencarian rute optimal untuk pengiriman atau pengumpulan
barang atau jasa dari satu atau lebih depot ke sejumlah kota atau
pelanggan dengan memenuhi kendala tertentu (Toth dan Vigo
2002).
Kelompok 6 Riset Operasi
Tujuan Vehiclle Routing Problem (VRP)
VRP pertama kali dipelajari oleh Dantzig dan Ramser pada
tahun 1959 dalam bentuk rute dan penjadwalan truk. Pada tahun
1964 Clarke dan Wright kemudian melanjutkan penelitian ini
dengan memperkenalkan istilah depot sebagai tempat
keberangkatan dan kembalinya kendaraan. Sejak saat itu penelitian
VRP terus berkembang karena peran VRP yang penting dalam
distribusi dunia industri. Terdapat empat tujuan utama VRP, yaitu
meminimalkan biaya transportasi, meminimalkan jumlah kendaraan
yang dibutuhkan, mengoptimalkan rute, dan meminimalkan biaya
penalti akibat pelayanan yang kurang memuaskan.
Kelompok 6 Riset Operasi
Klasifikasi Vehicle Routing Problem (VRP)
Secara ringkas, berikut adalah karakteristik dari
permasalahan VRP:
Perjalanan kendaraan berawal dan berakhir dari dan ke depot
awal.
Ada sejumlah tempat yang semuanya harus dikunjungi dan
dipenuhi permintaannya tepat satu kali.
Jika kapasitas kenderaan sudah terpakai dan tidak dapat
melayani tempat berikutnya, kendaraan dapat kembali ke
depot untuk memenuhi kapasitas kendaraan dan melayani
tempat berikutnya.
Tujuan dari permasalahan ini adalah meminimumkan total
jarak yang ditempuh kendaraan dengan mengatur urut-urutan
tempat yang harus dikunjungi beserta kapan kembalinya
kendaraan untuk mengisi kapasitasnya lagi.
Kelompok 6 Riset Operasi
Metode Penyelesaian VRP
Permasalahan untuk mendapatkan hasil solusi yang optimal
dari pemecahan VRP (Vehicle Routing Problem) menjadi
bertambah jika terdapat penambahan kendala (constraints) pada
kasus yang harus diselesaikan. Pada dasarnya terdapat tiga macam
penyelesaian VRP yaitu dengan metode solusi eksak yang
melakukan pendekatan dengan menghitung sampai satu solusi
terbaik dapat diperoleh, dengan metode heuristik yaitu dengan
melakukan pendekatan namun waktu penyelesaian lebih cepat
daripada solusi eksak, dan dengan metode metaheuristik yaitu
dengan melakukan perbaikan mulai dengan satu atau lebih solusi
awal (Toth dan Vigo 2002).
Kelompok 6 Riset Operasi
Formulasi Matematika VRP
Didefinisikan G = (V , A) merupakan graf lengkap dengan
G = {0, 1, ..., n}, verteks 0 menunjukkan depot, dan selainnya
menunjukkan pelanggan. Dimisalkan bahwa S ⊆ V − {0}
menunjukkan himpunan pelanggan, sedangkan A didefinisikan
sebagai sejumlah lintasan yang terdiri dari lintasan berlawanan (i,j)
dan (j,i) untuk setiap i, j ∈ A. Sedangkan Cij menunjukkan
besarnya biaya yang dikeluarkan untuk melakukan perjalanan dari
pelanggan i ke pelanggan j, r menunjukkan jumlah minimum
kendaraan yang yang di butuhkan untuk melayani pelanggan, serta
K menunjukkan banyaknya kunjungan yang masuk ataupun keluar
depot.
Kelompok 6 Riset Operasi
Formulasi Matematika VRP
variabel keputusan
x(kij =
1 jika kendaraan K melakukan perjalanan dari pelanggan i ke j
0 selainnya
(
1 jika terjadi kunjungan di antara (i,j)
yij =
0 selainnya
fungsi objektif min K
P P
Cij xkij
PK P(i,j)∈A
k=1
fungsi objektif min k=1 (i,j)∈A Cij xkij
Kelompok 6 Riset Operasi
Kendala :
Pn
1 yij = 1, j = 2, 3, ..., n
Pi=1
n
2 yij = 1, j = 2, 3, ..., n
Pj=1
n
3 y1j = K
Pj=1
n
4 y1i = K
Pi=1
n Pn
j=2 Dj xkij ≤ U, k = 1, 2, ..., K
5
i=1
PK
6 xkij = yij ∀i, j
Pk=1
(i,j)∈SxS ≤| S | −1, for all subsets S of (2, 3, ..., n), i 6= j
7
8 xkij = 0 or 1, ∀(i, j) ∈ A dan ∀K
9 yij = 0 or 1, ∀(i, j) ∈ A
Kelompok 6 Riset Operasi
Formulasi VRP
Dari formulasi matematika tersebut ditunjukkan bahwa fungsi
objektif bertujuan meminimumkan biaya perjalanan. Kendala (1)
dan (2) menyatakan bahwa tiap pelanggan tepat dikunjungi satu
kali. Kendala (3) dan (4) menyatakan bahwa banyaknya kunjungan
yang masuk ke depot dan keluar dari depot besarnya sama dan
ditunjukkan dengan K . Kendala (5) menyatakan setiap kendaraan
harus membawa kurang dari atau sama dengan jumlah kapasitas
yang tersedia. Kendala (6) menyatakan setiap kendaraan hanya
dapat melayani pelanggan satu kali. Kendala (7) menyatakan
bahwa kendaraan dari depot harus kembali ke depot. Kendala (8)
dan (9) menyatakan bahwa variabel kunjungan bernilai biner (Toth
dan Vigo 2002).
Kelompok 6 Riset Operasi