Performa: Media Ilmiah Teknik Industri ISSN 1412-8624 (cetak)  |  ISSN 2620-6412 (online) Vol. 22, No. 1, 2023, Hal. 58-66

## Penentuan Rute Distribusi Produk AMDK Menggunakan
Pengembangan Algoritma Clarke and Wright Savings

## di PT SMN
Nur Muhammad Yusuf 1  , Sukoyo 2
1,2 Program Studi Teknik Industri, Fakultas Teknologi Industri, Institut Teknologi Bandung Jl. Ganesha 10, Lb. Siliwangi, Coblong, Bandung, 40116, Indonesia Email: nmyucup@gmail.com 1 , sukoyo@itb.ac.id 2

## Abstrak
PT SMN merupakan salah satu perusahaan yang bergerak di bidang produksi, distribusi,  dan pemasaran produk Air Minum dalam Kemasan (AMDK). Rute distribusi produk AMDK harus dioptimasi agar biaya distribusi lebih murah. Pendekatan optimasi yang digunakan pada penelitian ini adalah pendekatat heuristik. Algoritma Clarke and  Wright Savings dan Sequential Insertion merupakan algoritma yang menggunakan pendekatan heuristik. Pada penelitian ini, algoritma Clarke  and  Wright  Savings digunakan  sebagai  algoritma  acuan  dalam  penyelesaian  permasalahan  dan Sequential Insertion digunakan sebagai pembanding performansi dari algoritma acuan. Penelitian ini bertujuan untuk menyelesaikan permasalahan distribusi di PT SMN dengan menggunakan pengembangan algoritma Clarke and Wright Savings .  Pengembangan  algoritma  dilakukan  untuk  mengakomodasi  kendala  waktu  operasional  distribusi  dan mengubah cara pemilihan titik pelanggan ke dalam rute menggunakan konsep head dan tail. Penyelesaian permasalahan penentuan  rute distribusi  produk  AMDK  di  PT  SMN  menghasilkan  biaya  yang  lebih  rendah  dibandingkan  kondisi eksisting dengan perbaikan biaya distribusi sebesar 27,56% yaitu Rp689.332 dalam seminggu. Hasil pengembangan algoritma juga menghasilkan biaya yang lebih rendah dibandingkan solusi algoritma acuan Clarke and Wright Savings dan Sequential Insertion.
Kata kunci : vehicle routing problem, capacitated vehicle routing problem, algoritma Clarke and Wright Savings

## Abstract
PT  SMN  is  one  of the  companies  engaged in the  production,  distribution, and  marketing  of  bottled  drinking  water products. The distribution route of bottled drinking water products must be optimized to reduce distribution costs. The optimization approach used in this research is a heuristic approach. The Clarke and Wright Savings and Sequential Insertion  algorithms  are  heuristic  algorithms  used  in  this  study.  In  this  research,  the  Clarke  and  Wright  Savings algorithm is used as the  reference  algorithm  for problem-solving, and  Sequential Insertion is  used  to  compare the performance of the reference  algorithm.  The  aim of this  study is to  solve  the  distribution problems  at  PT  SMN  by developing  the  Clarke  and  Wright  Savings  algorithm.  The  algorithm  development  is  carried  out  to  accommodate operational time constraints in distribution and change the way customer points are selected in routes using the head and tail concept. Solving the problem of determining the distribution routes of bottled drinking water products at PT SMN results in lower costs compared to the existing conditions, with a distribution cost improvement of 27.56%, which is Rp689,332 per week. The results of algorithm development also yield lower costs compared to the solutions of the reference algorithms, Clarke and Wright Savings, and Sequential Insertion .
Keywords : vehicle routing problem, capacitated vehicle routing problem, Clarke and Wright Savings algorithm

## 1. Pendahuluan
PT  SMN  merupakan  perusahaan  yang  bergerak di bidang  produksi,  distribusi,  dan  pemasaran  Air  Minum dalam Kemasan (AMDK). Distribusi produk PT SMN ke pelanggannya  harus  ditentukan  rutenya  sehingga  biaya distribusi  yang  dikeluarkan  menjadi  lebih  murah. Penentuan rute bertujuan untuk menghasilkan distribusi yang  efisien.  Penentuan  rute  distribusi  disebut  sebagai Vehicle Routing Problem (VRP) atau permasalahan rute kendaraan.
Salah satu varian VRP adalah Capacitated Vehicle
Routing Problem (CVRP). CVRP merupakan permasalahan  VRP  yang  mempertimbangkan  kendala
 Penulis korespondensi
