ASIMETRIS: JURNAL PENDIDIKAN MATEMATIKA DAN SAINS
p-ISSN 2721 – 8724, e-ISSN 2722 – 0214
Website Jurnal: http://journal.umuslim.ac.id/index.php/asm/
Info Artikel: Disubmit pada 12 Oktober 2023 Direview pada 14 Oktober 2023
Direvisi pada 24 Oktober 2023 Diterima pada 25 Oktober 2023 Tersedia secara daring pada 31 Oktober 2023
© 2023 oleh authors. Asimetris: Jurnal Pendidikan Matematika dan Sains. Artikel ini bersifat open Access yang didistribusikan di bawah syarat dan ketentuan Creative Commons Attribution-ShareAlike 4.0 International

## IMPLEMENTASI SIMULTANEOUS PICK UP AND DELIVERY VEHICLE ROUTING PROBLEM WITH TIME WINDOWS MENGGUNAKAN INTEGER NON-LINEAR PROGRAMMING
Maya Widyastiti 1 *, Amar Sumarsa 2 1,2 Program Studi Matematika, FMIPA, Universitas Pakuan, Bogor, Indonesia Alamat email: maya.widyastiti@unpak.ac.id *
ABSTRAK. Penelitian  ini  bertujuan  untuk  mengimplementasikan  variasi  dari  model Vehicle  Routing  Problem (VRP)  untuk melakukan pendistribusian suatu barang, Rute yang dirancang untuk menentukan banyaknya kendaraan yang digunakan dan rute  terpendek  pendistribusian.  Model Pickup  and  Delivery  Vehicle  Routing  Problem  with  Time  Windows (PDVRPTW) dimodelkan dalam bentuk Integer Non-Linear Programming , dan diselesaikan menggunakan metode Branch and Bound . Model ini  digunakan  karena  dapat  menghasilkan  solusi  dalam  menyelesaikan  masalah  optimisasi  rute  dengan  batasan  tertentu. PDVRPTW  merupakan  permasalahan  rute  kendaraan  dimana  setiap  konsumen  terjadi  pengiriman  dan  pengambilan  barang sekaligus dan terdapat batasan waktu. Hasil yang diperoleh sebanyak 4 kendaraan yang digunakan. Jarak tempuh terpendek sebesar 26816 meter. Jarak tempuh kendaraan 1 sebesar 5299 meter, kendaraan 2 sebesar 6546 meter, kendaraan 3 sebesar 6684 meter dan kendaraan 4 sebesar 8287 meter. Hasil penentuan rute menggunakan metode Branch and Bound memberikan rute yang lebih baik, dimana jarak pengiriman dapat dihemat sebesar 2575 meter atau 9,6%.
Kata Kunci: Batasan Waktu, Integer Non-Linear Programming, Rute kendaraan, Pengantaran dan Pengambilan
ABSTRAK. This  study  aims  to  develop  a  model  variant  of  VRP  to  prepare  the  distribution  of  goods.  Constructing  route  to determine the number of vehicles used and the shortest route in distribution. The Pickup and Delivery Vehicle Routing Problem with Time Windows (PDVRPTW) is modeled in the form of Integer Non Linear Programming, and is solved using the Branch and Bound method. It is used because it has a solution in solving the optimal routing problem with certain limitations. PDVRPTW is a problem of vehicle where the delivery and pick up of product each customer is conducted simultaneously and there are a time windows. The results obtained were 4 vehicles used. The shortest distance is 26816 meters. The distance of 1 st vehicle is 5299 meters, 2 nd vehicle is 6546 meters, 3rd vehicle is 6684 meters and 4 th vehicle is 8287 meters. The result of route determination using Branch and Bound Method provide a better route where delivery distance can be saved by 2120 meters or 7.32%.
Keyword: Integer Non-Linear Programming, Time Windows, Simultaneous Pick up and Delivery, Vehicle Routing Problem

