PERIODIC VEHICLE ROUTING PROBLEM

1. Pendahuluan
Sebuah perusahaan yang bergerak di bidang pendistribusian melakukan proses
pengiriman pupuk dari gudang penyimpanan ke kios-kios yang berjumlah
sembilan belas. Permintaan pupuk di tiap kios didasarkan pada rencana kebutuhan
petani dengan total permintaan rata-rata sebesar 3954 sak/minggu. Untuk
memenuhi permintaan tersebut, dilakukan pengiriman dengan menggunakan truk
yang berjumlah enam dengan kapasitas 150 sak pupuk/truk. Dengan total
kapasitas kendaraan sebesar 900 sak/hari maka pengiriman pupuk dari gudang
penyimpanan ke kios-kios tidak bisa dilakukan hanya dalam satu hari saja, oleh
karena itu perusahaan harus menentukan jadwal kunjungan dalam memenuhi
permintaan mingguan tiap kios. Perusahaan dapat mengunjungi tiap kios sebanyak
dua kali dalam satu minggu dengan alternatif kombinasi kunjungan adalah hari
senin dan kamis, hari selasa dan jumat atau hari rabu dan sabtu. Selain itu
perusahaan juga dapat mengunjungi tiap kios sebanyak tiga atau enam dalam satu
minggunya. Sehingga problem yang dihadapi perusahaan tersebut, tidak hanya
menentukan rute pengiriman tiap kendaraan tetapi juga menentukan jadwal
kunjungan ke tiap kios.
Permasalahan yang dihadapi perusahaan tersebut dikenal dengan istilah
Periodic Vehicle Routing Problem (PVRP) yang merupakan generalisasi dari
Vehicle Routing Problem (VRP) dengan memperluas rentang perencanaan
pengiriman menjadi t hari dengan konsumen ke-i dikunjungi sebanyak fi kali
dimana 1 ≤ fi ≤ t. VRP hanya melibatkan dua keputusan yaitu menugaskan
sekelompok konsumen yang akan dikunjungi oleh tiap kendaraan dan menentukan
rute kendaraan pada tiap harinya. Sedangkan PVRP lebih kompleks dibandingkan
dengan VRP karena selain dua keputusan tersebut masih ditambah dengan satu
keputusan yaitu memilih jadwal kunjungan ke tiap konsumen dari sekumpulan
alternatif kombinasi kunjungan yang ada.
Aplikasi pengiriman periodik bisa ditemukan pada beberapa area diantaranya
jasa pengiriman, perbaikan dan perawatan elevator, dan pengambilan sampah dari
Tempat Pembuangan Sampah (TPS). PVRP pertama kali dikenalkan oleh
Beltrami dan Bodin pada tahun 1974 dan telah mengalami evolusi yang cukup
signifikan baik dalam model dan metode solusi seperti ditunjukkan pada gambar
1.
 Problem Identification
Beltrami and Bodin (1974)

Formal definition / heuristic solution methods

Russel and Igo (1979)
Christofides and Beasley (1984)

Classical heuristics Metaheuristics Mathematical programming

Tan and Beasley (1984) Chao et al. (1995) based methods
Russel and Gribbin (1991) Cordeau et al. (1997) Francis et al. (2006)
Gaudiosio and Paletta (1992) Drummond et al. (2001) Mourgaya and Vanderbeck (2006)

Sumber: Golden, B., S. Raghavan, dan E. Wasil, 2008

Gambar 1. Evolusi Model dan Metode Solusi untuk PVRP

2. Model Matematis PVRP

Beberapa peneliti telah mengembangkan model matematis untuk PVRP
diantaranya Christofides and Beasley (1984), Tan and Beasley (1984), Cordeau et
al. (1997). Model matematis yang akan dijelaskan disini adalah model 0-1 integer
programming yang dikembangkan oleh Cordeau et al. (1997). Dalam model
tersebut, PVRP bekerja dalam sebuah horison perencanaan t hari dan tiap
konsumen i dilayani dengan frekuensi pengiriman ei dan sekumpulan kombinasi
hari kunjungan yang diijinkan Ci. Sebagai contoh jika ei = 2 dan Ci = {(1,3), (2,4),
(3,5)}, artinya konsumen i harus dikunjungi dua kali selama horison perencanaan
dengan kunjungan dapat dilakukan pada hari kesatu dan ketiga, kedua dan
keempat, atau ketiga dan kelima. Selanjutnya PVRP didefinisikan pada sebuah
multigraph G = (V, A) dimana V = {v0, v1,....., vn} adalah sekumpulan vertex dan
A = { (vi, vj)k,l} adalah sekumpulan arc, dengan k dan l menyatakan kendaraan
dan hari kunjungan. Vertex v0 menyatakan depot dan V\{v0} menunjukkan kota
atau konsumen. Model PVRP diformulasikan sebagai berikut :
Parameter
Cijkl : biaya transportasi dari konsumen i ke j dengan kendaraan ke-k pada
hari ke-l
cijkl : waktu perjalanan dari konsumen i ke j dengan kendaraan ke-k pada
hari ke-l
qi : permintaan/ukuran pengiriman konsumen ke-i
di : waktu pelayanan pada konsumen ke-i
Qk : kapasitas angkut dari kendaraan ke-k
Dk : kapasitas waktu/jam kerja dari kendaraan ke-k
arl : bernilai 1 jika konsumen dikunjungi pada hari ke-l yang sesuai dengan
kombinasi hari kunjungan ke-r
Variabel keputusan
Yir : bernilai 1 jika konsumen ke- i dikunjungi pada kombinasi hari
kunjungan ke-r
 Xijkl : bernilai 1 jika kendaraan ke-k mengunjungi konsumen ke-j setelah
dari konsumen ke-i pada hari ke-l

n n m t
Minimize     C ijkl . X ijkl (1)
i 0 j 0 k 1 l 1
Pembatas :
 yir  1
rCi
( i = 1,…,n); (2)
n m

 X
j 0 k 1
ijkl   arl yir  0
rci
( i = 1,….,n ; l = 1,…,t ) ; (3)
n n

 X ijkl   X hjkl  0
i 0 j 0
( h = 0,…,n ; k = l,…,m; l = 1,…,t); (4)
n

X
j 1
0 jkl 1 ( k = 1,….,m; l = 1,…. t) (5)
n n

 q x
i 0 j 0
i ijkl  Qk ( k = 1,….,m; l = 1,…..t) (6)
n n

 (c
i 0 j 0
ijkl  d i ) xijkl  Dk ( k = 1,….,m; l = 1,…..t) (7)

 x
