Emirul Bahar, Dewi Agushinta R., Rossi Septy Wahyuni

SOLUSI ALGORITMA GENETIKA PADA

PERMASALAHAN TRANSPORTASI KOMODITAS

BUNGA KRISAN

Hasil Penelitian Hibah Unggulan Perguruan Tinggi TA 2015-2016

PENERBIT GUNADARMA

Matlabprojects.org

ii

Emirul Bahar, Dewi Agushinta R., Rossi Septy Wahyuni

SOLUSI ALGORITMA GENETIKA PADA

PERMASALAHAN TRANSPORTASI KOMODITAS

BUNGA KRISAN

PENERBIT GUNADARMA

iii

Solusi Algoritma Genetika Pada Permasalahan Transportasi Komoditas Bunga Krisan

Oleh : Emirul Bahar, Dewi Agushinta R., Rossi Septi Wahyuni

Gambar Sampul : Dewi Agushinta R.

Design dan Layout : Dewi Agushinta R.

Edisi Pertama Cetakan Kedua, Desember 2016

Diterbitkan pertama kali oleh Gunadarma Hak Cipta Dilindungi Undang-Undang Jakarta 2016

ISBN : 978-602-9438-66-6

iv

PRAKATA

Segala puji serta syukur kehadirat Tuhan Yang Maha Esa, karena atas rahmat-

Nya sehingga Penulis dapat menyelesaikan buku hasil dari Penelitian

Unggulan Perguruan Tinggi yang berjudul “Optimalisasi Rute Transportasi

Komoditas Bunga Krisan Dengan Menggunakan Genetic Algorithm Untuk

Kapasitas Kendaraan Angkut Yang Berbeda”. Buku ini merupakan luaran

dari penelitian yang Penulis lakukan dalam rangka mengikuti Program DIKTI.

Penulisan ini tidak luput dari bantuan banyak pihak. Oleh karena itu, pada

kesempatan ini Penulis ingin menyampaikan rasa terima kasih yang sebesar-

besarnya kepada:

1. Prof. Dr. E. S. Margianti, SE., MM., selaku Rektor Universitas Gunadarma,

beserta seluruh pimpinan Universitas Gunadarma.

2. Prof. Dr. Ir. Bambang Suryawan, MT. selaku Dekan Fakultas Teknologi

Industri, Universitas Gunadarma.

3. Dr. Ir. Hotniar Siringoringo MSc., selaku Ketua Lembaga Penelitian,

Universitas Gunadarma.

4. Pihak pemberi hibah dalam hal ini Kementrian Riset Teknologi dan

Pendidikan Tinggi.

5. Maesa, Poltak dan Arum, mahasiswa mahasiswi yang membantu Penulis

melakukan penelitian.

6. Pihak-pihak lain yang tidak dapat disebutkan namanya satu per satu.

Penulis menyadari bahwa buku ini masih jauh dari sempurna karena

keterbatasan waktu dan kemampuan yang dimiliki. Penulis berharap agar buku

ini dapat bermanfaat bagi semua pihak yang membacanya. Untuk itu Penulis

mengharapkan saran dan kritik yang membangun demi kesempurnaan buku ini.

Jakarta, Oktober 2016

Penulis

v

DAFTAR ISI

PRAKATA

DAFTAR ISI

DAFTAR TABEL

DAFTAR GAMBAR

BAB 1. ALGORITMA GENETIKA

1.1 Fitness Value

1.2 Seleksi

1.3 Crossover

1.4 Mutasi

BAB 2. RUTE KENDARAAN ANGKUT

2.1 Masalah Rute kendaraan Angkut

2.2 Variasi Permasalahan VRP

2.2 Metode Penyelesaian VRP

2.4 Heterogeneous Fleet VRP

2.5 Model Matematis Heterogeneous Fleet VRP

2.6 Nearest Neighbor Algorithm

BAB 3. TRANSPORTASI KOMODITAS BUNGA KRISAN

3.1 Transportasi Komoditas

3.2 Profil Perusahaan (Depot)

3.3 Produk dan Armada Pengiriman (Vehicles)

3.4 Data Pelanggan (Customer)

3.5 Lokasi Pelanggan (Rute)

BAB 4. PEMODELAN ALGORITMA GENETIKA

4.1 Pengolahan Data

4.2 Pemodelan Chromosome

4.3 Pergantian Populasi

BAB 5. SOLUSI MASALAH ALAT ANGKUT YANG BERBEDA

5.1 Permasalahan Alat Angkut Berbeda

5.2 Tahap Pengembangan Model

BAB 6. PERANCANGAN DAN IMPLEMENTASI

iv

v

vii

viii

1

5

5

7

7

9

9

12

13

15

15

16

19

19

22

23

26

26

28

28

39

40

40

45

47

vi

6.1 Deskripsi Umum Perangkat Lunak

6.2 Rancangan Perangkat Lunak

6.3 Implementasi Arsitektur

6.4 Batasan Implementasi

6.5 Implementasi Algoritma

6.6 Uji Coba Evaluasi

DAFTAR PUSTAKA

LAMPIRAN BARIS PROGRAM

47

47

52

54

54

59

67

70

vii

DAFTAR TABEL

Tabel 1.1 Daftar Istilah pada AG Beserta Penjelasan

Tabel 3.1 Spesifikasi Kendaraan Perusahaan

Tabel 3.2 Volume Kendaraan

Tabel 3.3 Daftar Customer (Pelanggan) PT. EDAR

Tabel 4.1 Inisialisasi Awal

Tabel 4.2 Evaluasi Fitness Value Populasi Awal

Tabel 4.3 Proses Selection Populasi Awal

Tabel 4.4 Hasil Selection Populasi Awal

Tabel 4.5 Populasi Hasil Proses Crossover

Tabel 4.6 Hasil Proses Mutation

Tabel 4.7 Hasil Populasi Generasi Pertama Pada Tabel Evaluasi

Tabel 5.1 Demand Produk Krisan yang Dikirim Pemasok

Tabel 5.2 Proses Iterasi Mobil Boks L300 Kapasitas 372.000 Batang

Tabel 5.3 Proses Iterasi Mobil Boks Engkle Kapasitas 678.000 Batang

Tabel 5.4 Proses Iterasi Mobil Boks double Kapasitas 1.152.000 Batang

Tabel 5.5 Proses Penentuan Vehicle Untuk Daerah Serpong

Tabel 5.6 Hasil Penentuan Vehicle Optimal Model Permasalahan HFVRP

2

24

24

26

30

30

31

32

35

37

38

41

41

42

42

44

44

viii

DAFTAR GAMBAR

Gambar 1.1 Siklus Algoritma Genetika

Gambar 1.2 Contoh Metode Roulette Wheel

Gambar 1.3 Ilustrasi Proses Crossover

Gambar 1.4 Ilustrasi Proses Mutasi

Gambar 2.1 Solusi dari Sebuah VRP

Gambar 2.2 Permasalahan Dasar Kelas VRP dan Keterkaitannya (Prana, 2007)

Gambar 3.1 Perkembangan Produksi Krisan, 2000-2011 (Dep. Pertanian, 2013)

Gambar 3.2 Perkembangan Produktivitas Krisan, 2000-2011 (Dep. Pertanian,

2013)

Gambar 3.3 Karakteristik Armada Pengiriman

Gambar 3.4 Peta Lokasi Depot dan Customer

Gambar 4.1 Flowchart Proses Manual

Gambar 4.2 Pengkodean Chromosome Untuk Permasalahan VRP

Gambar 4.3 Pembangkitan Bilangan Acak 1 Sampai 25

Gambar 4.4 Hasil Rute Optimal Pendistribusian Bunga Krisan Generasi

Pertama

Gambar 6.1 Desain DFD Level 0

Gambar 6.2 Desain DFD Level 1

Gambar 6.3 Desain DFD Level 2

Gambar 6.4 Desain Perancangan User Interface Aplikasi

Gambar 6.5 Diagram Optimalisasi Rute dengan Fungsi Parameter De Jong

Gambar 6.6 Output Rute Optimal Aplikasi Untuk Skenario 1

Gambar 6.7 Optimalisasi Rute dengan Fungsi Parameter Lee Jacobson

Gambar 6.8 Output Rute Optimal Aplikasi Untuk Skenario 2

Gambar 6.9 Optimalisasi Rute dengan Fungsi Parameter Sri Kusumadewi

Gambar 6.10 Output Rute Optimal Aplikasi Untuk Skenario 3

Gambar 6.11 Output Aplikasi

5

6

7

8

10

13

20

20

25

27

28

29

36

39

49

50

51

52

60

61

62

63

64

65

66

1

BAB 1

ALGORITMA GENETIKA

Pada tahun 1859 Charles Darwin (1809 - 1882), seorang peneliti alam

dari Inggris, mengumumkan teorinya yang berjudul “Theory of Natural

Selection”. Teori tersebut menyatakan bahwa individu-individu yang

mempunyai karakteristik yang bagus (menurut kriteria-kriteria tertentu) akan

mempunyai kemungkinan untuk bertahan hidup lebih besar dan bereproduksi

dengan menurunkan karakteristiknya kepada keturunan-keturunannya.

Berlaku sebaliknya, individu-individu dengan karakteristik yang kurang

bagus secara perlahan akan tersingkir dari populasi.

Pada alam ini, informasi genetik dari sebuah individu disimpan

dalam chromosome, yang terdiri dari sekumpulan gen. Karakteristik dari setiap

individu dikendalikan oleh gen-gen tersebut, yang kemudian akan diwariskan

kepada keturunan-keturunannya ketika individu tersebut berkembang biak.

Selain faktor perkembangbiakan, suatu ketika juga terjadi peristiwa yang

disebut mutasi, yang menyebabkan terjadinya perubahan informasi pada

chromosome. Berdasarkan teori Darwin tersebut, nilai rata-rata karakteristik

dari populasi akan meningkat setiap generasi, seiring dengan bertambahnya

individu-individu yang mempunyai kriteria yang bagus dan punahnya

individu-individu yang mempunyai kriteria yang buruk.

Terinspirasi dari teori Darwin tersebut, pada tahun 1975 John Holland

dan timnya menciptakan teori Algoritma Genetika (AG). Ide utama di balik

Algoritma Genetika ini adalah memodelkan proses evolusi alami menggunakan

warisan genetika seperti yang diumumkan oleh Darwin. Meskipun

diperkenalkan oleh John Holland, penggunaan Algoritma Genetika untuk

memecahkan persoalan yang kompleks baru didemonstrasikan kemudian

(pada tahun yang sama) oleh De Jong, dan kemudian oleh Goldberg pada

tahun 1989. Menyesuaikan dengan teori Darwin, dalam Algoritma Genetika

digunakan istilah-istilah yang mewakili elemen-elemen dalam teori Darwin

tersebut, yaitu seperti yang dapat dilihat pada tabel 1.1.

2

Tabel 1.1 Daftar Istilah pada AG Beserta Penjelasan

Istilah Makna

Population

Merupakan sekumpulan solusi dari permasalahan yang akan diselesaikan menggunakan Algoritma Genetika. Population terdiri dari sekumpulan Chromosome.

Chromosome

Mewakili sebuah solusi yang mungkin (feasible solution) untuk permasalahan yang ingin diselesaikan. Sebuah Chromosome terdiri dari sekumpulan Gen.

Gen Mewakili elemen-elemen yang ada dalam sebuah solusi.

Parent Merupakan chromosome yang akan dikenai operasi genetik (crossover).

Offspring Adalah chromosome yang merupakan hasil dari operasi genetik (crossover).

Crossover

Merupakan operasi genetik yang mewakili proses perkembangbiakan antar individu. Proses crossover ini memerlukan dua buah parent dan menghasilkan satu atau lebih offspring (keturunan).

Mutation

Merupakan operasi genetik yang mewakili proses mutasi dalam perjalanan hidup individu. Mutasi berperan menghasilkan perubahan acak dalam populasi, yang berguna untuk menambah variasi dari chromosome-chromosome dalam sebuah populasi. Detail dari proses mutasi ini juga akan dibahas kemudian.

Selection Procedure

Merupakan proses yang mewakili proses seleksi alam (natural selection) dari teori Darwin. Proses ini dilakukan untuk menentukan parent dari operasi genetik (crossover) yang akan dilakukan untuk menghasilkan keturunan (offspring).

Fitness Value

Merupakan penilaian yang menentukan bagus tidaknya sebuah chromosome. Chromosome yang mempunyai Fitness Value yang rendah pada akhirnya akan tersingkir oleh chromosome-chromosome yang mempunyai Fitness Value yang lebih baik.

Evaluation Function

Merupakan fungsi yang digunakan untuk menentukan nilai dari Fitness Value. Evaluation Function ini merupakan sekumpulan kriteria-kriteria tertentu dari permasalahan yang ingin diselesaikan.

Generation Merupakan satuan dari populasi setelah mengalami operasi-operasi genetika, berkembang biak, dan

3

menghasilkan keturunan. Pada akhir dari setiap generation, untuk menjaga agar jumlah chromosome dalam populasi tetap konstan, chromosome-chromosome yang mempunyai Fitness Value yang rendah dan memiliki peringkat di bawah nilai minimal akan dihapus dari populasi.

Algoritma Genetika merupakan metode pembelajaran heuristic yang adaptif,

karena itu bisa jadi terdapat beberapa versi dari Algoritma Genetika, yang

menyesuaikan dengan permasalahan yang dihadapi. Algoritma Genetika juga

merupakan algoritma yang efektif dan sederhana dan relatif mudah untuk

diimplementasikan. Algoritma Genetika memiliki keunggulan-keunggulan

dibandingkan dengan metode-metode heuristic yang lain, yaitu (Eko, 2007):

1. AG menyelesaikan masalah dengan mengkodekan permasalahan menjadi

chromosome, bukan dengan menyelesaikan permasalahan itu sendiri.

Karena itu diperlukan pemodelan chromosome yang baik dan efektif yang

dapat mewakili solusi dari permasalahan yang dihadapi.

2. AG memulai prosesnya dengan sekumpulan initial solutions, berbeda

dengan metaheuristic lain seperti Simulated Annealing dan Tabu Search yang

memulai proses dengan sebuah solusi tunggal, dan berlanjut ke solusi

lainnya melalui suatu transisi. Karena itu AG melakukan pencarian

multi-directional dalam solution space, yang memperkecil kemungkinan

berhentinya pencarian pada kondisi local optimum.

3. Hanya diperlukan sebuah fungsi evaluasi tunggal yang berbeda untuk tiap

permasalahan.

4. Algoritma Genetika merupakan algoritma yang ‘buta’, karena AG tidak

mengetahui kapan dirinya telah mencapai solusi yang optimal.

Seperti yang telah disebutkan sebelumnya, Algoritma Genetika dapat

dengan mudah beradaptasi dengan berbagai macam permasalahan, sehingga

ada banyak versi dari Algoritma Genetika, tergantung dari permasalahan yang

ingin dipecahkan. Tapi secara umum Algoritma Genetika harus memenuhi

kriteria- kriteria berikut ini untuk menghasilkan solusi yang optimal:

4

1. Sebuah representasi yang tepat dari sebuah solusi permasalahan, dalam

bentuk chromosome.

2. Pembangkit populasi awal. Umumnya populasi awal dibangkitkan secara

acak, namun untuk beberapa kasus juga bisa dibangkitkan melalui

metode-metode tertentu. Penggabungan keduanya (pembangkitan

populasi awal secara acak dan menggunakan metode-metode tertentu)

disebut dengan seeding. Populasi awal yang dihasilkan sebaiknya bersifat

heterogen, karena jika populasi yang terbentuk terlalu homogen, Genetic

Algorithm kehilangan kemampuannya untuk mencari dalam solution space,

sampai populasi mempunyai variasi chromosome yang beragam melalui

operasi genetik lain (mutation).

3. Sebuah evaluation function untuk menentukan fitness value dari tiap

solusi.

4. Genetic Operator, mensimulasikan proses reproduksi (perkembangbiakan)

dan mutasi.

5. Parameter-parameter lain, seperti kapasitas populasi, probabilitas dari

operasi-operasi genetik, dan semacamnya.

6. Kapasitas populasi sangat mempengaruhi kemampuan Algoritma Genetika

dalam mencari solusi. Kapasitas populasi yang terlalu kecil menyebabkan

kurangnya variasi chromosome yang muncul, sehingga dapat menyebabkan

hasil akhir yang buruk. Kapasitas populasi yang besar biasanya

memberikan hasil yang lebih baik, dan mencegah terjadinya konvergensi

yang prematur.

Terbentuknya populasi merupakan sekumpulan individu yang diproses

bersama dalam sebuah siklus proses evolusi. Satu-satuan siklus proses evolusi

dinyatakan dalam generasi. Dalam proses evolusi, individu secara terus-

menerus mengalami perubahan gen untuk menyesuaikan diri dengan

lingkungan hidupnya. Hasil akhir tiap evolusi nantinya diharapkan diperoleh

individu yang terbaik. Siklus proses evolusi Algoritma Genetika ditunjukkan pada

Gambar 1.1.

5

Gambar 1.1 Siklus Algoritma Genetika

1.1 Fitness Value

Untuk melakukan seleksi alam, setiap individual i dievaluasi

menggunakan nilai fitness value fi, yang ditentukan dengan sebuah fungsi

evaluasi. Fitness value mengukur kualitas dari sebuah solusi dan memungkinkan

tiap solusi untuk dibandingkan. Memilih individual untuk proses reproduksi

dan seleksi alam mempunyai efek yang sangat berpengaruh terhadap efisiensi

AG. Seleksi yang berlebihan akan mengarahkan AG ke kondisi konvergen yang

prematur, yang merupakan masalah utama pada AG (Bangun, 2011). Karena

proses seleksi bergantung pada fitness value, maka penting dalam AG untuk

membuat fungsi evaluasi dengan hati-hati.

1.2 Seleksi

Dari berbagai penelitian, terlihat bahwa keragaman populasi dan

pemilihan seleksi merupakan faktor penting dalam pencarian genetik (Bangun,

2011). Keduanya saling berkaitan, karena penekanan pada proses seleksi akan

menurunkan jumlah populasi dan sebaliknya. Jika anggota populasi menjadi

