PENENTUAN RUTE OPTIMUM JALUR DISTRIBUSI DALAM SUPPLY CHAIN NETWORK MENGGUNAKAN ALGORITME GENETIKA DESCA MARWAN TONI

PENENTUAN RUTE OPTIMUM JALUR DISTRIBUSI DALAM SUPPLY CHAIN NETWORK MENGGUNAKAN ALGORITME GENETIKA

DESCA MARWAN TONI

DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2009

PENENTUAN RUTE OPTIMUM JALUR DISTRIBUSI DALAM SUPPLY CHAIN NETWORK MENGGUNAKAN ALGORITME GENETIKA

DESCA MARWAN TONI

Skripsi Sebagai salah satu syarat untuk memperoleh gelar Sarjana Komputer pada Departemen Ilmu Komputer

DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2009

ABSTRACT DESCA MARWAN TONI. Determining Optimal Distribution Route on the Supply Chain Network using Genetic Algorithm. Under the direction of SONY HARTONO WIJAYA. In the past few years, the Supply Chain Network (SCN) field has gained more attention due to the competition which is introduced by the market globalization. Distribution network design is one of the most comprehensive and strategic decision problem that need to be optimized for efﬁcient operation on the supply chain field. The distribution network design establishes distribution channels, determines the amount of materials and items to consume, and also ships the product from suppliers to customers. The optimal distribution depends on the optimal route, which is influenced by the distance and the distribution time. This paper presents a genetic algorithm approach to determine optimal distribution route. Genetic algorithm was implemented to search the optimal route from the start point to the destination point. Priority-based chromosomes (strings) and their genes (parameters) were used to encode the problem. Weight Mapping Crossover and Swap Mutation were used as genetic operator, while the selection method used was roulette wheel. The algorithm was tested in a road map containing 44 nodes and from the experiments, we could conclude that the genetic algorithm system design worked well to solve the optimation problem. Keywords: Supply Chain Network, Genetic Algorithm, distribution route.

Judul :

Penentuan Rute Optimum Jalur Distribusi Dalam Supply Chain Network Menggunakan Algoritme Genetika Nama : Desca Marwan Toni NIM : G64050979

Menyetujui:

Pembimbing

Sony Hartono Wijaya, M.Kom. NIP 198108092008121002

Mengetahui: Dekan Fakultas Matematika Dan Ilmu Pengetahuan Alam Institut Pertanian Bogor

Dr. Drh. Hasim, DEA NIP 196103281986011002

Tanggal Lulus:

PRAKATA Alhamdulillahi Rabbil ‘alamin, puji dan syukur penulis panjatkan kepada Allah SWT atas limpahan rahmat dan hidayah-Nya sehingga tugas akhir dengan judul Penentuan Rute Optimum Jalur Distribusi Dalam Supply Chain Network Menggunakan Algoritme Genetika dapat diselesaikan. Penelitian ini dilaksanakan mulai Maret 2009 sampai dengan Juli 2009, bertempat di Departemen Ilmu Komputer. Penulis ingin mengucapkan terima kasih kepada semua pihak yang telah memberikan bantuan, bimbingan dan dorongan kepada penulis selama menyelesaikan tugas akhir ini, antara lain : 1. Kedua orangtua tercinta, Bapak dan Ibu yang telah memberikan inspirasi, kasih sayang, doa dan dukungan moral selama ini. 2. Kakak dan kedua adik tercinta, Rini Hastuti, SE., Tri Putra Kurniawan, Yenni Novita Lestari yang selalu memberikan semangat dalam penyelesaian tugas akhir ini. 3. Bapak Sony Hartono Wijaya, M.Kom. selaku pembimbing atas bimbingan dan arahannya selama pengerjaan tugas akhir ini. 4. Bapak Azis Kustiyo, S.Si.,M.Kom. dan Bapak Toto Haryanto, S.Kom. yang telah berkenan untuk menjadi penguji penelitian ini. 5. Fitria Yulianti, Amd.Keb. dan keluarga yang telah memberikan dukungan, doa dan kasih sayangnya selama ini. 6. Seluruh penghuni Edensor : Hermawan Tri Rosanja, Fahmilu Kurniawan, Fathoni A.M, Hengky, Furqon Hensan M, Syariful Mizan, dan Haryanto atas kebersamaan dan semangat yang disalurkan selama pengerjaan tugas akhir ini. 7. Dimas Perdana, M.Saad N, dan Haryanto yang telah membantu penulis dalam mengumpulkan data untuk penelitian ini. 8. Rekan-rekan satu bimbingan atas dukungan dan kebersamaannya. 9. Fakhri Mahathir, Gaos Irwana dan rekan-rekan kerja yang telah memberikan semangat dalam penyelesaian tugas akhir ini. 10. Teman-teman seperjuangan Program Studi Ilmu Komputer angkatan 42 atas kebersamaan dan pengalaman berbagi ilmu selama menuntut ilmu di Ilmu Komputer IPB. Penulis selalu berharap semoga apa yang telah dikerjakan dalam penelitian ini dapat memberikan manfaat bagi semua pihak.

Bogor, Agustus 2009

Desca Marwan Toni

RIWAYAT HIDUP Penulis dilahirkan pada tanggal 1 Januari 1988 di Bengkulu, yang merupakan anak kedua dari empat bersaudara dengan ayah bernama M. Ayub Mazni dan ibu bernama Hasmiyati. Penulis berhasil menyelesaikan pendidikan Sekolah Menengah Atas (SMA) di SMAN 4 Bengkulu pada tahun 2005, dan penulis langsung diterima di Institut Pertanian Bogor melalui jalur Undangan Seleksi Masuk IPB (USMI) pada tahun yang sama, setelah melalui Tahap Persiapan Bersama (TPB) IPB, akhirnya penulis diterima di Departemen Ilmu Komputer IPB. Pada tahun 2008, penulis melaksanakan kegiatan praktik kerja lapangan di Pusat Perpustakaan dan Penyebaran Teknologi Pertanian selama 35 hari kerja. Dalam kegiatan perkuliahan, penulis juga aktif dalam berbagai organisasi kemahasiswaan, antara lain Himpunan Mahasiswa Ilmu Komputer sebagai ketua umum, DKM Al-Hurriyyah dan Organisasi Mahasiswa Daerah IMBR Bengkulu. Penulis mendapat kesempatan menjadi asisten praktikum basis data di Departemen Ilmu Komputer IPB pada tahun 2008 dan 2009, dan penulis juga menjadi pengajar aktif di bimbingan belajar Bintang Pelajar Bogor.

DAFTAR ISI Halaman DAFTAR TABEL……………………………………………………………………………………...

v

DAFTAR GAMBAR ………………………………………………………………………………….

v

DAFTAR LAMPIRAN ……………………………………………………………………………….

v

PENDAHULUAN Latar Belakang ……………………………………………………………………………………. Tujuan …………………………………………………………………………………………….. Ruang Lingkup …………………………………………………………………………………… Manfaat ……………………………………………………………………………………………

1 1 1 1

TINJAUAN PUSTAKA Supply Chain Management ………………………………………………………………………. Supply Chain Network ……………………………………………………………………………. Distribusi …………………………………………………………………………………………. Algoritme Genetika ……………………………………………………………………………….

1 2 2 2

METODE PENELITIAN Studi Pustaka ……………………………………………………………………………………… 5 Perumusan Masalah ………………………………………………………………………………. 5 Pembentukan Data ………………………………………………………………………………... 5 Pengembangan Sistem ……………………………………………………………………………. 6 Representasi Kromosom ………………………………………………………………………. 6 Penentuan Populasi Awal …………………………………………………………………….. 8 Menghitung Nilai Fitness …………………………………………………………………….. 8 Proses Elitisme ………………………………………………………………………………... 8 Proses Seleksi Kromosom …………………………………………………………………….. 8 Proses Crossover ……………………………………………………………………………… 8 Proses Mutasi …………………………………………………………………………………. 9 Evaluasi dan Kriteria Berhenti ………………………………………………………………... 9 Pengujian Sistem …………………………………………………………………………………. 9 Lingkungan Pengembangan Sistem ………………………………………………………………. 10 HASIL DAN PEMBAHASAN Percobaan 1……………………………………………………………………………………….. Percobaan 2 ……………………………………………………………………………………….

10 13

KESIMPULAN DAN SARAN Kesimpulan ……………………………………………………………………………………….. Saran ………………………………………………………………………………………………

15 15

DAFTAR PUSTKA …………………………………………………………………………………..

15

LAMPIRAN …………………………………………………………………………………………..

17

DAFTAR TABEL Halaman 1 2 3 4 5 6

Daftar istilah Biologi yang digunakan dalam Algoritme Genetika ………………………………. Parameter ukuran populasi dengan nilai fitness rata-rata.………….…………………………….. Parameter crossover probability dengan nilai fitness rata-rata.………………………………….. Parameter mutation probability dengan nilai fitness rata-rata.………….……………………….. Parameter stall generation dengan nilai fitness rata-rata.………….…………………………….. Jarak tempuh, waktu tempuh rata- rata, dan nilai fitness…………...……………………………..

2 10 11 12 13 13

DAFTAR GAMBAR Halaman 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

Ilustrasi Supply Chain Network…………………………………..………………………………. Diagram Alir Algoritme Genetika ……..…………………………………………………… ….. Proses Weight Mapping Crossover.………………………………………………………………. Proses Swap Mutation ……. ……………………………………………………………………… Metodologi Penelitian ……………………………………………………………………………. Peta jalan Kota Bogor …………………………..…………………..……………………………. Contoh Representasi Graf Peta Jalan …………………..………………………………………… Ilustrasi Proses Encoding Kromosom…………………………………………………………….. Contoh Representasi Peta Jalan Dalam Bentuk Graf …………………………………………….. Ilustrasi Proses Decoding Kromosom ..………………………………………………………… .. Hubungan Ukuran Populasi dan Nilai Fitness ………..………………………………………….. Hubungan Ukuran Populasi dan Waktu Eksekusi Program ……………………………………… Hubungan Croosover Probability dan Nilai Fitness….………………………………………….. Hubungan Crossover Probability dan Akhir Generasi …………………………………………... Hubungan Mutation Probability dan Nilai Fitness ……………..…………………………..……. Hubungan Mutation Probability dan Akhir Generasi ..……………………………………..…… Hubungan Stall Generation dan Nilai Fitness ………………………………………………… .. Hubungan Stall Generation dan Waktu Eksekusi …….………………………………………….. Rute Alternatif 1 ………………………………..…….………………………………………….. Rute Alternatif 2 ………………………………..…….………………………………………….. Rute Alternatif 3 ………………………………..…….………………………………………….. Rute Alternatif 4 ………………………………..…….………………………………………….. Rute Alternatif 5 ………………………………..…….………………………………………….. Rute Alternatif 6 ………………………………..…….…………………………………………..

