## JURNAL ILMIAH TEKNIK INDUSTRI
ISSN: 1412-6869   e-ISSN: 2480-4038 journal homepage: http://journals.ums.ac.id/index.php/jiti/index doi: 10.23917/jiti.v16i1.3846

## Penyelesaian CCVRPTW Menggunakan Biased Random Key Genetic Algorithm-Populasi Degradasi
Listy Avri Christiana 1 , Hari Prasetyo 1*
Abstract.    The  article  presents  the  Biased  Random  Key  Genetic  Algorithm-Population  Degradation (BRKGA-PD) design for completing Capacitated Closed Vehicle Routing Problem with Time Windows (CCVRPTW)  on  soft  drink  distributions  that  have  been  studied  by  Sembiring  (2008).  The  goal  is  to determine  some closed routes in meeting consumer demand  with time limits and limit the capacity of vehicles used, so the total cost of distribution is minimal. The proposed algorithm adopts the extinction of  population size.  BRKGA-PD is coded using  Matlab  programming  with  the best  parameter  setting. The resulting solution is a subrute with a minimum of distribution fee. This algorithm is compared with two  other  methods,  namely  BRKGA  general  and  heuristic  methods.  The  results  of  this  study  can  be concluded  that  the  BRKGA-PD  method  is  able  to  improve  the  general  BRKGA  because  with  a  time difference that is not significant can provide cost savings of Rp. 6.857,- and BRKGA-PD is better than heuristic method because it can save more cost Rp. 87.000,-.
Keywords. BRKGA, CCVRPTW, population degradation, minimum cost.
Abstrak.  Artikel menyajikan rancangan Biased Random Key  Genetic  Algorithm-Populasi  Degradasi (BRKGA-PD) untuk menyelesaikan Capacitated Closed Vehicle Routing Problem  with Time Windows (CCVRPTW)  pada  pendistribusian  soft  drink yang  telah  diteliti  oleh  Sembiring  (2008).  Tujuannya adalah  menentukan  beberapa  rute  tertutup  dalam  memenuhi  permintaan  konsumen  dengan  batasan waktu  dan  batasan  kapasitas  kendaraan  yang  digunakan,  sehingga  total  biaya  pendistribusian minimal.  Algoritma  yang  diusulkan  mengadopsi  kepunahan  ukuran  populasi.  BRKGA-PD  dikodekan menggunakan pemrograman Matlab dengan setting parameter terbaik. Solusi yang dihasilkan berupa subrute dengan minimum biaya pendistribusian. Algoritma ini dibandingkan dengan dua metode lain, yaitu  BRKGA  umum  dan  metode  heuristik.  Hasil  penelitian  ini  dapat  disimpulkan  bahwa  metode BRKGA-PD  mampu  memperbaiki  BRKGA  umum  karena  dengan  perbedaan  waktu  yang  tidak signifikan  mampu  memberikan  penghematan  biaya  Rp.  6.857,-  dan  BRKGA-PD  lebih  baik dibandingkan dengan metode heuristik karena dapat lebih menghemat biaya Rp. 87.000,-.
Kata Kunci. BRKGA, CCVRPTW, populasi degradasi, biaya minimum.