v j s v js
ijkl  S 1 ( k = 1,….,m; l = 1,…..t) S  V \ {0} ; [S] ≥ 2 ) (8)

xijkl  {0,1} (i = 0,….,n; j = 0,….,n; k = 1,….,m ; l = 1,….,t) (9)

yir {0,1} (i = 1,…,n; r  Ci) (10)

Dengan asumsi qo = 0 dan do = 0

Tujuan dari model PVRP ini adalah untuk meminimalkan total biaya transportasi.
Persamaan (2) merupakan pembatas yang menjamin hanya ada satu kombinasi
hari kunjungan yang ditugaskan pada tiap konsumen. Pembatas pada persamaan
(3) menunjukkan bahwa tiap konsumen hanya akan dikunjungi pada hari yang
sesuai dengan kombinasi hari kunjungan yang telah ditugaskan. Pembatas (4)
menjamin bahwa kedatangan dan kepergian tiap kendaraan pada tiap konsumen
akan berlangsung pada hari yang sama. Persamaan (5) membatasi bahwa tiap
kendaraan berangkat dari depot dan digunakan paling banyak satu kali dalam tiap
harinya. Persamaan (6) membatasi bahwa total permintaan yang akan dikirim
tidak boleh melebihi kapasitas angkut kendaraan sebesar Qk. Persamaan (7)
menunjukkan bahwa total waktu perjalanan dan waktu pelayanan tidak boleh
melebihi kapasitas waktu tiap kendaraan. Persamaan (8) menyatakan pembatas
subtour elimination.

3. Algoritma Heuristik
Menurut Prana (2007), penyelesaian PVRP juga dapat dilihat sebagai ‘multi
level combinatorial optimization problem’ , secara umum langkah – langkah
penyelesaiannya adalah sebagai berikut :
a. Pada tahap pertama, tujuannya adalah untuk menghasilkan sebuah
kelompok berisi kombinasi alternative – alternative solusi untuk tiap
 pelanggan. Contoh, jika rentang perencanaan t = 3 hari atau {d1, d2, d3}
maka kombinasi yang mungkin adalah 0  000; 1  001;2  010;3 
011;4  100;5  101;6  110; dan 7 111. Jika pelanggan menghendaki
dua kali kunjungan, maka pelanggan akan mendapatkan beberapa
alternative bentuk kunjungan {d1, d2}, {d1, d3}, {d2, d3}, atau pilihan 3, 5, 6
dari Tabel 1.
Tabel 1. Kombinasi kunjungan
J. Permintaan Kemungkinan
J. Pelanggan [Link] [Link]
Harian Kombinasi
1 30 1 3 1, 2, 4
2 20 2 3 3, 5, 6
3 20 2 3 3, 5, 6
4 30 2 3 1, 2, 4
5 10 3 1 7

b. Pada tahap kedua, kita harus memilih satu alternative untuk setiap
pelanggan, sehingga batasan harian terpenuhi. Oleh karena itu, kita
harus memilih pelanggan mana yang akan dikunjungi setiap harinya.
c. Pada tahap ketiga, kita harus menyelesaikan VRP untuk tiap harinya
(menggunakan perhitungan dasar VRP).

Metode solusi 2 phase yang diperkenalkan pertama kali oleh Beltrami and
Bodin pada tahun 1974 merupakan metode solusi yang umum digunakan diawal
pengembangan algoritma heuristik untuk PVRP. Saat ini literatur PVRP lebih
fokus pada metode metaheuristik yang terbukti dapat menghindari dari solusi
lokal optimum.

Heuristik Klasik
Awal penelitian tentang PVRP dilakukan oleh Beltrami and Bodin (1974)
untuk menugaskan truk pengangkut dalam pengambilan sampah di kota New
York. Peneliti menggambarkan sebuah situasi dimana lokasi sampah harus
dikunjungi dengan frekuensi yang berbeda. Tiap lokasi sampah atau yang disebut
juga dengan node memiliki 2 tipe : (1) node dengan pengambilan sampah
sebanyak 3 kali dalam satu minggu, dengan 2 jadwal kunjungan yang diijinkan
yaitu MWF (Monday, Wednesday, Friday) dan TRS (Tuesday,
Thursday,saturday) dan (2) node dengan pengambilan sampah sebanyak 6 kali
dalam satu minggu. Dalam papernya, Beltrami and Bodin mempertimbangkan dua
pendekatan untuk menyelesaikan problem PVRP yaitu :
1. Cluster first route second, dengan pendekatan ini dilakukan penugasan
tiap konsumen ke hari kunjungan dan selanjutnya menentukan rute
kunjungan pada tiap harinya.
2. Route first cluster second, membuat rute-rute pengiriman dan kemudian
baru menugaskan rute ke hari kunjungan.
Selanjutnya Russel and Igo (1979) mengusulkan tiga pendekatan heuristik
untuk menyelesaikan problem PVRP :
1. Heuristik 1 : Menugaskan tiap konsumen ke hari kunjungan dengan
sebuah algoritma klaster, dimana klaster untuk tiap hari terbentuk dari
 konsume-konsumen dengan kombinasi kunjungan satu kali dalam satu
minggu. Setelah dilakukan penugasan konsumen ke hari kunjungan
dilakukan penentuan rute kendaraan dengan menggunakan algoritma
MTOUR.
2. Heuristik 2 : memperbaiki solusi yang diperoleh dari heuristik 1 dengan
memodifikasi algoritma MTOUR yang dikembangkan oleh Russel (1977).
3. Heuristik 3: memodifikasi algoritma Clarke and Wright/Saving Approach
yang merupakan algoritma untuk menyelesaikan permasalahan rute
kendaraan dengan rentang satu hari.
Christofides and Beasley (1984) mengembangkan algoritma PVRP yang
didasarkan pada pemilihan awal dari kombinasi hari pengiriman untuk konsumen
dan selanjutnya diikuti dengan pertukaran kombinasi hari pengiriman untuk
meminimalkan total biaya distribusi yang dihasilkan dari VRP. Untuk
mengevaluasi efek dari pertukaran hari kunjungan tersebut, membutuhkan
perhitungan yang kompleks untuk menyelesaikan kembali (resolving) penentuan
rute kendaraan pada tiap harinya dengan VRP. Dalam penelitian tersebut,
Christofides and Beasley menggunakan alternatif lain untuk mengevaluasi
pertukaran hari tersebut dengan menggantikan VRP dengan (1) prblem median
dan (2) Travelling Salesman Problem (TSP). Sedangkan Tan and Beasley (1984)
mengembangkan sebuah algoritma heuristik untuk PVRP didasarkan pada
algoritma VRP yang dikembangkan oleh Fisher and Jaikumar pada tahun 1981
yaitu algoritma Generalized Assignment.