terlalu homogen, mutasi merupakan satu-satunya faktor untuk menghasilkan

variasi pada populasi. Karena itu proses selection merupakan tahapan yang

penting dalam AG. Individu yang lebih kuat akan mempunyai kemungkinan

yang lebih besar untuk melakukan reproduksi.

Salah satu metode selection yang banyak adalah metode Roulette Wheel.

Pada metode ini, kemungkinan memilih individual berkaitan langsung dengan

fitness value-nya. Gambar 1.3 mengilustrasikan sebuah cara sederhana untuk

menentukan selection pada individu dalam sebuah populasi. Individu P1

6

punya fitness value f1, P2 punya f2, dan seterusnya. Bayangkan ada sebuah pin

di atas roda tersebut, kemudian roda tersebut diputar sampai berhenti. Dari

proporsi pembagian luas roda pada tiap individu, dapat diperkirakan bahwa

individu P3 mempunyai kemungkinan terpilih paling besar, dan individu P4

mempunyai kemungkinan paling kecil. Gambar 1.2 merupakan contoh

pembagian luas roda untuk masing-masing individu.

Gambar 1.2 Contoh Metode Roulette Wheel

Kelemahan metode Roulette Wheel yaitu akan menimbulkan

permasalahan ketika perbedaan fitness value antar individu tidak terlalu besar,

sehingga kemungkinan tiap individu menjadi hampir sama.

Metode lainnya adalah metode Ranking, yang telah memberikan hasil

yang relatif lebih bagus. Metode ini menggunakan perbandingan nilai relatif

dari tiap individual, bukan nilai fitness itu sendiri. Karena jika menggunakan

nilai fitness langsung, jika populasi mempunyai beberapa individu yang

dominan, individu-individu tersebut akan semakin mendominasi populasi dan

menyebabkan konvergensi prematur.

Metode lainnya adalah Tournament Selection, yang merupakan kombinasi

dari selection dan ranking. Pada tournament selection, setiap individu

dibandingkan dalam sebuah ‘turnamen’, individu yang berkualitas lebih baik

akan menang. Metode turnamen yang umum digunakan adalah pendekatan

biner, pada satu waktu dipilih dua pasang individu (secara acak), dan

membandingkan masing-masing pasangan individu untuk mendapatkan dua

individu yang terbaik dari masing-masing pasangan.

7

1.3 Crossover

Operator AG yang paling utama adalah crossover, yang mensimulasikan

proses reproduksi antara dua individu. Cara kerjanya adalah menggabungkan

dua buah individu (yang disebut parent) untuk menghasilkan satu atau lebih

individu baru (yang disebut offspring). Offspring tersebut mewarisi sifat-sifat

genetik dari offspring-nya, sehingga sifat-sifat baik dari parent-nya tetap

dipertahankan dan diharapkan dari dua parent yang baik dapat

menghasilkan offspring/ keturunan yang lebih baik.

Ada beberapa proses crossover yang dapat diaplikasikan pada AG,

bergantung pada tipe permasalahan dan tipe populasi yang ada, namun proses

crossover sederhana dapat diilustrasikan sebagai dua parent P1 dan P2 yang

dipilih menggunakan proses selection (atau random), kemudian masing-masing

parent tersebut dipecah menjadi dua bagian pada bagian yang sama. Kedua

parent tersebut kemudian saling bertukar pasangan untuk menghasilkan dua

offspring O1 dan O2, seperti ditunjukkan pada Gambar 1.4. Offspring O1

dihasilkan dari potongan kanan P1 dan potongan kiri P2, dan offspring O2

dihasilkan dari potongan kiri P2 dan potongan kanan P2. Proses crossover lebih

jelas dapat dilihat pada Gambar 1.3.

P1 :

P2 :

O1 : O2 :

Gambar 1.3 Ilustrasi Proses Crossover

1.4 Mutasi

Operator lain yang juga berperan penting adalah mutation (mutasi), yang

diaplikasikan pada sebuah individual tertentu. Proses ini merubah sedikit

komposisi penyusun individual tersebut, dan menambahkan suatu karakteristik

1 0 1 1 1 0 1

1 1 1 1 0 1 1

1 1 1 1 1 0 1 1 0 1 1 0 1 1

8

tertentu secara acak. Proses ini tidak boleh terlalu banyak dilakukan karena

akan membuat AG menjadi seperti random search, sedangkan jika populasi AG

ada pada kondisi yang sangat konvergen, mutasi justru diperlukan untuk

membuat variasi-variasi baru pada populasi.

P :

O :

Gambar 1.4 Ilustrasi Proses Mutasi

Contoh sederhana operasi mutation dapat dilihat pada Gambar 1.4. Pada

gambar tersebut terdapat sebuah data biner P yang merupakan parent

individual. Kemudian dipilih sebuah bit secara acak untuk dilakukan proses

8utase. Pada contoh, dipilih bit pada posisi nomor 2, yang kemudian dirubah

dari 0 menjadi 1 pada offspring-nya.

1 0 1 1 0 1

1 1 1 1 0 1

9

BAB 2

RUTE KENDARAAN ANGKUT

2.1 Masalah Rute kendaraan Angkut

Masalah rute kendaraan angkut atau yang sangat dikenal dengan istilah

Vehicle Routing Problem (VRP), diperkenalkan pertama kali oleh Dantziq dan

Ramser pada tahun 1959 (Laporte et.al, 2000). Semenjak itu dipelajari secara luas.

Secara sederhana, VRP merupakan permasalahan yang meliputi konstruksi rute-

rute dari sejumlah vehicle (kendaraan) yang dimulai dari suatu depot utama

menuju ke lokasi sejumlah customer (pelanggan) dengan jumlah permintaan

tertentu. Tujuannya adalah untuk meminimumkan biaya total tanpa melebihi

kapasitas kendaraan yang berlokasi pada satu atau lebih depot yang dijalankan

oleh sekelompok pengendara dengan menggunakan road network yang sesuai.

VRP dapat didefinisikan sebagai suatu pencarian solusi yang meliputi

penentuan sejumlah rute. Masing-masing rute dilalui oleh satu kendaraan yang

berawal dan berakhir di depot asalnya sehingga kebutuhan/ permintaan semua

pelanggan terpenuhi dengan tetap memenuhi kendala operasional yang ada,

juga dengan meminimalisasi biaya transportasi global (Toth dan Vigo 2002)

(Prana, 2007).

VRP juga dapat dilihat sebagai kombinasi dari dua permasalahan

optimalisasi lain, yaitu Bin Packing Problem (BPP) dan Travelling Salesman

Problem (TSP). BPP dapat dideskripsikan sebagai “Diberikan sejumlah angka,

yang melambangkan ukuran dari sejumlah item, dan sebuah konstanta K, yang

melambangkan kapasitas dari bin. Berapa jumlah bin minimum yang

diperlukan?” (Falkanauer, 1996). Tentu saja satu item hanya dapat berada dalam

satu bin saja, dan total kapasitas item pada setiap bin tidak boleh melebihi

kapasitas dari bin tersebut. Di samping itu, TSP adalah sebuah permasalahan

tentang seorang salesman yang ingin mengunjungi sejumlah kota. Salesman harus

mengunjungi tiap kota sekali saja, dimulai dan diakhiri dari kota awal. Inti

permasalahan adalah untuk menemukan jalur terpendek melalui semua kota

10

yang ada. Hubungan keduanya dengan VRP adalah vehicle dapat dihubungkan

dengan customer menggunakan BPP, dan urutan kunjungan vehicle terhadap tiap

customer diselesaikan menggunakan TSP. Gambar 2.1 menunjukkan solusi dari

sebuah permasalahan VRP dalam bentuk graph. Pada Gambar 2.1, node 0

melambangkan depot (kota asal), dan node 1-10 melambangkan customer.

Gambar 2.1 Solusi dari Sebuah VRP

Menurut Toth dan Vigo, karakteristik utama VRP berdasarkan komponen-

komponennya adalah sebagai berikut (Prana, 2007):

1. Jaringan jalan, biasanya direpresentasikan dalam sebuah graph (diagram)

yang terdiri dari arc (lengkung atau bagian-bagian jalan) dan vertex (titik

lokasi customer dan depot). Tiap lengkung diasosiasikan dengan biaya

(jarak) dan waktu perjalanan (tergantung jenis kendaraan, kondisi/

karakteristik jalan, dan periode perlintasan).

2. Customer (pelanggan), ditandai dengan vertex (titik) dan biasanya memiliki

hal-hal seperti berikut:

a. Jumlah permintaan barang (untuk dikirim ataupun diambil), jenis

barang dapat berbeda-beda.

b. Periode pelayanan tertentu (time windows), di luar rentang waktu

tersebut konsumen tidak dapat menerima pengiriman maupun

pengambilan.

c. Waktu yang dibutuhkan untuk menurunkan atau memuat barang

(loading/ unloading time) pada lokasi konsumen, biasanya tergantung

dari jenis kendaraan.

11

d. Pengelompokkan (subset) kendaraan yang tersedia untuk melayani

konsumen (sehubungan dengan keterbatasan akses atau persyaratan

permuatan dan penurunan barang).

e. Prioritas atau penalti sehubungan dengan kemampuan kendaraan

untuk melayani permintaan.

3. Depot, juga ditandai dengan suatu titik, merupakan ujung awal dan akhir

dari suatu rute kendaraan. Tiap depot memiliki sejumlah kendaraan

dengan jenis dan kapasitas tertentu yang dapat digunakan untuk

mendistribusikan produk.

4. Vehicle (kendaraan/ armada angkut), memiliki:

a. Depot asal, dan kemungkinan untuk mengakhiri rutenya di depot lain.

b. Kapasitas (berat, volume atau jumlah barang yang dapat diangkut).

c. Kemungkinan untuk dipisah menjadi beberapa kompartemen untuk

mengangkut barang dengan jenis yang berbeda-beda.

d. Alat yang tersedia untuk operasi (permuatan atau penurunan barang).

e. Pengelompokan (subset) lintasan/ lengkung dari diagram jaringan

jalan.

f. Biaya yang berhubungan dengan penggunaan kendaraan tersebut

(unit per jarak, unit per waktu, unit per rute, dan lainnya).

5. Pengemudi, memiliki kendala seperti jam kerja harian, jumlah dan jam

istirahat, durasi maksimum perjalanan, serta lembur yang biasanya juga

dikenakan pada kendaraan yang digunakan.

Dalam membuat konstruksi rute, terdapat beberapa kendala yang harus

dipenuhi, seperti jenis barang yang diangkut, kualitas dari pelayanan, juga

karakteristik konsumen dan kendaraan. Beberapa kendala operasional yang

sering ditemui misalnya:

1. Pada tipe rute, besar muatan yang diangkut oleh kendaraan tidak boleh

melebihi kapasitas kendaraan tersebut.

2. Kegiatan yang dilayani dalam sebuah rute hanya merupakan pengiriman

atau pengembalian, atau mungkin keduanya.

12

3. Konsumen mungkin hanya dapat dilayani dalam rentang waktu tertentu

(time windows) dan jam kerja dari pengemudi kendaraan yang

melayaninya.

4. Kendala prioritas juga mungkin akan timbul ketika suatu konsumen harus

dilayani sebelum konsumen lain. Kendala seperti ini biasanya terdapat

pada kasus pickup and delivery (pengambilan dan pengiriman dalam satu

rute) atau VRP with backhauls di mana pengambilan baru dapat dilakukan

setelah semua pengiriman selesai dikarenakan kesulitan dalam mengatur

peletakan muatan.

Menurut Toth dan Vigo, terdapat empat tujuan umum dalam VRP, yaitu

(Prana, 2007):

1. Meminimumkan biaya transportasi global, terkait dengan jarak dan biaya

tetap yang berhubungan dengan kendaraan.

2. Meminimumkan jumlah kendaraan yang dibutuhkan untuk melayani

semua konsumen.

3. Menyeimbangkan rute-rute dalam hal waktu perjalanan dan muatan

kendaraan.

4. Meminimumkan penalti akibat pelayanan yang kurang memuaskan

terhadap konsumen, seperti ketidaksanggupan melayani konsumen secara

penuh ataupun keterlambatan pengiriman.

2.2 Variasi Permasalahan VRP

Menurut Toth dan Virgo, ditemukan beberapa kelas atau variasi

permasalahan utama dalam VRP, yaitu (Prana, 2007):

1. Capacitated VRP (CVRP), merupakan kelas VRP yang paling sederhana

dan yang paling banyak dipelajari di mana kendala yang ada hanya

berupa kapasitas kendaraan yang terbatas.

2. Distance Constrained VRP (DCVRP), merupakan VRP dengan kendala

batasan panjang rute.

13

3. VRP with Time Windows (VRPTW), merupakan kasus VRP dengan setiap

konsumen memiliki batasan rentang waktu pelayanan.

4. VRP with Pick up and Delivery (VRPPD), merupakan VRP dengan

pelayanan campuran, yaitu pengiriman dan pengambilan barang dalam

satu rute.

5. VRP with Backhauls (VRPB), di mana pengambilan baru dapat dilakukan

setelah semua pengiriman selesai.

Dasar kelas atau variasi dalam VRP di atas membentuk keterkaitan satu

sama lain. VRP with Backhauls bisa jadi membutuhkan kondisi permasalahan

CVRP dalam pemecahan masalah. Banyaknya barang yang akan diambil pada

aktivitas VRPB tidak boleh melebihi kemampuan kapasitas vehicle. Begitu juga

untuk keterkaitan antar variasi permasalahan VRP lainnya yang ditunjukkan

pada Gambar 2.2.

Gambar 2.2 Permasalahan Dasar Kelas VRP dan Keterkaitannya (Prana, 2007)

2.3 Metode Penyelesaian VRP

Sebelumnya telah dijelaskan bahwa VRP dapat dianggap sebagai

kombinasi dari BPP dan TSP. Baik BPP dan TSP, keduanya dikategorikan

sebagai permasalahan NP-hard sehingga VRP juga dikategorikan sebagai NP-

hard yang mungkin belum ditemukan metode eksak untuk mencari nilai

optimalnya. Karena itu digunakan metode selain eksak untuk memecahkan VRP

berskala besar. Untuk VRP skala kecil dengan beberapa customer dan

14

homogeneous fleet (semua kendaraan mempunyai kapasitas yang sama), branch

and bound terbukti merupakan metode terbaik untuk mencari solusi optimal

(Pereira et.al, 2002). Kebanyakan penyelesaian untuk VRP berskala besar

menggunakan heuristic. Heuristic adalah algoritma yang berbasis kira-kira, yang

berusaha mencari solusi optimal secepat mungkin. Secara garis besar, metode

heuristic dapat dikategorikan menjadi dua bagian besar, yaitu heuristic klasik

yang berkembang antara tahun 1960 dan 1990, dan metaheuristic yang

berkembang mulai 1990.

Metode heuristic klasik dapat dikategorikan lagi menjadi tiga kategori,

yaitu Construction Method, Twophase method, dan Improvement methods (Laporte &

Semet, 1999). Metode metaheuristic jauh lebih efektif dibandingkan metode

heuristic klasik. Metode-metode metaheuristic menggabungkan Neighbourhood

Search, Memory Structure, dan Recombination pada tiap solusi untuk

menghasilkan solusi yang lebih baik (Gendreau et. al, 1999). Akan tetapi, waktu

proses yang dibutuhkan metaheuristic tidak dapat diketahui secara pasti, dan

biasanya lebih lama dibandingkan heuristic klasik. Selain itu metaheuristic juga

melibatkan lebih banyak parameter daripada heuristic klasik.

Selama satu dekade terakhir, setidaknya ada enam metode metaheuristic

untuk aplikasi VRP yang ditemukan, metode-metode tersebut adalah Simulated

Annealing (SA), Deterministic Annealing (DA), Tabu Search (TS), Ant Systems (AS),

Neural Network (NN), dan Algoritma Genetika (Gendreau et. al, 1999). Algoritma

SA, DA, dan TS bergerak dari satu solusi ke solusi lain yang merupakan

tetangganya, sampai memenuhi stopping criterion yang ditentukan. Algoritma

AS menggunakan mekanisme konstruktif untuk menciptakan beberapa solusi

pada tiap iterasi berdasarkan informasi yang didapat dari iterasi sebelumnya.

Algoritma NN adalah algoritma pembelajaran, serangkaian parameter secara

bertahap disesuaikan nilainya sampai memenuhi solusi yang sesuai keinginan.

Dan yang terakhir, algoritma AG yang mempertahankan sejumlah solusi-solusi

yang paling berkualitas, dan mengkombinasikannya untuk membentuk solusi

baru.

15

2.4 Heterogeneous Fleet VRP

Aplikasi VRP pada kehidupan nyata dapat ditemukan pada banyak

hal, seperti pada permasalahan pengaturan produk dari supplier kepada agen,

pengangkutan sampah, pengambilan surat pada kotak pos, pengaturan koran

pada para pelanggan, dan sebagainya (Eko, 2007). Tidak semua perusahaan

pengangkut sampah mempunyai armada yang sama persis, tidak semua loper

koran menggunakan kendaraan yang sama, dan tidak semua supplier

menggunakan jenis pengangkutan yang sama, bisa menggunakan kendaraan

darat, sepeda motor, mobil, truk, atau bahkan kapal laut dan pesawat terbang.

Permasalahan-permasalahan tersebut dapat diefisiensikan dengan dicari nilai

optimalnya menggunakan pemodelan VRP. Namun parameter-parameter dari

proses pengiriman barang tidak sesederhana itu. Pada aplikasinya, ada berbagai

konstrain tambahan yang harus dipertimbangkan, seperti biaya perjalanan yang

asimetris, depot yang lebih dari satu, jangka waktu pengiriman (misalnya pada

pengiriman makanan), adanya penjemputan barang selain pengiriman, dan

masih banyak lagi kemungkinan-kemungkinan lain yang spesifik pada aplikasi

tertentu.

2.5 Model Matematis Heterogeneous Fleet VRP

Kebanyakan pemodelan integer programming pada permasalahan VRP

klasik (Capacitated VRP) menggunakan variabel biner sebagai variabel yang

melambangkan rute vehicle, untuk mengindikasikan apakah sebuah vehicle

bergerak antara dua customer pada kondisi optimal. Formulasi ini pertama kali