kapasitas  kendaraan.  CVRP  dapat  diselesaikan  dengan pendekatan eksak, heuristik, dan metaheuristik. Pendekatan  eksak  tidak  cocok  digunakan  pada permasalahan yang kompleks karena akan membutuhkan waktu komputasi yang cukup lama. Pendekatan heuristik lebih  cocok  untuk  digunakan  karena  penyelesaiannya lebih  cepat  dan  hasil  yang  diperoleh  cukup  baik.  Salah satu  pendekatan  heuristik  yang  dapat  digunakan  untuk menyelesaikan  permasalahan  CVRP  yaitu  algoritma Clarke and Wright Savings dengan kendala kapasitas. Algoritma Clarke and Wright Savings telah umum digunakan pada beberapa penelitian. Penelitian menggunakan algoritma Clarke and Wright Savings yang
mempertimbangkan  kendala  kapasitas  telah  dilakukan untuk  memecahkan  permasalahan  penentuan  rute (Rupiah,  et  al.,  2017).  Selain  itu,  algoritma Clarke  and Wright Savings juga dapat ditemukan pada penelitian lain yang tidak hanya mempertimbangkan kendala kapasitas, melainkan juga mempertimbangkan kendala waktu untuk memecahkan permasalahan penentuan rute (Octora et al., 2017).  Dalam  kedua  penelitian  tersebut,  masalah penentuan  rute  diselesaikan  menggunakan  algoritma Clarke  and  Wright  Savings dan  algoritma Sequential Insertion. Algoritma Sequential Insertion menghasilkan hasil  biaya  distribusi  yang  lebih  murah  dibandingkan dengan algorima Clarke and Wright Savings.
Penggunaan  algoritma Clarke  and  Wright  Savings juga ditemukan dalam penelitian lain (Meilani & Iswara, 2018).  Penelitian  tersebut  menyelesaikan  permasalahan penentuan rute distribusi LPG. Setelah menentukan rute menggunakan algoritma Clarke and Wright Savings, rute diperbaiki dengan algoritma lain yaitu algoritma Branch and Bound. Penelitian ini membuktikan hasil biaya yang lebih  murah  dibandingkan  dengan  kondisi  aktual perusahaan.
Penelitian penentuan rute distribusi produk AMDK menggunakan algoritma Clarke and Wright Savings juga dapat ditemukan pada penelitian lain (SM et al., 2017). Penelitian  menggunakan  algoritma Clarke  and  Wright Savings untuk  menyelesaikan  permasalahan  distribusi produk  makanan  juga  telah  dilakukan  sebelumnya (Arifudin  et  al.,  2017).  Kedua  penelitian  tersebut membandingkan penggunaan  metode saving matrix dan algoritma Clarke  and  Wright  Saving. Hasilnya menunjukkan  bahwa  algoritma Clarke  and  Wright Saving dapat menghasilkan hasil biaya yang lebih murah dibandingkan  kondisi  eksisting  dan  metode saving matrix.
Pada  awalnya,  algoritma Clarke  and  Wright Savings hanya  mempertimbangkan  kendala  kapasitas kendaraan  saja.  Namun,  pada  kondisi  nyata  distribusi juga  dibatasi  oleh  waktu  operasional  distribusi. Perusahaan  telah  menetapkan  batas  waktu  operasional distribusi sesuai dengan jam kerja. Selain itu, algoritma Clarke  and  Wright  Savings menentukan  urutan  rute dengan  mempertimbangkan  nilai  penghematan dari pasangan dua titik pelanggan saja, tanpa mempertimbangkan  nilai  penghematan  terhadap  titik- titik  pelanggan  yang  telah  dimasukkan  sebelumnya. Pendekatan  ini  perlu  diperbaiki  ulang  menggunakan algoritma lain.
Algoritma Clarke  and  Wright  Savings perlu dikembangkan agar dapat digunakan untuk menyelesaikan permasalahan di PT SMN.
Pengembangan algoritma dilakukan untuk mengakomodasi  kendala  waktu  operasional  distribusi dan  mengubah  proses  penentuan  rute  dengan  cara mempertimbangkan  nilai  penghematan  terhadap  titik- titik  yang  telah  dimasukkan  ke  dalam  rute  sementara yang terbentuk menggunakan konsep head dan tail . Head
dan tail merupakan  konsep  memilih  titik  dengan  cara menentukan  pasangan  titik  sebagai  kepala  ( head )  dan ekor ( tail ) awal, kemudian menambah titik baru sebagai head atau tail dan  mempertahankan  titik  yang  sudah terpilih sebelumnya . Selain itu, pada penelitian ini juga dilakukan  perbandingan  biaya  distribusi  usulan  dengan kondisi  eksisting  serta  perbandingan  biaya  distribusi usulan  dengan  biaya  distribusi  hasil  algoritma  acuan Clarke  and  Wright  Savings dan  algoritma Sequential Insertion .

## 2. Metode Penelitian

