VEHICLE ROUTING PROBLEM

1. Pengertian dan Tipe-Tipe VRP

Vehicle Routing Problem (VRP) merupakan permasalahan utama dalam manajemen

distribusi. Perusahaan-perusahaan yang bergerak di bidang distribusi akan selalu menghadapi
permasalahan ini dalam melaksanakan kegiatan operasionalnya. Permasalahan distribusi ini dapat
berupa distribusi barang ataupun manusia. Permasalahan distribusi barang sering dihadapi oleh
perusahaan-perusahaan manufaktur dalam mengirimkan produknya kepada konsumen. Sedangkan
untuk permasalahan distribusi manusia biasanya dihadapi oleh perusahaan yang bergerak di bidang
jasa, misalnya transportasi bagi penyandang cacat dan permasalahan penumpang bis kota.
VRP adalah problem penentuan sejumlah rute untuk sejumlah kendaraan yang berada pada
satu atau lebih depot sehingga bisa melayani konsumen-konsumen yang tersebar secara geografis.
VRP merupakan pengembangan dari Travelling Salesman Problem (TSP) dengan
mempertimbangkan batasan kapasitas muatan dan waktu tempuh. TSP memiliki fungsi tujuan untuk
meminimumkan jarak/waktu/biaya tempuh dengan batasan salesman hanya mengunjungi lokasi
konsumen hanya satu kali. Sedangkan VRP lebih kompleks dibandingkan TSP karena lebih banyak
mempertimbangkan faktor dalam membuat keputusan rute kendaraan dan memiliki batasan-batasan
yang lebih luas sesuai dengan kondisi nyata yang terjadi di lapangan. Batasan-batasan tersebut
dapat berupa :
1. Setiap lokasi pemberhentian/lokasi konsumen memiliki volume barang yang harus diangkut
ataupun dikirimkan.
2. Depot memiliki jenis kendaraan dengan kapasitas angkut heterogen. Batasan kapasitas dapat
berupa volume, berat atau keduanya.
3. Depot hanya memiliki jumlah kendaraan yang terbatas untuk melayani permintaan
konsumen.
4. Depot dapat memberlakukan aturan maksimum waktu tempuh kendaraan untuk melalui satu
rute.
5. Setiap lokasi pengangkutan ataupun pengiriman dapat menerapkan aturan kunjungan, yaitu
hanya dapat dikunjungi pada waktu tertentu.
6. Jumlah depot dapat lebih dari satu.
Berdasarkan batasan-batasan yang dipertimbangkan sesuai dengan kondisi nyata, VRP
dibagi menjadi 8 tipe yaitu :
1. Capacitated Vehicle Routing Problem (CVRP). Ciri khas dari permasalahan ini adalah
sistem distribusi memiliki satu depot dan hanya memiliki batasan kapasitas kendaraan
dengan fungsi tujuan meminimalkan total biaya transportasi. Contoh nyata dari
permasalahan ini adalah distribusi semen dimana pabrik mengirimkan semennya ke gudang
penyangga setiap hari. Contoh lainnya adalah pengumpulan sampah dari satu wilayah ke
wilayah lain oleh petugas sampah.
2. Distance Constrained Vehicle Routing Problem (DCVRP). Tipe permasalahan ini
merupakan turunan dari permasalahan CVRP, dengan menambahkan batasan total waktu
tempuh dari setiap rute. Tujuan dari permasalahan ini adalah meminimumkan total jarak
atau waktu tempuh.
3. Vehicle Routing Problem with Back Hauls (VRPB). Ciri khas dari permasalahan ini adalah
CVRP yang dibagi dalam 2 tipe konsumen, yaitu konsumen yang meminta layanan angkut
(back haul) dan konsumen yang meminta layanan antar (line haul). Dimana sebelum
melakukan pengangkutan maka kendaraan harus memenuhi semua jadwal pengiriman
terlebih dahulu.
 4. Vehicle Routing Problem with Time Windows (VRPTW). VRP yang mempertimbangkan
