## Scientific Journal Widya Teknik
Volume 17 No. 2  2018 ISSN 1412-7350

## PENENTUAN RUTE TERPENDEK DENGAN METODE TABU SEARCH
(STUDI KASUS)
Hendra Buc ika  Glen Kadam, Ig. Ja ka Mulyana*, Julius Mulyono Jurusan Teknik Industri, Faku ltas Teknik, Universitas Katolik Widya Mandala Surabaya, Ja lan Ka lijudan 37 Surabaya *Ema il : jmulyono@ukwms.ac.id

## ABSTRAK
Distribusi  atau  pengiriman  merupakan  salah  satu k egiatan  yang  penting  bagi  sebuah  perusahaan.  Beberapa permasalahan  dalam  melakuk an  distribusi  atau  pengiriman  antara  lain  menentukan  banyaknya  k endaraan  yang dipakai, dan juga menentukan rute k endaraan yang dapat dioptimalkan jarak  tempuhnya serta biaya transportasi agar seluruh permintaan  pelanggan  dapat  terpenuhi  sehingga k euntungan opt imal  ak an  diperoleh perusahaan.  Penentuan rute  pengiriman  dengan  menggunakan  metode  nearest  neighbor  dan  tabu  search  menghasilk an  rute  yang  optimal dengan mempertimbangk an jarak  serta k apasitas angkut k endaraan.  Jarak  tempuh pada rute ak tual perusahaan lebih besar daripada jarak  tempuh rute hasil metode. Selisih total jarak  yang dihasilkan yaitu 8.3 k m. Persentase selisih total jarak  yang diperoleh yaitu sebesar 13%, apabila perusahaan menggunakan rute hasil metode mak a perusahaan lebih efisien dalam pendistribusian produk nya dan juga dapat menekan biaya distribusi yang ak an dik eluark an.
Kata kunci : Vehicle Routing Problem (VRP), Nearest Neighbor , Tabu Search , Perencanaan Rute

## I. Pendahul uan
Distribusi  atau  pengiriman  merupakan  salah  satu kegiatan  yang  penting  bagi  sebuah  perusahaan. Beberapa  permasalahan  dala m  me la kukan  distribusi atau  pengiriman  antara  lain  menentukan  banyaknya kendaraan  yang  dipakai,  dan  juga  menentukan  rute kendaraan  yang  dapat  dioptima lkan  jara k  te mpuhnya serta  biaya  transportasi  agar  seluruh  permintaan pelanggan  dapat  terpenuhi  sehingga  keuntungan optima l akan diperoleh perusahaan. Dalam keberhasilan  distribusi  terdapat  beberapa  faktor  yaitu sistem  distribusi.  UD.  X  merupakan  perusahaan  yang bergerak  di  bidang  industri  pembuatan  makanan ringan.  Pengiriman  produk  makanan  ringan  ke pelanggan yang dilakukan perusahaan dalam menentukan  rute  pengiriman masih  berdasarkan pengalaman  dan  sepengetahuan  pengirim,  d imana pengiriman produk yang dilakukan oleh pengirim yang disediakan  oleh  perusahaan  ditentukan  oleh  pengirim sendiri dengan cara me milih jara k yang dirasa pendek. Perbaikan  dala m  masalah vehicle  routing  problem ini dapat menggunakan metode nearest neighbor dan tabu search .  VRP  ( Vehicle  Routing  Problem )  merupakan salah satu pemasalahan transportasi dalam  menentukan rute  kendaraan.  Kendaraan  yang  akan  digunakan me miliki  kapasitas  yang  terbatas  serta  tiap  kendaraan berawal  dan  berakhir  di  suatu  tempat.  Penentuan  rute me rupakan salah satu faktor yang sangat penting dalam me la kukan  pendistribusian  produk  kepada  pelanggan. Penentuan rute distribusi yang optimal dapat me min imasi  ja rak,  me mpersingkat  wa ktu  perjalanan dala m  pendistribusian  produk  dan  menghemat  biaya transportasi.  Dala m  penentuan  rute  kendaraan  untuk distribusi  produk  yang  diproduksi  oleh  UD.  X, perusahaan  meme rlu kan  perbaikan  dala m  perencanaan penentuan  rute  distribusi.  Pe rbaikan  yang  dilaku kan
dengan  menggunakan  metode nearest  neighbor dan tabu  search yaitu  dengan  mencari  rute  dengan  jarak terpendek  dan  dapat  me minimasi  jara k  tempuh kendaraan.