2 3 4 5 5 6 6 7 7 7 10 11 11 12 12 12 13 13 14 14 14 14 14 14

DAFTAR LAMPIRAN Halaman 1 2 3 4 5 6 7 8 9

Data Node Kota Bogor Sebagai Representasi Jalur Distribusi …………..………………………. Data Edge Kota Bogor Sebagai Representasi Jalur Distribusi …………………………………… Representasi Graf Data Peta Kota Bogor.………………………………………………………… Tampilan Awal dan Hasil Penentuan Rute Optimum Dalam Web ………………………………. Pengujian Ukuran Populasi Optimal …………………………………………………………….. Pengujian Crossover Probability Optimal …………………..…………………………………… Pengujian Mutation Probability Optimal.………………………………………………………… Pengujian Stall Generation Optimal ……………………………………………………………... Tampilan Sistem Rute Optimum Hasil Percobaan 2….…………………………………………...

18 19 22 23 24 27 29 31 33

v

PENDAHULUAN Latar Belakang Pada saat sekarang ini, setiap perusahaan yang ingin tetap bertahan dalam persaingan dengan perusahaan lainnya, harus bisa membuat semua lini proses bisnis perusahaan tersebut berjalan lebih efektif dan efisien. Perusahan tersebut harus bisa mengintegrasikan semua arus informasi, barang dan jasa mulai dari pemasok sampai ke konsumen. Proses integrasi ini akan menjadi andalan bagi suatu perusahaan sehingga diharapkan akan menambah keuntungan perusahaan. Proses integrasi ini dikenal dengan istilah Supply Chain Management. Supply chain management akan meningkatkan daya saing perusahaan. Salah satu faktor utama yang merupakan bagian dari supply chain management adalah supply chain network. Supply chain network terdiri atas dua bagian utama yaitu lokasi produksi dan proses distribusi. Penentuan lokasi produksi merupakan faktor yang sangat penting karena akan berhubungan dengan proses pemasaran dan pelayanan terhadap permintaan konsumen. Lokasi produksi yang tepat dapat meningkatkan kinerja perusahaan, sedangkan proses distribusi berhubungan dengan penyebaran informasi, barang dan jasa dari produsen ke konsumen. Proses distribusi harus memperhatikan penentuan jalur distribusi yang tepat. Penentuan jalur distribusi berkaitan dengan jarak tempuh dan waktu tempuh. Jalur distribusi yang tepat dapat mengoptimalkan proses distribusi. Oleh karena itu, dibutuhkan sebuah perancangan supply chain network yang baik, agar perusahaan dapat melakukan proses bisnis dengan lebih efektif dan efisien sehingga dapat meningkatkan kinerja perusahaan. Penelitian ini akan merancang supply chain network yang berfokus pada bagian proses distribusi yang dapat digunakan untuk mencari rute optimum jalur distribusi yaitu rute yang memiliki jarak tempuh terpendek dan waktu tempuh tercepat. Penelitian ini menggunakan Algoritme Genetika. Algoritme Genetika menggunakan representasi kromosom sebagai cara untuk mengkodekan suatu alternatif pencarian sehingga dapat diproses menggunakan Algoritme Genetika. Hasil dari perancangan ini akan diimplementasikan dalam bentuk web client yang dapat dengan mudah diakses oleh perusahaan.

Tujuan Tujuan dari penelitian ini adalah merancang supply chain network untuk menentukan rute optimum dengan menggunakan Algoritme Genetika. Ruang Lingkup Ruang lingkup penelitian ini adalah : 1. Data yang digunakan meliputi data peta jalan Kota Bogor yang merupakan data node dan edge yang akan merepresentasikan jalur distribusi. Data jarak antar node didapatkan dari penelitian Priasa (2008), sedangkan data waktu antar node didapatkan melalui survei di lapangan. 2. Penentuan rute optimum hanya memperhatikan satu kali perjalanan dalam proses distribusinya. 3. Pembuatan web client untuk mengimplementasikan perancangan supply chain network. Manfaat Manfaat yang dapat diperoleh dari penelitian ini adalah perancangan supply chain network yang dapat memberikan gambaran pemilihan rute jalur distribusi optimum untuk mencapai lokasi tujuan. TINJAUAN PUSTAKA Supply Chain Management Supply chain management merupakan sebuah proses pengintegrasian yang meliputi proses perancangan, pemeliharan, operasi, dan transportasi pada supply chain untuk menciptakan pelayanan yang lebih baik dan efisien sehingga dapat memuaskan permintaan pasar (Ayers 2001). Apabila mengacu pada sebuah perusahaan manufaktur, kegiatankegiatan utama yang masuk dalam klasifikasi Supply chain management adalah : · Kegiatan merancang produk baru (product development ) Cakupan kegiatan ini antara lain melakukan riset pasar, merancang produk baru, melibatkan supplier dalam perancangan produk baru. · Kegiatan mendapatkan (procurement)

bahan

baku

Cakupan kegiatan ini antara lain memilih supplier, mengevaluasi kinerja supplier, melakukan pembelian bahan baku dan 1

komponen, memonitor supply risk, membina dan memelihara hubungan dengan supplier. · Logistics Cakupan kegiatan ini antara lain perencanaan, implementasi produksi, mengontrol aliran dan penyimpanan bahan baku, layanan, dan berhubungan dengan informasi kebutuhan konsumen. · Information Kegiatan ini meningkatkan hubungan perusahaan dengan supply chain dengan mengimplementasikan aplikasi komputer. · Kegiatan melakukan (distribution).

pengiriman

Kegiatan ini merupakan strategi untuk bersaing yang mencakup perencanaan jaringan distribusi, penjadwalan pengiriman, mencari dan memelihara hubungan dengan perusahaan jasa pengiriman, memonitor service level di tiap pusat distribusi . Supply Chain Network Supply Chain Network merupakan sebuah jaringan dan pilihan distribusi yang melakukan fungsi dalam upaya mendapatkan bahan baku, transportasi bahan baku sampai pada tempat produksi dan distribusi hasil produksi kepada konsumen (Ganeshan & Harrison 1995). Ilustrasi dari proses supply chain network dapat dilihat dalam Gambar 1.

distribusi yang tepat dicapai dengan memilih jalur yang paling optimum antara lokasi asal dan lokasi tujuan (Hugos 2003). Misalkan sebuah perusahaan ingin mendistribusikan produknya ke setiap konsumen, perusahaan harus menentukan jalur distribusi yang tepat. Tujuannya bagi konsumen adalah dapat meningkatkan kepuasan konsumen karena produk yang mereka inginkan bisa mereka terima tepat waktu, sedangkan bagi perusahaan tujuannya adalah mengefisienkan biaya dan meningkatkan kinerja sumber daya manusianya. Algoritme Genetika Algoritme Genetika merupakan suatu metode pencarian yang didasarkan pada mekanisme seleksi alam dan genetika. Algoritme ini tepat digunakan untuk penyelesaian masalah optimasi yang kompleks dan susah diselesaikan dengan menggunakan metode optimasi yang konvensional karena memiliki beberapa keunggulan, yaitu (Sivanandam & Deepa 2008): 1. Algoritme Genetika memproses bentuk pengkodean dari parameter solusi, bukan parameter itu sendiri. 2. Algoritme Genetika melakukan pencarian dalam banyak solusi yang disebut populasi solusi, bukan pada satu solusi. 3. Informasi yang digunakan dalam Algoritme Genetika berasal dari fungsi fitness, bukan dari informasi tambahan. Algoritme yang ditemukan oleh Jhon Holland dan David Goldberg (1975) ini terinspirasi dari prinsip genetika dan seleksi alam (teori evolusi Darwin). Istilah-istilah dalam Algoritme Genetika berhubungan dengan istilah dalam ilmu Biologi. Daftar istilah ilmu Biologi yang digunakan dalam Algoritme Genetika dapat dilihat pada Tabel 1.

Gambar 1 Ilustrasi Supply Chain Network ( Gen & Cheng 2008). Distribusi Salah satu proses dalam supply chain network, yaitu pengiriman barang dan jasa sampai ke konsumen pada waktu yang tepat dan tempat yang tepat. Proses distribusi dipengaruhi oleh keputusan transportasi yang digunakan. Untuk menciptakan proses distribusi yang efektif dan efisien maka perusahaan harus merancang jalur distribusi yang tepat. Jalur

Tabel 1 Daftar istilah Biologi yang digunakan dalam Algoritme Genetika. Istilah Biologi Gen

Definisi dalam Algoritme Genetika Sebuah nilai yang menyatakan satuan dasar yang membentuk suatu arti tertentu. Gen bisa berupa nilai biner, float, integer maupun karakter.

Kromosom

Gabungan gen-gen yang akan membentuk nilai tertentu, sering dikenal sebagai String Gen. 2

Istilah Biologi

Definisi dalam Genetika

Algoritme

Allele

Nilai dari Gen.

Lokus

Posisi gen dalam kromosom.

Individu / kromosom

Satu nilai yang menyatakan salah satu solusi yang mungkin dari permasalahan yang diangkat.

Populasi

Sekumpulan individu yang akan diproses bersama dalam satu siklus proses evolusi.

Generasi

Menyatakan satu satuan siklus proses evolusi.

Nilai Fitness/ fitness

Menyatakan seberapa baik nilai dari solusi yang didapatkan.