Metaheuristics
Chao et al. (1995) membuat metode metaheuristic yang spesifik untuk
penyelesaian PVRP. Metode ini menghasilkan solusi awal yang layak untuk
PVRP dan secara iterasi melakukan langkah perbaikan menuju solusi optimal.
Solusi awal yang layak diperoleh dengan formulasi dari Christofides dan Beasley
(1984). Mereka menyelesaikan relaksasi linear terhadap problem penugasan node
ke hari pengiriman, dengan memiminalkan beban yang dibawa pada setiap
harinya. Meskipun solusinya tidak layak secara kapasitas, tetapi masih berguna
sebagai titik awal pencarian. Pada tahap metaheuristik berikutnya, peneliti
menggunakan konsep jadwal yang layak (mendefinisikan kumpulan spesifik node
yang layak Si) seperti yang ada di kebanyakan literatur PVRP. Kemudian langkah
perbaikan dilakukan untuk memperbaiki solusi dengan memindahkan sebuah node
dari satu jadwal ke jadwal yang lain. Jika sebuah perpindahan valid untuk node
tertentu (misalnya memindah node i dari jadwal s sehingga s  Si) dan jika
perpindahan tersebut mengurangi jarak total, maka perpindahan tersebut akan
langsung diterima. Jika ada penambahan jarak total, maka perpindahan tersebut
diterima jika penambahannya masih dalam batas tertentu. Jika tidak memenuhi
syarat maka node tidak akan dipindah dari lokasi awalnya. Proses ini diteruskan
dengan batasan yang terus dikurangi. Iterasi dihentikan jika tidak ada lagi
perpindahan yang mungkin dilakukan yang menghasikan penghematan biaya.
Chao et al. (1995) juga menjelaskan metode untuk meningkatkan heuristik ini
melalui relaksasi kapasitas dan pemrosesan setelahnya.
Cordeau et al. (1997) memperkenalkan metode Tabu search untuk
menyelesaikan beberapa problem rute yang berbeda, termasuk PVRP. Metode
Tabu search sudah dimodifikasi dengan menggunakan teknik penambahan dan
 perbaikan rute yang dibuat oleh peneliti; meskipun begitu tidak ada perubahan
yang cukup besar pada inti teknik Tabu search yang spesifik untuk PVRP. Fungsi
tujuannya adalah bobot kombinasi dari biaya perjalanan dan penalti untuk
kelebihan beban (sehingga solusi sementara mungkin akan melanggar batasan
kapasitas dan waktu). Metode tersebut dimulai dari solusi layak dan secara iterasi
bereksperimen dengan perpindahan (penambahan node pada jadwal yang
berbeda). Proses penambahan yang digunakan adalah prosedur GENI
(penambahan dengan biaya paling kecil) dari Gendreau et al. (1994). Prosedur
GENI juga dapat diaplikasikan untuk memilih node yang akan dikeluarkan dari
rutenya. Tidak diperlukan optimisasi ulang tur karena 4 pilihan modifikasi rute
sudah termasuk dalam prosedur GENI. Neighborhood dari perpindahan-
perpindahan yang mungkin adalah kumpulan seluruh solusi yang diperoleh
dengan memindahan konsumen i ke rute yang lain dan ke jadwal mana saja yang
termasuk dalam kumpulan layak Si. Awalnya metode tersebut memperbolehkan
beberapa perpindahan yang tidak layak yang dapat melanggar batasan kapasitas
dan durasi rute.
Dalam rangka memperluas pencarian ruang solusi, peneliti melakukan
pemecahan tahapan Tabu search. Tahapan ini menyebabkan tambahan penalti
pada nilai obyektif solusi yang berisi perpindahan-perpindahan yang sering
dilakukan. Peneliti tidak menggunakan tahapan penekanan akhir yang melakukan
pencarian secara detil dari neighborhood solusi-solusi terbaik yang diketahui.
Secara keseluruhan, metode ini diketahui dapat menghasilkan solusi yang baik
untuk PVRP, meningkatkan atau menghasilkan hasil yang dapat dibandingkan
dengan Chao et al. (1995).

4. Studi Kasus untuk PVRP

PT. X merupakan salah satu distributor elpiji didaerah Malang. Tabel 2
menunjukkan permintaan elpiji per minggu pada tiap agen. Selanjutnya
perusahaan memiliki 4 alternatif frekuensi kunjungan dalam 1 minggunya, seperti
ditunjukkan pada Tabel 3.

Tabel 2. Permintaan Elpiji di Tiap Kios (tabung/minggu) dan Jumlah Pengiriman

Total Demand Jumlah Pengiriman* (qi)

Kode Agen Nama Agen
per minggu (Di) fi =1 fi = 2 fi = 3 fi = 6
1 Toko Asung 50 50 25 17 9
2 Herve Mulyono 32 32 16 11 6
3 Rejo Turen 50 50 25 17 9
4 Bu Yani 50 50 25 17 9
5 Toko Dilarama 24 24 12 8 4
6 Toko Murni 12 12 6 4 2
Total 218 218 109 74 39

Di
* Jumlah Pengiriman diperoleh dengan menggunakan rumus : qi 
fi
Tabel 3. Frekuensi kunjungan
Frekuensi kunjungan (fi) Kombinasi hari
 1 {1} /{ 2} /{3}/{ 4}/{ 5} / {6}
2 {1,4}atau{2,5}atau {3,6}
3 {1,3,5}atau {2,4,6}
6 {1,2,3,4,5,6}

Tabel 4 dan 5 menunjukkan jarak dan waktu perjalanan yang dibutuhkan

kendaraan untuk mengirimkan elpiji dari gudang perusahaan ke tiap agen dan
antar agen.

Tabel 4. Matrik Jarak antar Agen (km)

No Node Gudang 1 2 3 4 5 6
0 Gudang 0 37.6 27.8 26.1 31.2 12.1 35.8
1 Toko Asung 0 7.5 9.2 5.7 23.2 0.7
2 Herve Mulyono 0 1.7 5.1 15.7 9.7
3 Rejo Turen 0 6.8 13 11.47
4 Bu Yani 0 20.8 4.6
5 Toko Dilarama 0 24.4
6 Toko Murni 0

Tabel 5. Matrik Waktu Perjalanan (Travelling Time) dalam menit

No Nama Agen Gudang 1 2 3 4 5 6

