VRP di R
Agsyan Muhammad Sayidar
2026-10-20
Vehicle Routing Problem (VRP)
Vehicle Routing Problem (VRP) merupakan permasalahan mencari rute optimal untuk mengirimkan barang dengan kendaraan yang diketahui kapasitasnya menuju titik-titik lokasi pelanggan dengan jumlah tertentu. VRP diperkenalkan oleh George Dantzig dan John Ramser dalam paper berjudul The Truck Dispatching Problem pada tahun 1959. VRP dari dahulu hingga saat ini masih menjadi permasalahan klasik dalam dunia riset operasi karena perlu mempertimbangkan banyak faktor dalam merencanakan rute yang optimal.
VRP sendiri memiliki beberapa varian umum, diantaranya adalah Capacitated VRP (CVRP), VRP with Pick up and Delivery (CRPPD), VRP with Time Windows (VRPTW), dan Open VRP (OVRP). Kesempatan kali ini, kita khusus membahas penyelesaian CVRP di R menggunakan package vrp.
Library
library vrpr merupakan library utama yang digunakan, lalu 5 lainnya sebagai library pendukung.
library(vrpr) #Library untuk berbagai kasus Vehicle Routing Problem## Warning: package 'vrpr' was built under R version 4.6.1library(readxl) #Membaca fail Excel
library(ggplot2) #Membuat grafik
library(geosphere) #Menghitung jarak riil## Warning: package 'geosphere' was built under R version 4.6.1library(kableExtra) #Membuat tabel agar tidak monoton
library(dplyr) #Modifikasi data frame##
## Attaching package: 'dplyr'## The following object is masked from 'package:kableExtra':
##
## group_rows## The following objects are masked from 'package:stats':
##
## filter, lag## The following objects are masked from 'package:base':
##
## intersect, setdiff, setequal, unionData
Data yang digunakan merupakan data titik titik kabupaten dan kota di 3 provinsi, yaitu Banten, DKI Jakarta, dan Jawa Barat. Di dalam data terdapat kolom x untuk longitude, y untuk latitude, dan Demand untuk jumlah permintaan.
Contoh kasus, anggap kita merupakan sebuah perusahaan logistik yang harus mengirimkan unit barang ke retail-retail di daerah Banten, DKI Jakarta, dan Jawa Barat. Setiap daerah memiliki permintaan barangnya masing-masing, tetapi kita memiliki batasan berupa jumlah Truk dan kapasitas truk sehingga perlu mencari rute optimal agar cost operasional bisa ditekan.
data.contoh <- read_xlsx("C:/Users/Agsyan M S/Documents/Bahas R/Data Contoh CVRP.xlsx")
data.contoh## # A tibble: 41 × 5
## Provinsi Kab_Kota x y Demand
## <chr> <chr> <dbl> <dbl> <dbl>
## 1 DKI JAKARTA Kota Jakarta Selatan 107. -6.27 10
## 2 DKI JAKARTA Kota Jakarta Timur 107. -6.26 11
## 3 DKI JAKARTA Kota Jakarta Barat 107. -6.17 12
## 4 JAWA BARAT Kota Bandung 108. -6.92 15
## 5 JAWA BARAT Kota Bekasi 107. -6.28 14
## 6 DKI JAKARTA Kota Jakarta Pusat 107. -6.18 3
## 7 BANTEN Kota Tangerang Selatan 107. -6.30 17
## 8 JAWA BARAT Kota Depok 107. -6.40 18
## 9 DKI JAKARTA Kota Jakarta Utara 107. -6.13 18
## 10 BANTEN Kota Tangerang 107. -6.18 3
## # ℹ 31 more rowssebelum mulai dengan contoh kasus, Kabupaten Kepulauan Seribu yang berada di Provinsi DKI Jakarta perlu disisihkan dari data karena contoh kasus akan memakai kendaraan darat berupa truk sehingga kali ini akan fokus pada titik-titik lokasi yang berada pada pulau yang sama.
data.contoh <- data.contoh[data.contoh$Kab_Kota != "Kepulauan Seribu",]Setelah itu, kita lakukan eksplorasi data sederhana membuat diagram batang permintaan atau demand setiap daerah. Terlihat permintaan tertinggi ada di daerah Tasikmalaya, Kota Tasikmalaya, dan Bandung Barat. Di sisi lain, permintaan terendah terdapat di daerah Kota Bogor, Kota Jakarta Pusat, dan Kota Tangerang. Dari grafik di bawah dapat tergambar dengan lebih jelas permintaan masing-masing retail.
ggplot(data.contoh, aes(x=reorder(Kab_Kota,Demand), y=Demand, fill=Provinsi)) +
geom_bar(stat="identity", width = 0.8)+theme(axis.text.x = element_text(angle = 45, hjust = 1)) +
ylab("Jumlah Pesanan") + xlab("Kabupaten/Kota") + ggtitle("Demand Kab/Kota")
Analisis CVRP
Persiapan Data
Contoh kasus ini kita anggap terdapat 1 depot yang berlokasi di Bogor. Dari depot di Bogor kita perlu mengirim barang ke retail lain diluar Bogor. Oleh karena itu, sebelumnya kita perlu mendefinisikan Bogor sebagai depot dan mendefinisikan pelanggan sebagai seluruh daerah kecuali Bogor.
depot <- data.contoh[data.contoh$Kab_Kota == "Bogor",c(2,3,4)]
pelanggan <- data.contoh[data.contoh$Kab_Kota != "Bogor", c(2,3,4,5)]Pemodelan Data
Dalam Capacitated Vehicle Routing Problem,terdapat beberapa batasan atau constrant, yaitu:
- Terdapat M kendaraan (truk) dengan N kapasitas
- Terdapat 1 Depot
- Setiap pelanggan hanya boleh dikunjungi sebanyak 1 kali dan hanya
oleh satu truk
- Setiap truk harus berangkat dari dan kembali lagi ke depot
total.demand <- sum(pelanggan$Demand)
total.demand## [1] 440Total permintaan ada 440 unit. Sekarang kita memiliki 10 truk yang masing-masing memiliki kapasitas 60 unit, artinya total unit yang bisa kita bawa adalah 10 x 60 = 600 unit. Apakah semua truk kita gunakan? mari kita lihat hasil perhitungannya.
colnames(pelanggan) <- c("Kab_Kota", "x", "y", "demand")
model <- vrp_model() |>
add_depot(x = depot$x, y = depot$y) |>
add_clients(pelanggan) |>
add_vehicle_type(num_available = 10, capacity = 60)
res <- vrp_solve(model, stop = max_iterations(5000), seed = 1, display = FALSE)
res## ## ── vrpr result ─────────────────────────────────────────────────────────────────## • cost 10 - feasible## • 8 routes - 39 clients## • 5000 iterations - 1.83shasilnya ternyata kita hanya perlu total 8 rute alias hanya perlu menggunakan 8 truk dari 10 truk yang tersedia untuk memenuhi permintaan 39 pelanggan/client. penjelasan keterangan lainnya, pertama untuk 5.000 iterasi yang telah ditentukan sebagai kriteria stop ternyata diperlukan waktu komputasi sebanyak 4,9 detik, kedua cost yang dikeluarkan (dalam hal ini adalah total jarak) adalah sebesar 10.
Kok kecil sekali total jarak cuma sepanjang 10? Hal tersebut terjadi karena kita menggunakan koordinat longitude dan latitude yang secara default memang akan menghasilkan nilai yang kecil. ambil contoh jarak antara Serang (106,1484 , -6,17427) dan Tangerang (106,5186 , -6,17427) jika dihitung jarak euclideannya hanya menghasilkan jarak sepanjang 0,371413 satuan. Alasan kedua, setting library vrpr sendiri jika kita tidak mengatur matriks jarak secara manual, maka library vrpr akan menghitung jarak euclidean ke dalam bilangan bulat, contoh seperti berikut
round(0.789)## [1] 1round(0.4999)## [1] 0round(1.3276)## [1] 1round(2.50001)## [1] 3round(0.500001)## [1] 1Terlihat bahwa sistem pembulatan yang dilakukan adalah pembulatan total hingga menjadi bilangan bulat. Hal tersebut sebetulnya tidak masalah jika jarak antar titik lokasinya besar semisal puluhan atau ratusan, tetapi bagaimana jika jarak yang terhitung ternyata hanya 0,245 hal itu tentunya akan membuat nilainya menjadi 0 yang tidak logis. Oleh karena itu, jarak koordinat perlu kita ubah menjadi jarak sebenarnya lalu memasukkan matriks jarak sebenarnya itu ke dalam solver vrpr seperti di bawah ini dengan bantuan library geosphere.
#Susun koordinat dengan depot sebagai lokasi pertama
lokasi <- rbind(
data.frame(x = depot$x[1], y = depot$y[1]),
data.frame(x = pelanggan$x, y = pelanggan$y)
)
#Hitung matriks jarak Haversine dalam meter
koordinat <- as.matrix(lokasi[, c("x", "y")])
distance_m <- round(
geosphere::distm(
koordinat,
fun = geosphere::distHaversine
)
)#Masukkan matriks jarak ke dalam problem data
problem <- vrp_problem_data(model, distance = distance_m)
#Solve lagi dari model yang telah diinputkan matriks jarak
res2 <- vrp_solve(
problem,
stop = max_iterations(5000),
seed = 1,
display = FALSE
)
res2## ## ── vrpr result ─────────────────────────────────────────────────────────────────## • cost 2231099 - feasible## • 8 routes - 39 clients## • 5000 iterations - 2.52sHasil terbarunya terlihat bahwa solusinya tetap sama sebanyak 8 rute alias 8 truk untuk memenuhi permintaan 39 pelanggan. Hal yang berbeda di sini adalah costnya yang menunjukkan jarak 2.231.099 meter atau 2.231,1 KM. dengan kata lain, total ke-8 rute hasil optimasi di mana truk berangkat dari dan pulang lagi ke depot adalah sepanjang 2.231 km.
Grafik Rute
Mari kita lihat perbandingan grafik rute antara kedua hasil CVRP tadi. Terlihat bahwa walaupun jumlah rutenya sama, terdapat beberapa perbedaan di dalam rute rutenya. Keputusan memilih perhitungan jarak otomatis atau memuat matriks jarak terlebih dahulu dikembalikan sesuai preferensi pribadi untuk kasus ini saya lebih condong menggunakan matriks jarak karena dapat melihat langsung berapa KM jarak yang harus ditempuh oleh setiap truk.
plot(res)
plot(res2)
Kalau ingin dituliskan nama daerah pelanggan bisa menggunakan syntax berikut
plot(res2) + annotate("text", x = pelanggan$x, y=pelanggan$y-0.02, label = pelanggan$Kab_Kota)
Perbedaan rute dapat kita cek dengan syntax routes()
routes(res)## # A tibble: 39 × 10
## route_id depot position activity client shipment trip vehicle_type
## <int> <int> <int> <chr> <int> <int> <int> <int>
## 1 1 1 1 client 6 NA 1 1
## 2 1 1 2 client 15 NA 1 1
## 3 1 1 3 client 9 NA 1 1
## 4 2 1 1 client 20 NA 1 1
## 5 2 1 2 client 33 NA 1 1
## 6 2 1 3 client 16 NA 1 1
## 7 2 1 4 client 19 NA 1 1
## 8 2 1 5 client 10 NA 1 1
## 9 2 1 6 client 5 NA 1 1
## 10 3 1 1 client 12 NA 1 1
## # ℹ 29 more rows
## # ℹ 2 more variables: start_service <dbl>, wait <dbl>routes(res2)## # A tibble: 39 × 10
## route_id depot position activity client shipment trip vehicle_type
## <int> <int> <int> <chr> <int> <int> <int> <int>
## 1 1 1 1 client 30 NA 1 1
## 2 1 1 2 client 22 NA 1 1
## 3 1 1 3 client 25 NA 1 1
## 4 1 1 4 client 26 NA 1 1
## 5 1 1 5 client 27 NA 1 1
## 6 1 1 6 client 13 NA 1 1
## 7 1 1 7 client 31 NA 1 1
## 8 1 1 8 client 32 NA 1 1
## 9 2 1 1 client 24 NA 1 1
## 10 2 1 2 client 23 NA 1 1
## # ℹ 29 more rows
## # ℹ 2 more variables: start_service <dbl>, wait <dbl>Catatan:
kolom start_service dan wait hanya bisa diinterpretasikan saat melakukan analisis VRP with Time Windows. Jadi, pada kasus Capacitated VRP ini kolom tersebut tidak memiliki arti
Rangkuman Rute
Rute lengkapnya kita bisa melihatnya sebagai berikut:
rute.cvrp2 <- routes(res2)
pelanggan$client <- rownames(pelanggan)
df2 = merge(x = rute.cvrp2, y = pelanggan, by = "client", all = TRUE)
df2 <- df2[,c("client","route_id","depot","position","Kab_Kota")]
df2 <- arrange(df2, route_id, position)
kable(df2[, 4:5], booktabs = TRUE, col.names = c("Urutan","Kab/Kota"), align = 'c') %>% pack_rows(
index = c("Rute 1" = nrow(df2[df2$route_id == 1,]),
"Rute 2" = nrow(df2[df2$route_id == 2,]),
"Rute 3" = nrow(df2[df2$route_id == 3,]),
"Rute 4" = nrow(df2[df2$route_id == 4,]),
"Rute 5" = nrow(df2[df2$route_id == 5,]),
"Rute 6" = nrow(df2[df2$route_id == 6,]),
"Rute 7" = nrow(df2[df2$route_id == 7,]),
"Rute 8" = nrow(df2[df2$route_id == 8,])
)
)| Urutan | Kab/Kota |
|---|---|
| Rute 1 | |
| 1 | Pangandaran |
| 2 | Kota Banjar |
| 3 | Ciamis |
| 4 | Kuningan |
| 5 | Cirebon |
| 6 | Kota Cirebon |
| 7 | Majalengka |
| 8 | Indramayu |
| Rute 2 | |
| 1 | Purwakarta |
| 2 | Karawang |
| 3 | Bekasi |
| 4 | Kota Bekasi |
| Rute 3 | |
| 1 | Kota Tangerang |
| 2 | Tangerang |
| 3 | Kota Serang |
| 4 | Serang |
| 5 | Kota Cilegon |
| 6 | Pandeglang |
| 7 | Lebak |
| Rute 4 | |
| 1 | Sukabumi |
| 2 | Cianjur |
| 3 | Kota Bandung |
| 4 | Kota Cimahi |
| 5 | Kota Bogor |
| Rute 5 | |
| 1 | Kota Jakarta Timur |
| 2 | Kota Jakarta Utara |
| 3 | Kota Jakarta Pusat |
| 4 | Kota Jakarta Barat |
| 5 | Kota Jakarta Selatan |
| Rute 6 | |
| 1 | Kota Tasikmalaya |
| 2 | Tasikmalaya |
| 3 | Garut |
| 4 | Kota Sukabumi |
| Rute 7 | |
| 1 | Subang |
| 2 | Sumedang |
| 3 | Bandung |
| 4 | Bandung Barat |
| Rute 8 | |
| 1 | Kota Depok |
| 2 | Kota Tangerang Selatan |
Kesimpulan
Perusahaan bisa mengirimkan permintaan 440 unit barang kepada 39 pelanggannya cukup menggunakan8 dari 10 kendaraan yang tersedia dengan total jarak perjalanan sepanjang 2.231,1 di 3 provinsi berbeda. Masing-masing rute melakukan perjalanan sebagai berikut:
Rute 1: Depot -> Pangandaran -> Kota Banjar -> Ciamis ->
Kuningan -> Cirebon -> Kota Cirebon -> Majalengka ->
Indramayu -> Depot
Rute 2: Depot -> Purwakarta -> Karawang -> Bekasi -> Kota
bekasi -> Depot
Rute 3: Depot -> Kota Tangerang -> Tangerang -> Kota Serang
-> Serang -> Kota Cilegon -> Pandeglang -> Lebak -> Depot
Rute 4: Depot -> Sukabumi -> Cianjur -> Kota Bandung ->
Kota Cimahi -> Kota Bogor -> Depot
Rute 5: Depot -> Kota Jakarta Timur -> Kota Jakarta Utara ->
Kota Jakarta Pusat -> Kota Jakarta Barat -> Kota Jakarta Selatan
-> Depot
Rute 6: Depot -> Kota Tasikmalaya -> Tasikmalaya -> Garut
-> Kota Sukabumi -> Depot
Rute 8: Depot -> Kota Depok -> Kota Tangerang Selatan ->
Depot
Referensi:
https://cran.r-project.org/web/packages/vrpr/vignettes/vrpr.html