IMPLEMENTASI ALGORITMA HEURISTIK UNTUK OPTIMASI RUTE TERPENDEK

IMPLEMENTASI ALGORITMA HEURISTIK UNTUK OPTIMASI RUTE TERPENDEK

IMPLEMENTASI ALGORITMA HEURISTIK UNTUK OPTIMASI RUTE TERPENDEK Hardianto Sekolah Tinggi Teknologi Bontang [email protected] Abstract Along with the development of science and technology emerging new problems, such as issues of efficiency and optimization. In this study, the chosen optimization problem is in the field of sales distribution tansportasi eagle beans, which will be searched in the search for the shortest route optimization, the fastest time and the obstacles on the way of the eagle bean distribution warehouse to the customer and back to the barn again with Genetic algorithms. The purpose of this study implements Genetic algorithms in determining the distribution route optimization eagle bean sales in Surakarta. The research method used is a matter of research, research tools, and how to research include: observation and interview, read the literature, installation of application programs, business analysis eagle bean sales distribution, design and implementation, testing, analysis of test results and draw conclusions. The research was done by designing a graph model distribution system in accordance with the eagle bean sales data obtained, then the graph is assigned a weighting of each form of distances and speeds between the use of standard nodes using ArcView GIS 3.3 program. Then calculated and simulated by computer to obtain the optimal route sales distribution system using a eagle beans Genetic algorithms. he study produced a information Genetic algorithm computing time, the street names as nuts eagle sales distribution routes that travel along the existing barriers, the travel distance and total travel time distribution of total travel sales nuts from the warehouse to the customer's eagle and back again to the warehouse with animation optimal route. Based on the test results shows that Genetic algorithms can produce close to optimal in the case of the distribution system sales compared to peanuts eagle Greedy algorithms of search results and the estimated riel a driver. Keywords: optimization, Genetic algorithms, Greedy algorithms 1. Latar belakang Kebutuhan teknologi informasi rute perjalanan dari suatu lokasi ke lokasi lain secara efisien semakin meningkat seiring dengan pesatnya laju kinerja masyarakat. Pemilihan rute jalan merupakan permasalahan yang dihadapi oleh para pedagang keliling (Salesman). Setiap hari Salesman harus menentukan pelanggan mana saja yang harus dikunjungi baik yang lokasinya dekat maupun jauh dari tempat lokasi Salesman berada. Penentuan lokasi pelanggan yang akan dikunjungi tersebut, akan sangat berdampak pada biaya transportasi yang harus dikeluarkan maupun waktu yang dibutuhkan untuk sampai ke pelanggan hingga ke tempat Salesman semula berada. Sejalan dengan perkembengan ilmu pengetahuan dan teknologi informasi, penentuan optimasi rute perjalanan bagi pedagang keliling akan dapat diselesaikan secara komputasi. Dengan teknologi komputasi, informasi rute perjalanan dari satu lokasi ke lokasi lain akan dapat diketahui dengan cepat dan mudah. Melalui sistem informasi berbasis teknologi informasi pekerjaan akan dapat diselesaikan dengan mudah, efektif dan efisien. Dari penjelasan tersebut yang menjadi permasalahan adalah bagaimana menentukan

optimasi rute terpendek. Optimasi rute bertujuan agar mendapatkan waktu dan jarak yang efisien. Sehingga bisa berjalan dengan cepat dan biaya transportasi yang rendah. Penelitian ini bertujuan mencermati unjuk kerja (performance) implementasi algoritma Heuristik dalam menyelesaikan optimasi rute terpendek. 2. Landasan Teori 2.1. Algoritma Hal-hal yang perlu diperhatikan dalam algoritma adalah mencari langkah-langkah yang paling sesuai untuk penyelesaian suatu masalah, karena setiap algoritma memiliki karakteristik tertentu yang memiliki kelebihan dan kekurangan (Zakaria, 2006). Beberapa hal yang harus dipahami dalam mencari algoritma antara lain: 1. Masalah seperti apa yang hendak diselesaikan. 2. Gagasan apa yang ada pada algoritma tersebut. 3. Berapa lama yang diperlukan untuk menyelesaikan masalah. 4. Berapa jumlah data yang dapat ditangani oleh suatu algoritma.

