PENYELESAIAN VEHICLE ROUTING PROBLEM UNTUK MINIMASI TOTAL BIAYA TRANSPORTASI PADA PT XYZ DENGAN METODE ALGORITMA GENETIKA

PENYELESAIAN VEHICLE ROUTING PROBLEM UNTUK MINIMASI TOTAL BIAYA TRANSPORTASI PADA PT XYZ DENGAN METODE ALGORITMA GENETIKA Astri Desiana1, AriYanuar Ridwan2, Rio Aurachman3 1, 2, 3 1

Program Studi Teknik Industri, Fakultas Rekayasa Industri, Universitas Telkom

[email protected], [email protected], [email protected]

ABSTRAK Transportasi merupakan bagian dalam rantai pasok yang menjamin barang yang telah diproduksi dapat sampai ke konsumen. Selain itu, transportasi dapat menyumbang hingga 40% dari total biaya logistik. Oleh sebab itu, suatu perusahaan perlu memiliki sistem transportasi yang baik. PT XYZ merupakan salah satu perusahaan farmasi yang mendistribusikan produknya ke berbagai wilayah seperti Bandung dan Jabodetabek. PT XYZ memiliki permasalahan di bagian transportasinya yaitu masih adanya keterlambatan pengiriman produk ke pelanggan karena belum adanya konfigurasi rute yang tepat. Keterlambatan ini mengakibatkan tidak terkirimnya barang tepat waktu dan penambahan biaya transportasi yang harus ditanggung oleh PT XYZ. Permasalahan yang ada di PT XYZ ini sering disebut dengan Vehicle Routing Problem (VRP) yaitu permasalahan penentuan rute kendaraan dengan berbagai batasan yang ada. Batasan-batasan VRP dalam penelitian ini yaitu adanya jam buka tutup di setiap pelanggan (time window), kendaraan yang digunakan terdiri atas berbagai jenis dan kapasitas (heterogeneous fleet), dan barang yang dikirim terdiri atas berbagai jenis produk (multiple products). Dalam penyelesaian permasalahan VRP ini maka digunakan algoritma nearest neighbor sebagai pembentuk solusi awal untuk kemudian diperbaiki dengan menggunakan algoritma genetika. Hasil dari penerapan algoritma tersebut dapat digunakan untuk menyelesaikan permasalahan keterlambatan dan dapat menurunkan total biaya transportasi di PT XYZ hingga mencapai 5.83%. Kata Kunci: VRP, Time Window, Heterogeneous Fleet, Multiple Products, Algoritma Nearest Neighbor, Algoritma Genetika ABSTRACT Transportation is one of the important part in the supply chain, because transportation has the responsibility to make sure that the product arrive in consumers. Besides that, transportation has 40% contribution in making total logistic cost. Therefore, a company needs to have a good transportation system. PT XYZ is one of the pharmaceutical company that distribute the product to some regions such as Bandung and Jabodetabek. PT XYZ has a problem with their transportation system that is the delay in sending the product to consumers caused by no configuration route yet. It causes there are the products that are not sent on time and extra cost that should be imposed to PT XYZ. The problem that happens in PT XYZ is called as Vehicle Routing Problem (VRP). The constraints that are used in this research are time window, heterogeneous fleet, and multiple product. The method that is used are nearest neighbor algorithm for initial solution and then improved using genetic algorithm. The implementation of these algorithms can be used for solving the delay and decrease the average of total transportation cost of PT XYZ up to 5.83%. Key Words: VRP, Time Window, Heterogeneous Fleet, Multiple Products, Nearest Neighbor Algorithm, Genetic Algorithm. 1.

PENDAHULUAN

