Email : fibonacci@umj.ac.id

## Jurnal Pendidikan Matematika dan Matematika

## OPTIMISASI RUTE PADA CVRP DALAM PENDISTRIBUSIAN GAS OKSIGEN MENGGUNAKAN ALGORITMA CLARKE AND WRIGHT SAVINGS
Fheby Moudya 1) , Niken Rarasati 2)* , Wardi Syafmen 3)
1,2) Jurusan Matematika dan Ilmu Pengetahuan Alam, Fakultas Sains dan Teknologi
3) Jurusan Pendidikan Matematika, Fakultas Keguruan dan Ilmu Pendidikan Universitas Jambi Jl. Lintas Jambi-Ma Bulian, Kode Pos 36361
*nikenrarasati@unja.ac.id

## Abstrack
In  this  distribution  process,  a  company  needs  to  maintain  trust  and  increase  the  number  of customers to survive in this industry. One way to improve this process is by delivering services by making delivery trips on demand in a timely and efficient manner. PT Rezeki Surya Gasindo is a company that focuses on producing oxygen gas in the health sector where its customers are spread  across  Jambi  City  area.  The  company  delivered  oxygen  gas  by  not  maximizing  the capacity of each vehicle moreover the route that are still used for this delivery process based on  the  driver's  experience  without  considering  the  mileage  and  travel  time.  This  will  affect delays  in  oxygen  gas  delivery.  One  of  the  VRP  types  used  for  this  problem  is  Capacitated Vehicle  Routing  Problem  (CVRP)  and  can  be  solved  with  Clarke  and  Wright  Savings Algorithm. This algorithm is used to determine the distribution route by identifying the distance and savings matrix, allocating customer locations into routes based on customer demands, and sorting customer locations that has been formed. To find the optimal distance and minimum distribution cost, the sorting will be processed using two methods, Nearest Insert and Nearest Neighbour.  The  research  results  show  there  are  7  routes  on  the  beginning,  then  after  the calculation is done, the route can be cut down to 4 routes according to the number of vehicles that the company has. Vehicle mileage can be cut down to 92.7 km or 44.08% and distribution costs can be lowered to Rp. 599,760.
Keywords : Clarke and Wright Savings Algorithm, CVRP, Distribution, Route

## Abstrak
Dalam proses pendistribusian, suatu perusahaan perlu menjaga kepercayaan serta menambah jumlah  customer  supaya  bisa  bertahan  dalam  persaingan  industri.  Salah  satu  upaya  untuk meningkatkan hal tersebut bisa dengan memberikan pelayanan dengan melakukan perjalanan pengantaran  sesuai  permintaan  dengan  tepat  waktu  dan  efisien.  PT.  Rezeki  Surya  Gasindo adalah perusahaan yang bergerak dibidang kesehatan dalam pembuatan gas oksigen dimana untuk customernya tersebar di beberapa wilayah di Kota Jambi. Permasalahan yang terjadi
Volume 9 No. 1 Bulan Juni  Tahun 2023
yaitu  perusahaan  mengirimkan  gas  oksigen  dengan  tidak  memaksimalkan  kapasitas  angkut yang dimiliki oleh tiap-tiap kendaraan ditambah lagi rute yang masih digunakan untuk proses pengantaran ini hanya berdasarkan pengalaman driver tanpa mempertimbangkan jarak yang dilewati  dan  waktu  tempuh  selama  di  perjalanan.  Hal  ini  nantinya  akan  berdampak  pada keterlambatan  pengantaran  gas  oksigen.  Salah  satu  jenis  VRP  yang  digunakan  untuk permasalahan ini yaitu Capacitated Vehicle Routing Problem (CVRP). Permasalahan CVRP pada  PT.  Rezeki  Surya  Gasindo  dapat  dirampungkan  dengan  Algoritma  Clarke  and  Wright Savings. Algoritma ini dipakai untuk menetapkan rute distribusi dengan cara mengidentifikasi matriks jarak dan mengidentifikasi matriks penghematan, mengalokasikan lokasi customer ke dalam  rute  berdasarkan  permintaan  customer  dan  kapasitas  kendaraan,  serta  mengurutkan lokasi customer dalam rute yang sudah terbentuk. Untuk menemukan jarak yang optimal dan biaya  distribusi  yang  minimum  pengurutan  akan  dilakukan  menggunakan  dua  metode  yaitu Nearest Insert dan Nearest Neighbour. Hasil penelitian memperlihatkan bahwa pada rute awal terdapat  7  rute  maka  setelah  dilakukan  perhitungan  dapat  dikurangi  menjadi  4  rute  sesuai dengan  banyak  kendaraan  yang  dimiliki  perusahaan.  Jarak  tempuh  kendaraan  dapat diperpendek sebesar 92,7 km atau 44,08% dan biaya distribusi dapat dikurangi sebesar Rp. 599.760.
Kata Kunci: Algoritma Clarke and Wright Savings, CVRP,  Distribusi, Rute.