79

Jurnal Teknologi Informasi dan Komunikasi, ISSN:2087-0868, Volume 4 Nomor 2 Agustus 2013

2.2. Kompleksitas Waktu Sebuah algoritma tidak saja harus menghasilkan keluaran yang benar, tetapi juga harus mangkus (efisien). Kebenaran suatu algoritma harus diuji dengan jumlah masukan tertentu untuk melihat kinerja algoritma berupa waktu yang diperlukan untuk menjalankan algoritmanya dan ruang memori yang diperlukan untuk struktur datanya (Munir, 2009). Algoritma yang bagus adalah algoritma yang mangkus (efisien). Kemangkusan algoritma diukur dari berapa jumlah waktu dan ruang memori yang dibutuhkan untuk menjalankan algoritma tersebut. Algoritma yang mangkus adalah algoritma yang meminimumkan kebutuhan waktu dan ruang. Kompleksitas waktu dari algoritma berisi ekspresi bilangan dan jumlah langkah yang dibutuhkan sebagai fungsi dari ukuran permasalahan. Kompleksitas ruang berkaitan dengan sistem memori yang dibutuhkan dalam eksekusi program (Purwanto, 2008). Pada Tabel 1 diperlihatkan kelompok algoritma berdasarkan kompleksitas waktu asimptotiknya. Tabel 1. Kelompok algoritma berdasarkan kompleksitas waktu asimptotik. Kelompok algoritma Nama O(1) Konstan O(log n) Logaritmik O(n) Linear O(n log n) n log n O(n2) Kuadratik O(n3) Kubik O(2n) Eksponensial O(n!) Faktorial

Kebutuhan waktu dan ruang suatu algoritma bergantung pada ukuran masukan, yang secara khas adalah jumlah data yang diproses. Ukuran masukan itu disimbolkan dengan n. Setelah menetapkan ukuran masukan, maka langkah selanjutnya dalam mengukur kompleksitas waktu adalah menghitung banyaknya operasi yang dilakukan algoritma sehingga didapatkan notasi kompleksitas waktunya dalam fungsi n yaitu f(n). Untuk mengukur kebutuhan waktu sebuah algoritma yaitu dengan mengeksekusi langsung algoritma tersebut pada sebuah komputer, lalu dihitung berapa lama durasi waktu yang dibutuhkan untuk menyelesaikan sebuah persoalan dengan n yang berbeda-beda. Kemudian dibandingkan hasil komputasi algoritma tersebut dengan notasi kompleksitas waktunya untuk mengetahui efisiensi algoritmanya. O(n!) dari tabel tersebut merupakan algoritma eksponensial, algoritma jenis ini memproses setiap masukan dan menghubungkannya dengan n - 1 masukan lainnya, misalnya algoritma persoalan Pedagang Keliling (Travelling Salesman Problem). Bila n = 5, maka waktu pelaksanaan algoritma adalah (5-1)!=1 x 2 x 3 x 4=24. Bila n dijadikan dua kali semula, maka waktu pelaksanaan algoritma menjadi faktorial dari 2n (Mehta et. al. 2004). 2.3. Lintasan Terpendek (Shortest Path) Suatu uraian pemecahan persoalan tentang graf berbobot G = (V,E) dan sebuah simpul a. Penentuan lintasan terpendek dari a ke setiap simpul lainnya di G. Asusmsi yang kita buat adalah bahwa semua sisi berbobot positip. Perhatikan Gambar 2.

Berdasarkan Tabel 1 di atas, maka dapat digambarkan grafik kelompok algoritma dengan kompleksitas waktu asimptotiknya seperti yang terlihat pada Gambar 1 (Mehta et. al., 2005).

Gambar 2 Graf yang digunakan sebagai contoh untuk persoalan Lintasan terpendek Lintasan terpendek dari simpul 1 ke semua simpul lain diberikan pada Tabel 2 (diurut dari lintasan terpendek pertama, kedua ketiga dan seterusnya). Tabel 2. Lintasan terpendek dari simpul 1 ke semua simpul