Crossover

Pertukaran kromosom kromosom induk.

Mutasi

Perubahan nilai kromosom.

antar

Algoritme Genetika dikarakterisasi dalam lima komponen penting, yaitu:

kembali. Populasi yang baru dibentuk dari seleksi individu-individu dalam beberapa generasi sehingga didapatkan individu yang terbaik. Individu terbaik inilah yang diharapkan akan menjadi solusi optimal atau suboptimal dari masalah yang diangkat (Gen & Cheng 2000). Struktur dari Algoritme Genetika sebagai berikut : Prosedur : Algoritme Genetika begin t ß 0; inisialisasi P(t); evaluasi C(t); while(I <= maksimum iterasi) do begin rekombinasi P(t); evaluasi C(t); pilih P(t+1) dari P(t) C(t); I ß i+1; end end

dan

Secara umum diagram dari mekanisme kerja Algoritme Genetika ini adalah seperti yang terlihat dalam Gambar 2.

1. Merepresentasikan kromosom yang menyatakan salah satu solusi dari masalah yang diangkat. 2. Inisialisasi populasi yaitu pembentukan populasi awal. 3. Mendefinisikan nilai fitness yang merupakan ukuran baik tidaknya sebuah individu dalam proses evaluasi. 4. Menghasilkan populasi baru dari populasi yang ada melalui proses genetika (crossover dan mutasi ). 5. Nilai dari parameter Algoritme Genetika yang terdiri atas ukuran populasi, probabilitas proses genetika dan banyaknya generasi. Algoritme Genetika memelihara populasi dari individu untuk tiap generasi. Setiap individu dievaluasi untuk diberikan nilai fitnessnya. Ada dua jenis transformasi yang digunakan dalam Algoritme Genetika yaitu Mutasi dan Crossover (pindah silang). Mutasi yaitu membentuk individu baru dengan cara mengubah satu individu tertentu saja, sedangkan crossover yaitu membentuk individu baru dengan cara mengombinasikan bagianbagian dari dua individu. Transformasi tersebut akan menghasilkan individu baru, yang dikenal sebagai offstring yang akan dilakukan evaluasi

Gambar 2 Diagram Alir Algoritme Genetika. Dalam algoritme ini dikenal istilah search space yaitu ruang dari semua solusi pencarian yang mungkin. Secara garis besar, langkahlangkah dari Algoritme Genetika ini dapat didefinisikan sebagai berikut: 3

1. Representasi Kromosom Representasi kromosom adalah proses pertama yang harus dilakukan sebelum inisialisasi populasi, proses ini dikenal dengan encoding. Proses ini berfokus untuk mengonversi masalah yang dihadapi ke dalam bentuk kromosom yang merupakan alternatif solusi dari masalah tersebut. Tata cara untuk menerjemahkan masalah yang dihadapi ke dalam framework Algoritme Genetika disebut encoding schema. Proses ini merupakan tahapan penting karena akan menentukan ketepatan solusi dari masalah yang dihadapi. 2. Inisialisasi Populasi Populasi awal ini dibangkitkan secara acak sehingga didapatkan beberapa kromosom yang merupakan alternatif solusi awal. Dalam populasi tersebut terdapat anggota populasi yang disebut dengan kromosom, yang berisikan informasi solusi dari sekian banyak alternatif solusi masalah yang dihadapi. Banyaknya kromosom dalam satu populasi ditentukan oleh ukuran populasi.

mutasi. Metode seleksi yang biasa digunakan dalam Algoritme Genetika adalah metode roulette wheel. Metode ini mencari populasi baru berdasarkan nilai fitness-nya. 6. Crossover Crossover merupakan proses mengombinasikan dua individu untuk memperoleh individu-individu baru yang diharapkan mempunyai nilai fitness yang lebih baik. Tidak semua pasangan induk yang akan mengalami crossover, banyaknya pasangan induk yang akan mengalami crossover akan ditentukan dengan nilai crossover probability. Crossover probability adalah sebuah parameter dalam Algoritme Genetika yang menggambarkan berapa seringnya crossover dilakukan. Metode crossover yang digunakan adalah Weight Mapping Crossover (WMX). Ilustrasi proses WMX dapat dilihat dalam Gambar 3.

3. Fungsi Fitness Kromosom-kromosom akan mengalami proses evolusi melalui sejumlah iterasi, proses ini disebut generasi. Pada setiap proses generasi, kromosom-kromosom akan dievaluasi menggunakan suatu fungsi yang disebut dengan fungsi fitness. Setiap generasi akan menghasilkan kromosom-kromosom baru yang dibentuk dari generasi sebelumnya. Fungsi fitness adalah fungsi yang digunakan untuk mengukur nilai kecocokan suatu kromosom. Nilai yang dihasilkan dari fungsi fitness disebut dengan nilai fitness. Nilai fitness ini akan menggambarkan seberapa baik solusi yang didapat. 4. Elitisme Suatu teknik yang dilakukan untuk mempertahankan suatu individu terbaik yang memiliki nilai fitness tertinggi agar tidak mengalami kerusakan yang diakibatkan oleh proses genetika, sehingga individu tersebut dapat bertahan hidup untuk generasi selanjutnya. 5. Seleksi Proses pembentukan generasi baru ini dilakukan melalui tahap seleksi. Seleksi adalah proses memilih individu terbaik dari sebuah populasi dengan mencari kromosom dengan nilai fitness terbaik, dan kemudian dilanjutkan ke proses berikutnya yaitu crossover dan

Gambar 3 Proses Weight Mapping Crossover. 7. Mutasi Mutasi adalah proses penggantian gen dengan nilai inversinya. Proses ini dilakukan secara acak pada posisi gen tertentu pada individu-individu yang terpilih untuk dimutasikan. Banyaknya individu yang mengalami mutasi ditentukan oleh besarnya mutation probability. Metode mutasi yang digunakan adalah swap mutation. Ilustrasi proses swap mutation dapat dilihat dalam Gambar 4. 4

Gambar 4 Proses Swap Mutation. 8. Evaluasi Solusi dan Kriteria Berhenti Proses evaluasi solusi ini akan mengevaluasi setiap populasi dengan menghitung nilai fitness setiap kromosom sampai terpenuhi kriteria berhenti. Apabila kriteria berhenti belum terpenuhi maka akan dibentuk lagi generasi yang baru dengan mengulangi langkah inisialisasi populasi. Beberapa kriteria berhenti yang sering digunakan dalam Algoritme Genetika antar lain: · Berhenti pada maksimum generasi tertentu. · Berhenti apabila dalam n generasi berikut tidak didapatkan nilai fitness yang lebih tinggi/rendah (stall generation). Kromosom-kromosom yang memiliki nilai fitness yang baik akan memiliki peluang yang lebih tinggi untuk terseleksi. Setelah dilakukan beberapa kali proses generasi, Algoritme Genetika akan menunjukkan kromosomkromosom yang terbaik, yang diharapkan merupakan solusi optimal atau mendekati optimal dari masalah yang dihadapi. METODE PENELITIAN Penelitian ini akan dikerjakan dalam beberapa tahap. Tahap-tahap tersebut disesuaikan dengan metode penelitian yang dapat dilihat pada Gambar 5. Studi Pustaka Dalam tahap ini, kegiatan yang dilakukan adalah mengumpulkan semua informasi atau literatur yang terkait dengan penelitian. Informasi tersebut akan didapatkan dari textbook, jurnal, buku, internet, dan artikel yang membahas tentang Algoritme Genetika dalam menyelesaikan masalah pencarian rute optimum. Selain mencari literatur terkait dengan Algoritme Genetika, literatur yang juga akan dicari yaitu terkait dengan cara dan tutorial pembuatan web client. Literatur-literatur yang digunakan dapat dilihat pada bagian daftar pustaka.

Gambar 5 Metodologi Penelitian. Perumusan Masalah Menentukan rute optimum jalur distribusi dengan menggunakan Algoritme Genetika. Penyelesaian masalah untuk menentukan rute optimum jalur distribusi ini akan sulit dan lama jika dilakukan secara manual. Algoritme Genetika digunakan sebagai cara untuk memecahkan masalah tersebut sehingga diharapkan rute optimum jalur distribusi dapat dicari dengan waktu yang lebih cepat. Pembentukan Data Data yang akan digunakan dalam penelitian ini adalah data peta jalan Kota Bogor. Data peta tersebut akan diubah ke dalam bentuk node dan edge yang merepresentasikan jalur distribusi. Node adalah titik persimpangan jalan sedangkan edge menyatakan ruas jalan yang ada. Pembentukan node dan edge dapat dilihat pada Gambar 6. Dari gambar tersebut terlihat bahwa node 1 menghubungkan dua jalan yaitu jalan Jalak Harupat dan jalan Pangrango, sedangkan node 2 akan menghubungkan jalan Pajajaran dengan jalan Jalak Harupat. Edge yang 5

menghubungkan antara node 1 dan node 2 dinamakan Jalak Harupat.

a) Representasi Kromosom dengan Metode Binary Encoding and Decoding. Pada proses encoding, metode Binary Encoding and Decoding ini menggunakan representasi kromosom dalam bentuk bit string. Panjang kromosom dipengaruhi oleh jumlah node. Dari data yang ada terdapat 44 node. Oleh sebab itu panjang kromosom dinyatakan dalam 44 gen. Sebagai contoh dari representasi kromosom yang dihasilkan adalah sebagai berikut : 01100101000010000101011101000101011101 011011.