## II. Landasan Teori
II.1 Studi Literatur Dala m studi literatur, beberapa penelit ian sebelumnya  yang  telah  dilakukan  o leh  peneliti terdahulu.  Sebelumnya  ada  beberapa  penelitian  yang telah  dilaku kan  yaitu  oleh  Ali  Mukhsinin,  Arif  Imran, dan  Susy  Susanty  tentang  penentuan  rute  distribusi menggunakan  metode nearest  neighbor dan local search .  Penelitian  yang  telah  dilakukan  oleh  Noer Ikfan  dan  Ilyas  Masudin  yaitu  tentang saving  matrix untuk menentukan rute distribusi. Serta penelit ian oleh Mahardika  A mri,  Arif  Rah man,  dan  Rah mi  Yun iarti tentang  penyelesaian vehicle  routing  problem dengan menggunakan metode nearest neighbor .

## II.2 Vehicle Routing Problem (VRP)
VRP  me rupakan sebuah permasalahan transportasi yang  melibatkan  rute  kendaraan  untuk  me layani pelanggan. Hal ini dapat dila kukan dengan menentukan ju mlah  kendaraan yang akan digunakan serta rute yang akan ditempuh kendaraan dalam  me menuhi permintaan pelanggan.  VRP  bertujuan  untuk  me min imasi  ja rak yang  akan  ditempuh,  me minimasi  wa ktu  tempuh, me min imasi  ju mlah  kendaraan,  dan  tujuan  lainnya yang sesuai dengan permasalahan.
Beberapa  hal  yang  dapat  dipertimbangkan  untuk masalah  VRP  menurut  (Toth,  P.  &  Vigo,  D.,  2002), yaitu:
- Meminimalkan  biaya  transportasi  global, bergantung  pada  jarak  global  yang  ditempuh (atau  pada  waktu  te mpuh  global)  dan  biaya
tetap  yang  terkait  dengan  kendaraan  yang digunakan  (dan  dengan  pengemudi  yang sesuai); - Minimisasi jumlah kendaraan (atau pengemudi)  yang  dibutuhkan  untuk  me layani semua pelanggan;
- Menyeimbangkan  rute,  untuk  waktu  te mpuh dan beban kendaraan;
- Minima lisasi  denda  yang  terkait  dengan layanan parsial pelanggan.
Ko mponen-komponen  yang berkaitan  dala m  VRP yaitu:
1.  Depot
2.  Pelanggan
3.  Pengemudi kendaraan
4.  Rute kendaraan