batasan-batasan time windows (dimana tiap konsumen memiliki waktu kunjungan tertentu).
5. Vehicle Routing Problem with Pick Up and Delivery (VRPPD). VRP dimana setiap
customer memiliki satu lokasi pick up (jemput) dan satu lokasi delivery (antar). Dengan
lokasi pick up bisa identik bisa tidak dengan lokasi delivery.
6. Vehicle Routing Problem with Back Hauls and Time Windows (VRPBTW). VRPB yang
memperhatikan time windows.
7. Vehicle Routing Problem with Pick Up and Delivery with Time Windows (VRPPDTW).
VRPPD dengan ada aturan kunjungan tertentu pada setiap lokasi penjemputan dan
pengiriman.
8. Multiple Depot Vehicle Routing Problem (MDVRP). VRP dengan jumlah depot lebih dari
satu.

2. Penyelesaian Capacitated Vehicle Routing Problem (CVRP)

Permasalahan VRP merupakan permasalahan NP-Hard (Non Polynomial Hard Problem),
yang berarti usaha komputasi yang digunakan akan semakin sulit dan banyak seiring dengan
meningkatnya ruang lingkup masalah. Apabila permasalahan VRP semakin besar (dengan
bertambahnya jumlah konsumen dan pembatas-pembatas yang dipertimbangkan) maka metode
eksak tidak dapat digunakan lagi secara efektif karena membutuhkan waktu komputasi yang sangat
lama. Oleh karena itu bannyak permasalahan VRP diselesaikan dengan metode heuristik.
Pada bagian ini akan dijelaskan 2 metode heuristik klasik untuk menyelesaikan CVRP yaitu
metode saving matrix dan generalized assignment.

A. Metode Saving Matriks

Langkah-langkah yang dilakukan untuk menentukan konsumen yang harus dilayani oleh sebuah
truk serta rute pengiriman yang harus ditempuh masing-masing truk adalah sebagai berikut :
1. Menentukan matriks jarak.
Matriks jarak menyatakan jarak diantara tiap pasangan lokasi-lokasi yang akan dikunjungi.
Jarak antara lokasi A yang terletak pada koordinat (X a, Ya) dan lokasi B yang terletak pada
koordinat (Xb, Yb) dicari dengan menggunakan rumus :

2. Menentukan matriks penghematan (saving matriks).

Matriks penghematan menunjukkan penghematan yang terjadi jika menggabungkan 2
konsumen kedalam satu truk. Penghematan bisa dievaluasi berdasarkan jarak atau waktu atau
uang.
S (x,y) menyatakan jarak yang dihemat jika perjalanan DC  konsumen x  DC dan DC 
konsumen y  DC dikombinasikan ke sebuah rute perjalanan tunggal yaitu DC  konsumen x
 konsumen y  DC. Rumus untuk mencari besarnya penghematan adalah :
S(x,y) = Dist (DC,x) + Dist (DC,y) – Dist (x,y)
3. Mengalokasikan konsumen-konsumen ke sebuah rute/kendaraan atau menugaskan konsumen
pada sebuah rute.
 Pengalokasian konsumen ke sebuah rute/kendaraan harus bisa memaksimalkan
penghematan.
 Pencarian solusi dilakukan dengan prosedur iteratif yaitu :
a. Pada tahap 1 : tiap konsumen dialokasikan pada truk/rute yang berbeda-beda/terpisah.
b. Pada tahap 2 : Dua rute selanjutnya dapat digabungkan pada satu rute/kendaraan dengan
didasarkan pada penghematan yang paling tinggi yang bisa diperoleh. Selanjutnya
dilakukan pengecekan apakah pengkombinasian tersebut layak atau tidak. Dikatakan
layak jika total pengiriman yang harus dilalui melalui rute tersebut tidak melebihi
kapasitas kendaraan.
4. Menentukan urutan konsumen/urutan pengiriman pada sebuah rute.
Tujuan dari tahap ini adalah meminimalkan jarak perjalanan yang harus ditempuh tiap
kendaraan. Untuk mendapatkan rute pengiriman yang optimal dilakukan dalam 2 tahap : (1)
menentukan rute pengiriman awal untuk tiap kendaraan dengan menggunakan prosedur Farthest
insert/Nearest insert/dll. (2) melakukan perbaikan dengan menggunakan prosedur tertentu.

B. Penjadwalan dan Penentuan Rute Pengiriman dengan Generalized Assigment

