## MODEL RUTE PERJALANAN MINIMAL DENGAN MENGGUNAKAN VEHICLE ROUTING PROBLEM PADA PT X

## Eko Sulistyono
Jurusan Matematika Fakultas Teknologi Informasi, Institut Teknologi Batam Tiban Baru, Kec. Sekupang, Kota Batam, Kepulauan Riau E-mail : eko@iteba.ac.id

## Abstract
In  this  research  discusses  the  problem  of  distributing  goods  from  a  depot  to  several  customer locations  to  minimize  travel  costs.  The  problem  is  solved  by  using  the  Vehicle  Routing  Problem method. The data used in this research is secondary data with 10 customers and one depot. The aim of this research is to form a model from the data that has been obtained and determine the optimal travel route based on the model that has been formed. The first step is to form the objective function of the problem, then form the constraints that may occur. After the model is formed, a solution to the problem is sought. The total cost of the trip is obtained by multiplying the cost of the trip per kilometer by the total distance traveled.
Keywords: Vehicle Routing Problem, Optimization, Mathematical Modeling

## Abstrak
Penelitian  ini  membahas  masalah  pendistribusian  barang  dari  suatu  depot  menuju  ke  beberapa lokasi  pelanggan  untuk  meminimumkan  biaya  perjalanan.  Permasalahan  diselesaikan  dengan menggunakan metode Vehicle Routing Problem. Data yang digunakan dalam penelitian ini adalah data sekunder dengan 10 pelanggan dan satu depot. Tujuan dalam penelitian ini adalah membentuk model  dari  data  yang  telah  diperoleh  dan  menentukan  rute  perjalanan  yang  optimal  berdasarkan model  yang  telah  dibentuk.  Langkah  pertama  membentuk  fungsi  objektif  dari  permasalahan, kemudian membentuk kendala-kendala yang kemungkinan terjadi. Setelah terbentuk model, dicari solusi  dari  permasalahan.  Total  biaya  perjalanan  diperoleh  dengan  melakukan  perkalian  biaya perjalanan perkilometer dengan total total jarak yang ditempuh.
Kata Kunci : Vehicle Routing Problem, Optimasi, Model Matematika
This work is licensed under Creative Commons Attribution License 4.0 CC-BY International license

## PENDAHULUAN

## Latar Belakang
Riset  operasi  merupakan  salah  satu cabang  ilmu  matematika.  Sejumlah permasalahan  dalam  kehidupan  sehari- hari dapat diselesaikan dengan
menggunakan  riset  operasi.  Beberapa
diantaranya  adalah  menentukan  jumlah pengiriman suatu barang untuk
mendapatkan keuntungan secara maksimal,  menentukan  penjadwalan secara  optimal,  serta  menentukan  rute terpendek  dari  suatu  perjalanan  untuk meminimumkan biaya perjalanan. Salah  satu  metode  yang  digunakan
untuk  menentukan  rute  terpendek adalah vehicle routing problem.
Vehicle routing problem (VRP)
merupakan  suatu  permasalahan  yang berfokus  pada  pendistribusian  barang dari  suatu  depot  kepada  pelanggannya [1]. Pengiriman barang ini dimulai dari suatu  kendaraan  yang  mengantarkan barang  dari  suatu  depot  ke  seluruh pelanggan  kembali  lagi  menuju  depot
setelah  barang  yang  diantar  habis  atau seluruh  pelanggan  selesai  dilayani. Tujuan dari VRP adalah meminimumkan  total  biaya  perjalanan yang  digunakan.  Dalam  penelitian  ini, dibahas  model  VRP  dari  suatu  data yang telah diperoleh, kemudian ditentukan rute perjalanan yang optimal berdasarkan model yang telah dibentuk

## Tujuan Penelitian
Penelitian ini bertujuan untuk;
1. Membentuk  model  VRP  dari  data yang telah diperoleh
2. Menentukan rute perjalanan optimal pada pengiriman barang

## TINJAUAN PUSTAKA