## II.3 Metode Nearest Neighbor
Metode nearest neighbor merupakan  metode yang sangat  sederhana  dan  pertama  kali  d ipopulerkan  pada tahun 1983.  Pada setiap prosesnya dilakukan pencarian pelanggan  terdekat  dengan  pelanggan  yang  terakhir untuk  ditambahkan  pada  akhir  rute.  Cara  kerja  dari metode  ini  yaitu,  semua  rute  kendaraan  masih  kosong pada  awalnya.  Dimu lai  dari  rute  kendaraan  pertama, metode  ini  me masukkan  satu  persatu  pelanggan terdekat yang belum dikunjungi ke  dala m rute, sela ma me masukkan  pelanggan  tersebut  ke  dalam  rute kendaraan tidak me lebih i kapasitas maksimu m kendaraan.
Algorit ma nearest  neighbor menurut  (Pop,  P.C., dkk. 2011) yaitu :
1. Dimu la i  dari  gudang  atau  depot,  kemudian mencari lokasi pelanggan yang belum dikunjungi  yang  me miliki  jara k  terde kat  dari gudang atau depot. Sebagai lokasi perta ma .
2. Selanjutnya ke lokasi lain yang me miliki ja rak terdekat  dari  lokasi  yang  terpilih  sebelumnya dan jumlah permintaan tidak me lebihi kapasitas muat kendaraan.
3. Apabila  semua  pelanggan  telah  dikunjungi satu kali ma ka a lgorit ma berakh ir.
II.4 Tabu Search
Tabu Search pertama ka li muncul dan diperkenalkan  pada  tahun  1986  oleh  Glover. Tabu Search merupakan  salah  satu  algorit ma  metode heuristik.  Konsep  dari Tabu  Search adalah  suatu algorit ma  yang  menuntun setiap  prosesnya  agar  dapat menghasilkan fungsi tujuan yang paling optimu m tanpa terjebak  ke  dala m  solusi  awal  yang  ditemukan  selama tahapan  ini  berlangsung.  Tujuan  dari  a lgorit ma  ini adalah mencegah terjadinya perulangan dan ditemu kannya solusi yang sama pada suatu iterasi yang akan  digunakan  lagi  pada  iterasi  selanjutnya.  Menurut (Gendreau,  M.,  dkk.  1994),  hasil  yang  diperoleh  pada serangkaian masalah  menunjukkan dengan jelas bahwa tabu search lebih unggul dari  metode heuristik terba ik yang ada.
Langkah-langkah  penentuan  solusi  rute  dengan menggunakan metode tabu search , sebagi berikut:
- Langkah 1
Langkah  perta ma  yaitu  me milih  solusi  awal  untuk dijadikan  iterasi  ke  0.  So lusi  awal  d itentukan dengan  metode nearest  neighbor .  Sehingga  rute tersebut menjadi tabu list pada iterasi ke 0 dan juga sebagai solusi optimu m a wal.
- Langkah 2 Langkah  kedua  menentukan iterasi selanjutnya dan mencari solusi alternatif.  Solusi alternatif dipe roleh dengan  menukar  posisi  2  t itik  lokasi  berdasarkan indeks.
- Langkah 3 Langkah  ketiga  yaitu  me milih  solusi  yang  terbaik diantara solusi alternatif pada langkah 2.
- Langkah 4 Langkah  kee mpat  yaitu  me mpe rbarui tabu  list dengan  me masukkan  solusi  yang  terpilih  pada langkah 3.
- Langkah 5 Langkah kelima  yaitu apabila iterasi telah mencapai sama  dengan  banyaknya  ju mlah  t itik  lokasi  maka, telah sampai ke proses pemberhentian.
III. Metode Pe nelitian
Dala m me laksanakan suatu penelitian diperlukannya  metodologi  penelitian  yang  merupakan langkah-langkah  untuk  mengumpu lkan  data  yang bertujuan  dan  kegunaan  tertentu.  Berikut  merupakan metodologi dala m penelitian ini:
Gambar  3.1 Flowchart Metodologi Penelit ian Studi Literatur Identifikasi Masalah Tahapan Pengelompokk an ( clustering ) Pelanggan Pengumpulan Data Mul ai Studi Lapangan A Seles ai Analisa Kesimpulan dan Saran A Validasi Hasil Pengolahan Data dengan Tabu Search
Pengolahan Data dengan Metode Nearest Neighbor
Gambar  3.2 Flowchart Algoritma Nearest
Neighbor Gambar  3.3 Flowchart Algoritma Tabu Search
IV. Hasil Penelitian dan Pe mbahasan IV.1 Pengumpulan Data Pengumpulan data diperoleh dengan cara wawancara  dan  pengamatan  pada  perusahaan.  Data yang diperoleh sebagai berikut:
a. Sekilas Tentang Perusahaan
b. Data Na ma  dan Lo kasi Pe langgan
c. Data Jara k Pe langgan
d. Data Permintaan Pe langgan
e. Data Kendaraan dan Kapasitas Angkut

## IV.1.1 Sek ilas Tentang Perusahaan
UD.  X  me rupakan  sebuah  perusahaan  yang bergerak  di  bidang  industri  makanan.  UD.  X me mp roduksi  makanan  ringan  atau  kerupuk  yang berbahan  dasar  ikan  tenggiri  dan  bahan -bahan  yang lainnya.  Saat  ini  UD.  X  me miliki  10  pe langgan  tetap untuk mendistribusikan a mplang yang dibuat oleh UD. X sendiri.  Pelanggan-pelanggan dari UD.  X tersebar di Kota Ba likpapan.