Langkah-langkah yang dilakukan meliputi :
1. Menentukan seed point untuk masing-masing rute/alat angkut dimana seed point
merupakan pusat perjalanan yang diambil oleh tiap alat angkut. Prosedurnya adalah :
a. Menentukan Lseed dengan rumus Lseed = total permintaan / jumlah alat angkut
b. Dimulai dari pelanggan manapun, lakukan gerakan searah jarum jam dimulai dari DC untuk
mendapatkan cone yang dialokasikan untuk tiap seed point sesuai dengan besarnya Lseed.
Langkah-langkah untuk mendapatkan cone, yaitu :
a. Menentukan posisi sudut angular ( ) dari masing-masing pelanggan i yang memiliki
koordinat (xi, yi).
= tan-1 (yi/ xi)
b. Menggeser searah jarum jam untuk menentukan urutan pelanggan yang akan masuk
dalam cone berdasarkan permintaan pelanggan dan Lseed.
c. Pada tiap cone, seed point diletakkan di tengah cone dan koordinat seed point i dihitung
dengan rumus :
= x cos ( )
= x sin ( )
Dimana :
= Jarak antara pelanggan yang paling jauh dari cone dengan DC.
= Sudut yang di bentuk dari penjumlahan sudut pelanggan awal dengan sudut pelanggan
terjauh yang masuk cone dan selanjutnya dibagi 2 .
d. Pembentukan cone kedua dan selanjutnya di mulai dari sudut hasil penyisipan pelanggan
terakhir pada cone sebelumnya.
2. Mengevaluasi biaya penyisipan untuk masing-masing pelanggan
Untuk tiap seed point Sk dan pelanggan i, biaya penyisipan merupakan jarak tambahan yang
akan di tempuh jika pelanggan disisipkan pada sebuah perjalanan dari DC ke seed point dan
kembali ke DC.
c = Dist (DC, i) + Dist (i, ) – Dist (DC, )
3. Menugaskan/mengalokasikan masing-masing pelanggan pada tiap kendaraan/rute
Penugasan pelanggan pada kendaraan/rute diformulasikan menggunakan integer programming
dengan fungsi tujuan meminimasikan biaya penyisipan dan fungsi batasan kapasitas alat angkut.
Variabel Keputusan :
Yik = 1, jika pelanggan i dialokasikan ke alat angkut k, 0 jika sebaliknya.
Formulasi Integer Programing untuk mengalokasikan pelanggan ke alat angkut
Min =

Subject to :

Dimana :
 cik = biaya penyisipan dari pelanggan i dan seed point k
ai = Order size atau permintaan dari pelanggan i
bk = kapasitas dari alat angkut k
4. Menentukan urutan kunjungan pelanggan untuk tiap kendaraan/rute
Tujuan dari tahap ini adalah meminimalkan jarak perjalanan yang harus di tempuh tiap
kendaraan dengan menggunakan metode-metode penentuan urutan kunjungan diantaranya
farthest insert atau nearest insert atau nearest neighbour.

CONTOH KASUS:
Sebuah Distribution Center (DC) yang berada di koordinat (0,0) melayani 5 retail yang
tersebar di beberapa tempat. Data mengenai koordinat dan order size (ukuran pemesanan)
dari masing-masing retail adalah sebagai berikut :
Retail Koordinat X Koordinat Y Order Size
Retail 1 0 12 136
Retail 2 15 3 40
Retail 3 7 15 72
Retail 4 9 12 47
Retail 5 6 5 36

Untuk mengirimkan kelima retail tersebut, DC memiliki 2 truk dengan kapasitas masing-masing
200 unit/truk. Tentukan :
(a) alokasi dari kelima retail pada 2 truk yang ada.
(b) urutan retail yang harus dikunjungi dari setiap rute yang ditempuh truk.

Penyelesaian dengan Metode Saving Matriks :

1. Menentukan matriks jarak
Perhitungan jarak dilakukan dari tiap DC ke masing-masing retail serta dari satu retail ke retail
yang lainnya.
a. Dari DC ke masing-masing retail

Jika dinyatakan pada tabel matriks diperoleh hasil sebagai berikut :

DC Retail 1 Retail 2 Retail 3 Retail 4 Retail 5

Retail 1 12
Retail 2 15,297
Retail 3 16,55
Retail 4 15
Retail 5 7,81

b. dari satu retail ke retail yang lainnya

 Sehingga diperoleh matriks jarak sebagai berikut :

DC Retail 1 Retail 2 Retail 3 Retail 4 Retail 5