## 2.1. Karakteristik Sistem
Objek pada penelitian ini adalah pusat distribusi PT SMN  yang  terletak  di  Ngadirojo,  Wonogiri,  Jawa Tengah. PT SMN beroperasi selama lima hari dalam satu minggu  dan  penelitian  ini  hanya  akan  menyelesaiakan permasalahan  distribusi  PT  SMN  selama  satu  minggu. PT  SMN  memiliki  dua  unit  kendaraan  yaitu truck dan pickup masing-masing  memiliki  kapasitas  6500  kg  dan 2000  kg.  Masing-masing  kendaraan  memiliki  batas waktu operasional distribusi selama 8 jam perhari mulai dari pukul 08:00 sampai pukul 16:00. Kedua kendaraan memiliki  biaya  tetap  yang  dihitung  sebagai  upah  sopir dan  kenek sebesar  Rp150.000  untuk  setiap  kendaraan. Masing-masing kendaraan juga  memiliki biaya  variabel yang  diestimasi  dari  biaya  bahan  bakar  kendaraan sebesar Rp1.046/km untuk truck dan Rp1.429/km untuk pickup .
PT SMN memiliki enam jenis produk AMDK yaitu cup 120 ml, cup 220 ml, botol 300 ml, botol 600 ml, botol 1500 ml, dan galon 19 liter. Masing-masing jenis produk tersebut dikonversikan ke satuan berat yang dapat dilihat pada Tabel 1.
Tabel 1. Jenis produk PT SMN dan konversi beratnya
No Nama produk Jumlah produk (pcs/unit) Berat satuan (kg/pcs) Berat kemasan (kg/unit) Berat (kg/unit) 1 Cup 120 ml 45 0,12 0,3 5,70 2 Cup 220 ml 48 0,22 0,3 10,86 3 Botol 330 ml 24 0,33 0,3 8,22 4 Botol 600 ml 18 0,60 0,3 11,10 5 Botol 1500 ml 12 1,50 0,3 18,30 6 Galon 19 liter 1 19,00 1 20,00
Data  permintaan  pelanggan  PT  SMN  selama  lima hari berturut-turut yang telah dikonversi ke dalam satuan berat ditunjukkan pada Tabel 2, Tabel 3, Tabel 4, Tabel 5, dan Tabel 6.
Tabel 2. Data permintaan pelanggan hari ke-1
Kode pelanggan Kode alamat Jumlah permintaan (kg) M001 A 1481 M002 B 727 M003 C 985 M004 D 200 M005 E 910 M006 F 540 M007 G 514 Tabel 3. Data permintaan pelanggan hari ke-2 Kode pelanggan Kode alamat Jumlah permintaan (kg) M008 H 810 M009 I 315 M010 J 400 M011 K 305 M012 L 2457 M013 M 167 M014 N 122 M015 O 66 Tabel 4. Data permintaan pelanggan hari ke-3 Kode pelanggan Kode alamat Jumlah permintaan (kg) M016 P 5766 M017 Q 387 M018 R 153 Tabel 5. Data permintaan pelanggan hari ke-4 Kode pelanggan Kode alamat Jumlah permintaan (kg) M019 S 967 M020 T 1220 M021 U 1120 M022 V 2758 M023 W 1819 M001 A 109 Tabel 6. Data permintaan pelanggan hari ke-5 Kode pelanggan Kode alamat Jumlah permintaan (kg) M024 X 1092 M025 Y 578 M008 H 692 M026 Z 355 M010 J 255 M027 AA 420 M028 AB 1380 M029 AC 80 M030 AD 257
2 .2. Model Matematis
Permasalahan  rute  distribusi  produk  di  PT  SMN dapat diilustrasikan pada Gambar 1 dan diformulasikan menjadi model sebagai berikut.
a. Indeks
Tabel 7. Notasi indeks Notasi Deskripsi 𝑁 {0,1,2,3, … , 𝑛} ,  himpunan  seluruh  titik pelanggan.  0  untuk  depot  dan  1  sampai 𝑛 untuk pelanggan yang dilayani 𝐾 {0,1,2, … , 𝑘} , himpunan kendaraan berbagai tipe kapasitas
b. Parameter
Tabel 8. Notasi parameter Notasi Satuan Deskripsi 𝐵𝑇 𝑘 Rp
biaya tetap kendaraan 𝑘 untuk 𝑘 ∈ 𝐾 𝐵𝑉 𝑘 Rp/km biaya variabel jarak tempuh kendaraan 𝑘 untuk 𝑘 ∈ 𝐾
𝑐 𝑖𝑗 km jarak tempuh dari titik 𝑖 ke titik 𝑗 untuk 𝑖, 𝑗 ∈ 𝑁 𝑑 𝑖 kg
permintaan pelanggan 𝑖 untuk 𝑖 ∈ 𝑁 𝑄 𝑘 kg kapasitas kendaraan 𝑘 untuk 𝑘 ∈ 𝐾
𝑇 𝑘 jam waktu operasional distribusi kendaraan 𝑘 untuk 𝑘 ∈ 𝐾 𝑉 𝑘 km/jam kecepatan rata-rata kendaraan 𝑘 untuk 𝑘 ∈ 𝐾 𝑆𝑇 𝑖 jam
waktu pelayanan masing-masing pelanggan 𝑖 untuk 𝑖 ∈ 𝑁