Transportasi sebagai salah satu area dalam supply chain management didefiniskan sebagai proses menentukan bagaimana dan kapan harus mengirim barang ke konsumen. Biaya menjadi pertimbangan dalam area transportasi karena transportasi dapat menyumbang hingga 40% dari total biaya logistik[2]. Obat merupakan salah satu produk yang memiliki nilai tinggi sehingga membutuhkan jaringan transportasi yang baik terutama yang menekankan pada kecepatan dalam pengiriman. PT XYZ merupakan salah satu perusahaan farmasi di Bandung yang memproduksi berbagai macam obat generik. Untuk dapat mendistribusikan produknya, PT XYZ menggunakan armada milik sendiri maupun menggunakan jasa transpoter. Dalam mendistribusikan produknya ke 28 titik PBF wilayah Bandung dan

Jakarta, PT XYZ menggunakan armada milik sendiri, sedangkan untuk ke 6 titik PBF wilayah selain Bandung dan Jakarta, perusahaan menggunakan jasa transpoter. PT XYZ sering mengalami kendala dalam proses pendistribusiannya yaitu adanya keterlambatan pengiriman. Keterlambatan yang dimaksud yaitu ketika armada datang melebihi dari jam buka tutup (time window) pelanggan. Keterlambatan tersebut terjadi karena belum adanya penentuan konfigurasi jalur distribusi yang tepat dan hanya berdasarkan pada pengetahuan yang dimiliki oleh bagian ekspedisi. Grafik di bawah ini menunjukkan jumlah keterlambatan pengiriman yang terjadi ke PBF wilayah Jakarta dan Bandung untuk delivery order (DO) bulan April-Juli 2015. Keterlambatan ini mengakibatkan menurunnya keberhasilan pengiriman yang dapat dilakukan oleh perusahaan

Volume Produk (liter)

Tabel 1. Perbandingan DO dengan DF

Perbandingan DO dengan DF

70000 60000 50000 40000 30000 20000 10000 0 APRIL

MAY

JUNE

JULY

AUGU SEPTE ST MBER

DO 57440 57003 58171 46773 51667 59036 DF

43543 45602 45620 30744 41652 46580

Keterlambatan tersebut juga dapat menyebabkan meningkatnya biaya transportasi yang harus ditanggung oleh PT XYZ karena keterlambatan mengakibatkan barang harus dibawa kembali ke depot untuk dikirim pada hari berikutnya. Keterlambatan ini tentunya akan mempengaruhi ke pengiriman berikutnya berkaitan dengan alokasi kapasitas armada dan juga menambah biaya pengiriman. Penelitian ini dimaksudkan untuk membuat perencanaan rute distribusi yang tepat pada PT XYZ untuk mengurangi keterlambatan sehingga dapat meminimasi biaya transportasi dengan menggunakan algoritma genetika. 2. TINJAUAN PUSTAKA 2.1 Vehicle Routing Problem Vehicle routing problem (VRP) merupakan perluasan dari traveling salesman problem (TSP) sehingga VRP sering disebut sebagai m-TSP. Vehicle routing problem merupakan penentuan sebuah set rute di mana setiap rute tersebut dilakukan oleh sebuah kendaraan yang memulai perjalanan dari depot dan kembali lagi ke depot untuk memenuhi permintaan konsumen tanpa melanggar batasan-batasan yang ditetapkan serta dapat meminimasi biaya transportasi [4] . Suprayogi (2003) telah mengembangkan beberapa varian dari VRP, seperti VRP with Heterogeneous Fleet, VRP with Time Window, VRP with Pick Up and Delivery, VRP with Split Delivery, VRP with Multiple Trip, VRP with Multiple Depot, VRP with Multiple Product and Compartment, Stochastic VRP, Dynamic VRP, Periodic VRP. 2.2 Biaya Transportasi Biaya menjadi salah satu pertimbangan dalam transportasi karena transportasi menyerap rata-rata biaya logistik terbesar dibanding dengan aktivitas lainnya. Terdapat dua komponen biaya transportasi yaitu biaya tetap dan biaya variabel. Biaya tetap dalam transportasi merupakan biaya yang digunakan untuk investasi armada, biaya perawatan, dan biaya administrasi kendaraan. Sedangkan biaya variabel terdiri atas biaya bahan bakar, pekerja, biaya handling, dan biaya pick up and delivery. Klasifikasi biaya-biaya tersebut sebenarnya bergantung pada perspektif masingmasing perusahaan, karena pada dasarnya setiap komponen biaya mengandung sebagian biaya tetap dan sebagiannya lagi biaya variabel [1].