Retail 1 12 0
Retail 2 15,297 17,49 0
Retail 3 16,55 7,62 14,42 0
Retail 4 15 9 10,82 3,61 0
Retail 5 7,81 9,22 9,22 10,05 7,62 0

2. Menentukan matriks penghematan

S(R1,R2) = Dist (DC,R1) + Dist (DC,R2) – Dist (R1,R2) = 12 + 15,297 – 17,49 = 9,807.
tambahan catatan :
Dimana angka 9,807 tersebut menyatakan penghematan jarak yang ditempuh sebagai akibat
pengiriman barang untuk retail 1 dan retail 2 dilakukan secara bersamaan dalam satu truk.
Darimana angka tersebut diperoleh ?????
 Jika pengiriman dilakukan sendiri-sendiri maka : DC  Retail 1  DC dimana jarak
yang ditempuh = 12 + 12 dan DC  Retail 2  DC dengan jarak yang ditempuh
15,297 + 15,297 = 30,594 sehingga total jarak yang ditempuh = 54,594.
 Jika pengiriman untuk Retail 1 dan 2 dilakukan bersamaan maka rute menjadi
DC  Retail 1  Retail 2  DC dimana jarak yang ditempuh = 12 + 17,49 + 15,297 =
44,787
 Sehingga total penghematan = 54,594 – 44,787 = 9,807.
Dengan cara yang sama maka hitung :
S(R1,R3) = Dist (DC,R1) + Dist (DC,R3) – Dist (R1,R3) = 12 + 16,55 – 7,62 = 20,93.
S(R1,R4) = Dist (DC,R1) + Dist (DC,R4) – Dist (R1,R4) = 12 + 15 – 9 = 18.
S(R1,R5) = Dist (DC,R1) + Dist (DC,R5) – Dist (R1,R5) = 12 + 7,81 – 9,22 = 10,59.
S(R2,R3) = Dist (DC,R2) + Dist (DC,R3) – Dist (R2,R3) = 15,297 +16,55 – 14,42 = 17,427.
S(R2,R4) = Dist (DC,R2) + Dist (DC,R4) – Dist (R2,R4) = 15,297 +15 – 10,82 = 19,477.
S(R2,R5) = Dist (DC,R2) + Dist (DC,R5) – Dist (R2,R5) = 15,297 +7,81 – 9,22 = 13,887.
S(R3,R4) = Dist (DC,R3) + Dist (DC,R4) – Dist (R3,R4) = 16,55 +15 – 3,61 = 27,94.
S(R3,R5) = Dist (DC,R3) + Dist (DC,R5) – Dist (R3,R5) = 16,55 + 7,81 – 10,05 = 14,31.
S(R4,R5) = Dist (DC,R4) + Dist (DC,R5) – Dist (R4,R5) = 15 +7,81 – 7,62 = 15,19.

Sehingga diperoleh matriks penghematannya adalah :

Retail 1 Retail 2 Retail 3 Retail 4 Retail 5
Retail 1 0
Retail 2 9,807 0
Retail 3 20,93 17,427 0
Retail 4 18 19,477 27,94 0
Retail 5 10,59 13,887 14,31 15,19 0
3. Mengalokasikan masing-masing retail kedalam truk/rute
Iterasi 1 : tiap retail dialokasikan pada rute yang terpisah, sehingga pada iterasi 1 diperoleh lima
rute (yang berarti membutuhkan lima truk yang berbeda untuk mengirimkan barang).
Hasil dari iterasi 1 :

rute Retail 1 Retail 2 Retail 3 Retail 4 Retail 5

Retail 1 1 0
Retail 2 2 9,807 0
Retail 3 3 20,93 17,427 0
Retail 4 4 18 19,477 27,94 0
Retail 5 5 10,59 13,887 14,31 15,19 0

Iterasi 2 : Dari matriks penghematan, diperoleh penghematan tertinggi sebesar 27,94 =

S(R3,R4) dengan mengkombinasikan rute untuk retail 3 dan retail 4 dalam satu rute saja atau
menambahkan retail 4 ke rute dari retail 3. Selanjutnya dilakukan pengecekan apakah
pengkombinasian tersebut layak dilakukan atau tidak, layak dilakukan jika total order size
kurang dari kapasitas truck.
Beban untuk rute 3 = order size retail 3 + retail 4 = 72 + 47 = 119 (<200)  layak
Hasil dari iterasi 2 :