diajukan oleh Garvin et al. (1957) untuk memodelkan sebuah permasalahan

pengaturan minyak, yang kemudian dikembangkan oleh Garvis dan Graves

(1982).

Gheysens et al. (1984) membuat formulasi menggunakan variabel biner

dengan tiga index Xijk sebagai aliran vehicle yang bernilai 1 jika sebuah vehicle

bertipe k melakukan perjalanan dari customer i ke customer j, dan 0 jika tidak. Di

samping itu ada variabel lain yaitu Yij melambangkan jumlah barang yang

16

dibawa ketika meninggalkan customer i menuju customer j. Formulasi matematis

Heterogeneous Fleet VRP secara lengkap dapat dilambangkan sebagai berikut

(Eko, 2007):

(F1) z(F1) = Min ∑ 𝐹𝑘𝑘∈𝑀 ∑ 𝑥0𝑗𝑘

𝑗∈𝑉′ + ∑ 𝑘∈𝑀 ∑ 𝑐𝑖𝑗𝑖,𝑗∈𝑉 𝑥𝑖𝑗𝑘 (2.1)

s.t. ∑ 𝑘∈𝑀 ∑ 𝑖∈𝑉 𝑥𝑖𝑗𝑘 = 1, ∀𝑗 ∈ 𝑉′ (2.2)

∑ 𝑥𝑖𝑝𝑘 𝑖∈𝑉 − ∑ 𝑗∈𝑉 𝑥𝑝𝑗

𝑘 = 0, ∀𝑝 ∈ 𝑉′, ∀𝑘 ∈ 𝑀 (2.3)

∑ 𝑥0𝑗𝑘 𝑗∈𝑉′ ≤ 𝑚𝑘

, ∀𝑘 ∈ 𝑀 (2.4)

∑ 𝑦𝑖𝑗 𝑖∈𝑉 − ∑ 𝑖∈𝑉 𝑦𝑗𝑖

= 𝑞𝑗, ∀𝑗 ∈ 𝑉′ (2.5)

𝑞𝑗 𝑥𝑖𝑗

𝑘 ≤ 𝑦𝑖𝑗 ≤ (𝑄𝑘 − 𝑞𝑖)𝑥𝑖𝑗𝑘 ,∀𝑖, 𝑗 ∈ 𝑉, 𝑖 ≠ 𝑗, ∀𝑘 ∈ 𝑀 (2.6)

𝑦𝑖𝑗 ≥ 0, ∀𝑖, 𝑗 ∈ 𝑉, 𝑖 ≠ 𝑗 (2.7)

𝑥𝑖𝑗𝑘 ∈ [0, 1], ∀𝑖, 𝑗 ∈ 𝑉, 𝑖 ≠ 𝑗, ∀𝑘 ∈ 𝑀 (2.8)

Fungsi konstrain (2.2) dan (2.3) pada formulasi memastikan tiap customer

hanya dikunjungi sekali saja, dan jika sebuah vehicle mengunjungi seorang

customer, dia juga harus berangkat meninggalkan customer tersebut. Jumlah

maksimal vehicle yang tersedia untuk setiap tipe vehicle dibatasi dengan konstrain

(2.4). Konstrain (2.5) merupakan konstrain pada arus item, di mana perbedaan

jumlah barang pada sebuah vehicle sebelum dan setelah mengunjungi suatu

customer harus sama dengan demand dari customer tersebut. Yang terakhir,

konstrain (2.6) memastikan bahwa jumlah barang yang dibawa sebuah vehicle

tidak boleh melebihi kapasitas maksimal dari vehicle tersebut.

2.6 Nearest Neighbor Algorithm

Nearest Neighbor Algorithm merupakan metode sederhana dalam

menyelesaikan suatu permasalahan dengan cara menghitung kedekatan antara

kasus baru dengan kasus lama, yaitu berdasarkan pada pencocokan bobot dari

sejumlah fitur yang ada (Aswar & Muriana, 2013). Contoh kasus seperti pada

solusi pencarian data seorang pasien baru di sebuah rumah sakit dengan

menggunakan informasi dari pasien terdahulu. Untuk mencari pasien mana

yang akan digunakan maka dihitung kedekatan kasus pasien baru dengan

17

semua kasus pasien lama. Kasus pasien lama dengan kedekatan terbesar yang

akan diambil untuk digunakan pada kasus pasien baru.

Metode Nearest Neighbor merupakan metode paling sederhana untuk

menyelesaikan masalah Travelling Salesman Problem yaitu dengan memilih salah

satu node yang mewakili suatu kota atau lokasi awal. Selanjutnya, pilih node

tujuan atau kota yang akan dikunjungi berikutnya, dengan pertimbangan hanya

memilih kota yang memiliki jarak terdekat dengan kota yang sebelumnya

dikunjungi. Kemudian, setelah seluruh kota dikunjungi atau seluruh node telah

terhubung, maka rute perjalanan ditutup dengan kembali ke kota asal (node asal).

Secara umum langkah-langkah dari metode ini dijabarkan sebagai berikut

(Aswar & Muriana, 2013):

1. Inisialisasi, hal pertama yang perlu dilakukan adalah menentukan nilai N

= {1, 2, 3, 4, …, n} sebagai jumlah kota atau lokasi yang akan dikunjungi.

Kemudian satu kota ditentukan secara sembarang sebagai titik awal

perjalanan (iº). V adalah sejumlah kota lain yang masih harus dikunjungi

serta S adalah urutan rute perjalanan saat ini. Pada langkah pertama, nilai

S dapat diartikan sama dengan (iº), karena belum ada kota lain yang

dikunjungi.

2. Pilih kota yang selanjutnya akan dikunjungi. Jika i1 adalah kota yang

berada di urutan terakhir dari rute S, kota berikutnya (j*) harus ditentukan

dari kota yang memiliki jarak paling minimal dengan i1 dan j* merupakan

anggota dari V. Apabila terdapat beberapa pilihan optimal, maka kota

dipilih secara acak.

3. Kota j* ditambahkan di urutan akhir dari rute sementara dan kota yang

terpilih diambil dari daftar kota yang belum dikunjungi.

4. Jika semua kota yang harus dikunjungi telah dimasukkan ke dalam rute

atau dapat diartikan V = 0, maka tidak ada lagi kota yang tertinggal.

Tahap selanjutnya, menutup rute dengan menambah kota inisialisasi atau

iº di akhir rute. Dengan kata lain, rute ditutup dengan proses kunjungan

kembali lagi ke kota asal.

18

Metode Nearest Neighbor banyak digunakan pada kasus TSP dikarenakan

metode ini merupakan salah satu metode yang memiliki karakteristik

pembentukan rute distribusi sesuai dengan keadaan nyata yang terdapat pada

kondisi di lapangan. Selain itu alasan penggunaan metode ini dikarenakan

teknik penentuan rute yang diterapkan pada metode ini lebih mudah dilakukan

dibandingkan dengan metode TSP yang lain. Metode Nearest Neighbor juga

merupakan metode yang dapat dijadikan sebagai dasar dalam pembuatan rute

distribusi sebelum melakukan proses optimalisasi rute dengan menggunakan

metode lain.

19

BAB 3

TRANSPORTASI KOMODITAS BUNGA KRISAN

3.1 Transportasi Komoditas

Transportasi komoditas merupakan komponen vital pada ranah ekonomi.

Transportasi ini mendukung aktivitas produksi, perdagangan, dan konsumsi

dengan jaminan ketersediaan waktu dan pergerakan yang efisien pada bahan

baku dan produk jadi. Perhitungan transportasi merupakan bagian signifikan

pada biaya akhir produk dan representasi komponen penting pada belanja

nasional suatu negara (Crainic dan Laporte, 1997). Salah satu produk yang

diangkut adalah bunga krisan sebagai komoditas perdagangan holtikultura

signifikan di Indonesia.

Perkembangan produksi krisan di Indonesia selama periode 2000-2011

terus mengalami peningkatan dengan rata-rata pertumbuhan 71,45% per tahun

(Gambar 3.1). Produksi krisan di Indonesia pada tahun 2000 dari hanya sebesar

2,28 juta tangkai meningkat menjadi 305,87 juta tangkai pada tahun 2011.

Kontribusi produksi krisan terbesar rata-rata tahun 2000-2011 diberikan oleh

Jawa sebesar 96,37%, sementara di Luar Jawa hanya memberikan kontribusi

produksi sebesar 3,63% dari total produksi krisan di Indonesia.

Secara umum perkembangan produktivitas krisan di Indonesia selama

periode 2000-2011 mengalami peningkatan dengan rata-rata pertumbuhan

sebesar 44,67% per tahun (Gambar 3.2). Pada tahun 2000 produktivitas krisan di

Indonesia sebesar 1,97 tangkai/m2 dan meningkat menjadi 34,71 tangkai/m2

pada tahun 2011 yang merupakan produktivitas tertinggi selama periode

tersebut. Pada tahun 2005 produktivitas krisan di Indonesia sempat mengalami

penurunan yang sangat drastis hingga mencapai 61,54% menjadi 6,90

tangkai/m2, dari sebesar 17,94 tangkai/m2 pada tahun 2004.

20

Gambar 3.1 Perkembangan Produksi Krisan, 2000-2011 (Dep. Pertanian, 2013)

Gambar 3.2 Perkembangan Produktivitas Krisan, 2000-2011 (Dep. Pertanian,

2013)

Secara umum kegiatan-kegiatan yang termasuk dalam industri bunga

krisan adalah awal pemesanan oleh konsumen pada produsen, pembuatan

kesepakatan antara pemasok dan pembeli, penyediaan pesanan, transportasi,

pendistribusian dan barang sampai di tangan konsumen. Masalah yang sering

timbul di dalam kegiatan tersebut adalah ketidakefisienan pada waktu dan

biaya. Barang yang dipesan sering tiba di tangan konsumen tidak tepat pada

waktu yang telah disepakati, atau jumlah yang diterima konsumen tidak tepat

sesuai dengan kesepakatan. Masalah-masalah ini sering menimbulkan

peningkatan biaya dalam pengiriman ulang barang kepada konsumen dan

penurunan kepercayaan produsen kepada produsen.

Permasalahan terjadi diakibatkan oleh sifat bunga krisan sebagai komoditas

mudah rusak (perishable). Selama pengangkutan sering terjadi penurunan

kualitas akibat pengaruh lamanya waktu pengangkutan terhadap perubahan

21

fisik maupun kimia bunga krisan tersebut. Sedangkan di sisi lainnya, semakin

banyak titik pelanggan yang dikunjungi dalam 1 (satu) rute transportasi, maka

semakin sedikit jumlah kendaraan angkut yang dibutuhkan sehingga akan

meminimumkan biaya transportasi walaupun secara aspek waktu akan

cenderung memperlambat waktu angkut sehingga cenderung akan menurunkan

aspek kualitas bunga krisan.

Penggunaan alat transportasi juga dapat menimbulkan kerugian terutama

bila terjadi kesalahan pemilihan jenis angkutan untuk pengiriman barang ke

konsumen. Apalagi jika pengiriman barang dilakukan dalam jumlah yang tidak

sedikit. Pemilihan jalur transportasi yang tepat juga perlu diperhatikan. Jika

tidak, maka akan terjadi peningkatan biaya transportasi atau biaya kerugian saat

pendistribusian.

Salah satu alternatif penyelesaian masalah tersebut, dapat digunakan

optimasi melalui pendekatan model transportasi Vehicle Routing Problem (VRP)

bunga krisan. VRP adalah sebuah model permasalahan optimasi kombinatorial

yang kompleks, yang didefinisikan sebagai pencarian cara penggunaan yang

efisien dari sejumlah kendaraan yang harus melakukan perjalanan untuk

mengunjungi sejumlah tempat untuk mengantar dan/ atau menjemput orang/

barang (Fisher, 1995). Setiap tujuan hanya boleh dilayani oleh satu kendaraan

saja. Hal ini dilakukan dengan mempertimbangkan kapasitas kendaraan dalam

satu kali angkut untuk meminimalkan biaya yang diperlukan. Biasanya

penentuan biaya minimal erat kaitannya dengan jarak yang minimal.

Permasalahan VRP klasik menganggap kapasitas tiap kendaraan yang

digunakan sama semua. Pada kenyataannya, sebuah perusahaan tidak selalu

mempunyai komposisi kendaraan yang sama sehingga metode penyelesaian

VRP klasik kurang mengena untuk diterapkan. Karena itu muncul varian metode

VRP klasik untuk menyelesaikan permasalahan VRP dengan komposisi

kendaraan yang berbeda, yang dikenal dengan Heterogeneous Fleet VRP. Lingkup

permasalahan VRP pada praktiknya sangat luas (dalam hal banyaknya jumlah

pelanggan), sehingga metode eksak tidak dapat digunakan untuk

22

menyelesaikannya. Penekanan penyelesaian permasalahan optimasi tersebut

akhirnya lebih ditekankan pada metode metaheuristik.

Selama satu dekade terakhir, setidaknya ada enam metode metaheuristik

untuk aplikasi VRP yang ditemukan, metode-metode tersebut adalah Simulated

Annealing (SA), Deterministic Annealing (DA), Tabu Search (TS), Ant Systems (AS),

Neural Network (NN), dan Algoritma Genetika (M. Gendreau, 1999). SA, DA, dan TS

bergerak dari satu solusi ke solusi lain yang merupakan tetangganya, sampai

memenuhi kriteria pemberhentian yang ditentukan. Algoritma AS menggunakan

mekanisme konstruktif untuk menciptakan beberapa solusi pada tiap iterasi

berdasarkan informasi yang didapat dari iterasi sebelumnya. Algoritma NN

adalah algoritma pembelajaran, serangkaian parameter secara bertahap

disesuaikan nilainya sampai memenuhi solusi yang diinginkan. Terakhir,

Algoritma Genetika (AG) mempertahankan sejumlah solusi-solusi yang paling

berkualitas, dan mengombinasikannya untuk membentuk solusi baru.

3.2 Profil Perusahaan (Depot)

PT. EDAR merupakan perusahaan agribisnis yang memproduksi berbagai

sayuran hidroponik maupun konvensional (Aswar & Muriana, 2013). Komoditi

produk perusahaan ini di antaranya adalah paprika, tomat recento, timun

jepang, berbagai jenis sayuran daun, berbagai jenis lettuce dan masih banyak

komoditi lain yang disediakan. Perusahaan ini juga mempunyai unit kerja

processing sayuran siap olah, di antaranya adalah lettuce, daun bawang, bawang

bombay, seledri dan lain-lain. Produk terbaru dari perusahaan ini adalah sayur

siap masak seperti sayur asem, sayur lodeh, mix salad dan lain-lain.

PT. EDAR didirikan pada tahun 1983, berlokasi di Bogor, Indonesia pada

ketinggian 670 meter di atas permukaan laut (mdpl) (Hermada, 2009). Pada

awalnya, perusahaan memulai dengan menanam melon di atas lahan terbuka

dengan beberapa staf dan beberapa karyawan harian. Daerah yang pertama kali

dijadikan lahan adalah daerah Sukamanah.

23

Tahun 1985 usaha mulai dikembangkan dengan menanam bawang putih

seluas 7 Ha di daerah Cipanas, Kab. Cianjur dan memperkerjakan karyawan

sebanyak 100 orang. Banyaknya petani lain yang juga membudidayakan bawang

putih membuat usaha tersebut kurang memberikan keuntungan sehingga

kemudian diputuskan untuk mengembalikan usahanya di sekitar desa

Sukamanah.

Perusahaan melakukan perubahan dalam pola usahanya dari cara

tradisional di lahan terbuka menjadi hidroponik dalam green house (rumah kaca).

Sistem irigrasi yang digunakan di dalam green house tersebut adalah drip

irrigation (irigasi tetes) yang digunakan untuk memproduksi paprika, cabe

jepang (shisito), timun jepang, tomat dan melon. Hasil percobaan teknik baru

tersebut menunjukkan hasil yang memuaskan yang membuat pimpinan

memutuskan untuk memperbesar usaha ini. Untuk itu pada akhir tahun 1991,

luas area green house diperlebar hingga mencapai 1,5 hektar.

Usaha penanaman sayur dalam green house perusahaan ini terus

berkembang. Melihat kondisi tersebut, maka pada tahun 1992 sebagai usaha

diverifikasi, mulai mengadakan percobaan untuk memproduksi stek krisan yang

sudah berakar (unrooted cutting), yang kemudian ditingkatkan kembali

produksinya dalam bentuk bunga pot. Hasil percobaan yang memuaskan

mendorong pembentukan divisi bunga dan mulai memproduksinya secara

komersial dan kontinyu.

3.3 Produk dan Armada Pengiriman (Vehicles)

PT. EDAR mendistribusikan produk bunga krisan dan sayur-sayuran

kepada konsumen menggunakan alat angkutan darat yang berpendingin untuk

menjaga kualitas bunga dan sayuran. Mutu bunga potong bergantung pada

penampilan dan daya tahan kesegarannya. Untuk mempertahankan mutu bunga

potong, perlu dilakukan beberapa perlakuan sejak bunga siap panen sampai tiba

di tangan konsumen. Salah satu tahap yang perlu diperhatikan adalah saat

pengangkutan.

24

Alat transportasi yang digunakan untuk melakukan pengiriman bunga

menggunakan mobil boks berpendingin dengan suhu rata-rata 8ºC. Selain itu

untuk menjaga kondisi bunga agar tetap baik maka bunga dikemas dengan

kertas porla lalu dilakukan pengepakan menggunakan karton dus (kardus) yang

cukup kuat sehingga tidak akan rusak saat disusun secara bertindihan di dalam

kendaraan. Spesifikasi kendaraan yang digunakan dijabarkan di dalam tabel 3.1.

Tabel 3.1 Spesifikasi Kendaraan Perusahaan

Kendaraan Nama Jumlah Kapasitas

(unit) (kardus) (batang)

1 Mobil boks L300 1 71 372000

2 Mobil boks engkle 6 131 678000

3 Mobil boks double 4 223 1152000

Besar kapasitas barang yang dapat diangkut didapat dari ukuran ruang

mobil boks. Berikut ini penjabaran volume masing-masing jenis mobil boks pada