2.3 Algoritma Nearest Neighbor Algoritma nearest neighbor didefinisikan sebagai teknik yang sederhana dan terbuka untuk berbagai variasi masalah [3] . Langkah-langkah penerapan Algoritma Nearest Neighbor [3] yaitu sebagai berikut: 1. Titik awal rute dimulai dari depot atau gudang. 2. Mencari lokasi pelanggan terdekat dari depot yang belum dikunjungi. Lokasi terdekat inilah yang menjadi lokasi pertama yang akan dikunjungi. 3. Mencari lokasi lain yang terdekat dari lokasi terpilih sebelumnya. Dalam mencari lokasi lain ini terdapat beberapa pertimbangan yaitu: a. Total jumlah pengiriman tidak melebihi kapasitas kendaraan yang digunakan. b. Jika terdapat lokasi terpilih berikutnya dan masih terdapat sisa kapasitas kendaraan maka ulangi langkah (2). c. Apabila kendaraan tidak memiliki sisa kapasitas, maka kembali ke langkah (1). 4. Algoritma berhenti jika semua pelanggan telah dikunjungi tepat satu kali 2.4 Algoritma Genetika Algoritma genetika merupakan algoritma dengan pendekatan metaheuristik yang termasuk ke dalam kelompok evolutionary algorithm. Elemen dasar dari algoritma genetika yaitu reproduksi, crossover, dan mutasi. Dalam agloritma genetika, prosedur pencarian hanya didasarkan pada nilai fungsi tujuan, tidak ada pemakaian gradien atau teknik kalkulus [5]. Beberapa istilah yang digunakan dalam algoritma genetika yaitu: 1. Kromosom Dalam algoritma genetika, satu kromosom atau individu mewakili satu vektor solusi. Jika tidak bisa langsung menggunakan vektor solusi dalam implementasi algoritma genetika ini, maka dibutuhkan pengkodean untuk mewakili suatu nilai solusi dengan menggunakan bilangan biner. 2. Fitness Fitness digunakan untuk mengukur tingkat kebaikan atau kesesuaian suatu solusi dengan solusi yang dicari. Fitness bisa berhubungan langsung dengan fungsi tujuan atau modifikasi terhadap fungsi tujuan. Setelah kondisi dievaluasi dengan fungsi fitness perlu dilakukan proses seleksi terhadap kromosom. Seleksi digunakan untuk memilih di antara kromosom anggota populasi mana yang bisa menjadi induk atau menentukan kromosom mana yang akan menjadi anggota populasi berikutnya. 3. Kawin silang Kawin silang dilakukan untuk mendapatkan kombinasi yang lebih baik antara satu individu dengan individu lain dalam suatu populasi. Parameter yang penting dalam kawin silang ini yaitu probabilitas kawin silang. Jika nilai probabilitas kecil maka sedikit kromosom yang akan mengalami kawin silang dan sebaliknya. 4. Mutasi Mutasi digunakan untuk memunculkan individu baru yang berbeda sama sekali dengan individu yang sudah ada atau dapat terjadi muncul solusi baru untuk bisa keluar dari optimum lokal. 3.

PEMBAHASAN

3.1 Karakteristik Permasalahan Permasalahan pada penelitian ini tergolong ke dalam permasalahan vehicle routing problem dengan karaktersitik: 1. 2. 3.

4. 5. 6. 7. 8.