## PENDAHULUAN
Masuk ke abad 21, di era society 5.0 dimana diartikan dengan ketatnya persaingan  di  berbagai  bidang  yang berkaitan  langsung  dengan  kebutuhan masyarakat.  Istilah  ini  adalah  bentuk pengembangan  dari  era industry 4.0, dimana  pada  era  tersebut  lebih  ditekankan pada  penggunaan  teknologi  dan  mesin untuk  membantu  berbagai  bentuk  aktivitas kehidupan manusia. Sedangkan society 5.0 lebih  berfokus  pada  bagaimana  manusia dalam  berupaya  untuk dapat hidup berdampingan dengan perkembangan
teknologi.  Bila  dicontohkan,  beberapa tahun  terakhir,  masyarakat  lebih  memilih membeli kebutuhan lewat e-commerce yang tersedia  dimana  nantinya  barang/produk yang  dibeli  bisa  diantarkan  ke  masyarakat tanpa  harus  keluar  rumah.  Kegiatan  ini merupakan salah satu bentuk pendistribusian.
Untuk  dapat  bertahan  dalam  dunia industri,  suatu  perusahaan  harus  dapat
memberikan kepuasan kepada pelanggannya dengan memberikan kemudahan  untuk  mendapatkan  produk yang mereka inginkan. Selain itu, perusahaan  harus  dapat  mempertahankan kepercayaan  dan  meningkatkan  jumlah pelanggannya. Mengirimkan barang sesuai permintaan dengan tepat waktu dan efisien adalah salah satu cara untuk meningkatkan hal  tersebut.  Permasalahan  pendistribusian sangat  penting  untuk  mencapai  puncak penjualan  dan  kepuasan  pelanggan  karena akan  berkaitan  dengan  biaya  pengiriman, yang berdampak pada total biaya produksi.
Permasalahan  untuk  penentuan  rute distribusi dari perusahaan menuju beberapa customer termasuk  ke  dalam Vehicle Routing  Problem (VRP).  Menurut  Toth  & Vigo  (2002), Vehicle  Routing  Problem (VRP)  adalah  masalah  penentuan  rute kendaraan  dalam  mendistribusikan  barang dari tempat produksi yang dinamakan depot ke customer dengan tujuan meminimumkan total  jarak  tempuh  kendaraan,  dan  dengan
Fheby  Moudya,  Niken  Rarasati,  dan  Wardi  Syafmen:  Optimisasi  Rute  Pada  Cvrp  Dalam  Pendistribusian  Gas Oksigen Menggunakan Algoritma Clarke And Wright Savings FIBONACCI : Jurnal Pendidikan Matematika dan Matematika. Vol. 9 (1), pp: 105-118
permintaan yang sudah diketahui, dari satu atau lebih depot (Yeun dkk, 2008).
Salah satu jenis VRP yang digunakan yaitu Capacitated Vehicle Routign Problem (CVRP)  bertujuan  untuk  meminimalkan jumlah  kendaraan  yang  digunakan  dan meminimalkan  total  jarak  tempuh  rute perjalanan  dalam  pendistribusian  produk dari  gudang  ke customer ,  solusi  CVRP dikatakan  layak  jika  permintaan customer pada setiap pemesanan tidak melebihi batas kapasitas kendaraan yang digunakan (Toth & Vigo, 2002).
Untuk  membantu  menyelesaikan permasalahan  CVRP  tersebut,  algoritma Clarke  and  Wright  Savings dipilih  karena metode ini dapat membantu menyelesaikan permasalahan  terkait  pendistribusian  yang bergantung pada kapasitas angkut pengiriman untuk tiap kendaraan.
Algoritma Clarke  and  Wright  Savings adalah  metode  yang  digunakan  untuk penentuan rute distribusi produk ke wilayah pemasaran  dengan  cara  menentukan  rute distribusi  yang  harus  dilalui  dan  jumlah kendaraan  yang  digunakan  berdasarkan kapasitas  angkut  dari  tiap  kendaraan  agar diperoleh rute optimal dan biaya transportasi yang minimal (Demez, 2013).
Menurut  (Suyadi,  2007),  model transportasi telah di terapkan pada berbagai macam organisasi usaha seperti pengendalian  operasi  pabrik,  penentuan daerah penjualan, dan pengalokasian pusat- pusat  distribusi  dan  gudang.  Optimisasi ( Optimization )  merupakan  kegiatan  untuk mendapatkan  hasil  yang  unggul  dibawah kondisi  yang  diberikan.  Tujuan  akhir  dari semua  bentuk  kegiatan  tersebut  adalah meminimalkan usaha ( effort ) atau
memaksimalkan  manfaat  ( benefit )  yang diinginkan (Moengin, 2011).
Menurut  Tjiptono  (2008),  disribusi dapat  diartikan  sebagai  suatu  usaha pemasaran  untuk    memperlancar  dan mempermudah  penyampaian  barang  dan jasa  dari  produsen  kepada  konsumen, sehingga  penggunaannya  sesuai  dengan yang  diperlukan  (jenis,  jumlah,  harga,  dan tempat). Dalam melakukan proses pendistribusian,  diperlukan  penyesuaian antara  waktu  pengiriman  dan  permintaan para  konsumen.  Oleh  karena  itu,  model pendistribusian  sangat  diperlukan  agar keterlambatan  dapat  diatasi  (Dinnullah, 2018).
Jadwal  pengiriman  dan  penentuan rute  yang  nantinya  akan  dilalui  oleh masing-masing  kendaraan  akan  sangat mempengaruhi  biaya  pengiriman.  Tujuan dari penentuan rute dan jadwal pengiriman adalah untuk mengoptimalkan waktu, biaya pengiriman,  dan  jarak  tempuh  yang diperlukan  oleh  perusahaan  dalam  proses pendistribusian produk (Pujawan, 2010).
Menurut  Battarra  (2007),  metode penghematan  ini  dapat  menjadwalkan kendaraan  untuk  mendistribusikan  produk dari  gudang central ke  beberapa  area customer .  Metode  ini  juga  mudah  untuk diimplementasikan ke dalam bentuk permasalahan  yang  kompleks.  Meskipun hasil  yang  diberikan  tidak  menjamin merupakan solusi optimal, tetapi metode ini merupakan  metode heuristik dimana  hasil yang  didapat  nantinya  akan  mendekati dengan solusi yang optimal.
Soenandi (2017)
melakukan penelitian  karena  ingin  mengurangi  biaya logistik  dan  transportasi  yaitu  dengan  cara
Volume 9 No. 1 Bulan Juni  Tahun 2023
mengoptimalkan  rute  pengambilan  atau pengangkutan komponen dari setiap supplier.  Penelitian  ini  menghasilkan  lima rute  optimal  yang  dapat  diusulkan  kepada perusahaan,  pengurangan  jarak  tempuh kendaraan pengangkut sebanyak 36 km/hari,  jika  dibandingkan  dengan  rute yang  berjalan  saat  ini.  Hasil  pengujian menggunakan  algoritma  ACO  diperoleh rute yang lebih cepat dibandingkan dengan metode yang diterapkan oleh perusahaan.
Permasalahan pokok dalam penelitian ini  adalah  bagaimana  rute  optimal  dalam pendistribusian  gas  oksigen  pada  PT. Rezeki  Surya  Gasindo  menggunakan Algoritma Clarke and Wright Savings ? dan biaya penghematan jarak untuk transportasi yang  digunakan  setelah  penentuan  rute optimal  pada  PT.  Rezeki  Surya  Gasindo menggunakan Algoritma Clarke and Wright Savings ?