## IV.1.2 Data Nama dan Lokasi Pelanggan
Berikut  merupakan  data  nama  dan  alamat pelanggan yang diperoleh dari UD. X:
Mulai
Menentukan
pelanggan terdekat dengan depot
Cari lokasi pelanggan yang paling dekat
dengan lokasi pelanggan sebelumnya Se mua pelanggan telah dila lui?
Selesa i Y a Tid ak
Mulai Menentukan solusi awa l Membuat daftar calon solusi atau me mpe rbarui tabu list Mencari solusi alternatif dengan mengevaluasi solusi Memilih solusi alternatif yang terbaik Pencarian solusi telah selesai? Y a Tid ak Solusi terbaik Selesai
Tabel 4.1 Data Na ma  dan Lo kasi Pe langgan Kode Na ma To ko Ala mat A Ade Jl. Ka rang Jati B Adinda Jl. Pandan Sari C Mitra Jl. Wahab Syarani D KJL Jl. Soeka rno Hatta E Yusniah Jl. MT. Haryono F Ring Road Jl. Ruhui Rahayu I G Biru Mart Jl. Mulawa rman H Sumber Reje ki Jl. Soeka rno Hatta I GJG Jl. MT. Haryono J Susana Jl. Jenderal Sudirman Z Depot Jl. Jenderal A. Yan i

## IV.1.3 Data Jarak  Pelanggan
Berikut  merupakan  data  jarak  antar  perusahaan dengan  pelanggan  maupun  antar  pelanggan  dalam
satuan  kilo meter  yang  diperoleh  dengan  bantuan aplikasi google maps :
Tabel 4.2 Data Jara k Pe langgan a b c d e f g h i j z a 0 2.1 4.5 2.2 6.5 7.7 14.1 2.9 5.7 5.2 2.8 b 2.2 0 5.3 3.5 7.8 8.9 15.4 4.2 6.9 6.5 4 c 6.5 4.3 0 2.9 5.5 8.5 15.1 2.3 9.9 8.4 6 d 3.5 3.1 2.9 0 5.5 6.9 15.1 1 6 6.1 3.7 e 8.2 8.5 8.9 7.2 0 2.9 9.6 8.1 4.4 9.8 8.9 f 8.8 10.8 9.4 9 4.9 0 6.5 8.6 5.2 10.6 9.8 g 15.2 15.3 15.7 15.3 11.2 7.1 0 14.9 9.9 14.6 14 h 4.2 3.8 2.2 1 4.8 7.8 14.4 0 6.7 6.8 12.1 i 5.9 6.6 10 6.9 5.4 4.3 9 7.6 0 5.4 4.7 j 4.3 6.2 9.2 6.3 9.7 8.5 12.9 7 4.2 0 3.3 z 1.6 3.6 6 3.7 8 8.7 14.4 4.3 4.4 2.8 0

## Gambar  4.1 Peta Balikpapan dan Lokasi Pelanggan

## IV.1.4 Data Permintaan Pelanggan
Jumlah  permintaan  pada  produk  makanan  ringan yang  telah  dike mas  dala m  bo x.  Satu  bo x  me mpunyai berat  sebesar  1  kilogra m  dan  dengan  dimensi  1  bo x yaitu  18c m  x  18c m  x  30c m.  Pengiriman  dilaku kan  1 minggu  sekali.  Be rikut  merupakan  data  permintaan yang diperoleh:

## Tabel 4.3 Data Permintaan Pe langgan Mingguan
Pelanggan Jumlah (Bo x) a 5 b 10 c 12 d 12 e 15 f 15 g 12 h 5 i 20
j
10
IV.1.5 Data Kendaraan dan Kapasitas Angkut
Jumlah kendaraan yang digunakan oleh perusahaan  untuk  mengirim  ke  pe langgan  yaitu  ada  2
kendaraan.  Jenis  kendaraan  tersebut  adalah  mobil  bo x yang  berukuran  kecil.  Setiap  kendaraan  me miliki kapasitas  beban  angkut  yang  sama  yaitu  dapat mengangkut sebanyak 70 bo x.

