Multi Depot VRP menggunakan R
Agsyan Muhammad Sayidar
2026-11-07
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 MDVRP di R menggunakan package vrp.
Teman-teman bisa melihat contoh VRP lainnya yang sudah saya buat di
tautan di bawah ini:
1. Capacitated VRP: https://rpubs.com/Agsyanms111/cvrp-r
Library
Digunakan 6 library dengan vrpr sebagai library utama
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 menjadi lebih menarik
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 sintetis terdiri dari 5 kolom, yaitu Provinsi, Kab_kota, longitude, latitude, dan status. Data sintetis ini meliputi 3 Provinsi di pulau Sumatera, yaitu Provinsi Lampung, Sumatera Selatan, dan Jambi dengan total kab/kota berjumlah 43. Kolom longitude dan latitude digunakan untuk menghitung jarak tempuh kendaraan. Kolom status terdiri dari 2 kategori, yaitu Pelanggan dan Depo.
Langsung saja kita load data excel ke dalam R menggunakan syntax read_xlsx.
data <- read_xlsx("C:/Users/Agsyan M S/Documents/Bahas R/Data Contoh MDVRP.xlsx")
head(data)## # A tibble: 6 × 5
## Provinsi Kab_Kota longitude latitude status
## <chr> <chr> <dbl> <dbl> <chr>
## 1 JAMBI Kerinci 101. -2.04 Pelanggan
## 2 JAMBI Merangin 102. -2.20 Pelanggan
## 3 JAMBI Sarolangun 103. -2.31 Pelanggan
## 4 JAMBI Batang Hari 103. -1.75 Pelanggan
## 5 JAMBI Muaro Jambi 104. -1.61 Pelanggan
## 6 JAMBI Tanjung Jabung Timur 104. -1.19 Pelanggansummary(data)## Provinsi Kab_Kota longitude latitude status
## Length :43 Length :43 Min. :101.3 Min. :-5.517 Length :43
## N.unique : 3 N.unique :43 1st Qu.:103.1 1st Qu.:-4.699 N.unique : 2
## N.blank : 0 N.blank : 0 Median :104.1 Median :-3.752 N.blank : 0
## Min.nchar: 5 Min.nchar: 4 Mean :104.0 Mean :-3.546 Min.nchar: 4
## Max.nchar:16 Max.nchar:26 3rd Qu.:104.9 3rd Qu.:-2.377 Max.nchar: 9
## Max. :105.6 Max. :-1.071Sekarang kita perlu memisahkan data antara Depo dan Pelanggan menggunakan syntax di bawah ini.
data.depo <- data[data$status=='Depo',]
data.pelanggan <- data[data$status=='Pelanggan',]Terdapat 4 Depo yang tersebar di 3 provinsi, yaitu Depo Kota Jambi di provinsi Jambi, Depo Muara Enim dan Depo Kota Palembang di provinsi Sumatera Selatan, dan Depo Kota Bandar Lampung di provinsi Lampung. Keempat Depo inilah yang akan memenuhi pesanan pelanggan di 39 Kab/kota lainnya.
data.depo## # A tibble: 4 × 5
## Provinsi Kab_Kota longitude latitude status
## <chr> <chr> <dbl> <dbl> <chr>
## 1 JAMBI Kota Jambi 104. -1.62 Depo
## 2 SUMATERA SELATAN Muara Enim 104. -3.76 Depo
## 3 SUMATERA SELATAN Kota Palembang 105. -2.97 Depo
## 4 LAMPUNG Kota Bandar Lampung 105. -5.42 DepoSekarang di data pelanggan kita buat kolom baru bernama Demand yang kita isi melalui angka simulasi dari rentang 3 sampai 20 unit.
set.seed(3) #Agar bisa merelikasi nilai yang sama
data.pelanggan$Demand <- sample(3:20,39, replace = TRUE)
head(data.pelanggan,5)## # A tibble: 5 × 6
## Provinsi Kab_Kota longitude latitude status Demand
## <chr> <chr> <dbl> <dbl> <chr> <int>
## 1 JAMBI Kerinci 101. -2.04 Pelanggan 7
## 2 JAMBI Merangin 102. -2.20 Pelanggan 14
## 3 JAMBI Sarolangun 103. -2.31 Pelanggan 9
## 4 JAMBI Batang Hari 103. -1.75 Pelanggan 6
## 5 JAMBI Muaro Jambi 104. -1.61 Pelanggan 10setelah disimulasikan unit Demand tiap Kab/Kota, Kita lihat melalui visualiasi bar chart di bawah.
ggplot(data.pelanggan, 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),
plot.background = element_rect(fill = "white", color = NA),
panel.background = element_rect(fill = "white", color = NA),
panel.grid = element_blank(),
panel.border = element_blank(),
axis.line = element_line(color = "black"),
axis.ticks = element_line(color = "black"),
axis.text = element_text(color = "black"),
axis.title = element_text(color = "black")) +
ylab("Jumlah Pesanan (Unit)") + xlab("Kabupaten/Kota") + ggtitle("Demand Kab/Kota")
Permintaan tertinggi ternyata terdapat di Kab Musi Rawas Utara, Kota Sungai Penuh, dan Kota Prabumilih. Di sisi lain, 3 permintaan terendah terdapat di Kab Mesuji, Kab Musi Rawas, dan Kab Lampung Utara.
Analisis MDVRP
Komponen Depo, Pelanggan, dan Demand sudah ada, mari kita lakukan analisis Multiple Depots Vehicle Routing Problem.
Pemodelan Data
Dalam Multiple Depot Vehicle Routing Problem,terdapat beberapa batasan atau constrant, yaitu:
- Terdapat M kendaraan (truk) dengan N kapasitas
- Terdapat X Depot
- Setiap pelanggan hanya boleh dikunjungi sebanyak 1 kali dan hanya
oleh satu truk
- Setiap truk harus berangkat dari dan kembali lagi ke depot awal
total.demand <- sum(data.pelanggan$Demand)
total.demand## [1] 412Total permintaan pelanggan adalah 412 unit. Kemudian, armada truk yang kita punya berjumlah 16 masing-masing depot memiliki 4 truk berkapasitas sama yaitu 60 unit. Secara perhitungan total unit yang bisa diangkut adalah 16x60 = 960 unit sekali jalan. Pertanyaannya berapa armada truk yang dibutuhkan dan total jarak yang ditempuh seluruh truk untuk mendapatkan rute optimal? Mari kita bahas
colnames(data.pelanggan) <- c("Provinsi","Kab_Kota", "x", "y", "status", "demand")
model <- vrp_model() |>
add_depot(x = data.depo$longitude, y = data.depo$latitude) |>
add_clients(data.pelanggan) |>
add_vehicle_type(num_available = 4, capacity = 60, depot = 1) |>
add_vehicle_type(num_available = 4, capacity = 60, depot = 2) |>
add_vehicle_type(num_available = 4, capacity = 60, depot = 3) |>
add_vehicle_type(num_available = 4, capacity = 60, depot = 4)#Susun koordinat dengan depot sebagai lokasi pertama
lokasi <- rbind(
data.frame(x = data.depo$longitude, y = data.depo$latitude),
data.frame(x = data.pelanggan$x, y = data.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 model yang telah diinputkan matriks jarak
res.md <- vrp_solve(
problem,
stop = max_iterations(5000),
seed = 1,
display = FALSE
)
res.md## ## ── vrpr result ─────────────────────────────────────────────────────────────────## • cost 2942658 - feasible## • 8 routes - 39 clients## • 5000 iterations - 5.5sDidapatkan hasil optimal hanya dibutuhkan 8 dari 16 truk dan total jarak 2.942,7 kilometer untuk menyelesaikan pengiriman seluruh pelangggan.
Jadi, kita tidak perlu menggunakan seluruh armada yang ada malah kita bisa berhemat banyak dengan hanya menggunakan setengah armada. Catatan: mungkin masih bisa didapatkan hasil yang lebih optimal jika parameter iterations diganti menjadi lebih banyak.
Grafik Rute
Di bawah ini ialah rute optimal hasil perhitungan MDVRP:
routes(res.md)[, c("route_id", "depot", "client")]## # A tibble: 39 × 3
## route_id depot client
## <int> <int> <int>
## 1 1 1 9
## 2 1 1 1
## 3 1 1 10
## 4 1 1 2
## 5 1 1 3
## 6 2 1 5
## 7 2 1 6
## 8 2 1 7
## 9 2 1 8
## 10 2 1 4
## # ℹ 29 more rowsunique(routes(res.md)[, c("route_id", "depot")])## # A tibble: 8 × 2
## route_id depot
## <int> <int>
## 1 1 1
## 2 2 1
## 3 3 2
## 4 4 2
## 5 5 3
## 6 6 3
## 7 7 4
## 8 8 4Terlihat bahwa setiap Depo mengakomodir masing-masing 2 rute alias setiap Depo cukup mengirimkan 2 Truk. Sekarang mari kita lihat jaringan rute-rute tersebut melalui plot di bawah ini.
plot(res.md)
Dari 8 rute yang ada, rute terpendek melewati 3 kab/kota dan rute terpanjang melewati 8 kab/kota. Jika ingin tertulis nama kab/kotanya bisa menggunakan syntax annotate. Pastikan label tidak overlapping dengan koordinat maupun label lainnya agar tidak pusing melihatnya
plot(res.md) + annotate("text", x = data.pelanggan$x+0.1, y=data.pelanggan$y-0.1, label = data.pelanggan$Kab_Kota, size = 1.5)
Rangkuman Rute
Rute lengkap bisa kita lihat melalui tabel di bawah ini.
rute.mdvrp <- routes(res.md)
data.pelanggan$client <- rownames(data.pelanggan)
df.md <- merge(x = rute.mdvrp, y = data.pelanggan, by = "client", all = TRUE)
df.md <- df.md[,c("client","route_id","depot","position","Kab_Kota","Provinsi")]
df.md <- arrange(df.md, route_id, position)
df.md$depot[df.md$depot=="1"] <- "Kota Jambi"
df.md$depot[df.md$depot=="2"] <- "Muara Enim"
df.md$depot[df.md$depot=="3"] <- "Kota Palembang"
df.md$depot[df.md$depot=="4"] <- "Kota Bandar Lampung"
kable(df.md[, c(4:6,3)], booktabs = TRUE, col.names = c("Urutan","Kab/Kota","Provinsi", "Depot"), align = 'c') %>% pack_rows(
index = c("Rute 1" = nrow(df.md[df.md$route_id == 1,]),
"Rute 2" = nrow(df.md[df.md$route_id == 2,]),
"Rute 3" = nrow(df.md[df.md$route_id == 3,]),
"Rute 4" = nrow(df.md[df.md$route_id == 4,]),
"Rute 5" = nrow(df.md[df.md$route_id == 5,]),
"Rute 6" = nrow(df.md[df.md$route_id == 6,]),
"Rute 7" = nrow(df.md[df.md$route_id == 7,]),
"Rute 8" = nrow(df.md[df.md$route_id == 8,])
)
)| Urutan | Kab/Kota | Provinsi | Depot |
|---|---|---|---|
| Rute 1 | |||
| 1 | Bungo | JAMBI | Kota Jambi |
| 2 | Kerinci | JAMBI | Kota Jambi |
| 3 | Kota Sungai Penuh | JAMBI | Kota Jambi |
| 4 | Merangin | JAMBI | Kota Jambi |
| 5 | Sarolangun | JAMBI | Kota Jambi |
| Rute 2 | |||
| 1 | Muaro Jambi | JAMBI | Kota Jambi |
| 2 | Tanjung Jabung Timur | JAMBI | Kota Jambi |
| 3 | Tanjung Jabung Barat | JAMBI | Kota Jambi |
| 4 | Tebo | JAMBI | Kota Jambi |
| 5 | Batang Hari | JAMBI | Kota Jambi |
| Rute 3 | |||
| 1 | Ogan Komering Ulu | SUMATERA SELATAN | Muara Enim |
| 2 | Ogan Komering Ulu Selatan | SUMATERA SELATAN | Muara Enim |
| 3 | Kota Pagar Alam | SUMATERA SELATAN | Muara Enim |
| Rute 4 | |||
| 1 | Lahat | SUMATERA SELATAN | Muara Enim |
| 2 | Empat Lawang | SUMATERA SELATAN | Muara Enim |
| 3 | Kota Lubuklinggau | SUMATERA SELATAN | Muara Enim |
| 4 | Musi Rawas Utara | SUMATERA SELATAN | Muara Enim |
| 5 | Musi Rawas | SUMATERA SELATAN | Muara Enim |
| Rute 5 | |||
| 1 | Banyu Asin | SUMATERA SELATAN | Kota Palembang |
| 2 | Musi Banyuasin | SUMATERA SELATAN | Kota Palembang |
| 3 | Penukal Abab Lematang Ilir | SUMATERA SELATAN | Kota Palembang |
| 4 | Kota Prabumulih | SUMATERA SELATAN | Kota Palembang |
| Rute 6 | |||
| 1 | Ogan Ilir | SUMATERA SELATAN | Kota Palembang |
| 2 | Ogan Komering Ulu Timur | SUMATERA SELATAN | Kota Palembang |
| 3 | Way Kanan | LAMPUNG | Kota Palembang |
| 4 | Lampung Utara | LAMPUNG | Kota Palembang |
| 5 | Tulang Bawang Barat | LAMPUNG | Kota Palembang |
| 6 | Tulangbawang | LAMPUNG | Kota Palembang |
| 7 | Mesuji | LAMPUNG | Kota Palembang |
| 8 | Ogan Komering Ilir | SUMATERA SELATAN | Kota Palembang |
| Rute 7 | |||
| 1 | Pesawaran | LAMPUNG | Kota Bandar Lampung |
| 2 | Tanggamus | LAMPUNG | Kota Bandar Lampung |
| 3 | Pesisir Barat | LAMPUNG | Kota Bandar Lampung |
| 4 | Lampung Barat | LAMPUNG | Kota Bandar Lampung |
| 5 | Pringsewu | LAMPUNG | Kota Bandar Lampung |
| Rute 8 | |||
| 1 | Kota Metro | LAMPUNG | Kota Bandar Lampung |
| 2 | Lampung Tengah | LAMPUNG | Kota Bandar Lampung |
| 3 | Lampung Timur | LAMPUNG | Kota Bandar Lampung |
| 4 | Lampung Selatan | LAMPUNG | Kota Bandar Lampung |
Tabel di atas menunjukkan depo di suatu provinsi umumnya mengirim permintaan unit pelanggan di provinsi yang sama. Akan tetapi tidak selalu seperti itu seperti terlihat di rute 6, Depo Palembang mengirim juga pesanan ke daerah Provinsi Lampung berdasarkan jarak yang lebih dekat.
Kesimpulan
Perusahaan bisa mengirimkan permintaan 412 unit barang kepada 39 pelanggannya cukup menggunakan 8 dari 16 kendaraan yang tersedia dengan total jarak perjalanan sepanjang 2.942,7 di 3 provinsi berbeda. Masing-masing rute melakukan perjalanan sebagai berikut:
Rute 1: Depot -> Bungo -> Kerinci -> Kota Sungai Penuh ->
Merangin -> Sarolangun -> Depot
Rute 2: Depot -> Muaro Jambi -> Tanjung Jabung Timur ->
Tanjung Jabung Barat -> Tebo -> Batang Hari -> Depot
Rute 3: Depot -> Ogan Komering Ulu -> Ogan Komering Ulu Selatan
-> Kota Pagar Alam -> Depot
Rute 4: Depot -> Lahat -> Empat Lawang -> Kota Lubuklinggau
-> Musi Rawas Utara -> Musi Rawas -> Depot
Rute 5: Depot -> Banyu Asin -> Musi Banyuasin -> Penukal
Abab Lematang Ilir -> Kota Prabumulih -> Depot
Rute 6: Depot -> Ogan Ilir -> Ogan Komering Ulu Timur -> Way
Kanan -> Lampung Utara -> Tulang Bawang Barat -> Tulangbawang
-> Mesuji -> Ogan Komering Ilir -> Depot
Rute 8: Depot -> Kota Metro -> Lampung Tengah -> Lampung
Timur -> Lampung Selatan -> Depot
Referensi:
https://cran.r-project.org/web/packages/vrpr/vignettes/vrpr.html