## I. P ENDAHULUAN
1
Vehicle  routing  problem (VRP)  menjadi permasalahan optimasi yang  terdiri  cara menentukan rute pendistribusian yang efektif dan efisien. Proses pendistribusian umumnya melibatkan depot tunggal untuk melayani sejumlah outlet atau konsumen yang tersebar
1
1 Jurusan Teknik Industri, Fakultas Teknik, Universitas Muhammadiyah Surakarta, Jalan Ahmad Yani, Pabelan – Sukoharjo (57162)
* email: hari.prasetyo@ums.ac.id
Diajukan: 02-02-2017 Diperbaiki: 09-04-2017 Disetujui: 30-05-2017
pada PRV. Tujuannya adalah menentukan urutan pengiriman (rute) agar semua permintaan konsumen dapat terpenuhi dan total jarak yang ditempuh oleh kendaraan tersebut minimal sehingga biayanya minimal. Permasalahan VRP banyak dijumpai di berbagai hal misalnya pendistribusian produk, pengangkutan sampah, pengantaran koran, dan sebagainya. Tidak semua perusahaan dalam pendistribusian produk, pengangkutan sampah, dan pengantaran koran menggunakan jenis kendaraan yang sama misalnya truk, motor, kapal bahkan pesawat terbang. Selain jenis kendaraan ( vehicle ), tentunya terdapat berbagai hal lain yang menjadi konstrain seperti biaya
perjalanan, jangka waktu, dan sebagainya sehingga perlu untuk  dipertimbangkan dalam penentuan rutenya (Hendrawan, 2007). Hal ini menunjukkan bahwa VRP merupakan masalah yang sangat penting untuk diselesaikan.
Pendistribusian yang dilakukan menggunakan kendaraan milik perusahaan sendiri yang mengharuskan pendistribusian berawal dan berakhir di depot dinamakan rutenya bersifat tertutup yang disebut dengan close  vehicle  routing  problem (CVRP). Beberapa kasus VRP pada penyelesaiannya perlu mempertimbangkan kapasitas yang menjadi kendala dimana proses pendistribusiannya setiap kendaraan yang mengangkut produk tidak boleh melampaui batas dari kapasitas kendaraan yang digunakan untuk mengirimkan produknya ke beberapa outlet (Toth  &  Vigo, 2002).  VRP variasi ini dinamakan dengan capacitated vehicle  routing  problem (CVRP).  Contoh implementasi CVRP seperti yang terdapat pada pengiriman pupuk urea bersubsidi di daerah Sumenep yang telah diselesaikan menggunakan bantuan software LINGO versi 11.0  dengan tipe penyelesaian Branch and bound (Awansari & Abusini, 2013). Penelitian tersebut dengan algoritma branch and  bound membutuhkan waktu yang panjang untuk menyelesaikannya,  sehingga kurang baik jika direkomendasikan apalagi untuk jumlah outlet konsumen yang semakin banyak.  Penelitian lain telah dilakukan Baskoro (2011)  yaitu  menyelesaiakan CVRP dengan algoritma tabu search di salah satu distributor LPG.
Penyelesaian kasus VRP selain adanya kendala kapasitas terdapat pula kendala yang mengharuskan setiap konsumen dilayani oleh kendaraan dalam time frame tertentu. Time frame merupakan batasan waktu yang diberikan perusahaan ataupun  konsumen, sehingga kendaraan tidak boleh melampui kendala waktu yang ditentukan  dalam pendistribusian. VRP variasi ini disebut dengan vehicle  routing  problem with  time
windows (VRPTW).  Penelitian berkaitan dengan VRPTW seperti terdapat pada pendistribusian beras bersubsidi yang diselesaikan dengan Algoritma Genetika (Putri, dkk., 2014). Penelitian juga pernah dilakukan oleh Sundarningsih, dkk. (2015) bahwa algoritma genetika dapat diterapkan dalam pencarian rute optimal pada pendistribusian air minum dengan kendala time windows .  Pada penelitian tersebut algoritma yang diterapkan sudah cukup baik, namun implementasinya dirasa kurang karna jumlah pelanggan yang sedikit dan data konsumen kurang bervariasi.
Pengimplementasian VRP lainnya terdapat variasi lain yang dinamakan capacitated closed  vehicle  routing  problem with time windows (CCVRPTW). Salah satunya terdapat pada pendistribusian sayuran dataran tinggi yang bertujuan untuk menentukan rute kendaraan optimal dalam mendistribusikan sayuran kepada konsumen yang tersebar secara  geografis dengan keberangkatan dan kembali pada pusat fasilitas  (Slamet,  dkk., 2014). Pada pendistribusian ini seharusnya perlu memperhatikan faktor kemacetan dan sayuran sampai ke konsumen dengan tepat waktu agar kualitas sayuran tetap terjaga.
VRP merupakan sebuah permasalahan non-deterministic polynomial-time hard (NP- Hard ) yang berarti masalah pemrograman integer dengan ukuran dari solusi komputasi yang dihasilkan mengalami peningkatan secara penuh ketika jumlah dari node meningkat (Garey &  Johnson, 1979). Node tersebut merepresentasikan konsumen atau outlet . Permasalahan VRP ini akan semakin sulit diselesaikan ketika ruang lingkup dari masalah tersebut semakin kompleks.
Permasalahan VRP tidak dapat diselesaikan dengan metode analitik, dikarenakan metode ini akan sulit untuk diturunkan/ dideferensialkan. Selain itu pemilihan metode eksak seperti branch and bound serta branch and cut dapat menghasilkan solusi yang mendekati optimal akan tetapi dibutuhkan waktu yang lama
Christiana & Prasetyo / Penyelesaiaan CCVRPTW Menggunakan Biased .... JITI, Vol.16 (1), Juni 2017, 28 – 39
untuk menyelesaikan permasalahan VRP (Asteria, 2008). Sementara itu, metode heuristik memberikan suatu cara untuk menyelesaikan permasalahan VRP dengan waktu penyelesaiannya yang lebih cepat dibandingkan dengan solusi eksak namun solusinya tidak optimal (Hendrawan, 2007). Contoh dari metode heuristik antara lain saving  based dan matching  based (Ballou  & Agarwal, 1998). Hal tersebut tentunya dalam pemilihan solusi (metode atau algoritma) yang tepat untuk memecahkan permasalahan VRP harus mempertimbangkan kualitas dari solusi yang dihasilkan (Goncalves & Resende, 2011). Maka dari itu untuk menyelesaikan permasalahan NP - Hard seperti CCVRPTW, peneliti cenderung menggunakan metode metaheuristik untuk mendapatkan solusi yang mendekati optimal dengan waktu yang relatif cepat (Grasas, dkk., 2014).
Pada  penelitian ini akan dirancang biased random  key genetic  algorithm (BRKGA) yang efisien dengan perlakuan modifikasi populasi degradasi untuk menyelesaikan capacitated closed vehicle  routing  problem with  time windows (CCVRPTW) pada pendistribusian soft drink yang telah diteliti oleh Sembiring (2008).    Adapun tujuan dalam penelitian ini yaitu membuat model terkait dengan CCVRPTW, merancang BRKGA yang efisien dengan perlakuan modifikasi populasi terdegradasi menggunakan bahasa pemrograman Matlab , mengevaluasi hasil performansi dari pengaplikasian biased  random  key  genetic algorithm (BRKGA) dengan perlakuan modifikasi populasi degradasi untuk menyelesaikan studi kasus tugas akhir Sembiring (2008) dan membandingkan dengan metode heuristik.