Gambar 6 Peta Jalan Kota Bogor (http://maps.google.com). Semua data yang dibutuhkan antara lain data node, data edge, data jarak antar node, data waktu antar node, titik asal dan titik tujuan. Data jarak antar node didapatkan dari penelitian Priasa (2008), sedangkan data waktu antar node didapatkan melalui survei di lapangan. Data waktu yang digunakan ini merupakan data waktu rata-rata dari tiga kali penghitungan waktu. Data node yang merupakan representasi dari peta jalan Kota Bogor selengkapnya dapat dilihat dalam Lampiran 1. Data edge secara lengkap dapat dilihat dalam Lampiran 2. Representasi peta jalan Kota Bogor dalam bentuk graf secara lengkap dapat dilihat dalam Lampiran 3. Pengembangan Sistem Pengembangan sistem mengikuti tahapan yang ada dalam Algoritme Genetika yaitu representasi kromosom, penentuan populasi awal, menghitung nilai fitness, proses elitisme, proses seleksi, proses crossover, proses mutasi, evaluasi dan kriteria berhenti. 1. Representasi Kromosom Dalam penelitian ini representasi kromosom menggunakan dua metode, yaitu Binary Encoding and Decoding dan Priority-based Encoding and Decoding. Encoding merupakan proses untuk menerjemahkan masalah ke dalam bentuk kromosom, sedangkan decoding merupakan proses untuk membangkitkan rute dari kromosom yang dihasilkan dari proses encoding. Dari dua metode representasi yang digunakan dipilih salah satu metode representasi kromosom yang paling tepat.

Kromosom di atas dibangkitkan secara acak. Kromosom ini selanjutnya akan dipotong tiap dua gen. Proses pemotongan kromosom dapat dilihat sebagai berikut : 01|10|01|01|00|00|10|00|01|01|01|11|01|00|01|01| 01|11|01|01|10|11. Pada proses decoding, kromosom dikonversi ke dalam bentuk percabangan, sesuai dengan nilai desimal dari kromosom yang sebelumnya sudah dilakukan pemotongan. Sebagai contoh pada Gambar 7.

Gambar 7 Contoh Representasi Graf Peta Jalan (Thiang dkk 2001 ). Gambar di atas memperlihatkan ada 8 node, maka jumlah gen yang akan digunakan adalah 8 gen. Pada proses decoding kromosom ini, representasi kromosom akan dikonversi ke dalam bentuk biner sehingga untuk nilai 0, 1, 2, dan 3 secara berurutan akan menjadi 00, 01, 10, 11. Misalkan salah satu contoh representasi kromosom yang dihasilkan adalah 00101010, maka representasi kromosom tersebut akan dikonversi menjadi 0222. Rute ditentukan berdasarkan cabang yang ada. Sebagai contoh pada Gambar 7, misal node awalnya adalah 1, dan setelah mengalami decoding kromosom dihasilkan cabang 0222. Proses penentuan rute adalah sebagai berikut : Cabang : 0 2 2 2 Rute : 1 à 2 à 3 à 4 à 5.

6

b) Representasi Kromosom dengan Metode Priority-based Encoding and Decoding. Pada proses encoding, metode ini mengkategorikan kromosom dalam dua faktor, yaitu locus dan allele. Locus menyatakan posisi gen dalam kromosom, sedangkan allele menyatakan nilai dari gen. Dalam metode ini, posisi gen digunakan untuk menyatakan ID node sedangkan nilai dari gen menyatakan prioritas node yang akan digunakan pada proses decoding. Ilustrasi proses encoding dapat dilihat pada Gambar 8.

Gambar 8 Ilustrasi Proses Encoding Kromosom. Posisi gen (lokus) 1 menyatakan node ID 1 dengan prioritas 11, posisi gen 2 menyatakan node ID 2 dengan prioritas 1, posisi gen 3 menyatakan node ID 3 dengan prioritas 10 dan seterusnya. Representasi kromosom yang digunakan dalam penelitian ini adalah berbentuk integer. Panjang kromosom dipengaruhi oleh jumlah node. Dari data yang ada terdapat 44 node, Oleh sebab itu panjang kromosom dinyatakan dalam 44 gen. Kromosom yang dihasilkan terdiri atas gen yang berbentuk integer dengan nilai 1 sampai 44 yang dibangkitkan secara acak. Pseudocode untuk membangkitkan kromosom secara acak adalah sebagai berikut : Prosedur : Priority-based Encoding Input : Jumlah node (n) Output : kromosom (v) Mulai for i=1 hingga n v[i] ß i; for i=1 hingga [n/2] ulangi j ß random[1,n]; l ß random[1,n]; if j != l swap(v[j],v[l]); output v; akhir

Sebagai contoh dari representasi kromosom yang dihasilkan adalah sebagai berikut : 4 21 5 12 39 6 3 38 16 29 10 1 18 7 25 43 19 17 37 34 2 44 22 20 31 26 23 14 36 35 24 13 40 41 42 27 32 33 9 15 28 8 11 30. Pada proses decoding, kromosom yang telah dihasilkan akan diubah ke dalam bentuk rute distribusi. Untuk menentukan rute digunakan prioritas gen. Sebagai contoh pada Gambar 9.

Gambar 9 Contoh Representasi Peta Jalan Dalam Bentuk Graf. Dari gambar di atas misalkan node awal adalah 1, maka node berikutnya yang mungkin dituju adalah node 2, 3, dan 4. Kemudian misalkan kromosom yang dihasilkan adalah seperti pada Gambar 8, dapat dilihat bahwa prioritas node 2, 3 dan 4 secara berurutan adalah 1, 10, dan 3. Node 3 memiliki prioritas paling besar sehingga node berikutnya yang akan dipilih adalah node 3. Node berikutnya yang mungkin dipilih dari node 3 adalah node 4, 6, dan 7. Node 6 memiliki prioritas paling besar sehingga node berikutnya yang terpilih adalah node 6 dan seterusnya. Proses decoding dilakukan hingga mencapai gen terakhir atau proses ini akan berhenti jika node tujuan telah dicapai. Ilustrasi proses decoding ini dapat dilihat dalam Gambar 10.

Gambar 10 Ilustrasi Proses Decoding Kromosom. Pseudocode proses decoding adalah sebagai berikut: Prosedur : Priority-based Encoding Input : jumlah node (n), kromosom (v), node tetangga dengan node i (s), node awal (i) dan node tujuan (k). Output : rute (p) Mulai v(i) ß 0; j’ ß maxPrioritas(v[j], j€s) Jika j’ != k Jika j’ != 0 v[j’] ß 0; p ß j’; i ß j’; Lainnya p ß j’; Selesai Akhir.

7

2. Penentuan Populasi Awal Populasi merupakan kumpulan kromosom yang merupakan alternatif solusi. Hasil dari tahap representasi kromosom adalah sebuah kromosom yang terdiri atas 44 gen. Ukuran populasi adalah jumlah kromosom yang ada dalam satu populasi. Dalam penelitian ini ukuran populasi yang digunakan adalah 300 kromosom. Sehingga dari proses encoding akan dihasilkan sebuah array dua dimensi berukuran 300 x 44, jumlah baris dalam array ini menunjukkan banyaknya kromosom dan jumlah kolom menunjukkan banyaknya gen. Setelah proses decoding, dilakukan evaluasi dengan memilih kromosom yang valid yaitu kromosom yang mengandung node tujuan sehingga populasi awal yang dihasilkan terdiri atas kromosom mengandung informasi node tujuan. 3. Menghitung Nilai Fitness · Hitung Jarak dan Waktu Mekanisme penghitungan jarak dan waktu sesuai dengan rute distribusi yang dilalui, dimulai dari node awal hingga mencapai node tujuan. Jarak dan waktu yang dihasilkan akan digunakan untuk mencari nilai fitness kromosom. · Menghitung Nilai Fitness Kromosom Penelitian ini akan menentukan rute optimum yang dipengaruhi oleh jarak terdekat dan waktu tercepat. Oleh karena itu, fungsi fitness yang akan digunakan dalam penelitian ini ditunjukkan dalam Persamaan 1. (1) , f(x,t) adalah fungsi fitness. j adalah jumlah hop yang diperlukan hingga mencapai titik tujuan, (hop adalah proses perpindahan dari satu titik ke titik lain yang merupakan tetangganya). x adalah jarak antar titik, t adalah waktu antar titik, v adalah kecepatan konstan, %D adalah bobot persentase untuk jarak, dan %W adalah bobot persentase untuk waktu. Optimasi yang diinginkan dalam penelitian ini adalah mencari waktu dan jarak paling minimal, berarti kromosom yang terseleksi adalah kromosom dengan nilai fitness yang terkecil. Metode yang digunakan adalah roulette-wheel, yaitu metode dimana peluang tiap kromosom untuk terpilih adalah sebanding dengan nilai fitness-nya. Artinya semakin besar nilai fitness-nya maka akan semakin besar

peluang untuk terseleksi. Oleh karena itu fungsi fitness-nya akan dibentuk seperti Persamaan 2. ,

(2)

Dengan fn adalah nilai fitness sebelumnya, fn’ adalah nilai fitness baru, fmax adalah nilai fitness maksimum, dan fmin adalah nilai fitness minimum. 4. Proses Elitisme Kromosom terbaik akan bertahan untuk generasi selanjutnya. Supaya kromosom terbaik tidak rusak karena proses algoritme maka dilakukan elitisme. Caranya adalah Jika jumlah populasi genap maka elitisme dalam penelitian ini dilakukan dengan meng-copy dua buah kromosom yang memiliki nilai fitness terbaik. Jika jumlah populasi ganjil maka hanya mengcopy satu buah kromosom yang memiliki nilai fitness terbaik. 5. Proses Seleksi Kromosom Metode yang digunakan adalah roulettewheel, yaitu metode dimana peluang tiap kromosom untuk terpilih adalah sebanding dengan nilai fitness-nya. Artinya semakin besar nilai fitness-nya maka akan semakin besar peluang untuk terseleksi. Pertama, dibuat interval nilai kumulatif (dalam interval [0,1]) dari nilai fitness dibagi total nilai fitness dari semua kromosom. Sebuah kromosom akan terpilih jika bilangan random yang dibangkitkan berada dalam interval kumulatifnya. 6. Proses Crossover Metode crossover yang digunakan dalam penelitian ini adalah weight mapping crossover (WMX). WMX merupakan perluasan dari mekanisme single point crossover dimana hanya ada satu titik potong. Proses penentuan titik potong dilakukan secara acak. Tidak semua kromosom yang akan mengalami crossover, banyaknya kromosom yang akan mengalami crossover ditentukan oleh crossover probability. Kromosom yang memiliki nilai random lebih kecil dari crossover probability maka kromosom tersebut akan mengalami crossover. Ilustrasi proses WMX dapat dilihat dalam Gambar 3. Dalam penelitian ini proses WMX dilakukan dalam 4 langkah yaitu : 1. Memilih titik potong dari dua kromosom hasil seleksi. Pemilihan titik potong ini dilakukan secara acak. Misalkan titik potong yang didapat adalah 40. kromosom induk akan dilakukan crossover 8