## IV.2 Pengolahan Data
Berikut merupakan pengolahan data yang dila kukan  setelah  me mpero leh  berbagai  data  dari perusahaan.
IV.2.1 Tahapan Pengelompokkan (clustering) Pelanggan Pelanggan  dibagi  menjadi  da la m  2 cluster pengiriman  maka  berikut  me rupakan  tahap-tahap  yang dila kukan:
1. Menggambar  masing-masing  titik  pelanggan dala m  koordinat  kartesius  dan  menetapkan lokasi depot sebagai pusat koordinat.
2. Melakukan pengelompokkan  dimula i dari tit ik yang me miliki kedekatan ja rak dala m koordinat  dan  seterusnya  berurutan  dengan me mpe rhatikan kapasitas kendaraan.
3. Memastikan  semua  titik  termasuk  dalam cluster saat ini.
4. Pengelompokkan dihentikan ket ika  dala m satu cluster akan mencapai atau me lebih i kapasitas ma ksima l dari kendaraan.
5. Membuat cluster baru  dengan  langkah  yang sama seperti langkah 2 d imula i dari tit ik yang belum termasuk dala m cluster sebelumnya.
6. Mengulangi  langkah  2  sampai  5,  sampai semua titik te lah dimasukkan da la m cluster .
Gambar  4.2 Cluster yang Terbentuk
Pada tahapan clustering didapatkan 2 cluster yaitu, cluster 1 yang terdiri dari pelanggan a,  b,  c,  d,  e, dan h sedangkan cluster 2 terdiri dari pelanggan f, g, i, dan j.

## IV.2.2  Solusi  Awal  Rute  dengan  Metode  Nearest Neighbor
Langkah-langkah  dala m  penentuan  solusi  rute dengan  metode nearest  neighbor adalah  sebagai berikut:
- Langkah 1
Dari  depot  menentukan  pelanggan  terdekat pertama yang akan dikunjungi untuk dimasukkan ke  dala m daftar rute.
- Langkah 2 Cari  lokasi  pe langgan  yang  paling  dekat dengan  lokasi  sebelumnya,  lalu  hubungkan kedua  titik  te rsebut,  lanjut  ke  langkah selanjutnya.
- Langkah 3 Set  pelanggan  yang  terpilih  terakh ir  sebagai titik a wal, ulangi langkah 2 hingga semua titik lokasi  telah  dila lui.  Jika  semua  titik  lo kasi telah dila lui lan jut ke langkah selanjutnya.
- Langkah 4 Penentuan rute berhenti ketika semua pelanggan sudah selasai dilalu i. Rute yang dihasilkan untuk cluster 1 ya itu,  z - a - b - d - h  - c  - e -  z, dengan total jara k 24.8  km.  Untuk cluster 2 rute yang dihasilkan yaitu,  z -  j  -  i -  f - g -  z, dengan total jara k 31.8 km.