## Pemrograman Linear
Pemorograman linear merupakan
masalah optimasi dengan fungsi
objektifnya  merupakan  linear  dan variabel  kendala terdiri  dari persamaan linear  dan  persamaan  tak  linear  [2]. Bentuk  dari  masing-masing  kendala mungkin  berbeda  dari  masalah  yang satu  dan  lainnya.  Secara  umum pemrograman  linear  dapat  disajikan dalam bentuk sebagai berikut:
min 𝑐 1 𝑥 1 + 𝑐 2 𝑥 2 + ⋯ + 𝑐 𝑛 𝑥 𝑛
Terhadap kendala
𝑎 11 𝑥 1 + 𝑎 12 𝑥 2 + ⋯ + 𝑎 1𝑛 𝑥 𝑛 = 𝑏 1
𝑎 21 𝑥 1 + 𝑎 22 𝑥 2 + ⋯ + 𝑎 2𝑛 𝑥 𝑛 = 𝑏 2 ⋮ 𝑎 𝑚1 𝑥 1 + 𝑎 𝑚2 𝑥 2 + ⋯ + 𝑎 𝑚𝑛 𝑥 𝑛 = 𝑏 𝑚 𝑥 1 ≥ 0, 𝑥 2 ≥ 0, … , 𝑥 𝑛 ≥ 0 dengan 𝑏 𝑖 , 𝑐 𝑖 , dan 𝑎 𝑖𝑗 merupakan bilangan  real  dan 𝑥 𝑖 merupakan bilangan real yang ditentukan.

## Vehicle Routing Problem
Vehicle  routing  problem  merupakan masalah optimasi  yang berkaitan dengan pengiriman barang dengan menggunakan rute  yang  optimal  dari  suatu  depot menuju sejumlah pelanggan untuk meminimumkan
biaya perjalanan.
Terdapat  beberapa  komponen  yang berkaitan dalam VRP, yaitu [4]
1. Pelanggan
2. Depot
3. Pengemudi
4. Rute kendaraan.

## METODE PENELITIAN

## Jenis Data
Data  yang  digunakan  dalam  penelitian ini adalah data sekunder antara depot dan 10  lokasi  tujuan  yang  berasal  dari penelitian Anton et al (2021) [3].

## Sumber Data
Dalam penelitian Anton et  al. data yang digunakan  adalah  data  pengiriman  TV ukuran  32  inch.  Kendaraan yang digunakan  adalah  truk  CDE  Jumbo dengan kapasitas 271 unit TV dalam satu kali  angkut.  Selanjutnya  disajikan  jarak antara  depot  dan  10  lokasi  tujuan. Berikut  ini  disajikan  data  jarak  antara depot  dengan  10  lokasi  tujuan  (dalam Km)
Tabel 1. Jarak Antara Depot dan Pelanggan
No Ke
Dari 1 2 3 4 5 DC   SSK   SE   EC   SEJ 1 DC 0 23 17 28 19 2 SSK 23 0 9 38 9
3 SE 17 9 0 33 10 4 EC 28 38 33 0 26 5 SEJ 19 9 10 26 0
6 TUCR   32 5 12 30 11
7 ERC 22 16 15 24 7 8 TEH 56 51 45 38 38 9 GP 48 17 30 27 24
10 ECT 27 16 18 19 12
11 TPE 53 33 44 53 41 Tabel 2. Jarak Antara Depot dan pelanggan (Lanjutan) No Ke Dari 6 7 8 9 10 11 TUCR  ERC  TEH GP ECT  TPE 1 DC 32 22 56 48 27 53 2 SSK 5 16 51 17 16 33
3 SE 12 15 45 30 18 44
4 EC 30 24 38 27 19 53 5 SEJ 11 7 38 24 12 41 6 TUCR 0 27 45 17 16 29 7 ERC 27 0 36 21 9 47
8 TEH 45 36 0 23 33 67 9 GP 17 21 23 0 11 33 10 ECT 16 9 33 11 0 38 11 TPE 29 47 67 33 38 0
Berdasarkan  Tabel  1  dan  Tabel  2,  DC merupakan  depot,  sedangkan  SSK,  SE, EC,  SEJ,  TUCR,  ERC,  TEH,  GP,  ECT, dan  TPE  merupakan  lokasi  pelanggan. Biaya  perjalanan  yang  dikeluarkan  oleh perusahaan sebesar Rp. 1.300/Km.
Jumlah permintaan untuk masing pelanggan disajikan dalam tabel berikut
Tabel 3. Jumlah Permintaan Pelanggan No Nama lokasi Jumlah 1 SSK 55 2 SE 90 3 EC 87 4 SEJ 120 5 TUCR 80 6 ECR 100 7 TEH 96
8 GP 78 9 ECT 105 10 TPE 135