pada gen ke-41. Contoh kromosom induk adalah sebagai berikut : Kromosom satu : 23 39 42 5 38 1 7 24 25 30 16 26 15 41 11 17 44 2 27 29 19 20 37 8 4 35 3 28 21 43 12 40 10 22 31 13 9 36 18 6 | 34 33 32 14 Kromosom dua : 41 33 30 7 39 10 14 25 42 17 18 11 27 21 44 31 37 8 43 23 35 16 28 22 19 38 4 13 3 9 32 2 12 34 40 1 29 20 15 5 | 26 36 6 24 2. Menggantikan substring antara kromosom induk. Setelah pemotongan pada gen ke-41 maka dilakukan penggantian nilai gen antara kromosom induk sehingga kromosom baru akan terbentuk sebagai berikut : Kromosom satu : 23 39 42 5 38 1 7 24 25 30 16 26 15 41 11 17 44 2 27 29 19 20 37 8 4 35 3 28 21 43 12 40 10 22 31 13 9 36 18 6 | 26 36 6 24

Kromosom dua baru : 41 33 30 7 39 10 14 25 42 17 18 11 27 21 44 31 37 8 43 23 35 16 28 22 19 38 4 13 3 9 32 2 12 34 40 1 29 20 15 5 36 26 24 6 7. Proses Mutasi Metode mutasi yang digunakan dalam penelitian ini adalah swap mutation. Tidak semua kromosom yang akan mengalami mutasi, banyaknya kromosom yang akan mengalami mutasi ditentukan oleh mutation probability. Kromosom yang memiliki nilai random lebih kecil dari mutation probability maka kromosom tersebut akan mengalam mutasi. Swap mutation akan memilih dua posisi gen secara acak dan kemudian dilakukan penggantian posisi. Misalkan posisi gen yang terpilih adalah 5 dan 42 maka proses swap mutation akan dilakukan sebagai berikut : 23 39 42 5 38 1 7 24 25 30 16 26 15 41 11 17 44 2 27 29 19 20 37 8 4 35 3 28 21 43 12 40 10 22 31 13 9 36 18 6 33 34 14 32

Kromosom dua :

Kromosom baru yang dihasilkan oleh proses swap mutation adalah :

41 33 30 7 39 10 14 25 42 17 18 11 27 21 44 31 37 8 43 23 35 16 28 22 19 38 4 13 3 9 32 2 12 34 40 1 29 20 15 5 | 34 33 32 14

23 39 42 5 34 1 7 24 25 30 16 26 15 41 11 17 44 2 27 29 19 20 37 8 4 35 3 28 21 43 12 40 10 22 31 13 9 36 18 6 33 38 14 32

3. Mapping nilai gen pada posisi yang sesuai.

8. Evaluasi dan Kriteria Berhenti

Setelah dilakukan penggantian substring dapat dilihat bahwa nilai gen 26, 36, 6 dan 24 muncul dua kali dalam kromosom satu. Hal yang sama juga dialami kromosom dua, sehingga harus dilakukan mapping nilai gen ke posisi yang sesuai dengan cara melakukan sorting. Mapping yang dihasilkan adalah sebagai berikut :

Dalam penelitian ini Algoritme Genetika akan berhenti jika memenuhi salah satu dari dua kriteria berhenti yaitu maksimum generasi dan stall generation. Dalam setiap generasi dilakukan proses evaluasi dengan menghitung nilai fitness dari setiap kromosom. Maksimum generasi yang ditentukan adalah 20 generasi, sehingga Algoritme Genetika akan berhenti jika sudah mencapai 20 generasi. Algoritme Genetika juga akan berhenti jika nilai fitness terbesar yang dihasilkan tidak berubah selama beberapa generasi (stall generation).

26 36 6 24 à

6

34 33 32 14 à

14 32 33 34

24 26 36

6

↔ 14

24 ↔ 32 26 ↔ 33 36 ↔ 34

4. Membangkitkan kromosom baru dengan menerapkan hubungan mapping. Kromosom baru yang dihasilkan dengan menerapkan hubungan mapping adalah sebagai berikut : Kromosom satu baru : 23 39 42 5 38 1 7 24 25 30 16 26 15 41 11 17 44 2 27 29 19 20 37 8 4 35 3 28 21 43 12 40 10 22 31 13 9 36 18 6 33 34 14 32

Pengujian dan Analisis Sistem Sistem Algoritme Genetika untuk menentukan rute distribusi optimum yang telah dihasilkan akan diimplementasikan dalam bentuk web client. Proses pengujian dan analisis sistem Algoritme Genetika akan dilakukan dalam dua tahap. Tahap pertama, pengujian sistem dilakukan dengan mengubah nilai parameter Algoritme Genetika yang digunakan, yaitu nilai crossover probability, nilai mutation probability, ukuran populasi dan stall generation. Tahap kedua, menguji rute distribusi optimum yang dihasilkan dari sistem berbasis web client. Input yang dimasukkan 9

oleh pengguna sistem adalah node awal dan node tujuan pengguna. Lingkungan Pengembangan Sistem Implementasi Algoritme Genetika dalam bentuk web client menggunakan bahasa pemrograman PHP dan DBMS MySQL. Spesifikasi perangkat keras dan perangkat lunak komputer yang digunakan dalam penelitian ini sebagai berikut : · Perangkat keras : Prosesor AMD Turion X2 dual core CPU 2.0 GHz, Memori 2.5 GB DDR2, hardisk 160 GB, mouse. · Perangkat lunak : Microsoft Windows XP SP 2, XAMPP 1.7.1, PHP 5.2.6, Firefox 3.0.6, Notepad++ . HASIL DAN PEMBAHASAN Perancangan supply chain network dalam menentukan jalur distribusi optimum dengan menggunakan Algoritme Genetika diawali dengan pembentukan representasi peta jalan Kota Bogor ke dalam bentuk graf. Perancangan tersebut diimplementasikan dalam web client dengan tujuan mempermudah pengguna dalam menggunakan rancangan tersebut. Tampilan web client yang telah dibuat dapat dilihat pada Lampiran 4. Algoritme Genetika yang digunakan untuk menentukan rute optimum jalur distribusi ini terdiri atas beberapa tahapan, yaitu representasi kromosom, penentuan populasi awal, menghitung nilai fitness, proses elitisme, proses seleksi, crossover, mutasi dan evaluasi kriteria berhenti algoritme. Untuk tahapan representasi kromosom, dari dua metode representasi kromosom yang dicoba dipilih salah satu metode representasi kromosom yang paling tepat. Dari percobaan yang dilakukan sebelumnya dalam penelitian ini menunjukkan bahwa metode Binary Encoding and Decoding membutuhkan waktu eksekusi program yang lebih lama daripada metode representasi kromosom Priority-based Encoding and Decoding. Oleh karena itu, metode Prioritybased Encoding and Decoding lebih tepat untuk merepresentasikan masalah yang dihadapi ke dalam bentuk kromosom sehingga penelitian ini menggunakan representasi kromosom dengan metode Priority-based Encoding and Decoding. Algoritme Genetika memerlukan pemilihan parameter yang tepat agar dapat memaksimalkan kinerja algoritme tersebut. Oleh karena itu tahap pengujian dalam penelitian ini terdiri atas dua kali percobaan. Percobaan pertama adalah menentukan

parameter optimal Algoritme Genetika. Percobaan kedua adalah menguji hasil keluaran sistem Algoritme Genetika berbasis web. Percobaan 1 Percobaan ini bertujuan menentukan parameter Algoritme Genetika yang paling optimal, yang terdiri atas pengujian parameter ukuran populasi, crossover probability, mutation probability, dan stall generation. Percobaan dilakukan dengan pengulangan masing-masing 10 kali dan untuk setiap percobaan node awal dan node tujuan ditetapkan masing-masing secara berurutan yaitu Node 21 dan Node 24. Percobaan untuk menentukan parameter ukuran populasi yang optimal dilakukan dengan cara mengubah nilai parameter ukuran populasi, sedangkan parameter yang lain dibuat tetap. Percobaan untuk menentukan parameter optimal crossover probability, mutation probability, dan stall generation dilakukan dengan cara yang sama dan parameter bukan uji dibuat tetap. Dalam menentukan parameter optimal ukuran populasi, parameter Algoritme Genetika yang terdiri atas crossover probability, mutation probability, dan stall generation nilainya dibuat tetap, secara berurutan yaitu 0.5, 0.1, dan 5. Nilai parameter ukuran populasi yang akan diuji adalah 50, 100 , 150, 200, 250, 300, 350, dan 400. Pengujian akan dilakukan masing-masing sebanyak 10 kali pengulangan. Hasil pengujian dapat dilihat pada Lampiran 5. Parameter ukuran populasi yang optimal didapatkan dengan memilih nilai ukuran populasi yang memiliki nilai fitness rata-rata paling kecil sehingga akan menghasilkan rute yang paling optimum. Parameter dan hasil uji dapat dilihat pada Tabel 2. Tabel 2 Parameter ukuran populasi dengan nilai fitness rata-rata. Ukuran Populasi

Crossover Probability = 0.5 Mutation Probability = 0.1 Stall Generation = 5

50

4580.6

100

4474.2

150

4350.6

200

4254.1

250

4312.1

300

4150

350

4150

400

4150 10

Pada Gambar 11 dapat dilihat hubungan parameter ukuran populasi dengan rata-rata nilai fitness.

Nilai parameter crossover probability yang akan diuji adalah 0.5, 0.6, 0.7, 0.8, dan 0.9. Ukuran populasi yang digunakan dalam pengujian ini adalah 300 kromosom yang merupakan ukuran populasi optimal berdasarkan hasil percobaan sebelumnya. Hasil pengujian dapat dilihat pada Lampiran 6. Parameter dan hasil uji dapat dilihat pada Tabel 3. Tabel 3 Parameter crossover probability dengan nilai fitness rata-rata. Crossover Probability

