## Vehicle Routing Problem by Combining Nearest Neighbour and Local Search
Kurnia Iswardani 1 , ira aprilia 2 , Dwi Putri K 3
1,2,3 Universitas Panca Marga,
1 kurnia.iswardani@upm.ac.id, 2 ira.aprilia11@upm.ac.id, 3 dwiputri@upm.ac.id
Abstract. PT. X is a company tasked with distributing Elpiji Gas to major agents. The  problem  under  study  is  to  find  a  more  optimal  distribution  route  so  it  can maximize the  use of other resources, for example the number of trucks used. This distribution  problem  will  be  solved  by  a  combination  two  methods,  Nearest Neighbor and Local Search with the hope of getting the shortest route. The way the Nearest  Neighbor  method  works  is  selecting  the  Agent's  location  based  on  the shortest  distance  from  the  last  location  and  improving  the  solution  using  Local Search (intra-route insertion (1-0)) by moving one customer's position in one route so that a good distribution route is produced.
Keywords: Vehicle Routing Problem, Nearest Neighbour, Local Search
Abstrak. PT. X merupakan perusahaan yang bertugas mendistribusikan Gas Elpiji kepada  Agen-Agen  Besar.  Persoalan  yang  diteliti  yaitu  mencari  rute pendistribusian  produk  yang  lebih  optimal  sehingga  bisa  memaksimalkan penggunaan  sumber  daya  yang  lainnya,  salah  satunya  adalah  jumlah  truk  yang digunakan.Persoalan pendistribusian ini  akan  diselesaikan dengan  kombinasi  dua metode yaitu Nearest Neighbour dan Local Search dengan harapan didapatkan rute terpendek.  Cara  kerja  metode Nearest  Neighbour adalah  pemilihan  lokasi  Agen berdasarkan  jarak  terdekat  dari  lokasi  terakhir  dan  perbaikan  solusi  dilakukan dengan  menggunakan Local  Search ( insertion  intra-route (1-0))  dengan memindahkan  posisi  satu  pelanggan  dalam  satu  rute  sehingga  dihasilkan  rute distribusi yang baik.
Kata Kunci: Vehicle Routing Problem, Nearest Neighbour, Local Search

## 1  Pendahuluan
Pelaku  bisnis  saat  ini  tengah  memasuki  era  persaingan  yang  begitu  ketat, persaingan bisnis yang begitu kompetitif merupakan salah satu resiko  yang perlu ditangani  dengan  solusi  penyelesaian  yang  tepat.  Setiap  pelaku  usaha  dituntut untuk  terus  mampu  bertahan,  dan  selalu  merumuskan  berbagai  strategi  dalam menghadapi  persaingan  bisnis.  Strategi  yang  digunakan  oleh  perusahaan  harus mampu dalam menciptakan keunggulan kompetitif [1].
Salah  satu  dimensi  keunggulan  kompetitif  perusahaan  adalah  kendala pengiriman  produk  ( dependable  delivery ),  baik  dari  pihak  pemasok  kepada perusahaan  ataupun  dari  pihak  perusahaan  kepada  konsumen.  Berdasarkan  hal tersebut  diketahui  bahwa  peran  manajemen  rantai  pasok  ( Supply  Chain

## Unisda Journal of Mathematics and Computer Science
Management ) memiliki posisi penting bagi sebuah perusahaan. Terdapat 3 bagian dalam Supply Chain Management yakni Upstream Supply Chain , Internal Supply Chain ,  dan Downstream  Supply  Chain .  Salah  satu  yang  akan  menjadi  pokok pembahasan  dalam  penelitian ini adalah bagian Downstream  Supply  Chain yang mencakup   kegiatan   penyimpanan,   distribusi   produk,   dan   pemasaran   produk hingga sampai kepada konsumen akhir [2].
Pendistribusian  produk  dari  tangan  produsen  hingga  sampai  ketangan konsumen,  perlu  dilakukan  dengan  strategi  yang  baik  dengan  memperhatikan efektivitas waktu dan efisiensi biaya. Dalam teori transportasi di jelaskan terdapat 5  unsur  di  dalam  proses  kinerja  transportasi  yakni  terdapat  muatan,  kendaraan, jalur atau rute, lokasi awal tujuan, dan manajemen [3].
Berfokus  pada  pendistribusian  gas  elpiji  3  kg  pada  PT.  X  yang  hanya melakukan pengiriman tabung gas elpiji 3 kg. Pendistribusian dilakukan di 8 agen yang  terletak  di  7  Kecamatan  wilayah  Probolinggo  dengan  menggunakan  4 kendaraan  berkapasitas  560  tabung.  Setiap  agen  menerima  kiriman  per  hari tergantung LO yang ditebus atau yang mendapatkan izin resmi dari PERTAMINA. Pedistribusian  gas  elpiji  kepada  agen  dilakukan  selama  jam  kerja  PT.  X berlangsung  yakni  dari  mulai  pukul  07:00  hingga  selesai  pengiriman,  sesuai karakteristik Vehicle Routing Problem (VRP) [4].Berdasarkan latar belakang di atas akan dilakukan analisis penentuan rute distribusi gas elpiji 3 kg terhadap PT. X dengan menggunakan metode Nearest Neighbour dan Local Search .