## c. Variable Keputusan
Tabel 9. Notasi variabel keputusan Notasi Deskripsi 𝑥 𝑖𝑗 𝑘
Variabel  biner  lintasan  terpilih.  Bernilai  1  jika kendaraan 𝑘 melakukan  perjalanan  dari 𝑖 ke 𝑗 dan bernilai  0  jika  kendaraan 𝑘 tidak  melakukan perjalanan dari 𝑖 ke 𝑗 untuk 𝑖, 𝑗 ∈ 𝑁 dan 𝑘 ∈ 𝐾
Gambar 1. Ilustrasi permasalahan rute distribusi PT SMN
2.2.1. Fungsi Tu juan
Fungsi tujuan dari penelitian ini adalah meminimasi biaya  distribusi  yang  terdiri  dari  biaya  tetap  dan  biaya variabel.  Biaya  tetap  ( 𝐵𝑇 𝑘 ) merupakan  biaya  yang berkaitan  dengan  kendaraan  jika  kendaraan  tersebut digunakan dan akan bernilai nol jika kendaraan tersebut tidak  digunakan.  Dalam  model  matematis,  nilai  biaya tetap  ditentukan  oleh  variabel  keputusan 𝑥 0𝑗 𝑘 . Biaya tetap akan dihitung jika 𝑥 0𝑗 𝑘 bernilai 1 yang berarti bahwa  kendaraan 𝑘 digunakan  dari  depot  0  untuk melayani  minimal  1  pelanggan 𝑗 . Biaya  variabel ( 𝐵𝑉 𝑘 ) berkaitan  dengan  jarak  tempuh  ( 𝑐 𝑖𝑗 ) atau  bahan bakar  yang  dikeluarkan  per  satuan  jarak.  Berdasarkan kedua komponen biaya tersebut maka didapatkan fungsi tujuan  pada  Persamaan  (1)  dengan  biaya  tetap (𝐹) diuraikan  pada  Persamaan  (2)  dan  biaya  variabel (𝑉) diuraikan pada Persamaan (3).
𝑀𝑖𝑛 𝑍 = 𝐹 +  𝑉 (1) 𝐹𝐶 = ∑ ∑ 𝐵𝑇 𝑘 𝑗∈𝑁 × 𝑥 0𝑗 𝑘 𝑘∈𝐾 (2)
𝑉𝐶 = ∑ ∑ ∑ 𝐵𝑉 𝑘 × 𝑐 𝑖𝑗 × 𝑥 𝑖𝑗 𝑘 𝑗∈𝑁 𝑖∈𝑁 𝑘∈𝐾 (3)