Dalam penelitian ini, PT XYZ hanya memiliki satu depot yang merupakan tempat mulai dan berakhirnya proses pendistribusian produk ke pelanggan. Produk yang didistribusikan terdiri atas berbagai jenis produk. Permintaan pelanggan dianggap deterministik dan telah diketahui sebelumnya. Selama proses pendistirbusian tidak ada proses penambahan permintaan. Setiap pelanggan memiliki permintaan terhap produk dengan jumlah dan jenis yang berbeda-beda. Proses pendistribusian menggunakan kendaraan yang terdiri atas dua jenis dan merupakan milik kendaraan. Setiap jenis kendaraan memiliki karakteristik masing-masing. Jarak antar pelanggan merupakan jarak sesungguhnya bukan jarak yang diukur dengan jarak lurus. Setiap pelanggan memiliki time window. Setiap armada melakukan satu rute per harinya dalam horizon perencanaan. Barang diukur berdasarkan volume karton kemasan bukan berdasarkan berat.

9. Waktu penyelesaian distribusi dalam perhitungan mempertimbangkan waktu perjalanan, waktu tunggu, waktu muat, dan waktu bongkar. 3.2 Model Matematika Indeks : i

tijk : waktu pengiriman dari i ke j dengan kendaraan k

: indeks customer i=0,1,2,3,…,N

j

: indeks customer j=0,1,2,3,…,N

di mana i≠j , i atau j = 0 = depot k

: indeks jenis kendaraan

p

: indeks jenis produk p=1,2,…,P

k=1,2

Parameter Qk

: kapasitas maksimal kendaraan k

Bp

: volume produk p

vk

: rata-rata kecepatan kendaraan k

Sj

: waktu pelayanan di titik j

fk

: biaya tetap kendaraan k

cijk k

: biaya variabel dari I ke j dengan kendaraan

ai

: kedatangan kendaraan di pelanggan i

bi

: keberangkatan kendaraan dari i

T

: horizon perencanaan

Variabel Keputusan Xijk = 1 jika dari i ke j menggunakan kendaraan k

Hpj : kuantitas produk p yang akan dikirim ke customer j

Xijk=0 jika lainnya

Mj

: total volume yang diminta customer j

Yk =1 jika kendaraan k digunakan

ei

: batas bawah time window customer i

Yk=0 jika lainnya

li

: batas atas time window customer i

Fungsi Tujuan: 𝑁 𝑁 𝐾 Minimasi ∑𝐾 𝑘=1 𝑓𝑘 . 𝑦𝑘 + ∑𝑘=1 ∑𝑗=0 ∑𝑖=0 𝑐𝑖𝑗𝑘 .𝑋 ……………………………………………........................1 𝑖𝑗𝑘

Pembatas: 1. Setiap lokasi tepat akan dikunjungi satu kali ∑𝐾 𝑘=0 𝑋𝑖𝑗𝑘 = 1…………………………………………………………………………………………....2 2. 3. 4.

5.

6.

Untuk i=0,1,2,3,…,N j=0,1,2,3,…N Setiap kendaraan setelah mengunjungi i akan ke i+1 𝑁 ∑𝑁 𝑖=0 𝑋𝑖ℎ𝑘 − ∑𝑗=0 𝑋ℎ𝑗𝑘 = 0 𝑑𝑖 𝑚𝑎𝑛𝑎 ∀ℎ ∈ 𝑁…………………………………………………………..3 Setiap pengiriman tidak boleh melebihi kapasitas armada 𝑁 ∑𝑁 𝑖=0 ∑𝑗=0 𝑀𝑗. 𝑋𝑖𝑗𝑘 ≤ 𝑄𝑘………………………………………………………………………………..4 Volume demand customer j merupakan penjumlahan dari hasil kali antara volume setiap jenis produk dengan jumlah setiap produk ∑𝑃𝑝=1 𝐵𝑝 . 𝐻𝑝𝑗 = 𝑀𝑗 ……………………………………………………………………………………….5 untuk j= 1, 2, …. N Kedatangan di titik j harus lebih dari waktu berangkat dari i ditambah dengan waktu tempuh dari i ke j 𝑏𝑖 + 𝑡𝑖𝑗𝑘 + 𝑀(1 − 𝑥𝑖𝑗𝑘 ) ≤ 𝑎𝑗 …………………………………………………………………………..6 untuk i=0,1,..N ; j=1,2,…,N dan k=1,2 Kedatangan harus berada dalam time window 𝑒𝑖 ≤ 𝑎𝑖 ≤ 𝑙𝑖 ………………………………………………………………………………………………7