## II. M ETODOLOGI
Pendistribusian soft drink merupakan salah satu permasalahan CCVRPTW  yang telah diselesaikan oleh Sembiring (2008) dalam
tugas akhirnya menggunakan metode heuristik. Berbeda dengan VRP pada umumnya, pendistribusian soft drink ini setiap kendaraan yang mengangkut permintaan konsumen memiliki batasan kapasitas  dalam satuan jumlah krat yang tidak boleh dilampaui pada proses pendistribusiannya. Selain itu terdapat batasan waktu dalam melayani konsumen yang merupakan batas jam kerja perusahaan. Konsumen terdiri dari 45 outlet meliputi kantin (lembaga pendidikasn & usaha), koperasi, minimarket, swalayan dan rumah makan di sekitar Kota Medan. Proses pendistribusian soft drink ini menggunakan kendaraan milik perusahaan sendiri yang mengharuskan pendistribusian dilakukan berawal dan berakhir di depot sehingga rutenya bersifat tertutup  ( closed ).  Jadi permasalahannya bertujuan untuk menentukan beberapa rute tertutup dalam memenuhi permintaan konsumen dengan batasan waktu dan batasan kapasitas kendaraan yang digunakan sehingga  total biaya pendistribusian tersebut minimal.
Kasus  CCVRPTW  ini secara matematis dapat dimodelkan ke dalam permasalahan optimasi seperti berikut:
Fungsi tujuan: Meminimalkan biaya pendistribusian Min 𝑍𝑍 = ∑ ∑ �𝐶𝐶 𝑖𝑖𝑖𝑖 ∑ 𝑋𝑋 𝑖𝑖𝑖𝑖𝑖𝑖 𝑖𝑖 𝑖𝑖=1 � 𝑁𝑁 𝐽𝐽=0 𝑁𝑁 𝑖𝑖=0 .... (1)
X ijk : apakah kendaraan k melewati rute ij
C ij : ongkos untuk melewati rute ij N : jumlah outlet k : jumlah kendaraan
Fungsi Kendala:
Kendala kapasitas kendaraan ∑ �𝑑𝑑 𝑖𝑖 ∑ 𝑋𝑋 𝑖𝑖𝑖𝑖𝑖𝑖 𝑁𝑁 𝑖𝑖=0 � ≤ 𝑊𝑊 𝑖𝑖 𝑁𝑁 𝑖𝑖=1 .... (2)
d i : permintaan konsumen di titik i Kendala waktu Pada kasus CCVRPTW dalam penyelesaiannya  diperlukan input data-data sebagai berikut:
1. Lokasi masing-masing outlet yang akan dilayani berupa jarak yang diperoleh dari aplikasi Google maps .
2. Permintaan rata-rata mingguan konsumen untuk setiap outlet -nya.
3. Waktu perjalanan antara setiap outlet ke depot dan waktu antar outlet .
4. Kapasitas kendaraan yang digunakan yaitu 130 krat.
5. Batasan waktu pendistribusian yaitu 8 jam kerja.
Pada penelitian ini didasari beberapa asumsi untuk menyelesaikan permasalahan CCVRPTW pendistribusian soft drink :
1. Permintaan konsumen telah diketahui sebelumya (konstan).
2. Model transportasi yang digunakan adalah model transportasi tunggal artinya terdapat satu jenis kendaraan yang sama.
3. Waktu setup kendaraan 15 menit.
4. Waktu berhenti rata-rata di setiap outlet dinamakan waktu pelayanan yaitu 19 menit yang  mencakup penempatan  atau parkir kendaraan, proses menurunkan krat permintaan dan mengambil krat yang kosong untuk dimuat kembali ke dalam kendaraan.
Pemilihan  metode solusi atau algoritma untuk menyelesaikan masalah optimasi seperti CCVRPTW ini perlu mempertimbangkan kualitas solusi yang dihasilkan.  Algoritma atau metode solusi yang dirancang untuk menyelesaikan CCVRPTW pada pendistribusian softdrink menggunakan metode metaheuristik yang didasarkan pada Genetic Algorithm (GA). GA merupakan algoritma yang efektif dan mudah dilakukan untuk menyelesaikan permasalahan optimasi kombinatorial dengan teknik pencarian dan teknik optimasi yang berdasarkan pada evolusi alam (Grasas, dkk., 2014). Algoritma ini memberikan solusi optimal atau mendekati optimal dalam menyelesaikan permasalahan optimasi kombinatorial. Setiap solusinya diperoleh
dari decoding kromosom masing-masing individu. Kromosom terkait fitness  value berkorelasi dengan fungsi tujuannya. Value fitness ini mampu mengukur kualitas solusi yang dihasilkan.  Kromosom setiap individu diwakili oleh n random keys (gen).    GA dengan adanya random keys dapat  disebut Random Key Genetic Algorithm (RKGA) yang  pertama  kalinya  diperkenalkan  oleh Bean (1994)  untuk memecahkan masalah sequencing .    Goncalves  dan  Resende  (2011) menyebutkan  bahwa  salah  satu  varian  dari RKGA  adalah Biased Random Key Genetic Algorithm
(BRKGA) yang mampu
memberikan  flexibilitas dan kinerjanya dimana  dalam penyelesaiannya dilakukan pengkodean dari setiap jenis permasalahannya.
Pada BRKGA terdapat populasi awal yang terdiri dari p individu yaitu p random - keys vectors . Random-keys terdiri dari bilangan riil  secara acak dengan interval antara 0 –  1. Populasi merupakan sekumpulan solusi dari permasalahan yang akan diselesaikan dimana terdiri dari sekumpulan individu dan setiap individu (kromosom) didalamnya terdapat gen yang berisi bilangan acak tersebut. Proses ini dalam BRKGA dinamakan pembentukan populasi atau inisialisai populasi.  Kromosom yang terbentuk dengan menerapkan metode sorting dilakukan penyortiran terhadap bilangan acak di dalamnya untuk diurutkan dari yang terkecil hingga terbesar.  Bilangan acak di dalam gen tersebut lalu diterjemahkan ke dalam solusi setiap jenis permasalahannya.  Pada penelitian ini untuk menyelesaikan permasalahan CCVRPTW pendistribusian soft drink ,  dengan menerapkan algoritma ini bilangan acak di dalam gen yang merepresentasikan  dari outlet yang harus dilayani. Gambar 1 menunjukkan contoh sebuah kromosom  yang terdiri dari 10 gen untuk mengilustrasikan dari perjelasan di atas.
BRKGA pada umumnya, ukuran populasi dibuat sama dalam artian konstan hingga generasi terakhir. Pada penelitian ini menerapkan mekanisme yang berbeda dalam memecahkan permasalahan CCVRPTW pendistribusian soft drink . Peneliti bukannya menjaga ukuran populasi  konstan tetapi mengadopsi kepunahan populasi (populasi degradasi).  Penyelesainnya menggunakan ukuran populasi yang besar untuk awalnya, kemudian berkurang dalam setiap n siklus selama dalam iterasi hingga mencapai titik
minimum ukuran populasi yang ditentukan. Pengurangan ukuran populasi menyebabkan konsentrasi yang terbaik dalam pencarian solusi baru. Mekanisme penurunan ukuran populasi dapat dilihat pada Gambar 2.
Seperti yang digambarkan diatas menunjukkan mekanisme populasi degradasi yang dicontohkan terdapat suatu populasi dengan ukuran populasi awal 20 diwakili oleh kromosom. Ukuran populasi akan mengalami penurunan setiap 2 siklus selama iterasi yang ditentukan misalnya 30 iterasi.
0.08 0.11 0.21 0.32 0.39 0.42 0.55 0.59 0.81 4 6 9 1 7 10 8 2 5
Decoding 0.32 0.59 0.42 0.11 0.08 0.81 0.39 0.55 0.85 Sort Kromosom 0.21
0.85 3 Gambar 1. Ilustrasi inisialisasi populasi siklus Ukuran populasi awal kromosom siklus Ukuran populasi (iterasi ke-n) kromosom Ukuran populasi kromosom
Gambar 2. Mekanisme perubahan ukuran populasi (populasi degradasi)
Pada 2 siklus pertama ukuran populasi mengalami penurunan menjadi 18 kromosom karena degradasi populasi yang ditentukan adalah 2 kromosom sehingga berkurang 2 kromosom. Begitu seterusnya siklus ini berkelanjutan hingga ukuran populasi akan menurun mencapai ukuran populasi minimum yang ditentukan. Ukuran populasi minimum pada gambar tersebut 4 kromosom yang merupakan ukuran populasi akhir untuk mencari solusinya. Berhentinya kondisi ini merupakan telah tercapainya nilai yang diinginkan dalam menghasilkan generasi.
Pada BRKGA-PD prosesnya populasi dikategorikan  menjadi dua kelompok yaitu kelompok individu ELIT dengan pe individu terbaik (sekitar 10%  –  20%) dan kelompok individu NON-ELITE dengan p – pe individu tersisa (dengan pe < p –  pe ). Populasi tersebut selanjutnya berevolusi untuk mendapatkan generasi berikutnya seperti terlihat dalam Gambar 3.
Pada gambar di atas  kelompok ELIT dan NON-ELITE diperoleh setelah semua individu diurutkan berdasarkan fitness kemudian disesuaikan penempatannya. Nilai fitness masing-masing individu dihasilkan dari pengkodean. Kelompok ELIT yang merupakan individu terbaik pada generasi k disalin seluruhnya untuk menjadi generasi
berikutnya k+1 ke bagian TOP (bagian kanan pada Gambar 3.). Sejumlah pm individu (mutasi) dihasilkan  dengan cara yang sama secara acak seperti individu dari populasi awal ditempatkan di BOT (bagian kanan bawah pada Gambar 3). Proses selanjutnya untuk melengkapi generasi k+1 dilakukan dengan menyilangkan/menggabungkan individu dari kelompok ELIT dan NON- ELIT yang disebut dengan crossover untuk memperoleh generasi berikutnya seperti yang terlihat di Gambar 4. Crossover ini merupakan proses yang mensimulasikan proses reproduksi antara dua individu (kromosom) untuk menghasilkan individu baru yang disebut offspring .  Pada crossover , probabilitas individu ELIT yang dipilih secara acak (1/ pe ) lebih besar dibandingkan dengan individu NON-ELIT (1/( p – pe )). Hal tersebut dimaksudkan agar generasi berikutnya memiliki kemungkinan yang lebih tinggi untuk memiliki karakteristik yang sama dengan individu ELIT. Seorang peneliti yang berasal dari Inggris menyatakan bahwa individu-individu yang memiliki karakteristik bagus (individu ELIT) akan mempunyai kemungkinan untuk bertahan hidup lebih besar sehingga mampu bereproduksi dan menurunkan karakteristik yang sama kepada keturunannya. Sebaliknya individu-individu
ELITE NON- ELITE TOP BOT Most fit Least fit Copy best solutions X Crossover Current Population Next Population Mutant solutions ( k ) ( k + 1) Select one parent from ELITE partition Select one parent from Non-ELITE partition
Gambar 3. Dinamika evolusi dari generasi
yang  memiliki karakteristik kurang bagus secara perlahan akan tersingkir dari populasi. Teori ini dinamakan “ Theory of Natural Selection ” oleh Charles Darwin pada tahun 1859 (Darwin, 2004).
Gambar  4  menunjukkan  proses crossover secara  acak  dengan  dua  kromosom  masing- masing terdiri dari  4 gen. Proses crossover dilakukan  berdasar pada uniform crossover parameter (Spears  &  De Jong, 1991) yaitu setiap  gen yang dipilih  dari  salah satu  orang tua  (ELIT)  dengan  probabilitas  tertentu  yang didefinisikan  oleh  pengguna  ( pe > 0,5). Probabilitas  pada  Gambar  4 dimisalkan  0,7 yang berarti bahwa keturunan akan mewarisi gen orang tua ELIT 0,7 dan orang tua lainnya 0,3.  Penentuan random number kemudian dilakukan, jika nilai acak yang muncul kurang dari atau sama dengan 0,7 maka akan mewarisi gen orang tua ELIT  selebihnya akan mewarisi gen orang tua NON-ELIT. Hasil yang diperoleh menunjukkan bahwa keturunan mewarisi gen orang tua ELIT adalah  gen pertama, ketiga dan keempat. Ketika seluruh populasi sudah terpenuhi maka akan dilakukan pengulangan kelompok
baru untuk merangkai generasi berikutnya hingga menghasilkan solusi yang optimal.
Pada BRKGA umumnya terdapat  sebuah parameter yang dikontrol meliputi jumlah kromosom/individu dalam populasi ( p ), jumlah solusi ELIT ( pe ), solusi mutan ( pm ) dan probabilitas keturunan gen ELIT ( ep ).
Parameter ini berlaku dalam perancangan algoritma BRKGA-PD. Tabel 1 menunjukkan parameter yang direkomendasi (Goncalves & Resende, 2011).
Pada penelitian ini maka dirancanglah arsitektur algoritma sebagai dasar untuk pembuatan program.  Program dibuat dengan menggunakan software Matlab  berdasarkan rancangan model dan arsitektur algoritma yang  nantinya  menghasilkan sebuah coding BRKGA-PD.  Program yang dibuat dengan parameter yang telah  ditentukan kemudian dilakukan pengujian (simulasi) untuk mengetahui hasilnya.  Pengujian program dilakukan berulang dengan sejumlah iterasi yang ditentukan agar mendapatkan setting parameter terbaik. Setting parameter terbaik inilah yang nantinya diterapkan dalam studi kasus agar diperoleh hasil yang optimal kemudian
dilakukan analisis untuk
Chromosome 1 (ELIT) Chromosome 2 (NON-ELIT) 0.32 0.77 0.53 0.85
0.26 0.15 0.91 0.44 Random Number Probability=0.7 0.58 0.89 0.68 0.25
< > < < Offspring Chromosome 0.32 0.15 0.53 0.85 X Crossover
Gambar 4. Crossover Process
Tabel 1. Parameter BRKGA (Goncalves & Resende, 2011)
Parameter Description Recommended value P size of population p = ax , where 1 ≤ a ∈ ℝ is a constant and x
is the length of the chromosome p e size of elite population 0.10 p ≤ p e ≤ 0.25 p p m size of mutant population 0.10 p ≤ p m ≤ 0.30 p ρ e elite allele inheritance probability 0.5 ≤ ρ e ≤ 0.8
dibandingkan dengan metode heuristik yang terdapat dalam penelitian Sembiring (2008).