## HASIL DAN PEMBAHASAN

## Formulasi Permasalahan
Model Vehicle Routing Problem menggunakan  depot  sebagai  lokasi  awal dalam  pengiriman  barang.  Kemudian depot  melakukan  pengiriman  barang  di 10  lokasi.  Terdapat  satu  kendaraan  yang dapat digunakan di masing-masing depot dengan kapasitas setiap kendaraan sebanyak  271  mengakibatkan  apabila jumlah barang  yang diangkut telah habis maka  kendaraan  akan  kembali  ke  depot untuk  mengambil  kembali  persediaan barang.  Fungsi  objektif  dalam  kasus  ini adalah  meminimumkan  biaya  perjalanan sehingga  fungsi  objektifnya  adalah sebagai berikut:
min Z = ∑ ∑ ∑ 𝑐 𝑖𝑗 𝑥 𝑖𝑗 𝑘 4 𝑘=1 4 𝑗=1 4 𝑘=1
Kendala  pada  permasalahan  adalah sebagai berikut:
1. Perjalanan  kendaraan  berawal  dari depot dan mengunjungi pelanggan.
∑ 𝑥 1𝑗 𝑘 11 𝑗=2 ≤ 1, 𝑘 = 1,2,3,4 2. Perjalanan  kendaraan  kembali  ke depot setelah mengunjungi pelanggan
∑ 𝑥 𝑗1 𝑘 11 𝑗=2 ≤ 1, 𝑘 = 1,2,3,4
3. Pelanggan  dilayani  tepat  satu  kali.
Apabila telah dilayani, maka kendaraan
pergi mengunjungi pelanggan  lainnya.  Artinya  terdapat dua  perjalanan  yaitu  mengunjungi dan meninggalkan pelanggan tersebut

## untuk menuju pelanggan lainnya
∑ ∑ 𝑥 𝑖𝑗 𝑘 11 𝑖=1 4 𝑘=1 = 1, 𝑗 = 1,2, … ,11 ∑ ∑ 𝑥 𝑖𝑗 𝑘 11 𝑗=1 4 𝑘=1 = 1, 𝑖 = 1,2, … ,11
4. Jika  kendaraan  yang  mengunjungi seorang  pelanggan  maka  setelah melayani  pelanggan,  kendaraan  akan meninggalkan pelanggan
∑ 𝑥 𝑖𝑟 𝑘 11 𝑖=1 − ∑ 𝑥 𝑟𝑗 𝑘 11 𝑗=1 = 0 5. Jumlah
permintaan pelanggan dalam  suatu  waktu  tidak  melebihi kapasitas kendaraan.
∑ 𝑞 𝑗 11 𝑗=2 ∑ 𝑥 𝑖𝑗 𝑘 11 𝑖=1 ≤ 𝑄 𝑘
6. Kendaraan tidak boleh berjalan dari suatu pelanggan ke pelanggan yang sama
𝑥 𝑗𝑗 𝑘 = 0, 𝑗 = 1,2, . .11, 𝑘 = 1,2,3,4
Keterangan simbol
𝑐 𝑖𝑗 merupakan biaya perjalanan kendaraan dari 𝑖 menuju 𝑗 𝑥 𝑖𝑗 𝑘 merupakan perjalanan kendaraan dari 𝑖 menuju 𝑗 pada waktu ke- 𝑘
𝑥 𝑖𝑗 𝑘 merupakan  variabel  keputusan  yang bernilai 0 atau 1
𝑞 𝑗 merupakan jumlah permintaan pelanggan ke- 𝑗
𝑄 𝑘 merupakan kapasitas kendaraan pada waktu ke- 𝑘