7.

8.

Keberangkatan dari titik i merupakan penjumlahan dari waktu kedatangan di titik tersebut dengan lamanya waktu pelayanan 𝑏𝑖 = 𝑎𝑖 + 𝑆𝑖 ……………………………………………………………………………………………...8 Semua rute untuk setiap kendaraan harus kurang dari horizon perencanaan 𝑁 ∑𝑁 𝑖=0 ∑𝑗=0(𝑆𝑖 + 𝑡𝑖𝑗𝑘 ). 𝑋𝑖𝑗𝑘 ≤ 𝑇………………………………………………………………………..…9

untuk k=1,2 9. 𝑋𝑖𝑗𝑘 ∈ {0,1}………………………………………………………………………………………………….10 10. 𝑦𝑘 ∈ {0,1}…………………………………………………………………………………………………...11 3.3 Menetukan Solusi Awal dengan Algoritma Nearest Neighbor Algoritma nearest neighbor ini digunakan untuk menentukan rute awal dari proses pendistribusian yang dilakukan oleh PT XYZ. Hasil dari solusi awal rute usulan ini menjadi individu awal dalam langkah Algoritma Genetika untuk mendapatkan rute usulan perbaikan. a.

Iterasi 1 Proses penentuan rute diawali dengan melihat jadwal untuk mengetahui pelanggan mana sajakah yang akan dikunjungi pada hari itu. Sebagai contoh, pelanggan yang akan dikunjungi yaitu PBF12, PBF05, PBF28, PBF19, PBF20, PBF07, PBF03, PBF27, PBF26, dan PBF09. Setelah itu menentukan kendaraan yang akan digunakan. Kendaraan yang akan digunakan yaitu disesuaikan dengan fungsi tujuan. Karena fungsi tujuan berupa minimasi biaya, maka kendaraan yang dipilih pertama dalah kendaraan dengan biaya terendah, yaitu kendaraan Gran Max. Sedangkan kebijakan perusahaan menetapkan bahwa keberangkatan kendaraan dimulai pukul 09.00 WIB. Tabel 2. Hasil Iterasi 1 Algoritma NN RUTE TIME WINDOW DEMAND (LITER) AKUMULASI MUATAN (LITER) KAPASITAS KENDARAAN (LITER) WAKTU PERJALANAN (menit) WAKTU TIBA WAKTU PELAYANAN WAKTU BERANGKAT

b.

PBF07 PBF03 PBF27 PBF05 PBF19 PBF28 PBF09 PBF20 PBF26 DEPOT 9:00:00 8:00:00 9:00:00 9:00:00 9:00:00 8:00:00 9:00:00 9:00:00 9:00:00 17:00:00 17:00:00 17:00:00 17:00:00 17:00:00 17:00:00 17:00:00 17:00:00 17:00:00 21.46302 128.5398905 22.536171 38.8480662 32.7311055 129.1816449 221.652672 411.159998 651.848602 0 21.46302 150.0029105 172.5390815 211.3871477 244.1182532 373.2998981 594.95257 1006.11257 1657.96117 5400 5378.53698 5249.997089 5227.460918 5188.612852 5155.881747 5026.700102 4805.04743 4393.88743 3742.03883 0:02:10 0:02:38 0:05:11 0:05:39 0:04:00 0:06:34 0:03:31 0:01:15 0:11:38 0:06:17 9:02:10 9:42:16 10:33:58 11:17:15 11:59:57 12:44:59 13:35:07 14:31:13 15:54:09 17:33:02 0:37:28 0:46:31 0:37:38 0:38:42 0:38:28 0:46:37 0:54:51 1:11:18 1:32:36 9:00:00 9:39:38 10:28:47 11:11:36 11:55:57 12:38:25 13:31:36 14:29:58 15:42:31 17:26:45