Gambar 1 Grafik kelompok algoritma dengan kompleksitas waktu asimptotik

80

IMPLEMENTASI ALGORITMA HEURISTIK UNTUK OPTIMASI RUTE TERPENDEK

Dari Tabel 2, bahwa lintasan terpendek dari 1 ke 2 berarti juga melalui lintasan terpendek dari 1 ke 3 dan dari 1 ke 4 (Haryanto, 2008). 2.4. Algoritma Heuristik. Secara umum, penyelesaian masalah pencarian jalur terpendek dapat dilakukan dengan menggunakan dua metode, yaitu metode konvensional dan metode heuristik. Metode konvensional diterapkan dengan perhitungan matematis biasa, sedangkan metode heuristik diterapkan dengan perhitungan kecerdasan buatan, dengan menentukan basis pengetahuan dan perhitungannya (Mutakhiroh, 2007). a. Metode konvensional Metode konvensional adalah metode yang menggunakan perhitungan matematis biasa. Ada beberapa metode konvensional yang biasa digunakan untuk melakukan pencarian jalur terpendek, diantaranya: algoritma Djikstraa, algoritma Floyd-Warshall, algoritma Greedy dan algoritma Bellman- Ford. b. Metode heuristik Metode Heuristik adalah sub bidang dari kecerdasan buatan yang digunakan untuk melakukan pencarian dan optimasi. Ada beberapa algoritma pada metode heuristik yang biasa digunakan dalam permasalahan optimasi, diantaranya algoritma Genetika, algoritma Semut, Logika fuzzy, Jaringan syaraf tiruan, dan lain-lain. Algoritma yang akan dibahas dalam penelitian ini adalah algoritma Heuristik dengan metode Genetika. Teknik pencarian dan optimasi dalam algoritma ini terinspirasi oleh prinsip dari genetika dan seleksi alam (teori evolusi Darwin). Sebelum algoritma genetika dijalankan, maka perlu didefinisikan fungsi fitness sebagai masalah yang ingin dioptimalkan. Jika nilai fitness semakin besar, maka sistem yang dihasilkan semakin baik. fungsi fitness ditentukan dengan metode heuristik. 2.5. Algoritma Genetika Algoritma genetika adalah algoritma pencarian yang didasarkan atas mekanisme seleksi alami dan evolusi biologis. Algoritma genetika mengkombinasikan antara deretan struktur dengan pertukaran informasi acak ke bentuk algoritma pencarian dengan beberapa

perubahan bakat pada manusia. Pada setiap generasi, himpunan baru dari deretan individu dibuat berdasarkan kecocokan pada generasi sebelumnya (Goldberg,1989). Oleh karena itu, algoritma ini digunakan untuk mendapatkan solusi yang tepat untuk masalah optimasi dari satu variabel atau multi variabel. Berbeda dengan teknik pencarian konvensional, algoritma genetika bermula dari himpunan solusi yang dihasilkan secara acak. Himpunan ini disebut populasi. Sedangkan setiap individu dalam populasi disebut kromosom yang merupakan representasi dari solusi. Kromosomkromosom berevolusi dalam suatu proses iterasi yang berkelanjutan yang disebut generasi. Pada setiap generasi, kromosom dievaluasi berdasarkan suatu fungsi evaluasi (Gen dan Cheng, 1997). Setelah beberapa generasi maka algoritma genetika akan konvergen pada kromosom terbaik, yang diharapkan merupakan solusi optimal (Goldberg,1989). Siklus dari algoritma Genetika menurut David Goldberg, dimana gambaran siklus tersebut adalah sebagai berikut:

Gambar 3 Siklus algoritma Genetika oleh David Goldberg Urutan dari siklus algoritma Genetika yang dikenalkan oleh David Goldberg tersebut adalah: a. Inisialisasi populasi. Inisialisasi ini dilakukan secara random dan hanya satu kali saja sewaktu start pertama kali Algoritma Genetika. Inisialisasi ini menghasilkan populasi awal dengan jumlah chromosome yang sesuai dengan yang kita harapkan. Populasi merupakan sejumlah jalur atau solusi yang dicari secara acak. b. Evaluasi. Ini adalah proses menghitung nilai fitness dari masing-masing chromosome yang ada . c. Seleksi. Melalui proses ini maka lahirlah genersi baru dimana chromosome diperoleh dari chromosome sebelumnya. Seleksi dapat dilakukan dengan menggunakan teknik mesin roullete. Tujuan dari proses seleksi adalah untuk mendapatkan calon induk yang baik bagi generasi berikutnya (Basuki, 2003). Langkahlangkah yang dilakukan dalam mesin roullete adalah: i. Mencari nilai fitness relatif (pk) dan fitness kumulatif (qk).

81


a. Fitness relatif [i] = F[i] /total nilai fitness, dimana F[i]=1/fitness[i] dan seterusnya sampai sebanyak ukuran populasi. b. Fitness kumulatif[i] =pk[i], contoh: Qk[1]=pk[1] Qk[2]=qk[1] + pk[2] Qk[3]=qk[2] + pk[3] dan seterusnya sebanyak ukuran populasinya. ii. Membangkitkan bilangan acak antara 0-1 sebanyak ukuran populasi. iii. Pencocokan nilai jangkauan bilangan acak untuk seleksi dengan qk. Contoh hasil proses seleksi dengan teknik roullete tersebut seperti Tabel 3 berikut:

Mulai

Induk 1 Induk 2 p = random[0,1]

p<probCo

Tidak

Ya

Cross Over

Selesai

Gambar 4 Flowchart crossover Tabel 3 Contoh proses seleksi

Dari Tabel 3 tersebut, hasil pencocokan nilai jangkauan bilangan acak (random) untuk seleksi dengan qk adalah terdapat pada kolom Kromosom Baru (Saptono et. al., 2007) d. Crossover Proses ini akan menghasilkan offspring (chromosome baru yang dihasilkan setelah melewati suatu generasi) yang berbeda dengan parent/orang tuanya. Untuk proses ini dilakukan dengan mengambil parent secara berpasangan dan akan menghasilkan offspring dengan jumlah yang sama dengan parent. Proses crossover dilakukan pada setiap individu (chromosome) dengan probabiltas crossover yang telah ditentukan (Basuki, 2003). Flowchart proses crossover adalah sebagai berikut:

Setelah melakukan pemilihan induk, proses selanjutnya menentukan posisi crossover. Hal tersebut dilakukan dengan membangkitkan bilangan acak (p) antara 0 sampai 1sebanyak ukuran populasi, guna memilih chromosome mana saja yang akan dilakukan persilangan (crossover). Selanjutnya proses memilih bilangan acak (p) yang kurang dari probabilitas crossover, sehingga chromosome-nya bisa disilangkan (Mutakhiroh, 2007). e.

Mutasi. Pada proses ini juga akan dihasilkan offspring dimana jumlahnya tergantung pada banyaknya bilangan random yang kurang dari probabilitas mutasinya (pm). Flowchart untuk proses mutasi seperti Gambar 5 berikut: Mula i Chromosome p =random [0,1]

p < prob mutasi ?

Tidak

Ya r = random

Gen termutasi Selesai

Gambar 5 Flowchart proses mutasi

82

