JTERA (Jurnal Teknologi Rekayasa), Vol. 6, No. 1, Juni 2021, Hal. 121-130 Terakreditasi “ Peringkat 3” oleh Kemenristek/BRIN, Nomor SK: 85/M/KPT/2020 DOI: 10.31544/jtera.v6.i1.2021.121-130
Diterima: 30 April 2021; Direvisi: 29 Mei 2021; Disetujui: 6 Juni 2021 JTERA, Vol. 6, No. 1, Juni 2021 © 2021 JTERA (Jurnal Teknologi Rekayasa), Politeknik Sukabumi

## Optimalisasi Penentuan Jalur Distribusi Terpendek Menggunakan Spanning Tree dan Nearest Neighbor
Muhamad Dhika Rahma Fauzi # , Wahyudin Wahyudin, Billy Nugraha Program Studi Teknik Industri, Fakultas Teknik, Universitas Singaperbangsa Karawang Jl. H. S. Ronggowaluyo, Telukjambe Timur, Karawang – 41361, Indonesia
# 1810631140104@student.unsika.ac.id

## Abstrak
Permasalahan  jalur distribusi  yang  optimal  adalah  pertimbangan  penting  dengan  tujuan  efisiensi.  Hal  ini  akan berdampak  pada  biaya  dan  waktu  yang  berlebih,  seperti  jumlah  bahan  bakar  yang  dikeluarkan.  UMKM  merupakan usaha  kecil  yang  bergerak  di  berbagai  bidang  kehidupan  sehari-hari.  Permasalahan  mengenai  pendistribusian  masih terjadi  berdasarkan  hasil  studi  lapangan  yang  telah  dilakukan.  Penelitian  ini  bertujuan  untuk  mengoptimalkan  jalur distribusi terpendek yang dapat ditempuh oleh pegawai. Metode yang digunakan dalam penelitian ini adalah spanning tree dan nearest neighbor . Selain itu teknik pengambilan sampel menggunakan purposive sampling dan teknik analisis data  merupakan  tahapan  pengerjaannya.  Dari  hasil  penelitian  menunjukkan  metode spanning  tree mendapatkan  jalur terpendek  dengan  jarak  yang  ditempuh  20  Km,  sedangkan  metode nearest  neighbor mendapatkan  jalur  terpendek dengan jarak yang ditempuh 38,7 Km. Maka dapat disimpulkan metode spanning tree menghasilkan jarak tempuh yang leih  optimal  dibandingkan  metode nearest  neighbor .  Selain  itu,  untuk  menunjukkan  hasil  yang  lebih  akurat  dengan bantuan software Program Operations Management - Quantitative Methods (POM-QM). Hal ini untuk mempermudah dalam pengolahan hasil penelitian dan merupakan pembaharuan yang dilakukan dari penelitian sebelumnya.
Kata kunci: spanning tree , nearest neighbour , purposive sampling , POM-QM

## Abstract
The  problem  of  optimal  distribution  routes  is  an  important  consideration  with  efficiency  goals.  It  will  have  an impact on excessive costs and time that must be incurred, such as fuel transportation. UMKM is a small business that was engaged in the various field of everyday life. This study aims to optimize the shortest distribution routes that can be taken  by  the  employees.  The  method  used  in  this  research  is  a  Spanning  Tree  and  Nearest  Neighbors.  In  addition, sampling techniques used purposive sampling and data analysis techniques that were the stages of their work. From the results  of  the  study,  it  showed  that  spanning  tree  method  got  the  shortest  path  with  a  distance  traveled  20  Km. Meanwhile, nearest neighbor method got the shortest path with a distance traveled 38.7 Km. Then, it can be concluded that  spanning  tree  method has more optimal result than  nearest  neighbor  method. In addition  to showing  accurated results, the help of the software Operations Management Program - Quantitative Methods (POM-QM) is used to make it easier in processing the results of the study and is a renewal conducted from previous research.
Keywords: spanning tree, nearest neighbor, purposive sampling, POM-QM