## I. PENDAHULUAN
Vehicle routing Problem (VRP) merupakan suatu masalah pada penentuan rute optimal dari satu  atau  lebih  sumber  (depot)  ke  sejumlah  titik lokasi  (pelanggan).  VRP  digambarkan  memiliki sejumlah  kendaraan  dengan  kapasitas  yang sama  pada  suatu  depot  dan  akan  melayani sejumlah  pelanggan.  Sejumlah  rute  akan dihasilkan  untuk  melakukan  pengiriman  barang yang dimulai dari depot ke beberapa pelanggan
dengan  menggunakan  kendaraan  tertentu,  dan berakhir  kembali  ke  depot  yang  sama.  Rute tersebut
mempertimbangkan
kapasitas kendaraan  dan  permintaan  pelanggan,  dengan tujuan meminimumkan jarak atau biaya ataupun waktu perjalanan.
Vehicle  Routing  Problem digambarkan sebagai  suatu  graf  terhubung , dengan
adalah  himpunan  tak
kosong  dari  simpul  ( vertex atau node )  dan adalah  himpunan  busur  ( edge atau arc )  yang menghubungkan  sepanjang  simpul  dalam  graf tersebut.  Simpul  didefinisikan  sebagai  sejumlah pelanggan yang akan dikunjungi, dengan indeks 1  diasumsikan  sebagai  depot,  sedangkan  busur didefinisikan  sebagai  perjalanan  atau  rute  yang menghubungkan  pelanggan i dan  pelanggan j . Menurut Adewumi & Adeleke (2016), rute optimal yang  dirancang  untuk  meminimumkan  jarak, VRP harus memenuhi batasan sebagai berikut.
1. Setiap  rute  perjalanan  berawal  dan berakhir di depot
2. Setiap pelanggan hanya dapat dikunjungi satu kali oleh satu kendaraan
3. Kendaraan  yang  digunakan  homogeny dan memiliki kapasitas tertentu
4. Permintaan  pelanggan  pada  setiap  rute perjalanan  tidak  melebihi  kapasitas kendaraan
Gambar  berikut  menjelaskan  input  dari  sebuah VRP dan solusi yang mungkin terjadi.
Gambar 1. Input VRP

## Gambar 2. Rute yang dihasilkan menggunakan VRP
Dalam  perkembangannya,  banyak  faktor- faktor  lainnya  yang  muncul.  Hal  ini  yang menyebabkan  VRP  memiliki  beberapa  variasi (Sandhya & Kumar, 2013), antara lain:
1. Capacitated VRP:  setiap  kendaraan  memiliki kapasitas yang sama dan terbatas
2. VRP  dengan  batasan  waktu  ( time  windows ): setiap  pelanggan  hanya  dapat  dilayani  pada waktu tertentu
3. Multiple depot  VRP:  Pengiriman  dilakukan dari  beberapa  depot  untuk  memenuhi permintaan pelanggan
4. Pickup  and  Delivery VRP:  Terjadi  proses pengiriman  dan  pengambilan  barang  dari pelanggan
5. Periodic VRP:  pengiriman  barang  dilakukan pada hari tertentu
6. Kombinasi dari variasi VRP yang ada, seperti multiple depot VRP with time windows VRP  telah  banyak  diteliti  sebelumnya, antara  lain  Kristina  et  al.  (2020)  yang menerapkan model
Capacitated VRP menggunakan Google OR-tools
untuk menentukan  rute  pengantaran  obat  pada perusahaan  Pedagang  Besar  Farmasi  (PBF). Hasil  yang  diperoleh  menggunakan  model  VRP lebih baik dari rute yang digunakan sebelumnya, sebesar  18,8%  untuk  jarak  mengiriman  dan 14,53% untuk biaya pendistribusian. Variasi VRP dengan time windows juga pernah diteliti dengan menggunakan algoritma genetika yang diterapkan  pada Mobile Grapari  (MOGI)  (Karim et  al.,  2018).  Implementasi  VRP  lainnya,  yaitu VRP multiple  trips pernah  diteliti  pada  masalah pengangkutan  sampah  (Widyastiti  &  Awaludin, 2021).  Selain  itu,  variasi  VRP  lain  pernah dimodelkan  dalam  bentuk Pickup  and  Delivery VRP  menggunakan  algoritma  Tabu  search, dengan penghematan biaya transportasi sebesar 13,72% daripada rute awal perusahaan (Garside &  Cahyanti,  2018).  Penelitian  mengenai  VRP lainnya  mengombinasikan  VRP time  windows, multiple product dan multiple route menggunakan algoritma Sequential insertion oleh (Putri, 2017),. Selain  untuk  meminimumkan  jarak  atau  biaya, model  VRP  juga  dapat  digunakan  untuk menentukan  banyaknya  rute  dan  armada pengangkutan  sampah  di  Kota  Bogor  oleh (Widyastiti & Kamila, 2020).
Pada  penelitian  ini  masalah Pickup  dan Delivery VRP with time windows diterapkan pada salah  satu  Usaha  Mikro  Kecil  dan  Menengah (UMKM)  yang  memproduksi  makanan  ringan yang  terletak  di  Kota  Bogor,  yaitu  Khalifah Sejahtera  Mandiri  (UMKM  KSM).  Dalam pendistribusian  makanan  ringan,  UMKM  ini
hanya mengandalkan jarak terdekat dari satu titik pengantaran  ke  titik  lainnya  atau  berdasarkan keinginan  dari  kurir  yang  mengantar  sehingga tiap  dilakukan  pengantaran  mungkin  saja  terjadi perbedaan  rute.  Hal  ini  mengakibatkan  biaya pengiriman  menjadi  tidak  menentu  dan  potensi adanya  keluhan  dari  pelanggan  bisa  terjadi karena  dikirim  tidak  sesuai  waktu  yang diharapkan.  Oleh  karena  itu,  diperlukan  adanya rute yang tepat sehingga biaya pengiriman dapat seminimal  mungkin  dan  keuntungan  yang diperoleh dapat menjadi maksimal.