tabel 3.2.

Tabel 3.2 Volume Kendaraan

Jenis Ukuran Ruang Dalam Kap. Ruang

Panjang (m) Lebar (m) Tinggi (m) (m3)

Mobil boks L300 2.30 1.50 1.1 3.80

Mobil boks enkle 2.94 1.57 1.5 6.92

Mobil boks double 4.07 1.7 1.7 11.76

Kapasitas mobil angkut mempengaruhi pemilihan dan penggunaan

jumlah vehicle yang optimal. Karakteristik masing-masing armada angkut yang

digunakan berbeda-beda seperti yang ditunjukkan pada Gambar 3.3.

Produk yang dikirim oleh perusahaan terdiri atas bunga potong, bibit

krisan unrooted cutting dan rooted cutting. Berdasarkan hasil pengamatan, hasil

penghitungan dan informasi dari berbagai sumber di mesin pencarian, kapasitas

angkut setiap kendaraan yang dimiliki perusahaan berbeda-beda. Ukuran tiap

produk krisan juga berbeda-beda sehingga untuk mendapatkan daya angkut

kendaraan yang tepat diasumsikan satuan kardus untuk bunga krisan berjenis

rooted cutting (batang stek berakar) dan bunga potong. Untuk produk unrooted

25

cutting, jumlah batang stek pada setiap kardus tidak seragam. Oleh karena itu,

untuk mendapatkan daya angkut kendaraan yang tepat maka digunakan satuan

batang.

(a) Mobil Boks L300 (b) Mobil Boks Double

(c) Mobil Boks Engkle

Gambar 3.3 Karakteristik Armada Pengiriman

Setiap pelanggan bunga memiliki daya beli yang relatif berbeda sehingga

kuantitas produk yang dibeli pun beragam. Oleh karena itu barang kiriman

untuk beberapa pelanggan yang berbeda dapat digabungkan dan dikirim dalam

satu kendaraan. Pelanggan-pelanggan yang pengiriman pesanannya

digabungkan dalam satu kendaraan merupakan pelanggan yang berdekatan

lokasinya, atau lokasi mereka terletak dalam jalan yang searah sehingga mudah

bagi pihak transportasi saat pendistribusian.

Penyusunan barang (bunga) ke dalam kendaraan sebelum didistribusikan

juga menjadi salah satu perhatian yang khusus untuk menjaga agar produk

tidak mengalami kerusakan saat pengiriman. Urutan pemasukan barang ke

dalam kendaraan disesuaikan dengan letak pelanggan yang bersangkutan.

Penyusunan dimulai dari pemasukan bunga untuk pelanggan yang terletak

paling jauh dari rute sampai ke rute terdekat.

26

3.4 Data Pelanggan (Customer)

Pembeli produk bunga krisan (customer/ pelanggan) di PT. EDAR berasal

dari berbagai daerah. Selain itu masing-masing pembeli melakukan pemesanan

dalam jumlah yang berbeda-beda. Total pembeli bunga krisan sampai Maret

2010 sebesar 41 pelanggan. Data customer diambil dari beberapa data yang

memiliki persentase pemesanan cukup sering atau dianggap sebagai pelanggan

tetap. Ini dilakukan untuk meminimalisir penggunaan data yang tidak tetap

dalam ruang lingkup aktivitas pendistribusian. Data yang tidak tetap adalah

data customer yang tidak pasti dalam melakukan pemesanan bunga krisan secara

berkala. Berikut ini data customer dan jumlah permintaan (demand) yang

dihimpun pada tabel 3.3.

Tabel 3.3 Daftar Customer (Pelanggan) PT. EDAR

No. Tujuan Demand

Kardus Batang

1 Bandara Soekarno-Hatta - 1.500.000

2 Cipanas 250 -

3 Jakarta 150 -

4 Serpong 100 -

5 Cikarang 75 -

Dari tabel 3.3 dapat dilihat jumlah permintaan setiap pelanggan berbeda-

beda dan satuan yang digunakan dalam jumlah permintaan ini adalah per

batang untuk produk jenis unrooted cutting dan kardus khusus untuk produk

bunga krisan jenis lainnya.

3.5 Lokasi Pelanggan (Rute)

Lokasi pendistribusian bunga krisan tersebar ke beberapa titik distribusi

di berbagai wilayah. Data jarak yang diperlukan untuk pengolahan adalah jarak

antara depot dengan titik distribusi (customer) dan jarak antar titik-titik distribusi

27

tersebut. Ilustrasi lokasi titik distribusi bunga krisan PT. EDAR dapat dilihat

pada Gambar 3.4.

Gambar 3.4 Peta Lokasi Depot dan Customer

Untuk mempermudah pengidentifikasian, digunakan pengkodean titik

distribusi berupa pengurutan nomor seperti pada gambar 3.4. Depot diberi

nomor 0 dan titik distribusi lain (customer) diberi nomor 1 sampai 5 sesuai

dengan jumlah customer. Pengukuran jarak antara dua titik dilakukan dengan

mengikuti alur jalan yang ada pada peta sehingga data jarak yang diperoleh

dapat mendekati jarak aktual yang ditempuh oleh vehicle (kendaraan).

Pengukuran jarak antar dua titik disesuaikan dengan rute yang memberikan

jarak terpendek. Pada pengumpulan data jarak ini, diasumsikan jarak tempuh

dari titik A ke titik B sama dengan jarak tempuh dari B ke titik A, sehingga jarak

yang dihasilkan akan simetris. Data jarak dari depot menuju titik distribusi dan

jarak antara titik-titik distribusi dituangkan dalam bentuk matriks jarak. Hasil

data jarak yang diperoleh digunakan sebagai dasar proses penghitungan

Algoritma Genetika.

28

BAB 4

PEMODELAN ALGORITMA GENETIKA

4.1 Pengolahan Data

Berbagai data riel pada bab 3 akan diproses secara manual menggunakan

konstruksi Algoritma Genetika. Tahap ini dilakukan untuk menghasilkan analisis

sistem secara keseluruhan, asumsi-asumsi, serta batasan-batasan sehingga

mempermudah perancangan aplikasi yang akan dibuat nantinya. Tahap

pengolahan data manual dimodelkan dalam bentuk flowchart pada gambar 4.1.

Gambar 4.1 Flowchart Proses Manual

4.2 Pemodelan Chromosome

Chromosome menyatakan salah satu solusi yang mungkin. Terdiri dari

kumpulan gen baik dalam bentuk biner, float maupun kombinatorial. Di dalam

chromosome berisi informasi banyaknya vehicle serta penugasan vehicle terhadap

tiap customer. Karena VRP merupakan permasalahan yang berkaitan dengan

rute, sebaiknya digunakan tipe chromosome yang non-repetitif. Oleh karena itu

chromosome yang terdiri dari angka-angka biner tidak dapat digunakan (Eko,

29

2007). Chromosome yang digunakan berisi angka-angka numerik di mana setiap

angkanya mewakili sebuah customer (gen). Visualisasi chromosome dapat dilihat

pada Gambar 4.2.

1 : 4 :

2 : 5 :

3 :

Gambar 4.2 Pengkodean Chromosome Untuk Permasalahan VRP

Hasil chromosome (rute) paling optimal yang telah dikenai proses

Algoritma Genetika akan diproses kembali untuk dipecah ke dalam beberapa sub

rute di mana tiap sub akan dilewati oleh vehicle yang ditentukan dari solusi

permasalahan HFVRP. Proses tersebut akan diolah dengan bantuan Nearest

Neighbor Algorithm.

4.2.1 Inisialisasi Populasi

Tahap inisialisasi populasi merupakan tahap pembangkitan populasi

awal secara random yang juga memperhatikan urutan node yang akan dilalui

vehicle dengan menyusun rute kunjungan dari titik depot ke titik kandidat

customer (gen) yang terdekat dan belum dikunjungi. Kemudian dari titik

customer yang terdekat tersebut, berangkat ke titik customer selanjutnya yang

paling terdekat sampai seluruh customer (gen) terlayani. Konsep tersebut diambil

dari bantuan metode pencarian solusi algoritma Nearest Neighbor karena pada

proses manual yang akan dijalani hanya akan dilakukan satu kali iterasi dan

menghasilkan populasi generasi pertama. Diharapkan inisialisasi awal yang

dihasilkan mendekati solusi optimal dan mempermudah pemrosesan manual

optimalisasi Algoritma Genetika. Iterasi harus dilakukan berkali-kali agar

menghasilkan banyak generasi untuk mendapatkan solusi yang paling optimal

sesuai dengan konsep Algoritma Genetika pada umumnya.

4 1 3 5 2 3 5 1 4 2

2 5 1 3 4 2 4 5 1 3

4 2 5 1 3

30

Inisialisasi populasi awal ditunjukkan pada tabel 4.1 dengan

menggunakan popsize = 5 di mana akan menghasilkan 5 buah parent yang hanya

muncul tepat 1 dari masing-masing node. Setiap parent memiliki 5 buah node

(gen) sesuai dengan jumlah customer yang akan dikunjungi vehicle.

Tabel 4.1 Inisialisasi Awal

Parent Ke- Chromosome Keterangan

P1 4 1 3 5 2 Serpong-Bandara-Jakarta-Cikarang-Cipanas

P2 2 5 1 3 4 Cipanas-Cikarang-Bandara-Jakarta-Serpong

P3 4 2 5 1 3 Serpong-Cipanas-Cikarang-Bandara-Jakarta

P4 3 5 1 4 2 Jakarta-Cikarang-Bandara-Serpong-Cipanas

P5 2 4 5 1 3 Cipanas-Serpong-Cikarang-Bandara-Jakarta

4.2.2 Evaluasi

Fungsi evaluasi akan menghasilkan suatu nilai yang disebut sebagai fitness

value. Hasil nilai tersebut dapat mengukur kualitas dari suatu chromosome (yang

mewakili sebuah solusi). Nilai fitness dilihat dari total jarak yang harus ditempuh

vehicle dalam sebuah solusi rute. Pada kasus ini, semakin rendah nilai fitness atau

total jarak yang ditempuh, maka solusi semakin baik. Ini dikarenakan jarak

tempuh vehicle semakin minim yang akan berbanding lurus dengan biaya yang

harus dikeluarkan vehicle untuk melakukan aktivitas distribusi.

Evaluasi bukan hanya memproses inisialisasi solusi awal, namun juga

memproses solusi akhir berupa chromosome yang dihasilkan dari porses

optimalisasi Algoritma Genetika nantinya. Semua solusi hasil seleksi, crossover,

dan mutasi akan dijadikan satu dalam tabel evaluasi sebagai individu-individu

terbaik. Untuk fitness value dari populasi awal yang telah dibentuk pada tahap

inisialisasi populasi sebelumnya, ditunjukkan pada tabel 4.2.

Tabel 4.2 Evaluasi Fitness Value Populasi Awal

Parent Inisialisasi Populasi Fitness (i)

P1 0 - 4 - 1 - 3 - 5 - 2 - 0 339

P2 0 - 2 - 5 - 1 - 3 - 4 - 0 391

P3 0 - 4 - 2 - 5 - 1 - 3 - 0 468

P4 0 - 3 - 5 - 1 - 4 - 2 - 0 353

P5 0 - 2 - 4 - 5 - 1 - 3 - 0 388

31

Summary 1939

Average 387.8

Minimum 339

4.2.3 Seleksi

Tahap seleksi (selection) merupakan proses pemilihan beberapa

chromosome dari keseluruhan populasi untuk dikenai operasi-operasi Algoritma

Genetika lainnya. Metode selection yang digunakan pada kasus ini adalah Roulette

Wheel Selection. Menggunakan teknik Roulette Wheel, berarti pemilihan individu

dilakukan berdasarkan pengaruh nilai fitness-nya. Individu dengan nilai fitness

terendah berarti individu yang baik dan akan memiliki peluang yang lebih besar

untuk terpilih.

Tabel 4.3 Proses Selection Populasi Awal

Parent Inisialisasi Fitness Inverse Probabilitas Persentase Expected Actual

Populasi (i) (i) (i) Probabilitas Count Count

P1 0-4-1-3-5-2-0 339 0.00295 0.226 22.6 1.130 2

P2 0-2-5-1-3-4-0 391 0.00256 0.196 19.6 0.980 0

P3 0-4-2-5-1-3-0 468 0.00214 0.164 16.4 0.818 0

P4 0-3-5-1-4-2-0 353 0.00283 0.217 21.7 1.085 2

P5 0-2-4-5-1-3-0 388 0.00258 0.197 19.7 0.987 0

Summary 1939 0.01305 1.000 100.0 5.000

Average 387.8 0.00261 0.200 20.0 1.000

Maximum 339 0.00295 0.226 22.6 1.130

Dari tabel 4.3, nilai fitness masing-masing chromosome didefinisikan dari

jarak total sebuah rute. Hasil fitness value terkecil mempunyai kemungkinan

terpilih besar atau mempunyai nilai probabilitas yang tinggi. Untuk itu

dilakukan pencarian inverse berupa kebalikan nilai fitness (1/ fitness value) untuk

menyatakan probabilitas suatu solusi P[i] = inverse[i]/ total_inverse. Kemudian

nilai probabilitas diubah dalam bentuk persentase sehingga didapat range

masing-masing chromosome dari angka 1 sampai 100. Expected count

menggambarkan gagasan parent yang akan dikenai proses crossover dan mutasi

di mana expected count = inverse[i]/ avg_inverse. Actual count menyatakan jumlah

parent yang akan dikenai proses crossover. Dilihat dari besar nilai probabilitas

32

dan expected count yang melebihi rata-rata nilai keseluruhan individu, parent P1

dan P4 terpilih untuk dikenai proses crossover. Parent P1 disilangkan dengan P4

dan begitu juga berlaku sebaliknya, sehingga P1 dan P4 akan mengalami 2 kali

proses seleksi yang dinyatakan oleh nilai actual count = 2. Hasil seleksi

membentuk populasi baru untuk digunakan pada proses crossover yang

digambarkan pada tabel 4.4. Tanda panah pada tabel menunjukkan keterkaitan

antar dua parent yang akan dikenai proses persilangan.

Tabel 4.4 Hasil Selection Populasi Awal

Parent Inisialisasi Fitness Inverse Probabilitas Persentase

Populasi (i) (i) (i) Probabilitas

P1 0-4-1-3-5-2-0 339 0.00295 0.255 25.5

P4 0-3-5-1-4-2-0 353 0.00283 0.245 24.5

P4 0-3-5-1-4-2-0 353 0.00283 0.245 24.5

P1 0-4-1-3-5-2-0 339 0.00295 0.255 25.5

Summary 1384 0.01157 1.000 100.0

Average 346 0.00289 0.250 25.0

Maximum 339 0.00295 0.255 25.5

4.2.4 Crossover

Tahap ini melibatkan dua parent yang diambil dari hasil selection tahap

sebelumnya untuk membentuk suatu chromosome baru. Crossover tidak selalu

dilakukan pada semua gen yang ada. Hanya gen yang terpilih secara acak yang

akan dikenai proses ini. Individu yang akan mengalami operator crossover adalah

parent yang dihasilkan pada proses selection yaitu P1 dan P4. Metode crossover

yang dipilih pada kasus ini adalah Partial-Mapped Crossover (PMX). Metode ini

diciptakan oleh Goldberg dan Linle yang merupakan rumusan modifikasi dari

crossover dua-poin. Hal penting dari PMX adalah pindah silang 2-poin ditambah

dengan beberapa prosedur tambahan.

Prosedur PMX meliputi :

1. Penentuan dua posisi pada kromosom dengan aturan acak. Substring

yang berada dalam dua posisi ini dinamakan daerah pemetaan.

2. Penukaran dua substring antar induk untuk menghasilkan proto-child.

33

3. Penentuan hubungan pemetaan di antara dua daerah pemetaan.

4. Penentuan chromosome keturunan yang mengacu pada hubungan

pemetaan.

Penentuan dua titik posisi pada chromosome dengan aturan acak pada

permasalahan optimalisasi ini dipilih daerah pemetaan antara gen ke-3 dan ke-4

yang akan dilakukan persilangan. Berikut ini penjabaran masing-masing proses

ke-2 chromosome yang akan dikenai proses crossover.

Chromosome[1] = Chromosome[1] >< Chromosome[4]

Chromosome[4] = Chromosome[4] >< Chromosome[1]

1. Chromosome[1] >< Chromosome[4]

Parent 1

Parent 2

Penggunaan chromosome pada proses crossover tanpa mengikutsertakan

gen depot (0), susunan chromosome hanya mengambil gen dari customer (1-

5).

Penukaran substring antar parent

Proto-child 1

Proto-child 2

Proto-child merupakan susunan chromosome hasil persilangan substring

antar 2 parent. Substring pada proto-child 1 adalah 1 dan 4, gen 1 berada di

posisi ke-3 dan gen 4 berada di posisi ke-4 pada sebuah susunan

chromosome, sesuai dengan 2 titik posisi yang telah ditentukan secara

random sebelumnya.

Menentukan hubungan mapping

1-3 1 3

4-5 4 5

Susunan chromosome pada tahap proto-child masih terjadi duplikasi gen,

sehingga dibutuhkan proses normalisasi perubahan gen di luar daerah

4 1 3 5 2

3 5 1 4 2

4 1 1 4 2

3 5 3 5 2

34

pemetaan dengan menentukan hubungan mapping pada kedua parent.

Pertama untuk gen pada substring proto-child1 yaitu 1 dan 3, gen 1 yang

berada di luar daerah substring akan diubah menjadi 3. Begitu juga jika

ditemukan gen 3 di luar substring, maka gen akan berubah menjadi 1.

Hal ini juga berlaku pada proto-child2. Hasil proses ini akan membentuk

susunan chromosome child.

Menentukan child yang mengacu pada hubungan mapping

Child 1

Child 2

Proses persilangan antara parent 1 dan 4 menukarkan daerah pemetaan

yaitu gen yang terletak pada posisi 3 dan 4 dari kedua chromosome

sehingga menghasilkan susunan chromosome baru seperti pada child 1 dan

2. Dari proses ini didapat susunan chromosome child[1] yaitu 0-5-3-1-4-2-0.

2. Chromosome[4] >< Chromosome[1]

Parent 1