rute Retail 1 Retail 2 Retail 3 Retail 4 Retail 5

Retail 1 1 0
Retail 2 2 9,807 0
Retail 3 3 20,93 17,427 0
Retail 4 3 18 19,477 27,94 0
Retail 5 5 10,59 13,887 14,31 15,19 0

Iterasi 3 : Dari matriks penghematan, diperoleh penghematan tertinggi berikutnya sebesar 20,93
= S(R1,R3) dengan mengkombinasikan rute untuk retail 1 dan 3. Karena dari iterasi
sebelumnya, rute untuk retail 3 sudah tetap yaitu rute 3 maka yang terjadi sama dengan
menambahkan retail 1 ke rute 3. Penambahan dikatakan layak jika total order size dengan
menambahkan order size retail 1 kurang dari kapasitas truck yang ada
Beban untuk rute 3 = order size retail 3 + retail 4 + retail 1 = 72 + 47 + 136 = 255 (> 200) 
tidak layak.

Hasil dari iterasi 3 : tetap sama dengan iterasi 2

rute Retail 1 Retail 2 Retail 3 Retail 4 Retail 5
Retail 1 1 0
Retail 2 2 9,807 0
Retail 3 3 20,93 17,427 0
Retail 4 3 18 19,477 27,94 0
Retail 5 5 10,59 13,887 14,31 15,19 0
Iterasi 4 : Dari matriks penghematan, diperoleh penghematan tertinggi berikutnya sebesar
19,477 = S(R2,R4) dengan jalan menambahkan retail 2 pada rute 3 atau mengkombinasikan
rute 2 dan rute 3. Pengkombinasian layak dilakukan jika total order size dengan menambahkan
order size retail 2 masih kurang dari kapasitas truck.
Beban untuk rute 3 = order size retail 3 + retail 4 + retail 2 = 72 + 47 + 40 = 159 (< 200) 
layak.
Hasil dari iterasi 4 :
rute Retail 1 Retail 2 Retail 3 Retail 4 Retail 5
Retail 1 1 0
Retail 2 3 9,807 0
Retail 3 3 20,93 17,427 0
Retail 4 3 18 19,477 27,94 0
Retail 5 5 10,59 13,887 14,31 15,19 0

Iterasi 5 : Dari matriks penghematan, diperoleh penghematan tertinggi berikutnya sebesar 18 =

S(R1,R4). Sehingga pada tahap ini dilakukan pengecekan apakah retail 1 dapat ditambahkan
pada rute 3.
Beban untuk rute 3 = order size retail 3 + retail 4 + retail 2 + retail 1 = 72 + 47 + 40 + 136 =
295 (> 200)  tidak layak.
Hasil dari iterasi 5 :
rute Retail 1 Retail 2 Retail 3 Retail 4 Retail 5
Retail 1 1 0
Retail 2 3 9,807 0
Retail 3 3 20,93 17,427 0
Retail 4 3 18 19,477 27,94 0
Retail 5 5 10,59 13,887 14,31 15,19 0

Iterasi 6 : Dari matriks penghematan, diperoleh penghematan tertinggi berikutnya sebesar

17,427 = S(R2,R3). Dari iterasi sebelumnya dapat dilihat bahwa retail 2 dan 3 sudah dalam satu
rute.

Iterasi 7 : Dari matriks penghematan, diperoleh penghematan tertinggi berikutnya sebesar 15,19
= S(R4,R5) dengan jalan menambahkan retail 5 pada rute 3 atau mengkombinasikan rute 3 dan
rute 5. Pengkombinasian layak dilakukan jika total order size dengan menambahkan order size
retail 5 masih kurang dari kapasitas truck.
Beban untuk rute 3 = order size retail 3 + retail 4 + retail 2 + retail 5 = 72 + 47 + 40 + 36 =
195 (<200)  layak.

Hasil dari iterasi 7 :

rute Retail 1 Retail 2 Retail 3 Retail 4 Retail 5
Retail 1 1 0
Retail 2 3 9,807 0
Retail 3 3 20,93 17,427 0
Retail 4 3 18 19,477 27,94 0
Retail 5 3 10,59 13,887 14,31 15,19 0
 Sehingga diperoleh dua penugasan kendaraan yaitu : {2,3,4,5} dan {1} yang berarti truk