## METODE PENELITIAN
Jenis  data  yang  digunakan  pada penelitian ini merupakan data primer yang diperoleh melalui observasi langsung di PT. Rezeki Surya Gasindo.
Adapun sumsi-asumsi yang digunakan  pada  penelitian  ini  adalah  (1) Rute  yang  dilewati  dapat  dilalui  oleh kendaraan yang digunakan oleh PT. Rezeki Surya Gasindo. (2) Kendaraan dan keadaan jalan dalam kondisi normal. (3) Rute untuk jalur pendistribusian yang dilewati diasumsikan  simetris (𝐶 𝑖𝑗 = 𝐶 𝑗𝑖 ) .  (4)  Titik lokasi pengantaran hanya ke Rumah Sakit, Apotek  dan  Bengkel.  (5)  Permintaan  dari customer sudah ditetapkan. (6) Pengiriman kepada customer terjadwal. (7) Untuk biaya transportasi  hanya  meliputi  biaya  bahan bakar.  (8)  1  liter  bahan  bakar  dapat menempuh  8  km  perjalanan.  (9)  Jenis
tabung yang di distribusikan adalah tabung gas oksigen bervolume 6𝑚 3 . (10)
Banyaknya  kendaraan  yang  beroperasi hanya  mengangkut  dan  mendistribusikan pesanan  dari customer Rumah  Sakit, Bengkel dan juga Apotek.
Sebagai gambaran permasalahan dapat dilihat pada Gambar 1 berikut :
Data yang digunakan merupakan data kualitatif  yang  didapatkan  langsung  dari perusahaan.
Langkah-langkah yang dilakukan  dalam  penelitian  ini  adalah    (1) Pengumpulan  data,  dilakukan  dengan  cara melakukan  penelitian  langsung  di  PT. Rezeki  Surya  Gasindo  terkait  informasi yang  dibutuhkan.  (2)  Penyelesaian  dengan Algoritma Clarke  and  Wright  Savings  : Langkah-langkah  menggunakan  metode tersebut adalah sebagai berikut :
(a)  Menentukan  titik  lokasi  yang  menjadi tujuan pendistribusian
0=PT. Rezeki Surya Gasindo (Depot/tempat produksi gas oksigen)
1 =Lokasi RS. DR. BRATANATA
2=Lokasi RSUD. H. ABDUL  MANAP
3=Lokasi RS. ISLAM ARAFAH
4=Lokasi RS. KAMBANG
Gambar 1. Diagram Permasalahan CVRP
Fheby  Moudya,  Niken  Rarasati,  dan  Wardi  Syafmen:  Optimisasi  Rute  Pada  Cvrp  Dalam  Pendistribusian  Gas Oksigen Menggunakan Algoritma Clarke And Wright Savings FIBONACCI : Jurnal Pendidikan Matematika dan Matematika. Vol. 9 (1), pp: 105-118
5=Lokasi bengkel Bubut Aan Jaya
6=Lokasi bengkel Rascar Variasi
7=Lokasi Apotek K24 Simpang Rimbo
8=Lokasi bengkel Toko Jaya Buana Motor
9=Lokasi Apotek K24 Kebun Handil
10=Lokasi RS. Royal Prima Jambi
11=Lokasi RS. Baiturrahim
12= Lokasi Apotek KDA Mandala Mart
13= Lokasi bengkel Las Amar Cipta
14 = Lokasi Apotek Harmoni Indo Farma
15= Lokasi bengkel Handil Motor
16= Lokasi Apotik KDA Mayang
17= Lokasi bengkel Utama Teknik
18= Lokasi Apotek KDA Jerambah Bolong
19= Lokasi Apotek Sari Asih
20= Lokasi bengkel Ginting
(b)  Mengidentifikasi  matriks  jarak,  pada tahap  ini  diperlukan  jarak  antara  tempat produksi  gas  ke  masing-masing customer dan jarak antar customer.
(c)  Mengidentifikasi  matriks  penghematan
( Saving  Matrix ),  pada  tahap  ini Saving Matrix menyajikan penghematan yang bisa direalisasikan dengan menggabungkan dua atau lebih customer dalam satu rute dan satu kendaraan.
(d)  Mengalokasikan  tujuan  ke  dalam  rute, langkah ini adalah menggabungkan dua rute dengan penghematan terbesar menjadi satu rute yang layak.
(e)  Mengurutkan  tujuan  dalam  rute  yang telah terdefinisi, menentukan urutan kunjungan menggunakan algoritma Nearest
Insert dan Nearest Neighbour .