Iterasi 2 Iterasi kedua ini dimulai dengan memilih dari pelanggan yang akan dikunjungi yang memiliki jarak terdekat dari depot. Berdasarkan data matriks jarak, pelanggan yang terpilih adalah PBF07 dengan jarak 1.8 km dan waktu tempuh selama 1 menit 70 detik. Kemudian dilakukan pemeriksaan kriteria kelayakan berupa permintaan dibandingkan dengan kapasitas kendaraan. Permintaan PBF07 tidak boleh lebih dari kapasitas kendaraan yang digunakan. Selain itu, waktu tiba di pelanggan tersebut juga tidak boleh melebihi dari jam tutup pelanggan. Ulangi langkah ini hingga semua konsumen terkunjungi atau terdapat batasan yang tidak terpenuhi. Tabel 3. Hasil Iterasi 2 Algoritma NN RUTE TIME WINDOW DEMAND (LITER) AKUMULASI MUATAN (LITER) KAPASITAS KENDARAAN (LITER) WAKTU PERJALANAN (menit) WAKTU TIBA WAKTU PELAYANAN WAKTU BERANGKAT

c.

DEPOT

DEPOT


Iterasi 3 Setelah kendaraan mengunjungi PBF26, seharusnya kendaraan akan mengunjungi PBF12. Akan tetapi, berdasarkan matriks waktu, maka kendaraan akan tiba di PBF12 melebihi dari jam tutup pelanggan tersebut meskipun kapasitas kendaraan masih mencukupi. Sehingga, kendaraan harus kembali ke depot.

Tabel 4. Hasil Iterasi 3 Algoritma NN RUTE

DEPOT


TIME WINDOW DEMAND (LITER) AKUMULASI MUATAN (LITER) KAPASITAS KENDARAAN (LITER) WAKTU PERJALANAN (menit) WAKTU TIBA WAKTU PELAYANAN WAKTU BERANGKAT

d.

Iterasi 4 Dari hasil iterasi 5, masih terdapat pelanggan yang belum dikunjungi. Berdasarkan diagram alir di atas, karena masih tersedia kendaraan lain maka proses iterasi akan diulang kembali dari iterasi 1 untuk jenis kendaraan yang berbeda. Berikut ini merupakan hasil dari proses iterasi untuk jenis kendaraan CDD terhadap sisa pelanggan yang belum dikunjungi. Tabel 5. Hasil Iterasi 4 Algoritma NN RUTE

DEPOT

PBF12

DEPOT

8:00:00

TIME WINDOW

17:00:00 DEMAND (LITER) AKUMULASI MUATAN (LITER) KAPASITAS KENDARAAN (LITER) WAKTU PERJALANAN (menit)

107.3151 0

107.3151

17200

17092.6849

WAKTU TIBA WAKTU PELAYANAN WAKTU BERANGKAT

3:06:34

3:06:34

12:06:34

15:57:52

0:44:44 0.375

0.535625

Proses iterasi berakhir ketika semua pelanggan telah tepat dikunjungi satu kali. Dengan urutan kunjungan tersebut, maka total jarak yang dilalui oleh kendaraan GranMax pada hari tersebut yaitu sepanjang 77.3 km. Sedangkan untuk kendaraan CDD melakukan perjalanan sejauh 340 km dalam hari yang sama. 3.4 Perbaikan Rute dengan Algoritma Genetika Langkah-langkah penentuan rute dengan Algoritma Genetika adalah sebagai berikut: 1.

2.