pertama akan melayani/mengirimkan produk ke retail 2, 3, 4 dan 5 sedangkan truk kedua akan
melayani hanya retail 1 saja.

4. Pengurutan rute pengiriman untuk rute yang terdiri dari retail 2,3,4, dan 5.
Penyelesaian menjadi Travelling Salesman Problem (untuk solusinya lihat pada contoh soal di
materi Travelling Salesman Problem).
Solusi terbentuk dua rute untuk masing-masing kendaraan:
Kendaraan 1: DC-R1-DC dengan jarak = 12 x 2 = 24
Kendaraan 2: DC – R3 – R4 - R2 – R5 – DC dengan jarak = 16,55 + 3,61 + 10,82 + 9,22 + 7,81
= 48,01 (solusi berdasarkan metode nearest insertion)
Total jarak tempuh = 24 + 48,01 = 72,01

Penyelesaian dengan dengan Generalized Assigment

1. Menentukan Lseed
L =

= 165,5 ~ 166
2. Menentukan posisi sudut angular ( ) yang diperoleh dari invers tangen koordinat masing-
masing retail i
Retail Koordinat X Koordinat Y
Retail 1 0 12 1.570796
Retail 2 15 3 0.197396
Retail 3 7 15 1.134169
Retail 4 9 12 0.927295
Retail 5 6 5 0.694738
3. Menggeser searah jarum jam untuk menentukan urutan retail yang akan dikunjungi (dimulai
dari sudut angular terbesar ke terkecil) : R1, R3, R4, R5, R2.
4. Menentukan cone berdasarkan permintaan retail, urutan kunjungan dan Lseed dan selanjutnya
menghitung koordinat seed point di tiap cone.

 Penentuan Cone ke-1 dan koordinat seed pointnya

Iterasi 1 : Menggabungkan order size R1 dan R3
= 136 + 72 = 208 > Lseed (Kesimpulan : tidak dapat digabungkan)
Iterasi 2 : karena besarnya harus sama dengan Lseed, maka untuk tepat sebesar 166 dari R3
hanya diambil = 166 – 136 = 30, sehingga cone ke-1 berada di titik 30/72 dari
sebuah sudut yang terletak antara R1 dan R3 R3
Iterasi 3 : ujung terjauh cone 1 terletak di antara R1 dan R3
Sudut angular R1 (dlm radian) = 1,57 R1
SP

DC
 Sudut angular R3 (dlm radian) = 1,13
Selisih Radian R1 dengan R3 = 1,57 – 1,13 = 0,44
Sudut paling jauh dari cone 1 : 1,57 - x 0,44 = 1,3867

Jadi cone 1 berada pada radian 1,57 dan 1,3867

Iterasi 4 : Penentuan = = 1,47835
= 1,028 x 57,3250
= 84,7460
Iterasi 5 : Penentuan koordinat seed point pada cone 1 :
X1 = dDC-R1 Cos 84,7460 = 12 x 0,09157 = 1,098
Y1 = dDC-R1 Sin 84,7460 = 12 x 0,86 = 12,9 x 0,9957 = 11,949

 Penentuan Cone ke-2 dan koordinat seed pointnya

Iterasi 1 : Cone 2 dimulai dari Radian 1,3867 dan memasukkan sisa order size dari R3 = 72
– 30 = 42. Dengan searah jarum jam, maka ditambahkan muatan/order size R4
sebesar 47. Total muatan = 42 + 47 = 89 < Lseed
Iterasi 2 : Tambahkan order size R5 sehingga total muatan = 89 + 36 = 125 < Lseed
Iterasi 3 : Tambahkan order size R2 sehingga total muatan = 125 + 40 = 165 < Lseed
Iterasi 3 : Seluruh order size retail sudah masuk pada cone 2 dan tidak melebihi L seed. Jadi
cone 2 berada pada radian 1,3867 dan 0,1973 (sudut angular R2)
R3
Iterasi 4 : Penentuan = = 0,792
SP
0
= 0,792 x 57,325
R4
= 45,40140
Iterasi 5 : Penentuan koordinat seed point pada cone 2 :
X1 = dDC-R2 Cos 45,40140= 15,297 x 0,7021 = 10,741 R5
Y1 = dDC-R2 Sin 45,40140= 15,297 x 0,71204 = 12,9 x 0,9957 = 10,892 R2

Diperoleh koordinat seed point pada tiap cone adalah : DC