0 Gudang 0 56.4 41.7 39.15 46.8 18.15 53.7
1 Toko Asung 0 11.25 13.8 8.55 34.8 1.05
2 Herve Mulyono 0 2.55 7.65 23.55 14.55
3 Rejo Turen 0 10.2 19.5 17.205
4 Bu Yani 0 31.2 6.9
5 Toko Dilarama 0 36.6
6 Toko Murni 0

Selanjutnya biaya transportasi (dalam hal ini biaya bahan bakar) yang diperlukan
untuk melakukan pengiriman ditunjukkan pada tabel 6.

Tabel 6. Matriks Biaya Transportasi (rupiah)

No Nama Agen Gudang 1 2 3 4 5 6

0 Gudang 0 28200 20850 19575 23400 9075 26850
1 Toko Asung 0 5625 6900 4275 17400 525
2 Herve Mulyono 0 1275 3825 11775 7275
3 Rejo Turen 0 5100 9750 8602.5
4 Bu Yani 0 15600 3450
5 Toko Dilarama 0 18300
6 Toko Murni 0
Selanjutnya waktu pelayanan dapat diperkirakan berdasarkan aktivitas bongkar
muat elpiji di masing-masing agen seperti ditunjukkan pada Tabel 7.

Tabel 7. Waktu pelayanan di tiap agen sesuai dengan frekuensi

Waktu Pelayanan (menit)
No. Nama Agen
fi =1 fi = 2 fi = 3 fi = 6
1 Toko Asung 20 9 7 5
2 Herve Mulyono 15 7 5 3
3 Rejo Turen 20 8 7 5
4 Bu Yani 20 8 7 5
5 Toko Dilarama 15 5 4 3
6 Toko Murni 6 4 3 2

Saat ini perusahaan memiliki 2 kendaraan dengan kapasitas angkut sebanyak 50

tabung dan jam kerja selama 5 jam. Tentukan solusi jadwal dan rute kunjungan
untuk keenam agen tersebut.

Penyelesaian Menggunakan Model Matematis yang Dikembangkan oleh

Cordeau et al. (1997) dengan Bantuan Software LINGO

Langkah pertama adalah menterjemahkan persamaan 1 sampai 10 diterjemahkan

ke dalam bahasa LINGO dan menginputkan data-data berdasarkan Tabel 2 – 7.
Model LINGO untuk penyelesaian PVRP pada frekuensi kunjungan sebanyak 2
adlah sebagai berikut.
MODEL:
!Periodic Vehicle routing problem (PVRP) for f =2;

SETS:
CUSTOMER/GDG Asung Herve Rejo Yani Dila_R Murni/: QUANTITY,
SERVICE_TIME;
VEHICLE /1 2/: CAPACITY,CAP_TIME;
DAY / 1 2 3 4 5 6 /;
COMB/1 2 3 /;
OBJECTS(CUSTOMER,CUSTOMER,VEHICLE,DAY): X;
ROUTES(CUSTOMER,CUSTOMER):COST,TRAVELLING_TIME ;
CUSTOMER_D(CUSTOMER,DAY);
CUSTOMER_C(CUSTOMER,COMB):Y;
VEHICLE_D (VEHICLE,DAY);
JOIN(CUSTOMER,VEHICLE,DAY);
CUSTOMER_V(CUSTOMER,VEHICLE);
COMB_DAY(COMB,DAY):A;

ENDSETS

DATA:
TRAVELLING_TIME =! To Agen;
!0 1 2 3 4 5 6 From;
0 56.4 41.7 39.15 46.8 18.15 53.7 ! 0;
56.4 0.00 11.25 13.8 8.55 34.8 1.05 ! 1;
41.7 11.25 0.00 2.55 7.65 23.55 14.55 ! 2;
39.15 13.8 2.55 0.00 10.2 19.5 17.205 ! 3;
46.8 8.55 7.65 10.2 0.00 31.2 6.9 ! 4;
18.15 34.8 23.55 19.5 31.2 0.00 36.6 ! 5;
53.7 1.05 14.55 17.205 6.9 36.6 0.00 ! 6;;

COST = !To Agen;

!0 1 2 3 4 5 6 From;
0 28200 20850 19575 23400 9075 26850 ! 0;
28200 0 5625 6900 4275 17400 525 ! 1;
20850 5625 0 1275 3825 11775 7275 ! 2;
19575 6900 1275 0 5100 9750 8602.5 ! 3;
23400 4275 3825 5100 0 15600 3450 ! 4;
9075 17400 11775 9750 15600 0 18300 ! 5;
26850 525 7275 8602.5 3450 18300 0 ! 6;;

CAPACITY = 50 50;
CAP_TIME = 300 300;
SERVICE_TIME = 0 9 7 8 8 5 4;
QUANTITY = 0 25 16 25 25 12 6;

A =
1 0 0 1 0 0
0 1 0 0 1 0
0 0 1 0 0 1;

Catatan untuk penentuan A

Pada frekuensi sama dengan 2 maka tiap agen akan dikunjungi 2 kali dalam waktu 6 hari
sehingga diperoleh 3 kombinasi hari kunjungan yang bisa dinyatakan dengan:

Kombinasi/hari 1 2 3 4 5 6
1  - -  - -
2 -  - -  -
3 - -  - - 