## 2  Metode Penelitian

## 2.1   Perancangan Penelitian
Pada penelitian ini peneliti akan menggunakan jenis penelitian Survei yang menggunakan  test  sebagai  instrumen  pengumpulan  datanya  dengan  tujuan  untuk mendapatkan informasi tentang sejumlah responden untuk menguji hipotetis yang diajukan.  Menurut  [5]“Metode  survey  yang  digunakan  untuk  mendaptkan  data dari  tempat  tertentu  yang  alamiah  (bukan  buatan),  tetapi  peneliti  melakukan perlakuan  dalam  pengumpulan  data,  misalnya  dengan  mengedarkan  kuesioner, test, wawancara terstruktur dan sebagainya”. Metode survei merupakan penelitian yang  mendapatkan  sampel  dari  suatu  populasi  dan  menggunakan  kuesioner sebagai alat pengumpulan data yang utama.

## 2.2   Jenis Sumber Data
Terdapat  dua  jenis  data  yang  diperlukan  dalam  penelitian  ini,  diantaranya yaitu data kualitatif dan  data kuantitatif. Data kualitatif mencakup informasi dari PT. X objek penelitian yang digunakan. Informasi tersebut mencakup profil yakni, sejarah pendirian, struktur keorganisasian, dan data historis proses pendistribusian tabung gas elpiji 3 kg yang telah dilakukan. Sedangkan data kuantitatif mencakup datahasil  pengukuran  jaark  tempuh  pengiriman,  waktu  dalam  proses pendistribusian    tabung    gas    elpiji    3    kg    kepada    pelanggan,    data    kecepatan kendaraan  yang  digunakan  dalam  proses  pengiriman,  data  kapasitas  muatan armada kendaraan yang dimiliki PT. X.

## Unisda Journal of Mathematics and Computer Science
2.3   Teknik Pengumpulan Data
Dalam proses pengumpulan data yang diperlukan dalam kegiatan penelitian, teknik  yang  digunakan  adalah  observasi  langsung  kepada  PT.  X.  Dari  proses observasi  tersebut  dapat  diperoleh  data  keseluruhan  yang  diperlukan  untuk dilakukan proses analisis penentuan rute distribusi.

## 2.4 Metode Analisis Data