## I. P ENDAHULUAN
Kegiatan  usaha  tidak  terlepas  dari  proses distribusi  produk.  Distribusi  merupakan  proses penyaluran  barang  atau  jasa  dari  produsen  ke perantara dan akhirnya sampai ke tangan konsumen. Selain  itu,  distribusi  merupakan  kunci  perusahaan karena  secara  langsung  akan  mempengaruhi  biaya dari supply  chain dan  kebutuhan  konsumen  [1].
Peranan penting proses distribusi dalam usaha atau bisnis  tentunya  harus  diperhatikan  dengan  baik. Dalam  pendistribusian  produk  terdapat  beberapa aspek  yang  perlu  diperhatikan  seperti  transportasi, fasilitas,  dan  komunikasi.  Proses  distribusi  yang kurang  efektif  akan  memengaruhi  kualitas  produk yang  sampai  di  tangan  konsumen  [2].  Salah  satu aspek  yang  erat  kaitannya  dalam  masalah pendistribusian  adalah  transportasi  karena  harus
menjamin  mobilitas  produk  di  antara  berbagai sistem dengan efisiensi tinggi dan ketepatan waktu. Selain  itu,  pada  saat  yang  sama  harus  dapat mengurangi biaya distribusi dengan jalur pendistribusian agar optimal [3]. Permasalahan jalur distribusi  yang  optimal  merupakan  pertimbangan penting  yang  harus  efisiensi.  Karena  dampak  dari permasalahan  adalah  biaya  berlebih  yang  harus dikeluarkan,  seperti  bahan  bakar  transportasi. Kaitannya  dengan  permasalahan  jalur  transportasi, salah  satu  metode  yang  dapat  membantu permasalahan  adalah nearest  neighbor dan spanning  tree .  Metode nearest  neighbor akan melakukan  pencarian  pelanggan  terdekat  dengan pelanggan selanjutnya sampai didapatkan pelanggan terakhir  untuk  jalur  yang  dilalui  [4].  Sedangkan, metode spanning  tree tidak  diperkenankan  atau dihidarkan  jalan  berulang  yang  menyebabkan terjadinya looping atau  siklus  dari node satu  ke node yang lain.
Sebagai  studi  kasus,  salah  satu  UMKM  yang bertempat  di  Jln.  Eyang  Weri  No.  365  RT/RW 003/006  Awirarangan,  Kecamatan  Kuningan, Kabupaten  Kuningan,  Jawa  Barat  dengan  nama Z&J Cookies bergerak di bidang produksi beraneka macam  olahan  kue.  Kegiatan  pengiriman  produk kepada  konsumen  dilakukan  pegawai  dengan menggunakan  sepeda  motor  untuk  didistribusikan kepada konsumen di berbagai tempat tujuan. Tetapi dalam  kegiatan  pendistribusian  yang  dilakukan tidak  memperhatikan  jalur  terpendek.  Dalam beberapa  bulan  kegiatan  berlangsung  biaya transportasi menjadi beban yang cukup besar setiap bulannya.  Hal  ini  didapatkan  dari  hasil  wawancara dengan pemilik UMKM.
Metode nearest  neighbor dan spanning  tree dalam penentuan  jalur distribusi terpendek menjadi salah  satu  metode  yang  tepat  untuk  digunakan. Masing-masing  metode  memiliki  karakteristik  dan cara  yang  berbeda  dalam  penyelesaiannya.  Dengan kedua  metode  tersebut,  penelitian  yang  dilakukan oleh  G.  D.  Rembulan,  dkk.  menghasilkan  biaya yang  dikeluarkan  untuk  PT.  PAM  Lyonaisse  Jaya berkurang 2 kali lipat dan PT. Aetra Air Jakarta 16 kali  lipat  lebih  rendah  dari  semula.  Penelitian  ini menggunakan      asumsi      yang  sangat  sederhana bahwa  jarak  berbanding  lurus  dengan  biaya  [5]. Penelitian  yang  dilakukan  oleh  R.  Ramadan,  dkk. merancang  model  jaringan spanning  tree yaitu untuk  mengetahui  jarak  minimal  karyawan  untuk mendistribusikan  roti.  Hasil  penelitian  didapatkan jalur  optimal  yaitu  A–B–D–E–F  dan  A–C–G–H, sehinga  tidak  terjadinya  sirkuit  atau  pengulangan dalam node dimana total jarak yang harus ditempuh adalah  sepanjang  7.550  m  [6].  Penelitian  yang dilakukan  oleh  S.  Martono,  dkk.  menghasilkan
jumlah  jalur  paling  sedikit  dibandingkan  dengan sebelum menggunakan metode dan pada total jarak dengan  menggunakan  metode  98.610  meter  atau 98,61  Km.  Sedangkan  jika  pada  jalur  sebelum mengunakan  metode  124.198  meter  atau  124,198 Km  terjadi  pengurangan  jarak  25.588  atau  25,588 atau  sebesar  20.6026%  [7].  Penelitian  yang dilakukan  oleh  W.  Prasetyo,  dkk.  menghasilkan jarak  total  yang  ditempuh  oleh  armada  pengiriman diperoleh penghematan jarak sejauh 538,2 Km atau sebesar 26,59% [8].
Penelitian  ini  bertujuan  untuk  mengoptimalkan jalur distribusi terpendek yang dapat ditempuh oleh pegawai  menggunakan  metode spanning  tree dan nearest  neighbor yang  dibandingkan  untuk mendapatkan hasil optimal. Perbandingan hasil dari kedua  metode  merupakan  salah  satu  pembaharuan yang  dilakukan  pada  penelitian  ini  karena  masih minimnya  literatur  atau  penelitian  terdahulu. Padahal  kedua  metode  memiliki  karakteristik  yang berbeda  dalam  penyelesaiannya,  tetapi  tujuannya sama.  Melalui  penelitian  ini  dapat  ditarik kesimpulan  penggunaan  metode  mana  yang  akan menghasilkan perhitungan jalur distribusi terpendek untuk mengurangi beban biaya UMKM. Sedangkan untuk gap penelitian  ini  berdasarkan  dari penelitian/penulisan terdahulu adalah dapat diketahui  dari  hasil  penelitian/penulisan  terdahulu yang  hanya  fokus  pada  salah  satu  metode  saja. Sedangkan  hal  tersebut  belum  tentu  hasil pengolahan  perhitungan  yang  optimal.  Maka penelitian  ini  mencoba  untuk  melengkapi  kembali dengan  membandingkan  hasil  dari  kedua  metode. Selain itu, pada penelitian ini perhitungan dilakukan dengan  bantuan  aplikasi Program Operations Management – Quantitative Methods (POM-QM). Hal  ini  untuk  memudahkan  dan  meminimalisir terjadinya human  error pada  perhitungan  secara manual. Versi pertama software ini berbentuk DOS yang  dipublikasi  di  tahun  1989  sebagai  PC-POM.. Versi  Windows  pertama  yaitu  QM  for  Windows (versi  1.0)  yang  didistribusikan  pada  musim  panas 1996  merupakan  program  terpisah  tetapi  tetap sejenis  [9].  Pengunaan  aplikasi  tersebut  sebagai bentuk  pemanfaatan  teknologi  yang  sedang berkembang.