Seed Point X Y
S1 1,098 11,949
S2 10,741 10,892

5. Hitung biaya penyisipan untuk tiap pelanggan i pada tiap seed point Sk
- Tentukan jarak dari DC ke tiap retail = Dist (DC,i)
DC
Retail 1 12
Retail 2 15,297
Retail 3 16,55
Retail 4 15
Retail 5 7,81
 - Tentukan jarak dari tiap retail ke tiap seed point = Dist (i, Sk)
1,099
16,533
6,644
7,902
8,504
10,798
8,967
5,556
2,063
7,563
- Tentukan jarak dari DC ke tiap seed point = Dist (DC,Sk)
11,99934 = 12
15,29721 = 15,297

Biaya penyisipan tiap retail pada seed point 1

C11 = Dist (DC,R1) + Dist (R1, S1) - Dist (DC,S1) = 12 +1,099 – 12 = 1,099
C21 = Dist (DC,R2) + Dist (R2, S1) - Dist (DC,S1) = 15,297 +16,533 – 12 = 19,83
C31 = Dist (DC,R3) + Dist (R3, S1) - Dist (DC,S1) = 16,55 +6,644 – 12 = 11,194
C41 = Dist (DC,R4) + Dist (R4, S1) - Dist (DC,S1) = 15 +7,902 – 12 = 10,902
C51 = Dist (DC,R5) + Dist (R5, S1) - Dist (DC,S1) = 7,81 +8,504 – 12 = 4,314

Biaya penyisipan tiap retail pada seed point 2

C12 = Dist (DC,R1) + Dist (R1, S2) - Dist (DC,S2) = 12 +10,798 – 15,297 = 7,501
C22 = Dist (DC,R2) + Dist (R2, S2) - Dist (DC,S2) = 15,297 +8,967 – 15,297 = 8,967
C32 = Dist (DC,R3) + Dist (R3, S2) - Dist (DC,S2) = 16,55 + 5,556 – 15,297 = 6,809
C42= Dist (DC,R4) + Dist (R4, S2) - Dist (DC,S2) = 15 + 2,063 – 15,297 = 1,766
C52 = Dist (DC,R5) + Dist (R5, S2) - Dist (DC,S2) = 7,81 +7,563 – 15,297 = 0,076

6. Menugaskan konsumen ke kendaraan/rute

Variabel keputusan :
yik = 1 jika retail ke-i ditugaskan ke kendaraan k , dimana i = 1, 2, 3, 4 dan 5 dan k = 1 dan 2

Formulasi Integer Programming untuk menugaskan retail ke kendaraan

Min z = 1,099 y11 + 19,83 y21 + 11,194 y31 + 10,902 y41 + 4,314 y51 + 7,501 y12 + 8,967 y22 +
6,809 y32 + 1,766 y42 + 0,076 y52
Fungsi pembatas untuk menjamin tiap retailer akan masuk pada satu kendaraan
(1) y11 + y12 = 1
(2) y21 + y22 = 1
(3) y31 + y32 = 1
(4) y41 + y42 = 1
 (5) y51 + y52 = 1
Fungsi pembatas untuk menjamin total muatan tidak melebihi kapasitas kendaraan sebesar 200
(6) 136 y11 + 40 y21 + 72 y31 + 47 y41 + 36 y51 ≤ 200 (untuk kendaraan 1)
(7) 136 y12 + 40 y22 + 72 y32 + 47 y42 + 36 y52 ≤ 200 (untuk kendaraan 2)
(8) y11, y21, ..........y52 = 0 atau 1

Solusi formulasi IP diatas dengan menggunakan bantuan software WinQSB

Dari hasil diatas diperoleh penugasan untuk tiap kendaraan :

- Kendaraan 1 : R1
- Kendaraan 2 : R2, R3, R4, R5
Hasil tersebut sama dengan hasil metode Saving Matrix

7. Menentukan rute kunjungan kendaraan 1 : DC – R1 – DC

8. Menentukan rute kunjungan kendaraan 2 dengan menggunakan metode-metode di TSP (lihat
contoh soal pada TSP sebelumnya).

Penyelesaian dengan Menggunakan file VROUTE yang ada pada folder Samples LINGO
MODEL:

! The Vehicle Routing Problem (VRP);