## IV.2.3  Solusi  Optimal  Rute  dengan  Metode  Tabu Search
Langkah-langkah  penentuan  solusi  rute  dengan menggunakan metode tabu search , sebagi berikut:
- Langkah 1
Langkah  perta ma   yaitu  me milih   solusi  awal untuk  dijadikan  iterasi  ke  0.  Solusi  a wal ditentukan  dengan  metode nearest  neighbor. Sehingga  rute  tersebut  menjadi tabu  list pada iterasi  ke  0  dan  juga  sebagai  solusi  optimu m awal.
- Langkah 2
Langkah kedua menentukan iterasi selanjutnya  dan  mencari  solusi  alternatif. Solusi  alternatif  diperoleh  dengan  menukar posisi  2  tit ik  lo kasi  berdasarkan  indeks.
Banyaknya indeks yaitu 45.
- Langkah 3 Langkah  ketiga  yaitu  me milih  solusi  yang terbaik  diantara  solusi  alternatif  pada  langkah
2.
- Langkah 4
Langkah kee mpat yaitu  me mperbarui tabu list dengan me masukkan solusi yang terpilih pada langkah 3.
- Langkah 5 Langkah  ke lima  yaitu  apabila  iterasi  telah mencapai  sa ma  dengan  banyaknya  jumlah titik  lokasi  ma ka,  te lah  sampai  ke  proses pemberhentian.
Tabel 4.4 Rute Hasil Metode Tabu Search untuk
Cluster 1 Rute Total Jara k (Km) 1  z - a - b - d - h - c  - e  - z 24.8 2  z - a - b - h - d - c  - e  - z 26.2 3  z - a - b - c - d - h - e  - z 26.6 4  z - a - b - c - h - d - e  - z 26.7 5  z - a - b - c - e - d - h - z 34.8 6  z - a - b - c - e - h - d - z 27.3 7  z - a - e - c - b - h - d - z 30.2
Tabel 4.5 Rute Hasil Metode Tabu Search untuk Cluster 2 Rute Total Jara k (Km) 1  z - j - i - f - g - z 31.8 2  z - j - i - g - f - z 32.9 3  z - i - j - g - f - z 39.6 4  z - i - j - f - g - z 38.8 5  z - i - j - g - f - z 39.6
IV.3 Solusi Rute Tanpa Clustering Berikut merupakan pengolahan data yang dila kukan  setelah  me mpero leh  berbagai  data  dari perusahaan.
- Solusi  Awal  Rute  dengan  Metode Nearest Neighbor.
Rute yang dihasilkan: z - a - b - d - h - c  - e  - f - i - j - g - z
- Solusi  Optima l  Rute  dengan  Metode Tabu Search.
Berikut  merupakan  rute  yang  dihasilkan  dari perhitungan metode Tabu Search:
Tabel 4.6 Rute hasil metode Tabu Search
Rute Total Jara k 1 a - b - d - h - c  - e  - f - i - j - g 40.7
2 a - b - d - h - c  - e  - j - i - f - g 39.1 3 b - a - d - h - c  - e  - j - i - f - g 37.9 4 b - a - d - h - c  - e  - i - j - f - g 37.9 5 b - a - d - h - c  - j - i - e - f - g 35.0 6 b - a - c - h - d - j - i - e - f - g 35.1 7 b - a - h - c - d - j - i - e - f - g 35.3
8 b - a - d - c - h - j - i - e - f - g 35.4
9 b - a - c - d - h - j - i - e - f - g 36.4 10 b - a - h - d - c  - j - i - e - f – g 36.4 11 b - c - h - d - a  - j - i - e - f - g
36.3
Dari rute yang dihasilkan metode Tabu Search rute dibagi  menjad i  2  ka rena  perusahaan  menggunakan  2 kendaraan berikut contoh pembagiannya:
Tabel 4.7 Contoh Pembagian Rute Kendaraan 1 Pelanggan  Permintaan Ku mulatif a 5 5 b 10 15 d 12 27 h 5 32 c 12 44 e 15 59 f 15 74
Untuk contoh rute 1 yang dihasilkan yaitu, z  - a - b - d - h - c  - e  - z. Pe langgan f tidak termasuk dala m rute 1 karena akan meleb ihi kapasitas beban angkut kendaraan sehingga pelanggan f akan masuk dala m rute pengiriman kendaraan 2.
Tabel 4.8 Contoh Pembagian Rute Kendaraan 2
Pelanggan  Permintaan Ku mulatif f 15 15 i 20 35 j 10 45 g 12 57
Untuk contoh rute 2 yang dihasilkan yaitu, z  - f - i - j - g - z.
Berikut merupakan hasil pe mbagian rute setiap kendaraan:
Tabel 4.9 Hasil Pe mbagian Rute Kendaraan Rute Jarak (Km) Total Jara k (Km) 1 1 z - a - b - d - h - c  - e  - z 24.8 71.0 2 z - f - i - j - g - z 46.2 2 1 z - a - b - d - h - c  - e  - z 24.8 56.6 2 z - j - i - f - g - z 31.8 3 1 z - b - a - d - h - c  - e  - z 25.6 57.4 2 z - j - i - f - g - z 31.8 4 1 z - b - a - d - h - c  - e  - z 25.6 64.4 2 z - i - j - f - g - z 38.8 5 1 z - b - a - d - h - c  - j - z 22.9 56.1 2 z - i - e - f - g - z 33.2 6 1 z - b - a - c - h - d - j - z 23.0 56.2 2 z - i - e - f - g - z 33.2 Tabel 4.10 Hasil Pe mbagian Rute (Lanjutan) Kendaraan Rute Jarak (Km) Total Jara k (Km) 7 1 z - b - a - h - c - d - j - z 23.2 56.4 2 z - i - e - f - g - z 33.2 8 1 z - b - a - d - c - h - j - z 23.3 56.5 2 z - i - e - f - g - z 33.2 9 1 z - b - a - c - d - h - j - z 24.3 57.5 2 z - i - e - f - g - z 33.2 10 1 z - b - a - h - d - c  - j - z 24.3 57.5 2 z - i - e - f – g - z 33.2 11 1 z - b - c - h - d - a  - j - z 24.2 57.4 2 z - i - e - f - g - z 33.2
Dari tabel d i atas dapat dipilih rute dengan total jara k yang terpendek yaitu nomor 5, dengan hasil sebagai berikut:
Rute pengiriman kendaraan 1 z - b - a - d - h - c  - j - z
Total ja rak
: 22.9 km
Total beban angkut : 54 bo x Rute pengiriman kendaraan 2
z - i - e - f - g - z
Total ja rak
: 33.2 km
Total beban angkut : 62 bo x
IV.4 Validasi Hasil
Pengecekan  yang  dilakukan  dala m  verifikasi  hasil antara lain sebagai berikut:
Hasil Dengan Clustering
- Pengecekan  ju mlah  kapasitas  muatan  dengan beban angkut. a. Kendaraan 1: Kapasitas muatan = 70 bo x Beban angkut permintaan  = 59 bo x Beban  angkut  permintaan  tidak  me lebihi kapasitas muatan. b. Kendaraan 2: Kapasitas muatan = 70 bo x Beban angkut permintaan  = 57 bo x Beban  angkut  permintaan  tidak  me lebihi kapasitas muatan.
- Se mua  konsumen  telah  dila lui  satu  kali  dala m satu kali perja lanan dari rute 1 dan rute 2. Hasil Tanpa Clustering
- Pengecekan  ju mlah  kapasitas  muatan  dengan beban angkut.
a. Kendaraan 1:
Kapasitas muatan = 70 bo x
Beban angkut permintaan  = 54 bo x Beban  angkut  permintaan  tidak  me lebihi kapasitas muatan.
b. Kendaraan 2:
Kapasitas muatan
= 70 bo x
Beban angkut permintaan  = 62 bo x Beban  angkut  permintaan  tidak  me lebihi kapasitas muatan.
- Se mua  konsumen  telah  dila lui  satu  kali  dala m satu kali perja lanan dari rute 1 dan rute 2.