IMPLEMENTASI ALGORITMA HEURISTIK UNTUK OPTIMASI RUTE TERPENDEK Jumlah kromosom yang mengalami mutasi dalam satu populasi ditentukan oleh probabilitas mutasi (pm). Proses selanjutnya membangkitkan bilangan acak (p) antara 0-1sebayak jumlah gen dalam suatu kromosom. Jika bilangan acak (p) lebih kecil dari nilai probabilitas mutasi, maka kromosom tersebut akan termutasi (Mutakhiroh, 2007). Proses mutasi dilakukan dengan cara menukar gen yang dipilih secara acak dengan gen sesudahnya. Jika gen tersebut berada diakhir kromosom, maka ditukar dengan gen yang pertama. f. Lakukan pengulangan kembali ke langkah b dan bila kriteria berhenti sudah dicapai, maka Algoritma Genetika ini sudah selesai. Berikut adalah pseudocode untuk algoritma Genetika (Eiben, 2003): BEGIN GENERASI = 0 INISIALISASI parameter BANGKITKAN populasi EVALUASI nilai fitness DO GENERASI = GENERASI+1 SELEKSI induk REKOMBINASI pasangan induk MUTASI hasil keturunan EVALUASI nilai fitness BANGKITKAN populasi baru WHILE (maksimum generasi) END. 3. Metode Penelitian 3.1. Materi Penelitian Penyelesaian optimasi rute terpendek penelitian ini digunakan algoritma Exhaustive Search. Untuk mempercepat kompleksitas waktu dari kinerja algoritma Exhaustive Search dalam menemukan solusi digunakan metode Heuristik. Informasi yang diberikan dari hasil penelitian ini berupa rute terpendek dari satu titik ke titik tujuan yang akan dikunjungi, jarak yang harus ditempuh dan waktu yang dibutuhkan algoritma dalam menentukan solusi rute mendekati optimal. 3.2. Alat Penelitian Alat penelitian yang digunakan dalam perancangan sistem meliputi kebutuhan perangkat lunak dan prangkat keras. Ada beberapa perangkat lunak yang digunakan dalam penelitian ini yaitu: - Sistem Operasi Microsoft Windows XP SP2. - ArcView GIS 3.3 - Microsoft Office 2007. Sedangkan perangkat kerasnya berupa satu unit komputer Laptop dengan sepesifikasi yang cukup untuk mejalankan perangkat-perangkat lunak diatas. Spesifikasi yang dimaksud meliputi: 1. Prosesor Intel Celeron 1.6 GHz.

2. 3. 4.

Ram 1 GB. Hard dis drive 160 GB Mouse dan layar LCD 14” untuk menampilkan informasi dan data.

3.3. Tahapan Penelitian Penelitian ini dilakukan dengan melalui tahapan-tahapan berikut: 1. Prosiding dan jurnal ilmiah yang terkait dengan pengembangan algoritma Heuristik dalam penyelesaian rute optimal. 2. Buku (textbook) yang terkait dengan pengembangan algoritma Heuristik, metode Genetika dan pengembangan perangkat lunak untuk metode Genetika. 3. Instalasi program aplikasi yang dibutuhkan, seperti (ArcView GIS 3.3, Microsoft office 2007) dan program pendukung lainnya yang digunakan dalam penelitian. 4. Pembuatan peta (map) distribusi. 5. Menganalisa proses bisnis distribusi. 6. Dari hasil observasi dan survei, diperoleh data mengenai prosedur pengiriman pesanan yang bersifat spontanitas, prosedur pengiriman atau distribusi produk secara rutinitas dan armada yang digunakan dalam proses distribusi kacang garuda. 7. Perancangan dan implementasi sistem penentuan rute optimal dengan algoritma Genetika. Dalam hal ini dilakukan perancaan diagram konteks, use case, diagram alir data, relasi tabel dan flowchart proses siklus Genetika untuk optiasi rute. 8. Melakukan pengujian program dan pengamatan terhadap rute optimal yang dihasilkan serta kompleksitas waktu dari algoritma Genetika. Rute optimal diperoleh berdasarkan rumus kecepatan = (jarak antar lokasi atau simpang /waktu tempuh). 9. Menganalisa dan menarik kesimpulan dari hasil pengujian tersebut. 4. Hasil dan Pembahasan 4.1 Pembahasan Rute Optimal Genetika Proses pencarian rute optimal ini akan dilakukan dengan 2 jumlah pelanggan Jika seorang sopir hendak menghantarkan pesanan 20 box kacang garuda ke pelanggan Heru Sumber dan pelanggan Sugeng dengan lintasan distribusi seperti gambar 6. Dari 20 box kacang garuda tadi akan didistribusikan ke pelanggan Heru Sumber sebanyak 10 box dan sisanya ke pelanggan Sugeng. Proses distribusi yang dikehendaki berangkat dari Gudang baru ke pelanggan dan kembali lagi ke gudang.

83


