PENYELESAIAN VEHICLE ROUTING PROBLEM MENGGUNAKAN ALGORITME GENETIKA DEDI HARIYANTO

PENYELESAIAN VEHICLE ROUTING PROBLEM MENGGUNAKAN ALGORITME GENETIKA

DEDI HARIYANTO

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2016

PERNYATAAN MENGENAI SKRIPSI DAN SUMBER INFORMASI SERTA PELIMPAHAN HAK CIPTA Dengan ini saya menyatakan bahwa skripsi berjudul Penyelesaian Vehicle Routing Problem Menggunakan Algoritme Genetika adalah benar karya saya dengan arahan dari komisi pembimbing dan belum diajukan dalam bentuk apa pun kepada perguruan tinggi mana pun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di bagian akhir skripsi ini. Dengan ini saya melimpahkan hak cipta dari karya tulis saya kepada Institut Pertanian Bogor. Bogor, April 2016 Dedi Hariyanto NIM G54110045

ABSTRAK DEDI HARIYANTO. Penyelesaian Vehicle Routing Problem Menggunakan Algoritme Genetika. Dibimbing oleh PRAPTO TRI SUPRIYO dan MUHAMMAD ASYHAR AGMALARO. Vehicle routing problem (VRP) adalah masalah penentuan rute terpendek sekelompok kendaraan yang harus mengunjungi beberapa kota. Penyelesaian VRP berukuran besar dengan metode eksak akan memerlukan waktu komputasi yang lama, sehingga pada umumnya VRP berukuran besar diselesaikan dengan metode pendekatan (heuristik). Algoritme genetika adalah salah satu metode pendekatan untuk masalah optimasi seperti VRP. Secara umum, tahapan algoritme genetika adalah pengodean, pembangkitan populasi awal, seleksi induk, kawin silang, mutasi, dan penggantian generasi. Banyak pilihan metode yang dapat digunakan dalam tahapan-tahapan algoritme genetika tersebut. Tujuan penelitian ini adalah mendeskripsikan cara kerja algoritme genetika untuk menyelesaikan VRP. Dalam penelitian ini, VRP dengan 9 kota diselesaikan dengan algoritme genetika menggunakan metode stochastic universal sampling untuk seleksi induk, order crossover untuk kawin silang, dan insertion untuk mutasi dengan bantuan software MATLAB R2008b. Algoritme genetika menghasilkan rute terpendek 29 km, sedangkan hasil dengan metode eksak diperoleh rute terpendek 27 km. Kata kunci: algoritme genetika, kawin silang, mutasi, seleksi, VRP

ABSTRACT DEDI HARIYANTO. The Solution of Vehicle Routing Problem Using Genetic Algorithms. Supervised by PRAPTO TRI SUPRIYO and MUHAMMAD ASYHAR AGMALARO Vehicle routing problem (VRP) is the problem of determining the shortest route for a fleet of vehicles that have to visit several cities. The big VRP solution using the exact method will require a long computing time, so, generally, these big VRP are solved by the approach method (heuristics). One such approach method for an optimization problem, such as VRP, is to use a genetic algorithm. In general, the genetic algorithms stages are encoding, initial population generation, parents selection, crossovers, mutations, and the generation replacement. Each of these genetic algorithm stages can be performed using one of many available methods. The purpose of this study is to describe how the genetic algorithms work to solve VRP. In this study, VRP with 9 cities were solved by genetic algorithms using stochastic universal sampling method for parents selection, order crossover for recombination, and the insertion for mutations by MATLAB R2008b software. Genetic algorithms find the shortest route, 29 kilometers, while the exact method finds the shortest route, 27 kilometers. Keywords: genetic algorithms, mutations, recombinations, selections, VRP

PENYELESAIAN VEHICLE ROUTING PROBLEM MENGGUNAKAN ALGORITME GENETIKA

DEDI HARIYANTO

Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Departemen Matematika

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2016

PRAKATA Segala puji bagi Allah subhanahu wa ta’ala atas segala rahmat dan karuniaNya sehingga penulis dapat menyelesaikan karya ilmiah ini. Topik yang dipilih dalam penelitian ini ialah vehicle routing problem, dengan judul Penyelesaian Vehicle Routing Problem Menggunakan Algoritme Genetika. Penulis mengucapkan terima kasih kepada Bapak Drs Prapto Tri Supriyo, MKom dan Bapak Muhammad Asyhar Agmalaro, SSi, MKom selaku pembimbing, serta Ibu Dra Farida Hanum, MSi yang telah banyak memberikan saran. Terima kasih juga penulis ucapkan kepada segenap dosen Departemen Matematika IPB atas ilmu dan pelajaran yang telah diberikan, serta staf Departemen Matematika IPB yang telah banyak membantu penulis. Selain itu, terima kasih juga penulis sampaikan kepada teman-teman Matematika angkatan 48 yang selalu saling memberi dukungan dan semangat, serta Ilham yang selalu bersedia membantu. Ungkapan terima kasih juga penulis sampaikan kepada ibu, kakak, dan keluarga tercinta yang selalu memberikan dukungan, motivasi, dan doa-doanya, serta semua pihak yang sudah membantu penulis dan tidak dapat disebutkan satu per satu. Penulis menyadari karya ilmiah ini memiliki kekurangan. Oleh karena itu, penulis sangat menghargai kritik dan saran dari pembaca. Semoga karya ilmiah ini bermanfaat.

Bogor, April 2016 Dedi Hariyanto

DAFTAR ISI DAFTAR TABEL

vi

DAFTAR GAMBAR

vi

DAFTAR LAMPIRAN

vii

PENDAHULUAN

1

Latar Belakang

1

Tujuan Penelitian

1

Ruang Lingkup Penelitian

1

TINJAUAN PUSTAKA

2

Formulasi VRP Menggunakan Interger Linear Programming

2

Algoritme Genetika

3

IMPLEMENTASI ALGORITME GENETIKA PADA VRP Solusi Manual

9 9

Solusi VRP dengan Bantuan Software

28

Perbandingan Solusi Eksak dengan Solusi Algoritme Genetika

29

SIMPULAN DAN SARAN

29

Simpulan

29

Saran

29

DAFTAR PUSTAKA

30

LAMPIRAN

31

DAFTAR TABEL 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

Jarak antarpelanggan dan permintaan Individu hasil pembangkitan populasi awal Nilai fitness dan peluang kumulatif individu pada populasi awal Anak hasil kawin silang pada Iterasi 1 Nilai fitness anak pada Iterasi 1 Individu pada generasi ke-2 Nilai fitness dan peluang kumulatif individu pada Iterasi 2 Pemilihan induk pada Iterasi 2 Anak hasil kawin silang pada Iterasi 2 Nilai fitness anak pada Iterasi 2 Individu pada generasi ke-3 Nilai fitness dan peluang kumulatif individu pada Iterasi 3 Pemilihan induk pada Iterasi 3 Pemilihan induk pada Iterasi 4 Anak hasil kawin silang pada Iterasi 4 Nilai fitness anak pada Iterasi 4 Individu baru pada generasi ke-5 Nilai fitness dan peluang kumulatif individu pada Iterasi 5 Pemilihan induk pada Iterasi 5 Anak hasil kawin silang pada Iterasi 5 Nilai fitness anak pada Iterasi 5 Individu pada generasi ke-6 Nilai fitness dan peluang kumulatif individu pada Iterasi 6 Pemilihan induk pada Iterasi 6 Pemilihan induk pada Iterasi 7 Pemilihan induk pada Iterasi 8 Pemilihan induk pada Iterasi 9 Anak hasil kawin silang pada Iterasi 9 Nilai fitness anak pada Iterasi 9 Individu pada generasi ke-10 Nilai fitness dan peluang kumulatif individu pada Iterasi 10 Pemilihan induk pada Iterasi 10

9 11 12 14 15 16 16 16 17 17 18 18 19 19 20 20 20 21 21 21 22 22 23 23 24 24 24 25 25 26 26 26

DAFTAR GAMBAR 1 2 3 4 5 6 7 8

Diagram alir algoritme genetika Ilustrasi kromosom bilangan bulat Ilustrasi satu individu atau kromosom dengan 3 blok Letak pointer untuk populasi awal Hasil mutasi Anak 1 dengan motede insertion Rute optimal pada akhir Iterasi 10 Grafik nilai fitness terbaik setiap iterasi Rute optimal yang didapat pada akhir Iterasi 50

5 6 10 13 14 27 28 28

DAFTAR LAMPIRAN 1 2 3 4

Pembangkitan bilangan acak untuk setiap kromosom Perhitungan jarak setiap rute/kromosom Sintaks dan hasil software Matlab R2008b untuk implementasi VRP Sintaks dan hasil software LINGO 11.0

31 31 33 39

PENDAHULUAN Latar Belakang Transportasi merupakan bidang penting dalam industri logistik atau pengiriman barang. Ada beberapa masalah yang harus diperhatikan dalam transportasi barang, misalkan waktu pengiriman, keselamatan, keamanan, dan biaya pengiriman barang. Transportasi yang diharapkan adalah transportasi dengan waktu pengiriman seminimal mungkin, barang aman dan selamat sampai tujuan, dan biaya pengiriman minimum. Pemilihan kendaraan dan jalur transportasi yang tepat dapat menekan biaya transportasi. Salah satu masalah transportasi adalah traveling salesman problem (TSP). TSP adalah masalah penentuan rute terpendek seorang salesman untuk mengunjungi beberapa kota dengan ketentuan setiap kota hanya dapat dikunjungi tepat satu kali. TSP tidak mempertimbangkan kapasitas pengangkutan atau permintaan dari kota yang dikunjungi. Namun dalam beberapa kasus transportasi, terdapat kendala-kendala yang lebih kompleks, sehingga TSP dikembangkan menjadi vehicle routing problem (VRP). VRP adalah masalah penentuan rute terpendek sekelompok kendaraan atau salesman yang harus mengunjungi beberapa kota dengan mempertimbangkan kapasitas kendaraan dan permintaan di tiap kota. VRP termasuk dalam masalah optimasi kombinatorial dan masuk ke dalam kelas NP hard problem (Sarwadi dan Anjar 2004). Karenanya, penyelesaian VRP berukuran besar dengan metode eksak akan memerlukan waktu komputasi yang lama, sehingga pada umumnya VRP berukuran besar diselesaikan dengan metode pendekatan atau heuristik. Beberapa metode heuristik antara lain metode saving, algoritme sweep, algoritme tabu search, dan algoritme genetika. Algoritme genetika dikembangkan berdasarkan konsep evolusi pada makhluk hidup. Proses evolusi pada makhluk hidup diharapkan akan menghasilkan individu baru atau keturunan dengan sifat-sifat unggul dan mampu bertahan terhadap tantangan lingkungan. Tujuan Penelitian Tujuan dari karya ilmiah ini ialah mendeskripsikan dan menyelesaikan vehicle routing problem dengan menggunakan algoritme genetika. Ruang Lingkup Penelitian Penelitian ini menguraikan algoritme genetika menggunakan metode stochastic universal sampling untuk seleksi induk, order crossover untuk kawin silang, dan insertion untuk mutasi. Implementasi algoritme genetika untuk menyelesaikan VRP menggunakan beberapa asumsi dan data hipotetik yang umum digunakan dalam VRP.

2

TINJAUAN PUSTAKA Formulasi VRP Menggunakan Interger Linear Programming Vehicle routing problem (VRP) diakui merupakan salah satu pengalaman tersukses dalam riset operasi. VRP dipublikasikan oleh Dantzig dan Ramser pada tahun 1959. VRP adalah masalah penentuan rute bagi sekelompok kendaraan sehingga total jarak yang ditempuh oleh semua kendaraan adalah minimum. Kendaraan-kendaraan tersebut memiliki kapasitas tertentu dan berangkat dari satu depot untuk melayani atau mengunjungi beberapa konsumen atau pelanggan. Setelah selesai melayani semua konsumen atau pelanggan, setiap kendaraan harus kembali ke depot. Agar mudah dipahami VRP ini diformulasikan dalam bentuk Integer Linear Programming (ILP) sebagai berikut (Wilck 2009). Himpunan = Himpunan semua pelanggan = Himpunan semua kendaraan Indeks = Indeks yang menyatakan pelanggan, indeks i,j = 0 menunjukkan depot = Indeks yang menyatakan kendaraan Parameter = Banyaknya kendaraan = Banyaknya pelanggan = Kapasitas kendaraan = Jarak dari pelanggan i ke j = Banyaknya permintaan pelanggan i Variabel Keputusan = Variabel bantuan untuk mengatasi terjadinya subrute pada pelanggan i oleh kendaraan k. 1, jika kendaraan k mengunjungi pelanggan j setelah pelanggan i = 0, lainnya