END DATA
!Fungsi Tujuan;
MIN = @SUM (OBJECTS(I,J,K,L)|I#NE#J :COST(I,J)*X(I,J,K,L));

!Batasan terkait kombinasi hari kunjungan;

@FOR (CUSTOMER(I)|I #EQ# 1:
@SUM(COMB(R):Y(I,R))<= 3);
@FOR (CUSTOMER(I)|I #GT# 1:
@SUM(COMB(R):Y(I,R))= 1);
@FOR(CUSTOMER_D(I,L)|I #GE# 1:
@SUM(CUSTOMER_V(J,K)|J #GE#1 #AND#J #NE# I:X(I,J,K,L))-
@SUM(COMB(R):A(R,L)*Y(I,R))=0);
@FOR(JOIN(H,K,L)|H #GE# 1:
@SUM(CUSTOMER(I)| I #NE# H :X(I,H,K,L))-@SUM(CUSTOMER(J)| J #NE# H
:X(H,J,K,L))=0);
@FOR(JOIN(H,K,L)|H #EQ# 1:
@SUM(CUSTOMER(J)|J #GT# 1 #AND# (H #NE# J):X(H,J,K,L))<=1);

!Batasan Kapasitas angkut kendaraan;

@FOR(VEHICLE_D(K,L):
@SUM(ROUTES(I,J)|I #NE# J:QUANTITY(I)*X(I,J,K,L))<=CAPACITY(K));

!Batasan kapasitas waktu kendaraan;

@FOR(VEHICLE_D(K,L):
@SUM(ROUTES(I,J)|I #NE#
J:(TRAVELLING_TIME(I,J)+SERVICE_TIME(I))*X(I,J,K,L))<=CAP_TIME(K));

!Subtour elimination,mengenumerasi seluruh subset;

!{2,3},{2,4},{2,5},{2,6},{2,7},{3,4},{3,5},{3,6},{3,7},{4,5},
{4,6},{4,7},{5,6},{5,7},{6,7};
@FOR(VEHICLE_D(K,L):
X(2,3,K,L)+X(3,2,K,L)<=1;
X(2,4,K,L)+X(4,2,K,L)<=1;
X(2,5,K,L)+X(5,2,K,L)<=1;
X(2,6,K,L)+X(6,2,K,L)<=1;
X(2,7,K,L)+X(7,2,K,L)<=1;
X(3,4,K,L)+X(4,3,K,L)<=1;
X(3,5,K,L)+X(5,3,K,L)<=1;
X(3,6,K,L)+X(6,3,K,L)<=1;
X(3,7,K,L)+X(7,3,K,L)<=1;
X(4,5,K,L)+X(5,4,K,L)<=1;
X(4,6,K,L)+X(6,4,K,L)<=1;
X(4,7,K,L)+X(7,4,K,L)<=1;
X(5,6,K,L)+X(6,5,K,L)<=1;
X(5,7,K,L)+X(7,5,K,L)<=1;
X(6,7,K,L)+X(7,6,K,L)<=1;
X(2,3,K,L)+X(3,2,K,L)+X(2,4,K,L)+X(4,2,K,L)+X(3,4,K,L)+X(4,3,K,L)<=2;
X(2,3,K,L)+X(3,2,K,L)+X(2,5,K,L)+X(5,2,K,L)+X(3,5,K,L)+X(5,3,K,L)<=2;
X(2,3,K,L)+X(3,2,K,L)+X(2,6,K,L)+X(6,2,K,L)+X(3,6,K,L)+X(6,3,K,L)<=2;
X(2,3,K,L)+X(3,2,K,L)+X(2,7,K,L)+X(7,2,K,L)+X(3,7,K,L)+X(7,3,K,L)<=2;
X(2,4,K,L)+X(4,2,K,L)+X(2,5,K,L)+X(5,2,K,L)+X(4,5,K,L)+X(5,4,K,L)<=2;
X(2,4,K,L)+X(4,2,K,L)+X(2,6,K,L)+X(6,2,K,L)+X(4,6,K,L)+X(6,4,K,L)<=2;
X(2,4,K,L)+X(4,2,K,L)+X(2,7,K,L)+X(7,2,K,L)+X(4,7,K,L)+X(7,4,K,L)<=2;
X(2,5,K,L)+X(5,2,K,L)+X(2,6,K,L)+X(6,2,K,L)+X(5,6,K,L)+X(6,5,K,L)<=2;
X(2,5,K,L)+X(5,2,K,L)+X(2,7,K,L)+X(7,2,K,L)+X(5,7,K,L)+X(7,5,K,L)<=2;
X(2,6,K,L)+X(6,2,K,L)+X(2,7,K,L)+X(7,2,K,L)+X(6,7,K,L)+X(7,6,K,L)<=2;
X(3,4,K,L)+X(4,3,K,L)+X(3,5,K,L)+X(5,3,K,L)+X(4,5,K,L)+X(5,4,K,L)<=2;
X(3,4,K,L)+X(4,3,K,L)+X(3,6,K,L)+X(6,3,K,L)+X(4,6,K,L)+X(6,4,K,L)<=2;
X(3,4,K,L)+X(4,3,K,L)+X(3,7,K,L)+X(7,3,K,L)+X(4,7,K,L)+X(7,4,K,L)<=2;
X(3,5,K,L)+X(5,3,K,L)+X(3,6,K,L)+X(6,3,K,L)+X(5,6,K,L)+X(6,5,K,L)<=2;
X(3,5,K,L)+X(5,3,K,L)+X(3,7,K,L)+X(7,3,K,L)+X(5,7,K,L)+X(7,5,K,L)<=2;
X(3,6,K,L)+X(6,3,K,L)+X(3,7,K,L)+X(7,3,K,L)+X(6,7,K,L)+X(7,6,K,L)<=2;
X(4,5,K,L)+X(5,4,K,L)+X(4,6,K,L)+X(6,4,K,L)+X(5,6,K,L)+X(6,5,K,L)<=2;
X(4,5,K,L)+X(5,4,K,L)+X(4,7,K,L)+X(7,4,K,L)+X(5,7,K,L)+X(7,5,K,L)<=2;
X(4,6,K,L)+X(6,4,K,L)+X(4,7,K,L)+X(7,4,K,L)+X(6,7,K,L)+X(7,6,K,L)<=2;
X(5,6,K,L)+X(6,5,K,L)+X(5,7,K,L)+X(7,5,K,L)+X(6,7,K,L)+X(7,6,K,L)<=2;
X(2,3,K,L)+X(3,2,K,L)+X(2,4,K,L)+X(4,2,K,L)+X(2,5,K,L)+X(5,2,K,L)+X(3,4,K
,L)+X(4,3,K,L)+X(3,5,K,L)+X(5,3,K,L)+X(4,5,K,L)+X(5,4,K,L)<=3;
X(2,3,K,L)+X(3,2,K,L)+X(2,4,K,L)+X(4,2,K,L)+X(2,6,K,L)+X(6,2,K,L)+X(3,4,K
,L)+X(4,3,K,L)+X(3,6,K,L)+X(6,3,K,L)+X(4,6,K,L)+X(6,4,K,L)<=3;
X(2,3,K,L)+X(3,2,K,L)+X(2,4,K,L)+X(4,2,K,L)+X(2,7,K,L)+X(7,2,K,L)+X(3,4,K
,L)+X(4,3,K,L)+X(3,7,K,L)+X(7,3,K,L)+X(4,7,K,L)+X(7,4,K,L)<=3;
X(2,3,K,L)+X(3,2,K,L)+X(2,5,K,L)+X(5,2,K,L)+X(2,6,K,L)+X(6,2,K,L)+X(3,5,K
,L)+X(5,3,K,L)+X(3,6,K,L)+X(6,3,K,L)+X(5,6,K,L)+X(6,5,K,L)<=3;
X(2,3,K,L)+X(3,2,K,L)+X(2,5,K,L)+X(5,2,K,L)+X(2,7,K,L)+X(7,2,K,L)+X(3,5,K
,L)+X(5,3,K,L)+X(3,7,K,L)+X(7,3,K,L)+X(5,7,K,L)+X(7,5,K,L)<=3;
X(2,3,K,L)+X(3,2,K,L)+X(2,6,K,L)+X(6,2,K,L)+X(2,7,K,L)+X(7,2,K,L)+X(3,6,K
,L)+X(6,3,K,L)+X(3,7,K,L)+X(7,3,K,L)+X(6,7,K,L)+X(7,6,K,L)<=3;
X(2,4,K,L)+X(4,2,K,L)+X(2,5,K,L)+X(5,2,K,L)+X(2,6,K,L)+X(6,2,K,L)+X(4,5,K
,L)+X(5,4,K,L)+X(4,6,K,L)+X(6,4,K,L)+X(5,6,K,L)+X(6,5,K,L)<=3;
X(2,4,K,L)+X(4,2,K,L)+X(2,5,K,L)+X(5,2,K,L)+X(2,7,K,L)+X(7,2,K,L)+X(4,5,K
,L)+X(5,4,K,L)+X(4,7,K,L)+X(7,4,K,L)+X(5,7,K,L)+X(7,5,K,L)<=3;
X(2,4,K,L)+X(4,2,K,L)+X(2,6,K,L)+X(6,2,K,L)+X(2,7,K,L)+X(7,2,K,L)+X(4,6,K
,L)+X(6,4,K,L)+X(4,7,K,L)+X(7,4,K,L)+X(6,7,K,L)+X(7,6,K,L)<=3;
X(2,5,K,L)+X(5,2,K,L)+X(2,6,K,L)+X(6,2,K,L)+X(2,7,K,L)+X(7,2,K,L)+X(5,6,K
,L)+X(6,5,K,L)+X(5,7,K,L)+X(7,5,K,L)+X(6,7,K,L)+X(7,6,K,L)<=3;
X(3,4,K,L)+X(4,3,K,L)+X(3,5,K,L)+X(5,3,K,L)+X(3,6,K,L)+X(6,3,K,L)+X(4,5,K
,L)+X(5,4,K,L)+X(4,6,K,L)+X(6,4,K,L)+X(5,6,K,L)+X(6,5,K,L)<=3;
X(3,4,K,L)+X(4,3,K,L)+X(3,5,K,L)+X(5,3,K,L)+X(3,7,K,L)+X(7,3,K,L)+X(4,5,K
,L)+X(5,4,K,L)+X(4,7,K,L)+X(7,4,K,L)+X(5,7,K,L)+X(7,5,K,L)<=3;
X(3,4,K,L)+X(4,3,K,L)+X(3,6,K,L)+X(6,3,K,L)+X(3,7,K,L)+X(7,3,K,L)+X(4,6,K
,L)+X(6,4,K,L)+X(4,7,K,L)+X(7,4,K,L)+X(6,7,K,L)+X(7,6,K,L)<=3;
X(3,5,K,L)+X(5,3,K,L)+X(3,6,K,L)+X(6,3,K,L)+X(3,7,K,L)+X(7,3,K,L)+X(5,6,K
,L)+X(6,5,K,L)+X(5,7,K,L)+X(7,5,K,L)+X(6,7,K,L)+X(7,6,K,L)<=3;
X(4,5,K,L)+X(5,4,K,L)+X(4,6,K,L)+X(6,4,K,L)+X(4,7,K,L)+X(7,4,K,L)+X(5,6,K
,L)+X(6,5,K,L)+X(5,7,K,L)+X(7,5,K,L)+X(6,7,K,L)+X(7,6,K,L)<=3;
X(2,3,K,L)+X(3,2,K,L)+X(2,4,K,L)+X(4,2,K,L)+X(2,5,K,L)+X(5,2,K,L)+X(2,6,K
,L)+X(6,2,K,L)+X(3,4,K,L)+X(4,3,K,L)+X(3,5,K,L)+X(5,3,K,L)+X(3,6,K,L)+X(6
,3,K,L)+X(4,5,K,L)+X(5,4,K,L)+X(4,6,K,L)+X(6,4,K,L)+X(5,6,K,L)+X(6,5,K,L)
<=4;
X(2,3,K,L)+X(3,2,K,L)+X(2,4,K,L)+X(4,2,K,L)+X(2,5,K,L)+X(5,2,K,L)+X(2,7,K
,L)+X(7,2,K,L)+X(3,4,K,L)+X(4,3,K,L)+X(3,5,K,L)+X(5,3,K,L)+X(3,7,K,L)+X(7
,3,K,L)+X(4,5,K,L)+X(5,4,K,L)+X(4,7,K,L)+X(7,4,K,L)+X(5,7,K,L)+X(7,5,K,L)
<=4;
X(2,3,K,L)+X(3,2,K,L)+X(2,4,K,L)+X(4,2,K,L)+X(2,6,K,L)+X(6,2,K,L)+X(2,7,K
,L)+X(7,2,K,L)+X(3,4,K,L)+X(4,3,K,L)+X(3,6,K,L)+X(6,3,K,L)+X(3,7,K,L)+X(7
,3,K,L)+X(4,6,K,L)+X(6,4,K,L)+X(4,7,K,L)+X(7,4,K,L)+X(6,7,K,L)+X(7,6,K,L)
<=4;
X(2,3,K,L)+X(3,2,K,L)+X(2,5,K,L)+X(5,2,K,L)+X(2,6,K,L)+X(6,2,K,L)+X(2,7,K
,L)+X(7,2,K,L)+X(3,5,K,L)+X(5,3,K,L)+X(3,6,K,L)+X(6,3,K,L)+X(3,7,K,L)+X(7
,3,K,L)+X(5,6,K,L)+X(6,5,K,L)+X(5,7,K,L)+X(7,5,K,L)+X(6,7,K,L)+X(7,6,K,L)
<=4;
X(2,4,K,L)+X(4,2,K,L)+X(2,5,K,L)+X(5,2,K,L)+X(2,6,K,L)+X(6,2,K,L)+X(2,7,K
,L)+X(7,2,K,L)+X(4,5,K,L)+X(5,4,K,L)+X(4,6,K,L)+X(6,4,K,L)+X(4,7,K,L)+X(7
,4,K,L)+X(5,6,K,L)+X(6,5,K,L)+X(5,7,K,L)+X(7,5,K,L)+X(6,7,K,L)+X(7,6,K,L)
<=4;
X(3,4,K,L)+X(4,3,K,L)+X(3,5,K,L)+X(5,3,K,L)+X(3,6,K,L)+X(6,3,K,L)+X(3,7,K
,L)+X(7,2,K,L)+X(4,5,K,L)+X(5,4,K,L)+X(4,6,K,L)+X(6,4,K,L)+X(4,7,K,L)+X(7
,4,K,L)+X(5,6,K,L)+X(6,5,K,L)+X(5,7,K,L)+X(7,5,K,L)+X(6,7,K,L)+X(7,6,K,L)
<=4;
X(2,3,K,L)+X(3,2,K,L)+X(2,4,K,L)+X(4,2,K,L)+X(2,5,K,L)+X(5,2,K,L)+X(2,6,K
,L)+X(6,2,K,L)+X(2,7,K,L)+X(7,2,K,L)+X(3,4,K,L)+X(4,3,K,L)+X(3,5,K,L)+X(5
,3,K,L)+X(3,6,K,L)+X(6,3,K,L)+X(3,7,K,L)+X(7,3,K,L)+X(4,5,K,L)+X(5,4,K,L)
+X(4,6,K,L)+x(6,4,K,L)+X(4,7,K,L)+X(7,4,K,L)+X(5,6,K,L)+X(6,5,K,L)+X(5,7,
K,L)+X(7,5,K,L)+X(6,7,K,L)+X(7,6,K,L)<=5;
);

!kendala biner untuk variabel keputusan;

@FOR(OBJECTS(I,J,K,L):
@BIN(X(I,J,K,L)));
@FOR(CUSTOMER_C(I,R):
@BIN(Y(I,R)));
END

Model matematis PVRP pada frekuensi 2 x kunjungan dalam seminggu, 2

kendaraan dan 6 agen ternyata menghasilkan model yang kompleks karena
melibatkan 609 variabel keputusan yang bernilai biner (1 atau 0) dan 854
pembatas. Running Model dengan menggunakan Software LINGO belum
mencapai solusi global optimal sampai menit ke-28 dan diputuskan untuk di-
interrupt, sehingga solusi yang diperoleh menjadi sub optimal, seperti ditunjukkan
berikut ini:
Feasible solution found.
Objective value: 240150.0
Objective bound: 152317.5
Infeasibilities: 0.000000
Extended solver steps: 33628
Total solver iterations: 3715089

Variable Value Reduced Cost

X( GDG, REJO, 1, 1) 1.000000 19575.00

X( GDG, REJO, 1, 4) 1.000000 19575.00
X( GDG, DILA_R, 1, 2) 1.000000 9075.000
X( GDG, DILA_R, 1, 5) 1.000000 9075.000
X( GDG, MURNI, 1, 3) 1.000000 26850.00
X( GDG, MURNI, 2, 6) 1.000000 26850.00
X( ASUNG, HERVE, 1, 3) 1.000000 5625.000
X( ASUNG, HERVE, 2, 6) 1.000000 5625.000
X( HERVE, GDG, 1, 3) 1.000000 20850.00
X( HERVE, GDG, 2, 6) 1.000000 20850.00
X( REJO, YANI, 1, 1) 1.000000 5100.000
X( REJO, YANI, 1, 4) 1.000000 5100.000
X( YANI, GDG, 1, 1) 1.000000 23400.00
X( YANI, GDG, 1, 4) 1.000000 23400.00
X( DILA_R, GDG, 1, 2) 1.000000 9075.000
X( DILA_R, GDG, 1, 5) 1.000000 9075.000
X( MURNI, ASUNG, 1, 3) 1.000000 525.0000
X( MURNI, ASUNG, 2, 6) 1.000000 525.0000
Y( GDG, 1) 1.000000 0.000000
Y( GDG, 2) 1.000000 0.000000
Y( GDG, 3) 1.000000 0.000000
Y( ASUNG, 3) 1.000000 0.000000
Y( HERVE, 3) 1.000000 0.000000
Y( REJO, 1) 1.000000 0.000000
Y( YANI, 1) 1.000000 0.000000
Y( DILA_R, 2) 1.000000 0.000000
Y( MURNI, 3) 1.000000 0.000000

Dari solusi Y(I,R) diperoleh kesimpulan bahwa kombinasi hari kunjungan untuk
masing-masing agen adalah:
Kombinasi 1 (Hari ke-1 dan 4) : Toko Rejo Turen dan Bu Yani
Kombinasi 2 (Hari ke-2 dan ke-5) : Toko Dilarama
Kombinasi 3 (Hari ke-3 dan ke-6) : Toko Asung, Herve Mulyono dan Murni

Sedangkan rute masing-masing kendaraan per hari pada frekuensi kunjungan 2

kali seminggu diperoleh sebagai berikut:

Hari Kendaraan Rute Total Jarak (km)

1 1 Gudang – Rejo Turen – Yani - 26,1+6,8+31,2 =
Gudang 64,1
2 1 Gudang – Dilarama - Gudang 24,2
3 1 Gudang – Murni – Asung – Herve - 35,8+0,7+7,5+27,8=
Gudang 71,8
4 1 Gudang – Rejo Turen – Yani - 64,1
Gudang
5 1 Gudang – Dilarama - Gudang 24,2
6 2 Gudang – Murni – Asung – Herve - 71,8
Gudang

Total biaya transportasi = Rp 240.150/minggu

Total jarak = 320,2 km/minggu

Solusi jadwal dan rute kunjungan pada frekuensi 1 kali kunjungan (dari running
diperoleh kondisi global optimum) adalah sebagai berikut:

Hari Kendaraan Rute Total Jarak (km)

1 1 Gudang – Yani - Gudang 41,6
2 1 Gudang – Asung - Gudang 75,2
3 1 Gudang – Rejo - Gudang 52,1
4 1 Gudang – Dilarama - Gudang 24,2
5 1 Gudang – Herve – Murni - Gudang 27,8+9,7+35,8=73,3
6 - - -

Total biaya transportasi = Rp 215.475/minggu

Total jarak = 266,4 km/minggu

Solusi jadwal dan rute kunjungan pada frekuensi 3 kali kunjungan (dari running
diperoleh kondisi global optimum) adalah sebagai berikut:

Hari Kendaraan Rute Total Jarak (km)

1 2 Gudang – Rejo – Dilarama - 26,1+13+12,1=51,2
Gudang
2 1 Gudang – Yani – Murni – 31,2+4,6+0,7+7,5+27,8
Asung – Herve - Gudang =71,8
3 1 Gudang – Dilarama – Rejo - 12,1+13+26,1=51,2
Gudang
4 1 Gudang – Yani – Murni – 31,2+4,6+0,7+7,5+27,8
 Asung – Herve - Gudang =71,8
5 1 Gudang – Dilarama – Rejo - 51,2
Gudang
6 2 Gudang – Herve – Asung – 27,8+7,7+5,7+4,6+35,8=81,6
Yani- Murni - Gudang

Total biaya transportasi = Rp 283.950/minggu

Total jarak = 378,8 km/minggu

Kesimpulan: Dengan frekuensi kunjungan ditambah semakin banyak, biaya

transportasi dan jarak tempuh semakin besar. Solusi terbaik diperoleh pada saat
frekuensi sama dengan 1.

Penyelesaian Menggunakan Metode Heuristik Cluster First Route Second

Beltramani dan Bodin mempertimbangkan dua pendekatan untuk penyelesaian

masalah PVRP salah satunya yakni cluster first route second, dengan pendekatan ini yang
pertama kali dilakukan adalah menugaskan tiap agen ke hari kunjungan dan selanjutnya
menentukan rute kunjungan pada tiap harinya (Golden et al., 2008).

Tahap 1: Penugasan Agen ke hari kunjungan dan kendaraan

Dalam tahap ini setiap agen akan ditugaskan kunjungan ke dalam satu hari atau
lebih berdasarkan frekuensi kunjungan yang telah ditentukan. Penugasan agen ke hari
kunjungan bisa menggunakan metode optimasi yang dimodifikasi dari model matematis
IPVRPTW yang dirumuskan oleh Rusdiansyah dan Tsao (2005). Model matematis
dinyatakan pada persamaan 11-16.

Subject to:

Parameter :
r = kombinasi hari kunjungan
m = panjang periode waktu
fi = frekuensi kunjungan pada agen ke-i
qi = jumlah produk yang dikirim ke agen ke-i
Ck = kapasitas kendaraan ke-k
Ci = biaya transportasi per unit dari distributor ke agen ke-i

Variabel keputusan:
Yit = bernilai 1 jika agen ke-i akan dikunjungi pada hari ke ke-t
Xitk = bernilai 1 jika kendaraan ke-k mengunjungi agen ke-i pada hari ke ke-t

Tahap 2: Penentuan rute kunjungan pada setiap harinya

Setelah semua agen masuk ke hari kunjungan, untuk menentukan rute kunjungan
tahap ini bisa digunakan metode nearest neighbour.

Latihan Soal
PT. X merupakan salah satu distributor LPG di kawasan Malang Raya. Untuk
mendistribusikan elpiji ke 7 toko yang terletak di wilayah Turen – Dampit,
perusahaan menggunakan kendaraan dengan kapasitas angkut 100 tabung.
Perusahaaan sedang mempertimbangkan 2 strategi pengiriman untuk memenuhi
permintaan masing-masing agen pada tiap minggunya :
Strategi 1 : masing-masing agen dikunjungi tiap hari (frekuensi kunjungan 6x).
Strategi 2 : masing-masing agen dikunjungi 3 kali dalam satu minggu (frekuensi
kunjungan 3x). Dengan jadwal kunjungan sebagai berikut :
- Kombinasi 1 : Hari Senin, Rabu dan Jumat. Dengan mengunjungi 3
agen : Asung, Herve Mulyono, Rejo Turen.
- Kombinasi 2 : Hari Selasa, Kamis dan Sabtu. Dengan mengunjungi
4 agen : Bu Yani, Dilarama, Murni dan Lancar Jaya.
Data permintaan elpiji dan jarak tempuh (km) dari perusahaan ke masing-masing
agen dan antar agen ditunjukkan pada tabel berikut :

Permintaan
Kode Nama Agen P TA HM RT BY TD TM LJ
(tabung/minggu)
P Perusahaan 0 37,6 27,8 26,1 31,2 12,1 35,8 36,7 -
TA Toko Asung 0 7,5 9,2 5,7 23,2 0,7 0,2 100
HM Herve Mulyono 0 1,7 5,1 15,7 9,7 7,3 64
RT Rejo Turen 0 6,8 13 11,47 9 100
BY Bu Yani 0 20,8 4,6 2,2 100
TD Toko Dilarama 0 24,4 2,3 48
TM Toko Murni 0 0,9 24
LJ Toko Lancar Jaya 0 48

Pertanyaan :
a. Tentukan kuantitas pengiriman yang harus dibawa ke masing-masing agen
baik pada strategi pengiriman 1 dan 2.
b. Jika perusahaan menggunakan strategi 1, apakah satu kendaraan sudah
mencukupi untuk membawa kuantitas pengiriman untuk ke 7 agen pada
tiap kali kunjungan? Jika ya, tentukan rute pengiriman ke 7 agen tersebut
dengan metode nearest neighbour dan hitung total jarak yang harus
ditempuh kendaraan untuk tiap kali kunjungan.
c. Jika perusahaan menggunakan strategi 2, cek jumlah kendaraan yang
dibutuhkan untuk mengirimkan elpiji baik pada kombinasi kunjungan 1
 dan 2. Jika hanya membutuhkan 1 kendaraan maka tentukan rute
pengiriman baik pada kombinasi kunjungan 1 dan 2 dengan metode
nearest neighbour. Hitung total jarak yang harus ditempuh kendaraan
untuk tiap kali kunjungan.
d. Dengan asumsi konsumsi bensin 1 liter untuk 6 km dan harga bensin Rp
4.500/liter, tentukan biaya bahan bakar yang diperlukan untuk
mengirimkan elpiji pada tiap minggu baik pada strategi 1 dan 2.
e. Tentukan strategi pengiriman mana yang menghasilkan biaya bahan bakar
yang minimum.

Daftar Pustaka
Cordeau, J.F., M. Gendreau, dan G. Laporte, 1997. A Tabu Search Heuristic for
Periodic and Multi-Depot Vehicle Routing Problems, Networks, 30 (2),
105–119.
Golden, B., S. Raghavan, dan E. Wasil, 2008. The Vehicle Routing Problem :
Latest Advances and New Challenges, Springer, New York
Prana, A R., 2007. Aplikasi Kombinatoring pada Vehicle Routing Problem, Jurnal
Teknik Informatika, ITB.
Rusdiansyah, A. dan Tsao, D., 2005. An Integrated Model of The Periodic
Delivery Problems for Vending Machine Supply Chains, Journal of Food
Engineering 70, 421 – 434.