Sugeng dengan melalui jalan Banyuanyar SLT1. Untuk kembali lagi ke gudang kacang garuda, rute jalan yang dipilih adalah jalan Banyuanyar SLT1 dan Banyuanyar SLT2 dengan tidak ada hambatan yang dilalui. Panjang rute perjalan yang dilalui untuk menghantarkan pesanan tersebut adalah 2.295 km dengan membutuhkan waktu tempuh 3 menit lebih 31 detik. Proses siklus Genetika untuk penyelesaian rute optimal seperti Gambar 6, akan terbagi menjadi 1 siklus rute optimal yaitu: Penyelesaian rute optimal dari gudang menuju pelanggan Untuk mendapatkan rute optimal dari gudang PT. Bintang Mas menuju ke pelanggan Heru Sumber dan Sugeng seperti Gambar 7, dengan proses siklus Genetika sebagai berikut: Pertama, penentuan populasi secara acak yang hasilnya seperti Gambar 8 Keteterangan kode jalan: 557 :Banyuanyar SLT2 556 :Letjend Suprapto 4 409 :Letjend Suprapto 3 73 :Adi Sumarmo 14 65 :Banyuanyar SLT1 64 :Kahuripan Utara 2 Gambar 6 Rute optimal Genetika 2 pelanggan Jarak yang ditampilkan pada Gambar 6 masih dalam satuan centimeter (cm). Warna coklat merupakan lokasi yang dipilih atau yang akan dikunjungi. Dalam lintasan tersebut terdapat sebuah hambatan yaitu Traffic light plesungan. Hasil dari proses pencarian rute optimal Genetikanya seperti gambar 7

Gambar 8 Populasi Genetika Pada Gambar 8 parameter ukuran populasi ditentukan sebesar = 10 populasi, populasi ini dihasilkan secara acak oleh komputer. Dari gambar 8 terlihat bahwa dari 10 populasi yang telah ditentukan tersebut, yang berhasil mendapatkan nilai fitness hanyalah P[3], P[6] dan P[8], dengan nilai : P[3] : Kode jalan yang terpilih secara acak adalah 557 (Banyuanyar SLT2), dengan waktu optimum 0.023 jam. Selanjutnya nilai Fitness: 0.023 , Inverse : 43.4783. Nilai fitness merupakan nilai yang menunjukkan kualitas suatu kromosom dalam populasi.

Gambar 7 Informasi rute optimal Genetika 2 pelanggan Hasil rute optimal yang didapat seperti Gambar 7 bahwa, Distributor yang akan melakukan pengiriman kacang garuda adalah PT. Bintang Mas. Selanjutnya pelanggan yang akan di kunjungi terlebih dahulu adalah Heru Sumber melalui jalan Banyuanyar SLT2, kemudian baru ke pelanggan

84

P[6] : Kode jalan yang terpilih adalah Adi Sumarmo 14 dengan waktu optimum 0.009 jam dan nilai (Fitness: 0.009, Inverse : 111.111) Letjend Suprapto 4

IMPLEMENTASI ALGORITMA HEURISTIK UNTUK OPTIMASI RUTE TERPENDEK dengan waktu optimum 0.022 dan nilai (Fitness: 0.031, Inverse : 32.2581)Letjend Suprapto 3 dengan waktu optimum 0.006 jam dan nilai (Fitness: 0.037, Inverse : 27.027) Kahuripan Utara 2 dengan waktu optimum 0.01 dan nilai (Fitness: 0.047, Inverse : 21.2766)Banyuannyar SLT1 dengan waktu optimum 0.007 dan nilai (Fitness: 0.054 , Inverse : 18.5185) P[8] : Kode jalan yang terpilih adalah Banyuanyar SLT2, dengan waktu optimum 0.023 dan nilai (Fitness: 0.023, Inverse : 43.4783) Kedua, proses seleksi populasi untuk mendapatkan kandidat induk yang baik. Proses seleksi menggunakan metode roda roulette, maka langkahnya adalah mencari nilai fitness relatif dan membangkitkan bilangan acak sebanyak ukuran populasi. Proses seleksi seperti terlihat pada Gambar 9.