## 2.4.1  Analisis Data Menggunakan Metode Nearest Neighbour
Proses  analisis  data  dalam  menentukan  rute  distribusi  dengan  metode
Nearest  Neighbour ,  metode  ini  terdiri  dari  beberapa  langkah  yang  harus dilaksanakan [6], diantaranya :
Langkah 1 : Input data permintaan setiap agen ( Di ), jarak antara depot ke agen dan agen pelanggan, horison perencanaan ( H ), waktu Loading ( LT )
dan Unloading ( UT ). Lanjutkan ke langakah 2.
Langkah 2 :  Inisialisasi awal, rute ( r = 1) dan tur ( t = 1). Lanjutkan ke langkah 3. Langkah 3 :  Lokasi awal dari depot . Lanjutkan ke langkah 4 Langkah 4 : Melakukan proses loading gas elpiji 3 kg, LT = 30 menit, kapasitas ( Q ) = 560 tabung gas, lanjutkan ke langkah 5.
Langkah 5 : Cari agen yang memiliki jarak terpendek dari lokasi terakhir, lanjut ke langkah 6.
Langkah  6 :  Jika Q < Di ,  jumlah  Gas  yang  dipenuhi  adalah  sejumlah Q dan lanjutkan  ke  langkah  8,  jika Q > Di maka  jumlah  Gas  yang diepenuhi  sejumlah  permintaan  agen  ( Di ),  kemudian  tandai  agen telah terlayani dan lanjutkan ke langkah 7.
Langkah 7 : Menghitung nilai Q yang tersisa, Q = Q – Di , lanjutkan ke langkah 8.
Langkah 8 : Hitung Unloading Time ( UT ), Completion Time ( CT ) dan, lanjut ke langkah 9.
UT = Di* 0.05 Menit = UT (1) Langkah  9 :  Jika CT <  9  jam  maka  lanjutkan  ke  langkah  10,  jika  tidak  maka kalian batalkan agen terakhir dan lanjutkan ke langkah 10.
Langkah 10 : Jika Q > 0, jika ya lanjutkan ke langkah 14, jika tidak lanjutkan ke langkah 11.
Langkah 11 : Buat rute baru ( r ), r = r + 1. Kembali ke langkah 3. Langkah 12 : Buat tur baru ( t ), t = t + 1. Kembali ke langkah 3. Langkah 13 : Jika semua agen sudah terlayani terlayani, lanjutkan ke langkah 14, jika   tidak ke langkah 4.
Langkah 14 : Rute dan tur sudah terbentuk, prosedur selesai.

## 2.4.2 Analisis Perbaikan Rute denganAlgoritma Local Search
Proses  analisis  data  dengan  metode Local  Search dilakukan  untuk mengevaluasi  dan  memperbaiki  rute  distribusi  awal  yang  telah  ditentukan  oleh metode Nearest  Neighbour .  Terdapat  beberapa  langkah  yang  harus  dilakukan, diantaranya :
Langkah 1 : Input tur dan rute hasil Nearest Neighbour, matriks jarak, LT dan UT ,  permintaan  setiap  agen  ( Di ),  kapasitas  kendaraan  ( Q ). Lanjutkan ke langkah 2.

## Unisda Journal of Mathematics and Computer Science
Langkah  2 : Dimulai dari tur ke 1, i = 1. Lanjutkan ke langkah 3.
Langkah  3: Melakukan  proses Insertion  Intra-route (1-0),  menukar  urutan pelayanan  setiap  titik  agen  dalam  rute  yang  sama  setiap  rute kendaraan,  lanjutkan  ke  langkah  4,  kija  semua  rute  telah  dicari tanda tur dan lanjutkan ke langkah 6. Langkah  4  : Jika  total  jarak  pada  rute  baru  telah  lebih  kecil  dari  sebelumnya maka lanjutkan ke langkah 5, jika tidak kembali ke langkah 3.
Langkah  5  : Pilih  rute  baru  untuk  menggantikan  rute  sebelumnya,  kembali  ke langkah 3.
Langkah  6  : Jika  semua  tur  sudah  dicari  lanjutkan  ke  langkah  8,  jika  tidak  ke langkah 7.
Langkah 7  : Hitung i, i = i +1. Kembali ke langkah 3.
Langkah 8  : Prosedur selesai.

## 2.5   Kerangka Pemecahan Masalah
Gambar 1. Kerangka Pemecahan Masalah
START Studi Pustaka Penentuan Metode Pemecahan Masalah : • Analisis Nearest Neighbour & Analisis Local Search Pengumpulan Data Melalui Proses Wawancara dan Observasi Pengolahan Data Identifikasi Masalah Penentuan Rute Pendistribusian Menggunakan Metode Nearest Neighbour Perbaikan Rute Pendistribusian Menggunakan Metode Local Search
Solusi Penentuan Rute Distribusi

## 3. Hasil dan Analisa Data
Tabel 1. Data waktu tempuh menggunakan perhitungan menit Depot P1 P2 P3 P4 P5 P6 P7 P8 Depot 0 2 5 15 13 21 34 44 50 P1 2 0 5 13 13 20 32 37 45 P2 5 5 0 12 12 19 31 35 40 P3 15 13 12 0 15 22 31 41 56 P4 13 13 12 15 0 9 21 26 39 P5 21 20 19 22 9 0 17 20 15 P6 34 32 31 31 21 17 0 35 31 P7 44 37 35 41 26 20 35 0 23 P8 50 45 40 56 39 15 31 23      0
Tabel 2. Rute Existing  PT. X Tur Rute 1 P1-P2 2 P3-P4 3 P5-P6