## II. M ETODE P ENELITIAN
A. Nearest Neighbor Method
Metode nearest neighbor merupakan algoritma  yang  mudah  untuk  diimplementasikan. Penggunaan algorimatnya, hanya mencari pelanggan  dengan  jarak  yang  terdekat  yang  belum dikunjungi  dengan  menyertakan  beberapa  batasan. Setiap  prosesnya  dilakukan  pencarian  pelanggan
terdekat  dengan  pelanggan  yang  terakhir  untuk ditambahkan  pada  akhir  jalur.  Cara  kerja  dari metode  ini  yaitu,  semua  jalur  kendaraan  masih kosong pada awalnya. Dimulai dari jalur kendaraan pertama,  metode  ini  memasukkan  satu  persatu pelanggan terdekat yang belum dikunjungi ke dalam jalur.  Selama  memasukkan  pelanggan  tersebut  ke dalam  jalur  kendaraan  tidak  melebihi  kapasitas maksimum  kendaraan  [10].  Berikut  ini  merupakan rumus  persamaaan yang  digunakan  untuk menyelesaikan metode nearest neighbor [11]:
(1)
Dalam hal ini nilai adalah total jarak jalur yang diperoleh dan nilai c merupakan jarak tiap lokasi i, j, dan k.

## B. Spanning Tree
Metode spanning  tree merupakan  subgraf sederhana  yang  terhubung  dengan  jarak  yang minimal  dan  tidak  memuat cycle .  Setiap  graf terhubung  paling  sedikit  mempunyai  satu spanning tree .  Graf  terhubung  G  adalah spanning  tree jika dan hanya jika menambahkan sebuah sisi antara dua titik  sebarang  dalam  G  akan  membentuk  tepat  satu cycle [12].  Pada  metode  ini  terdapat  sumber  dan tujuan  yang  akan  dicapai.  Sumber  yang  dimaksud adalah  lokasi  titik  awal  pegawai,  sedangkan  yang dimaksud  dengan  tujuan  adalah  tempat  atau  lokasi yang  dituju.  Jadi,  dalam  hal  ini  terdapat  pegawai (m)  yang  ditugaskan  untuk  mendistribusikan  kue kepada kota atau suatu lokasi (n). Jika pegawai I (I = 1, 2, ..., m), ditugaskan kepada lokasi j (j =1, 2, ..., n) akan muncul jalur terpendek 𝐶𝑖𝑗 .