{

Fungsi Tujuan Fungsi tujuan atau fungsi objektif dari VRP adalah menentukan rute yang meminimumkan total jarak tempuh kendaraan dengan memenuhi semua kendalanya, yaitu ∑∑∑

3 Kendala 1. Setiap pelanggan hanya dilayani sekali oleh satu kendaraan ∑∑ 2.

Semua kendaraan harus berangkat dari depot, yaitu ∑

3.

Semua kendaraan harus kembali ke depot ∑

4.

Rute harus kontinu, artinya setiap kendaraan yang mengunjungi suatu pelanggan pasti akan meninggalkan pelanggan tersebut ∑

5.

∑

Semua kendaraan tidak boleh melayani melebihi kapasitasnya ∑∑

6.

Eliminasi subrute pada pelanggan i

7.

Setiap kendaraan tidak boleh mengunjungi kembali pelanggan yang sama

8.

Kendala biner

{

}

Algoritme Genetika Algoritme genetika (AG) pertama kali dikemukakan oleh John Holland pada tahun 1975. Algoritme genetika adalah algoritme optimasi yang dikonstruksi mengikuti proses evolusi dalam bidang biologi. Evolusi mengakibatkan perubahan materi genetik pada sebuah individu. Evolusi terjadi karena adanya seleksi alam, kawin silang antarindividu, atau mutasi materi genetika pada sebuah individu. Algoritme genetika bekerja menggunakan operator seperti dalam evolusi yaitu seleksi (selection), kawin silang (crossover), dan mutasi (mutation). Banyak dilakukan pengembangan-pengembangan dalam algoritme genetika. Algoritme

4 genetika dapat digunakan untuk menyelesaikan masalah optimasi seperti penjadwalan, penentuan rute, dan permainan (Sivanandam dan Deepa 2008). Beberapa istilah dalam algoritme genetika adalah gen, alel, kromosom, individu, populasi dan generasi. Gen adalah sebuah nilai yang menyatakan satuan dasar dalam proses genetika. Alel adalah nilai-nilai yang terdapat dalam gen. Kromosom adalah kumpulan dari gen-gen yang membentuk satu individu. Individu menyatakan suatu nilai atau keadaan yang merepresentasikan satu solusi yang mungkin dari permasalahan yang dibahas. Populasi adalah kumpulan dari individu-individu, sehingga populasi merupakan himpunan dari beberapa solusi yang mungkin. Generasi menyatakan satu siklus proses evolusi atau satu iterasi dalam algoritme genetika. Algoritme genetika memiliki beberapa sifat yang menjadi ciri-cirinya. Algoritme genetika bekerja secara paralel pada sekumpulan solusi awal sehingga dapat mempercepat penemuan solusi terbaik. Semakin besar ukuran solusi atau populasi awal akan memperluas daerah pencarian solusi oleh algoritme genetika. Penggunaan fungsi fitness untuk mengevaluasi sebuah solusi membuat algoritme genetika dapat diterapkan pada masalah pengoptimuman diskret maupun kontinu. Algoritme genetika bersifat probabilistik karena menggunakan peluang sebagai parameter dalam operasi evolusi. Algoritme genetika tidak bekerja secara langsung pada parameter-parameter permasalahan, namun bekerja pada tahap gen. Agar sebuah permasalahan dapat diselesaikan dengan algoritme genetika, perlu dilakukan pengodean (encoding) dari permasalahan nyata ke dalam bentuk yang dapat diproses dengan algoritme genetika (Sivanandam dan Deepa 2008). Algoritme genetika bekerja secara iteratif. Pada setiap ulangan, proses seleksi, kawin silang, dan mutasi dilakukan dengan peluang tertentu. Seleksi dilakukan untuk memilih individu-individu terbaik pada suatu generasi. Kawin silang adalah upaya merekombinasi generasi selanjutnya yang melibatkan dua individu. Mutasi bertujuan memperbaiki variasi gen pada sebuah individu. Proses ini berlanjut hingga didapat individu terbaik atau kriteria penghentian telah tercapai. Secara umum langkah dasar algoritme genetika adalah sebagai berikut (Wilck 2009): 1. mengodekan permasalahan ke dalam bentuk yang dapat diproses dengan algoritme genetika dan penentuan parameter-parameter, 2. membangkitkan populasi awal sebagai solusi awal permasalahan, 3. menyeleksi individu terbaik dengan menggunakan fungsi fitness untuk proses kawin silang dan mutasi, 4. memproduksi individu-individu baru atau anak (offspring) dengan proses kawin silang, 5. merekombinasi gen-gen anak hasil kawin silang secara acak dengan proses mutasi, 6. melakukan perbaikan dan penggantian generasi lama dengan generasi baru, 7. mengulangi langkah 3 sampai 6 hingga kriteria penghentian tercapai. Gambar 1 menunjukkan cara kerja algoritme genetika secara umum. Selanjutnya akan dijelaskan langkah-langkah algoritme genetika secara lebih rinci.

5 mulai

encoding

Solusi awal

Hitung fitness

Ya Output final

Kriteria penghentian tercapai?

Tidak Seleksi parents selesai Tidak r < Pc ?

Ya Crossover

Tidak r < Pm ?

Ya Mutasi

Hitung fitness offspring

Penggantian dan Perbaikan

Gambar 1 Diagram alir algoritme genetika

1.

Pengodean dan Penentuan Parameter Pengodean adalah metode bagaimana merepresentasikan masalah yang akan diselesaikan ke dalam bentuk gen-gen dan kromosom. Nilai sebuah gen (alel) dapat berupa biner, bilangan real, bilangan bulat, atau daftar aturan yang dapat diproses algoritme genetika. Metode pengodean tersebut berbeda-beda sesuai

6 dengan masalah yang akan diselesaikan. Sebuah metode pengodean yang cocok untuk suatu masalah tidak dijamin cocok untuk masalah yang lain. Metode pengodean biner adalah metode yang umum digunakan. Pada metode ini hanya tersedia dua kemungkinan nilai gen yaitu 0 atau 1. Individu atau kromosom dinyatakan sebagai sederet gen-gen yang merepresentasikan sebuah solusi. Panjang kromosom ditentukan berdasarkan batasan masalah yang akan diselesaikan. Misalkan untuk mencari nilai maksimum sebuah fungsi dalam dua dimensi. Solusi dinyatakan sebagai titik koordinat . Masalah ini dapat direpresentasikan dengan metode pengodean biner. Misalkan = (2,5), sehingga dengan notasi biner = 0010 dan = 0101. Dalam contoh ini nilai-nilai dan dibatasi hanya sampai empat bit saja, sehingga (2,5) sebagai sebuah kromosom atau individu dinotasikan dalam biner menjadi 00100101 (Hopgood 2001). Metode pengodean yang lain yaitu dengan bilangan bulat. TSP dapat dikodekan ke dalam algoritme genetika dalam bentuk bilangan bulat. Misalkan kita akan mengodekan TSP dengan 7 pelanggan. Pelanggan yang akan dikunjungi diberi indeks bilangan bulat 1 sampai 7. Solusi yang diharapkan berupa permutasi bilangan 1 sampai 7 yang merepresentasikan urutan kunjungan ke pelangganpelanggan tersebut, sehingga solusi 2-4-1-3-5-6-7 berarti salesman berkunjung dari depot ke pelanggan 2, kemudian ke pelanggan 4, dan seterusnya hingga kembali ke depot lagi.

2

4

1

3

5

6

7

Satu kromosom/individu

populasi Alel

5

7

Gen

1

2

3

6

4

Satu kromosom/individu

Gambar 2 Ilustrasi kromosom bilangan bulat

Parameter-parameter yang harus ditentukan adalah ukuran populasi (pop_size), peluang kawin silang ( ), peluang mutasi ( ) dan kriteria penghentian ( ). Ukuran populasi menunjukkan banyaknya individu awal yang akan dibangkitkan dan diproses dengan algoritme genetika. Peluang kawin silang dan mutasi menunjukkan peluang sebuah individu terpilih untuk mengalami kawin silang dan mutasi. Beberapa kriteria penghentian yang dapat digunakan adalah generasi maksimum, waktu maksimum, dan nilai fitness yang tidak berubah. Terkait penentuan parameter, Hopgood (2001:200) menyatakan “Pedoman De Jong masih umum digunakan, yaitu peluang kawin silang yang relatif tinggi (0.6 – 0.7), peluang mutasi yang relatif rendah (sebesar 1/ untuk kromosom dengan panjang , dan ukuran populasi yang sedang (50 – 500)”. Ukuran populasi awal yang dibangkitkan bergantung pada kompleksitas permasalahan. Semakin besar ukuran populasi yang dibangkitkan semakin baik

7 karena akan memperluas daerah pencarian, sehingga solusi yang diharapkan dapat bersifat optimum global. Selama proses pencarian solusi, parameter-parameter tersebut dapat saja berubah. 2.

Pembangkitan Populasi Awal Pembangkitan populasi awal adalah proses membangkitkan individuindividu awal yang selanjutnya akan diproses dengan algoritme genetika. Populasi awal biasanya dibangkitkan secara acak. Hal ini untuk menjamin bahwa semua alel memiliki peluang yang sama untuk muncul. Kromosom yang acak akan memperluas daerah pencarian solusi. Semakin luas daerah pencarian solusi, diharapkan solusi yang didapatkan bersifat optimum global. Metode pembangkitan populasi awal yang umum digunakan adalah random generator. Metode ini melibatkan bilangan acak untuk mengurutkan gen-gen pada kromosom. Bilangan acak dibangkitkan sebanyak jumlah gen dalam kromosom. Satu gen memiliki satu nilai bilangan acak. Kemudian gen-gen diurutkan berdasarkan nilai bilangan acaknya yang terkecil hingga yang terbesar. Misalkan sebuah kromosom dengan 7 gen sebagai berikut : gen 1 2 3 4 5 6 7 random (0,1) 0.23 0.82 0.45 0.74 0.67 0.11 0.56. Setelah bilangan acak tersebut diurutkan dari yang terkecil hingga terbesar didapatkan kromosom dengan urutan gen menjadi 6 3.

1

3

7

5

4

2.

Seleksi Seleksi dilakukan untuk memilih individu-individu terbaik yang akan dijadikan induk (parent) untuk proses kawin silang dan mutasi. Pada proses ini diharapkan induk yang baik akan menghasilkan anak yang baik. Beberapa metode seleksi antara lain random selection, Roulette wheel, rank selection, tournament selection, Boltzmann selection, stochastic universal sampling, dan elitism. Sebelum menyeleksi, terlebih dahulu ditentukan kriteria atau ukuran yang menyatakan suatu individu baik atau buruk. Tingkat kebaikan dari individuindividu tersebut diukur dengan fungsi fitness. Semakin tinggi nilai fitness suatu individu, semakin baik individu tersebut sehingga memiliki peluang lebih besar untuk terpilih sebagai induk (Sivanandam dan Deepa 2008). Bentuk fungsi fitness bisa bermacam-macam, bergantung pada parameter apa saja yang menjadi pertimbangan menilai sebuah individu baik atau buruk. Tujuan dan kendala-kendala yang tidak boleh dilanggar adalah contoh parameter dalam menentukan fungsi fitness. Misalkan dalam TSP atau VRP hal yang menjadi pertimbangan adalah jarak atau biaya perjalanan, kapasitas kendaraan, dan besarnya permintaan pelanggan. Penalti juga dapat menjadi pertimbangan membentuk fungsi fitness. Penalti diberikan sebagai hukuman jika ada kendala yang dilanggar. Karenanya, dengan mempertimbangkan penalti akan mempengaruhi bentuk fungsi fitness. Tentu saja dengan adanya penalti akan membuat nilai fitness semakin kecil. Misalkan dalam TSP atau VRP, setiap kendaraan memiliki kendala kapasitas maksimal. Jika kendaraan tersebut memilih rute yang melebihi kapasitasnya maka akan diberikan penalti pada rute tersebut.

8 4.

Kawin Silang Kawin silang bertujuan memproduksi individu-individu baru dari indukinduk terbaik yang dipilih sebelumnya. Kawin silang akan mengeksploitasi solusi yang didapat sebelumnya. Kawin silang antara dua induk akan menghasilkan dua anak (offspring). Sebelum dilakukan kawin silang, sudah ditentukan parameter peluang kawin silang yaitu peluang dilakukannya kawin silang pada individu yang terpilih pada proses sebelumnya. Dilakukan atau tidaknya kawin silang, ditentukan menggunakan bilangan acak ( ) antara 0 sampai 1. Jika < maka kawin silang dilakukan pada induk terpilih. Jika maka kawin silang tidak dilakukan, sehingga semua gen induk akan diturunkan kepada generasi selanjutnya. Beberapa metode kawin silang antara lain kawin silang satu titik, kawin silang dua titik, kawin silang banyak titik, kawin silang aritmatika, partial matched crossover (PMX), order crossover (OX), dan cycle crossover (CX) (Sivanandam dan Deepa 2008). 5.

Mutasi Mutasi bertujuan mempertahankan keragaman gen pada populasi dengan cara mengembalikan gen yang hilang atau memunculkan gen yang belum pernah muncul pada generasi sebelumnya. Mutasi akan menjelajahi lebih dalam solusi sebelumnya sehingga diharapkan solusi yang didapat tidak berkisar pada optimum lokal saja (Sivanandam dan Deepa 2008). Sebelum dilakukan mutasi, sudah ditentukan parameter peluang mutasi. Peluang mutasi dipandang sebagai persentase gen yang diharapkan mengalami mutasi dari jumlah total gen pada populasi. Dilakukan atau tidaknya mutasi, ditentukan menggunakan bilangan acak ( ) antara 0 sampai 1. Jika < , maka mutasi dilakukan dan sebaliknya, jika maka mutasi tidak dilakukan. Beberapa metode mutasi antara lain dengan penyisipan, flipping, interchanging, dan reversing (Sivanandam dan Deepa 2008). Metode mutasi flipping digunakan pada kromosom biner yaitu mengganti gen 0 dengan 1 dan gen 1 dengan 0 berdasarkan sembarang kromosom yang dibangkitkan acak. Metode mutasi interchanging dilakukan dengan cara saling menukarkan dua posisi gen secara acak. Metode mutasi reversing dilakukan dengan cara membalik urutan gen-gen terpilih. 6.

Perbaikan dan Penggantian Pada tahap perbaikan, dilakukan pemeriksaan pada kromosom anak. Kromosom yang kelebihan gen akan dikurangi pada gen yang kelebihan. Kromosom yang kekurangan gen akan disisipkan gen yang hilang. Posisi tempat penyisipan gen dapat dipilih secara acak. Perbaikan kromosom ini dilakukan hanya untuk kromosom yang mengalami perubahan jumlah atau jenis gen karena proses kawin silang atau mutasi. Hal ini bisa terjadi pada kromosom dengan repesentasi bilangan biner. Pada tahap penggantian, ukuran populasi dipertahankan tetap. Secara umum terdapat dua tipe penggantian generasi. Tipe pertama, generasi berikutnya adalah semua individu baru atau anak semua. Tipe kedua, generasi berikutnya adalah individu baru ditambah individu sebelumnya dengan nilai fitness yang terbesar. Individu lama akan digantikan oleh individu baru yang memiliki nilai fitness lebih baik. Individu baru adalah anak hasil kawin silang atau mutasi.

9 Pada tahun 2004, Sarwadi dan Anjar telah menyelesaikan VRP dengan menggunakan algoritme genetika dengan mempertimbangkan jarak pada penentuan fungsi fitness-nya. Mereka juga membandingkan solusi yang didapat antara algoritme genetika dan metode saving. Pada penelitian yang dilakukan oleh Kusuma dan Aji (2013) tentang studi kasus VRP dengan algoritme genetika, kromosom dibagi menjadi beberapa blok yang merepresentasikan kendaraankendaraan. Pada penelitian ini, fungsi fitness yang digunakan mempertimbangkan jarak dan penalti yang diterima setiap individu.

IMPLEMENTASI ALGORITME GENETIKA PADA VRP Penelitian ini menggunakan data hipotetik. Hal ini bertujuan untuk mempermudah implementasi dan memahami bagaimana algoritme genetika bekerja. Penelitian ini mengasumsikan jarak antarpelanggan ( ) simetrik. Jarak pelanggan A ke pelanggan B sama dengan jarak pelanggan B ke pelanggan A. Permintaan setiap pelanggan ( ) telah diketahui dan kapasitas setiap kendaraan sama. Pandang sebuah VRP dengan jumlah pelanggan ( ) = 9 dan jumlah kendaraan ( ) = 3. Setiap kendaraan memiliki kapasitas maksimum ( ) = 10. Setiap kendaraan harus berangkat dari depot dan kembali ke depot lagi. Data dan diberikan pada Tabel 1.

Tabel 1 Jarak antarpelanggan dan permintaan Jarak antarpelanggan (km) Pelanggan ke-i 0 1 2 3 4 5 6 a 0 0 2 5 1 5 4 3 1 2 0 5 3 3 4 4 2 5 5 0 2 3 2 3 3 1 3 2 0 5 5 3 4 5 3 3 5 0 4 2 5 4 4 2 5 4 0 1 6 3 4 3 3 2 1 0 7 5 2 5 2 2 2 4 8 5 1 3 2 4 1 3 9 2 2 5 2 2 3 4 a

b

7 5 2 5 2 2 2 4 0 5 4

8 5 1 3 2 4 1 3 5 0 1

9 2 2 5 2 2 3 4 4 1 0

0 3 3 2 5 2 2 5 2 2

Pelanggan 0 dianggap sebagai depot; bPermintaan pelanggan (tanpa satuan)

Solusi Manual Subbab ini mendeskripsikan penerapan algoritme genetika secara manual untuk VRP di atas. Sesuai diagram alir algoritme genetika, proses kawin silang dan mutasi akan dilakukan berulang-ulang. Satu iterasi atau perulangan dapat dipandang sebagai siklus satu generasi. Pada akhir iterasi didapat generasi baru

10 yang akan menggantikan generasi sebelumnya. Generasi ke-1 adalah individuindividu pada populasi awal yang dibangkitkan secara acak pertama kali. Pendeskripsian algoritme genetika secara manual ini akan dilakukan sampai Iterasi 10. Iterasi 1 I

Pengodean dan Penentuan Parameter VRP di atas akan dikodekan dalam bentuk bilangan bulat antara 1 sampai 9 yang merupakan indeks pelanggan. Solusi yang diharapkan berupa urutan kunjungan ke pelanggan untuk semua kendaraan. Nilai-nilai gen merepresentasikan indeks pelanggan dan satu kromosom dengan panjang 9 gen merepresentasikan satu solusi VRP. Sebuah kromosom atau individu memiliki blok-blok yang merepresentasikan rute masing-masing kendaraan. Setiap kromosom akan memiliki 3 blok karena dalam permasalahan ini menggunakan 3 kendaraan. Blok 1 merepresentasikan rute kendaraan ke-1, Blok 2 merepresentasikan rute kendaraan ke-2, dan Blok 3 merepresentasikan rute kendaraan ke-3 (Kusuma dan Aji 2013). Sebelum dibangkitkan populasi awal, terlebih dahulu ditentukan parameterparameter yang akan digunakan. Ukuran populasi diambil 10 individu untuk mempermudah dalam mendeskripsikan algoritme genetika secara manual, = 0.6, dan = 0.1 sebagai pembulatan dari 1/panjang kromosom. Kriteria penghentian yang digunakan adalah iterasi maksimum. Algoritme genetika dihentikan setelah iterasi ke-10.

Blok 1

Blok 2

Blok 3 satu individu

9

7

1

2

3

6

4

8

5

Gambar 3 Ilustrasi satu individu atau kromosom dengan 3 blok

II

Pembangkitan Populasi Awal Pembangkitan populasi awal menggunakan metode random generator. Kemudian setiap individu dalam populasi awal tersebut dibagi ke dalam tiga blok. Setiap blok merepresentasikan kendaraan dan setiap kendaraan memilki kapasitas maksimum sebesar 10. Hasil pembangkitan 10 bilangan acak antara 0 dan 1 dapat dilihat di Lampiran 1. Selanjutnya dari bilangan acak yang dibangkitkan didapat representasi 10 individu atau kromosom pada populasi awal seperti pada Tabel 2. Sebagai ilustrasi, Kromosom 1 adalah (4 6 5 9 1 3 8 2 7). Hal ini berarti kendaraan ke-1 akan berjalan dari depot mengunjungi Pelanggan 4, 6, dan 5 secara berurutan kemudian kembali ke depot. Kendaraan ke-2 akan berjalan dari depot mengunjungi Pelanggan 9, 1, dan 3 secara berurutan kemudian kembali ke depot. Kendaraan ke-3 akan berjalan dari depot mengunjungi Pelanggan 8, 2, dan 7 secara berurutan kemudian kembali ke depot.

11 Tabel 2 Individu hasil pembangkitan populasi awal Kromosom i Blok 1 Blok 2 1 4 6 5 9 1 2 2 4 5 1 7 3 3 7 9 1 5 4 7 5 8 6 4 5 8 6 4 9 2 6 7 6 8 3 2 7 6 9 2 5 7 8 2 9 6 3 7 9 9 2 6 1 5 10 6 5 7 1 2

III

3 9 2 3 1 5 3 4 7 8

8 3 6 9 5 1 8 1 3 4

Blok 3 2 8 4 2 7 9 1 5 4 9

7 6 8 1 3 4 4 8 8 3

Menghitung Penalti dan Fitness Penghitungan penalti memerlukan penghitungan total permintaan yang harus dilayani. Jika suatu kendaraan harus melayani melebihi kapasitasnya maka dikenakan penalti. Total penalti pada sebuah kromosom adalah penjumlahan penalti dari setiap blok. Sebagai contoh, Kromosom 1 (4 6 5 9 1 3 8 2 7) dibagi menjadi Blok 1 (4 6 5), Blok 2 (9 1 3) dan Blok 3 (8 2 7). Kendaraan 1 melayani Pelanggan 4, 6, dan 5 dengan besar permintaan masing-masing berturutturut adalah 5, 2, dan 2. Total permintaan yang harus dipenuhi kendaraan ke-1 adalah 5 + 2 + 2 = 9, sehingga kendaraan ke-1 tidak mendapatkan penalti karena total permintaan yang harus dilayani kurang dari kapasitas kendaraan. Total permintaan yang harus dipenuhi kendaraan ke-2 adalah 7 dan total permintaan yang harus dipenuhi kendaraan 3 adalah 10. Kromosom 1 tidak mendapatkan penalti karena semua semua pelanggan dapat terlayani oleh kendaraan. Penghitungan nilai fitness dalam VRP ini mempertimbangkan total jarak yang ditempuh dan penalti. Bentuk fungsi fitness yang digunakan menunjukkan semakin besar jarak dan penalti, maka nilai fitness-nya semakin kecil. Mengacu pada Sarwadi dan Anjar (2014), langkah-langkah mencari nilai fitness dan peluang kumulatif tiap individu untuk terpilih dalam proses seleksi adalah sebagai berikut: 1. mencari jarak tempuh ( ) dan penalti ( ) masing-masing individu, 2. nilai fitness tiap individu ( ) dirumuskan

3. mencari total fitness dari seluruh individu ∑ 4. mencari peluang fitness tiap individu ( )

∑

12 5. mencari peluang kumulatif tiap individu ∑

Setiap blok dihitung jaraknya. Jarak kromosom adalah penjumlahan jarak dari ketiga blok tersebut. Sebagai contoh untuk Kromosom 1, pada Blok 1, jarak dari depot ke pelanggan 4 adalah 5 km, jarak dari pelanggan 4 ke pelanggan 6 adalah 2 km, jarak dari pelanggan 6 ke pelanggan 5 adalah 1 km, dan jarak dari pelanggan 5 ke depot adalah 4 km, sehingga total jarak Blok 1 adalah 5 + 2 + 1 + 4 = 12 km. Total jarak Blok 2 adalah 2 + 2 + 3 + 1 = 8 km dan total jarak Blok 3 adalah 5 + 3 + 5 + 5 = 18 km. Total jarak untuk Kromosom 1 ( ) adalah 12 + 8 + 18 = 38 km. Tabel 3 menunjukkan total jarak, permintaan tiap blok, penalti, nilai fitness, dan peluang kumulatif tiap kromosom pada populasi awal. Penghitungan nilai fitness dan peluang kumulatif menggunakan bantuan program MS. Excel. Perincian perhitungan total jarak, permintaan, dan penalti tiap kromosom disediakan dalam Lampiran 2.

Tabel 3 Nilai fitness dan peluang kumulatif individu pada populasi awal Kromosom Permintaan blok i 1 2 3 1 38 9 7 10 0 0.026316 0.09973 2 35 10 10 6 0 0.028571 0.10827 3 36 9 8 9 0 0.027778 0.10527 4 38 9 9 8 0 0.026316 0.09973 5 38 9 8 9 0 0.026316 0.09973 6 37 9 7 10 0 0.027027 0.10242 7 40 7 9 10 0 0.025000 0.09474 8 39 7 12 7 2 0.024390 0.09243 9 41 7 10 9 0 0.024390 0.09243 10 36 9 8 9 0 0.027778 0.10527 Total fitness 0.263882

IV

0.10 0.21 0.31 0.41 0.51 0.62 0.71 0.80 0.89 1.00

Pemilihan Parent dengan Pengambilan Contoh Universal Stokastik Penelitian ini menggunakan metode stochastic universal sampling dalam proses seleksinya agar setiap individu memiliki peluang terpilih yang hampir sama. Setiap individu diurutkan dalam sebuah garis linear sepanjang 1 satuan. Besarnya bagian setiap individu dalam garis sama dengan besarnya peluang akumulatif fitness. Kemudian ditentukan banyaknya induk yang akan dipilih, dapat digunakan rumus Pc × pop_size, sehingga dalam penelitian ini akan dipilih 0.6 × 10 = 6 individu untuk menjadi induk. Pemilihan enam individu tersebut menggunakan penunjuk (pointer). Jarak antarenam pointer tersebut ditentukan dengan rumus 1/ , dengan adalah banyaknya individu yang akan dipilih. Jarak antar-pointer dalam penelitian ini adalah 1/6 = 0.167. Kemudian letak pointer

13 pertama ditentukan dengan membangkitkan bilangan acak antara 0 dan 0.167 (Sivanandam dan Deepa 2008). Pembangkitan bilangan acak antara 0 dan 0.167 diperoleh bilangan 0.07, sehingga pointer ke-1 berada di titik 0.07, pointer ke-2 di titik 0.07 + 0.167 = 0.237, dan seterusnya. Titik 0.07 berada pada daerah peluang kumulatif Kromosom 1, sehingga Kromosom 1 terpilih sebagai induk dan seterusnya. Pada populasi awal ini yang terpilih sebagai induk adalah Kromosom 1, 3, 4, 6, 8, dan 10. Untuk lebih jelasnya, dapat dilihat pada Gambar 4 berikut.

pointer 1 (0.07)

0.0

1

0.1

pointer 2 (0.237)

2

0.21

3

pointer 3 (0.404)

0.31

4

0.41

pointer 4 (0.571)

5

0.51

6

0.62

pointer 5 (0.738)

7

0.71

8

pointer 6 (0.905)

0.81

9

0.89

10

1.0

Gambar 4 Letak pointer untuk populasi awal

V

Kawin Silang Penentuan dilakukan kawin silang atau tidak dari individu terpilih melibatkan pembangkitan bilangan acak r antara 0 dan 1. Jika < maka kawin silang dilakukan. Parameter sudah ditentukan nilainya pada tahap sebelumnya, yaitu sebesar 0.6. Pembangkitan bilangan acak diperoleh = 0.4, sehingga kawin silang dilakukan. Penelitian ini menggunakan metode order crossover dengan dua titik potong untuk melakukan kawin silang. Dua induk yang akan dilakukan kawin silang dipilih secara acak dari enam induk yang sudah terpilih. Hasil dari pengacakan mendapatkan kawin silang dilakukan antara Kromosom 1 dengan 6, Kromosom 3 dengan 4, dan Kromosom 8 dengan 10. Sebagai penjelasan kawin silang dengan metode order crossover dengan dua titik potong, berikut ini diberikan contoh kawin silang antara Kromosom 1 dan Kromosom 6. Kromosom 1 4 6 5 9 1 3 8 2 7 Kromosom 6 7 6 8 3 2 5 1 9 4

1.

2.

Langkah-langkah order crossover dengan dua titik potong: Membangkitkan dua bilangan bulat acak antara 1 dan panjang kromosom -1 sebagai dua titik potong untuk memilih substring dari kedua induk. Hasil pengacakan didapat titik 3 dan 6 sebagai titik potong. Gen-gen ke-3 sampai ke-6 pada kromosom induk menjadi substring yang akan dipertukarkan. Kromosom 1 4 6 5 9 1 3 8 2 7 Kromosom 6 7 6 8 3 2 5 1 9 4 Kromosom anak didapat dengan menukar substring Kromosom 1 (induk pertama) dengan Kromosom 6 (induk kedua). Gen-gen yang lain dibiarkan kosong terlebih dahulu. Anak 1 _ _ 8 3 2 5 _ _ _ Anak 2 _ _ 5 9 1 3 _ _ _

14 3.

Mengisikan gen-gen induk pertama kepada gen-gen Anak 1 (anak pertama) yang dimulai dari gen setelah titik potong kedua hingga akhir kromosom kemudian dilanjutkan dari gen pertama hingga gen pada titik potong kedua. Apabila gen tersebut sudah ada di substring anak, maka gen tersebut dilewati atau tidak diwariskan kepada anak. Gen 8, 2, 3, dan 5 dari Kromosom 1 sudah ada di substring Anak 1, sehingga gen-gen tersebut tidak diisikan ke Anak 1. Anak 1 9 1 8 3 2 5 7 4 6 4. Mengisikan gen-gen Kromosom 6 kepada gen-gen Anak 2 dengan proses yang sama dengan langkah 3. Gen 1, 9, 3, dan 5 dari Kromosom 6 sudah ada di substring Anak 2, sehingga gen-gen tersebut tidak diisikan ke Anak 2. Anak 2 8 2 5 9 1 3 4 7 6 Dengan cara yang serupa, didapat anak-anak dari kawin silang antara Kromosom 3 dengan 4 dan Kromosom 8 dan 10 seperti dalam Tabel 4. Substring yang ditandai menunjukkan substring yang dikawinsilangkan.

Tabel 4 Anak hasil kawin silang pada Iterasi 1 Induk Kromosom induk Anak Kromosom 1 4 6 5 9 1 3 8 2 7 Anak 1 Kromosom 6 7 6 8 3 2 5 1 9 4 Anak 2 Kromosom 3 3 7 9 1 5 2 6 4 8 Anak 3 Kromosom 4 7 5 8 6 4 3 9 2 1 Anak 4 Kromosom 8 2 9 6 3 7 4 1 5 8 Anak 5 Kromosom 10 6 5 7 1 2 8 4 9 3 Anak 6

Kromosom anak 1 8 3 2 5 7 4 6 2 5 9 1 3 4 7 6 2 8 6 4 3 7 9 1 3 9 1 5 2 7 8 6 3 7 1 5 8 4 9 2 7 2 8 9 4 1 5 3

9 8 5 4 6 6

VI

Mutasi Sebelum mutasi dilakukan, dibangkitan bilangan acak antara 0 dan 1. Jika maka mutasi dilakukan. Peluang mutasi = 0,1 merepresentasikan sebesar 10% dari gen-gen anak mengalami mutasi. Hasil pembangkitan bilangan acak untuk keenam anak menghasilkan mutasi dilakukan hanya pada Anak 1 saja. Metode mutasi yang digunakan adalah metode insertion. Dua posisi gen dipilih secara acak sebagai posisi gen yang dipotong dan posisi gen akan disisipkan. Kromosom Anak 1 akan dipotong pada gen kedua dan disisipkan di posisi setelah gen kelima, sehingga Gen 1 dipotong dan disisipkan setelah Gen 2. disisipkan

dipotong

Anak 1

9

Hasil Mutasi

9

1

8

8

3

2

3

2

1

5

5

7

7

4

4

6

6

Gambar 5 Hasil mutasi Anak 1 dengan motede insertion

15

Proses perbaikan tidak diperlukan dalam implementasi ini karena selama proses kawin silang dan mutasi kromosom tidak mengalami perubahan banyaknya gen. Setiap kromsosom baru hasil kawin silang atau mutasi pasti akan memiliki 9 gen yang berbeda, sehingga setiap pelanggan pasti akan dikunjungi. VI

Penggantian Proses penggantian dilakukan untuk menjamin bahwa individu pada generasi selanjutnya adalah individu terbaik. Metode penggantian yang digunakan adalah metode steady state update. Ukuran populasi pada setiap generasi dipertahankan tetap 10 individu. Individu yang memiliki nilai fitness terendah akan dihapus dari generasi atau populasi. Nilai fitness dari setiap anak disajikan dalam Tabel 5. Nilai fitness anak akan dibandingkan dengan nilai fitness individu seperti dalam Tabel 3. Selanjutnya enam individu dengan nilai terendah akan dihapus dari populasi yaitu anak ke-4, 5, dan 6 serta individu ke-7, 8, dan 9. Individu ke-7, 8, dan 9 akan digantikan oleh anak ke-1, 2, dan 3, sehingga didapat populasi baru sebagai generasi ke-2 yang diberikan dalam Tabel 6. Karena iterasi dalam algoritme belum mencapai batas iterasi maksimum, iterasi dilanjutkan untuk Iterasi 2.

Tabel 5 Nilai fitness anak pada Iterasi 1 Anak Permintaan blok ke-i 1 2 3 1 36 6 8 12 2 2 36 7 7 12 2 3 38 7 10 10 0 4 43 9 8 9 0 5 42 9 7 10 0 6 42 10 9 7 0 Total fitness

0.026316 0.026316 0.026316 0.023256 0.023810 0.023810 0.149822

0.17565 0.17565 0.17565 0.15522 0.15892 0.15892

0.18 0.35 0.53 0.68 0.84 1.00

Iterasi 2 Individu pada Iterasi 2 akan mengalami proses yang sama dengan individu sebelumnya. Nilai fitness individu pada Iterasi 2 sudah dihitung sebelumnya saat akan membandingkan anak dan induk pada Iterasi 1. Rangkuman nilai fitness individu pada Iterasi 2 disajikan dalam Tabel 7. Proses seleksi induk dilakukan untuk memilih enam individu sebagai induk. Pembangkitan bilangan acak antara 0 dan 0.167 diperoleh bilangan 0.135 sebagai letak pointer ke-1. Letak pointer dan individu terpilih disajikan dalam Tabel 8.

16 Tabel 6 Individu pada generasi ke-2 Kromosom ke-i Blok 1 1 4 6 5 2 2 4 5 3 3 7 9 4 7 5 8 5 8 6 4 6 7 6 8 a 7 9 8 3 a 8 8 2 5 a 9 5 2 8 10 6 5 7 a

9 1 1 6 9 3 2 9 6 1

Blok 2 1 7 5 4 2 2 1 1 4 2

3 9 2 3 1 5 5 3 3 8

8 3 6 9 5 1 7 4 7 4

Blok 3 2 8 4 2 7 9 4 7 9 9

7 6 8 1 3 4 6 6 1 3

individu baru

Nilai fitness

Tabel 7 Nilai fitness dan peluang kumulatif individu pada Iterasi 2 Kromosom Permintaan blok ke-i 1 2 3 1 38 9 7 10 0 0.026316 0.097810 2 35 10 10 6 0 0.028571 0.106194 3 36 9 8 9 0 0.027778 0.103244 4 38 9 9 8 0 0.026316 0.097810 5 38 9 8 9 0 0.026316 0.097810 6 37 9 7 10 0 0.027027 0.100454 7 36 6 8 12 2 0.026316 0.097810 8 36 7 7 12 2 0.026316 0.097810 9 38 7 10 10 0 0.026316 0.097810 10 36 9 8 9 0 0.027778 0.103244 Total fitness 0.269049

0.10 0.20 0.31 0.41 0.50 0.60 0.70 0.80 0.90 1.00

Pemilihan induk

Tabel 8 Pemilihan induk pada Iterasi 2 Pointer ke-i 1 2 Letak pointer 0.135 0.302 Kromosom terpilih 2 3

3 0.469 5

4 0.636 6

5 0.803 9

6 0.97 10

17 Kawin silang Pembangkitan bilangan acak r diperoleh r = 0.37. Karena r < Pc maka kawin silang dilakukan. Pengacakan pasangan kawin silang diperoleh pasangan Kromosom 2 dengan Kromosom 7, Kromosom 3 dengan Kromosom 5, dan Kromosom 9 dengan Kromosom 10.


2 9 5 4 4 1

Kromosom anak 5 1 9 3 8 7 4 2 1 5 7 4 3 8 6 4 9 2 1 8 3 7 9 1 5 2 3 8 3 7 1 2 8 9 5 2 8 6 4 3 9 5

6 6 7 6 6 7

Mutasi Hasil pembangkitan bilangan acak untuk keenam anak menghasilkan keputusan mutasi dilakukan hanya pada Anak 1 dan Anak 4. Anak 1 dan Anak 4 di mutasi dengan titik potong dan titik penyisipan masing-masing adalah (8;3) dan (7;1). Anak 1 2 5 1 9 3 8 7 4 6 Hasil mutasi 2 5 1 4 9 3 8 7 6 Anak 4 4 7 9 1 5 2 3 8 6 Hasil mutasi 4 3 7 9 1 5 2 8 6 Penggantian


0.025000 0.026316 0.025000 0.022222 0.023256 0.026316 0.148110

0.168794 0.177678 0.168794 0.150039 0.157018 0.177678

0.17 0.35 0.52 0.67 0.82 1.00

Nilai fitness anak akan dibandingkan dengan nilai fitness individu pada Tabel 7. Beberapa nilai fitness yang rendah ditandai dan kromosomnya akan dihapus dari populasi. Jika ada dua atau lebih kromosom dengan nilai fitness yang sama maka kromosom yang dipertahankan dipilih secara acak atau kromsom yang tidak terkena penalti. Individu ke-8 diganti dengan anak ke-6. Setelah

18 pengantian diperoleh populasi baru sebagai generasi ke-3 yang dapat dilihat pada Tabel 11. Karena iterasi dalam algoritme belum mencapai batas iterasi maksimum, iterasi dilanjutkan untuk Iterasi 3.

Tabel 11 Individu pada generasi ke-3 Kromosom ke-i Blok 1 1 4 6 5 2 2 4 5 3 3 7 9 4 7 5 8 5 8 6 4 6 7 6 8 7 9 8 3 a 8 1 2 8 9 5 2 8 10 6 5 7 a

9 1 1 6 9 3 2 6 6 1

Blok 2 1 7 5 4 2 2 1 4 4 2

3 9 2 3 1 5 5 3 3 8

8 3 6 9 5 1 7 9 7 4

Blok 3 2 8 4 2 7 9 4 5 9 9

7 6 8 1 3 4 6 7 1 3

individu baru

Iterasi 3 Nilai fitness


0.10 0.20 0.31 0.41 0.50 0.60 0.70 0.80 0.90 1.00

19 Pemilihan induk


3 0.495 5

4 0.662 7

5 0.829 9

6 0.996 10

Kawin silang Pada Iterasi 3 proses kawin silang tidak dilakukan karena pembangkitan bilangan acak r diperoleh r = 0.66692 sehingga r > Pc. Karena kawin silang tidak dilakukan, mutasi tidak dilakukan dan semua individu pada generasi ke-3 menjadi individu pada generasi ke-4. Karena iterasi dalam algoritme belum mencapai batas iterasi maksimum, iterasi dilanjutkan untuk Iterasi 4. Iterasi 4 Nilai fitness Individu pada Iterasi 4 sama dengan Iterasi 3. Individu-individu pada Iterasi 4 dan nilai fitness-nya bisa dilihat pada Tabel 11 dan Tabel 12. Namun pada Iterasi 4 ini dilakukan pemilihan induk baru lagi secara acak. Pada Iterasi 4 proses kawin silang dilakukan karena pembangkitan bilangan acak r diperoleh r = 0.273046 sehingga r < Pc. Pemilihan induk


3 0.429 5

4 0.596 6

5 0.763 8

6 0.93 10

Kawin silang Pengacakan pasangan dilakukan untuk mendapatkan pasangan kawin silang, diperoleh Kromosom 6 dengan 3, Kromosom 5 dengan 8, dan Kromosom 1 dengan 10. Substring terpilih yang akan dikawinsilangkan untuk semua induk sama, yaitu substring pada gen ke-6 dan ke-7. Anak hasil kawin silang pada Iterasi 4 disajikan dalam Tabel 15. Mutasi Hasil pembangkitan bilangan acak r untuk keenam anak diperoleh r < Pm sehingga mutasi tidak dilakukan terhadap anak hasil kawin silang. Algoritme dilanjutkan pada proses penggantian.

20 Tabel 15 Anak hasil kawin silang pada Iterasi 4 Induk Kromosom induk Anak Kromosom 6 7 6 8 3 2 5 1 9 4 Anak 1 Kromosom 3 3 7 9 1 5 2 6 4 8 Anak 2 Kromosom 5 8 6 4 9 2 1 5 7 3 Anak 3 Kromosom 8 1 2 8 6 4 3 9 5 7 Anak 4 Kromosom 1 4 6 5 9 1 3 8 2 7 Anak 5 Kromosom 10 6 5 7 1 2 8 4 9 3 Anak 6

7 3 6 8 6 5

Kromosom anak 8 3 5 1 2 6 9 7 9 2 6 5 1 4 4 2 1 5 3 9 7 6 4 3 9 1 5 7 5 9 1 3 8 4 2 7 1 2 4 3 8 9

4 8 8 2 7 6

Penggantian Nilai fitness anak dan individu pada Iterasi 4 dibandingkan dan dipilih 10 individu terbaik. Tabel nilai fitness individu pada Iterasi 4 sama dengan nilai fitness individu pada Iterasi 3, dapat dilihat pada Tabel 12. Nilai fitness anak pada Iterasi 4 diberikan dalam Tabel 16. Individu ke-1 dan individu ke-7 digantikan oleh anak ke-2 dan anak ke-6 karena nilai fitness-nya lebih tinggi. Setelah pengantian diperoleh populasi baru sebagai generasi ke-5 yang dapat dilihat pada Tabel 17. Karena iterasi dalam algoritme belum mencapai batas iterasi maksimum, iterasi dilanjutkan untuk Iterasi 5. Tabel 16 Nilai fitness anak pada Iterasi 4 Anak Permintaan blok ke-i 1 2 3 1 2 3 4 5 6

45 36 41 38 39 37

9 8 9 9 7 10 10 7 9 9 7 10 6 7 13 10 10 6 Total fitness

0 0 0 0 3 0

Tabel 17 Individu baru pada generasi ke-5 Kromosom ke-i Blok 1 1a 3 7 9 2 2 2 4 5 1 3 3 7 9 1 4 7 5 8 6 5 8 6 4 9 6 7 6 8 3 a 7 5 7 1 2 8 1 2 8 6 9 5 2 8 6 10 6 5 7 1 a

individu baru

0.022222 0.027778 0.024390 0.026316 0.023810 0.027027 0.151543

Blok 2 6 7 5 4 2 2 4 4 4 2

5 9 2 3 1 5 3 3 3 8

0.146640 0.183300 0.160946 0.173653 0.157114 0.178346

1 3 6 9 5 1 8 9 7 4

Blok 3 4 8 4 2 7 9 9 5 9 9

0.15 0.33 0.49 0.66 0.82 1.00

8 6 8 1 3 4 6 7 1 3

21 Iterasi 5 Nilai fitness


0.10 0.21 0.31 0.41 0.50 0.60 0.70 0.80 0.90 1.00

Pemilihan induk


3 0.465 5

4 0.632 7

5 0.799 8

6 0.966 10

Kawin silang Pada Iterasi 5, kawin silang dilakukan karena pembangkitan bilangan acak r diperoleh r = 0.576154 sehingga r < Pc.


5 5 6 8 6 8

Kromosom anak 1 2 8 7 9 4 3 1 7 9 2 8 3 6 4 2 1 7 3 9 5 6 4 3 9 1 5 7 7 1 2 4 3 8 9 7 9 1 5 2 6 4

6 4 8 2 5 3

22 Mutasi Hasil pembangkitan bilangan acak r untuk keenam anak diperoleh r > Pm sehingga mutasi tidak dilakukan terhadap anak hasil kawin silang. Algoritme dilanjutkan pada proses penggantian. Penggantian

Tabel 21 Nilai fitness anak pada Iterasi 5 Anak Permintaan blok ke-i 1 2 3 1 2 3 4 5 6

50 41 31 38 38 40

9 8 9 9 7 10 10 7 9 9 7 10 6 7 13 10 10 6 Total fitness

0 0 0 0 0 0

0.020000 0.024390 0.032258 0.026316 0.026316 0.025000 0.154280

0.129635 0.158091 0.209088 0.170572 0.170572 0.162043

0.13 0.29 0.50 0.67 0.84 1.00

Nilai fitness individu pada Iterasi 5 dapat dilihat pada Tabel 18. Individu ke4 digantikan oleh anak ke-3 karena nilai fitness-nya lebih tinggi. Setelah pengantian diperoleh populasi baru sebagai generasi ke-6 yang dapat dilihat pada Tabel 22. Karena iterasi dalam algoritme belum mencapai batas iterasi maksimum, iterasi dilanjutkan untuk Iterasi 6.

Tabel 22 Individu Kromosom ke-i 1 2 3 4a 5 6 7 8 9 10 a

individu baru

pada generasi ke-6 Blok 1 3 7 9 2 4 5 3 7 9 6 4 2 8 6 4 7 6 8 5 7 1 1 2 8 5 2 8 6 5 7

2 1 1 1 9 3 2 6 6 1

Blok 2 6 7 5 7 2 2 4 4 4 2

5 9 2 3 1 5 3 3 3 8

1 3 6 9 5 1 8 9 7 4

Blok 3 4 8 4 5 7 9 9 5 9 9

8 6 8 8 3 4 6 7 1 3

23 Iterasi 6 Nilai fitness


0.10 0.20 0.30 0.42 0.51 0.61 0.71 0.80 0.90 1.00

Pemilihan induk


3 0.491 5

4 0.658 7

5 0.825 9

6 0.992 10

Kawin silang Pada Iterasi 6 kawin silang tidak dilakukan karena pembangkitan bilangan acak r diperoleh r = 0.657591 sehingga r > Pc. Karena kawin silang tidak dilakukan, mutasi tidak dilakukan dan semua individu pada generasi ke-6 menjadi individu pada generasi ke-7. Karena iterasi dalam algoritme belum mencapai batas iterasi maksimum, iterasi dilanjutkan untuk Iterasi 7. Iterasi 7 Nilai fitness Nilai fitness individu pada Iterasi 7 sama dengan nilai fitness individu pada Iterasi 6. Nilai fitness individu pada Iterasi 6 dapat dilihat pada Tabel 23.

24 Pemilihan induk Tabel 25 Pemilihan induk pada Iterasi 7 Pointer ke-i 1 2 Letak pointer 0.122 0.289 Kromosom terpilih 2 3

3 0.456 5

4 0.623 7

5 0.79 8

6 0.957 10

Kawin silang Pada Iterasi 7 proses kawin silang tidak dilakukan karena pembangkitan bilangan acak r diperoleh r = 0.661623 sehingga r > Pc. Karena kawin silang tidak dilakukan, mutasi tidak dilakukan dan semua individu pada generasi ke-7 menjadi individu pada generasi ke-8. Karena iterasi dalam algoritme belum mencapai batas iterasi maksimum, iterasi dilanjutkan untuk Iterasi 8. Iterasi 8 Nilai fitness Nilai fitness individu pada Iterasi 8 sama dengan nilai fitness individu pada Iterasi 6. Nilai fitness individu pada Iterasi 6 dapat dilihat pada Tabel 23. Pemilihan induk Tabel 26 Pemilihan induk pada Iterasi 8 Pointer ke-i 1 2 Letak pointer 0.136 0.303 Kromosom terpilih 2 3

3 0.47 5

4 0.637 7

5 0.804 8

6 0.971 10

Kawin silang Pada Iterasi 8 proses kawin silang tidak dilakukan karena pembangkitan bilangan acak r didapat r = 0.650385 sehingga r > Pc. Karena kawin silang tidak dilakukan, mutasi tidak dilakukan dan semua individu pada generasi ke-8 menjadi individu pada generasi ke-9. Karena iterasi dalam algoritme belum mencapai batas iterasi maksimum, iterasi dilanjutkan untuk Iterasi 9. Iterasi 9 Nilai fitness Nilai fitness individu pada Iterasi 9 sama dengan nilai fitness individu pada Iterasi 6. Nilai fitness individu pada Iterasi 6 dapat dilihat pada Tabel 23. Pemilihan induk Tabel 27 Pemilihan induk pada Iterasi 9 Pointer ke-i 1 2 Letak pointer 0.039 0.206 Kromosom terpilih 1 3

3 0.373 4

4 0.54 6

5 0.707 7

6 0.874 9

25

Kawin silang Pembangkitan bilangan acak r = 0.020396. Karena r < Pc maka kawin silang dilakukan. Pengacakan pasangan untuk mendapatkan pasangan kawin silang, diperoleh Kromosom 3 dengan 7, Kromosom 1 dengan 9, dan Kromosom 4 dengan 6. Anak hasil kawin silang dapat dilihat dalam Tabel 28.


9 2 1 3 4 6

Kromosom anak 7 1 2 5 6 4 8 3 7 9 1 4 3 8 6 5 2 8 6 4 3 7 9 5 7 9 2 6 5 1 4 8 7 8 3 2 5 1 9 6 8 2 1 7 3 9 5 4

Mutasi Hasil pembangkitan bilangan acak r untuk keenam anak menghasilkan r > Pm sehingga mutasi tidak dilakukan terhadap anak hasil kawin silang. Algoritme dilanjutkan pada proses penggantian. Penggantian Nilai fitness anak dan individu pada Iterasi 9 dibandingkan dan dipilih 10 individu terbaik. Nilai fitness anak pada Iterasi 9 diberikan dalam Tabel 29. Individu ke-5, individu ke-8, dan individu ke-9 digantikan oleh anak ke-1, anak ke-4, dan anak ke-6 karena nilai fitness-nya lebih tinggi. Setelah pengantian diperoleh populasi baru sebagai generasi ke-10 yang dapat dilihat pada Tabel 30. Karena iterasi dalam algoritme belum mencapai batas iterasi maksimum, iterasi dilanjutkan untuk Iterasi 10.


0.030303 0.025000 0.023810 0.027778 0.025641 0.028571 0.161103

0.188097 0.155180 0.147791 0.172423 0.159159 0.177349

0.19 0.34 0.49 0.66 0.82 1.00

26 Tabel 30 Individu pada generasi ke-10 Kromosom ke-i Blok 1 1 3 7 9 2 2 4 5 3 3 7 9 4 6 4 2 a 5 9 7 1 6 7 6 8 7 5 7 1 a 8 3 7 9 a 9 6 8 2 10 6 5 7 a

Blok 2 6 7 5 7 5 2 4 6 7 2

2 1 1 1 2 3 2 2 1 1

5 9 2 3 6 5 3 5 3 8

1 3 6 9 4 1 8 1 9 4

Blok 3 4 8 4 5 8 9 9 4 5 9

8 6 8 8 3 4 6 8 4 3

individu baru

Iterasi 10 Nilai fitness

Tabel 31 Nilai fitness dan peluang kumulatif individu pada Iterasi 10 Kromosom Permintaan blok ke-i 1 2 3 1 36 9 7 10 0 0.027778 0.097511 2 35 10 10 6 0 0.028571 0.100297 3 36 9 8 9 0 0.027778 0.097511 4 31 10 10 6 0 0.032258 0.113238 5 33 10 7 9 0 0.030303 0.106375 6 37 9 7 10 0 0.027027 0.094875 7 37 10 10 6 0 0.027027 0.094875 8 36 9 7 10 0 0.027778 0.097511 9 35 7 10 9 0 0.028571 0.100297 10 36 9 8 9 0 0.027778 0.097511 Total Fitness 0.284869

0.10 0.20 0.30 0.41 0.51 0.61 0.70 0.80 0.90 1.00

Pemilihan induk


3 0.404 4

4 0.571 6

5 0.738 8

6 0.905 10

27 Kawin silang Pada Iterasi 10 proses kawin silang tidak dilakukan karena pembangkitan bilangan acak r diperoleh r = 0.703588 sehingga r > Pc. Karena kawin silang tidak dilakukan, mutasi tidak dilakukan dan semua individu pada generasi ke-10 menjadi individu pada generasi ke-11. Namun karena iterasi dalam algoritme telah mencapai batas iterasi maksimum, iterasi dihentikan. Pada implementasi algoritme genetika secara manual ini telah dilakukan 10 kali iterasi dengan generasi terakhir adalah generasi ke-11. Individu pada generasi ke-11 sama dengan individu pada generasi ke-10 (lihat Tabel 30) karena tidak terjadi kawin silang pada Iterasi 10. Pada generasi ke-11, Kromosom 4 memiliki nilai fitness tertinggi yaitu 0.032258, sehingga Kromosom 4 dipilih sebagai solusi dari VRP. Kromosom 4 dengan rute 6 - 4 - 2 - 1 - 7 - 3 - 9 - 5 – 8 memiliki total jarak tempuh 31 km. Kendaraan 1 melayani konsumen 6, 4, dan 2 kemudian kembali ke depot. Kendaraan 2 melayani konsumen 1, 7, dan 3 kemudian kembali ke depot. Kendaraan 3 melayani konsumen 9, 5, dan 8 kemudian kembali ke depot.

7

1

3

8

K=2 2

4 K=1

5

K=3 Depot

6

9

Gambar 6 Rute optimal pada akhir Iterasi 10

Hasil implementasi algoritme genetika secara manual menunjukkan setiap iterasi mendapatkan hasil yang lebih baik atau sama dibandingkan iterasi sebelumnya. Sampai Iterasi 4 masih ditemukan individu yang mendapatkan penalti. Namun sejak Iterasi 5 tidak ada lagi individu yang mendapat penalti sehingga kendala permintaan pelanggan terpenuhi. Beberapa iterasi memiliki kesamaan dalam pemilihan induk. Induk terpilih pada Iterasi 1 sama dengan induk terpilih pada Iterasi 10. Begitu juga Iterasi 3 dan 6 serta Iterasi 5, 7, dan 8. Namun hal ini tidak berpengaruh pada generasi yang dihasilkan karena penentuan terjadinya kawin silang dan mutasi menggunakan bilangan acak r. Seringnya muncul bilangan acak r yang lebih besar dari Pc atau Pm menyebabkan waktu operasi algoritme lebih cepat, namun daerah pencarian solusi menjadi lebih sempit.

28 Solusi VRP dengan Bantuan Software Selanjutnya untuk menyelesaikan VRP dengan algoritme genetika dan mengetahui apakah algoritme dapat mencapai solusi yang lebih baik, dilakukan penyelesaian dengan bantuan software MATLAB R2008b sampai dengan Iterasi 50. Gambar 7 menunjukkan grafik iterasi dengan nilai fitness maksimum dan rataratanya. Nilai fitness populasi konvergen menuju 0.0345 setelah Iterasi 48. Pada populasi akhir didapatkan dua individu berbeda dengan total jarak optimum 29 km yaitu (6 2 4 9 8 1 3 7 5) dan (9 8 1 6 2 4 3 7 5). Perbedaan dua individu tersebut hanya terletak pada kendaraan mana yang melayani. Sintaks dan hasil populasi terakhir yang bertahan diberikan pada Lampiran 3.

Gambar 7 Grafik nilai fitness terbaik setiap iterasi

8

9

1

5

K=2 4

2 K=1

7

K=3 Depot

6

3

Gambar 8 Rute optimal yang didapat pada akhir Iterasi 50

29 Perbandingan Solusi Eksak dengan Solusi Algoritme Genetika Solusi eksak dari VRP ini didapatkan rute optimum untuk Kendaraan 1 ( 0 – 7 – 4 – 0 ), Kendaraan 2 ( 0 – 3 – 2 – 5 – 6 – 0 ), dan Kendaraan 3 ( 0 – 1 – 8 – 9 – 0 ). Total jarak untuk semua kendaraan adalah 27 km yang merupakan nilai solusi global optimum. Solusi eksak ini didapat dengan menggunakan bantuan software LINGO 11.0. Sintaks dan hasil keluaran software LINGO 11.0 diberikan pada Lampiran 4. Penyelesaian menggunakan algoritme genetika sampai 10 iterasi didapatkan solusi optimum 31 km, sedangkan pencarian sampai 50 iterasi didapatkan solusi optimum 29 km. VRP dalam implementasi ini memiliki kemungkinan solusi sebanyak 9! = 362.880 solusi. Algoritme genetika dalam implementasi manual sampai 10 iterasi telah mengevaluasi kurang dari 10 solusi × 10 iterasi = 100 solusi. Algoritme genetika telah mengeksplorasi daerah pencarian sebesar kurang dari (100/362.880) × 100% = 0.0276%. Sedangkan dalam implementasi menggunakan MATLAB R2008b sampai 50 iterasi, algoritme genetika telah mengevaluasi kurang dari 10 solusi × 50 iterasi = 500 solusi atau sekitar (500/362.880) × 100% = 0.138% solusi. Dapat dikatakan bahwa algoritme genetika cukup baik untuk menemukan solusi yang mendekati global optimum dengan daerah pencarian yang relatif kecil.

SIMPULAN DAN SARAN Simpulan Algoritme genetika dapat digunakan untuk mencari penyelesaian VRP. Algoritme ini merupakan metode pendekatan yang bersifat iteratif untuk menyelesaikan VRP dengan hasil yang tidak dijamin optimum global. Metode pengodean dengan bilangan bulat dapat digunakan untuk menyelesaikan VRP dengan algoritme genetika. Algoritme genetika bekerja cukup efektif, dengan hanya mengeksplorasi daerah pencarian yang relatif kecil didapat solusi yang mendekati solusi optimum global. Semakin besar iterasi yang dilakukan, solusi yang didapat akan semakin mendekati optimum global sampai batas tertentu. Saran Algoritme genetika pada penelitian ini diimplementasikan pada VRP yang hanya mempertimbangkan jarak dan kendala permintaan. Penelitian ini dapat dikembangkan dengan memvariasikan kendala maupun metode yang digunakan dalam algoritme genetika. Kendala time windows dapat ditambahkan pada VRP. Metode-metode lain dalam pemilihan induk, proses kawin silang dan mutasi dapat diterapkan untuk mendapatkan hasil yang lebih baik. Pembagian rute atau blok untuk setiap kendaraan dapat dioptimalkan dengan menerapkan algoritme Greedy atau yang lainnya.

30

DAFTAR PUSTAKA Hopgood AA. 2001. Intelligent Systems for Engineers and Scientists. 2nd ed. New York (US): CRC Press LLC. Kusuma TYT, Aji T. 2013. Algoritma Genetika untuk Penyelesaian Vehicle Routing Problem dengan Pemerataan Beban. JII SUKA. 2(1):4-23. Sarwadi, Anjar KSW. 2004. Algoritma Genetika untuk Penyelesaian Masalah Vehicle Routing. JMK Undip. 7(2).1-10. Sivanandam SN, Deepa SN. 2008. Introduction to Genetic Algorithms. New York (US): Springer Berlin Heidelberg. Wilck JH IV. 2009. Solving the split delivery vehicle routing problem [disertasi]. Pennsylvania (US): The Pennsylvania State University.

31

LAMPIRAN Lampiran 1 Pembangkitan bilangan acak untuk setiap kromosom Kromosom ke-i 1 2 3 4 5 6 7 8 9 10

Nomor Gen 1 0.48 0.44 0.21 0.94 0.50 0.75 0.98 0.72 0.56 0.44

2 0.76 0.02 0.40 0.76 0.48 0.59 0.18 0.03 0.19 0.46

3 0.56 0.80 0.11 0.61 0.98 0.15 0.60 0.58 0.95 0.96

4 0.01 0.03 0.75 0.43 0.25 0.91 1.00 0.70 0.98 0.79

5 0.46 0.33 0.30 0.20 0.60 0.72 0.46 0.94 0.57 0.15

6 0.08 0.94 0.47 0.37 0.23 0.11 0.08 0.48 0.20 0.03

7 0.85 0.47 0.16 0.16 0.67 0.01 0.55 0.63 0.63 0.20

8 0.56 0.87 0.98 0.26 0.22 0.14 0.63 0.97 0.99 0.57

9 0.48 0.75 0.17 0.73 0.42 0.86 0.18 0.14 0.02 0.84

Lampiran 2 Perhitungan jarak setiap rute/kromosom Perhitungan jarak kromosom pada Iterasi 1 Kromosom kei 1 2 3 4 5 6 7 8 9 10

Penjumlahan jarak antarpelanggan dan depot

Total jarak

5+2+1+4+2+2+3+1+5+3+5+5 5+3+4+4+2+2+4+2+1+2+3+3 1+2+4+2+2+4+2+5+3+2+4+5 5+2+1+5+3+2+5+1+2+5+5+2 5+3+2+5+2+5+5+2+4+2+2+1 5+4+3+5+1+2+2+4+2+2+2+5 3+4+5+5+4+2+2+1+5+1+3+5 5+5+4+3+1+2+2+5+2+4+1+5 2+5+3+3+2+4+2+5+1+5+4+5 3+1+2+5+2+5+3+5+5+2+2+1

38 35 36 38 38 37 40 39 41 36

Perhitungan jarak kromosom anak pada Iterasi 1 Anak ke-i


Total jarak

1 2 3 4 5 6

2+1+2+1+5+5+4+4+5+2+2+3 5+3+2+4+2+2+3+1+5+2+4+3 4+2+3+5+3+2+5+2+5+4+2+2 5+5+2+2+2+4+2+5+5+5+3+3 3+3+2+5+2+4+1+5+5+2+5+5 3+4+5+5+5+1+2+5+2+4+5+1

36 36 38 43 42 42

32 Perhitungan jarak kromosom anak pada Iterasi 2 Anak ke-i


Total jarak

1 2 3 4 5 6

5+2+4+2+5+2+2+1+5+5+4+3 2 + 5 + 5+ 2 + 4 + 2 + 2 + 5 + 1 + 2 + 3 + 3 4+1+2+5+2+5+5+2+5+2+2+5 5+5+2+5+2+2+4+4+5+3+3+3 5+5+2+5+2+5+3+5+2+3+1+3 2+5+3+5+3+2+5+1+2+3+2+5

40 36 40 43 41 38



Total jarak

1 2 3 4 5 6

5+5+2+1+4+4+5+5+3+4+2+5 1 + 2 + 4+ 2 + 5 + 3 + 1 + 4 + 2 + 3 + 4 + 5 3 + 2 + 3 + 5 + 2+ 4 + 5 + 1 + 2 + 4 + 5 + 5 5+3+2+5+1+2+2+2+4+2+5+5 3+1+3+2+2+3+2+5+5+3+5+5 4+2+2+2+5+3+5+1+5+1+4+3

45 36 41 38 39 37



Total jarak

1 2 3 4 5 6

4 + 4 + 5 + 5 + 5 + 5 + 4 + 2 + 5 + 5+ 3 + 3 4+4+2+5+2+5+3+5+1+3+2+5 3+2+3+5+2+2+2+1+2+3+1+5 5+3+2+5+1+2+2+2+4+2+5+5 3+4+2+2+5+3+5+1+5+1+3+4 5+5+4+2+2+4+2+5+3+2+5+1

50 41 31 38 38 40



Total jarak

1 2 3 4 5 6

2+4+2+2+5+2+1+3+5+4+2+1 5+5+4+2+2+3+5+1+5+3+1+4 2+5+3+5+3+2+5+1+5+4+3+4 1+2+4+2+5+3+1+4+2+3+4+5 5+2+5+5+1+2+2+4+2+2+4+3 3+3+3+5+2+2+2+1+2+3+4+5

33 40 42 36 37 35

33 Lampiran 3 Sintaks dan hasil software Matlab R2008b untuk implementasi VRP

Sintaks MATLAB R2008b untuk implementasi VRP %***********************MATLAB FOR VRP****************** %By Dedi Hariyanto %Definisi semua variabel %Popu = Matriks 10x9 yang menyatakan 10 kromosom dalam 1 Populasi %Jarak = Matriks jarak 10X10, termasuk depot dan pelanggan %Demand = Vektor/Array (1x10) yang menyatakan demand di setiap kota %(termasuk depot) %Term = Kriteria penghentian, banyaknya iterasi %Popu_Size = Ukuran Populasi %Panjang_Krom= Banyak gen dalam satu kromosom %Pc = Peluang Kawin silang %Pm = Peluang Mutasi %W = Kapasitas kendaraan %Z(i) = Total jarak di kromosom i %load(i,k) = total muatan/demand yang harus dipenuhi kendaraan ke k pada individu/rute i %Pinalti(i,k) = Pinalti di kendaraan ke k pada rute ke i %Total_Pinalti(i) = Total pinalti pada rute ke i %F(i) = Nilai fitness kromosom i %P(i) = Probabilitas kromosom i %Q(i) = Probabilitas Kumulatif kromosom i %Iterasi(i)= Iterasi ke i %Parent = Kromosom dari Popu yang terpilih jadi induk %Child = Kromosom Anak hasil dari kawin silang %LANGKAH 1 : MENENTUKAN PARAMETER DAN MEMBANGKITKAN POPULASI AWAL Jarak=[0 0 0 0 0 0 0 0 0 0; % Matriks bersifat simetrik 2 0 0 0 0 0 0 0 0 0; 5 5 0 0 0 0 0 0 0 0; 1 3 2 0 0 0 0 0 0 0; 5 3 3 5 0 0 0 0 0 0; 4 4 2 5 4 0 0 0 0 0; 3 4 3 3 2 1 0 0 0 0; 5 2 5 2 2 2 4 0 0 0; 5 1 3 2 4 1 3 5 0 0; 2 2 5 2 2 3 4 4 1 0]; %Membuat Matriks Jarak menjadi simetrik Jarak=Simetrik(Jarak,10); Demand=[0 3 3 2 5 2 2 5 2 2]; %Demand(1)=demand untuk depot=0 Pc=0.6; Pm=0.1; Popu_Size=10; Panjang_Krom=9; Term=50;

34 %Populasi awal random permutasi 1-9 for i=1:Popu_Size Popu(i,:)=randperm(Panjang_Krom); end %LANGKAH 2 : MENGHITUNG FITNESS %Hitung Jarak,Total Pinalti,Fitness tiap kromosom di Populasi Awal Z = HitungJarak(Popu,Jarak,Panjang_Krom); Total_Pinalti = HitungPinalti(Popu,Demand); F=1./(Z + Total_Pinalti); %Menghitung Probabilitas P(i)dan Probabilitas Kumulatif Q(i) kromosom i P=F/sum(F); Q=cumsum(P); %LANGKAH 3 : BAGIAN UTAMA ALGORITME GENETIKA Iterasi=1; while Iterasi <= Term %Memilih 6 Parent dg Stochastic Universal Sampling(SUS) Parent = MemilihInduk(Popu,Popu_Size,Pc,Q); if (rand < Pc) %Lakukan kawin silang v=randperm(6); %mengacak pasangan kawin silang Child(1:2,:)=KawinSilang(Parent(v(1),:),Parent(v(2),:)); Child(3:4,:)=KawinSilang(Parent(v(3),:),Parent(v(4),:)); Child(5:6,:)=KawinSilang(Parent(v(5),:),Parent(v(6),:)); for i=1:6 if (rand < Pm) %Lakukan Mutasi mutasi_point=ceil(rand(1,2).*9); trans(i)=Child(i,mutasi_point(1)); Child(i,mutasi_point(1))= Child(i,mutasi_point(2)); Child(i,mutasi_point(2))=trans(i); end end %Gabungkan Kromosom Generasi sebelumnya dengan kromosom anak Popu=[Popu;Child]; %Ukuran Popu jadi (10+6) kromosom %Hitung TotalJarak,Pinalti,Fitness tiap kromosom Z = HitungJarak(Popu,Jarak,Panjang_Krom); Total_Pinalti = HitungPinalti(Popu,Demand); F=1./(Z + Total_Pinalti); %Nilai fitness %Lakukan Penggantian hanya jika Kawin Silang dilakukan t=16; while t>10 for i=1:t if(F(i)==min(F)) Popu(i,:)=[]; Z(i)=[];

35 Total_Pinalti(i)=[]; F(i)=[]; break; end end t=t-1; end end %Menghitung Peluang Kumulatif P=F/sum(F); Q=cumsum(P); %Plot(Iterasi,max_fitness, mean_fitness) hold on; plot(Iterasi,max(F),'-rs',Iterasi,mean(F),'-ko'); xlabel('Iterasi'); ylabel('Nilai fitness'); title('Grafik Fitness Setiap Generasi'); legend('Best Fitness','Mean Fitness'); hold off Iterasi=Iterasi+1; end %Akhir Iterasi disp('Populasi Akhir') disp (Popu) Z = HitungJarak(Popu,Jarak,Panjang_Krom) %Jarak Populasi Akhir Total_Pinalti = HitungPinalti(Popu,Demand)%Pinalti Populasi Akhir F=1./(Z + Total_Pinalti) %Fitness Populasi Akhir disp('Waktu Eksekusi') cputime disp('Algoritme Genetika Berakhir') %*************************TERIMA KASIH**********************

36 Fungsi-fungsi yang digunakan untuk implementasi VRP Fungsi Simetrik %Fungsi yang membuat matriks jadi simetrik %m=banyak kolom = banyak baris function Matriks=Simetrik(Matriks,m) for i=1:m for j=1:m if (j>i) %yang akan diubah bag.segitiga atasnya Matriks(i,j)=Matriks(j,i); end end end

Fungsi HitungJarak function Z = HitungJarak(Popu,Jarak,Panjang_Krom) for i=1:length(Popu) %Cat: length(Popu)=Ukuran Pop jika ukuran Populasi >= Panjang Kromosom Z(i)=0; for j=1:Panjang_Krom if ((0==mod(j,3))||(0==mod(j-1,3))) %tidak berlaku umum Z(i)=Z(i)+ Jarak(1,(Popu(i,j)+1)); else Z(i)=Z(i)+ Jarak((Popu(i,j-1)+1),(Popu(i,j)+1)) + Jarak((Popu(i,j)+1),(Popu(i,j+1)+1)); end end end

Fungsi HitungPinalti function Total_Pinalti = HitungPinalti(Popu,Demand) for i=1:length(Popu) %Cat: length(Popu)=Ukuran Pop jika ukuran Populasi >= Panjang Kromosom for k=1:3 if (k==1) load(i,k)=Demand(Popu(i,1)+1)+Demand(Popu(i,2)+1)+Demand(Pop u(i,3)+1); elseif (k==2) load(i,k)=Demand(Popu(i,4)+1)+Demand(Popu(i,5)+1)+Demand(Pop u(i,6)+1); else load(i,k)=Demand(Popu(i,7)+1)+Demand(Popu(i,8)+1)+Demand(Pop u(i,9)+1); end if (load(i,k)>10) Pinalti(i,k)=load(i,k)-10; else Pinalti(i,k)= 0; end end Total_Pinalti(i)=sum(Pinalti(i,:)); end

37 Fungsi MemilihInduk function Parent = MemilihInduk(Popu,Popu_Size,Pc,Q) t=floor(Popu_Size*Pc); Pointer(1)=0+((1/t)*rand); for i=2:t Pointer(i)=(i-1)*(1/t)+ Pointer(1); end for i=1:t for m=2:10 if ((Pointer(i)>=Q(m-1)) && (Pointer(i)
Fungsi KawinSilang function Child=KawinSilang(Parent1,Parent2) xover_point=[ceil(rand*(length(Parent1)-1)) ceil(rand*(length(Parent1)-1))]; a=min(xover_point); b=max(xover_point); %*********MENUKAR STRING ANTAR INDUK********** Child=zeros(2,length(Parent1)); %Nilai awal kromosom Child for i=a:b Child(1,i)=Parent1(i); Child(2,i)=Parent2(i); end %MENYUSUN ULANG KROMOSOM Parent DIMULAI DARI xover_point YANG KEDUA for i=1:length(Parent1) if (i>b) Reorder(1,(i-b))=Parent1(i); Reorder(2,(i-b))=Parent2(i); end if (i<=b) Reorder(1,(length(Parent1)-b+i))=Parent1(i); Reorder(2,(length(Parent1)-b+i))=Parent2(i); end end %***MEMBUAT SUSUNAN KROMOSOM YANG AKAN DISISIPKAN KE Child*** Inserted1=Reorder(1,:); %Inserted1 akan disisipkan ke Child(2) Inserted2=Reorder(2,:); %Inserted2 akan disisipkan ke Child(1) for m=1:length(Reorder) for n=a:b if (Reorder(2,m)==Parent1(n)) i=1; while i<=length(Inserted2)

38 if (Inserted2(i)==Reorder(2,m)) Inserted2(:,i)=[]; end i=i+1; end end if (Reorder(1,m)==Parent2(n)) j=1; while j<=length(Inserted1) if (Inserted1(j)==Reorder(1,m)) Inserted1(:,j)=[]; end j=j+1; end end end end %***********MEMASUKKAN Inserted KE Child****************** for i=b+1:length(Child) Child(1,i)=Inserted2(i-b); Child(2,i)=Inserted1(i-b); end for i=1:(a-1) Child(1,i)=Inserted2(length(Child)-b+i); Child(2,i)=Inserted1(length(Child)-b+i); end

Hasil keluaran MATLAB R2008b untuk implementasi VRP Populasi Akhir 6 2 6 2 9 8 6 2 6 2 6 2 6 2 6 2 9 8 9 8 Z = 29

29

29

4 4 1 4 4 4 4 4 1 1 29

Total_Pinalti = 0 0 0 0

9 9 6 9 9 9 9 9 6 6

8 8 2 8 8 8 8 8 2 2

1 1 4 1 1 1 1 1 4 4

3 3 3 3 3 3 3 3 3 3

7 7 7 7 7 7 7 7 7 7

29

29

29

29

29

29

0

0

0

0

0

0

F = 0.0345 0.0345 0.0345 0.0345 0.0345 0.0345 0.0345 0.0345 0.0345

5 5 5 5 5 5 5 5 5 5

0.0345

39 Waktu Eksekusi ans = 31.6838 Algoritme Genetika Berakhir

Lampiran 4 Sintaks dan hasil software LINGO 11.0 Sintaks software LINGO 11.0 untuk implementasi VRP model: sets: kendaraan/1..3/; node/1..10/:d; !node 1= depot !d(i) = demand di node i; !U=dummy variabel yang akan digunakan untuk eliminasi subtour; jarak(node,node):c ; !c(i,j) =jarak node i ke node j; dummy(node,kendaraan):U; rute(node,node,kendaraan):x; !x(i,j,k)=variabel keputusan jika kendaraan k digunakan untuk melayani node j setelah node i; endsets DATA: c= 0 2 5 1 5 4 3 5 5 2 2 0 5 3 3 4 4 2 1 2 5 5 0 2 3 2 3 5 3 5 1 3 2 0 5 5 3 2 2 2 5 3 3 5 0 4 2 2 4 2 4 4 2 5 4 0 1 2 1 3 3 4 3 3 2 1 0 4 3 4 5 2 5 2 2 2 4 0 5 4 5 1 3 2 4 1 3 5 0 1 2 2 5 2 2 3 4 4 1 0 ; d= 0 3 3 2 5 2 2 5 2 2 ; ENDDATA W=10; !Kapasitas kendaraan; N=@size(node); !FUNGSI OBJEKTIF; min = @sum(kendaraan(k):@sum(node(i):@sum(node(j):c(i,j)*x(i,j,k)) ));

40 !KENDALA KENDALA; !setiap pelanggan hanya dilayani sekali oleh satu kendaraan; @for(node(j)|j#GT#1:@sum(kendaraan(k):@sum(node(i)|i#NE#j:x( i,j,k)))=1); !setiap kendaraan harus berangkat dari depot; @for(kendaraan(k):@sum(node(j):x(1,j,k))=1); !kendaraan yang digunakan harus kembali ke depot; @for(kendaraan(k):@sum(node(i):x(i,1,k))=1); !kekontinuan rute, setiap kendaraan yang mengunjungi suatu pelanggan harus meninggalkan pelanggan tsb; @for(kendaraan(k):@for(node(p):@sum(node(i)|p#NE#i:x(i,p,k)) -@sum(node(j)|p#NE#j:x(p,j,k))=0)); !Setiap kendaraan tidak boleh melayani melebihi kapasitas W; @for(kendaraan(k):@sum(node(i):@sum(node(j)|i#NE#j:d(i)*x(i, j,k)))<= W); !eliminasi subtour; @for(kendaraan(k):@for(node(i)|(i#GT#1):@for(node(j)|(j#GT#1 )#AND#(j#NE#i):U(i,k)-U(j,k)+(N*x(i,j,k))<=N-1))); !Setiap kendaraan tidak boleh mengunjungi kembali pelanggan yang sama; @for(kendaraan(k):@for(node(i):x(i,i,k)=0)); !x(i,j,k) adalah biner; @for(node(i):@for(node(j):@for(kendaraan(k):@bin(x(i,j,k)))) );

41 Hasil software LINGO 11.0 untuk implementasi VRP.

Global optimal solution found. Objective value: Objective bound: Infeasibilities: Extended solver steps: Total solver iterations: Variable W N D( 2) D( 3) D( 4) D( 5) D( 6) D( 7) D( 8) D( 9) D( 10) C( 1, 2) C( 1, 3) C( 1, 4)

Value 10.00000 10.00000 3.000000 3.000000 2.000000 5.000000 2.000000 2.000000 5.000000 2.000000 2.000000 2.000000 5.000000 1.000000

27.00000 27.00000 0.000000 5178 111173 Variable C( 1, 5) C( 1, 6) C( 1, 7) C( 1, 8) C( 1, 9) C( 1, 10) C( 2, 1) C( 2, 3) C( 2, 4) C( 2, 5) C( 2, 6) C( 2, 7) C( 2, 8) C( 2, 9)

Value 5.000000 4.000000 3.000000 5.000000 5.000000 2.000000 2.000000 5.000000 3.000000 3.000000 4.000000 4.000000 2.000000 1.000000

42

Variable C( 2, 10) C( 3, 1) C( 3, 2) C( 3, 4) C( 3, 5) C( 3, 6) C( 3, 7) C( 3, 8) C( 3, 9) C( 3, 10) C( 4, 1) C( 4, 2) C( 4, 3) C( 4, 5) C( 4, 6) C( 4, 7) C( 4, 8) C( 4, 9) C( 4, 10) C( 5, 1) C( 5, 2) C( 5, 3) C( 5, 4) C( 5, 6) C( 5, 7) C( 5, 8) C( 5, 9) C( 5, 10) C( 6, 1) C( 6, 2) C( 6, 3) C( 6, 4) C( 6, 5) C( 6, 7) C( 6, 8) C( 6, 9) C( 6, 10) C( 7, 1) C( 7, 2) C( 7, 3) C( 7, 4) C( 7, 5) C( 7, 6) C( 7, 8) C( 7, 9) C( 7, 10) C( 8, 1)

Value 2.000000 5.000000 5.000000 2.000000 3.000000 2.000000 3.000000 5.000000 3.000000 5.000000 1.000000 3.000000 2.000000 5.000000 5.000000 3.000000 2.000000 2.000000 2.000000 5.000000 3.000000 3.000000 5.000000 4.000000 2.000000 2.000000 4.000000 2.000000 4.000000 4.000000 2.000000 5.000000 4.000000 1.000000 2.000000 1.000000 3.000000 3.000000 4.000000 3.000000 3.000000 2.000000 1.000000 4.000000 3.000000 4.000000 5.000000

Variable C( 8, 2) C( 8, 3) C( 8, 4) C( 8, 5) C( 8, 6) C( 8, 7) C( 8, 9) C( 8, 10) C( 9, 1) C( 9, 2) C( 9, 3) C( 9, 4) C( 9, 5) C( 9, 6) C( 9, 7) C( 9, 8) C( 9, 10) C( 10, 1) C( 10, 2) C( 10, 3) C( 10, 4) C( 10, 5) C( 10, 6) C( 10, 7) C( 10, 8) C( 10, 9) U( 2, 1) U( 2, 2) U( 3, 1) U( 3, 2) U( 4, 1) U( 4, 3) U( 5, 3) U( 6, 1) U( 9, 2) X( 1, 7, 1) X( 1, 8, 3) X( 1, 10, 2) X( 2, 1, 2) X( 3, 4, 1) X( 4, 1, 1) X( 5, 1, 3) X( 6, 3, 1) X( 7, 6, 1) X( 8, 5, 3) X( 9, 2, 2) X( 10, 9, 2)

Value 2.000000 5.000000 2.000000 2.000000 2.000000 4.000000 5.000000 4.000000 5.000000 1.000000 3.000000 2.000000 4.000000 1.000000 3.000000 5.000000 1.000000 2.000000 2.000000 5.000000 2.000000 2.000000 3.000000 4.000000 4.000000 1.000000 9.000000 9.000000 2.000000 9.000000 9.000000 9.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000

43

RIWAYAT HIDUP Penulis dilahirkan di Kotabumi pada tanggal 9 Oktober 1991 sebagai anak kedua dari dua bersaudara, dari ayah Seman (alm) dan ibu Poniyem. Tahun 2011 penulis lulus dari SMAN 5 Bandar Lampung dan pada tahun yang sama penulis lulus seleksi masuk IPB melalui jalur Undangan Seleksi Masuk IPB (USMI). Penulis diterima di Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam. Selama masa kuliah di IPB, penulis aktif dalam beberapa organisasi intra kampus. Penulis aktif sebagai staf fundrising LDK Al Hurriyyah 2011/2013, staf PSDM Kopma IPB 2012, Ketua Divisi Sosial dan Lingkungan Gugus Mahasiswa Matematika IPB 2013/2014, dan Ketua Himpunan Rohis Matematika IPB 2013/2014. Penulis juga pernah aktif dalam beberapa kepanitian, di antaranya sebagai staf Divisi Medis Masa Perkenalan Kampus Mahasiswa Baru (MPKMB) 2012, koordinator acara Gebyar Kopma IPB 2012, penanggung jawab kelompok Masa Perkenalan Fakultas dan Departemen 2013 dan 2014, koordinator bagian Lampung Utara acara Back to Village (BTV) 2013, ketua Divisi Konsumsi Musyawarah Tahunan Ikatan Himpunan Mahasiswa Matematika Indonesia 2013, ketua Divisi Konsumsi IPB Mathematics Challenge 2014, ketua pelaksana Baksos Mahasiswa Matematika IPB 2014, dan penanggung jawab Matematika Go Field 2014. Selain itu, penulis juga aktif mengajar mata kuliah matematika TPB di lembaga bimbingan belajar Katalis Corp.

PENYELESAIAN VEHICLE ROUTING PROBLEM MENGGUNAKAN ALGORITME GENETIKA DEDI HARIYANTO

Recommend Documents