Gambar 10 Proses Crossover dan Mutasi Probabilitas Crossover (pc) pada Gambar 10 ditetapkan sebesar =0.25. Bilangan acak yang kurang dari pc, maka kromosomnya akan mengalami persilangan. Kromosom yang mengalami persilangan tersebut adalah:

Gambar 9. Proses seleksi Genetika Pada Gambar 9 terlihat bahwa total nilai inverse dari kromosom sebesar 297.148, sehingga didapatkan nilai fitness relatifnya adalah : P[3]: 0.146319 P[6]: 0.373925 P[6]: 0.108559 P[6]: 0.0909548 P[6]: 0.0716027 P[6]: 0.0623209 P[8]: 0.146319. Ketiga, proses crossover dan mutasi. Pada proses crossover jumlah kromosom yang di crossover dipengaruhi oleh parameter probabilitas crossover seperti terlihat pada Gambar 10

Kromosom[1]->0.146319,R: 0.1 Kromosom[2]->0.373925,R: 0.142857 Kromosom[4]->0.0909548,R: 0.2 Kromosom[5]->0.0716027,R: 0.125, hasil dari proses crossover akan terbentuk populasi baru. Probabilitas Mutasi (pm) pada Gambar 10 ditetapkan sebesar =0.15. Pada proses mutasi kromosom yang terkecil daripada probabilitas mutasi akan terkena mutasi, sehingga dalam proses mutasi ini kromosom yang terpilih adalah P[2] dengan Random[2]:0.166667 dan kode jalan yang terpilih adalah 557 yaitu ke lokasi Heru Sumber (lihat tabel jalan). Sedangkan untuk Populasi awal [per-kode jalan] terlihat seperti Gambar 11.

85


Selanjutnya untuk proses seleksi kromosomnya terlihat pada Gambar 12.

Gambar 12. Proses seleksi Genetika Gambar 11. Populasi awal per-kode jalan Dari 10 ukuran populasi yang telah ditetapkan seperti Gambar 11, hanya 4 buah populasi yang dipakai secara acak oleh komputer yaitu: P[4] : => 557 , Optimum = 0.023 **>Fitness: 0.023 , Inverse : 43.4783 => 65 , Optimum = 0.007 **>Fitness: 0.03 , Inverse : 33.3333 P[5] : => 73 , Optimum = 0.009 **>Fitness: 0.009 , Inverse : 111.111 => 556 , Optimum = 0.022 **>Fitness: 0.031 , Inverse : 32.2581 => 409 , Optimum = 0.006 **>Fitness: 0.037 , Inverse : 27.027 => 64 , Optimum = 0.01 **>Fitness: 0.047 , Inverse : 21.2766 P[6] : => 557 , Optimum = 0.023 **>Fitness: 0.023 , Inverse : 43.4783 => 65 , Optimum = 0.007 **>Fitness: 0.03 , Inverse : 33.3333 P[10] : => 557 , Optimum = 0.023 **>Fitness: 0.023 , Inverse : 43.4783 => 65 , Optimum = 0.007 **>Fitness: 0.03 , Inverse : 33.3333.

86

Pada proses seleksi Genetika seperti Gambar 12, didapatkan total inverse dari nilai fitness sebesar 422.108. Sehingga proses perhitungan nilai fitness relatif (pk) tiap-tiap kromosomnya adalah: P[4]: 0.103003 P[4]: 0.0789688 P[5]: 0.263229 P[5]: 0.0764214 P[5]: 0.0640288 P[5]: 0.0504056 P[6]: 0.103003 P[6]: 0.0789688 P[10]: 0.103003 P[10]: 0.0789688. Selanjutnya untuk proses persilangan dan mutasi terlihat pada Gambar 13.

IMPLEMENTASI ALGORITMA HEURISTIK UNTUK OPTIMASI RUTE TERPENDEK informasi berupa: rute optimal jarak tempuh dari gudang menuju pelanggan dan kembali lagi ke gudang, waktu yang dibutuhkan terhadap jarak yang ditempuh. 3. Waktu komputasi algoritma Genetika pada Arc View GIS 3.3 menjadi besar, karena Arc View GIS 3.3 saat mengeksekusi script Avenue algoritma Genetika tidak menggunakan struktur data array dan record, namun menggunakan cara membuat tabel dan dihubungkan dengan script Avenue Arc View GIS 3.3 5.1 Saran 1. Pada penelitian optimasi rute distribusi ini, baru dilakukan pengujian sebatas menggunakan algoritma Greedy dan Genetika, maka perlu dilakukan penyelesaian dengan algoritma Heuristik lainnya seperti algoritma Semut maupun Fuzzy Logic. DAFTAR PUSTAKA