## Rute Perjalanan
Berdasarkan model yang telah diperoleh,
ditentukan  penyelesaian  dengan  bantuan program sehingga diperoleh hasil sebagai berikut:
a. Waktu Perjalanan ke- 1
Untuk  waktu  perjalanan  pertama diperoleh rute perjalanan yang dimulai dari depot kemudian dilanjutkan  menuju  pelanggan  SSK dengan  jumlah  permintaan  sebanyak 55, kendaraan berjalan menuju pelanggan  TUCR  dengan  jumlah permintaan  sebanyak  80,  selanjutnya menuju  pelanggan  TPE  dengan jumlah  permintaan  135.  Jumlah pelanggan yang telah dilayani sebanyak  3  orang  dengan  jumlah permintaan  barang  sebanyak  270. Karena  jumlah  barang  yang  tersisa tidak dapat untuk memenuhi permintaan  pelanggan  lainnya  maka kendaraan  harus  kembali  ke  depot untuk mengambil barang dan mendistribusikan  barang  pada  waktu perjalanan selanjutnya.
b. Waktu Perjalanan ke- 2
Pada waktu perjalanan kedua diperoleh rute perjalanan yang dimulai dari depot  kemudian  menuju pelanggan EC dengan jumlah permintaan  sebanyak  87,  selanjutnya kendaraan berjalan menuju pelanggan GP untuk mendistribusikan  barang  sebanyak 78, kemudian pergi menuju pelanggan  TEH  dengan  jumlah permintaan  sebanyak  96.  Jumlah pelanggan  yang  telah  dilayani  pada waktu  kedua  sebanyak  3  orang dengan  jumlah  permintaan  sebanyak 261. Jumlah barang yang tersisa tidak dapat  untuk  memenuhi  permintaan pelanggan selanjutnya sehingga kendaraan  harus  kembali  ke  depot untuk mengambil barang dan mendistribusikan  barang  pada  waktu
perjalanan selanjutnya
c. Waktu Perjalanan ke- 3
Pada waktu perjalanan kedua
diperoleh rute perjalanan yang dimulai dari depot  kemudian menuju pelanggan SEJ dengan jumlah permintaan sebanyak 120, selanjutnya kendaraan berjalan menuju pelanggan SE untuk mendistribusikan  barang  sebanyak 90.  Jumlah  pelanggan  yang  telah dilayani  pada  waktu  ketiga  sebanyak 2  orang  dengan  jumlah  permintaan sebanyak  210.  Jumlah  barang  yang tersisa  tidak  dapat  untuk  memenuhi permintaan  pelanggan  selanjutnya sehingga kendaraan harus kembali ke depot  untuk  mengambil  barang  dan mendistribusikan  barang  pada  waktu perjalanan selanjutnya
d. Waktu Perjalanan ke- 4
Pada waktu perjalanan kedua
diperoleh rute perjalanan yang dimulai dari depot  kemudian menuju pelanggan  ECR  dengan  jumlah permintaan  sebanyak  100,  kemudian kendaraan berjalan menuju pelanggan ECT untuk mendistribusikan  barang  sebanyak 105.  Karena  seluruh  pelanggan  telah dilayani  maka  kendaraan  kembali  ke depot.  Jumlah  pelanggan  yang  telah dilayani pada waktu keempat sebanyak  2  orang  dengan  jumlah permintaan sebanyak 205.
Rute untuk  setiap waktu perjalanan ke- 𝑘 dapat diperlihatkan pada tabel berikut:
Tabel 4. Rute Perjalanan kendaraan pada
waktu ke- 𝑘 No Rute Perjalanan Jumlah Permintaan
1 DC-SSK-TUCR-TPE- DC 270 2 DC-EC-GP-TEH-DC 261 3 DC-SEJ-SE-DC 210 4 DC-ECR-ECT-DC 205 Jumlah 946
Total  jarak  yang  ditempuh  adalah  348 Km  dengan  biaya  perjalanan  yang dikeluarkan  adalah  Rp.452.400,-.  Total perjalanan  dan  total  biaya  untuk  masing masing  waktu  perjalanan  ke- 𝑘 disajikan pada Tabel berikut:
Tabel 5. Total Perjalanan dan biaya kendaraan pada waktu ke- 𝑘
No Rute Perjalanan Total Perjalanan (Km) Total Biaya (Rp) 1 DC-SSK-TUCR- TPE-DC 110 143000 2 DC-EC-GP- TEH-DC 134 174200 3 DC-SEJ-SE- DC 46 59800 4 DC-ECR- ECT-DC 58 75400 Jumlah 348 452400

