bab ii landasan teori 2.1 vehicle routing problem (vrp)
TRANSCRIPT
4
BAB II
LANDASAN TEORI
2.1 Vehicle Routing Problem (VRP)
Vehicle Routing Problem (VRP) dideskripsikan sebagai masalah merancang
pengiriman yang optimal dari satu atau lebih depot ke sejumlah pelanggan yang
tersebar secara geografis (Laporte, 1992). VRP biasanya memiliki π β kendaraan
dengan kapasitas yang sama pada suatu depot untuk melayani sejumlah konsumen
atau retail. Depot akan menentukan rute yang akan dilalui oleh kendaraan untuk
mengirim barang ke sejumlah retail. Pada VRP seringkali diasumsikan bahwa
perjalanan kendaraan akan berawal dan berakhir di depot yang sama. Pemilihan rute
juga dilakukan dengan mempertimbangkan kapasitas kendaraan dan permintaan
retail yang ada.
Dalam VRP kendaraan dengan kapasitas terbatas terletak di depot dalam grafik
πΊ = (π, πΈ). Dimana π = [1, . . , π] merupakan himpunan tidak kosong dari simpul
(vertex atau node) dan πΈ adalah himpunan busur (edges atau arcs), πΈ = [1, β¦ , π]
yang menghubungkan sepasang simpul pada grafik tersebut. Vertex atau node
diartikan sebagai sejumlah retail yang akan dikunjungi, dimana π£1 diasumsikan
sebagai depot. Sedangkan busur melambangkan jalan yang menghubungkan retail
π ke retail π, π = (π£π, π£π). Dalam merancang rute yang optimal untuk meminimasi
biaya transportasi menurut Gendreau, Hertz, and Laporte (1994) VRP harus
memenuhi batasan sebagai berikut :
1) Setiap rute kendaraan berawal dan berakhir di depot
2) Setiap pelanggan atau retail hanya boleh dikunjungi satu kali oleh satu kendaraan
3) Kendaraan yang digunakan adalah homogen dan memiliki kapasitas tertentu,
sehingga permintaan pelanggan pada setiap rute yang dilalui tidak boleh melebihi
kapasitas kendaraan.
2.1.1 Jenis-Jenis VRP
Studi mengenai VRP terus mengalami perkembangan. Beberapa literatur membagi
VRP menjadi beberapa jenis (Lin, Choy, Ho, Chung, & Lam, 2014) sebagai berikut :
5
1) Capacitated VRP (1959)
CVRP adalah masalah optimasi pengiriman barang dengan
mempertimbangkan kapasitas kendaraan.
2) Time-dependent VRP(1966)
TDVRP mempunyai karakteristik bahwa perjalanan di tentukan oleh setiap
retail yang berdekatan yang berguna untuk masalah kemacetan.
3) Pickup and Delivery Problem (1967)
PDP atau VRPPD merupakan pengiriman barang dengan mengambil atau
mengangkut beberapa barang dari retail.
4) Multi-depot VRP (1969)
Multi-depot VRP (MDVRP) masalah yang berisi lebih dari satu depot dan
setiap pelanggan dikunjungi oleh kendaraan yang ditugaskan ke salah satu depot
ini (yaitu setiap rute kendaraan harus mulai dan berakhir di depot yang sama).
5) Stochastic VRP (1969)
Stochastic VRP (SVRP) terjadi ketika beberapa elemen seperti permintaan
pelanggan, waktu perjalanan, dan bahkan set pelanggan dalam masalah routing
adalah acak (Gendreau, Laporte, & SΓ©guin, 1996). Teori probabilitas adalah alat
utama untuk mewakili ketidakpastian dalam model matematika ini.
6) Location Routing Problem (1973)
Pengamatan yang menunjukkan bahwa lokasi depot terpisah dan rute
kendaraan sering menghasilkan solusi yang kurang optimal dan menghasilkan
biaya tambahan. Hal tersebut yang memotivasi munculnya Location Routing
Problem (LRP) oleh Watson-Gandy and Dohrn (1973). Dalam LRP, keputusan
terdiri dari membuka satu set depot dan merancang sejumlah rute, dengan tujuan
meminimalkan biaya tetap dan biaya rute.
7) Periodic VRP (1974)
PVRP adalah sebuah masalah pemenuhan pengiriman dari depot ke retail
dengan beberapa hari kunjungan sampai barang terkirim seluruhnya.
6
8) Dynamic VRP (1976)
Dynamic VRP permasalahan dimana permintaan kostumerdi keluarkan
selama periode pemesanan dan harus di tempatkan pada waktu yang sebenarnya
untuk memastikan kendaraan yang cocok.
9) Inventory Routing Problem (1984)
Inventory Routing Problem (IRP) pertama kali dipertimbangkan oleh Bell et
al. (1983) yang berurusan dengan distribusi produk udara dalam hal manajemen
persediaan terpadu dan pengiriman kendaraan.
10) Fleet Size and Mix Vehicle Routing Problem (1984)
The Fleet Size and Mix VRP (FSMVRP) adalah menentukan kombinasi
paling ekonomis dari kendaraan ketika mempertimbangkan trade-off antara
biaya kendaraan tetap dan biaya variabel proporsional dengan jarak yang
ditempuh (Baldacci, Battarra, & Vigo, 2009; Liu, Huang, & Ma, 2009). Kasus
yang lebih kompleks dalam masalah ukuran kendaraan adalah
mempertimbangkan kendaraan heterogen dengan kapasitas dan biaya perjalanan
yang berbeda.
11) Generalized VRP (1984)
Generalized VRP, pelanggan dipartisi menjadi cluster dan kendaraan wajib
mengunjungi hanya satu pelanggan di setiap cluster (Ghiani & Improta, 2000).
12) Multi-Compartment VRP (1985)
Dalam MCVRP, setiap pelanggan meminta satu atau lebih jenis produk
dimana harus dikirimkan hanya dengan 1 kendaraan. Namun, beberapa
kunjungan diizinkan untuk mengirimkan produk yang diminta berbeda untuk
memenuhi permintaan produk. MCVR secara alami melakukan beberapa
industri, seperti pengiriman makanan ke toserba dan distribusi bahan bakar.
13) Site-dependent VRP (1986)
Site-dependent VRP (Nag, 1988) merupakan ketidak terikatan antara
pelanggan dan jenis kendaraan. Setiap pelanggan diizinkan untuk dikunjungi
oleh hanya satu jenis kendaraan.
7
14) Split-delivery VRP (1989)
Permasalahan bahwa setiap pelanggan dikunjungi hanya sekali saja.
Namun, hal ini tidak selalu realistis karena terkadang permintaan pelanggan
melebihi kapasitas kendaraan. Split-delivery VRP (SDVRP) pertama kali
diperkenalkan oleh Dror and Trudeau (1989) yang menunjukkan bahwa
penghematan biaya yang luar biasa berkaitan dengan jumlah kendaraan dan
total jarak perjalanan dapat dicapai oleh pengiriman split.
15) Multi-echelon VRP (2009)
Multi-echelon VRP (MEVRP) mempelajari perpindahan arus dalam strategi
distribusi multi-eselon. Pengiriman oleh angkutan dari tempat asal kepada
kostumer harus di kirim melalui intermediate depot.
16) VRP with Time Windows (1977)
Tujuan VRPTW adalah untuk melayani semua pelanggan dengan batasan
waktu dan jumlah minimum kendaraan. Hal tersebut untuk jumlah rute yang
sama dengan jarak tempuh perjalanan minimum yang diikuti oleh waktu jadwal
minimum dan waktu tunggu minimum.
2.1.2 Capacitated Vehicle Routing Poblem
Pengoptimalan kapasitas pada suatu kendaraan merupakan masalah yang
terkandung dalam persoalan VRP. Dalam CVRP, jumlah pelanggan dan kebutuhan
sudah di ketahui dan dalam pemenuhannya dilakukan dengan sekali kunjungan dari
satu depot ke jumlah pelanggan lalu kembali ke depot. Penyelesaian CVRP
bertujuan untuk menentukan rute dan jarak terpendek. Cara penyelesaian CVRP
diperlukan metode metaheuristik untuk mengaproksimasi solusi optimum agar
solusinya dapat dapat diperoleh dengan cepat dan cukup baik.adapun asumsi untuk
CVRP :
1. Setiap pelanggan hanya dikunjungi tepat oleh satu kendaraan.
2. Setiap kendaraan mempunyai batasan kapasitas yang sama.
3. Setiap pelanggan terhubung satu sama lain dimana jarak i ke j sama dengan
jarak j ke i.
4. Kendaraan ayng tersedia cukup untuk mengirim semua permintaan pelanggan.
8
Pada permasalahan CVRP akan dicari rute dengan total terpendek umtuk
melakukan pendistribusian barang dari depot ke pelanggan dengan suatu kendaraan
sehingga permintaan pelanggan terpenuhi. Berikut formulasi matematika CVRP
disediakan di bawah ini:
Min β β β πΆπππ πππ
πππ=0
ππ=0
πΎπ=0 (1)
Persamaan (1) untuk meminimalkan total biaya perjalanan semua kendaraan
ππππ = 1 (2)
Persamaan (2) menunjukkan kendaraan datang dari pelanggan i ke pelanggan j
bernilai 1, maka selain itu bernilai 0
β β πππππ
π=0 = 1. π = 1,2, β¦ . , ππΎπ=0 (3)
β β πππππ
π=0 = 1. π = 1,2, β¦ . , ππΎπ=0 (4)
Persamaan (3) dan (4) untuk memastikan bahwa setiap pelanggan hanya di kunjungi
sekali
β πππ‘π β β ππ‘π
π = 0, π = 1,2, β¦ , πππ=0
ππ=0 (5)
Persamaan (5) untuk memastikan rute selanjutnya
β β ππππ πππ
π β€ π·π = 1,2, β¦ , πΎππ=0
ππ=0 (6)
Persamaan (6) menunjukkan jumlah jarak dari setiap rute mempunyai batas
β ππ(β πππππ
π=0 ) β€ ππ, π = 1,2, β¦ , πΎπ π=0 (7)
Persamaan (7) menunjukkan bahwa jumlah permintaan dari setiap rute tidak dapat
melebihi kapasitas dari kendaraan
β π0ππ β€ 1, π = 1,2, β¦ . , πΎπ
π=1 (8)
β ππ0π β€ 1, π = 1,2, β¦ . , πΎπ
π=1 (9)
Persamaan (8) dan (9) memastikan bahwa kendaraaan hanya digunakan sekali
dalam satu rute
ππππ π{0,1}; π, π = 0,1, β¦ , π; π = 1,2, β¦ , πΎ (10)
9
Persamaan (10) memastkan bahwa variabel yang digunakan hanya menggunakan
interger 0/1
Dimana :
i = Pelangaan
S = Jumlah Pelanggan
ππ= Permintaan pelanggan ke-i
Q = Kapasaitas Kendaraan
k = Kendaraan
K= Jumlah kendaraan
d = Jarak Perjalanan
π·π= Jarak maksimum kendaraan ke-k
C = Total biaya perjalanan
2.1.3 Perhitngan Konsumsi Bahan Bakar
Perhitungan total konsumsi bahan bakar Kuo (2010) mengusulkan model
konsumsi bahan bakar dengan membagi kendaraan routing ke beberapa sub-rute.
Masing βmasing kendaraan memiliki batasan kapasitas dan total konsumsi bahan
bakar dihitung dengan menjumlahkan konsumsi bahan bakar dari setiap sub-rute.
Pada penelitian ini, perhitungan total konsumsi bahan bakar mengacu pada artikel
J. Zhang et al. (2015). Mereka mengusulkan prosedur dinamis untuk menghitung
total konsumsi bahan bakar. πΎππΏππ dan π£ππ menunjukkan jarak tempuh kendaraan
per liter bahan bakar dan kecepatan rata β rata kendaraan. Apabila kendaraan
berjalan dari node π menuju node π, kemudian konsumsi bahan bakar per unit waktu
dinotasikan sebagai πΏππ»ππ digambarkan pada persamaan (11).
πΏππ»ππ = π£ππ
πΎππΏππ (11)
10
Konsumsi bahan bakar πΉππ untuk kendaraan tanpa muatan yang berjalan
dari node π menuju node π ditunjukkan pada persamaan (12).
πΉππ = πΏππ»ππ π₯ πππ
π£ππ (12)
Berdasarkan penelitian Kuo and Wang (2011), diasumsikan bahwa setiap
penambahan beban muatan kendaraan dengan berat π akan meningkatkan
konsumsi bahan bakar sebanyak π%. ketika kendaraan bergerak mengirim barang
dari node π menuju node π dengan berat muatan πΏππ, total konsumsi bahan bakar
dari π ke π ditunjukkan pada persamaan (13).
πΉπΆππ = πΏππ»ππ π₯ πππ
π£ππ π₯ (1 + π π₯
πΏππ
π) (13)
Total konsumsi bahan bakar untuk sub-rute π dinotasikan sebagai πΉπΆπ dan πΏ
adalah berat muatan saat ini. Berdasarkan perhitungan πΉπΆππ dan πΉππ, langkah -
langkah perhitungan total konsumsi bahan bakar ππΉ di deskripsikan sebagai
berikut:
Langkah 1 : Inisialisasi
Inisialisasi total konsumsi bahan bakar (ππΉ) = 0 dan indeks sub-rute = 1;
Langkah 2 :
Hitung konsumsi bahan bakar untuk setiap sub β rute secara berurutan sesuai
tahapan berikut :
Langkah 2.1 : Untuk setiap sub-rute, set total konsumsi bahan bakar πΉπΆπ = 0,
π = ππ β 1, πΏ = 0 ;
Langkah 2.2 : πΉπΆπ = πΉ(π ππ )(0) ;
Langkah 2.3 : Apabila π β 2, hitung konsumsi bahan bakar dari sub-rute
secara terbalik dengan berat muatan:
πΏ = πΏ + π(π ππ ) (Sbihi,
#38)
Total konsumsi bahan bakar dari sub-rute r:
11
πΉπΆπ = πΉπΆπ π₯ πΉ(π ππ β1)(π π
π ) π₯ (1 + π (πΏ
π)), (14)
apabila π = π β 1, maka kembali ke langkah 2.2;
Langkah 2.4 : Apabila π = 2, maka:
πΏ = πΏ + π(π ππ ),
πΉπΆπ = πΉπΆπ π₯ πΉ(0)(π ππ ) π₯ (1 + π (
πΏ
π)), (15)
ππΉ = ππΉ + πΉπΆπ (16)
Apabila π < π, dimana π = π + 1, maka ulangi perhitungan
mulai dari langkah 1.
Langkah 3 : output total konsumsi bahan bakar.
prosedur perhitungan ditunjukkan pada Error! Reference source
not found. Perhitungan akumulasi konsumsi bahan bakar pada setiap sub-
rute dihitung dengan cara membalik urutan dari sub-rute.
π βΆ Panjang busur atau jarak antara π dan π
π : Jumlah kendaraan
π : Indeks sub-rute
ππ : Himpunan node pada sub-rute π.
π ππ : Nomor seri pada node π di sub-rute π, sebagai contoh pada sub-rute
2 yaitu 0-3-1-7-0. Maka π 23 = 1
ππ : Permintaan pada node π
Q : Kapasitas kendaraan (Kilogram)
πΆπ : Biaya bahan bakar per liter (Pratysto, #15)
πΆπ : Biaya emisi karbon per liter bahan bakar (Pratysto, #15)
πΆπ£ : Biaya penggunaan kendaraan (Rp/jam)
πΏππ»ππ : Konsumsi bahan bakar per unit waktu (liter/jam)
π£ππ : Kecepatan rata β rata kendaraan (km/jam)
12
πππ : Jarak tempuh node i menuju node j (km)
πΎππΏππ : jarak tempuh per liter bahan bakar
πΉππ : Konsumsi bahan bakar untuk kendaraan tanpa muatan
πΏ : Berat muatan saat ini
π : Peningkatan konsumsi bahan bakar setiap penambahan beban muatan (2%)
π : Peningkatan kapasitas kendaraan setiap 100 lb atau 45,35 kilogram
ππΉ : Total konsumsi bahan bakar
2.2 Dasar teori Particle Swarm Optimization (PSO)
Particle Swarm Optimization (PSO) adalah algoritma metaheuristik yang
diusulkan oleh (Eberhart & Kennedy, 1995). PSO yang mengidentifikasi dari
perilaku sosial organisme seperti pengelompokan burung dan ikan dalam bertahan
hidup. Particle Swarm Optimization adalah teknik optimasi dengan cara
menghitung secara terus menerus calon solusi dengan menggunakan suatu acuan
kualitas dengan cara menggerakan partikel / calon solusi di dalam ruang
permasalahan menggunakan fungsi tertentu untuk posisi dan kecepatan dari
partikel. Setiap partikel dapat menyampaikan informasi atau posisi sebagai objek
dan menyesuaikan posisi dan kecepatan masing-masing. dengan beberapa
karakteristik.
Secara umum solusi yang ada pada algoritma PSO disebut partikel yang
menciptakan suatu kerumunan. Algortima ini mengadopsi 2 vektor yaitu X untuk
posisi dan V untuk kecepatan. Dengan cara menempatkan partikel ke salah satu
ruang dan memberikan nilai-nilai fungsi maka dapat di hitung dengan (Marinakis,
Marinaki, & Migdalas, 2017):
πππ(0) = ππππ.π + ππ(ππππ₯.π β ππππ.π) (17)
Dimana :
ππππ₯ : nilai maksimum
13
ππππ : nilai minimum
ππ : nilai acak antara 0-1
i : ukuran kawanan
j : dimensi kawanan
kecepatan dan posisi partikel diperbarui dengan persamaan berikut :
π£ππ(π‘ + 1) = π€1π£ππ(π‘) + π1π1(ππππ π‘ππ β πππ(π‘)) + π2π2(ππππ π‘ππ β πππ(π‘))
(18)
π₯ππ(π‘ + 1) = πππ(π‘) + π£ππ(π‘ + 1) (19)
Dimana t adalah iterasi ke-, c1 dan c2 adalah coeficient acceleration yang bernilai
positif dan r1 dan r2 merupakan nilai random yang bernilai antara 0-1. Nilai C bisa
konstan atau dapat didapatasi selama iterasi. Namun, ada kemungkinan untuk nilai
yang berbeda atau menyesuikan nilainya selama iterasi yang dapat di jalankan
dengan faktor bobot inersia yang bervariasi terhadap waktu sesuai pada persamaan
(14).
πππ’ππ_ππ‘ππ = (ππππ₯ β ππππ) βπππ₯_ππ‘ππβππ’ππππ‘ππ
πππ₯_ππ‘ππ+ ππππ (20)
Nilai π1 dan π2 di tulis sebagai berikut :
π1 = π1,πππ +π1,πππ₯βπ1,πππ
ππ‘πππππ₯π₯π‘ (21)
π2 = π2,πππ +π2,πππ₯βπ2,πππ
ππ‘πππππ₯π₯π‘ (22)
Dengan melakukan ini pada iterasi pertama ada banyak kebebasan bergerak dalam
ruang solusi partikel untuk memukan yang optimal. Perhitungan Pbest dapat dilihat
pada persamaan (23)
ππππ π‘ = {π₯ππ(π‘ + 1), ππ π(π₯ππ(π‘ + 1)) < π(π₯ππ(π‘)
ππππ π‘, ππ‘βπππ€ππ π (23)
Posisi optimal (gbest) dapat di hitung sesuai persamaan (24)
14
ππππ π‘π β {ππππ π‘1π,ππππ π‘2π , β¦ . ππππ π‘ππ}|π(ππππ π‘π) =
min{π(ππππ π‘1π,ππππ π‘2π, β¦ . ππππ π‘ππ) (24)
Algorithm 1 Particle Swarm Optimization.
Initialize the swarm
Initialize velocity
Initialize position
Initialize parameters
Evaluate particles
Find the local best
Find the global best
Calculate of the initial cost function (fitness function) value of each particle
Keep global best particle (solution) of the whole swarm
Keep personal best of each particle
Do
{
Update velocity (10)
Update position (11)
Evaluate
Update Pbest
Update Gbest
}
End do
Return the best pasticle (the global best solution)
Gambar 2. 1 Psedocode PSO
15
Swarm Initialization
START
Particle fitness evaluating
Calculating the Individual historical optimal position
Calculating the Swarm historical optimal position
Updating the Particle velocity and position according
to the velocity and position updating equation
Satisfying the ending condition
END
NO
YES
Gambar 2. 2 Flowchart PSO
Menurut (Santosa, 2006) proses implementasi algoritma PSO dapat dituliskan
sebagai berikut :
1. Bangkitkan partikel atau populasi awal secara acak.
2. Hitung nilai fungsi fitness.
3. Bandingkan nilai fitness dengan pbest.
4. Identifikasi partikel-partikel lain yang mempunyai pbest, jika nilai pbest lebih
besar dari gbest, maka set gbest dengan pbest.
5. Update nilai kecepatan dan posisi suatu partikel. (18) (19)
16
6. Ulangi langkah 2 sampai kriteria sudah cocok (mempunyai fitness yang
optimum atau jumlah iterasi telah tercapai). Jika nelum, ulangi langkah
dengan memperbarui iterasi i=i+1, dengan cara menghitung nilai baru Pbest
dan Gbest.
Sebagian besar mengenai Vehicle Routingg Problem terfokus pada meminimasi
jarak dan biaya, beberapa contoh penelitian yang berkaitan dengan Vehicle Routing
Problem ditunjukkan pada Tabel 2.1
Tabel 2. 1 Penelitian Terdahulu
No. Penulis Fungsu tujuan Pendekatan Klasifikasi
1. (Chen, 2011) Minimasi total jarak
dan biaya
transportasi
Algoritma
PSO for
CVRP
Hybird
2. (Venkatesan,
Logendran, &
Chandramohan,
2011)
Minimasi total
biaya transportasi
CVRP with
Algoritma
PSO
Metaheuristik
3. (Razaq, 2019) Meminimalkan
biaya distribusi
Algoritma
PSO untuk
CVRP
Metauristik
4. (Tavakoli, Sami, &
Informatics, 2013) Menentukan waktu
dan biaya optimal
Algoritma
PSO untuk
memecahkan
CVRP
Metauristik
5. (Ai &
Kachitvichyanukul,
2009)
Menemukan
serangkaian rute
dan total biaya
minimum
PSO for
CVRP
Metaheuristik
6. (Hannan et al.,
2018)
Optimalisasi rute
dan biaya
operasional
PSO for
CVRP
Metaheuristik
17
7. (Utama, 2021 #92) Optimalisasi rute
dan biaya konsumsi
bahan bakar
Bee Colony
for GVRPTD
Metaheuristik
8. (Utama, #88) Optimalisasi rute
dan biaya konsumsi
bahan bakar
New HBO
for GVRP
Metaheuristik
9. (Ibrahim, 2021
#91) Optimalisasi rute
dan biaya distribusi
Improved
GA for
VRPPDTW
Metaheuristik
10. (Ibrahim, 2021
#90) Optimalisasi rute
dan biaya distribusi
Optimised
GA
crosssover
and mutation
for VRPPD
Metaheuristik