## C. Alur Penelitian
Pada  bagian  ini  menjelaskan  rangkaian  alur penelitian  yang  dilakukan.  Rangkaian  alur penelitian  merupakan  kegiatan/aktivitas  yang dilakukan  di  lapangan.  Hal  ini  sesuai  dengan identifikasi  dan  rumusan  masalah  pada  penelitian. Sehingga  hasil  akhir  penelitian  akan  sesuai  dengan tujuan  dan  manfaat  yang  telah  ditentukan.  Alur penelitian  yang  dilakukan  dapat  dilihat  pada Gambar 1.
Di  bawah  ini  merupakan  penjelasan flowchart pada Gambar 1 sebagai berikut:
1. Identifikasi Masalah Permasalahan  yang  ditemukan  yaitu  jalur kegiatan  distribusi  kue  kepada  pelanggan  yang belum  optimal,  sehingga  menyebabkan  biaya jumlah bahan bakar dan waktu yang berlebih. Studi pendahuluan  dalam  penelitian  terbagi  menjadi  dua, yaitu  studi  literatur  dan  lapangan.  Studi  literatur dilakukan dengan mencari referensi hasil penelitian
terdahulu,  sedangkan  studi  lapangan  dilakukan  di UMKM J&Z Cookies yang bertempat di Jln. Eyang Weri  No.  365  RT/RW  003/006  Awirarangan, Kecamatan  Kuningan,  Kabupaten  Kuningan,  Jawa Barat.  Lokasi  UMKM  berada  di  tengah-tengah pemukiman  yang  padat  karena  setiap  sisinya  di kelilingi oleh rumah masyarakat setempat.
Mulai Identifikasi Masalah Pengumpulan dan Pengolahan Data Metode Spanning Tree Metode Nearest Neighbor Aplikasi POM-QM Analisis Hasil Kesimpulan dan Saran Selesai Apakah Data sudah cukup? Apakah Data sudah sesuai? Iya Tidak Iya Tidak
2. Pengumpulan dan Pengolahan Data Data yang dikumpulkan dalam penelitian berasal dari  sumber  data  primer  dan  data  sekunder.  Data primer  berupa  informasi  jalur  yang  sering  dilalui dalam  mendistribusikan  produk  melalui  kegiatan wawancara,  sedangkan data  sekunder  berupa kumpulan  pendukung  informasi  penelitian  melalui kegiatan studi literatur. Teknik pengambilan sampel pada  penelitian  ini,  menggunakan purposive sampling .  Karena  obyek  yang  diteliti  berkaitan dengan  pengalaman  yang  terjadi  dilapangan,  maka informasi  kebutuhan data harus  kepada orang yang tepat  seperti  pemilik  UMKM  dan  pegawai. Pengolahan  data  dilakukan  dengan  menggunakan metode spanning tree dan nearest neighbor melalui data yang telah didapat.
3. Apakah Data Sudah Cukup?
Iya,  ketika  data  sudah  cukup  dapat  dilanjutkan ke  tahap  pengolahan  data.  Tidak,  jika  data  masih kurang.
4. Metode Spanning Tree Penggunaan  metode  ini  dengan  mencari  jarak terpendek  melalui node lokasi  awal  menuju node tujuan  yang  tersebar.  Algoritma  untuk  metode spanning tree , sebagai berikut [13]:
a. Pilih  sembarang  simpul  dan  hubungkanlah (tambahkan  suatu  busur)  dengan  simpul terdekat.
b. Tentukan  suatu  simpul  tak  terhubungkan  yang terdekat  dari  suatu  simpul  terhubungkan,  lalu hubungkanlah  kedua  simpul  tersebut.  Ulangi langkah ini sampai seluruh simpul
terhubungkan.
5. Metode Nearest Neighbor
Penggunaan  metode  ini  dengan  mencari  titik terdekat  dan  belum  dikunjungi.  Algoritma  untuk metode nearest neighbor , sebagai berikut [13]:
a. Tujuan  dari  iterasi  ke-n :  Menentukan  simpul yang  menduduki  urutan  ke-n  dalam  jaraknya terhadap  simpul  asal  (yang  akan  diulang  untuk n=  1,  2,  3,  …  sampai  simpul  yang  menduduki tempat ke-n tersebut adalah simpul tujuan).
b. Masukan  bagi  iterasi  ke -n:  Simpul  terdekat  ke-
(n-1)  dalam  jaraknya  terhadap  simpul  asal (didapatkan  dari  iterasi  sebelumnya),  termasuk lintasan  terpendeknya  dan  jaraknya  terhadap simpul  asal.  (Simpul  yang  termasuk  dalam lintasan ini disebut sebagai simpul terselesaikan , sedangkan  yang  lainnya  disebut  sebagai simpul tak terselesaikan . Simpul asal  selalu merupakan simpul terselesaikan).
c. Calon untuk simpul terdekat ke-n : setiap simpul terselesaikan yang secara langsung terhubungkan  dengan  link  menuju  satu  atau lebih simpul tak terselesaikan akan memberikan satu  calon  –  suatu  simpul  tak  terselesaikan
dengan busur tak berarah terpendek (jarak sama akan memberikan calon tambahan).
6. Aplikasi POM-QM Penggunaan aplikasi POM-QM dilakukan untuk membandingkan hasil pengerjaan manual.
Tidak Mulai Mencari Data Jalur Distribusi (Wawancara) Melakukan
Perhitungan Spanning Tree
Melakukan Perhitungan
Nearest Neighbor Melakukan Perhitungan POM-QM Apakah Data sudah cukup? Tidak Iya Apakah Data sudah sesuai? Iya Mulai Menarik Kesimpulan Jalur Terpendek Analisis Hasil Perbandingan Setiap Metode
7. Apakah data sudah sesuai?
Iya,  jika  hasil  sudah  sesuai  dengan  aturan pengerjaan dan dapat lanjut ke analisis hasil. Tidak, jika hasil belum sesuai dengan aturan pengerjaan. 8. Analisis Hasil Hasil  dari  pengolahan  data  di  analisis  dan  di identifikasi  terkait  jalur  yang  paling  optimal  untuk mendistribusikan kue kepada pelanggan.
9. Kesimpulan dan Saran Keluaran  yang  dihasilkan  dari  penelitian  ini,  di bentuk  kesimpulan  berupa  hipotesis  penelitian, sedangkan  saran  ditujukan  kepada  UMKM  Z&J Cookies sebagai  bentuk  rekomendasi  perbaikan dalam memperbaiki jalur pendistribusian kuenya.