Parent 2

Penukaran substring antar parent

Proto-child 1

Proto-child 2

Menentukan hubungan mapping

3-1 3 1

5-4 5 4

Menentukan child yang mengacu pada hubungan mapping

Child 1

Child 2

5 3 1 4 2

1 4 3 5 2

3 5 1 4 2

4 1 3 5 2

3 5 3 5 2

4 1 1 4 2

1 4 3 5 2

5 3 1 4 2

35

Persilangan antara parent 4 dan 1 juga diproses dengan teknik yang sama

seperti persilangan sebelumnya, menghasilkan susunan chromosome baru

child 1 dan child 2 dengan menukarkan daerah pemetaan (gen di posisi

titik 3 dan 4) dari kedua parent. Dari proses ini didapat susunan

chromosome child[2] yaitu 0-1-4-3-5-2-0.

Semua chromosome hasil proses crossover yang telah didapat dari kedua

bagian proses sebelumnya kemudian dimasukkan ke dalam tabel yang

membentuk populasi baru seperti pada tabel 4.5.

Tabel 4.5 Populasi Hasil Proses Crossover

Parent Inisialisasi

Child Inisialisasi Fitness Inverse Probabilitas Persentase

Populasi Child (i) (i) (i) Probabilitas

P1 0-4-1-3-5-2-0 C1 0-5-3-1-4-2-0 344 0.00291 0.254 25.4

P4 0-3-5-1-4-2-0

353 0.00283 0.247 24.7

P4 0-3-5-1-4-2-0 C2 0-1-4-3-5-2-0 361 0.00277 0.242 24.2

P1 0-4-1-3-5-2-0

339 0.00295 0.257 25.7

Summary 1397 0.01146 1.000 100.0

Average 349.3 0.00286 0.250 25.0

Maximum 339 0.00295 0.257 25.7

Populasi hasil persilangan pada tabel 4.5 menunjukkan chromosome atau

rute terbaik yaitu pada parent P1 dengan persentase probabilitas sebesar 25.7%.

C (child) merupakan inisialisasi untuk parent yang telah dikenai proses crossover.

Nilai probabilitas pada hasil proses crossover di atas memberi perubahan

signifikan di mana hasil probabilitas C1 meningkat optimal dibandingkan parent

P1 pada inisialisasi populasi awal yang belum dikenai proses persilangan

dengan probabilitas sebesar 22.6%.

4.2.5 Mutasi

Seperti pada operator crossover, proses mutasi juga dirancang untuk

digunakan pada suatu masalah yang spesifik sehingga tidak setiap proses mutasi

36

dapat diterapkan pada suatu masalah yang akan diselesaikan. Teknik mutasi

yang dipilih juga harus sesuai dengan teknik encoding yang digunakan.

Pada kasus ini, skema mutasi yang digunakan adalah swapping mutation.

Jumlah chromosome yang mengalami mutasi dalam satu populasi ditentukan oleh

parameter mutation rate (ρm). Parameter mutation rate (ρm) pada kasus ini

diambil sebesar 10% (0.1) sesuai rekomendasi penentuan parameter kontrol

Algoritma Genetika, jika fitness dari individu terbaik dipantau pada setiap

generasi, maka ukuran populasi dan mutation rate yang digunakan sebesar

(popsize; ρm) = (80; 0.1).

Jumlah gen yang akan dimutasi adalah perkalian antara mutation rate

dengan jumlah gen dalam satu populasi (0.1*25 = 2.5 = 2). Dua buah gen akan

dimutasi pada kasus ini.

Posisi gen mana saja yang akan dimutasi didapat dari pembangkitan

bilangan acak antara 1 sampai panjang_total_gen (1 – (5*5)) yaitu 1 sampai 25.

Bilangan acak dibangkitkan dengan menggunakan Microsoft Excel dengan fungsi

= RANDBETWEEN(1, 25) di mana fungsi ini akan membangkitkan bilangan

acak dari 1 sampai 25. Hasil pembangkitan bilangan acak dapat dilihat pada

Gambar 4.3.

Gambar 4.3 Pembangkitan Bilangan Acak 1 Sampai 25

Dari pembangkitan bilangan acak pada gambar 4.3 didapat 2 titik gen

yang akan terkena proses mutasi adalah pada posisi ke-3 dan ke-13. Dalam

proses mutasi, populasi yang digunakan adalah dari hasil proses crossover

sebelumnya. Proses mutasi dilakukan dengan cara menukar gen pada posisi

yang dipilih secara acak (3 dan 13) dengan gen sesudahnya. Jadi untuk gen

posisi ke-3 yaitu 1 bertukar posisi dengan gen ke-4 yaitu 4. Begitu juga dengan

37

gen pada posisi ke-13 yaitu 5 ditukar dengan gen posisi setelahnya yaitu 1. Jika

posisi gen berada di akhir chromosome, maka ditukar dengan gen yang pertama.

Hasil proses mutasi ditampilkan pada tabel 4.6.

Tabel 4.6 Hasil Proses Mutation

Parent Inisialisasi Titik Parent Chromosome Fitness Inverse Probabilitas Persentase

Populasi Mutasi Mutasi Baru (i) (i) (i) Probabilitas

C1 0-5-3-1-4-2-0 3 PM1 0-5-3-4-1-2-0 367 0.00272 0.214 21.4

P2 0-2-5-1-3-4-0

391 0.00256 0.201 20.1

P3 0-4-2-5-1-3-0 13 PM2 0-4-2-1-5-3-0 472 0.00212 0.166 16.6

C2 0-1-4-3-5-2-0

361 0.00277 0.217 21.7

P5 0-2-4-5-1-3-0

388 0.00258 0.202 20.2

Summary 1979 0.01275 1.000 100.0

Average 395.8 0.00255 0.200 20.0

Maximum 361 0.00277 0.217 21.7

Pada tabel 4.6, parent C1 dan P3 dikenai proses mutasi dan menghasilkan

susunan rute yang berbeda dari sebelumnya. PM merupakan inisialisasi untuk

parent yang telah dikenai proses mutasi. Hasil fitness kedua parent tidak

menunjukkan value optimal jika dibandingkan dengan chromosome hasil

persilangan sebelumnya. Nilai fitness yang meningkat menunjukkan probabilitas

atau kemungkinan kecil individu untuk terpilih. Meskipun chromosome hasil

mutasi tidak memiliki nilai fitness yang optimal, ada kemungkinan chromosome

tersebut tetap dimasukkan ke dalam populasi. Proses ini diperlukan untuk

memperkaya populasi dengan berbagai variasi chromosome yang berakibat

memperlebar ruang pencarian dan mendapatkan hasil yang lebih optimal.

4.2.6 Proses Elitisme

Operator crossover dan mutasi merupakan proses penting Algoritma

Genetika di mana menghasilkan beberapa chromosome baru dengan value beragam

yang diharapkan menghasilkan sebuah nilai paling optimal. Tahap elitisme ini

bertujuan untuk mempertahankan chromosome dari inisialisasi populasi awal

dengan menyertakan kembali pada populasi baru hasil proses Algoritma Genetika.

Secara teori, tahap elitisme dapat meningkatkan kemampuan dari Algoritma

38

Genetika karena mempertahankan chromosome yang baik pada populasi awal.

Namun kadang tahap ini juga dapat menyebabkan konvergensi prematur karena

nilai fitness terjebak pada optimum lokal.

Setelah melewati proses crossover dan mutasi pertama, chromosome hasil

kedua proses tersebut dan chromosome terbaik disalin ulang dan disimpan pada

tabel evaluasi, begitu seterusnya sampai nilai terbaik keseluruhan diperoleh.

Chromosome pada tabel evaluasi tidak akan mengalami proses crossover dan

mutasi, sehingga chromosome terbaik dapat dipertahankan pada tiap iterasi.

Pada proses penghitungan manual ini, pencarian solusi optimal diproses

hanya sampai 1 kali iterasi (generasi pertama). Untuk memperkaya hasil

perhitungan, iterasi dilakukan berkali-kali untuk menghasilkan keberagaman

solusi. Populasi yang terbentuk dari hasil proses manual Algoritma Genetika pada

generasi pertama ditunjukkan pada tabel 4.7.

Tabel 4.7 Hasil Populasi Generasi Pertama Pada Tabel Evaluasi

Parent Inisialisasi Fitness Inverse Probabilitas Persentase

Populasi (i) (i) (i) Probabilitas

P1 0-4-1-3-5-2-0 339 0.00295 0.125 12.5

P2 0-2-5-1-3-4-0 391 0.00256 0.108 10.8

P3 0-4-2-5-1-3-0 468 0.00214 0.091 9.1

P4 0-3-5-1-4-2-0 353 0.00283 0.120 12.0

P5 0-2-4-5-1-3-0 388 0.00258 0.109 10.9

C1 0-5-3-1-4-2-0 344 0.00291 0.123 12.3

C2 0-1-4-3-5-2-0 361 0.00277 0.118 11.8

PM1 0-5-3-4-1-2-0 367 0.00272 0.116 11.6

PM2 0-4-2-1-5-3-0 472 0.00212 0.090 9.0

Summary 3483 0.02357 1.000 100.0

Average 387 0.00262 0.111 11.1

Maximum 339 0.00295 0.125 12.5

Seperti pada pembahasan sebelumnya, individu terbaik dari sebuah

populasi pada kasus ini dipilih dari fitness terendah dengan hasil probabilitas

tertinggi. Tabel 4.7 merupakan tabel evaluasi generasi pertama yang berisi

penggabungan chromosome inisialisasi populasi awal dan chromosome yang

dikenai proses Algoritma Genetika. Hasil rute terbaik paling optimal untuk kasus

39

pendistribusian bunga krisan dari iterasi pertama ini pada parent 1 (0-4-1-3-5-2-0)

yaitu rute dari mulai Depot–Serpong–Bandara–Jakarta–Cikarang–Cipanas–

sampai kembali ke Depot. Ilustrasi rute optimal pendistribusi bunga krisan PT.

EDAR dapat dilihat pada Gambar 4.4.

Gambar 4.4 Hasil Rute Optimal Pendistribusian Bunga Krisan Generasi Pertama

4.3 Pergantian Populasi

Prosedur pergantian dilakukan dengan membentuk populasi baru yang

diambil dari hasil crossover dan mutasi serta ditambah chromosome hasil elitisme.

Populasi pada generasi sebelumnya yang merupakan parent diganti seluruhnya

dengan populasi baru yang merupakan anak atau turunannya (offspring).

Pergantian populasi diharapkan dapat memperkaya keberagaman solusi seperti

yang telah dibahas sebelumnya di mana iterasi sebaiknya dilakukan berkali-kali.

Proses tahapan Algoritma Genetika akan berlaku sama untuk generasi berikutnya

dan untuk tiap generasi. Penghitungan dilakukan hingga mencapai generasi

paling maksimum sehingga didapat chromosome terbaik dari seluruh generasi

sebagai solusi permasalahan.

40

BAB 5

SOLUSI MASALAH ALAT ANGKUT YANG BERBEDA

5.1 Permasalahan Alat Angkut Berbeda

Selain mencari rute optimal pendistribusian produk ke konsumen,

pemilihan armada kendaraan untuk mengirim produk ke pelanggan juga

menjadi salah satu kendala penting dalam model permasalahan pendistribusian

bunga krisan. Kendala yang dimaksud yaitu permasalahan kapasitas kendaraan

angkut yang berbeda jenis (Heterogeneous Fleet VRP). Penyelesaian tahap ini

menggunakan bantuan algoritma Nearest Neighbor dalam memilih jenis dan

meminimalkan jumlah kendaraan yang beroperasi dalam kegiatan distribusi.

Pada proses penyelesaian permasalahan ini tetap membutuhkan data rute

pendistribusian optimal yang diambil dari proses optimalisasi rute Algoritma

Genetika sebelumnya.

Berdasarkan urutan rute optimal tersebut, berangkat dari depot menuju

customer, muatan kendaraan disesuaikan dengan permintaan dari tiap customer

yang akan dilalui. Kendaraan akan berhenti melakukan pendistribusian pada

suatu customer ketika muatan yang diangkut kurang dari permintaan untuk

customer selanjutnya. Kemudian mengurangi barang yang diangkut ketika

berangkat dari depot dengan jumlah muatan yang tersisa ketika meninggalkan

customer terakhir. Ketika muatan sudah kosong saat customer terakhir, maka

kendaraan kembali ke depot. Langkah tersebut akan diimplementasikan pada

masing-masing kendaraan sampai seluruh customer terlayani.

Pemasok bunga krisan (PT. EDAR) memasok bunga krisan ke lima daerah

pengiriman yaitu Bandara, Cipanas, Jakarta, Serpong dan Cikarang dengan jenis

dan kuantitas permintaan produk yang berbeda pada tiap daerah. Dengan

perbedaan jenis dan kuantitas pemesanan bunga krisan yang dipesan (batang

dan kardus), proses penyelesaian permasalahan ini dibagi ke dalam dua kasus

seperti pada tabel 5.1.

41

Tabel 5.1 Demand Produk Krisan yang Dikirim Pemasok

No. Tujuan Demand Keterangan

1 Bandara Soekarno-Hatta 1.500.000 Batang Kasus 1

2 Cipanas 250 Kardus

Kasus 2 3 Jakarta 150 Kardus

4 Serpong 100 Kardus

5 Cikarang 75 Kardus

Pembagian kasus pada tabel 5.1 didasari karena perbedaan satuan

kuantitas permintaan bunga masing-masing daerah yang dapat berpengaruh

terhadap penghitungan kapasitas vehicle yang dibutuhkan. Pada kasus pertama,

satuan yang digunakan adalah batang karena dapat mewakili kapasitas

kendaraan yang sebenarnya. Hal ini disebabkan oleh perbedaan ukuran batang

stek, sehingga jika menggunakan satuan kardus maka tidak mewakili kapasitas

kendaraan sebenarnya. Berikut ini akan dilakukan proses manual penyelesaian

permasalahan HFVRP yang dibagi menjadi dua kasus seperti pada tabel 5.1.

A. Kasus 1

Proses manual yang dibahas pada kasus pertama ini mengenai

pendistribusian bunga krisan ke customer tujuan Bandara Soekarno-Hatta. PT.

EDAR mengirim produk ke Bandara berupa bunga krisan unrooted cutting

berjumlah 1.500.000 batang. Armada angkut yang dapat digunakan sebagai alat

distribusi yaitu satu unit mobil boks L300, enam unit berjenis engkle dan empat

unit jenis double dengan kapasitas masing-masing 372.000, 678.000, 1.152.000

batang yang selengkapnya dapat dilihat pada tabel 5.2. Untuk pengerjaan proses

manual pada kasus pertama ini terbagi ke dalam beberapa iterasi yang akan

dijabarkan pada tabel 5.2, tabel 5.3 dan tabel 5.4.

Tabel 5.2 Proses Iterasi Mobil Boks L300 Kapasitas 372.000 Batang

Keterangan Demand (batang)

Kapasitas Muatan Lebih

Feasible

Langkah ke-1 1 unit mobil boks L300 Kapasitas total = 372.000

1.500.000 - Tidak

42

Pada tabel 5.2 diperoleh bahwa pendistribusian bunga krisan ke bandara

tidak feasible jika menggunakan kendaraan jenis L300. PT. EDAR hanya memiliki

1 unit kendaraan, sehingga iterasi hanya sampai pada langkah pertama dengan

kapasitas vehicle hanya 372.000 batang. Sedangkan jumlah permintaan lebih besar

dari muatan yang dapat diangkut vehicle pada jenis ini. Kemudian dilakukan

iterasi berikutnya pada mobil boks berjenis engkle yang dijabarkan pada tabel 5.3.

Tabel 5.3 Proses Iterasi Mobil Boks Engkle Kapasitas 678.000 Batang

Keterangan Demand (batang)

Kapasitas Muatan Lebih

Feasible

Langkah ke-1 1 unit mobil boks engkle Kapasitas total = 678.000

1.500.000 - Tidak

Langkah ke-2 Mobil boks engkle & L300 Kapasitas total = 1.050.000

1.500.000 - Tidak

Hasil iterasi pada tabel 5.3 juga menunjukkan bahwa pendistribusian

bunga krisan ke bandara dengan menggunakan mobil boks berjenis engkle tidak

optimal karena kapasitas antara daya angkut vehicle dengan permintaan tidak

mencukupi. Perusahaan memiliki enam unit kendaraan, namun pada kasus ini,

penggunaan kendaraan yang berjenis sama dibatasi hanya maksimal satu unit.

Penggunaan kendaraan yang berjenis sama dengan jumlah banyak hanya untuk

pendistribusian ke sebuah daerah akan menghabiskan biaya yang besar sehingga

tidak optimal dan berbanding terbalik dengan tujuan penelitian ini. Langkah

iterasi selanjutnya pada mobil boks berjenis double yang ditunjukkan pada tabel

5.4.

Tabel 5.4 Proses Iterasi Mobil Boks double Kapasitas 1.152.000 Batang

Keterangan Demand (batang)

Kapasitas Muatan Lebih

Feasible

Langkah ke-1 1 unit mobil boks double Kapasitas total = 1.152.000

1.500.000 - Tidak

Langkah ke-2 Mobil boks double & L300 Kapasitas total = 1.050.000

1.500.000 24.000 Ya

Langkah ke-3 1.500.000 330.000 Ya

43

Mobil boks double & engkle Kapasitas total = 1.830.000

Dari tabel 5.4 diperoleh hasil optimal untuk kasus pendistribusian bunga

krisan ke bandara dengan menggunakan mobil boks berjenis double yang

ditunjukkan pada langkah ke-2 dan ke-3. Kapasitas kendaraan terhadap

banyaknya permintaan customer mencukupi bahkan melebihi muatan.

Perusahaan memiliki 4 unit kendaraan untuk jenis mobil boks double.

Langkah ke-2 merupakan langkah paling optimal karena kelebihan muatan pada

kendaraan mendapat value minimum sebesar 24.000. Semakin kecil kelebihan

muatan pada kendaraan menjadi semakin optimal karena tidak membuang

banyak kelebihan muatan secara sia-sia, terutama karena pendistribusian hanya

terpusat pada satu daerah saja. Dapat disimpulkan untuk pendistribusian bunga