## III. H ASIL DAN P EMBAHASAN

## Pengaturan Parameter BRKGA-Populasi Degradasi
BRKGA-PD dikodekan menggunakan Matlab versi 7.11.0.584 (R2010b) 64-bit (Win64) yang dijalankan pada notebook dengan spesifikasi Intel® CoreTM i5-2450M @ 2.50GHz dan memiliki kapasitas RAM sebesar 4GB. Pada perancangan BRKGA-PD sebelum mendapatkan setting parameter terbaik terlebih dahulu menentukan siklus dalam iterasi untuk menurunkan ukuran populasi.  Penentuan setiap berapa siklus akan mengalami penurunan ukuran populasi dilakukan 50 kali percobaan untuk setiap variasi siklus yang ditentukan.  Pada percobaan terdapat 4 variasi siklus yaitu 20, 50, 100, dan 120.  Hasil percobaan ditabelkan pada Tabel 2 yang merupakan hasil minimum biaya kemudian dirata-rata dari setiap variasi siklus yang dihasilkan.
Terlihat dalam Tabel 2 menunjukkan hasil minimum biaya yang terkecil dengan standar deviasi terkecil di siklus 50.   Penentuan siklusnya dengan bedasar pada ilmu statistik, dilihat dari nilai minimum biaya rata-rata yang  terkecil dan standar deviasi yang terkecil.    Standar deviasi merupakan selisih antar nilai yang satu dengan yang lainnya yang terdapat dalam percobaan pengulangan. Supaya terlihat jelas perbandingan dari hasil setiap siklusnya dapat digambarkan ke dalam sebuah grafik.   Gambar 5  memperlihatkan hasil dari setiap siklusnya yang menunjukkan bahwa hasilnya akan menuju konvergen pada
suatu iterasi.  Konvergen yang artinya sebuah nilai menuju titik yang memiliki nilai tidak jauh berbeda dan mampu bertahan dalam beberap iterasi.    Pada siklus 20 nilai minimum biaya menuju konvergen di iterasi ke-865, siklus 50 lebih cepat menuju konvergen dibandingkan dengan kedua variasi siklus yang lainnya di iterasi ke-223, dan siklus 100 menuju konvergen di iterasi ke-266.    Penentuan siklusnya sehingga terpilihlah setiap 50 siklus ukuran populasi akan mengalami degradasi populasi.
Perubahan ukuran populasi seperti yang ditunjukkan dalam Tabel 3, dimana siklus ini continue hingga kondisi berhenti. Berhentinya kondisi tersebut ketika telah mencapai nilai yang diinginkan yaitu 50 pada suatu generasi yang menunjukkan ukuran populasinya minimum.