## D. Analisis Data
Analisis data yang dilakukan pada penelitian ini melalui beberapa tahapan seperti pada Gambar 2. Di bawah  ini  merupakan  deskripsi  dari flowchart Gambar 2 sebagai berikut:
1. Mencari Data Jalur Distribusi (Wawancara)
Kegiatan wawancara dilakukan untuk
mendapatkan  informasi  data  jalur  distribusi dilakukan  secara  langsung  kepada  pemilik  dari UMKM Z&J Cookies . 2. Apakah data sudah cukup?
Iya,  ketika  data  sudah  cukup  dapat  dilanjutkan ke  tahap  perhitungan  data.  Tidak,  jika  data  masih kurang.
3. Melakukan Perhitungan Spanning Tree Penentuan jalur optimal dengan cara menghubungkan  subgraf  yang  terdekat  dan  tidak memuat cycle .
4. Melakukan Perhitungan Nearest Neighbor Penentuan  jalur  dengan  mencari  yang  terdekat yang belum dikunjungi.
5. Melakukan Perhitungan POM-QM
Data  diolah  menggunakan  aplikasi  POM-QM agar  mengurangi  resiko  kesalahan  dalam  cara manual.
6. Apakah data sudah sesuai? Iya, jika hasil sudah sesuai dengan perhitungannya  dan  dapat  lanjut  ke  analisis  hasil. Tidak,  jika  hasil  belum  sesuai  dengan  aturan perhitungannya.
7. Analisis Hasil Perbandingan Setiap Metode Melalui  perbandingan  hasil  dari  pengerjaan kedua metode, didapati hasil paling optimal dengan menggunakan metode spanning tree sejauh 20 Km. Hasil tersebut lebih pendek daripada metode nearest neighbor yang  menghasilkan  jarak  optimalnya sejauh 38,7 Km.
8. Menarik Kesimpulan Jalur Terpendek Penarikan  kesimpulan  dilakukan  setelah  hasil analisa dari perbandingan metode.
Berikut  merupakan  beberapa  dokumentasi  yang diambil seperti pada Gambar 3. di bawah ini.