## V. Analisa
V.1 Rute Hasil Metode
Tabel 5.1 Rute Hasil Metode Hasil Dengan Clustering Kendaraan Rute Jarak (Km) Total Jarak (Km) Beban Angkut (Bo x) 1 z - a - b - d - h - c  - e  - z 24.8 56.6 59 2 z - j - i - f - g - z 31.8 57 Hasil Tanpa Clustering 1 z - b - a - d - h - c  - j - z 22.9 56.1 54 2 z - i - e - f - g - z 33.2 62
Rute  yang  dihasilkan  metode  dengan  tahapan clustering  me miliki  total  ja rak  56.6  km.  Sedangkan rute  yang  dihasilkan  metode  tanpa  tahapan  clustering me miliki  total  jara k  56.1  km.  Dari  hasil  tersebut me miliki  sedikit  selisih  total  ja rak  ya itu  0.5  km.  Rute yang dipilih  yaitu rute yang dihasilkan  metode dengan tahapan clustering karena rute tersebut dapat diterapkan  untuk  perusahaan.  Untuk  rute  tanpa clustering tidak dipilih karena urutan-urutan pelanggan dala m  rute  t idak  tepat  sehingga  akan  susah  untuk diterapkan.

## V.2 Analisa Sensitifitas
Analisa sensitifitas terhadap permintaan pelanggan berdasarkan pengalaman perusahaan:
- Jika permintaan pelanggan a, b, c, d, e , dan h mengala mi kenaikan 12 bo x.
Maka hasil rute yang dihasilkan  metode maka rute  mengala mi  perubahan  hanya  pada bertambahnya beban angkut.
- Jika  permintaan  pelanggan  g  mengala mi kenaikan sebesar 50%.
Pada saat permintaan naik 50% di tit ik a  maka hasil  rute  yang  dihasilkan  metode  dan  rute aktual  perusahaan  saat  ini  t idak  berubah namun  hanya  berakibat  pada  bertambahnya beban angkut.

## V.3 Rute Ak tual
Rute  aktual  pengiriman  perta ma  yang  biasa dipakai perusahaan yaitu, z - a  - b - d - h - i - j - z. Total jara k yang ditempuh sejauh 23.6 km dan beban angkut yang dibawa sebanyak 62 bo x.
Rute  aktual  pengiriman  kedua  yang  biasa  dipakai perusahaan yaitu, z  - g  - f - e  - c  -  z. Total  jara k yang ditempuh  sejauh  41.3  km  dan  beban  angkut  yang dibawa sebanyak 54 bo x.