Ukuran Populasi = 300 Mutation Probability = 0.1 Stall Generation = 5

0.5

4150

0.6

4150

Gambar 11 Hubungan Ukuran Populasi dan Nilai Fitness Rata-Rata.

0.7

4150

0.8

4150

Dari Gambar 11 dapat dilihat kecenderungan bahwa semakin besar ukuran populasi akan menghasilkan nilai fitness ratarata yang sama atau semakin kecil. Ukuran populasi yang menghasilkan nilai fitness ratarata paling kecil adalah 300, 350, dan 400 kromosom dengan nilai fitness rata-rata 4150. Namun untuk memilih nilai ukuran populasi yang lebih baik untuk digunakan adalah dilihat dari hubungan ukuran populasi dengan waktu eksekusi program. Pada Gambar 12 diperlihatkan hubungan nilai ukuran populasi dengan waktu eksekusi program. Pada Gambar 12 dapat dilihat bahwa semakin besar nilai ukuran populasi maka waktu eksekusi yang diperlukan akan semakin lama, sehingga hasil pengujian menunjukkan bahwa parameter ukuran populasi yang optimal adalah 300 kromosom.

0.9

4150

Pada Gambar 13 diperlihatkan hubungan parameter crossover probability dengan nilai fitness rata-rata. Pada Gambar 13 dapat dilihat bahwa untuk setiap nilai crossover probability akan menghasilkan nilai fitness rata-rata yang sama.

Gambar 13 Hubungan Crossover Probability dan Nilai Fitness.

Gambar 12 Hubungan Ukuran Populasi dan Waktu Eksekusi Program.

Hal ini memperlihatkan bahwa semua nilai crossover probability tersebut menghasilkan nilai rata-rata fitness optimum, namun untuk memilih nilai crossover probability yang lebih baik untuk digunakan adalah dilihat dari hubungan antara nilai crossover probability dengan akhir generasi yang dihasilkan yang dapat dilihat pada Gambar 14.

11

Pada Gambar 15 dapat dilihat hubungan parameter mutation probability dengan nilai fitness rata-rata.

Gambar 14 Hubungan Crossover Probability dan Akhir Generasi. Gambar 14 diperlihatkan semua nilai crossover probability yang menghasilkan nilai fitness rata-rata sama. Dari nilai crossover probability ini dapat dilihat perbedaan akhir generasi yang dihasilkan. Akhir generasi ini memperlihatkan penggunaan crossover probability, semakin besar akhir generasi yang didapatkan untuk menghasilkan rute optimum maka crossover probability yang menghasilkan akhir generasi tersebut akan semakin baik digunakan. Hasil pengujian menunjukkan bahwa parameter crossover probability yang optimal adalah 0.6. Nilai parameter mutation probability yang akan diuji adalah 0.1, 0.2, 0.3, 0.4, 0.5, dan 0.6. Parameter ukuran populasi dan crossover probability yang digunakan dalam pengujian ini secara berurutan adalah 300 dan 0.6 yang merupakan parameter optimal berdasarkan hasil percobaan sebelumnya. Hasil pengujian dapat dilihat pada Lampiran 7. Parameter dan hasil uji dapat dilihat pada Tabel 4.

Gambar 15 Hubungan Mutation Probability dan Nilai Fitness. Dari Gambar 15 dapat dilihat bahwa nilai mutation probability 0.1, 0.2, 0.3, 0.4, 0.5, dan 0.6 menghasilkan nilai fitness rata-rata yang sama sehingga dari hubungan ini tidak bisa ditentukan nilai parameter mutation probability optimal. Penentuan parameter mutation probability yang lebih baik untuk digunakan adalah dilihat dari hubungan antara nilai mutation probability dengan akhir generasi yang dihasilkan. Hubungan parameter mutation probability dengan akhir generasi rata-rata dapat dilihat pada Gambar 16.

Tabel 4 Parameter mutation probability dengan nilai fitness rata-rata. Mutation Probability

Ukuran Populasi = 300 Crossover Probability = 0.6 Stall Generation = 5

0.1

4150

0.2

4150

0.3

4150

0.4

4150

0.5

4150

0.6

4150

Gambar 16 Hubungan Mutation Probability dan Akhir Generasi. Pada Gambar 16 ditunjukkan semua nilai mutation probability yang menghasilkan nilai fitness rata-rata sama. Dari nilai-nilai mutation probability ini dapat dilihat perbedaan akhir generasi yang dihasilkan. Akhir generasi ini 12

memperlihatkan penggunaan mutation probability, semakin besar akhir generasi yang didapatkan untuk menghasilkan rute optimum maka mutation probability yang menghasilkan akhir generasi tersebut akan semakin baik digunakan. Hasil pengujian menunjukkan bahwa parameter mutation probability yang optimal adalah 0.5.

Dari Gambar 17 dapat dilihat bahwa semua nilai stall generation menghasilkan nilai fitness yang sama. Oleh sebab itu hubungan ini tidak bisa digunakan untuk menentukan parameter stall generation yang lebih baik untuk digunakan. Penentuan parameter stall generation ditentukan oleh waktu eksekusi program.

Nilai parameter stall generation yang akan diuji adalah 5, 10, 15, dan 20. Parameter ukuran populasi, crossover probability dan mutation probability yang digunakan dalam pengujian ini secara berurutan adalah 300, 0.6, dan 0.5 yang merupakan parameter optimal berdasarkan hasil percobaan sebelumnya. Salah satu kriteria berhenti Algoritme Genetika adalah apabila nilai fitness tidak mengalami perubahan selama generasi yang ditentukan yang disebut dengan stall generation. Hasil pengujian dapat dilihat pada Lampiran 8. Parameter dan hasil uji dapat dilihat pada Tabel 5.

Pada Gambar 18 ditunjukkan hubungan parameter stall generation dengan waktu eksekusi. Semakin besar nilai parameter stall generation yang digunakan maka akan menghasilkan waktu eksekusi program yang lebih lama. Hasil pengujian menunjukkan bahwa parameter stall generation yang optimal adalah 5, karena dengan menggunakan nilai parameter stall generation yaitu 5 hanya akan membutuhkan waktu eksekusi program rata-rata sebesar 3 detik.

Tabel 5 Parameter stall generation dengan nilai fitness rata-rata. Stall Generation

Ukuran Populasi = 300 Crossover Probability = 0.6 Mutation Probability = 0.5

0.1

4150

0.2

4150

0.3

4150

0.4

4150

0.5

4150

0.6

4150

Gambar 18 Hubungan Stall Generation dan Waktu Eksekusi. Percobaan 2

Hubungan parameter stall generation dengan nilai fitness rata-rata dapat dilihat dalam Gambar 17.

Gambar 17 Hubungan Stall Generation dan Nilai Fitness.

Algoritme Genetika ini diimplementasikan dalam sebuah web client dengan menggunakan parameter optimal yang telah didapatkan yaitu parameter ukuran populasi, crossover probability, mutation probability, dan stall generation secara berurutan adalah 300, 0.6, 0.5, dan 5. Pada percobaan ini akan dilakukan pengujian rute distribusi optimum yang dihasilkan dari sistem berbasis web. Input yang dimasukkan oleh pengguna sistem adalah node awal dan node tujuan pengguna. Pada percobaan ini, node awal yang dipilih adalah Node 21, sedangkan node tujuan yang dipilih adalah Node 42. Rute dari Node 21 menuju Node 42 dapat dilewati melalui beberapa alternatif rute. Beberapa alternatif rute tersebut secara berurutan dapat dilihat pada Gambar 19, Gambar 20, Gambar 21, Gambar 22, Gambar 23, Gambar 24. 13

Gambar 19 Rute Alternatif 1.



Gambar 24 Rute Alternatif 6. Pada Tabel 6 dapat dilihat jarak tempuh, waktu tempuh rata-rata, dan nilai fitness yang dihasilkan dengan menggunakan perhitungan secara manual dari masing-masing gambar di atas. Tabel 6 Jarak tempuh, waktu tempuh rata - rata, dan nilai fitness.



Alternatif Rute

Jarak (meter)

Waktu RataRata (detik)

Nilai Fitness

Rute 1

1189

603

3006.5

Rute 2

1434

202

1473

Rute 3

1217

492

2576.5

Rute 4

1422

616

3175

Rute 5

1586

456

2617

Rute 6

1921

535

3100.5

Dari Tabel 6 dapat dilihat bahwa rute yang paling optimum adalah rute alternatif 2, yaitu Node 21 – 35 – 14 – 15 – 27 – 28 – 42. Rute ini memiliki nilai fitness terkecil sehingga dianggap merupakan rute paling optimum. 14

Rute optimum antarnode sebagai representasi dari jalur distribusi yang dihasilkan oleh sistem berbasis web dengan node awal adalah Node 21 dan node akhir adalah Node 42 sebagai berikut : Rute : Node 21 - Node 35 - Node 14 - Node 15 - Node 27 - Node 28 - Node 42. Jalan yang dilalui : Kapten Muslihat - Kapten Muslihat - Ir.H.Juanda Ir.H.Juanda - Sudirman Sudirman. Jarak tempuh : 1434 meter. Waktu tempuh rata-rata : 202 detik. Tampilan sistem yang menghasilkan rute optimum ini dapat dilihat pada Lampiran 9. Rute optimum yang dihasilkan oleh sistem berbasis web sama dengan rute optimum yang dihasilkan dengan perhitungan secara manual di atas. Hal ini menunjukkan bahwa sistem berbasis web tersebut berjalan dengan baik. KESIMPULAN DAN SARAN Kesimpulan Berdasarkan hasil penelitian beberapa kesimpulan, yaitu :