## III. H ASIL DAN P EMBAHASAN
A. Wilayah Distribusi UMKM  Z&J Cookies bergerak  di  bidang makanan,  yaitu  memproduksi  berbagai  macam varian cookies .  Jumlah  produksi  perharinya  dapat mencapai 4000-5000 pcs roti. Proses pendistribusian  yang  dilakukan  berdasarkan  hasil wawancara dengan pemiliknya dilakukan di daerah Kuningan dan luar Kuningan. Pegawai mendistribusikan  kue  menggunakan  kendaraan sepeda  motor.  Pada  penelitian  ini  proses pendistribusian  yang  di  amati  berada  di  wilayah Kuningan.  Berikut  merupakan  data  distribusi  kue kepada pelanggan dan reseller seperti pada Tabel 1.
Gambar 3. Dokumentasi UMKM Z&J Cookies
Tabel 1. Data pendistribusian UMKM Z&J Titik pengantaran Simbol Jarak (Km) Awirarangan – Ciporang H – A 3,2 Awirarangan – Ancaran H – B 5,1 Awirarangan – Purwasari H – C 7,5 Awirarangan – Winduhaji H – D 1,7 Awirarangan – Pasapen H – E 4,9 Awirarangan – Cigugur H – F 7,0 Awirarangan – Purnawinangun H – G 2,7 Gambar 4. Graf jaringan pendistribusian kue Proses distribusi yang biasa dilakukan ditunjukkan seperti pada Tabel 1. Jalur dimulai dari Awirarangan  –  Ciporang  –  Ancaran  –  Purwasari  – Winduhaji – Pasapen – Cigugur – Purnawinangung. Jarak  yang  ditempuh  adalah  28  Km  berdasarkan Google maps.
B. Hasil Pengujian Menggunakan Metode Spanning Tree
Pada  bagian  ini  akan  diuraikan  tahapan pengujian  metode spanning  tree. Tahapan  yang dilakukan  terdiri  dari  Tahap  1  Mendefinisikan Masalah,  Tahap  2  Pengembangan  Model,  Tahap  3 Pemecahan Model, dan Tahap 4 Hasil Akhir.
1. Tahap 1: Mendefinisikan Masalah Fungsi  tujuan  yang  ditetapkan  adalah  untuk membuat minimum spanning tree pada pendistribusian  produk  kue.  Fungsi  kendala node dan path didefinisikan seperti Tabel 1.
2. Tahap 2: Pengembangan Model Data simbol dan jarak pada Tabel 1 dibuatkan ke dalam  bentuk  model  graf  seperti  Gambar  4.  Pada Gambar  4 node H  menjadi  titik  awal  distribusi. Selanjutnya,  dilakukan  pemilihan node lain  yang terpendek  dari node H  seterusnya  dilakukan  secara berulang  sampai  terbentuk  model  graf  seperti  di Gambar 4.
3. Tahap 3: Pemecahan Model Pencarian  jalur  dilakukan  dengan  mencari  jalur paling  pendek  di  titik  awal  distribusi,  berikut penyelesaiannya:
Gambar 5. Graf iterasi 1 Gambar 6. Graf iterasi 2
Gambar 7. Graf iterasi 3
Gambar 8. Graf iterasi 4
a. Jalur titik H  ke D merupakan tahapan distribusi pertama  karena  jaraknya  lebih  dekat,  yaitu  1,7 Km seperti pada Gambar 5.
b. Jalur titik H  ke G merupakan tahapan distribusi kedua karena jaraknya lebih dekat, yaitu 2,7 Km seperti pada Gambar 6.
c. Jalur titik  G  ke  E  merupakan  tahapan  distribusi ketiga karena jaraknya lebih dekat, yaitu 2,2 Km seperti pada Gambar 7.
d. Jalur titik  E  ke  F  merupakan  tahapan  distribusi keempat  karena  jaraknya  lebih  dekat,  yaitu  2,5 Km seperti pada Gambar 8.
Gambar 9. Graf iterasi 5
Gambar 10. Graf iterasi 6
Gambar 11. Graf iterasi 7 Gambar 12. Graf optimal
e. Jalur titik  H  ke  A  merupakan  tahapan  distribusi kelima karena jaraknya lebih dekat, yaitu 3,2 Km seperti pada Gambar 9.
f. Jalur titik  A  ke  B  merupakan  tahapan  distribusi keenam  karena  jaraknya  lebih  dekat,  yaitu  1,9 Km seperti pada Gambar 10.
g. Jalur titik  D  ke  C  merupakan  tahapan  distribusi ketujuh  karena  jaraknya  lebih  dekat,  yaitu  5,8 Km seperti pada Gambar 11.
h. Graf  optimal  menunjukan  bahwa  semua node sudah  terselesaikan,  dalam  artian  kegiatan distribusi  yang  berawal  dari  titik  H  di  UMKM kepada  titik  tujuannya  yaitu  para  pelanggannya. Bentuk  graf  optimal  dapat  dilihat  seperti  pada Gambar 12.
4. Tahap 4: Hasil Akhir
Pada  penyelesaian  menggunakan  metode spanning  tree di  atas  hasil  optimal  dari  distribusi kue yang awalnya sejauh 28 Km berkurang menjadi 20 Km. Dengan pengurangan hasil yang diberikan, tentunya akan mengurangi beban biaya transportasi.
C. Hasil  Pengolahan  Menggunakan  Aplikasi POM – QM for Windows
Pada  Gambar  13  menunjukan  hasil  dari pengolahan  data  menggunakan  aplikasi  POM-QM. Tampilan  pada  aplikasi  tersebut  terdapat branch name ,  yaitu  menunjukan  cabang  setiap node atau garis  penghubung  antara node satu  dengan  yang lainnya. Start  node dan end  node merupakan  titik awal dan akhir dari cabang atau garis penghubung. Cost merupakan  hasil  dari  jarak  yang  ditempuh antara  kedua node . Include merupakan  penanda jarak  antar node dapat  dilakukan.  Tanda  Y  pada kolom include merupakan  parameter  kesesuaian dari  cabang  antar  setiap node .  Jika  tanda  tersebut selain  Y  dapat  dikatakan  cabang  antar  setiap node tidak terhubung. Nilai atau data masukan diperoleh dari  Tabel  2.  yaitu  data node dan  jarak  yang dimasukan  ke  dalam  aplikasi  sebagai  dasar perhitungan yang akan menghasilkan jarak optimal.
Penggunaan  aplikasi  tujuannya  adalah  untuk membuktikan  bahwa  dalam  pengerjaan  hitung manual  tidak  mengalami  kesalahan  ( human error ). Hasil  dari  perhitungan  menggunakan  POM-QM sesuai  dengan  perhitungan  manual  dapat  dilihat pada Gambar 13.
D. Hasil Pengujian Metode Nearest Neighbor
Penggunaan  metode  kedua  ini  tujuannya  adalah sebagai pembanding dari metode pertama dan hasil realita  di  lapangan.  Berikut  merupakan  tahapan- tahapan penyelesaiannya:
1. Tahap  1:  Membuat  tabel  jarak  setiap node ke node lainnya seperti pada Tabel 3. Sumber awal data  Tabel  3  diperoleh  dari  Tabel  2  agar  lebih mudah  dalam  menentukan  jarak  tiap node- nya dibentuk  graf  seperti  Gambar  4  karena  pada tabel  tersebut  dibutuhkan  data  jarak  antar node bukan jarak dari titik awal ke setiap node .
2. Tahap  2:    Memulai  perhitungan  dengan  titik  H sebagai  titik  awal  pendistribusian  kepada pelanggan  seperti  pada  Tabel  4.  Tahapan pertama  dilakukan  sesuai  dengan node awal kegiatan distribusi yaitu node H. Lalu, dari baris node H  dipilih  jarak  terpendek  dan node D terpilih  sebagai node yang  dikunjungi  setelah node H.  Tahapan  selanjutnya  dilakukan  dengan proses  yang  sama  dari node yang  terpilih  dari baris  sebelumnya  menjadi  baris  penentu  jalur distribusi  selanjutnya  dengan  mencari  jarak terpendek dari baris tersebut.