## KESIMPULAN
Berdasarkan  penjelasan  yang  telah dipaparkan  pada  bab-bab  sebelumnya, maka dapat diambil kesimpulan sebagai berikut :
1. Model  VRP  pada  penelitian  ini adalah sebagai berikut
Fungsi Objektif
min Z = ∑ ∑ ∑ 𝑐 𝑖𝑗 𝑥 𝑖𝑗 𝑘 4 𝑘=1 4 𝑗=1 4 𝑘=1 terhadap kendala 1.   ∑ 𝑥 1𝑗 𝑘 11
𝑗=2 ≤ 1, 𝑘 = 1,2,3,4
2. ∑ 𝑥 𝑗1 𝑘 11 𝑗=2 ≤ 1, 𝑘 = 1,2,3,4 3. ∑ ∑ 𝑥 𝑖𝑗 𝑘 11 𝑖=1 4 𝑘=1 = 1, 𝑗 = 1,2, … ,11 4. ∑ ∑ 𝑥 𝑖𝑗 𝑘 11 𝑗=1 4 𝑘=1 = 1, 𝑖 = 1,2, … ,11 5. ∑ 𝑥 𝑖𝑟 𝑘 11 𝑖=1 − ∑ 𝑥 𝑟𝑗 𝑘 11 𝑗=1 = 0, 𝑘 = 1,2,34 6. ∑ 𝑞 𝑗 11 𝑗=2 ∑ 𝑥 𝑖𝑗 𝑘 11 𝑖=1 ≤ 𝑄 𝑘 , 𝑘 = 1,2,3,4 7. 𝑥 𝑗𝑗 𝑘 = 0, 𝑗 = 1,2, . .11;  𝑘 = 1,2,3,4
2. Rute  perjalanan  optimal  dalam penelitian  ini  terbagi  menjadi  4 waktu perjalanan dengan total jarak yang  ditempuh  sejauh  348  Km  dan biaya  perjalanan  yang  dikeluarkan sebesar  Rp.452.400.  Rute  untuk perjalanan  pada  waktu  pertama adalah DC-SSK-TUCR-TPE-DC. Selanjutnya  untuk  rute  perjalanan pada  waktu  kedua  adalah  DC-EC- GP-TEH-DC. Kemudian
rute perjalanan pada waktu ketiga adalah DC-SEJ-SE-DC. Rute
perjalanan  pada  waktu  keempat adalah DC-ECR-ECT-DC.

## UCAPAN TERIMA KASIH
Ucapan  terimkasih  saya  haturkan  untuk keluarga  dan  rekan  kerja  serta  seluruh civitas  akademik  di  ITEBA  yang  telah membantu  dan  memudahkan  saya  dalam menyelesaikan peneltiian ini.

## DAFTAR PUSTAKA
[1] Prasetyo, W. dan Tamyiz, M. (2017). Vehicle  Routing  Problem  dengan Aplikasi  Metode  Nearest  Neihbor, Journal of Research and Technology, 03(02),88-99.
[2] Luenberger,  D.  G.  dan  Ye,  Y. (2021). Linear and Nonlinear Programming 5 th Edition. Springer [3] Ferdiansyah,  A.,  Sholihah,  S.  A., Rifni,  M.,  Grets,  E.  S.,  Situmorang,
J.  K.,  dan  Oktaviany,  I.  (2021). Analisis Perencanaan Rute Pengiriman  Barang  Menggunakan Metode  Vehicle  Routing  Problem (VRP). [4] Amri, M., Rahman, A., dan Yuniarti,
R.  (2014).  Penyelesaian  Vehicle Routing Problem dengan Menggunakan Metode Nearest Neighbor.