## II. METODE PENELITIAN
Metode Branch and Bound Prinsip  dasar  metode Branch  and  Bound adalah  memecah  daerah  fisibel  suatu  masalah LP-relaksasi  dengan  membuat subproblem- subproblem (Nur  &  Abdal,  2017).  Ada  dua konsep dasar dalam metode ini , yaitu branching dan bounding . 1. Branching, yaitu
proses membagi permasalahan menjadi subproblem- subproblem  yang  mungkin  mengarah  ke solusi.
2. Bounding, yaitu  proses  untuk  menghitung batas  atas  (kasus  minimisasi)  dan  batas bawah  (kasus  maksimisasi)  untuk  solusi optimal pada subproblem yang mengarah ke solusi.
Berikut  ini  adalah  langkah-langkah penyelesaian  suatu  masalah  dengan  metode branch and bound (Nur & Abdal, 2017).
1. Selesaikan  masalah  program  linear  dengan metode  simpleks  selesaikan  masalah  tanpa pembatasan bilangan integer.
2. Teliti  solusi  optimalnya,  jika  variabel keputusan  yang  diharapkan  adalah  bilangan integer, solusi optimum integer telah tercapai. Jika satu atau lebih variabel keputusan yang diharapkan  ternyata  bukan  bilangan  integer, lanjutkan ke langkah 3.
3. Jadikan  solusi  pada  penyelesaian  langkah  1 menjadi  batas  atas  dan  untuk  batas bawahnya  merupakan  solusi  yang  variabel keputusannya  telah  diintegerkan  (rounded – down).
4. Pilih  variabel  yang  mempunyai  nilai  pecahan terbesar  (artinya  bilangan  desimal  terbesar dari  masing-masing  variabel  untuk  dijadikan pencabangan  ke  dalam  beberapa  sub- masalah. Tujuannya
adalah
untuk menghilangkan  solusi  yang  tidak  memenuhi persyaratan  integer  dalam  masalah  itu. Pencabangan  itu  dilakukan  secara  mutually exclusive  untuk  memenuhi  persyaratan integer dengan jaminan tidak ada solusi fisibel (layak)  yang  diikutsertakan.  Hasilnya  adalah sebuah sub masalah dengan batasan ≤ atau batasan ≥ .
5. Untuk  setiap  sub-masalah,  nilai  optimum fungsi  tujuan  ditetapkan  sebagai  batas  atas. Solusi  optimum  yang  diintegerkan  menjadi batas  bawah  (solusi  yang  sebelumnya  tidak integer kemudian diintegerkan). Untuk semua sub-  masalah  yang  memiliki  batas  atas kurang  dari  batas  bawah  yang  ada,  tidak diikutsertakan  pada  analisa  selanjutnya. Suatu  solusi  integer  fisibel  (layak)  adalah sama  baik  atau  lebih  baik  dari  batas  atas untuk  setiap  sub  masalah  yang  dicari.  Jika solusi  yang  demikian  terjadi,  suatu  sub masalah  dengan  batas  atas  terbaik  dipilih untuk dicabangkan. Kembali ke langkah 4.

## III. HASIL PENELITIAN DAN PEMBAHASAN
Data  yang  digunakan  berupa  data  lokasi tiap kios makanan beserta jaraknya. UMKM KSM dijadikan sebagai depot, dimana kendaraan yang digunakan  akan  dimulai  dan  berakhir  di  UMKM KSM ini. Lokasi UMKM KSM ini selanjutnya akan diberi indeks 1. Kios yang menjualkan makanan ringan  dari  UMKM  KSM  ini  merupakan  tujuan pengiriman  dan  pengambilan  makanan  ringan yang  tidak  laku  terjual  sebanyak  31  kios,  dan diberi  indeks  2-32.  Data  jarak  antar  lokasi diperoleh dengan  bantuan google  maps dengan mempertimbangkan  jalur  yang  dapat  dilalui  oleh kendaraan  milik  UMKM  KSM.  Jarak  dari  kios satu ke kios lainnya diasumsikan berupa matriks simetri,  artinya  jarak  dari  kios    ke  kios    sama dengan  jarak  dari  kios    ke  kios    ( ). UMKM  ini  memiliki  7  kendaraan  yang  tersedia,
dengan kapasitas yang sama, yaitu 200 bungkus makanan ringan. Pada penelitian ini, tidak semua kendaraan  akan  digunakan  dalam  proses pengiriman  dan  pengambilan  makanan  ringan. Selain  itu,  kecepatan  dari  kendaraan  juga diasumsikan  sama,  yaitu  30  km/jam  atau  500 meter/menit.
Pada  penelitian  ini  setiap  kios  memiliki banyaknya  permintaan  makanan  ringan  yang harus  dikirim  dan  diambil, yang  sudah  diketahui
sebelumnya  dan  harus  terpenuhi.  Setiap  kios juga  memiliki  batasan  waktu  ( time  windows ) untuk dilayani. Hal ini menunjukkan bahwa setiap kios  hanya  dapat  dilayani  pada  selang  waktu tertentu.  Data  banyaknya  yang  dikirim  ( ), banyaknya  yang  diambil  ( ,  waktu  pelayanan ( ),  waktu  tercepat  ( )  dan  waktu  terlama  ( ) dari setiap kios dapat dilihat pada Tabel 3.1.
Tabel 3.1 Data banyaknya pengiriman dan pengambilan, waktu pelayanan, waktu tercepat dan terlama

## Formulasi Matematika Parameter
= jarak dari kios   ke kios = waktu tempuh dari kios   ke kios
= banyaknya pengiriman di kios
= banyaknya pengambilan di kios = kapasitas kendaraan
= rata-rata kecepatan kendaraan
= waktu kios   dilayani
= lama pelayanan di kios
= waktu tercepat kios  dilayani
= waktu terlama kios   dilayani
= konstanta riil yang bernilai relatif besar
Variabel Keputusan , bernilai 1 jika kendaraan-i digunakan, dan bernilai 0 jika lainnya
, bernilai 1 jika ada perjalanan dari kios-i ke kios-j menggunakan kendaraan-k, dan bernilai 0 jika lainnya , bernilai 1 jika banyaknya barang yang dikirimkan dari kios-i ke kios-j menggunakan kendaraan k
, bernilai 1 jika banyaknya barang yang
diambil dari kios-i ke kios-j menggunakan kendaraan k

## Fungsi Objektif
a.  Penentuan  Banyaknya  kendaraan  yang digunakan,  yaitu  meminimumkan  banyaknya kendaraan  dalam  pendistribusian  makanan. Formulasi  dari  fungsi  objektif  adalah  sebagai berikut. (Widyastiti & Kamila, 2020)
Kios ke- Kios ke- 1 0 0 0 0 0 17 23 23 90 300 5 2 12 27 0 300 5 18 17 23 90 300 5 3 24 24 0 300 5 19 24 22 90 540 5 4 13 29 0 300 5 20 23 21 90 540 5 5 19 15 60 300 5 21 23
21 90 540 5 6 16 28 60 300 5 22 21
14 120 540 5 7 23 12 60 300 5 23 13
23 120 540 5 8 11 18 60 300 5 24 24
21 120 540 5 9 25 13 60 300 5 25 21
16 120 540 5 10 14 22 60 300 5 26 21
29 120 540 5 11 19 20 60 300 5 27 16
14 120 540 5 12 24 27 90 300 5 28 16
26 120 540 5 13 10 19 90 300 5 29 19
13 120 540 5 14 14 11 90 300 5 30 20
13 120 540 5 15 16 16 90 300 5 31 13
15 120 540 5 16 11 16 90 300 5 32 21
19 120 540 5
(1)
b. Penentuan rute optimal, yaitu meminimumkan total  jarak  tempuh  kendaraan.  Formulasi  dari fungsi objektif adalah sebagai berikut. (Widyastiti & Kamila, 2020)
(2)

## Kendala
1.  Tidak  semua  kendaraan  akan  keluar  dari depot, artinya hanya kendaraan yang terpilih saja yang  akan  digunakan  untuk  mengantar  dan mengambil makanan ringan di kios
(3) 2. Setiap kios hanya dikunjungi satu kali. Proses kunjungan
meliputi
pengantaran dan pengambilan makanan ringan yang tidak terjual
(4)
3.  Kekontinuan  Rute,  artinya  bahwa  setiap kendaraan  yang  mengunjungi  suatu  kios  maka kendaraan  tentu  akan  meninggalkan  kios tersebut
(5)
4.  Banyaknya  makanan  ringan  yang  dikirim  dan diangkut sesuai dengan data di kios tersebut
(6)
5.  Kendala  kapasitas  kendaraan,  artinya banyaknya  makanan  ringan  yang  akan  dikirim dan  diambil  dari  suatu  kios  tidak  melebihi kapasitas kendaraan yang digunakan
(7)
6. Waktu kios mulai dilayani. Waktu suatu kios j akan  dilayani  dapat  dihitung  berdasarkan penjumlahan  dari  waktu  pelayanan  kios sebelumnya (kios i ), lamanya waktu pelayanan di kios i dan waktu temppuh dari kios i ke kios j.
(8) 7.  Memastikan  setiap  kios  akan  dilayani  pada waktu yang telah ditentukan
(9)
8. Kendala bilangan bulat dan kenonnegatifan dan integer
(10)
9. Kendala Binary dan
(11)
Dalam  proses  penyelesaiannya,  model Pickup  and  Delivery  Vehicle  Routing  Problem with  Time  Windows dimodelkan  dalam  bentuk Integer  Non-Linear  Programming .  Formulasi yang  dibentuk  kemudian  diselesaikan  dengan bantuan  perangkat  lunak  berbasis  fungsional
menggunakan metode Branch and Bound . Hasil yang diperoleh sebanyak 4 kendaraan digunakan untuk  mendistribusikan  makanan  ringan  dari depot  ke  kios  dengan  jarak  tempuh  terpendek
sebesar  26816  meter.  Hasil  rute  yang  diperoleh dengan menggunakan model Integer Non-Linear Programming dapat dilihat pada Tabel 3.2.
Tabel 3.2 Hasil Rute menggunakan Model Integer Non-Linear Programming
Kendaaraan ke-  Dilayani Ke-  Kios ke-  Total Jarak  Kendaaraan ke-  Dilayani Ke-  Kios ke-  Total Jarak 1 1 1 0 2 1 1 0 2 19 501 2 17 592 3 13 1009 3 16 1158 4 20 1534 4 22 1740 5 21 2091 5 11 2271 6 32 2879 6 2 3053 7 3 3490 7 8 3894 8 14 4369 8 10 5766 9 1 5299 9 1 6546 3 1 1 0 4 1 1 0 2 12 609 2 15 675 3 28 965 3 5 1313 4 18 1465 4 6 1937 5 7 2170 5 26 2527 6 24 2845 6 25 3071 7 29 3448 7 27 4207 8 4 4163 8 23 5031 9 9 4762 9 31 5540 10 30 5445 10 1 8287 11 1 6684 Total Jarak Tempuh 26816
Pada  Tabel  3.2  dapat  dilihat  bahwa kendaraan 1 melayani 7 kios dengan menempuh jarak minimum sebesar 5299 meter, dengan rute pendistribusian  dari  depot-kios  19-kios  13-kios 20-kios  21-kios  32-kios  3-kios  14-depot. Kendaraan  2  mengirimkan  dan  mengambil makanan  ringan  ke  7  kios,  yang  dimulai  dari depot-kios 17-kios 16-kios 22-kios 11-kios 2-kios 8-kios  10-depot  dengan  total  jarak  minimum sebesar
6546
meter. Kendaraan 3 mendistribusikan  makanan  ringan  ke  9  kios dengan  jarak  minimum  sebesar  6684  meter dengan rute depot-kios 12-kios 28-kios 18-kios 7- kios  24-kios  29-kios  4-kios  9-kios  30-depot. Untuk  kendaraan  4,  makanan  ringan  dikirimkan ke 8 kios lainnya dari depot-kios 15-kios 5-kios 6- kios  26-kios  25-kios  27-kios  23-kios  31-depot dengan jarak minimum sebesar 8287 meter.
Selanjutnya,  pengiriman  ke  kios  13, mengantar  10  makanan  ringan  dan  mengambil 19  makanan  yang  tidak  terjual.  Kendaraan  1
membawa 146 makanan ke kios 20. Di kios 20, makanan ringan dikirimkan sebanyak 23 unit dan mengambil  21  unit  makanan  yang  tidak  terjual sehingga  banyaknya  makanan  yang  diangkut kendaraan  1  sebanyak  144.  Pengiriman dilanjutkan  ke  kios  21,  dengan  mengirimkan  23 unit  dan  mengambil  21  unit.  Pengiriman selanjutnya  ke  kios  32,  dengan  makanan  baru yang dikirim sebanyak 21 unit dan mengambil 19 unit makanan ringan yang tidak terjual, sehingga pada kendaraan 1 mengangkut makanan ringan sebanyak  140  unit.  Selanjutnya,  pengiriman menuju  kios  3  dengan  makanan  yang  dikirim sebanyak  24  unit  dan  diambil  sebanyak  24  unit sehingga  kendaraan  1  mengangkut  makanan ringan  sebanyak  140  unit  menuju  ke  kios  14. Kunjungan  ke  kios  terakhir  adalah  kios  14 dengan mengirimkan 14 unit makanan baru dan mengambil  11  unit  makanan  ringan  yang  tidak terjual  sehingga  total  makanan  yang  diangkut oleh  mobil  1  sebanyak  137.  Pada  kendaraan
kedua,  pendistribusian  awal  membawa  111  unit dan  selanjutnya  mengirimkan  dan  mengambil makanan  ke  8  kios  lainnya  sehingga  di  akhir pendistribusian  kendaraan  2  membawa  140 makanan  ringan.  Kendaraan  ketiga  membawa makanan  ringan  sebanyak  181  unit  dan mengambil makanan ringan yang tidak terjual ke kios 12, 28, 18, 7, 24, 29, 4, 9 30, dan  kembali lagi  ke  depot  dengan  membawa  168  unit
makanan yang tidak terjual. Kendaraan keempat mengirimkan  sebanyak  135  unit  ke  8  kios,  dan mengambil 156 unit makanan yang tidak terjual. Hal  ini  menunjukkan  bahwa  pendistribusian makanan  ringan  tidak  melebihi  kapasitas kendaraan  yaitu  200  unit. Secara  lengkap, hasil pendistribusian berdasarkan
kapasitas kendaraan dapat dilihat di Tabel 3.3.
Tabel 3.3 Hasil Kapasitas Kendaraan menggunakan Model Integer Non-Linear Programming
Kendaaraan ke-  Kios ke- Jumlah Kendaaraan ke-  Kios ke- Jumlah Antar  Ambil  Total Antar  Ambil  Total 1 1 139 0 139 2 1 111 0 111 19 115 22 137
17 88 23 111 13 105 41 146
16 77 39 116 20 82 62 144
22 56 53 109 21 59 83 142
11 37 73 110
32 38 102 140
2 25 100 125
3 14 126 140
8 14 118 132
14 0 137 137
10 0 140 140 1 0 137 137
1 0 140 140 3 1 181 0 181 4 1 135 0 135
12 157 27 184 15 119 16 135 28 141 53 194 5 100 31 131
18 124 76 200 6
84 59 143
7 101 88 189 26
63 88 151
24 77 100 177 25 42 104 146
29 58 113 171 27 26 118 144
4 45 142 187 23 13 141 154
9 20 155 175 31
0 156 156 30 0 168 168
1 0 156 156 1 0 168 168

## Rute Awal Perusahaan
Rute  awal  yang  digunakan  oleh  UMKM KSM  yaitu  berdasarkan  jarak  terdekat  dari  kios, tanpa  mempertimbangkan  waktu.  Pada  rute sebelumnya,  UMKM  KSM  menggunakan  4 kendaraan,  dengan  rincian  kendaraan  1 mengirimkan  makanan  ringan  ke  8  kios, kendaraan 2 mengirimkan ke 9 kios, kendaraan 3 mengirimkan  ke  8  kios,  dan  kendaraan  4 mengirimkan  ke  6  kios.  Total  jarak  tempuh  dari keempat  kendaraan  sebesar  29391  meter, dengan  masing-masing  kendaraan  menempuh jarak  sebesar  7056  meter,  8196  meter,  6583 meter  dan  7556  meter.  Untuk  kapasitas
kendaraan,  kendaraan  1  mengirimkan  makanan ringan  sebanyak  161  unit  dan  mengambil makanan ringan sebanyak 161 unit. Kendaraan 2 mengirimkan  166  unit  dan  mengambil  163  unit yang  tidak  terjual.  Kendaraan  3  mengambil  126 unit  dan  mengambil  167  unit  yang  tidak  terjual, sedangkan untuk kendaraan 4 mengirimkan 113 unit dan mengambil 110 unit makanan yang tidak terjual. Hal ini dapat terlihat bahwa dari keempat kendaraan yang digunakan untuk mengantar dan mengambil  makanan  ringan  tidak  melebihi  dari kapasitas  kendaraan,  yaitu  200  unit.  Rute  yang digunakan dan kapasitas kendaraan dapat dilihat pada Tabel 3.4 dan Tabel 3.5.
Tabel 3.4 Rute yang digunakan oleh UMKM KSM
Kendaaraan ke-  Dilayani Ke-  Kios ke-  Total Jarak  Kendaaraan ke-  Dilayani Ke-  Kios ke-  Total Jarak
1 1 1 0 2 1 1 0 2 19 501 2 12 609 3 13 1009 3 28 965 4 20 1534 4 18 1465 5 21 2091 5 7 2170 6 17 2822 6 24 2845 7 30 3543 7 29 3448 8 4 4201 8 16 5540 9 9 4800 9 8 6158 1 7056 10 25 6702 1 8196 3 1 1 0 4 1 1 0 2 15 675 2 14 930 3 5 1313 3 3 1809 4 6 1937 4 32 2420 5 26 2527 5 22 3349 6 27 3287 6 11 3880 7 23 4111 7 10 6776 8 31 4620 1 7556 9 2 5465 1 6583 Total Jarak Tempuh 29391 Tabel 3.5 Hasil Kapasitas Kendaraan menggunakan rute yang digunakan oleh UMKM KSM Kendaaraan ke-  Kios ke- Jumlah Kendaaraan ke-  Kios ke- Jumlah Antar  Ambil  Total Antar  Ambil  Total 1 1 161 0 161
2 1 166 0 166 19 137 22 159
12 142 27 169 13 127 41 168
28 126 53 179 20 104 62 166
18 109 76 185 21 81 83 164
7 86 88 174 17 58 106 164 24
62 100 162 30 38 119 157 29 43 113 156 4 25 148 173
16 32 129 161 9 0 161 161
8 21 147 168 1 0 161 161
25 0 163 163 1 0 163 163 3 1 126 0 126
4 1 113 0 113 15 110 16 126 14
99 11 110 5 91 31 122
3 75 35 110 6 75 59 134
32 54 54 108 26 54 88 142
22 33 68 101 27 38 102 140
11 14 88 102
23 25 125 150
10 0 110 110 31 12 140 152
1 0
110 110 2 0 167 167 1 0 167 167
Perbandingan Rute Awal dan Rute Usulan
Perbandingan  jarak  tempuh  pada  rute awal yang digunakan oleh UMKM KSM dan rute
usulan
menggunakan integer non-linear programming dapat dilihat pada Tabel 3.6.
Tabel 3.6 Perbandingan Rute Awal dan Rute Usulan Rute yang digunakan Rute Awal  Rute Usulan Rute 1 7056 5299 Rute 2 8196 6546 Rute 3 6583 6684 Rute 4 7556 8287 Total 29391 26816
Berdasarkan  tabel  tersebut  dapat  dilihat bahwa  total  jarak  tempuh  yang  dihasilkan menggunakan  integer  non-linear  programming lebih  baik  dibandingan  dengan  rute  awal  yang digunakan  oleh  UMKM  KSM,  dengan  selisih jarak tempuh sebesar 2575 meter atau 9,6%.
Pada  penelitian  sebelumnya  yang  telah dilakukan oleh (Raipuriya & Gupta, 2020), model integer  non  linear  programming  memberikan hasil  yang  efektif  dalam  menyelesaikan  kasus VRP. Pada penelitian ini, bentuk yang digunakan adalah  Mixed  Integer  Non  Linear  Programming. Hal ini menunjukkan bahwa  bentuk  integer non- linear  programming  dapat  digunakan  untuk menyelesaikan  masalah Vehicle  Routing Problem dengan efektif.

## IV. SIMPULAN
Model Simultaneous Pickup  and  Delivery Vehicle  Routing  Problem  with  Time  Windows dapat  dimodelkan  dalam  bentuk Integer  Non- Linear  Programming dengan  bantuan  perangkat lunak  berbasis  fungsional  menggunakan  metode Branch  and  Bound .  Sebanyak  4  kendaraan digunakan  untuk  mendistribusikan  makanan ringan  dari  depot  ke  kios.  Jarak  tempuh terpendek yang dihasilkan sebesar 26816 meter, dengan  rincian  kendaraan  1  menempuh  jarak minimum  sebesar  5299  meter,  dengan  rute pendistribusian  dari  depot-kios  19-kios  13-kios 20-kios  21-kios  32-kios  3-kios  14-depot. Kendaraan  2  mengirimkan  dan  mengambil makanan  ringan  dari  depot-kios  17-kios  16-kios 22-kios  11-kios  2-kios  8-kios  10-depot  dengan total  jarak  minimum  sebesar  6546  meter. Kendaraan  3  mendistribusikan  makanan  ringan dengan  jarak  minimum  sebesar  6684  meter
dengan rute depot-kios 12-kios 28-kios 18-kios 7- kios 24-kios 29-kios 4-kios 9-kios 30-depot. Untuk kendaraan 4, makanan ringan dikirim dari depot- kios 15-kios 5-kios 6-kios 26-kios 25-kios 27-kios 23-kios 31-depot dengan jarak minimum sebesar 8287.  Rute  yang  menggunakan  metode Branch and Bound menghasilkan total jarak tempuh yang lebih pendek jika dibandingkan dengan rute awal yang  digunakan  oleh  UMKM  Khalifah  Sejahtera Mandiri  yaitu  29391  meter,  atau  selisih  jarak sebesar 2575 meter atau 9,6%.

## DAFTAR PUSTAKA
Adewumi, A. O., & Adeleke, O. J. (2016). A new model for optimizing waste disposal based on  customers’  time  windows  and  road attributes. Applied Mathematical Sciences , 10 , 2051 – 2063. https://doi.org/10.12988/ams.2016.63114 Garside,  A.  K.,  &  Cahyanti,  D.  N.  (2018). Penyelesaian  Vehicle  Routing  Problem with  Simultaneous  Pick  Up  and  Delivery dengan  Algoritma  Tabu  Search. Jurnal Ilmiah  Teknik  Industri , 17 (2),  125. https://doi.org/10.23917/jiti.v17i2.6703
Karim,  M.  K.,  Setiawan,  B.  D.,  &  Adikara,  P.  P. (2018). Optimasi Vehicle Routing Problem With Time Windows (VRPTW) Pada Rute Mobile Grapari (MOGI) Telkomsel Cabang Malang Menggunakan Algoritme Genetika. Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer , 2 (8), 2702 – 2709. Kristina, S., Sianturi, R. D., & Husnadi, R. (2020). Penerapan  Model  Capacitated  Vehicle Routing  Problem  (CVRP)  Menggunakan Google  OR-Tools  untuk  Penentuan  Rute Pengantaran  Obat  pada  Perusahaan Pedagang  Besar  Farmasi  (PBF). Jurnal Telematika , 15 (2), 101 – 106. Nur,  W.,  &  Abdal,  N.  M.  (2017).  Penggunaan Metode  Branch  and  Bound  dan  Gomory Cut  dalam  Menentukan  Solusi  Integer Linear  Programming. SAINTIFIK , 2 (1),  9 – 15. https://doi.org/10.31605/saintifik.v2i1.91
Putri,  D.  A.  P.  (2017).  Vehicle  Routing  Problem Dengan  Time  Window  Untuk  Multiple Product Dan Multiple Route Menggunakan Algoritma  Sequential  Insertion.
Jurnal Teknik Industri , 17 (1), 22.
https://doi.org/10.22219/JTIUMM.Vol17.No 1.22-30 Raipuriya,  M.,  &  Gupta,  R.  (2020).  On  Vehicle routing Problem using Mixed Integer Non- Linear Programming. International Journal for Research in Engineering Application & Management ,
06 (01),
32 – 34. https://doi.org/10.35291/2454- 9150.2020.0251 Widyastiti,  M.,  &  Awaludin,  M.  (2021). Implementasi  Vehicle  Routing  Problem with  Multiple  Trips  pada  Masalah Pengangkutan Sampah. Limits: Journal of Mathematics  and  Its  Applications , 18 (1),
45 – 56. https://doi.org/10.12962/limits.v18i1.6038 Widyastiti, M., & Kamila, I. (2020). Model Vehicle Routing  Problem  Dalam  Menentukan
Banyaknya Rute Dan Armada Pengangkutan  Sampah  Di  Kota  Bogor. EKOLOGIA , 19 (1),
39 – 43. https://doi.org/10.33751/ekol.v19i1.1661