## V.4  Perbandingan  Rute  Aktual  dengan  Rute  Hasil Metode
Berikut  merupakan  perbandingan  dan  persentase selisih  antara  rute  hasil  metode  dengan  rute  aktual perusahaan:
Tabel 5.2 Pe rbandingan dan Presentase Rute Aktual Terhadap Rute Hasil Metode Rute Aktual Rute Hasil Metode Selisih Persentase Jarak (km) 64.9 56.6 8.3 13%
Menurut  tabel  di  atas  dapat  disimpu lkan  bahwa jara k  tempuh  antara  rute  aktual  dengan  rute  hasil metode me miliki  selisih  8.3 km. Berdasarkan perhitungan  persentase  penghematan  jarak  yang  telah dihitung yaitu didapatkan persentase sebesar 13%.  Hal
ini  menunjukkan  bahwa  rute  distribusi  yang digunkan perusahaan  saat  ini  belum  optimal.  Oleh  karena  itu, optimasi  rute  dengan  menggunakan  metode  tersebut dapat  me mbantu  perusahaan  dalam  menekan  biaya distribusi yang akan dikeluarkan.

## VI. Kesimpul an
Rute  yang  diperoleh  dari  hasil  metode  optimasi adalah sebagai berikut:
1. Rute  pengiriman  yang  dihasilkan  untuk kendaraan  1  yaitu,  d imula i  dari  Depot  (UD.  X)  - Toko  A  -  Toko  B  -  Toko  D  -  Toko  H  -  Toko  C  - Toko  E  -  Depot  (UD.  X).  Total  ja rak  yang ditempuh  sejauh  24.8  km  dan  beban  angkut  yang dibawa sebanyak 59 bo x.
2. Rute  pengiriman  yang  dihasilkan  untuk kendaraan  2  yaitu,  d imula i  dari  Depot  (UD.  X)  - Toko J  - Toko  I  - Toko  F  - To ko  G -  Depot (UD.
X). Total  jara k yang ditempuh sejauh 31.8  km dan beban angkut yang dibawa sebanyak 57 bo x. Jarak  te mpuh  pada  rute  aktual  perusahaan  lebih besar  daripada  jarak  tempuh  rute  hasil  metode optimasi.  Se lisih  total  jara k  yang  dihasilkan  yaitu  8.3 km.  Persentase selisih  total  jarak  yang  diperoleh  yaitu sebesar  13%,  apabila  perusahaan  menggunakan  rute hasil  metode  ma ka  perusahaan  lebih  efisien  dala m
pendistribusian  produknya  dan  juga  dapat  menekan biaya distribusi yang akan dike luarkan.

## Daftar Pustaka
1. Mukhsinin,  Ali.,  dkk.  2013.  “Penentuan  Rute Distribusi  CV.  IFFA  Menggunakan  Metode Nearest  Neighbour  dan  Local  Search”.  Jurnal Online Institut Teknologi Nasional.
2. Ikfan,  Noer  dan  Masudin,  Ilyas.  2014.  “ Saving Matrix untuk Menentukan Rute Distribusi”. Jurnal Ilmiah  Tekn ik  Industri.  Progra m  Studi  Tekn ik Industri Un iversitas Muhammadiyah Malang.
3. Amri,  Mahardika .,  d kk.  2014.  “Penyelesaian Vehic le  Routing  Proble m  dengan  Menggunakan Metode  Nearest  Neighbor  (Studi  Kasus:  MTP Nganjuk  Distributor  PT.  Coca  Cola )”.  Jurusan Teknik Industri Universitas Bra wijaya.
4. Toth, P. dan Vigo,  D. 2002.  “The  Vehic le Routing Proble m”. Un iversita degli Studi d i Bologna Italy.
5. Pop,  P.C.,  d kk.  2011.  “ Heuristic  Algorith ms  for Solving the Generalized Vehic le Routing Proble m”.  Int.  J.  of  Co mputers,  Commun ications & Control.
6. Gendreau,  M.,  dkk.  1994.  “Tabu  Search  Heuristic for  the  Vehic le  Routing  Proble m”.  Management Science,  Vo l.  40,  No.  10  (Oct.,  1994),  p.  1276- 1290.
7. .