## Gambar 13. Hasil perhitungan menggunakan aplikasi POM-QM
Tabel 3. Jarak antar node A B C D E F G H A - 1,9 9 4,9  8,1  10,6  5,9 3,2 B 1,9 - 7,1 6,8  10  12,5  7,8 5,1 C 9 7,1 - 5,8  9,2  11,7  10,2  7,5 D 4,9 6,8 5,8 - 3,4 5,9 4,4 1,7 E 8,1 10 9,2 3,4 - 2,5 2,2 4,9 F 10,6  12,5  11,7  5,9  2,5 - 4,3 7 G 5,9 7,8  10,2  4,4  2,2 4,3 - 2,7 H 3,2 5,1 7,5 1,7  4,9 7 2,7 - Tabel 4. Penentuan jalur A B C D E F G H A - 1,9 9 4,9  8,1  10,6  5,9 3,2 B 1,9 - 7,1 6,8  10  12,5  7,8 5,1 C 9 7,1 - 5,8  9,2  11,7  10,2  7,5 D 4,9 6,8 5,8 - 3,4 5,9 4,4 1,7 E 8,1 10 9,2 3,4 - 2,5 2,2 4,9 F 10,6  12,5  11,7  5,9  2,5 - 4,3 7 G 5,9 7,8  10,2  4,4  2,2 4,3 - 2,7 H 3,2 5,1 7,5 1,7  4,9 7 2,7 -

## Gambar 13. Graf Optimal
3. Tahap  3:  Graf  dari  jalur yang  dihasilkan berdasarkan  tabel  diatas  dan  graf  optimal  dapat dilihat  pada  Gambar  13.  Pada  gambar  tersebut menunjukkan  graf  optimal  yang  didapat  dari penentuan  jalur  distribusi  menggunakan  metode
nearest  neighbor .  Warna  yang  terdapat  pada graf tersebut tujuannya sebagai tanda node awal distribusi  yang  ditandai  warna  biru  dan  warna hijau  muda  ditunjukan  untuk node pelanggan yang  dituju.  Sehingga,  secara  visual  dapat memudahkan  peneliti  dan  pembaca  dalam membaca jalur pada graf dari awal sampai akhir. Berdasarkan  perhitungan  menggunakan  metode nearest  neighbor dihasilkan  jalur distribusi  yang optimal  sejauh  38,7  Km.  Hasil  tersebut  lebih  jauh dari  perhitungan  metode  sebelumnya,  yaitu spanning  tree dan  juga  realita  yang  terjadi dilapangan.

## IV. K ESIMPULAN
Berdasarkan  dari  kegiatan  wawancara  dengan pemilik  UMKM  untuk  jarak  distribusi  kepada pelanggan  sejauh  28  Km.  Selain  itu,  jarak  tersebut dapat  diketahui  dengan  bantuan  melalui  Google Maps.  Maka  dari  hasil  penelitian  yang  telah dilakukan  dengan  menggunakan  metode spanning tree dan nearest neighbour , didapatkan hasil untuk jarak  optimal  menggunakan  metode spanning  tree sejauh  20  Km,  sedangkan  dengan  metode nearest neighbor sejauh  38,7  Km.  Selain  itu,  untuk mendapatkan  hasil  yang  akurat  dilakukan perhitungan  dengan  bantuan software POM-QM. Setelah  dilakukan  perhitungan  dengan software tersebut  didapatkan  hasil  yang  sama  dengan perhitungan manual. Sehingga dari faktor pencarian jalur terpendek dengan aturan metode spanning tree lebih  mengoptimalkan  hasil  jalur  distribusi,  jika dibandingkan  dengan  aturan  metode nearest neighbor . Hal ini dikarenakan lebih mengutamakan jalur terpendek pada setiap cabangnya. Saran untuk penelitian  selanjutnya  dapat  mempertimbangkan aspek  biaya  yang  dikeluarkan.  Aspek  biaya  dan
jarak saling berkaitan satu sama lain dengan  tujuan mendapatkan hasil biaya dan jarak yang optimal.