!************************************;
! WARNING: Runtimes for this model ;
! increase dramatically as the number;
! of cities increase. Formulations ;
! with more than a dozen cities ;
! WILL NOT SOLVE in a reasonable ;
! amount of time! ;
!************************************;

SETS: DC + Retail 1- 5
! Q(I) is the amount required at city I,
U(I) is the accumulated delivers at city I ;
CITY/1..6/: Q, U;

! DIST(I,J) is the distance from city I to city J

X(I,J) is 0-1 variable: It is 1 if some vehicle
travels from city I to J, 0 if none;
CXC( CITY, CITY): DIST, X;
ENDSETS

DATA: inputkan data order size (untuk DC=0)

! city 1 represent the common depo;
Q = 0 136 40 72 47 36;

! distance from city I to city J is same from city

Input matriks
J to city I distance fromjarak
city I to the depot is
0, since the vehicle has to return to the depot;

DIST = ! To City;
! DC R1 R2 R3 R4 R5 From;
0 12 15.297 16.55 15 7.81!DC;
12 0 17.49 7.62 9 9.229!R1;
 15.297 17.49 0 14.42 10.82 9.22!R2;
16.55 7.62 14.42 0 3.61 10.05!R3;
15 9 10.82 3.61 0 7.62!R4;
7.81 9.229 9.22 10.05 7.62 0;!R5;

! VCAP is the capacity of a vehicle ;

VCAP = 200;
ENDDATA

! Minimize total travel distance;

MIN = @SUM( CXC: DIST * X);

! For each city, except depot....;

@FOR( CITY( K)| K #GT# 1:

! a vehicle does not traval inside itself,...;

X( K, K) = 0;

! a vehicle must enter it,... ;

@SUM( CITY( I)| I #NE# K #AND# ( I #EQ# 1 #OR#
Q( I) + Q( K) #LE# VCAP): X( I, K)) = 1;

! a vehicle must leave it after service ;

@SUM( CITY( J)| J #NE# K #AND# ( J #EQ# 1 #OR#
Q( J) + Q( K) #LE# VCAP): X( K, J)) = 1;

! U( K) is at least amount needed at K but can't

exceed capacity;
@BND( Q( K), U( K), VCAP);

! If K follows I, then can bound U( K) - U( I);

@FOR( CITY( I)| I #NE# K #AND# I #NE# 1:
U( K) >= U( I) + Q( K) - VCAP + VCAP *
( X( K, I) + X( I, K)) - ( Q( K) + Q( I))
* X( K, I);
);

! If K is 1st stop, then U( K) = Q( K);

U( K) <= VCAP - ( VCAP - Q( K)) * X( 1, K);

! If K is not 1st stop...;

U( K)>= Q( K)+ @SUM( CITY( I)|
I #GT# 1: Q( I) * X( I, K));
);

! Make the X's binary;

@FOR( CXC: @BIN( X));

! Minimum no. vehicles required, fractional

and rounded;
VEHCLF = @SUM( CITY( I)| I #GT# 1: Q( I))/ VCAP;
VEHCLR = VEHCLF + 1.999 -
@WRAP( VEHCLF - .001, 1);

! Must send enough vehicles out of depot;

@SUM( CITY( J)| J #GT# 1: X( 1, J)) >= VEHCLR;
END

Dari hasil running LINGO diperoleh solusi

Total jarak
Global optimal solution found.
Objective value: 71.58700
Objective bound: 71.58700
Infeasibilities: 0.000000
Extended solver steps: 0
Total solver iterations: 115

Variable Value Reduced Cost

VCAP 200.0000 0.000000
VEHCLF 1.655000 0.000000
VEHCLR 2.000000 0.000000
X( 1, 2) 1.000000 12.00000
X( 1, 6) 1.000000 7.810000
X( 2, 1) 1.000000 12.00000
X( 3, 1) 1.000000 15.29700
X( 4, 5) 1.000000 3.610000
X( 5, 3) 1.000000 10.82000
X( 6, 4) 1.000000 10.05000

Dimana 1 = DC, 2 = R1, 3 = R2 dan seterusnya

Terbentuk dua rute:

 1-2-1 atau DC-R1-DC
 1-6-4-5-3-1 atau DC-R5-R3-R4-R2-DC
Dengan total jarak dari kedua rute = 71,587 (lebih kecil dibanding dengan hasil perhitungan dengan
metode heuristik yang dijelaskan sebelumnya)