hubungan crossover probability dan mutation probability dengan akhir generasi algoritme. 5. Hubungan stall generation dengan nilai fitness rata-rata tidak bisa digunakan untuk menentukan nilai parameter stall generation yang paling optimum, sehingga digunakan hubungan stall generation dengan waktu eksekusi program. Saran Beberapa saran yang dapat dilakukan untuk penelitian berikutnya, yaitu: 1. Mengembangkan sistem ini dengan mengakomodasi masalah kepadatan lalu lintas dengan membedakan antara waktu sibuk dan waktu tidak sibuk. 2. Mengembangkan visualisasi yang baik untuk sistem penentuan rute optimum ini. 3. Mempercepat proses eksekusi program Algoritme Genetika dengan memanfaatkan Algoritme Genetika parallel. DAFTAR PUSTAKA

didapat

Ayers B. 2001. Handbook of Supply Chain Management. USA : st.Lucie Press.

1. Perancangan supply chain network dalam menentukan rute optimum jalur distribusi yang dilakukan dengan menggunakan Algoritme Genetika dan diimplementasikan dalam bentuk web client sudah dapat berjalan dengan baik.

Gen M, Cheng R. 2000. Genetic Algorithm and Engineering Optimization. Canada. John Wiley & Sons, Inc.

2. Kinerja Algoritme Genetika dalam penelitian ini yang bertujuan menentukan rute optimum jalur distribusi dalam supply chain network dengan menggunakan data peta jalan Kota Bogor akan mencapai optimal pada kombinasi nilai parameter untuk ukuran populasi, crossover probability, mutation probability, dan stall generation secara berurutan adalah 300, 0.6, 0.5 dan 5. 3. Hubungan jumlah kromosom dengan nilai fitness rata-rata tidak bisa digunakan untuk menentukan nilai parameter ukuran populasi yang paling optimum, sehingga digunakan hubungan jumlah kromosom dan waktu eksekusi program. 4. Hubungan crossover probability dan mutation probability dengan nilai fitness rata-rata tidak bisa digunakan untuk menentukan nilai parameter crossover probability dan mutation probability yang paling optimum, sehingga digunakan

Gen M, Cheng R. 2008. Network Models and Optimization. London. Springer-Verlag London. Goldberg D. 1989. Genetic Algorithms in Search, Optimization, and Machine Learning. England : Addison-Wesley Publishing Company. Hugos M. 2003. Essentials of Supply Chain Management. Canada : John Wiley & Sons, Inc. Priasa A. 2008. Perancangan Supply Chain Network Untuk Penentuan Lokasi Produksi dan Jalur Distribusi [skripsi]. Bogor. Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor. Sivanandam S, Deepa S. 2008. Introduction to Genetic Algorithms. New York. Springerverlag Berlin Heidelberg. Suyanto. 2005. Algoritma Genetika Dalam Matlab. Yogyakarta : Andi. Thiang, dkk. 2001. Implementation of Genetic Algorithm on MCS51 Microcontroller for 15

Finding the Shortest Path. Prosiding seminar of intelligent Technology and Its Aplication (SITIA 2001). ITS-Surabaya. Thiang, dkk. 2002. Pencarian Rute Terpendek Menggunakan Algoritme Genetika. Jurnal Teknik Elektro Vol 2, No 2 September 78 – 83. Yinzhen, dkk. 2006. Faster Genetic Algorithm For Network Paths. The Sixth International Symposium on Operations Research and Its Applications (ISORA’06). Xinjiang, China.

16

LAMPIRAN

Lampiran 1 Data Node Kota Bogor Sebagai Representasi Jalur Distribusi. ID Node 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

Nama Node

Keterangan Node

NODE 1 NODE 2 NODE 3 NODE 4 NODE 5 NODE 6 NODE 7 NODE 8 NODE 9 NODE 10 NODE 11 NODE 12 NODE 13 NODE 14 NODE 15 NODE 16 NODE 17 NODE 18 NODE 19 NODE 20 NODE 21 NODE 22 NODE 23 NODE 24 NODE 25 NODE 26 NODE 27 NODE 28 NODE 29 NODE 30 NODE 31 NODE 32 NODE 33 NODE 34 NODE 35 NODE 36 NODE 37 NODE 38 NODE 39 NODE 40 NODE 41 NODE 42 NODE 43 NODE 44

padjadjaran - ottoiskandar dinata padjadjaran - jalak harupat padjadjaran - pangarango - lodaya 1 padjadjaran - salak - lodaya II salak - jalak harupat padjadjaran - tol jagorawi ottoiskandar dinata - bangka ottoiskandar dinata - roda padjadjaran - sambu banka - sambu ir.h.juanda-ottosikandar dinata-suya kencana roda - surya kencana ir.h.juanda - paledang ir.h.juanda - kapten muslihat ir.h. juanda - gedong sawah 1 paledang - kapten muslihat veteran - merdeka - kapten muslihat perintis kemerdekaan - veteran perintis kemerdekaan - dr semeru merdeka - dr semeru kapten muslihat - raja permas m.a.salmun - raja permas m.a.salmun - merdeka ahmad yani - padjadjaran mandalawangi - pangarango pangrango 1 - jalak harupat ir.h.juanda - jalak harupat - sudirman pengadilan - sudirman ahmad yani-sudirman-re martadinata re. martadinata - merdeka raja permas - dewi sartika dewi satika - m.a.salmun pangrango - salak pangrango - pangrango 1 kapten muslihat - dewi sartika pengadilan - dewi sartika raja permas perintis kemerdekaan perintis kemerdekaan - merdeka mandalawangi - padjadjaran gedong sawah 1 - dewi sartika sawo jajar - sudirman merdeka - mawar ahmad yani - dadali 18

Lampiran 2 Data Edge Kota Bogor Sebagai Representasi Jalur Distribusi. ID Ed ge 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

Nama Edge

Nama Jalan

Node Awal

Node Akhir

Jarak (meter)

Waktu (detik)

E1 E2 E3 E5 E2 E4 E8 E12 E4 E14 E15 E14 E17 E13 E16 E22 E50 E1 E3 E53 E52 E54 E53 E55 E50 E51 E51 E52 E56 E57 E55 E54 E38 E37 E57 E24 E37 E26 E24 E25 E23 E38 E36 E39 E39 E49 E48 E47 E61 E46 E43

padjadjaran padjadjaran ottoiskandar dinata jalak harupat padjadjaran padjadjaran pangrango padjajaran padjajaran lodaya I - Kumbang - lodaya 2 salak lodaya 2 - Kumbang - lodaya 1 padjadjaran padjadjaran salak jalak harupat padjadjaran padjadjaran ottoiskandar dinata ottoiskandar dinata bangka roda ottoiskandar dinata ottoiskandar dinata padjadjaran sambu sambu bangka surya kencana ir.h.juanda ottoiskandar dinata roda paledang ir.h.juanda ir.h.juanda ir.h.juanda ir.h.juanda kapten muslihat ir.h.juanda gedong sawah ir.h.juanda Paledang kapten muslihat kapten muslihat kapten muslihat veteran perintis kemerdekaan perintis kemerdekaan mawar dr.semeru merdeka

1 1 1 2 2 2 3 3 3 3 4 4 4 4 5 5 6 6 7 7 7 8 8 8 9 9 10 10 11 11 11 12 13 13 13 14 14 14 15 15 15 16 16 16 17 17 18 19 19 19 20

6 2 7 26 1 3 34 40 2 4 33 3 24 40 33 27 9 1 1 8 10 12 7 11 6 10 9 7 12 13 8 8 16 14 11 15 13 35 14 41 27 13 21 17 16 18 38 38 43 20 23

390 684 129 269 684 375 79 84 375 552 374 552 2350 395 390 570 304 390 129 503 420 1010 503 127 304 167 167 420 988 274 127 1010 1019 530 274 274 530 259 274 246 328 1019 128 138 138 100 358 180 77 53 225

49 59 22 24 59 42 5 7 42 97 40 97 150 100 42 86 28 49 22 103 92 322 103 43 28 113 113 92 116 101 43 322 127 81 101 39 81 37 39 39 52 127 29 26 26 37 57 57 15 20 123 19

Lampiran 2 Lanjutan 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106

E46 E41 E36 E35 E28 E33 E32 E44 E44 E43 E45 E17 E64 E9 E11 E10 E7 E22 E23 E21 E21 E58 E31 E63 E19 E20 E20 E62 E27 E29 E34 E32 E30 E59 E15 E10 E16 E8 E6 E9 E26 E27 E28 E59 E30 E60 E34 E33 E47 E42 E40 E41 E12 E13 E11

dr.semeru merdeka kapten muslihat raja permas kapten muslihat raja permas m.a.salmun m.a.salmun m.a.salmun merdeka merdeka padjadjaran ahmad yani pangrango mandalawangi pangrango jalak harupat jalak harupat ir.h.juanda sudirman sudirman sudirman pengadilan pemuda/dadali sudirman re martadinata re martadinata merdeka dewi sartika dewi sartika raja permas m.a.salmun dewi sartika sawo jajar salak pangrango salak pangrango pangrango I pangrango kapten muslihat dewi sartika kapten muslihat pengadilan dewi sartika dewi sartika raja permas raja permas perintis kemerdekaan perintis kemerdekaan merdeka merdeka padjajaran padjadjaran mandalawangi

20 20 21 21 21 22 22 22 23 23 23 24 24 25 25 25 26 27 27 27 28 28 28 29 29 29 30 30 31 31 31 32 32 32 33 33 33 34 34 34 35 35 35 36 36 36 37 37 38 38 39 39 40 40 40

19 39 16 37 35 37 32 23 22 20 43 4 44 34 40 33 5 5 15 28 27 42 36 44 42 30 29 43 35 41 37 22 36 42 4 25 5 3 26 25 14 31 21 28 32 41 31 22 19 39 17 20 3 4 25

53 100 128 350 83 300 78 460 460 225 50 2350 460 161 193 246 157 570 328 130 130 360 500 2314 776 1064 1064 770 100 52 120 78 134 461 374 246 390 79 212 161 259 100 83 152 134 237 120 300 180 100 240 100 84 395 193