krisan ke Bandara Soekarno-Hatta menggunakan 1 unit mobil boks berjenis L300

dan 1 unit mobil boks double.

PT. EDAR hanya memiliki 1 unit mobil boks berjenis L300 dan karena

pada kasus pendistribusian ke customer daerah Bandara sudah menggunakan

kendaraan jenis ini, mobil boks tipe L300 tidak dapat dimasukkan ke daftar

proses iterasi untuk kasus kedua.

B. Kasus 2

Proses manual yang dibahas pada kasus kedua ini mengenai

pendistribusian bunga krisan ke customer tujuan Cipanas, Jakarta, Serpong dan

Cikarang. Jenis bunga krisan yang dikirim adalah jenis bunga potong dan bibit

krisan rooted cutting.

Armada angkut yang dapat digunakan sebagai alat distribusi pada kasus

ini yaitu enam unit berjenis engkle dan tiga unit jenis double. Seperti pada

pembahasan sebelumnya, berbeda dari kasus pertama, pada kasus ini kapasitas

vehicle dihitung dalam satuan kardus dengan ukuran masing-masing 131 kardus

untuk jenis mobil boks engkle dan 223 kardus untuk jenis mobil boks double.

Langkah pengerjaan proses manual pada kasus ini sama seperti pembahasan

pada kasus pertama yang akan dijabarkan pada tabel 5.5.

44

Tabel 5.5 Proses Penentuan Vehicle Untuk Daerah Serpong

Customer Demand (kardus)

Kapasitas Muatan Lebih

Feasible

a. Langkah 1, Mobil Boks Engkle

Serpong 100 31 Ya

Jakarta 150 - Tidak

b. Langkah 2, Mobil Boks Engkle

Serpong 100 31 Ya

Tabel 5.5 merupakan langkah pemilihan vehicle untuk kunjungan pada

customer pertama yaitu Serpong. Vehicle yang digunakan untuk kunjungan ke

daerah Serpong berupa mobil boks engkle yang memiliki kapasitas daya angkut

lebih besar dari banyaknya permintaan.

Seperti yang telah dibahas sebelumnya mengenai metode Algoritma

Nearest Neighbor, selain kapasitas vehicle, permintaan customer lain yang berada di

node terdekat juga perlu diperhatikan. Daerah Jakarta (daerah kunjungan

berikutnya setelah daerah Serpong) memiliki demand lebih besar dari kapasitas

sisa vehicle seperti yang ditunjukkan pada langkah pertama tabel 5.5. Oleh karena

itu, langkah kedua pada tabel adalah menetralkan penghitungan yang tidak

feasible di mana kunjungan mobil boks engkle hanya feasible untuk daerah

Serpong. Demikian halnya dengan pemilihan vehicle untuk pendistribusian

bunga krisan ke daerah lainnya menggunakan langkah dan cara yang sama.

Hasil penentuan vehicle pada tiap daerah pendistribusian bunga krisan

ditunjukkan pada tabel 5.6.

Tabel 5.6 Hasil Penentuan Vehicle Optimal Model Permasalahan HFVRP

Jenis Mobil Customer Demand Muatan Lebih Feasible

Engkle Serpong 100

31 Ya

Double 123 Tidak

Engkle Jakarta 150

- Tidak

Double 73 Ya

Engkle Cikarang 75

56 Ya

Double 148 Tidak

Engkle Cipanas 250

- Tidak

Double - Tidak

45

Engkle & Double 104 Ya

Seperti pada tabel 5.6, vehicle optimal yang digunakan untuk proses

pendistribusian bunga krisan ke daerah Jakarta menggunakan mobil boks jenis

double, daerah Cikarang menggunakan mobil boks engkle, dan daerah Cipanas

menggunakan kombinasi dua unit mobil boks berjenis engkle dan double.

5.2 Tahap Pengembangan Model

Pengembangan model yang dibahas pada sub bab ini mengenai

perancangan suatu model yang dapat menyatukan berbagai kebutuhan

komponen dari aplikasi yang akan dibuat untuk pemecahan masalah

optimalisasi rute transportasi pendistribusian bunga krisan. Perancangan model

berisi penetapan asumsi-asumsi, penetapan variabel keputusan, penentuan

fungsi tujuan serta identifikasi kendala-kendala. Tahap ini disusun sesuai

dengan pemahaman permasalahan yang didapat dari persiapan, pengumpulan

data serta analisis dan pengolahan data manual. Tahap-tahap pengembangan

model dijabarkan sebagai berikut.

5.2.1 Penetapan Asumsi

Asumsi-asumsi yang digunakan terdiri atas customer, produk, jarak dan

armada pengiriman (vehicle), sebagai berikut:

1. Customer

PT. EDAR mendistribusikan produknya ke daerah Bandara, Serpong,

Jakarta, Cikarang dan Cipanas yang diasumsikan perusahaan mampu

memenuhi semua permintaan customer. Customer yang menjadi kandidat

untuk dikenai proses optimalisasi rute transportasi pada kasus ini

diambil dari data customer dengan persentase pemesanan cukup sering

atau dianggap sebagai pelanggan tetap. Ini dilakukan untuk

meminimalisir penggunaan data yang tidak tetap dalam ruang lingkup

aktivitas pendistribusian. Data yang tidak tetap adalah data customer

46

yang tidak pasti dalam melakukan pemesanan bunga krisan secara

berkala.

2. Produk

Produk yang dikirim oleh perusahaan terdiri atas bunga potong, bibit

krisan unrooted cutting dan rooted cutting. Produk diasumsikan bersifat

homogen, artinya dalam satu vehicle hanya terdapat satu varietas. Hal ini

bertujuan untuk memudahkan penghitungan proses Algoritma Genetika

nantinya. Untuk produk bunga krisan jenis bunga potong dan bibit krisan

rooted cutting, dalam penentuan besar kapasitas muatan produk di mobil

boks digunakan satuan kadus. Sedangkan untuk jenis bibit krisan

unrooted cutting digunakan satuan batang.

3. Jarak

Data jarak merupakan data utama dalam kegiatan proses optimalisasi

rute transportasi menggunakan Algoritma Genetika. Jarak yang ditempuh

vehicle menuju titik-titik customer dalam proses pendistribusian bunga

krisan diasumsikan di mana pengukuran jarak antara dua titik dilakukan

dengan mengikuti alur jalan yang ada pada peta, sehingga data jarak

yang diperoleh dapat mendekati jarak aktual yang ditempuh oleh vehicle

(kendaraan). Pengukuran jarak antar dua titik disesuaikan dengan rute

yang memberikan jarak terpendek. Pada pengumpulan data jarak ini,

diasumsikan jarak tempuh dari titik A ke titik B sama dengan jarak

tempuh dari B ke titik A, sehingga jarak yang dihasilkan akan simetris.

4. Vehicle (Kendaraan)

Kendaraan yang digunakan untuk melakukan pendistribusian bunga

krisan adalah mobil boks L300, mobil boks engkle dan mobil boks double.

Masing-masing vehicle memiliki kapasitas angkut yang berbeda-beda.

Jumlah tiap unit kendaraan adalah 1 unit untuk mobil boks jenis L300, 6

unit mobil boks engkle dan 4 unit mobil boks double. Kondisi kendaraan

diasumsikan baik dan layak digunakan. Tiap customer diasumsikan hanya

dapat dikunjungi oleh satu vehicle untuk masing-masing tipe mobil boks.

47

BAB 6

PERANCANGAN DAN IMPLEMENTASI

Pada bab ini akan dibahas mengenai pembuatan perangkat lunak untuk

menyelesaikan permasalahan optimalisasi rute transportasi dan pemilihan vehicle

yang tepat dalam proses kegiatan pendistribusian bunga krisan. Pembahasan

dimulai dari definisi umum perangkat lunak, rancangan perangkat lunak,

implementasi arsitektur dan uji coba evaluasi.

6.1 Deskripsi Umum Perangkat Lunak

Aplikasi ini dibuat untuk menyelesaikan permasalahan optimalisasi rute

transportasi yang bertipe Heterogeneous Fleet VRP pada kasus pendistribusian

bunga krisan.

Metode yang digunakan untuk menghasilkan rute optimal adalah

Algoritma Genetika yang terbukti memiliki kemampuan dalam pemecahan

masalah Integer Programming bersifat metaheuristic. Semakin lama proses

pencarian, solusi yang didapat cenderung semakin baik. Karena itu, proses

komputasi dilakukan berulang sampai menemukan solusi paling optimal. Selain

itu juga digunakan bantuan metode Nearest Neighbor Algorithm untuk

menghasilkan tipe vehicle yang tepat sebagai alat transportasi perndistribusian

bunga.

6.2 Rancangan Perangkat Lunak

Rancangan perangkat lunak merupakan hal yang sangat penting untuk

mempermudah pembuatan aplikasi. Selain itu penggunaan properti yang sesuai

dengan kebutuhan komputasi juga perlu diperhatikan untuk memberi

kemudahan pengguna dalam mengoperasikan aplikasi secara efisien. Rancangan

aplikasi terdiri dari rancangan operator Algoritma Genetika, rancangan aliran data

dan rancangan user interface.

48

6.2.1 Rancangan Operator Algoritma Genetika

Operator Algoritma Genetika yang digunakan pada aplikasi ini meliputi

operator populasi, seleksi, crossover, mutasi, evaluasi dan evolve populasi.

1. Populasi

Operator populasi berisi kumpulan individu atau chromosome yang

menggambarkan solusi rute. Populasi awal dibentuk dari chromosome

acak. Pertama di-list customer (gen) yang sebelumnya telah terdata di

dalam sebuah tabel. Kemudian gen-gen dibentuk menjadi sebuah

chromosome yang menyatakan sebuah rute. Populasi terbentuk dari

beberapa chromosome yang diacak menggunakan fungsi random.

2. Seleksi

Populasi yang telah terbentuk diseleksi dengan dipilih beberapa dari

keseluruhan chromosome dalam sebuah individu. Jumlah chromosome yang

terkena proses seleksi sesuai dengan jumlah parameter seleksi yang diiput

user.

3. Crossover

Chromosome hasil seleksi diproses menggunakan operator crossover dengan

menukar sub chromosome antar kedua chromosome (parent). Sub chromosome

didapat dari penentuan titik awal dan titik akhir masing-masing secara

random. Hasil proses crossover disimpan sebagai chromosome child.

4. Mutasi

Proses mutasi dengan menukar dua posisi gen (customer) menggunakan

teknik swap mutation. Dua posisi gen ditentukan secara acak sesuai dengan

probabilitas mutasi yang diinput user.

5. Evaluasi

Operator evaluasi akan menghasilkan suatu nilai yang disebut sebagai

fitness value sebagai pengukur kualitas suatu chromosome. Fitness value

diperoleh dari total jarak yang ditempuh vehicle dalam tiap solusi rute

(chromosome).

6. Evolve Populasi

49

Evolve populasi adalah pembentukan populasi baru dari hasil populasi

generasi awal. Perkembangan populasi didasari banyaknya generasi yang

diproses. Jumlah generasi diiput oleh user yang melambangkan jumlah

iterasi proses komputasi algoritma.

6.2.2 Perancangan Aliran Data

Aliran data pada aplikasi ditampilkan dengan desain Data Flow Diagram

(DFD) yang terbagi menjadi DFD level 0, level 1 dan level 2. DFD level 0 dari

aplikasi ini dapat dilihat pada Gambar 6.1.

Gambar 6.1 Desain DFD Level 0

Pada Gambar 6.1, pengguna memasukkan input data awal yang

mempengaruhi komputasi Algoritma Genetika seperti jumlah populasi, jumlah

generasi, parameter seleksi dan probabilitas mutasi. Setelah itu aplikasi akan

melakukan proses penyelesaian optimalisasi yang menghasilkan output rute

optimal dan mengembalikannya kembali pada pengguna. Breakdown pada DFD

level 0 ini akan menghasilkan DFD level 1 yang dapat dilihat pada gambar 6.2.

50

Gambar 6.2 Desain DFD Level 1

Alur DFD level 1 pada gambar 6.2, terdapat proses inisialisasi populasi

awal sebelum melakukan komputasi Algoritma Genetika. Pencarian solusi diawali

dengan pembacaan masukan data awal yang diinput user, kemudian dilanjutkan

dengan insialisasi populasi awal. Solusi optimal didapat dari hasil pencarian

solusi menggunakan Algoritma Genetika yang akhirnya dikembalikan dan

ditampilkan kembali kepada user. Desain DFD level 1 kemudian di-breakdown

sehingga menjadi proses pencarian solusi DFD level 2 seperti terlihat pada

Gambar 6.3.

51

Gambar 6.3 Desain DFD Level 2

Dari alur DFD level 2 pada gambar 6.3, proses Algoritma Genetika terdiri

dari proses Generate Initial Population di awal yang bertujuan menghasilkan initial

population yang kemudian diproses dengan AG. Proses Algoritma Genetika ini

kemudian dilakukan berulang sampai memenuhi stopping condition berupa

banyaknya iterasi sesuai dengan data jumlah generasi yang diiput user.

6.2.3 Perancangan User Interface

Seperti yang telah dibahas pada alur DFD level 1, diperlukan penginputan

data yang dilakukan oleh user sebelum akhirnya proses komputasi algoritma

dijalankan. Aplikasi ini dirancang menggunakan user interface sebagai sarana

interaksi user dengan data dan parameter Algoritma Genetika. Berikut ini

rancangan tampilan aplikasi pada gambar 6.4.

52

Gambar 6.4 Desain Perancangan User Interface Aplikasi

Dua buah tabel di gambar 6.4 menunjukkan data customer yang

dibutuhkan untuk mencari rute optimal, dan data vehicle untuk mendapatkan

jenis vehicle yang tepat sebagai alat transportasi. User diharuskan menginput

jumlah populasi, jumlah generasi, probabilitas mutasi dan parameter seleksi

untuk digunakan pada proses iterasi. Button proses untuk menampilkan

keluaran berupa jarak optimal, solusi rute dan solusi vehicle dari proses Algoritma

Genetika.

6.3 Implementasi Arsitektur

Pada sub bab ini akan dibahas mengenai implementasi berdasarkan

perancangan perangkat lunak yang telah dijabarkan sebelumnya. Perangkat

lunak dibuat menggunakan aplikasi pemograman, kemudian dilakukan uji coba

apakah aplikasi menghasilkan keluaran sesuai dengan yang diharapkan.

Pembahasan terdiri dari spesifikasi alat yang digunakan untuk pembuatan

aplikasi, batasan-batasan dalam implementasi, dan implementasi algoritma.

Genetic Algorithm

Optimalisasi Rute Transportasi Pendistribusian Bunga Krisan

Data Customer

Jumlah Populasi Probabilitas Mutasi

Jumlah Generasi Parameter Seleksi Input

HASIL JARAK OPTIMA

SOLUSI RUTE Output

SOLUSI VEHICLE

Reset Proses

53

Spesifikasi software dan hardware yang digunakan dalam pembangunan sistem ini

yaitu:

1. Spesifikasi Software

Spesifikasi software dibagi ke dalam dua bagian yaitu manajemen data dan

manajemen model.

a) Manajemen Data

Data yang digunakan dalam pengolahan Optimalisasi Rute

Transportasi Pendistribusian Bunga Krisan adalah bentuk data yang

dibangkitkan secara random.

b) Manajemen Modal

Bahasa pemrograman yang digunakan adalah bahasa pemrograman

Java. Bahasa pemrograman ini memiliki kelebihan dalam hal

multiplatform dan menggunakan konsep Object Oriented Programming

(OOP). Selain itu Java juga memiliki library yang lengkap di mana

sangat membantu dalam membangun sebuah aplikasi khususnya

aplikasi berbasis pengolahan data.

Netbeans adalah salah satu aplikasi IDE yang digunakan programmer

untuk menulis, mengkompilasi, mencari kesalahan dan menyebarkan

program. Source code Netbeans bukan hanya ditulis dalam bahasa

Java, namun dapat juga mendukung bahasa pemograman lain. Fitur

yang dimiliki Netbeans ini seperti smart code, compilation, code

generator, error stripe, dan go to commands. Netbeans yang digunakan

dalam penelitian ini adalah Netbeans IDE 7.1.

2. Spesifikasi Hardware

Berikut ini perangkat keras yang digunakan dalam mambantu proses

pembuatan program.

Sistem operasi : Windows 7 Ultimate 32-bit (6.1, Build 7601)

System model : TOSHIBA Satellite L730

Prosesor : Intel Core i5, 2.53 GHz

Memori : 4138 MB

54

6.4 Batasan Implementasi

Batasan implementasi adalah batasan proses yang bisa dilakukan sistem

sesuai dengan perancangan awal sistem. Batasan ditampilkan agar penelitian ini

memiliki ruang lingkup yang jelas dalam mengimplementasikan sistem.

Beberapa batasan tersebut antara lain:

1. Aplikasi dijalankan khusus untuk mengolah permasalahan Optimalisasi

Rute Transportasi Pendistribusian Bunga Krisan menggunakan metode

Algoritma Genetika di Netbeans.

2. Data yang diproses sesuai dengan data fungsi yang telah didefinisikan di

dalam program.

3. Data jarak merupakan data terpenting dalam pengolahan ini dan

diperoleh dari jarak antar titik customer (gen).

4. Hasil optimalisasi rute selalu berbeda di tiap running program

dikarenakan beberapa data pengolahan diperoleh dari pembangkitan

bilangan random. Ini juga terjadi karena Algoritma Genetika mencari solusi

yang terbaik dengan metode pendekatan terhadap solusi paling optimal

dari beberapa kali pemrosesan ulang (proses lebih dari satu generasi).

5. Data jarak antar node atau gen dibangkitkan secara random dengan

jumlah node sebanyak 5 sesuai dengan jumlah pelanggan.

6. Solusi jenis vehicle yang tepat untuk melakukan distribusi bunga ke

masing-masing customer ditentukan dari data kapasitas vehicle dan besar

demand dari masing-masing customer. Kapasitas vehicle harus lebih besar

dari permintaan customer yang akan dikunjungi.

6.5 Implementasi Algoritma

Aplikasi Optimalisasi Rute Transportasi Pendistribusian Bunga Krisan