## HASIL DAN PEMBAHASAN
PT.  Rezeki  Surya  Gasindo  saat  ini mempunyai satu pusat tempat produksi gas oksigen yang berada di Jalan Lingkar Barat 1,  Kenali  Asam  Bawah.  Lokasi customer dengan  alamat  yang  tersebar  di  wilayah Kota Jambi beserta jumlah permintaan gas oksigen  di  setiap customer berbeda  satu sama  lain.  Pada  penelitian  ini,  proses pendistribusian  gas  oksigen  dilakukan menggunakan  banyaknya  4  kendaraan dengan  kapasitas  yang  heterogen.  Adapun data  lokasi customer dan  jumlah  data pengiriman gas oksigen ke setiap customer dapat dilihat pada Tabel 1, untuk PT. Rezeki Surya Gasindo dinyatakan dengan kode 0.

## Tabel 1. Data Customer dan Banyaknya Permintaan Customer
No (kode cust) Nama customer Alamat Banyak permintaan (tabung) 1 RS. Dr. Bratanata Jl. Rd. Mattaher 82 2 RSUD. H. Abdul Manap Jl. Sk. Rd. Syahbudin 32 3 RS. Islam Arafah Jl. Mpu Gandring 38
Volume 9 No. 1 Bulan Juni  Tahun 2023
No (kode cust) Nama customer Alamat Banyak permintaan (tabung) 4 RS. Kambang Jl. Kol. Amir Hamzah 20 5 Bengkel Bubut Aan Jaya Jl. Lkr. Selatan II 11 6 Bengkel Rascar Variasi Jl. Lkr. Barat III 5 7 Apotek K24 Simpang Rimbo Jl. Kapten Pattimura 6 8 Bengkel T. Jaya Buana Motor Jl. DI. Panjaitan 8 9 Apotek K24 Kebun Handil Jl. Sumatera 9 10 RS. Royal Prima Jambi Jl. Raden Wijaya 16 11 RS. Baiturrahim Jl. Moh Yamin 10 12 Apotek KDA Mandala Mart Jl. Sultan Hasanuddin 13 13 Bengkel Las Amarta Cipta Jl. RB. Siagian 10 14 Apotek Harmoni Indo Firma Jl. Hayam Wuruk 13 15 Bengkel Handil Motor Jl. Yunus Sanis 6 16 Apotek KDA Mayang Jl. Sk. Rd. Syahbudin 6 17 Bengkel Utama Teknik Jl. Lkr Barat III 6 18 Apotek KDA Jerambah Bolong Jl. Lingkar Selatan 12 19 Apotek Sari Asih 1 Jl. Sultan Agung 8 20 Bengkel Ginting Jl. Lkr Barat III 5 Total 316 (sumber : PT. Rezeki Surya Gasindo) Berdasarkan informasi yang diberikan  oleh  PT.  Rezeki  Surya  Gasindo berikut pada Tabel 2 ditampilkan rute yang diterapkan oleh perusahaan untuk pendistribusian  dari  tempat  produksi  ke customer dan 0 sebagai tempat produksi .
Tabel 2. Rute yang diterapkan perusahaan
Rute Urutan Rute Pengiriman Total Jarak (km) A 0 − 1 − 4 − 10 − 0 35 B 0 − 2 − 14 − 18 − 0 29,1 C 0 − 3 − 11 − 0 22,3 D 0 − 5 − 12 − 19 − 0 36,7 E 0 − 7 − 16 − 20 − 0 26 F 0 − 13 − 9 − 15 − 0 30,6 G 0 − 6 − 8 − 17 − 0 30,6 Total 210,3 (sumber : PT. Rezeki Surya Gasindo) Parameter yang digunakan yaitu : 𝑖  =
titik awal; 𝑗  = titik tujuan; 𝑘 = kendaraan ke-; 𝐶 𝑖𝑗𝑘 = Jarak  dari  titik  awal 𝑖 ke  titik tujuan 𝑗 yang dilakukan oleh kendaraan ke
Gambar 2 . Rute Awal Pendistribusian
Fheby  Moudya,  Niken  Rarasati,  dan  Wardi  Syafmen:  Optimisasi  Rute  Pada  Cvrp  Dalam  Pendistribusian  Gas Oksigen Menggunakan Algoritma Clarke And Wright Savings FIBONACCI : Jurnal Pendidikan Matematika dan Matematika. Vol. 9 (1), pp: 105-118
𝑘 (km); 𝑋 𝑖𝑗𝑘 = Nilai  yang  menentukan dilakukannya perjalanan dari titik awal 𝑖 ke titik tujuan 𝑗 yang dilakukan oleh kendaraan ke 𝑘 .  (Variabel  keputusan); 𝑑 𝑖 = Banyak permintaan customer ke 𝑖 (tabung); 𝑞 𝑘 = Kapasitas  kendaraan  yang  digunakan  pada kendaraan ke 𝑘 (tabung)
Model  CVRP  adalah  salah  satu  tipe dari  VRP  dengan  masalah  batas  kapasitas kendaraan,  jarak  diasumsikan  simetris 𝐶 𝑖𝑗 = 𝐶 𝑗𝑖
Didefinisikan : Untuk setiap 𝐸  = {(𝑖, 𝑗)|𝑖, 𝑗 ∈ 𝑉, ( 𝑖 ≠ 𝑗)}. (𝑖, 𝑗) menyatakan sisi dari titik 𝑖 ke titik tujuan 𝑗 . Semua rute dimulai dari 0 dan berakhir di 0 . Himpunan kendaraan 𝑘 adalah  kumpulan  kendaraan yang  berbeda  kapasitas  angkut,  dengan 𝑞 sebagai  kapasitasnya.  Setiap  agen 𝑖 untuk setiap 𝑖 ∈ 𝑉 punya  permintaan 𝑑 𝑖 maka panjang  rute  dibatasi  oleh  kapasitas kendaraan, variabel keputusan adalah 𝑋 𝑖𝑗𝑘 :
𝑋 𝑖𝑗𝑘 = { 1, bila ditemukan perjalanan dari 𝑖 ke 𝑗 dengan kendaraan ke 𝑘 0, bila tidak ditemukan perjalanan dari 𝑖 ke 𝑗 𝑑engan kendaraan ke 𝑘
Model  matematika  CVRP  untuk pengoptimalan  rute  di  PT.  Rezeki  Surya Gasindo adalah :
𝑀𝑖𝑛  𝑍 =   ∑ ∑ ∑ 𝐶 𝑖𝑗𝑘 𝑋 𝑖𝑗𝑘 4 𝑘=1 20 𝑗=1 20 𝑖=0

## Dengan kendala
a. Setiap customer hanya  dikunjungi  tepat
sekali oleh suatu kendaraan
∑ ∑ 𝑋 𝑖𝑗𝑘 = 1,
4 𝑘=1 20 𝑗=1 ∀𝑖 = 0,1,2,3,4 … ,20
b. Permintaan pada semua customer dalam satu rute tidak melebihi kapasitas angkut kendaraan
∑ 𝑑 𝑖 ∑ ∑ 𝑋 𝑖𝑗𝑘 ≤ 𝑞 𝑘 ,              ∀𝑘 = 1,2,3,4 20 𝑗=1 20 𝑖=0 20 𝑖=1 c. Setiap rute berawal dari tempat produksi ∑ 𝑋 0𝑗𝑘 = 1,           ∀𝑘 = 1,2,3,4
20
𝑗=1
Data  kendaraan  yang  tersedia  dan yang  digunakan adalah (1) Mobil  Truk PS dengan  kapasitas  maksimal  tabung  adalah 145 tabung. (2) Mobil Truk Engkel dengan kapasitas  maksimal  tabung  adalah  85 tabung.  (3)  Mobil  L300 pick  up dengan kapasitas  maksimal  tabung  adalah  50 tabung, untuk kendaraan L300 ini perusahaan  memiliki  2  kendaraan.  Biaya transportasi  seharga  Rp.  6.800/1  liter,  dan diasumsikan  dapat  menempuh  8  km perjalanan.
Pada  bagian  pengolahan  data  untuk matriks  jarak,  data  diperoleh  dari  pihak perusahaan  lalu  dihitung  besarnya  jarak yang  dilalui  dari  tempat  produksi  ke customer serta  jarak  antar customer diperoleh  dengan  bantuan  aplikasi Google Maps yang  dinyatakan  dalam  satuan kilometer  (km).  Hasil  data  dapat  dilihat pada Tabel 3 :
Volume 9 No. 1 Bulan Juni  Tahun 2023
Tabel 3 . Data Matriks Jarak
0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 0 0 0 1 1 3 0 2 3, 5 9 0 3 1 1 3 7 0
4 7 6 3, 6 3 0 5 1 3 8, 7 1 1 1 0 1 1 0 6 5, 8 1 2 6, 7 8, 7 6, 5 1 6 0 7 7, 3 1 0 6, 5 8 6 1 5 1, 9 0 8 9, 6 3, 3 6, 5 3, 3 4, 4 6, 7 9, 6 9 0 9 9 4 6, 9 3, 9 4, 6 6, 6 9, 9 8, 8 0, 6 0 1 0 9, 4 6, 7 7, 2 7, 1 6, 6 4, 2 1 2 1 1 3, 3 3, 2 0 1 1 1 0 3, 8 6 1, 3 2, 9 9, 4 9, 1 7, 9 2, 7 3, 3 6, 5 0 1 2 1 6 8, 6 1 4 1 0 1 1 5 1 6 1 5 6, 8 6, 7 7, 5 9, 2 0 1 3 1 4 7 1 2 8, 8 9, 7 5, 2 1 5 1 3 5, 6 5, 5 5, 5 8 3, 2 0 1 4 1 2 2 7, 9 4, 2 5, 9 7, 4 1 1 1 0 2 2, 6 5, 3 3, 7 7, 3 5, 8 0 1 5 9, 9 4, 6 7, 7 4, 6 5, 6 5, 4 1 1 9, 8 1, 3 1, 2 2 4 6, 8 4, 9 3, 3 0 1 6 3, 8 9 0, 4 6 3, 2 1 0 6, 5 6, 1 6 6, 5 7, 1 5, 6 1 4 1 2 7, 5 7, 3 0 1 7 4, 2 1, 3 5, 3 9, 9 7, 7 1 5 1, 7 3, 1 1 1 1 1 1 2 1 0 1 7 1 6 1 2 1 2 4, 9 0 1 8 1 2 7 8, 4 8, 6 9, 1 2, 4 1 4 1 3 5 5 1, 8 8 7, 4 3 5, 7 3, 8 8 1 3 0 1 9 9, 1 2, 5 5, 7 0, 6 2, 7 9, 9 9 7, 7 3, 2 3, 9 7 1, 3 9, 6 8, 4 4, 2 4, 5 5 1 0 8, 6 0 2 0 5, 9 1 4 7, 1 1 1 8, 5 1 8 2 3, 8 1 1 1 2 1 4 1 1 1 8 1 7 1 3 1 3 6, 7 1, 8 1 5 1 1 0
(sumber : PT. Rezeki Surya Gasindo)
Fheby  Moudya,  Niken  Rarasati,  dan  Wardi  Syafmen:  Optimisasi  Rute  Pada  Cvrp  Dalam  Pendistribusian  Gas Oksigen Menggunakan Algoritma Clarke And Wright Savings FIBONACCI : Jurnal Pendidikan Matematika dan Matematika. Vol. 9 (1), pp: 105-118

## Pada pencarian penghematan menggunakan
rumus :
𝑆(𝑖, 𝑗) = 𝐽(𝐺, 𝑖) + 𝐽(𝑗, 𝐺) − 𝐽(𝑖, 𝑗) Dimana :
𝑆(𝑖, 𝑗) = penghematan jarak customer 𝑖 dan customer 𝑗
𝐽(𝐺, 𝑖) = jarak  antara  tempat  produksi  ke customer 𝑖
𝐽(𝑗, 𝐺) = jarak antara customer 𝑗 ke tempat produksi
𝐽(𝑖, 𝑗) = jarak  antara customer 𝑖 ke customer 𝑗
Dengan :
𝐺          = kode tempat produksi = 0
Perhitungan matriks penghematan akan dicontohkan pada beberapa titik:
1. Perhitungan matriks penghematan
customer 2 dan 1
𝑆(2,1) = 𝐽(0,2) + 𝐽(1,0) − 𝐽(2,1)
= 3,5 + 13 − 9
= 7,5
2. Perhitungan matriks penghematan
customer 3 dan 1
𝑆(3,1) = 𝐽(0,3) + 𝐽(1,0) − 𝐽(3,1)
= 11 + 13 − 3 = 21
3. Perhitungan matriks penghematan customer 3 dan 2
𝑆(3,2) = 𝐽(0,3) + 𝐽(2,0) − 𝐽(3,2)
= 11 + 3,5 − 7
= 7,5
4. Perhitungan matriks penghematan customer 4 dan 1
𝑆(4,1) = 𝐽(0,4) + 𝐽(1,0) − 𝐽(4,1)
= 7 + 13 − 6
= 14
5. Perhitungan matriks penghematan customer 4 dan 2
𝑆(4,2) = 𝐽(0,4) + 𝐽(2,0) − 𝐽(4,2)
= 7 + 3,5 − 3,6
= 6,9
6. Perhitungan matriks penghematan customer 4 dan 3
𝑆(4,3) = 𝐽(0,4) + 𝐽(3,0) − 𝐽(4,3)
= 7 + 11 − 3
= 15
Lakukan cara yang sama untuk semua titik yang belum dikunjungi. Setelah dicari menggunakan  rumus  penghematan  diatas langkah selanjutnya mengalokasikan lokasi customer ke dalam rute. Pada asumsi awal terdapat  7  rute  yang  berbeda,  dengan  ini akan dialokasikan customer-customer yang bisa  digabungkan  sampai  batas  kapasitas kendaraan yang ada. Penggabungan customer-customer dilakukan  dari  nilai
Volume 9 No. 1 Bulan Juni  Tahun 2023
penghematan  paling  besar  hingga  yang paling kecil dengan tujuan memaksimumkan  penghematan.  Sehingga didapatlah rute pendistribusian seperti yang ditunjukkan pada Tabel 4. Tabel 4. Rute Pendistribusian Rute Kendaraan Kode Customer Permintaan (tabung) Jumlah Permintaan (tabung) A 12 13 141 13 10
5 11 1 82 14 13 18 12
B 3 38 80 11 10 8
8 10 16
19
8 𝐂 𝟏 15 6 46 9 9 17
6 4 20 6 5 𝐂 𝟐 7 6 49
20
5 16
6 2 32
Pada  pencarian  urutan  rutenya menggunakan  metode Nearest  Neighbour, seperti yang terlihat di Tabel 5.
Tabel 5. Pengurutan menggunakan metode Nearest Neighbour
Rute Urutan Rute Pengiriman Total Jarak (km) A 0 − 18 − 5 − 12 − 13 − 14 − 1 − 0 43,4 B 0 − 19 − 3 − 11 − 8 − 10 − 0 26,4 Rute Urutan Rute Pengiriman Total Jarak (km) 𝑪 𝟏 0 − 17 − 6 − 4 − 9 − 15 − 0 28,1
𝑪 𝟐 0 − 2 − 16 − 7 − 20 − 0 19,7 Total 117,6
Bila dibandingkan berdasarkan Tabel 2  dan  Tabel  5,  terlihat  bahwa  terdapat penghematan  jarak.  Besar  penghematan jarak adalah :
Fheby  Moudya,  Niken  Rarasati,  dan  Wardi  Syafmen:  Optimisasi  Rute  Pada  Cvrp  Dalam  Pendistribusian  Gas Oksigen Menggunakan Algoritma Clarke And Wright Savings FIBONACCI : Jurnal Pendidikan Matematika dan Matematika. Vol. 9 (1), pp: 105-118

## Penghematan jarak

## =
𝑇𝑜𝑡𝑎𝑙 𝐽𝑎𝑟𝑎𝑘 𝑅𝑢𝑡𝑒 𝐴𝑤𝑎𝑙−𝑇𝑜𝑡𝑎𝑙 𝐽𝑎𝑟𝑎𝑘 𝑅𝑢𝑡𝑒 𝑇𝑒𝑟𝑝𝑖𝑙𝑖ℎ 𝑇𝑜𝑡𝑎𝑙 𝐽𝑎𝑟𝑎𝑘 𝑅𝑢𝑡𝑒 𝐴𝑤𝑎𝑙
× 100 % = 210,3 km−117,6 km
210,3 km
× 100 %
= 44,08 %
Berikut  ditunjukkan  pada  peta  rute final yang telah dihasilkan.
Gambar 3 . Rute Final
Pada perhitungan total biaya distribusi  sebelum  penggunaan  Algoritma Clarke  and  Wright  Savings untuk  rute  A dapat diketahui sebagai berikut :
1. Bahan bakar yang dibutuhkan
= 𝑗𝑎𝑟𝑎𝑘 𝑡𝑒𝑚𝑝𝑢ℎ 8 𝑘𝑚/𝑙 = 35 𝑘𝑚 8 𝑘𝑚/𝑙 = 4,38 liter

## 2. Biaya bahan bakar
= bahan bakar yang dibutuhkan
× Rp. 6.800
= 4,38 𝑙𝑖𝑡𝑒𝑟 × Rp. 6.800
= Rp. 29.784
3. Biaya distribusi = biaya bahan bakar
4. Biaya distribusi 1 minggu (6 hari)
= biaya bahan bakar × 6
= Rp. 29.784  × 6
= Rp. 178.704
Perusahaan memiliki empat kendaraan  dengan  tiga  jenis  kendaraan berkapasitas berbeda  kecuali kendaraan ke 3  dan  ke  4  berkapasitas  sama,  sehingga untuk memudahkan pencarian jumlah biaya distribusi  maka,  untuk  mencari  total  biaya distribusi akan dijumlahkan biaya distribusi 1 minggu/kendaraan.
Perhitungan  total  biaya  distribusi setelah  penggunaan  Algoritma Clarke  and Wright  Savings untuk  rute  A  dapat diketahui sebagai berikut :
5. Bahan bakar yang dibutuhkan
= 𝑗𝑎𝑟𝑎𝑘 𝑡𝑒𝑚𝑝𝑢ℎ 8 𝑘𝑚/𝑙 = 43,4 𝑘𝑚 8 𝑘𝑚/𝑙 = 5,43 liter

## 6. Biaya bahan bakar
= bahan bakar yang dibutuhkan ×
Rp. 6.800
= 5,43 𝑙𝑖𝑡𝑒𝑟 × Rp. 6.800
= Rp. 36.924
7. Biaya distribusi = biaya bahan bakar
8. Biaya distribusi 1 minggu (6 hari)
= biaya bahan bakar × 6
= Rp. 36.924 × 6 = Rp. 221.544
9. Jumlah biaya distribusi/kendaraan
Volume 9 No. 1 Bulan Juni  Tahun 2023

## = biaya distribusi 1 minggu (6 hari)
Perusahaan memiliki
empat kendaraan  dengan  tiga  jenis  kendaraan berkapasitas berbeda kecuali kendaraan ke 3  dan  ke  4  berkapasitas  sama,  sehingga untuk memudahkan pencarian jumlah biaya distribusi  maka,  untuk  mencari  total  biaya distribusi akan dijumlahkan biaya distribusi 1  minggu/kendaraan.  Karena  rute  yang didapat  adalah  4  rute  dan  sesuai  dengan banyaknya  kendaraan  yang  dimiliki  oleh perusahaan maka jumlah
biaya distribusi/kendaraan  =  biaya  distribusi  1 minggu (6 hari).

## SIMPULAN
Simpulan  yang  dapat  diambil  dari hasil  olah  data  dengan  Algoritma Clarke and Wright Savings yaitu telah didapat rute yang  optimal  untuk  pendistribusian  gas oksigen  sebanyak  4  rute,  hal  ini  sesuai dengan jumlah kendaraan yang dimiliki dan digunakan oleh perusahaan dalam melakukan proses pendistribusian.
Kesimpulan kedua yaitu untuk jumlah biaya  distribusi  yang  diperoleh  setelah menggunakan Algoritma Clarke and Wright Savings yaitu sebesar Rp. 559.760 , menghasilkan  penghematan  dari  biaya sebelum  penggunaan  algoritma  ini  yaitu sebesar Rp. 473.688 .

## UCAPAN TERIMA KASIH
Peneliti sangat berterimakasih kepada PT.  Rezeki  Surya  Gasindo  beserta  seluruh karyawan  dan  staff  yang  bertugas  yang telah  memberikan  izin  kepada  peneliti untuk  melakukan  penelitian  di  perusahaan tersebut.

## DAFTAR PUSTAKA
Battara, M., G, Edorgan dan D, Vigo. 2007.
Exact  Algorithms  for  the  Clustered Vehicle  Routing  Problem .  Operation Research
Demez, H. 2013. Combinatorial
Optimization  :  Solution  Methods  of Travelling Salesman Problem. Thesis tidak diterbitkan. Eastern Mediterranean University.
Dinnullah,  R.  2018.  Skema  Pengiriman
Susu  dengan  Menggunakan  Graf. FIBONACCI: Jurnal Pendidikan Matematika  dan  Matematika .  Vol
4(2).
Moengin,  P.  2011. Metode  Optimisasi . Muara Indah Prawirosetono, Bandung.
Pujawan,  I,  Nyoman  dan  Mahendrawathi.
2010. Supply  Chain  Management. Edisi Kedua. Surabaya : Guna Widya.
Soenandi,  I,  A.,  Joice  dan  Marpaung,  B. 2019.  Optimasi  Capacitated  Vehicle Routing Problem with Time
Windows  dengan  Menggunakan  Ant Colony  Optimization. Jurnal  Sistem dan Manajemen Indsutri. Vol 3(1).
Suyadi,  P.  2007. Manajemen  Operasi . Jakarta : Bumi Aksara,
Tjiptono,  F.  2008. Strategi  Pemasaran.
Edisi 3. Yogyakarta : Andi.
Toth dan Vigo. 2002. The Vehicle Routing
Problem. SIAM  Monographs  on
Discrete
Mathematics and Application, Philadelphia.
Fheby  Moudya,  Niken  Rarasati,  dan  Wardi  Syafmen:  Optimisasi  Rute  Pada  Cvrp  Dalam  Pendistribusian  Gas Oksigen Menggunakan Algoritma Clarke And Wright Savings FIBONACCI : Jurnal Pendidikan Matematika dan Matematika. Vol. 9 (1), pp: 105-118
Yeun, L.C.,  Ismail, W. A N. R., Omar, K. dan Zirour, M. 2008. Vehicle Routing Problem:Models and Solutions.
Journal of Quality Measurement and Analysis, 4 (1).
Volume 9 No. 1 Bulan Juni  Tahun 2023