20 13 29 132 13 134 95 84 84 123 26 150 57 37 19 23 22 86 52 17 17 44 98 205 91 182 182 53 92 50 122 95 24 242 40 23 42 5 33 37 37 92 13 98 24 46 122 134 57 34 41 13 7 100 19 20

Lampiran 2 Lanjutan 107 108 109 110 111 112 113 114 115 116 117

E29 E25 E60 E58 E19 E59 E62 E45 E61 E64 E18

dewi sartika gedong sawah dewi sartika sudirman sudirman sawo jajar merdeka merdeka mawar ahmad yani ahmad yani

41 41 41 42 42 42 43 43 43 44 44

31 15 36 28 29 32 30 23 19 24 29

52 346 237 360 776 461 770 50 77 460 1606

50 39 47 44 91 242 53 26 15 57 205

21

Lampiran 3 Representasi Graf Data Peta Kota Bogor.

22

Lampiran 4 Tampilan Awal dan Hasil Penentuan Rute Optimum Dalam Web.

23

Lampiran 5 Pengujian Ukuran Populasi Optimal 1. Uji ukuran populasi 50 kromosom Ulangan

1 2 3 4 5 6 7 8 9 10 Rata- rata

Nilai Fitness 4712 4150 4965 4553 4150 4759 4759 4553 4150 5055 4580.6

Akhir Generasi 5 5 5 7 5 5 5 5 5 5 5.2

Waktu Eksekusi (dtk) 0 0 0 1 0 0 0 0 0 0 0.1

Rute Optimum

Node 21 - 35 - 14 - 15 - 27 - 28 - 42 - 29 - 44 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 41 - 36 - 28 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 31 - 41 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 31 - 41 - 36 - 28 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 31 - 41 - 36 - 28 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 31 - 41 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 31 - 41 - 36 - 28 - 42 - 29 - 44 - 24

2. Uji ukuran populasi 100 kromosom Ulangan

1 2 3 4 5 6 7 8 9 10 Rata- rata

Nilai Fitness 4150 4150 4553 4553 4965 4150 4553 4553 4150 4965 4474.2

Akhir Generasi 5 5 5 5 5 5 5 5 5 5 5

Waktu Eksekusi (dtk) 1 1 1 1 1 1 1 1 1 1 1

Rute Optimum

Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 31 - 41 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 31 - 41 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 41 - 36 - 28 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 31 - 41 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 31 - 41 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 41 - 36 - 28 - 27 - 5 - 33 - 4 - 24


1 2 3 4 5 6 7 8 9 10 Rata- rata

Nilai Fitness 4553 4150 4150 5115 4150 4150 4788 4150 4150 4150 4350.6

Akhir Generasi 5 5 5 5 5 5 6 5 5 5 5.1


Rute Optimum

Node 21 - 35 - 31 - 41 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 31 - 41 - 15 - 27 - 28 - 42 - 29 - 44 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 25 - 40 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24

24

Lampiran 5 Lanjutan 4. Uji ukuran populasi 200 kromosom Ulangan

1 2 3 4 5 6 7 8 9 10 Rata- rata

Nilai Fitness 4150 4150 4553 4150 4150 4150 4788 4150 4150 4150 4254.1

Akhir Generasi 5 5 5 5 5 5 5 5 5 5 5


Rute Optimum

Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 31 - 41 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 25 - 40 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24


1 2 3 4 5 6 7 8 9 10 Rata- rata

Nilai Fitnessny a 4150 4150 4553 4150 4150 4759 4150 4150 4759 4150 4312.1

Akhir Generasi 5 5 5 5 5 5 5 7 5 5 5.2


Rute Optimum

Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 31 - 41 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 31 - 41 - 36 - 28 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 31 - 41 - 36 - 28 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24


1 2 3 4 5 6 7 8 9 10 Rata- rata

Nilai Fitnessny a 4150 4150 4150 4150 4150 4150 4150 4150 4150 4150 4150

Akhir Generasi 5 5 5 5 5 5 5 5 5 5 5


Rute Optimum

Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24 Node 21 - 35 - 14 - 15 - 27 - 5 - 33 - 4 - 24

25

Lampiran 5 Lanjutan 7. Uji ukuran populasi 350 kromosom Ulangan

1 2 3 4 5 6 7 8 9 10 Rata- rata


Akhir Generasi 5 8 8 8 5 5 5 5 9 5 6.3


Rute Optimum



1 2 3 4 5 6 7 8 9 10 Rata- rata


Akhir Generasi 6 5 5 5 5 5 5 5 5 5 5.1


Rute Optimum


26

Lampiran 6 Pengujian Crossover Probability Optimal. 1. Uji crossover probability = 0.5 Ulangan

1 2 3 4 5 6 7 8 9 10 Rata- rata

Nilai Fitness

Akhir Generasi

4150 4150 4150 4150 4150 4150 4150 4150 4150 4150 4150

Waktu Eksekusi (dtk)

5 5 5 5 5 5 5 5 5 5 5

Rute Optimum

3 3 3 3 3 3 3 3 3 3 3


2. Uji crossover probability = 0.6 Ulangan

1 2 3 4 5 6 7 8 9 10 Rata- rata

Nilai Fitness

Akhir Generasi

4150 4150 4150 4150 4150 4150 4150 4150 4150 4150 4150

5 5 5 5 5 5 5 5 8 5 5.3


Rute Optimum

3 3 3 3 3 3 3 3 4 3 3.1



1 2 3 4 5 6 7 8 9 10 Rata-rata

Nilai Fitness 4150 4150 4150 4150 4150 4150 4150 4150 4150 4150 4150

Akhir Generasi 5 5 5 5 5 5 5 5 5 5 5


Rute

3 3 3 3 3 3 3 3 3 3 3


27

Lampiran 6 Lanjutan 4. Uji crossover probability = 0.8 Ulangan

1 2 3 4 5 6 7 8 9 10 Rata- rata

Nilai Fitness

Akhir Generasi

4150 4150 4150 4150 4150 4150 4150 4150 4150 4150 4150


5 5 5 5 5 5 5 5 5 5 5

Rute

3 3 3 3 3 3 3 3 3 3 3



1 2 3 4 5 6 7 8 9 10 Rata- rata

Nilai Fitness 4150 4150 4150 4150 4150 4150 4150 4150 4150 4150 4150

Akhir Generasi 5 5 5 5 5 5 5 5 5 5 5


Rute

3 3 3 3 3 3 3 3 3 3 3


28

Lampiran 7 Pengujian Mutation Probability Optimal. 1. Uji mutation probability = 0.1 Ulangan

1 2 3 4 5 6 7 8 9 10 Rata- rata

Nilai Fitness

Akhir Generasi

4150 4150 4150 4150 4150 4150 4150 4150 4150 4150 4150


5 5 5 5 5 5 5 5 5 5 5

Rute Optimum

3 3 3 3 3 3 3 3 3 3 3


2. Uji mutation probability = 0.2 Ulangan

1 2 3 4 5 6 7 8 9 10 Rata- rata

Nilai Fitness

Akhir Generasi

4150 4150 4150 4150 4150 4150 4150 4150 4150 4150 4150


5 6 5 5 5 5 5 5 5 5 5.1

Rute Optimum

3 3 3 3 3 3 3 3 3 3 3



1 2 3 4 5 6 7 8 9 10 Rata- rata

Nilai Fitness 4150 4150 4150 4150 4150 4150 4150 4150 4150 4150 4150

Akhir Generasi 5 5 5 5 5 5 5 5 5 5 5


Rute Optimum


29

Lampiran 7 Lanjutan 4. Uji mutation probability = 0.4 Ulangan

1 2 3 4 5 6 7 8 9 10 Rata- rata


Akhir Generasi


5 5 5 5 5 5 5 5 5 5 5

Rute Optimum

3 3 3 3 3 3 3 3 3 3 3



1 2 3 4 5 6 7 8 9 10 Rata- rata

Nilai Fitness

Akhir Generasi

4150 4150 4150 4150 4150 4150 4150 4150 4150 4150 4150

5 5 5 5 8 5 5 5 5 9 5.7


Rute Optimum

3 3 3 3 4 3 3 3 3 5 3.3



1 2 3 4 5 6 7 8 9 10 Rata- rata

Nilai Fitness 4150 4150 4150 4150 4150 4150 4150 4150 4150 4150 4150

Akhir Generasi 5 5 5 5 5 5 5 5 5 5 5


Rute Optimum

3 3 3 3 3 3 3 3 3 3 3


30

Lampiran 8 Pengujian Stall Generation Optimal. 1. Uji stall generation = 5 Ulangan

1 2 3 4 5 6 7 8 9 10 Rata- rata

Nilai Fitness 4150 4150 4150 4150 4150 4150 4150 4150 4150 4150 4150

Akhir Generasi


5 5 5 5 5 6 5 5 5 5 5.1

Rute Optimum

3 3 3 3 3 4 3 3 3 3 3


2. Uji stall generation = 10 Ulangan

1 2 3 4 5 6 7 8 9 10 Rata- rata

Nilai Fitness 4150 4150 4150 4150 4150 4150 4150 4150 4150 4150 4150

Akhir Generasi 10 10 10 10 10 10 10 10 10 10 5.1


Rute Optimum


3. Uji stall generation = 15 Ulangan

1 2 3 4 5 6 7 8 9 10 Rata- rata

Nilai Fitness 4150 4150 4150 4150 4150 4150 4150 4150 4150 4150 4150

Akhir Generasi 15 15 17 15 15 15 15 19 15 15 15.6


Rute Optimum


31

Lampiran 8 Lanjutan 4. Uji stall generation = 20 Ulangan

1 2 3 4 5 6 7 8 9 10 Rata- rata

Nilai Fitness 4150 4150 4150 4150 4150 4150 4150 4150 4150 4150 4150

Akhir Generasi 20 20 20 20 20 20 20 20 20 20 20


Rute Optimum


32

Lampiran 9 Tampilan Sistem Rute Optimum Hasil Percobaan 2.

33

PENENTUAN RUTE OPTIMUM JALUR DISTRIBUSI DALAM SUPPLY CHAIN NETWORK MENGGUNAKAN ALGORITME GENETIKA DESCA MARWAN TONI

Recommend Documents