menggunakan Algoritma Genetika terdiri dari beberapa tahapan proses

pengolahan data yang dijabarkan sebagai berikut.

55

6.5.1 Implementasi Algoritma Pembangkitan Populasi Awal

Proses ini merupakan proses di mana populasi awal dibentuk. Di dalam

proses ini akan terbentuk chromosome yang memiliki sifat permutasi. Tiap

chromosome tidak boleh memiliki nilai yang sama, tepat satu nilai dari masing-

masing gen di tiap individu.

public class Chromosome { // chromosome, solusi rute, terdiri dari seluruh gen yg akan di kunjungi private ArrayList chromosome = new ArrayList<Gen>(); // Reset fitness dan jarak awal = 0 private double fitness = 0; private int jarak = 0; // Membangun chromosome awal = null public Chromosome(){ for (int i = 0; i < ChromosomeController.jumlahKota(); i++) { chromosome.add(null); } } public Chromosome(ArrayList chromosome){ this.chromosome = chromosome; } // Membangun sebuah chromosome public void generateIndividual() { for (int genIndex = 0; genIndex < ChromosomeController.jumlahKota(); genIndex++) { setGen(genIndex, ChromosomeController.getGen(genIndex)); } // Random chromsome Collections.shuffle(chromosome); } // Function getGen // Get posisi gen didalam chromosome // chromosomePosition = index posisi gen dalam chromosome public Gen getGen(int chromosomePosition) { return (Gen)chromosome.get(chromosomePosition);

} // Menetapkan kota(gen) dalam posisi tertentu dalam chromosome public void setGen(int chromosomePosition, Gen gen) { chromosome.set(chromosomePosition, gen); // Jika komposisi chromosome berubah, reset ulang fitness dan jarak = 0 fitness = 0; jarak = 0; }

56

6.5.2 Implementasi Proses Algoritma Genetika

Proses optimalisasi rute menggunakan Algoritma Genetika terdiri dari

beberapa tahapan dimulai dengan inisialisasi populasi awal, kemudian seleksi

populasi untuk memperoleh parent yang nantinya dikenai proses crossover dan

mutasi. Tiga tahap penting tersebut dijabarkan ke dalam source code berikut.

//SELEKSI // Seleksi kandidat chromosome yang akan di crossover private static Chromosome rouletteSelection(Population pop) { // Populasi Seleksi Population seleksi = new Population(seleksiSize, false); for (int i = 0; i < seleksiSize; i++) { // chromosome hasil seleksi diambil secara random dari total populasi int randomId = (int) (Math.random() * pop.populationSize()); // chromosome seleksi (index, city) seleksi.saveChromosome(i, pop.getChromosome(randomId)); } // fittest dari chromosome hasil seleksi Chromosome fittest = seleksi.getFittest(); return fittest; }

// CROSSOVER

// Set parent dan offspring dalam proses crossover (kawin silang) public static Chromosome crossover(Chromosome parent1, Chromosome parent2) { // Child Chromosome child = new Chromosome(); // Posisi titik awal dan akhir dari parent yang akan di crossover int awalPos = (int) (Math.random() * parent1.chromosomeSize()); int akhirPos = (int) (Math.random() * parent1.chromosomeSize()); // Menambahkan sub chromosome dari parent1 ke child for (int i = 0; i < child.chromosomeSize(); i++) { // Posisi awal dan akhir titik chromosome yang menjadi daerah pemetaan if (awalPos < akhirPos && i > awalPos && i < akhirPos) { child.setGen(i, parent1.getGen(i)); } else if (awalPos > akhirPos) { if (!(i < awalPos && i > akhirPos)) { child.setGen(i, parent1.getGen(i)); } } } // Chromosome parent 2 for (int i = 0; i < parent2.chromosomeSize(); i++) { // jika child tidak ada dalam chromosome, di add if (!child.containsGen(parent2.getGen(i))) {

57

for (int ii = 0; ii < child.chromosomeSize(); ii++) { if (child.getGen(ii) == null) { child.setGen(ii, parent2.getGen(i)); break; } } } } return child; }

// MUTASI

// Mutasi menggunakan swapp Mutation private static void mutate(Chromosome chromosome) { for(int chromosomePos1=0; chromosomePos1 < chromosome.chromosomeSize(); chromosomePos1++){ // Membandingkan dengan nilai probabilitas mutasi if(Math.random() < mutationRate){ // Posisi gen kedua dari chromosome secara random int chromosomePos2 = (int) (chromosome.chromosomeSize() * Math.random()); // city1 = posisi gen kesatu, city2 posisi gen kedua untuk dimutasi Gen gen1 = chromosome.getGen(chromosomePos1); Gen gen2 = chromosome.getGen(chromosomePos2); // kedua posisi di swap (index, gen) chromosome.setGen(chromosomePos2, gen1); chromosome.setGen(chromosomePos1, gen2); } } }

6.5.3 Implementasi Algoritma Penentuan Jarak dan Nilai Fitness

Penghitungan nilai fitness dilakukan untuk mengetahui solusi rute

(chromosome) yang paling optimal. Dalam menentukan nilai fitness, digunakan

metode seleksi elitisme yaitu memilih fitness yang mempunyai nilai terkecil dari

kumpulan chromosome yang telah dihitung. Nilai fitness merupakan inverse dari

data jarak antar titik distribusi. Struktur program untuk penhitungan fitness

ditunjukkan pada source code berikut.

// Function getFitness // Menghitung fitness tiap chromosome (1/total jarak sebuah rute) public double getFitness() {

if (fitness == 0) { fitness = 1/(double)getJarak();

58

} return fitness; }

// Function getJarak // Get total jarak dari sebuah chromosome public int getJarak(){ if (jarak == 0) { int chromosomeDistance = 0; // looping seluruh gen dalam sebuah chromosome for (int genIndex=0; genIndex < chromosomeSize(); genIndex++) { // Kota (gen) posisi awal Gen fromGen = getGen(genIndex); // Kota (gen) tujuan Gen kotaTujuan; // Cek posisi bukan pada kota (gen) teakhir, // Jika posisi pada kota (gen) terakhir pada sebuah rute (chromosome), // kotaTujuan = kembali ke posisi kota (gen) awal if(genIndex+1 < chromosomeSize()){ kotaTujuan = getGen(genIndex+1); } else{ kotaTujuan = getGen(0); } // Jarak antar dua customer (gen) chromosomeDistance += fromGen.jarakDua(kotaTujuan); } jarak = chromosomeDistance; } return jarak; }

6.5.4 Implementasi Algoritma Fungsi Elitisme

Chromosome dari hasil inisialisasi populasi awal, crossover dan mutasi perlu

dipertahankan terutama untuk individu dengan hasil fitness terbaik. Secara teori,

tahap elitisme dapat meningkatkan kemampuan dari Algoritma Genetika karena

mempertahankan chromosome yang baik. Untuk memperkaya keberagaman hasil

solusi, proses iterasi dilakukan sebanyak jumlah generasi yang diinput user.

Berikut ini source code fungsi elitisme sebagai berikut.

// Mengembangkan populasi lebih dari satu generasi public static Populasi evolvePopulasi(Populasi pop) { Populasi newPopulasi = new Populasi(pop.populasiSize(), false); // Menjaga chromosome terbaik pada fungsi elitisme int elitismOffset = 0; if (elitism) {

59

newPopulasi.saveChromosome(0, pop.getFittest()); elitismOffset = 1; } // Populasi baru didalam fungsi elitisme for (int i = elitismOffset; i < newPopulasi.populasiSize(); i++) { // Parent Hasil seleksi Chromosome parent1 = rouletteSelection(pop); Chromosome parent2 = rouletteSelection(pop); // Parent crossover Chromosome child = crossover(parent1, parent2); // Child newPopulasi.saveChromosome(i, child); } // Mutasi gen didalam sebuah populasi untuk saling ditukar for (int i = elitismOffset; i < newPopulasi.populasiSize(); i++) { mutate(newPopulasi.getChromosome(i)); } return newPopulasi; }

6.6 Uji Coba Evaluasi

Uji coba dilakukan untuk menganalisa kemampuan aplikasi dalam

memecahkan permasalahan optimalisasi rute transportasi. Uji coba berdasarkan

acuan parameter Algoritma Genetika terhadap kualitas solusi yang dihasilkan.

Parameter AG yang digunakan pada aplikasi ini terdiri dari Jumlah chromosome

dalam sebuah populasi, jumlah generasi, besar parameter seleksi dan

probabilitas mutasi.

Jumlah chromosome dalam sebuah populasi menyatakan banyaknya solusi

rute yang dibentuk pada inisialisasi populasi awal. Jumlah generasi akan

membuat proses komputasi Algoritma Genetika mengalami pengulangan proses

iterasi sebanyak jumlah generasi tersebut. Dengan proses iterasi berulang,

diharapkan solusi rute dapat diperoleh mendekati hasil optimal. Selanjutnya

besar parameter seleksi adalah banyaknya parent yang dihasilkan dari proses

penyeleksian seluruh chromosome di dalam sebuah populasi untuk nantinya akan

dikenai proses persilangan (crossover). Sedangkan probabilitas mutasi digunakan

untuk menentukan chromosome-chromsome yang akan mengalami mutasi.

Pengujian akan dibagi ke dalam beberapa scenario, tiap skenario menggunakan

parameter yang berbeda-beda.

60

6.6.1 Uji Coba Skenario 1

Untuk pengujian awal, digunakan nilai-nilai parameter sebagai berikut :

Jumlah Populasi : 50

Jumlah Generasi : 100

Parameter Seleksi : 5

Probabilitas Mutasi : 0.001

Parameter pada skenario pertama menggunakan rekomendasi nilai parameter

De Jong. Untuk permasalahan yang memiliki kawasan solusi cukup besar, De

Jong merekomendasikan nilai parameter (popsize; pc; pm) = (50; 0.6; 0.001). Hasil

pengamatan tiap output komputasi Algoritma Genetika pada kasus permasalahan

ini ditampilkan ke dalam diagram pada gambar 6.5.

Gambar 6.5 Diagram Optimalisasi Rute dengan Fungsi Parameter De Jong

Gambar 6.5 merupakan diagram hasil iterasi proses optimalisasi rute

transportasi pendistribusian bunga krisan sebanyak 10 kali iterasi. Tiap iterasi

menghasilkan jarak optimum 257 titik yang merupakan jarak paling optimal

dari hasil proses komputasi Algoritma Genetika menggunakan aplikasi. Rute

paling optimal pada iterasi skenario pertama ini didapat susunan chromosome (4-

1-3-5-2). Rute ini merupakan solusi rute (chromosome) dengan persentase

kemunculan paling besar dari keseluruhan iterasi seperti yang ditampilkan pada

diagram. Susunan rute tersebut merupakan kunjungan dari Depot-Serpong-

0

0,5

1

1,5

2

2,5

3

3,5

4

5-2-4-1-3 4-2-5-3-1 4-1-3-5-2

Tingkat FrekuensiKemunculan Solusi RuteDalam 10 Kali Iterasi

61

Bandara-Jakarta-Cikarang-Cipanas-kembali ke Depot. Berikut ini tampilan

output aplikasi yang ditunjukkan pada Gambar 6.6.

Gambar 6.6 Output Rute Optimal Aplikasi Untuk Skenario 1

Hasil output pada Gambar 6.6 menunjukkan jarak optimal untuk

populasi awal dan populasi seluruh generasi. Jarak optimal yang diperoleh pada

insialisasi populasi awal adalah sebesar 257 titik. Sedangkan jarak optimal dari

seluruh iterasi (100 generasi) adalah sebesar 257 titik. Jarak optimal yang didapat

pada inisialisasi populasi awal sama dengan jarak optimal dari keseluruhan

generasi, karena pada inisialisasi populasi awal, jumlah populasi terbentuk

sebanyak 50 solusi, sehingga pencarian pada inisialisasi awal langsung

memenuhi hasil rute optimal.

6.6.2 Uji Coba Skenario 2

Skenario ini menggunakan parameter yang diperoleh dari penelitian

terdahulu yang membuat sebuah proyek mengenai Applying a Algoritma Genetika

to The Traveling Salesman Problem oleh Lee Jacobson, seorang developer di Bristol,

UK. Projek tersebut membahas mengenai pencarian solusi optimal dari bentuk

62

TSP dengan menggunakan Algoritma Genetika. Berikut ini parameter-parameter

yang digunakan pada proses komputasi.

Jumlah Populasi : 50

Jumlah Generasi : 100

Parameter Seleksi : 5

Probabilitas Mutasi : 0.015

Hasil uji coba menggunakan parameter tersebut ditampilkan pada diagram

optimalisasi rute Gambar 6.7.

Gambar 6.7 Optimalisasi Rute dengan Fungsi Parameter Lee Jacobson

Rute optimal yang diperoleh dari proses komputasi Algoritma Genetika

pada Gambar 6.7 menggunakan parameter Lee Jacobson dengan susunan rute

dari Depot menuju-Serpong-Bandara-Jakarta-Cikarang-Cipanas-kembali ke

Depot. Pada susunan rute ini mendapatkan persentase muncul sebanyak 4 kali

dari 10 kali iterasi. Hasil susunan solusi rute pada skenario ini sama dengan

hasil solusi rute pada skenario pertama. Hasil output pada aplikasi ditampilkan

pada Gambar 6.8.

0

0,5

1

1,5

2

2,5

3

3,5

4

3-1-4-5-2 2-4-1-3-5 1-4-2-5-3 4-1-3-5-2 4-2-5-3-1

Tingkat Frekuensi

Kemunculan Solusi

Rute Dalam 10 Kali

Iterasi

63

Gambar 6.8 Output Rute Optimal Aplikasi Untuk Skenario 2

6.6.3 Uji Coba Skenario 3

Pada skenario kali ini, komputasi Algoritma Genetika menggunakan

parameter dengan ukuran (popsize; pc; pm) = (80; 0.45; 0.01). Ukuran parameter

ini diperoleh dari rekomendasi nilai parameter oleh Sri Kusumadewi dalam

sebuah modul mengenai Pendahuluan Struktur Umum Komponen Utama

Seleksi, Rekombinasi dan Mutasi Algoritma Genetika Sederhana. Pada modul

dibahas bahwa jika fitness dari individu terbaik dipantau pada setiap generasi,

maka usulan batasan parameternya adalah :

Jumlah Populasi : 80

Jumlah Generasi : 1

Parameter Seleksi : 5

Probabilitas Mutasi : 0.01

Untuk memantau fitness terbaik dari individu ditiap generasi, maka jumlah

generasi pada skenario ini adalah 1. Berbeda seperti skenario sebelumnya yang

melakukan komputasi Algoritma Genetika sebanyak 100 generasi. Hasil uji coba

64

menggunakan parameter ini ditampilkan pada diagram optimalisasi rute

Gambar 6.9.

Gambar 6.9 Optimalisasi Rute dengan Fungsi Parameter Sri Kusumadewi

Hasil optimalisasi rute transportasi yang ditunjukkan diagram pada

Gambar 6.9, terdapat dua solusi rute yang memiliki jumlah frekuensi

kemunculan sama dalam 10 kali iterasi. Berbeda dari skenario sebelumnya, pada

skenario ini komputasi Algoritma Genetika hanya melakukan satu kali proses

optimalisasi sesuai dengan tujuan uji coba skenario ini yaitu untuk menganalisa

solusi rute yang dihasilkan pada tiap generasi. Susunan rute 2-4-1-3-5

menggambarkan rute transportasi beragkat dari Depot menuju-Cipanas-

Serpong-Bandara-Jakarta-Cikarang-kembali ke Depot. Untuk susunan rute 1-4-

2-5-3 menggambarkan rute transportasi dimulai dari Depot-Bandara-Serpong-

Cipanas-Cikarang-Jakarta- kembali ke Depot. Output rute optimal pada aplikasi

ditampilkan pada Gambar 6.10.

0

0,5

1

1,5

2

2,5

3

3-1-4-5-2 2-4-1-3-5 1-4-2-5-3 4-1-3-5-2 4-2-5-3-1

Tingkat Frekuensi

Kemunculan Solusi

Rute Dalam 10 Kali

Iterasi

65

Gambar 6.10 Output Rute Optimal Aplikasi Untuk Skenario 3

6.6.4 Uji Coba Heterogeneous Fleet VRP

Seperti yang telah dibahas sebelumnya bahwa permasalahan

Heterogeneous Fleet VRP pada kasus ini menggunakan bantuan algoritma Nearest

Neighbor dalam proses optimalisasi pemilihan alat transportasi (vehicle). Hasil

optimalisasi ditampilkan pada hasil output aplikasi gambar 6.11.

66

Gambar 6.11 Output Aplikasi

Pada Gambar 6.11, output dari solusi alat transportasi menunjukkan hasil

dengan deskripsi sebagai berikut:

1. Bandara, vehicle yang tepat untuk digunakan sebagai alat angkut

pendistribusian bunga krisan adalah tipe mobil boks L300 dan mobil boks

double. Banyaknya permintaan produk bunga krisan membutuhkan dua

kombinasi alat angkut transportasi.

2. Cipanas, pada output aplikasi menghasilkan solusi vehicle optimal pada

jenis mobil boks engkle dan double untuk melakukan pendistribusian

bunga krisan. Cipanas juga membutuhkan kombinasi dua mobil boks

sesuai dengan banyaknya permintaan dan kapasitas alat angkut.

3. Jakarta, solusi alat transportasi yang optimal pada customer ini adalah

jenis mobil boks double.

4. Serpong, optimal mengangkut bunga krisan dengan mobil boks engkle.

5. Cikarang, optimal mengangkut bunga krisan dengan mobil boks engkle.

67

DAFTAR PUSTAKA

Aswar, Wahyuda dan Muriana Emelda. 2013. Penerapan Metode Nearest Neighbor untuk Menentukan Rute Distribusi Roti Tawar Citarasa Bakery PT KMBU Bontang. Jurnal Teknik Industri. Tidak dipublikasikan. Samarinda: Universitas Mulawarman Samarinda.