Inisialisasi Proses inisialisasi merupakan proses menentukan parameter-parameter yang digunakan dalam Algoritma Genetika ini. Penentuan parameter dimulai dengan menentukan jumlah gen dalam satu kromosom. Setelah ditentukan lebar kromosom atau jumlah gen dalam satu kromosom, maka selanjutnya adalah menentukan banyaknya kromosom dalam satu populasi. Ukuran populasi yang digunakan dalam penelitian ini yaitu 30 individu dengan probabilitas kawin silang 0.95 dan probabilitas mutasi 0.01. Setelah ditentukan parameter yang akan digunakan, maka tahapan inisialisasi dilanjutkan dengan pembangkitan populasi awal. Kromosom pertama pada populasi pertama diperoleh dari hasil rute awal dengan menggunakan Algoritma Nearest Neighbor. Sedangkan untuk kromosom-kromosom lainnya pada populasi pertama diperoleh dari hasil acak permutasi gen-gen pada kromosom pertama. Evaluasi Fungsi Fitness Setelah terbentuk kromosom-kromosom pada populasi pertama, maka dihitung fitness dari setiap kromosom tersebut. Untuk kasus minimasi, fungsi fitness diperoleh dengan rumus: 1 𝐹(𝑥) = ……………………………………………………………………………………..12 𝑓(𝑥)+1

dimana f(x) merupakan fungsi tujuan. Hasil dari perhitungan fungsi fitness untuk populasi awal seperti pada tabel di bawah ini.

Tabel 6. Contoh Hasil Perhitungan Fitness KROMOSOM

3.

FITNESS

1

2.2130 e-6

2

2.2595 e-6

3

2.2112 e-6

4

1.9515 e-6

5

1.9836-6

Seleksi Proses seleksi merupakan proses pemilihan individu yang akan dipertahankan untuk populasi selanjutnya [6]. Proses seleksi yang digunakan yaitu proses seleksi sebanding dengan nilai fitness, sehingga individu yang memiliki nilai fitness tinggi memiliki peluang bertahan lebih besar. Seleksi sebanding dengan nilai fitness ini biasanya diimplementasikan dengan model roda rolet [6]. Pendekatan proses seleksi dengan roda rolet yang digunakan yaitu seleksi secara acak menggunakan bilangaan riil. Berikut ini merupakan contoh proses seleksi untuk kromosom pada populasi pertama. Tabel 7. Contoh Perhitungan Seleksi

4.

KROMOSOM

Fitness

Proporsi Fitness

Kumulatif

Bil Random

Kromosom Terpilih

1 2 3 4 5 . . . . 30 TOTAL FITNESS

0.000002213 0.000002259 0.000002003 0.000002205 0.000002035 . . . . 0.000002014

0.0357 0.036442 0.032312 0.035571 0.032829 . . . . 0.03249

0.0357 0.072142 0.104454 0.140025 0.172854 . . . . 1

0.0583 0.9722 0.251475 0.091406 0.894502 . . . . 0.800092

2 30 8 3 27 . . . . 24

6.19888E-05

Kawin Silang Proses kawin silang merupakan operator dalam algortima genetika yang berfungsi untuk melahirkan kromosom baru yang mewarisi sifat-sifat induknya [6]. Kawin silang dimulai dengan menentukan individuindividu yang akan dijadikan induk. Individu-individu yang akan dipilih tersebut berasal dari hasil seleksi berdasarkan pada nilai fitness pada proses selanjutnya.Penentuan induk dimulai dengan pembangkitan bilangan random sejumlah kromosom dalam populasi. Apabila bilangan random untuk kromosom tersebut kurang dari probabilitas kawin silang yang digunakan yaitu 0.95, maka individu tersebut terpilih sebagai induk. Berikut ini merupakan contoh proses pemilihan induk untuk kawin silang pada populasi pertama. Tabel 8.Contoh Pemilihan Induk Kawin Silang KROMOSOM 1 2 3 4 5

BIL RANDOM 0.5343 0.68179 0.988 0.445 0.339

INDUK V V V V