## 2.2.2. Batasan Model
Batasan model yang dibangun dalam penelitian ini adalah sebagai berikut:
a. Setiap pelanggan dikunjungi tepat satu kali.
∑ ∑ 𝑥 𝑖𝑗 𝑘 𝑖∈𝑁 𝑘∈𝐾 = 1, 𝑗 ≠ 0, 𝑖 ≠ 𝑗, ∀𝑗 ∈ 𝑁 (4)
b. Total  jumlah  permintaan  pelanggan  dalam  satu rute kendaraan tidak melebihi kapasitas kendaraan yang melayani rute tersebut.
∑ ∑ 𝑑 𝑗 𝑖∈𝑁 𝑗∈𝑁 𝑥 𝑖𝑗 𝑘 ≤ 𝑄 𝑘 , 𝑖 ≠ 𝑗, ∀𝑘 ∈ 𝐾 (5)
c. Setiap rute perjalanan harus berawal dari depot.
∑ 𝑥 0𝑗 𝑘 𝑗∈𝑁 ≤ 1, ∀𝑘 ∈ 𝐾 (6)
d.
Setiap  kendaraan  yang  mengunjungi  satu  titik pasti akan meninggalkan titik tersebut (kontinu)
∑ ∑ 𝑥 𝑖𝑗 𝑘 𝑖∈𝑁 𝑗∈𝑁 − ∑ ∑ 𝑥 𝑖𝑗 𝑘 𝑗∈𝑁 𝑖∈𝑁 = 0, ∀𝑘 ∈ 𝐾 (7)
e. Setiap rute perjalanan harus berakhir di depot
∑ 𝑥 𝑖0 𝑘 𝑖∈𝑁 ≤ 1, ∀𝑘 ∈ 𝐾 (8)
f. Setiap rute perjalanan tidak boleh melebihi batas waktu operasional distribusi kendaraan
(∑ ∑( 𝑗∈𝑁 𝑖∈𝑁 𝑐 𝑖𝑗 𝑉 𝑘 + 𝑆𝑇 𝑗 ) × 𝑥 𝑖𝑗 𝑘 )) ≤ 𝑇 𝑘 , ∀𝑘 ∈ 𝐾 (9)
g. Variabel keputusan 𝑥 𝑖𝑗 𝑘 merupakan integer biner, bernilai  1  jika  kendaraan 𝑘 mengunjungi  titik 𝑗 dari titik 𝑖 , dan bernilai 0 jika kendaraan 𝑘 tidak mengunjungi titik 𝑗 dari titik 𝑖 . 𝑥 𝑖𝑗 𝑘 ∈ {0,1}, ∀ 𝑖, 𝑗 ∈ 𝑉, ∀𝑘 ∈ 𝐾 (10)
2 .3. Modifikasi Usulan Algoritma Clarke and Wright Savin gs Pada algoritma Clarke and Wright Savings , kendala waktu  belum  dipertimbangkan  dan  penggabungan  rute hanya  mempertimbangkan  nilai  penghematan  untuk masing-masing  dua  titik  saja  dalam list nilai penghematan.  Pada  saat  penggabungan  rute,  titik-titik dimasukkan  berdasarkan  urutan  keseluruhan  nilai penghematan  yang  didapatkan.  Modifikasi  yang diusulkan  yaitu  dengan  menambah  kendala  waktu  total distribusi  dan  mengubah  penggabungan  rute  dengan
mempertimbangkan  titik-titik  yang  telah  dipilih sebelumnya.  Diagram  alir  modifikasi  usulan  algoritma Clarke and Wright Savings ditunjukkan pada Gambar 2. Berdasarkan  Gambar  2,  terdapat  lima  tahapan umum penyelesaian  menggunakan  modifikasi algoritma Clarke and Wright Savings sebagai berikut:
1. Menentukan Matriks Jarak Pada  tahap  ini,  jarak  antar  depot  ke  masing- masing titik dan jarak antar titik ditentukan dengan menggunakan  bantuan Google  Maps. Tujuan penggunaan Google  Maps adalah  agar  jarak  yang didapatkan merupakan jarak riil sesuai dengan akses jalan yang ada. Seluruh jarak yang telah didapatkan dibentuk  menjadi  sebuah  matriks.  Contoh  matriks jarak dapat dilihat pada Tabel 10.
Tabel 10. Contoh matriks jarak Node Depot 1 2 3 4 Depot 0 17 3 8 2 1 17 0 14 10 12 2 3 14 0 3 1 3 8 10 3 0 5 4 2 12 1 5 0
2. Menentukan Saving Matrix
Matriks jarak yang telah didapatkan pada tahap sebelumnya  digunakan  untuk  menentukan saving matrix pada  tahap  ini. Saving  matrix merupakan matriks  yang  terbentuk  dari saving  value . Berdasarkan  matriks  jarak  yang  telah  ditentukan pada Tabel 10, maka didapatkan saving matrix yang dapat dilihat pada Tabel 11.
Tabel 11. Contoh saving matrix Node 1 2 3 4
1 0 6 15 7 2 6 0 8 4
3 15 8 0 5 4 7 4 5 0 3. Menentukan Head dan Tail Awal Saving  matrix yang  didapatkan  dari  tahap sebelumnya  diurutkan  dari  pasangan  titik  yang memiliki saving  value terbesar  hingga  terkecil. Saving  value bersifat  simetris  sehingga 𝑆 𝑖𝑗 =   𝑆 𝑗𝑖 .
Kemudian  dibuat  rute  pertama  kendaraan 𝑘 1 dan melakukan  iterasi  untuk  menetukan head dan tail awal. Head dan tail awal merupakan pasangan titik yang  memiliki saving  value terbesar.  Namun,  jika terdapat  pasangan  titik  yang  memiliki  nilai saving value sama  maka  diambil  pasangan  titik  yang memiliki jarak terdekat.
Sebelum  pasangan  titik  ini  ditentukan  sebagai head dan tail awal,  pasangan  titik  ini  diuji  terlebih
dahulu ke dalam kendala kapasitas dan  waktu. Jika kendala  waktu  dan  kapasitas  terpenuhi  maka pasangan titik tersebut ditentukan sebagai head dan tail awal, list  saving  value dihapus  untuk  iterasi berikutnya.  Jika  pasangan  titik  tidak  memenuhi kendala kapasitas dan waktu maka list saving value dihapus dan dilakukan pencarian ulang head dan tail awal. List  saving  value dari  Tabel  11  dapat  dilihat pada Tabel 12.
Iterasi 0
Tabel 12. Iterasi 0 Saving value (𝒊, 𝒋) 15 (1,3)
8 (2,3)
7 (1,4)
6 (1,2)
5 (3,4) 4 (2,4)
Berdasarkan  Tabel  12,  maka  titik  1  dan  3 ditetapkan  sebagai head dan tail awal  (memenuhi kendala kapasitas dan waktu). Rute sementara yang terbentuk: Depot – 1 – 3 – Depot.
4. Menentukan Head dan Tail Baru Setelah ditentukan head (titik 1) dan tail (titik 3) awal,  tahap  selanjutnya  adalah  menentukan  titik selanjutnya yang digabungkan ke dalam rute. Saving value antara titik yang tersisa dengan head dan titik yang  tersisa  dengan tail dibandingkan  untuk menentukan apakah  yang  akan diganti adalah head atau tail dengan  titik  yang  baru.  Jika saving  value titik head dengan  titik  tersisa  lebih  besar  daripada saving value titik tail dengan titik tersisa, maka yang diganti  adalah head dengan  titik  yang  baru  dan berlaku sebaliknya.
Namun, sebelum head atau tail diganti dengan titik yang baru, titik yang ditambahkan diuji terlebih dahulu ke dalam kendala kapasitas dan  waktu. Jika kendala  waktu  dan  kapasitas  terpenuhi  maka  titik tersebut ditentukan sebagai head atau tail baru, list saving  value dihapus  untuk  iterasi  berikutnya.  Jika titik  tidak  memenuhi  kendala  kapasitas  dan  waktu maka list saving value dihapus. Jika masih terdapat list  saving  value maka  iterasi  dilanjutkan  dengan menentukan head dan tail baru.  Namun,  jika  tidak terdapat list saving  value tersisa  maka  iterasi dilakukan dengan memulai kembali dari menentukan head dan tail awal pada rute kendaraan selanjutnya ( 𝑘 = 𝑘 + 1) .
Gambar 2. Digram alir algoritma pencarian solusi
Iterasi 1 Tabel 13. Iterasi 1 Saving value (𝒊, 𝒉𝒆𝒂𝒅) Saving value (𝒕𝒂𝒊𝒍, 𝒋) 7 (4,1) 8 (3,2) 6 (2,1) 5 (3,4)
Maka  titik  yang  dipilih  untuk  dimasukkan  ke dalam  rute  sementara  adalah  titik  2  menggantikan titik 3 sebagai tail (memenuhi kendala kapasitas dan waktu) . Rute sementara yang terbentuk: Depot – 1 – 3 – 2 – Depot.
Iterasi 2
Tabel 14. Iterasi 2 Saving value (𝒊, 𝒉𝒆𝒂𝒅) Saving value (𝒕𝒂𝒊𝒍, 𝒋) 7 (4,1) 4 (2,4)
Maka  titik  yang  dipilih  untuk  dimasukkan  ke dalam  rute  sementara  adalah  titik  4  menggantikan titik  1  sebagai head (memenuhi  kendala  kapasitas dan waktu) . Rute sementara yang terbentuk: Depot –
4 – 1 – 3 – 2 – Depot.
5. Menentukan Rute Iterasi diselesaikan jika seluruh kendaran telah memenuhi  kendala  kapasitas  dan  waktu  atau  jika
seluruh  titik  telah  terpenuhi  permintaannya.
Penentuan rute dilakukan dengan cara menambahkan titik depot pada kedua ujung rute-rute yang telah didapatkan pada iterasi sebelumnya. Jarak antar  titik  bersifat  simetris  sehingga  rute  yang dihasilkan juga bersifat simetris atau sama saja jika didistribusikan dari arah sebaliknya. Rute terbentuk: Depot – 4 – 1 – 3 – 2 – Depot atau Depot – 2 – 3 – 1 – 4 – Depot.
3. Hasil dan Pembahasan
Permasalahan  yang  akan  diselesaikan  adalah permasalahan penentuan rute distribusi PT SMN selama satu  minggu.  Rute  distribusi  eksisting  PT  SMN selama satu  minggu  ditunjukkan  pada  Tabel  15.  Pada  kondisi eksisting,  dua  kendaraan  yang  dimiliki  PT  SMN  yaitu truck dan pickup dioperasikan setiap hari dan melakukan satu kali pengiriman dalam satu hari selama lima hari per minggu.  Pada  kondisi  eksisting,  total  biaya  distribusi selama satu minggu sebesar Rp2.501.058 dengan rincian yang dapat dilihat pada Tabel 15.
Selanjutnya, Tabel 16 menunjukkan hasil penyelesaian rute distribusi PT SMN menggunakan hasil pengembangan  modifikasi  algoritma  selama  satu
minggu.  Secara  total,  biaya  distribusi  yang  diperlukan berkurang  menjadi  Rp1.811.726  selama  satu  minggu. Dari tabel tersebut juga didapatkan bahwa distribusi PT SMN pada hari pertama, kedua, ketiga, dan kelima hanya membutuhkan satu jenis kendaraan saja yaitu truck . Pada hari ke empat, rute usulan yang dihasilkan sama dengan kondisi eksiting PT SMN dan tidak ada perubahan. Biaya tetap distribusi berkurang karena kendaraan pickup hanya beroperasi 1 hari dalam seminggu, sedangkan kendaraan
truck beroperasi  setiap  hari  selama  seminggu.  Biaya variabel  juga  berkurang  yang  direpresentasikan  dengan pengurangan  jarak  tempuh  dari  886  kilometer  menjadi 846 kilometer.
Berdasarkan rute distribusi eksisting PT SMN pada Tabel 15 dan rute distribusi usulan pada Tabel 16, maka didapatkan ringkasan perbandingan indikator performansi  rute  distribusi  eksisting  dan  usulan  yang dapat dilihat pada Tabel 17.
Tabel 15. Rekap rute distribusi eksisting PT SMN
Hari ke- Kendaraan Rute
Jarak tempuh (km) Biaya transportasi
Total biaya Biaya tetap Biaya variabel 1 Truck Depot - A - B - C - D - Depot 80 Rp150.000 Rp83.860 Rp457.988 Pickup Depot - E - F - G - Depot 52 Rp150.000 Rp74.308 2 Truck Depot - H - I - J - K - L - Depot 92 Rp150.000 Rp96.232 Rp430.528 Pickup Depot - M - N - O - Depot 24 Rp150.000 Rp34.296 3 Truck Depot - P - Depot 166 Rp150.000 Rp173.636 Rp525.080 Pickup Depot - Q - R - Depot 36 Rp150.000 Rp51.444 4 Truck Depot - S - T - U - V - Depot 264 Rp150.000 Rp276.144 Rp676.174 Pickup Depot - W - A - Depot 70 Rp150.000 Rp100.030 5 Truck Depot - X - Y - H - Z - J - AA - AB - Depot 90 Rp150.000 Rp94.140 Rp411.288 Pickup Depot - AC - AD - Depot 12 Rp150.000 Rp17.148 Total 886 Rp1.500.000 Rp1.001.058 Rp2.501.058
Tabel 16. Rekap rute distribusi usulan PT SMN
Hari ke- Kendaraan Rute
Jarak tempuh (km)
Biaya transportasi
Total biaya Biaya tetap Biaya variabel 1 Truck Depot - F - E - G - C - A - B - D - Depot 118 Rp150.000 Rp123.428 Rp273.428 Pickup - - - - 2 Truck Depot - N - M - H - O - I - J - K - L - Depot 94 Rp150.000 Rp98.324 Rp248.324 Pickup - - - - 3 Truck Depot - Q - R - P - Depot 200 Rp150.000 Rp209.200 Rp359.200 Pickup - - - - 4 Truck Depot - S - T - U - V - Depot 264 Rp150.000 Rp276.144 Rp676.174 Pickup Depot - W - A - Depot 70 Rp150.000 Rp100.030 5 Truck Depot - X - Y - H - Z - J - AA - AB - AC - AD - Depot 100 Rp150.000 Rp104.600 Rp254.600 Pickup - - - - Total 846 Rp900.000 Rp911.726 Rp1.811.726
Tabel 17. Perbandingan indikator performansi eksisting dan usulan PT SMN Indikator performansi Satuan Eksisting Solusi Perbaikan/s avings (a) (b) (c) (d) (e)=((c)-(d))/(c) Total Biaya Rp 2.501.058 1.811.726 27,56% Jumlah Kendaraan Unit 10 6 40% Jarak Tempuh Km 886 846 4,51%
Pada Tabel 17, total biaya rute distribusi PT SMN selama  satu  minggu  berkurang  sebesar  Rp689.332 dengan persentase perbaikan sebesar 27,56%. Perbaikan tersebut  dihasilkan  dari  adanya  pengurangan  jumlah kendaraan  yang  digunakan  sebesar  40%  sebagai  biaya
tetap  dan  pengurangan  jarak  tempuh  sebesar  4,51% sebagai  biaya  variabel.  Dari  data  tersebut  dapat  dilihat bahwa  PT  SMN  hanya  membutuhkan  satu  jenis kendaraan ( truck ) untuk melakukan distribusinya selama empat dari total lima hari dalam satu  minggu. PT SMN
dapat  memperhatikan  penggunaan  kendaraan  untuk distribusi dengan mempertimbangkan alternatif- alternatif distribusi yang lain.
Selanjutnya,  performansi  modifikasi  algoritma usulan dibandingkan dengan algoritma acuan Clarke and Wright Savings dan algoritma Sequential Insertion . Data yang  digunakan  merupakan  data  dari  penelitian sebelumnya  dengan  menyesuaikan  kendala-kendalanya (Rupiah  et  al.,  2017).  Secara  berturut-turut,  hasil penentuan  rute  menggunakan  algoritma  acuan Clarke and Wright Savings , algoritma Sequential Insertion , dan algoritma modifikasi usulan dapat dilihat pada Tabel 18, Tabel 19, dan Tabel 20.
Masing-masing  algoritma  menghasilkan  rute  yang berbeda.  Namun,  dapat  dilihat  bahwa  algoritma  usulan dengan  algoritma  acuan Clarke  and  Wright  Savings menghasilkan  kelompok  rute  dengan  titik-titik  yang sama. Hal ini disebabkan cara pemilihan rute modifikasi usulan diubah yang awalnya hanya  mempertimbangkan saving value antar dua titik saja menjadi titik-titik yang telah dimasukkan ke dalam rute sementara dipertimbangkan saving  value -nya  terhadap  titik  yang akan  dimasukkan  selanjutnya.  Dari  ketiga  hasil  rute tersebut,  indikator  performansi  algoritma  dibandingkan dan hasil perbandingan dapat dilihat pada Tabel 21.
Tabel 18. Hasil rute benchmark dengan algoritma Clarke and Wright savings Rute 1 Rute 2 Rute 3 Dataset benchmark Depot – 8 – 7 – 6 – 3 – 10 – Depot Depot  –  5 – 2 – 11 – 9 – Depot Depot – 13 – 4 – 1 –  12 – Depot Jarak tempuh (km) 116,7 81,6 50,1 Biaya distribusi/kendaraan/hari (Rp) 75.125,625 52.530,00 32.251,875
Tabel 19. Hasil rute benchmark dengan algoritma sequential insertion Rute 1 Rute 2 Rute 3 Dataset benchmark Depot  –  1  – 13 –  11 – 4 – 12 – Depot Depot – 9 – 10 – 3 – 2 – Depot Depot  –  5  – 8  –  7  –  6  – Depot Jarak tempuh (km) 51,4 73,9 115,7 Biaya distribusi/kendaraan/hari (Rp) 33.088,75 47.573,125 74.481,875 Tabel 20. Hasil rute usulan Rute 1 Rute 2 Rute 3 Dataset benchmark Depot – 0 – 6 – 7 – 8 – 10  –  3  – Depot Depot – 2 – 5 –  11  –  9  – Depot Depot – 12 – 4 – 13 – 1 – Depot Jarak tempuh (km) 111,4 79,7 48,7 Biaya distribusi/kendaraan/hari (Rp) 71.713,75 51.306,875 31.350,625
Tabel 21. Perbandingan indikator performansi algoritma Clarke and Wright savings , sequential insertion , dan usulan
Indikator Performansi Satuan Solusi Benchmark Clarke and Wright Savings Perbaikan Sequential Insertion Perbaikan (a) (b) (c) (d) (e)=((d)-(c))/(d) (f) (g)=((f)-(c))/(f) Total biaya Rp 154.371,25 159.907,5 3,46% 155.143,75 0,498% Jarak tempuh Km 239,8 248,4 3,46% 241 0,498%
Berdasarkan  Tabel  21,  dapat  dilihat  bahwa modifikasi  algoritma  usulan  menghasilkan  biaya  yang lebih murah dibandingkan dengan algoritma Clarke and Wright  Savings dan  algoritma Sequential  Insertion . Algoritma  usulan  dapat  menghasilkan  perbaikan  biaya distribusi  sebesar  Rp5.536,25  dan  jarak  tempuh  8,6 kilometer dengan persentase perbaikan 3,46% dibandingkan dengan algoritma acuan Clarke and Wright Savings . Algoritma usulan juga menghasilkan perbaikan biaya  distribusi  sebesar  Rp772,5  dan  jarak  tempuh  1,2 kilometer  dengan  persentase  0,498%  dibandingkan dengan algoritma Sequential Insertion .