Bahar, Emirul. 2003. Analisis Penentuan Jalur Transportasi Limbah Minyak Pada Aktivitas Pelayaran Laut Untuk Menghasilkan Total Biaya Pelayaran Minimum. Jurnal Ilmiah Ekonomi & BisnisUniversitas Gunadarma. Terakreditasi Nomor 2 Jilid 8 Agustus 2003, ISSN : 0853 – 862 X hal. 88 – 102. Bahar, Emirul. 2011. Optimasi Biaya Sistem Transportasi Berbasis Waktu, Jurnal Ilmiah Ekonomi Bisnis Universitas Gunadarma. Terakreditasi Volume 16 Nomor 2 Agustus 2011, ISSN 0853 – 862 X hal. 135 – 146.

Balai Pengkajian Teknologi Pertanian. 2006. Budidaya Tanaman Krisan, Yogyakarta.

Ballou, R. H. 1999. Business Logistics Management, 4th Ed. Prentice Hall International.

Bangun, Paulus Martua. 2011. Perancangan Algoritma Ant Colony Optimization (ACO) untuk Penyelesaian Vehicle Routing Problem (VRP). Skripsi. Tidak dipublikasikan Depok: Universitas Indonesia.

Charles Darwin. 2004. Britannica concise encyclopedia. URL: http://concise.britannica.com/ebc/article?eu=387589. (diakses 25 Mei 2015)

Crainic, T.G., Laporte, G. 1997. Planning Models for Freight Transportation. European Journal of Operational Research 97 (3): 409 438. Departemen Pertanian. 2013. Pusat Data Dan Sistem Informasi Pertanian No. 01/03/I, 5 Maret 2013. Dewi Agushinta Rahayu. 1994. A Algoritma Genetika on Coin Recognition System. Thesis. AIT. Thailand. Dunn, N. W. 1994. Analisis Kebijakan Publik, edisi kedua. Yogyakarta: AGdjah Mada University Press.

Eko, Bambang. 2007. Implementasi Algoritma Paralel Algoritma Genetika Untuk

68

Penyelesaian Heterogeneous Fleet Vehicle Routing Problem. Skripsi. Tidak dipublikasikan. Surabaya: Institut Teknologi Sepuluh Nopember.

Falkenauer. E. 1996. A Hybrid Grouping Algoritma Genetika for Bin Packing. Journal of Heuristics. 2:5-20.

Fisher. M. 1995. Vehicle Routing. Handbooks of Operations Research and Management Science. New York: North-Holland.

Gendreau, M. Laporte, G. and Potvin. J-Y. 1999. Metaheuristics for The Vehicle Routing Problem. Technical Report G-98-52, GERAD.

Gheysens, F. G., Golden, B.L. and Assad. A.A. 1984. A comparison of techniques for solving the fleet size and mix vehicle routing problem. OR Spectrum, 6(4):207-216.

Hermada, Johan. 2009. Info Perusahaan PT. Saung Mirwan. URL: http://saung-mirwan.indonetwork.co.id/. (diakses 1 Maret 2015)

Jacobson Lee. 2012. Applying a Algoritma Genetika To The Traveling Salesman Problem. URL: http://www.theprojectspot.com/tutorial-post/applying-a-genetic-algorithm-to-the-travelling-salesman-problem/5. (diakses 14 September 2015)

Kusumadewi, Sri dan Luger Subblefield. Pendahuluan Struktur Umum Komponen Utama Seleksi Rekombinasi Mutasi Algoritma Genetika Sederhana.

Laporte, G. Gandreau, M. Potvin, J-Y. dan Semet, F. 2000. Classical and Modern Heuristic for the Vehicle Routing Problem. International Transactions in Operational Research. 7:285-300.

Laporte G. dan Semet. F. 1999. Classical Heuristic for the Vehicle Routing Problem. Technical Report.

Leonita dan Evi Sipayung. 2011. Kajian Jaringan Transportasi dalam Manajemen Rantai Pasokan Bunga Krisan di Jawa Barat. Skripsi. Tidak dipublikasikan. Bogor: Institut Pertanian Bogor.

69

Liu, Shuguang, Weilai, Huang, Huiming, Ma. 2009. An Effective Algoritma Genetika for The fleet Size and Mix Vehicle Routing Problems. Transportation Research Part E45 (2009) 434–445, Elsevier.

Pankratz, Giselher. 2005. A Grouping Algoritma Genetika for the Pickup and Delivery Problem with Time Windows. OR Spectrum 27:21–41.

Pavela, V. dan Nurhadi, I. 2013. Penyelesaian Vehicle Routing Problem dengan Menggunakan Algoritma Nearest Neighbor dan Tabu Search. Studi Kasus di PT Nippon Indosari Corpindo. Skripsi. Tidak dipublikasikan. Malang: Universitas Brawijaya.

Pereira, F. B., Tavares, J., Machado P. dan Costa, E. 2002. A New Genetic Representation for the Vehicle Routing Problem. Prodeedings of the 13th Irish International Conference on Artifical Intelligence and Cognitive Science. Hal 95-102.

Pisinger, David, Ropke, Stefan. 2007. A General Heuristic for Vehicle Routing Problems. Computers & Operations Research 34 2403–2435, Elsevier.

Prana, Raden A. 2007. Aplikasi Kombinatorial pada Vehicle Routing Problem. Jurnal Teknik Informatika. Tidak dipublikasikan. Bandung: Institut Teknik Bandung.

Russel, R. S., Taylor, B. W. 2003. Operations Management. New Jersey: Prentice Hall. Sait S.M. and Youssef, H. editors. 1999. Iterative Computer Algorithms with Application in Engineering: Solving Combinatorial Optimization Problems, Chapter 3. IEEE Computer Society.

Wikimapia. 2006. PT. Saung Mirwan. URL: http://wikimapia.org/1661888/PT-Saung-Mirwan. (diakses 12 April 2015)

70

LAMPIRAN

BARIS PROGRAM

AGBungaKrisan.java /* * Teknik Informatika Fak. Teknologi Industri Universitas Gunadarma * Optimalisasi Rute Transportasi Heterogeneous Fleet VRP * Pendistribusian Bunga Krisan * Menggunakan Algoritma Genetika */ package AGbungakrisan; import java.awt.Graphics; import java.awt.Graphics2D; import java.awt.Image; import javax.swing.ImageIcon; import javax.swing.JFrame; /** * * @author Maesa Maziah */ public class AGBungaKrisan extends JFrame { /** * @param args the command line arguments */ public static void main(String[] args) { // TODO code application logic here //Menampilkan interface hasil berupa frame Interface.java Interface frame = new Interface(); frame.setVisible(true); frame.setTitle("Optimalisasi Rute Transportasi Pendistribusian Bunga Krisan Menggunakan Algoritma Genetika"); frame.pack(); frame.setDefaultCloseOperation(Interface.EXIT_ON_CLOSE); } } Gen.java

/* * Teknik Informatika Fak. Teknologi Industri Universitas Gunadarma * Optimalisasi Rute Transportasi Heterogeneous Fleet VRP * Pendistribusian Bunga Krisan * Menggunakan Algoritma Genetika */ package AGbungakrisan; /** * * @author Maesa Maziah */ public class Gen { int x; int y; // Menentukan titik x,y dari tiap gen secara random public Gen(){

71

this.x = (int)(Math.random()*108); this.y = (int)(Math.random()*78); } // Gen(x,y) // Membangun suatu posisi gen dari titik x,y public Gen(int x, int y){ this.x = x; this.y = y; } // Function getX() // Get koordinat x sebuah gen public int getX(){ return this.x; } // Function getY() // Get koordinat y sebuah gen public int getY(){ return this.y; } // Function jarakDua // Menghitung jarak antar dua titik gen public double jarakDua(Gen gen){ int xJarak = Math.abs(getX() - gen.getX()); int yJarak = Math.abs(getY() - gen.getY()); double jarak = Math.sqrt( (xJarak*xJarak) + (yJarak*yJarak) ); return jarak; } @Override // Output posisi gen (x, y) public String toString(){ return getX()+", "+getY(); } } Chromosome.java

/* * Teknik Informatika Fak. Teknologi Industri Universitas Gunadarma * Optimalisasi Rute Transportasi Heterogeneous Fleet VRP * Pendistribusian Bunga Krisan * Menggunakan Algoritma Genetika */ package AGbungakrisan; import java.util.ArrayList; import java.util.Collections; /** * * @author Maesa Maziah */ public class Chromosome { // chromosome, solusi rute, terdiri dari seluruh gen yg akan di kunjungi private ArrayList chromosome = new ArrayList<Gen>(); // Reset fitness dan jarak awal = 0 private double fitness = 0;

72

private int jarak = 0; // Membangun chromosome awal = null public Chromosome(){ for (int i = 0; i < ChromosomeController.jumlahKota(); i++) { chromosome.add(null); } } public Chromosome(ArrayList chromosome){ this.chromosome = chromosome; } // Membangun sebuah chromosome public void generateIndividual() { for (int genIndex = 0; genIndex < ChromosomeController.jumlahKota(); genIndex++) { setGen(genIndex, ChromosomeController.getGen(genIndex)); } // Random chromsome Collections.shuffle(chromosome); } // Function getGen // Get sebuah gen didalam chromosome // chromosomePosition = index posisi gen dalam chromosome public Gen getGen(int chromosomePosition) { return (Gen)chromosome.get(chromosomePosition); } // Menetapkan kota(gen) dalam posisi tertentu dalam chromosome public void setGen(int chromosomePosition, Gen gen) { chromosome.set(chromosomePosition, gen); // Jika komposisi chromosome berubah, reset ulang fitness dan jarak = 0 fitness = 0; jarak = 0; } // Function getFitness // Menghitung fitness tiap chromosome (1/total jarak sebuah rute) public double getFitness() { if (fitness == 0) { fitness = 1/(double)getJarak(); } return fitness; } // Function getJarak // Get total jarak dari sebuah chromosome public int getJarak(){ if (jarak == 0) { int chromosomeDistance = 0; // looping seluruh gen dalam sebuah chromosome for (int genIndex=0; genIndex < chromosomeSize(); genIndex++) { // Kota (gen) posisi awal Gen fromGen = getGen(genIndex); // Kota (gen) tujuan Gen kotaTujuan; // Cek posisi bukan pada kota (gen) teakhir, // Jika posisi pada kota (gen) terakhir pada sebuah rute (chromosome), // kotaTujuan = kembali ke posisi kota (gen) awal if(genIndex+1 < chromosomeSize()){ kotaTujuan = getGen(genIndex+1);

73

} else{ kotaTujuan = getGen(0); } // Jarak antar dua customer (gen) chromosomeDistance += fromGen.jarakDua(kotaTujuan); } jarak = chromosomeDistance; } return jarak; } // Jumlah customer (gen) dalam sebuah chromosome (solusi rute) public int chromosomeSize() { return chromosome.size(); } // Cek sebuah chromosome berisi gen (customer) public boolean containsGen(Gen gen){ return chromosome.contains(gen); } // Output Solusi rute, pembatas antar gen (customer) @Override public String toString() { String geneString = " | "; for (int i = 0; i < chromosomeSize(); i++) { geneString += getGen(i)+" | "; } return geneString; } } ChromosomeController.java /* * Teknik Informatika Fak. Teknologi Industri Universitas Gunadarma * Optimalisasi Rute Transportasi Heterogeneous Fleet VRP * Pendistribusian Bunga Krisan * Menggunakan Algoritma Genetika */ package AGbungakrisan; import java.util.ArrayList; /** * * @author Maesa Maziah */ public class ChromosomeController { // kotaTujuan = gen-gen dalam satu buah rute (chromosome) private static ArrayList kotaTujuan = new ArrayList<Gen>(); // Prosedur add gen ke dalam kotaTujuan public static void addGen(Gen gen) { kotaTujuan.add(gen); } // Function getGen // get gen dari sebuah kotaTujuan public static Gen getGen(int index){ return (Gen) kotaTujuan.get(index);

74

} // Function jumlahKota // Total gen di dalam kotaTujuan public static int jumlahKota(){ return kotaTujuan.size(); } } Population.java

/* * Teknik Informatika Fak. Teknologi Industri Universitas Gunadarma * Optimalisasi Rute Transportasi Heterogeneous Fleet VRP * Pendistribusian Bunga Krisan * Menggunakan Algoritma Genetika */ package AGbungakrisan; /** * * @author Maesa Maziah */ public class Population { // Inisialisasi populasi = chromosome Chromosome[] chromosomes; // Membangun sebuah populasi public Population(int populationSize, boolean initialise) { chromosomes = new Chromosome[populationSize]; // if initialise = true, inisialisasi populasi if (initialise) { // membangun chromosome // prosedure generateIndividual pada Chromosome.Java for (int i = 0; i < populationSize(); i++) { Chromosome newChromosome = new Chromosome(); newChromosome.generateIndividual(); saveChromosome(i, newChromosome); } } } // Save sebuah chromosome public void saveChromosome(int index, Chromosome chromosome) { chromosomes[index] = chromosome; } // Get sebuah chromosome dari populasi public Chromosome getChromosome(int index) { return chromosomes[index]; } // Get chromosome terbaik dari populasi public Chromosome getFittest() { Chromosome fittest = chromosomes[0]; // Looping chromosome-chromosome untuk mendapatkan fittest for (int i = 1; i < populationSize(); i++) { if (fittest.getFitness() <= getChromosome(i).getFitness()) { fittest = getChromosome(i); } } return fittest;

75

} // PopulastionSize = Seumlah populasi pada array tours public int populationSize() { return chromosomes.length; } } AG.java /* * Teknik Informatika Fak. Teknologi Industri Universitas Gunadarma * Optimalisasi Rute Transportasi Heterogeneous Fleet VRP * Pendistribusian Bunga Krisan * Menggunakan Algoritma Genetika */ package AGbungakrisan; /** * * @author Maesa Maziah */ public class AG { /* Parameter AG */ private static final double mutationProb = Interface.probMutasi; private static final int seleksiSize = Interface.probSeleksi; private static final boolean elitisme = true; // Mengembangkan populasi lebih dari satu generassi public static Population evolvePopulation(Population pop) { Population newPopulation = new Population(pop.populationSize(), false); // Elitism // Menjaga chromsome terbaik // elitismOffset = generasi awal == 0 int elitismeOffset = 0; if (elitisme) { // Chromosome terbaik (Fittest) dengan index 0 newPopulation.saveChromosome(0, pop.getFittest()); // generasi + 1 elitismeOffset = 1; } // Populasi crossover // Membangun populasi baru pada generasi-generasi selanjutnya // Populasi saat ini for (int i = elitismeOffset; i < newPopulation.populationSize(); i++) { // Parent seleksi Chromosome parent1 = rouletteSelection(pop); Chromosome parent2 = rouletteSelection(pop); // di Crossover menghasilkan chromosome child Chromosome child = crossover(parent1, parent2); // child di tambahkan ke dalam newPopulation dengan index = i newPopulation.saveChromosome(i, child); } // Memutasi populasi baru untuk mendapatkan beberapa materi genetik baru (gen hasil mutasi) for (int i = elitismeOffset; i < newPopulation.populationSize(); i++) { mutate(newPopulation.getChromosome(i)); } return newPopulation;

76

} // Crossover // Set parent dan menghasilkan offspring (child) public static Chromosome crossover(Chromosome parent1, Chromosome parent2) { // Membuat chromosome child Chromosome child = new Chromosome(); // Mendapatkan titik (gen) awal dan akhir sebagai posisi sub chromosome dari chromosome Parent1 // Titik awal dan akhir di dapat secara acak int startPos = (int) (Math.random() * parent1.chromosomeSize()); int endPos = (int) (Math.random() * parent1.chromosomeSize()); // Looping dan tambahkan sub chromosome tersebut ke chromosome child for (int i = 0; i < child.chromosomeSize(); i++) { // Jika posisi mulai lebih kecil dari posisi akhir if (startPos < endPos && i > startPos && i < endPos) { child.setGen(i, parent1.getGen(i)); } // Jika posisi mulai lebih besar else if (startPos > endPos) { if (!(i < startPos && i > endPos)) { child.setGen(i, parent1.getGen(i)); } } } // Looping sebanyak gen didalam chromosome parent2 for (int i = 0; i < parent2.chromosomeSize(); i++) { // If chromosome child tidak berisi gen, add gen if (!child.containsGen(parent2.getGen(i))) { // Looping untuk menemukan sebuah posisi lain di chromosme child (cadangan) // Loop to find a spare position in the child's tour for (int ii = 0; ii < child.chromosomeSize(); ii++) { // posisi di temukan, add if (child.getGen(ii) == null) { child.setGen(ii, parent2.getGen(i)); break; } } } } return child; } // Mutasi menggunakan swap mutation private static void mutate(Chromosome chromosome) { // Looping keseluruhan gen didalam chromosome, posisi gen kesatu for(int chromosomePos1=0; chromosomePos1 < chromosome.chromosomeSize(); chromosomePos1++){ // Menerapkan probabilitas mutasi (Mutation Rate) if(Math.random() < mutationProb){ // Posisi gen kedua dari chromosome secara random int chromosomePos2 = (int) (chromosome.chromosomeSize() * Math.random()); // city1 = posisi gen kesatu, city2 posisi gen kedua untuk dimutasi Gen gen1 = chromosome.getGen(chromosomePos1); Gen gen2 = chromosome.getGen(chromosomePos2); // kedua posisi di swap (index, gen) chromosome.setGen(chromosomePos2, gen1); chromosome.setGen(chromosomePos1, gen2); }

77

} } // Seleksi kandidat chromosome yang akan di crossover private static Chromosome rouletteSelection(Population pop) { // Populasi Seleksi Population seleksi = new Population(seleksiSize, false); for (int i = 0; i < seleksiSize; i++) { // chromosome hasil seleksi diambil secara random dari total populasi int randomId = (int) (Math.random() * pop.populationSize()); // chromosome seleksi (index, city) seleksi.saveChromosome(i, pop.getChromosome(randomId)); } // fittest dari chromosome hasil seleksi Chromosome fittest = seleksi.getFittest(); return fittest; } }

Solusi Algoritma Genetika Pada Permasalahan Transportasi Komoditas Bunga Krisan Emirul Bahar, Dewi Agushinta R., Rossi Septy Wahyuni

Diterbitkan pertama kali oleh Gunadarma Hak Cipta Dilindungi Undang-Undang Jakarta 2016