## 4
P7-P8
Tabel 3. Rute Menggunakan Metode Nearest Neighbour dan Local Search Tur Rute Waktu Penyelesain (Menit) 1 P7-P3-P4 621 2 P1-P2-P8 526 3 P5-P6 418 TOTAL 1.565
Jumlah  kendaraan  yang  dimiliki  PT.  X  saat  ini  adalah  sebanyak  4  truk, dengan  kapasitas  yang  sama  560  tabung.  Tur  yang  pertama  di  lakukan  dengan menggunakan 4 truk dengan melakukan 4 tur dalam seharinya. Dengan di lakukan menggunakan  metode Nearest  Neighbour dan Local  Search mendapatkan  hasil yang  maksimal  dari  pada  sebelumnya,  yang  pertamanya  4  tur  setelah  dilakukan metode tersebut menghasilkan 3 tur. Tur pertama dilakukan pada ( P1-P2-P4-P3 ) menghasilkan total waktu sebesar 589 menit, tur ke dua dilakukan pada ( P5-P6 ) menghasilkan total waktu 418 menit, tur yang tiga ( P7-P8 ) menghasilakan waktu sebesar  558  menit.  Dari  hasil  analisis  tersebut  menghasilkan  tur  yang  maksimal
pertamanya  4  tur  setelah  dilakukan  analisis  menggunakan  metode Nearest Neighbour dan Local Search mendapatkan hasil 3 tur dalam seharinya. Sehingga menghasilkan penghematan pendistribusian yakni di dalam alokasi kendaraannya, yang pertamanya dilakukan dengan 4 tur yang dilakukan 4 truk, dengan dilakukan analisis menghasilkan 3 yang dilakukan dengan 3 truk.

## 4. Kesimpulan
Pada   penelitian   ini   menggunakan   metode   kombinasi   antara   nearest neighbour  dan  local  search  untuk  menyelesaikan  permasalahan vehicle  routing problem. Tujuannya  adalah  mencari  jarak  terpendek  untuk  menentukan  rute sehingga  bisa  mengoptimalkan  penggunaan  sumber  daya  yang  ada.  Hasil eksperimennya  menunjukkan  setelah  menggunakan  kombinasi  dua  metode tersebut,  ada  pengoptimalan  penggunaan  truk  yang  digunkan.  Eksisting membutuhkan 4 truk, sedangan setelah pengoptimalan hanya membutuhkan 3 truk saja.  Pada  penelitian  kedepannya,  sangat  memungkinkan  menggunakan pengembangan metode optimasi lainnya sehingga menghasilkan tujuan yang lebih optimal.

## 5. Daftar Pustaka
[1] Abdullah.  M.,  2015. Metodologi  Penelitian  Kuantitatif,  untuk  Ekonomi, Manajemen,  Komunikasi,  dan  Ilmu  Sosial  Lainnya. Yogyakarta  :  Aswaja Pressindo.
[2]   Anwar.   S.   N.,   2013. Management   Rantai   Pasokan   (Supply   Chain Management) : Konsep dan Hakikat. Universitas Stikubank Semarang.
[3]  Arinalhaq.  F.,  Imran.  A.,  Fitria.  L.,  2013. Penentuan  Rute  Kendaraan Pengangkutan  Sampah  dengan  Menggunakan  Metode  Nearest  Neighbour (Studi  Kasus  PD  Kebersihan  Kota  Bandung). Jurnal  Online  Institut Teknologi Nasional Vol.1 : 22-32.
[4]   Toth,  P.,  and  Vigo.2020. An   Overview  of  Vehicle  Routing  Problem. Philadelphia: Society for Industrial and Applied Mathematics.
[5]    Brandenburg. M., Govindan. K., Sarkis. J., Seuring. S., 2013. Quantitative Models  for  Sustainable  Supply  Chain  Management  :  Developments  and Directions. European Journal of Operational Research 233 (2013) 299-312.
[6]    Koswara. H., Adianto. H., Nughraha. A., 2017 Penentuan Rute Distribusi Produk   Kaos   Pada   Dobujack   Inv.   Menggunakan   Metode   Nearest Neighbour  dan  (1-  0)  Insertion  Intra  Route. Jurnal  Rekayasa  Sistem  &
Industri, No.2, Vol.4 : 192-198