## 4. Kesimpulan
Hasil  pengembangan  modifikasi  algoritma Clarke and Wright Savings dapat menyelesaikan permasalahan distribusi  PT  SMN  dengan  biaya  yang  lebih  murah. Pengembangan modifikasi algoritma Clarke and Wright Savings yang  mengakomodasi  kendala  waktu  dan mengubah cara pemilihan titik pelanggan dengan konsep head dan tail dapat  digunakan  dalam  penyelesaian masalah  CVRP.  Pengembangan  algoritma  usulan  juga memberikan  solusi  biaya  distribusi  yang  lebih  murah
dibandingkan  algoritma  acuan Clarke  and  Wright Savings dan Sequential Insertion.

## Daftar Pustaka
Arifudin,  A.,  Wisnubroto,  P.,  &  Parwati,  C.  I.  (2017).
Optimalisasi  vehicle  routing  problem  dengan pendekatan  metode  saving  matrix  dan  clarke  & wright saving heuristic. Jurnal REKAVASI , 5(1), 1- 9.
Clarke,  G.,  &  Wright,  J.  W.  (1964).  Scheduling  of vehicles  from  a  central  depot  to  a  number. 12(4) , 568-581.
Meilani,  D.,  &  Iswara,  A.  (2018).  Aplikasi  penentuan rute  distribusi  LPG  3  kg. Jurnal  Optimasi  Sistem Industri , 17(2), 208-219.
Montoya-Torres,  J.  R.,  Franco,  J.  L.,  Isaza,  S.  N., Jiménez,  H.  F.,  &  Herazo-Padilla,  N.  (2015).  A literature  review  on  the  vehicle  routing  problem with  multiple  depots. Computers  &  Industrial Engineering , 115-129.
Octora,  L.,  Imran,  A.,  &  Susanty,  S.  (2014). Pembentukan rute distribusi menggunakan algoritma  clarke  &  wright  savings  dan  algoritma
sequential  insertion. Jurnal  Online  Institut Teknologi Nasional, 2 . Rupiah, S., Mulyono, & Sugiharti, E. (2017). Efektivitas algoritma  clarke-wright  dan  sequential  insertion dalam  penentuan  rute  pendistribusian  tabung  gas LPG. UNNES Journal of Mathematics, 6(2) .
SM,  A.  I.,  Ekawati,  R.,  &  Febriana,  N.  (2017). Optimalisasi  rute  distribusi  air  minum  quelle dengan algoritma clarke & wright saving dan model vehicle routing problem. Prosiding SENIATI , C1-1. Toth, P., & Vigo, D. (2002). The vehicle routing problem. Philadelphia: Siam.