Gambar 13. Proses Crossover dan Mutasi Genetika Pada proses Crossover kode jalan seperti Gambar 13, terlihat bahwa Probabilitas Crossover (pc) ditetapkan sebesar = 0.25. Sehingga kromosom yang akan mengalami persilangan adalah: CROSSOVER 1->0.103003,R: 0.125 ***> Populasi Baru :1 4->0.0764214,R: 0.142857 ***> Populasi Baru :4 5->0.0640288,R: 0.111111 ***> Populasi Baru :5 9->0.103003,R: 0.166667 ***> Populasi Baru :9. Sedangkan pada proses mutasi seperti Gambar 13, terlihat bahwa nilai Probabilitas Mutasi (pm) ditetapkan sebesar = 0.15. Sehingga kromosom yang termutasi adalah P[1] dengan nilai Random[1]:0.166667 dan kode jalan yang terpilih adalah [557][65]Ke lokasi Sugeng. 5. KESIMPILAN DAN SARAN Setelah dilakukan implementasi dan pengujian algoritma Genetika untuk menentukan rute optimal: 5.1 Kesimpulan : 1. Algoritma Genetika dapat menyelesaikan rute optimal distribusi sales kacang garuda 2. Dengan bantuan program ArcView GIS 3.3 sistem optimasi rute distribusi dengan Algoritma Genetika dapat menghasilkan

Hannawati.A, Thiang, Eleazar, 2002, “Pencarian Rute Optimal Menggunakan Algoritma Genetika”, Jurnal Teknik Elektro Vol 2 Universitan Kristen Petra, Hal 78-83. Kristanto, A., 2008, “Perancangan Sistem Informasi dan Aplikasinya”, Gava Media, Yogyakarta. Kusumadewi, S., 2005, “PenyelesaianMasalah Optimasi dengan Teknik-teknik Heuristi”, Yogyakarta: Graha Ilmu. Kusumadewi, S., 2003, “ Artificial Intelligence (Teknik danAplikasinya)”, Yogyakarta: Graha Ilmu. Lukas, dkk., 2005, “Penerapan Algoritma Genetika untuk Travelling Salesman Problem dengan Menggunakan Metode Order Crossover dan Insertion Mutation”, Seminar Nasional Aplikasi Teknologi Informasi, hlm: 1 s/d 5. Mutakhiroh.I,2007, “Pemanfaatan Metode Heuristik Dalam Pencarian Rute Terpendek Dengan Algoritma Semut Dan Algoritma Genetika”, SNATI, Yoyakarta, hal B33-B39. Mehta, D. P., 2005, “Handbook of Data Structures and Applications”, Chapman & Hall/CRC Computer and Information Science Series, United States of America. Mitsuo,G and Cheng,R.,1997, Genetic Algoritms and Engineering Design.John Wiley and Sons, Inc. New York. Nugraha.D.W., 2010, “Pengkajian Kompleksitas Waktu Implementasi Algoritma Prim (Studi Kasus: Pada Jaringan Distribusi Listrik Primer Di Wilayah Kota Palu)”,

87


Tesis Program Studi Teknik Elektro, Universitas Gadjah Mada, Yogyakarta. Oetomo, B. S., 2002, “Perencanaan dan Pembangunan Sistem Informasi”, Andi, Yogyakarta. Prahasta, E., 2009, ”Sistem Informasi Geografis: Tutorial ArcView”, Informatika, Bandung. Purwanto, E. B., 2008, “Perancangan Dan Analisis Algoritma”, Edisi 1, Graha Ilmu, Yogyakarta.

88

IMPLEMENTASI ALGORITMA HEURISTIK UNTUK OPTIMASI RUTE TERPENDEK

Recommend Documents