## U CAPAN T ERIMA K ASIH
Ucapan  terimakasih  penulis  sampaikan  kepada pihak  Universitas  Singaperbangsa  Karawang  yang telah membantu jalannya penelitian ini.

## R EFERENSI
[1]   H.  KHIRAM  and  W.  IRAWATI,  “Analisis Perencanaan  Sistem  Distribusi  Pada  PT.Lafarge Cement  Indonesia  Aceh  Besar,” Jurnal  Ilmiah Mahasiswa Ekonomi Manajemen , vol. II, no. 1, pp. 118 - 134, 2017.
[2]   T.  N.  Karundeng,  S.  L.  Mandey,  and  J.  S.  B. Sumarauw,  “Analisis  Saluran  Distribusi  Kayu (Studi  Kasus  di  CV.  Karya  Abadi,  Manado),” Jurnal EMBA , vol. VI, no. 3, pp. 1748 - 1757, 2018.
[3]   S.  S.  F.  Addini  and  M.  Fauzan,  “Penyelesaian Masalah  Rute  Terpendek  Distribusi  Kertas  di  CV. Margotama  Fancindo  Yogyakarta  Menggunakan Metode  Nearest  Neighbor  dan  Metode  Saving Matrix,” Jurnal Matematika S1 , vol. VII, no. 3, pp. 1 -11, 2018.
[4]   C.  W.  Oktavia,  C.  Natalia,  and  I.  Adigunawan, “Penentuan  Jalur  Rute  Distribusi  Produk  Fast Moving  Consumer  Goods  (FMCG)  dengan Menggunakan  Metode  Nearest  Neighbour  (Studi Kasus:  PT.XYZ),” Jurnal  AL-Azhar Indonesia  Seri Sains  dan  Teknologi ,  vol.  V,  no.  2,  pp.  101  -  110, 2019.
[5]   G.  D.  Rembulan,  J.  A.  Luin,  V.  Julianto,  and  G. Septorino, “Optimalisasi Panjang Jaringan Pipa Air Bersih  di  DKI  Jakarta  Menggunakan  Minimum
Spanning  Tree,” Jurnal  INTECH  Teknik  Industri Universitas Serang Raya , vol. VI, no. 1, pp. 75 -87,
2020.
[6]   R.  Ramadan,  Wahyudin  and  E.  N.  A.  Satya, “Optimalisasi Penugasan Kerja dan Distribusi Roti dengan  Metode  Assignment  dan  Spanning  Tree,” Jurnal  Sistem  Teknik  Industri  (JSTI) ,  vol.  XXIII, no. 1, pp. 22 - 33, 2020.
[7]   S.  Martono  and  H.  L.  H.  S.  Warnars,  “Penentuan Rute  Pengiriman  Barang  Dengan  Metode  Nearest Neighbor,” Jurnal  Pengkajian  dan  Penerapan Teknik  Informatika ,  vol.  XIII,  no.  1,  pp.  44  -  57, 2020.
[8]   W.  Prasetyo  and  M.  Tamyiz,  “Vehicle  Routing Problem  dengan  Apliaksi  Metode  Nearest Neighbor,” Journal  of  Research  and  Technolog y, vol. III, no. 2, pp. 88 - 98, 2017.
[9]   H.  J.  Weiss,  POM  -  QM  for  Windows  Version  3, New Jersey: Pearson Education Inc, 2013.
[10]  H.  B.  G.  Kadam,  J.  Mulyana  and  J.  Mulyono, “Penentuan  Rute  Terpendek  dengan  Metode  Tabu Search  (Studi  Kasus),” Scientific  Journal  Widya Teknik , vol. XVII, no. 2, pp. 93 - 102, 2018.
[11]  L.  Leymena,  C.  S.  B.  W,  Yuniaristanto  and  W. Sutopo,  “Analisis  Penentuan  Rute  Distribusi Menggunakan  Metode  Nearest  Neighbor  di  PT. KALOG,”  in Seminar  dan  Konferensi  Nasional IDEC , Surakarta, 2019.
[12]  L.  C.  THASYA  and  NARWEN,  “Menentukan Minimum  Spanning  Tree  dengan  Menggunakan Determinan,” Jurnal Matematika UNAND , vol. VII, no. 2, pp. 84 - 88, 2018.
[13]  F. S. Hillier, G. J. Lieberman, E. G. S. and  A. W. Mulia, Introduction Operation Research, Singapore: McGraw-Hill Inc., 1990.