## Tabel 3. Perubahan ukuran populasi dalam
BRKGA-PD Ukuran Populasi Jumlah Generasi Generasi ke- 400 100 1-50 350 100 51-100 300 100 101-150 250 100 151-200 200 100 201-250 150 100 251-300 100 100 301-350 50 300 351-1000 Gambar 5. Perbandingan hasil setiap siklus Tabel 2. Hasil siklus populasi degradasi Siklus Min biaya rata-rata (Rp) σ 20 150618,3551 3253,364 50 145733,9973 2193,299 100 145763,5404 2636,525
Pada BRKGA-PD setelah menentukan siklus untuk populasi degradasinya kemudian setting parameter yang dilakukan meliputi ukuran populasi ( P ), persen elit  ( p e ), probabilitas  ( ρ e ), dan persen mutasi  ( p m ).
Kombinasi parameter yang digunakan sebanyak 48 kombinasi. Setiap parameter diulang sebanyak 50 kali percobaan, ini
Tabel 4. Hasil rata-rata minimum biaya pada setting parameter
Kombinasi ke- Parameter Min Biaya Rata-rata
(Rp) σ P p e p m ρ ε 1 400 0,1 0,1 0,5 147310,174 2991,029 2 400 0,1 0,2 0,5 145420,152 3378,337 3 400 0,1 0,3 0,5 147312,400 2747,308 4 400 0,1 0,1 0,6 146355,230 2581,038 5 400 0,1 0,2 0,6 146580,808 3146,636 6 400 0,1 0,3 0,6 146871,660 2840,618 7 400 0,1 0,1 0,7 146325,493 2757,786 8 400 0,1 0,2 0,7 146786,940 2898,242 9 400 0,1 0,3 0,7 147345,405 2570,798 10 400 0,1 0,1 0,8 146368,847 2590,402 11 400 0,1 0,2 0,8 146431,522 2476,401 12 400 0,1 0,3 0,8 147312,400 2747,308 13 400 0,15 0,1 0,5 145447,118 1999,962 14 400 0,15 0,2 0,5 145882,918 2548,167 15 400 0,15 0,3 0,5 148958,507 3662,948 16 400 0,15 0,1 0,6 145918,283 2299,643 17 400 0,15 0,2 0,6 146407,394 2858,129 18 400 0,15 0,3 0,6 148383,139 2671,501 19 400 0,15 0,1 0,7 145436,750 2466,407 20 400 0,15 0,2 0,7 146032,281 2577,471 21 400 0,15 0,3 0,7 148422,326 3378,463 22 400 0,15 0,1 0,8 145640,111 2638,138 23 400 0,15 0,2 0,8 145812,579 2577,576 24 400 0,15 0,3 0,8 147389,877 3422,784 25 400 0,2 0,1 0,5 145293,703 2659,427 26 400 0,2 0,2 0,5 145838,485 2875,425 27 400 0,2 0,3 0,5 153376,327 6227,809 28 400 0,2 0,1 0,6 145525,942 2672,103 29 400 0,2 0,2 0,6 146110,828 2943,725 30 400 0,2 0,3 0,6 152253,922 6306,843 31 400 0,2 0,1 0,7 144978,074 2067,171 32 400 0,2 0,2 0,7 146147,225 2927,581 33 400 0,2 0,3 0,7 153829,375 5918,636 34 400 0,2 0,1 0,8 145312,929 2811,007 35 400 0,2 0,2 0,8 146430,738 2762,098 36 400 0,2 0,3 0,8 152472,735 6352,726 37 400 0,25 0,1 0,5 144463,736 2609,793 38 400 0,25 0,2 0,5 148592,998 3476,601 39 400 0,25 0,3 0,5 163844,811 10441,173 40 400 0,25 0,1 0,6 145044,112 2484,834 41 400 0,25 0,2 0,6 149112,075 4822,782 42 400 0,25 0,3 0,6 164989,022 9438,703 43 400 0,25 0,1 0,7 145151,918 1981,698 44 400 0,25 0,2 0,7 148356,804 3451,702 45 400 0,25 0,3 0,7 164183,861 10773,572 46 400 0,25 0,1 0,8 146035,845 2542,651 47 400 0,25 0,2 0,8 148323,349 3189,721 48 400 0,25 0,3 0,8 161540,565 10618,71
dilakukan karena solusi yang dihasilkan bervariasi berdasar pada sifatnya yang random sehingga didapatkan hasil rata-rata minimum biaya, seperti pada Tabel 4.
Berdasarkan hasil percobaan yang telah dilakukan, terlihat dalam Tabel 4 bahwa tidak terjadi perubahan hasil minimum biaya rata- rata yang signifikan. Pada Tabel 4 menunjukkan bahwa hasil minimum biaya rata-rata terkecil terdapat dalam kombinasi parameter ke-37. Selain itu berdasarkan percobaan tersebut untuk mengetahui lebih jelasnya hasil yang diperoleh dilakukan perbandingan 2 hasil parameter untuk melihat perbedaan dari hasilnya. Salah satu diambil secara acak terpilih pada kombinasi ke-21 untuk dibandingkan dengan kombinasi ke-37 yang disajikan ke dalam grafik Gambar 6.
Gambar 6. menunjukkan kemampuan parameter menuju ke konvergen pada suatu iterasi. Pada kombinasi parameter ke-21 terlihat kemampuan menuju konvergen di iterasi ke-689,  sedang  kombinasi parameter ke-37 kemampuan menuju konvergen lebih cepat yang terletak di iterasi ke-230. Setting parameter terbaik sehingga didapatkan di kombinasi parameter ke-37 dengan ukuran populasi  ( P ) 400 yang kemudian setiap 50 siklus akan menurun dan hingga menjadi 50, persen elit  ( p e ) 0,25, probabilitas  ( ρ e ) 0,5, persen mutasi ( p m ) 0,1.