Berdasarkan pada tabel di atas, diperoleh 4 induk yang terpilih sebagai induk dalam proses kawin silang dengan pasangan 1 dengan 2 dan 4 dengan 5. Proses kawin silang yang digunakan yaitu kawin silang berbasis urutan. Metode ini akan memilih posisi gen secara acak. Pemilihan gen dilakukan dengan pembangkitan bilangan random sejumlah sub rute dalam kromosom. Kemudian gen-gen yang terpilih tersebut digunakan untuk membentuk kromosom anak hasil persilangan. Kromosom anak pertama diperoleh dari gen-gen terpilih induk pertama namun dengan urutan mengikuti gen-gen pada induk kedua. Sedangkan gen-gen yang tidak terpilih diambil dari gen tidak terpilih dari kromosom pertama. Populasi yang terbentuk setelah proses penyilangan diilustrasikan seperti di bawah ini.

anak 1 anak2

0 0

27 27

9 19

19 9

8 8

20 20

12 28

0 5

0 7

28 26

5 0

7 0

26 12

0 0

Gambar 1. Contoh Hasil Penyilangan 5.

4.

Mutasi Kromosom-kromosom hasil kawin silang ini akan dikenai operator mutasi. Gen-gen yang akan dikenai operator mutasi dipilih berdasarkan mekanisme random. Bilangan random yang dibangkitkan sejumlah banyaknya gen dalam satu populasi. Apabila bilangan random untuk suatu gen kurang dari samadengan probabilitas mutasi yang ditetapkan yaitu 0.01 maka gen tersebut terpilih untuk dilakukan proses mutasi. Mutasi ini dapat menghasilkan kromosom yang lebih bervariasi dalam suatu populasi. Hasil dari proses mutasi ini akan menjadi individu-individu anggota populasi pada generasi berikutnya. Langkah-langkah di atas akan terus diulangi hingga 200. Sebagai contoh, setelah dilakukan proses penghitungan hingga 200 generasi, maka diperoleh individu terbaik untuk pengiriman pada tangga 22 Juli 2015 berdasarkan pada nilai fitness terbesar dengan nilai 0.00000227 dan menghasilkan rute untuk kendaraan 1: Depot-5-28-12-19-Depot dan untuk kendaraan 2: depot-7-3-27-20-Depot.

KESIMPULAN

Berdasarkan hasil penentuan rute pendistribusian pada PT XYZ dengan menggunakan Algoritma Genetika, maka diperoleh kesimpulan: 1. Penggunaan Algoritma Genetika untuk menentukan rute distribusi mampu untuk mengatasi keterlambatan pengiriman dan menghasilkan rute yang lebih baik dari rute eksisting. Hal ini dibuktikan dengan berkurangnya jumlah konsumen yang tidak terlayani dan meningkatnya pemenuhan demand konsumen dalam satu horizon perencanaan. 2. Rute usulan hasil dari Algoritma Genetika mampu menghasilkan rute dengan jarak tempuh dan waktu tur yang lebih pendek, serta biaya transportasi yang lebih sedikit seperti ditunjukkan dalam tabel di bawah ini. Berdasarkan rute usulan ini mampu menghasilkan rata-rata penurunan biaya transportasi sebesar Rp 102.309,55 atau 5.83% dari biaya eksisting. DAFTAR PUSTAKA [1] Ballou, R. H. (2004). Business Logistics/Supply Chain Management. Pearson Prentice Hall. [2] Frazelle, Edward. (2001). Supply Chain Strategy. McGraw-Hill [3] Mahardika Amri, A. R. (n.d.). Penyelesaian Vehicle Routing Problem dengan Menggunakan Metode Nearest Neighbor. [4] Paolo Toth, D. V. (2002). The Vehicle Routing Problem. Philadelpia: Siam. [5] Santosa, B. (2011). Metoda Metaheuristik Konsep dan Implementasi. Surabaya: Prima Printing. [6] Zukhri, Z. (2014). Algoritma Genetika Metode Komputasi Evolusioner untuk Menyelesaikan Masalah Optimasi. Yogyakarta: Andi offset.

PENYELESAIAN VEHICLE ROUTING PROBLEM UNTUK MINIMASI TOTAL BIAYA TRANSPORTASI PADA PT XYZ DENGAN METODE ALGORITMA GENETIKA

Recommend Documents