## Performansi Algoritma BRKGA-Populasi Degradasi dan BRKGA Umum
Pada penelitian ini untuk mengetahui hasil performansi dari algoritma BRKGA-PD yang telah dirancang dapat membandingkannya dengan algoritma BRKGA umum. Pada BRKGA umum dilakukan pengaturan parameter sama seperti BRKGA-PD hanya saja ukuran populasinya konstan yaitu 50. Hasil yang didapatkan dari modifikasi populasi  degradasi pada algoritma BRKGA dengan perbedaan waktu tidak signifikan mampu memberikan penghematan biaya Rp. 6.857,-  dari BRKGA umum. Tabel 5 menyajikan hasil minimum biaya dari algoritma BRKGA-PD dan BRKGA umum.
Tabel 5. Hasil minimum biaya dari algoritma Algoritma Biaya (Rp/minggu) BRKGA Umum 156357 BRKGA-PD 149500 Perbandingan  performansi dari algoritma BRKGA-PD dan BRKGA umum untuk lebih jelasnya dapat dilihat pada grafik Gambar 4. Grafik tersebut menunjukkan bahwa hasil solusinya menuju konvergen pada suatu iterasi. BRKGA-PD terlihat lebih cepat menghasilkan solusi menuju konvergen yaitu pada iterasi ke-230 dengan biaya minimum Rp. 149.500,- dibandingkan dengan BRKGA umum.
Gambar 4. Grafik perbandingan performansi algoritma
Gambar 6. Grafik konvergen hasil BRKGA-PD

## Perbandingan BRKGA-PD dengan Metode Heuristik
Penyelesaian permasalahan CCVRPTW pada pendistribusian softdrink sebelumnya telah diteliti oleh Sembiring (2008) dengan metode heuristik. Berdasarkan metode tersebut dihasilkan minimum biaya sebesar Rp. 236.500,-.  Algoritma BRKGA-PD mampu menghasilkan minimum biaya yang lebih kecil yaitu Rp. 149.500,- sehingga lebih menghemat Rp. 87.000,-. Selain minimum biaya yang dihasilkan juga terbentuk subrute dari kedua metode tersebut. Pada metode heuristik penyusunan subrute terbentuk melalui 2 tahapan yaitu divide (pecah) dan conqueror (pengembangan).
Tahap divide merupakan pembentukan sub-sub rute dalam artian pengelompokkan outlet kedalam beberapa subrute. Pembentukan subrute ini dilakukan secara manual berdasarkan jarak terdekat. Tahap congueror merupakan tahap pengembangan subrute yang telah terbentuk ditambahkan dengan adanya batasan waktu dan kapasitas. Hasil tersebut kemudian disempurnakan dengan mengunakan software QUANT SYSTEM. Tabel 6  menampilkan subrute yang terbentuk dari BRKGA-PD dan metode heuristik.
Pada  Tabel  6  terbentuk 7 subrute dengan permasalahan yang sama.  Salah satu subrute adalah D – 7 – 8 – 10 – 9 – 6 – 5 – 4 – D.  D menunjukkan depot sedangkan angka-angka 7 – 8 – 10 – 9 – 6 – 5 – 4 merupakan outlet yang harus dilayani dalam subrutenya.

## IV. S IMPULAN
Pada penelitian ini telah dihasilkan rancangan BRKGA yang efisien dengan perlakuan modifikasi populasi degradasi untuk menyelesaikan permasalahan CCVRPTW pada pendistribusian softdrink . Rancangan BRKGA ini mampu membentuk satu set subrute dan mengurangi biaya dalam proses pendistribusiannya. BRKGA-PD telah berhasil menghasilkan solusi biaya yang lebih minimum dibandingkan dengan metode heuristik oleh Sembiring (2008).   Tidak hanya mampu menghasilkan solusi yang lebih baik dari metode heuristik, BRKGA-PD dapat memperbaiki solusi yang dihasilkan dari BRKGA umum. Rancangan algoritma ini dapat diterapkan kedalam permasahan lainnya yang memiliki karakteristik serupa.
Penerapan BRKGA-PD pada pendistribusian softdrink masih ada beberapa hal yang menjadi kelemahan. Pada penelitian ini masalah yang ditangani terkait dengan permasalahan deterministik, disarankan untuk kasus-kasus terkait dengan permasalahan probabilistik agar diteliti lebih lanjut. Selain BRKGA-PD masih banyak modifikasi yang dapat dilakukan untuk menyelesaikan permasalahan lainnya tidak hanya permasalahan pendistribusian misalnya penjadwalan proyek ataupun tata letak fasilitas. Oleh karena itu, perlu ekploitasi dan eksplorasi penerapan BRKGA lebih lanjut untuk penelitian masa depan.
Tabel 6. Hasil subrute dari metode BRKGA-PD dengan metode Heuristik
Metode Heuristik Metode BRKGA-PD Subrute Rute Rute 1 D – 7 – 8 – 10 – 9 – 6 – 5 – 4 – D D – 44 – 30 – 40 – 4 – 18 – 32 – 33 – 45 – 26 – D 2 D – 1 – 2 – 3 – 11 – 12 – 45 – 42 – 27 – D D – 7 – 21 – 2 – 20 – 28 – 34 – D 3 D – 13 – 14 – 15 – 16 – 17 – 19 – 20 – D D – 35 – 22 – 14 – 36 – 29 – 13 – D 4 D – 18 – 21 – 22 – 23 – 24 – 25 – 26 – 34 – 40 – D D – 11 – 37 – 31 – 19 – D 5 D – 28 – 31 – 32 – 33 – 35 – 36 – 37 – D D – 1 – 39 – 15 – 23 – 24 – 3 – 5 – 17 – D 6 D – 34 – 29 – 30 – 38 – 39 – 41 – 43 – 44 – D D – 10 – 6 – 25 – 41 – 42 – 38 – 8 – 12 – D 7 D – 45 – D D – 43 – 27 – 9 – D

## D AFTAR P USTAKA
Asteria, C. (2008). Penentuan Rute Distribusi dengan Algoritma Tabu Search untuk VRP dengan Time Windows . Tesis. Universitas Indonesia. Awansari, S.A.;  S. Abusini. (2013).  “Impementasi  model Capacitated Vehicle Routing problem  pada  pengiriman pupuk  urea bersubsidi”. Jurnal Mahasiswa Matematika , Vol. 1 (5).
Ballou, R.H.;  Agarwal, Y.K.  (1998).  “A  performance comparison of several  popular  algorithms for vehicle routing and scheduling”. Journal of Business Logistics, Vol. 9 (1), pp.: 51 – 65. Baskoro, S. (2011). Penerapan Algoritma Tabu Search Untuk Penyelesaian Capacitated Vehicle Routing Problem (CVRP) Studi Kasus di PT. Wahyu Jaya . Skripsi. Diponegoro University. Semarang. Bean, J.C. (1994). “Genetic algorithms and random keys for sequencing and optimization”. ORSA Journal on Computing , Vol. 6 , pp.: 154 – 160. Darwin, C. (2004). Britannica Concose Encylopedia from Encyclopedia Britanica. Available from: <http://comcise.britannica.com/ ebc/article?eu=387589>. Garey M.R.;  Johnson, D.S.  (1979). Computers and Intractability: A guide to The Theory of NP- Completeness . W.H. Freeman & Co. San Francisco. Gonçalves, J.F.; Resende, M.G. (2011). “Biased random-key genetic  algorithms for combinatorial  optimization”. Journal of Heuristics , Vol. 17 , pp.: 487 – 525. Grasas, A.;  Ramalhinho,  H.;  Pessoa,  L.S.;  Resende, M.G.; Caballé,  I.;  Barba, N.  (2014).  “On  the  improvement of blood  sample  collection at clinical  laboratories”. BMC Health Services Sesearch, Vol. 14 , pp.: 12. Hendrawan, B.E. (2007). Implementasi Algoritma Pararel Genetic Algorithm untuk Penyelesaian Heterogeneous Fleet Vehicle Routing Problem . Tugas Akhir. Institut Teknologi Sepuluh November. Surabaya. Putri, F.B.;  Mahmudy, W.F.;  Ratnawati, D.E. (2014). Penerapan Algoritma Genetik Untuk Vehicle Routing Problem with Time Window (VRPTW) Pada Kasus Optimasi Distribusi Beras Bersubsidi . Skripsi . Malang: Universitas Brawijaya. Sembiring, A. C. (2008). Penentuan Rute Distribusi Produk yang Optimal dengan Menggunakan Algoritma Heuristik Pada PT. Coca-Cola Bottling Indonesia Medan . Tugas Akhir. Universitas Sumatera Utara. Medan. Slamet, A.S., Siregar, H.H.;  Kustiyo, A.  (2014).  “Vehicle routing  problem (VRP) dengan algoritma  genetika  pada pendistribusian sayuran dataran tinggi”. Jurnal Teknologi Industri Pertanian , Vol. 24 (1), pp.: 1 – 10. Spears, V.M.;  De Jong,  K.A.  (1991).  “On The Virtues of Parameterized Uniform Crossover”.  In Proceedings of the Fourth International Conference on Genetic Algorithms , pp.: 230–236. Sundarningsih, D.;  Mahmudy,  W.F.;  Sutrisno. (2015). Penerapan Algoritma Genetika untuk Optimasi Vehicle Routing Problem With Time Window (VRPTW) Studi Kasus Air Minum Kemasan . Skripsi. Malang: Universitas Brawijaya. Toth,  P.;  Vigo,  D.  (2002). An Overview of Vehicle Roting Problem. In The Vehicle Routing Problem . Edited by Toth P, Vigo D. Philadelphia: SIAM, pp.:1 – 26.