IMPLEMENTASI ALGORITMA PARALEL GENETIC ALGORITHM UNTUK PENYELESAIAN HETEROGENEOUS FLEET VEHICLE ROUTING PROBLEM

TUGAS AKHIR – CI 1599

IMPLEMENTASI ALGORITMA PARALEL GENETIC ALGORITHM UNTUK PENYELESAIAN HETEROGENEOUS FLEET VEHICLE ROUTING PROBLEM BAMBANG EKO HENDRAWAN NRP 5103 100 024 Dosen Pembimbing Ir. F.X. Arunanto, M.Sc. JURUSAN TEKNIK INFORMATIKA Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember Surabaya 2007

iii

FINAL PROJECT – CI 1599

IMPLEMENTATION OF PARALLEL GENETIC ALGORITHM TO SOLVE HETEROGENEOUS FLEET VEHICLE ROUTING PROBLEM BAMBANG EKO HENDRAWAN NRP 5103 100 024 Advisor Ir. F.X. Arunanto, M.Sc.

DEPARTMENT OF INFORMATICS Faculty of Information Technology Institute of Technology Sepuluh Nopember Surabaya 2007

iv

TUGAS AKHIR – CI 1599

IMPLEMENTASI ALGORITMA PARALEL GENETIC ALGORITHM UNTUK PENYELESAIAN HETEROGENEOUS FLEET VEHICLE ROUTING PROBLEM BAMBANG EKO HENDRAWAN NRP 5103 100 024 Dosen Pembimbing Ir. F.X. Arunanto, M.Sc. JURUSAN TEKNIK INFORMATIKA Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember Surabaya 2007

v

IMPLEMENTASI ALGORITMA PARALEL GENETIC ALGORITHM UNTUK PENYELESAIAN HETEROGENEOUS FLEET VEHICLE ROUTING PROBLEM

TUGAS AKHIR Diajukan Guna Memenuhi Sebagian Persyaratan Untuk Memperoleh Gelar Sarjana Komputer pada Jurusan Teknik Informatika Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember Oleh : BAMBANG EKO HENDRAWAN NRP : 5103 100 024 Disetujui oleh Dosen Pembimbing Tugas Akhir :

Ir. F.X. Arunanto, M.Sc. NIP: 131.285.253

................................ (pembimbing 1)

SURABAYA JANUARI 2008

vi

[Halaman ini sengaja dikosongkan]

vii

IMPLEMENTASI ALGORITMA PARALEL GENETIC ALGORITHM UNTUK PENYELESAIAN HETEROGENEOUS FLEET VEHICLE ROUTING PROBLEM Nama Mahasiswa NRP Jurusan Dosen Pembimbing

: Bambang Eko Hendrawan : 5103 100 024 : Teknik Informatika FTIf-ITS : Ir. F.X. Arunanto, M.Sc.

Abstrak Vehicle Routing Problem (VRP) adalah sebuah permasalahan optimasi kombinatorial yang kompleks. VRP bertujuan untuk meminimalkan biaya yang diperluka, dimana penentuan biaya erat kaitannya dengan jarak yang ditempuh. Permasalahan VRP klasik menganggap kapasitas tiap kendaraan yang digunakan sama semua. Pada kenyataannya, sebuah perusahaan tidak selalu mempunyai komposisi kendaraan yang sama, sehingga VRP klasik kurang mengena untuk diterapkan. Karena itu muncul varian VRP untuk menyelesaikan permasalahan VRP dengan komposisi kendaraan yang berbedabeda, yang dikenal dengan Heterogeneous Fleet VRP. Lingkup VRP pada praktiknya biasanya sangatlah luas, sehingga metode eksak tidak dapat digunakan untuk menyelesaikannya. Penelitian akhirnya lebih ditekankan pada metaheuristic, dan beberapa eksperimen telah membuktikan kehebatan Genetic Algorithm untuk menyelesaikan VRP. Semakin banyak generasi, keberhasilan GA semakin baik. Namun kebutuhan komputasional menjadi lebih tinggi, sehingga muncul ide untuk menggunakan teknik komputasi paralel. Aplikasi yang dibuat dalam laporan ini mampu memenuhi kebutuhan untuk menyelesaikan permasalahan heterogeneous VRP menggunakan GA secara paralel. Kata kunci : Heterogeneous Fleet VRP, Genetic Algorithm, Island Model, MPI viii

[Halaman ini sengaja dikosongkan]

ix

IMPLEMENTATION OF PARALLEL GENETIC ALGORITHM TO SOLVE HETEROGENEOUS FLEET VEHICLE ROUTING PROBLEM Name NRP Department Lecturers

: Bambang Eko Hendrawan : 5103 100 024 : Teknik Informatika FTIf-ITS : Ir. F.X. Arunanto, M.Sc.

Abstract Vehicle Routing Problem (VRP) is one of the complex combinatorial optimation problem. The main point of VRP is to search the minimal cost needed, which is corelated with distance traveled. Classic VRP assume that every vehicle in the problem has the same capacity. In reality, a company doesn't always have same vehicles in it's fleet, which makes classic VRP not fit to apply. Considering the previous condition, researcher created another variant to the VRP problem called heterogeneous fleet VRP, where every vehicle c an have it's own capacity. Daily use of VRP is usually very large, that there is no exact method can solve the problem. Later research is then concentrated to metaheuristic algorithm and found out that Genetic Algorithm has a good ability in solving VRP. Genetic Algorithm relies in it’s parameter to make good results, mainly in the generation number used. Sadly, increasing GA’s parameter requries more computational cost. Researcher then came into idea to paralelize Genetic Algorithm to get better result using lower computational cost. The implemented VRP solver in this report is able to solve heterogeneous VRP using paralel Genetic Algorithm. . Keywords : Heterogeneous Fleet VRP, Genetic Algorithm, Island Model, MPI x

[Halaman ini sengaja dikosongkan]

xi

KATA PENGANTAR Puji syukur penulis panjatkan kepada Allah SWT. Karena limpahan rahmat dan karunia-Nya lah penulis dapat menyelesaikan Tugas Akhir yang berjudul : IMPLEMENTASI ALGORITMA PARALEL GENETIC ALGORITHM UNTUK PENYELESAIAN HETEROGENEOUS FLEET VEHICLE ROUTING PROBLEM Tidak lupa penulis sampaikan ucapan terima kasih kepada pihak-pihak yang telah membantu penyelesaian Tugas Akhir ini : - Bapak Ir. F.X. Arunanto, M.Sc. atas bimbingannya selama pengerjaan Tugas Akhir. - Ayah, Pak Dodhi, Mama, Adik, serta Kakek dan Nenek tercinta atas semua dukungan dan doa yang dipanjatkan. - dr Frida Kurnia Pratama yang telah memberikan dukungan penuh atas terselesaikannya Tugas Akhir ini, serta bapak Chumaidi (alm) sekeluarga atas semua dukungannya. - Teman-teman seperjuangan TA: Syaiful, Rino, dan Fajar N. - Helmi, Henry, Tri Wahyu, Dwi, Afis, Munif, Praja, Wachid, Hudha, Adam, Novia, Mas Gayuh, dan seluruh keluarga besar Laboratorium Pemrograman Informatika ITS. - Dimas, Chika, Zul, Silas, Prasta, Yulianus, dan seluruh keluarga besar GCL yang telah meberikan bantuan teknis serta fasilitas dan lingkungan yang kondusif. - Teman-teman 2003 serta semua pihak yang telah membantu penulis menyelesaikan Tugas Akhir ini dan selama menjalani perkuliahan di Teknik Informatika ITS. Penulis berharap semoga tugas akhir memberikan manfaat bagi yang membacanya.

ini

dapat

Surabaya, Januari 2008 Penulis xii

[Halaman ini sengaja dikosongkan]

xiii

DAFTAR ISI Abstrak ...................................................................................... viii  Abstract ......................................................................................... x  KATA PENGANTAR .................................................................xii  DAFTAR ISI .............................................................................. xiv  DAFTAR GAMBAR ................................................................. xvi  DAFTAR TABEL ................................................................... xviii  BAB 1 PENDAHULUAN............................................................. 1  1.1  Latar Belakang.................................................................. 1  1.2  Rumusan Permasalahan .................................................... 3  1.3  Batasan Masalah ............................................................... 3  1.4  Tujuan dan Manfaat .......................................................... 4  1.5  Metodologi ....................................................................... 4  1.6  Sistematika Penulisan ....................................................... 5  BAB 2 TINJAUAN PUSTAKA .................................................... 7  2.1  Vehicle Routing Problem ................................................. 7  2.1.1  Permasalahan ............................................................ 7  2.1.2  Model Matematis Heterogeneous VRP .................... 8  2.1.3  Aplikasi VRP Pada Kehidupan Nyata .................... 10  2.1.4  Metode penyelesaian VRP ...................................... 10  2.2  Genetic Algorithm .......................................................... 12  2.2.1  Latar belakang Genetic Algorithm.......................... 12  2.2.2  Fitness Value........................................................... 16  2.2.3  Selection.................................................................. 17  2.2.4  Crossover ................................................................ 18  2.2.5  Mutation .................................................................. 19  2.3  Genetic Algorithm Dalam Lingungan Paralel ................ 20  2.4  Message Passing Interface .............................................. 23  2.4.1  Terminologi Dasar Pemrograman Paralel ............... 24  2.4.2  Fungsi-fungsi dasar MPI ......................................... 25  BAB 3 PERANCANGAN PERANGKAT LUNAK................... 27  3.1  Deskripsi Umum Perangkat Lunak................................. 27  3.2  Rancangan Aplikasi Secara Umum ................................ 27  xiv

3.3  Pemodelan Chromosome ................................................ 29  3.4  Perancangan Operator-Operator Genetic Algorithm ...... 30  3.5  Perancangan Class .......................................................... 38  3.6  Perancangan Aliran Data ................................................ 41  3.7  Perancangan Konsep Paralel Genetic Algorithm............ 44  3.8  Perancangan Format File Input....................................... 46  3.8.1  File Input Parameter Permasalahan VRP ................ 46  3.8.2  File Input Parameter Genetic Algorithm ................. 49  BAB 4 IMPLEMENTASI PERANGKAT LUNAK ................... 51  4.1  Lingkungan Pembangunan Perangkat Lunak ................. 51  4.2  Implementasi Proses ....................................................... 51  4.2.1  Implementasi Proses Membaca Data Input VRP .... 52  4.2.2  Implementasi Proses Inisialisasi MPI .................... 59  4.2.3  Implementasi Proses Initial Population Generation 59  4.2.4  Implementasi Proses Iterasi Genetic Algorithm ..... 66  4.2.5  Implementasi Proses Selection ............................... 68  4.2.6  Implementasi Proses CrossOver ............................. 69  4.2.7  Implementasi Proses Mutation ................................ 72  4.2.8  Implementasi Proses Inversion ............................... 73  4.2.9  Implementasi Proses Migration .............................. 75  BAB 5 UJI COBA DAN EVALUASI ........................................ 81  5.1  Lingkungan Uji Coba ..................................................... 81  5.2  Uji Coba Parameter GA .................................................. 82  5.3  Uji Coba Performa .......................................................... 84  5.3.1  Skenario 1 ............................................................... 84  5.3.2  Skenario 2 ............................................................... 87  5.3.3  Skenario 3 ............................................................... 89  BAB 6 PENUTUP ....................................................................... 93  6.1  KESIMPULAN .............................................................. 93  6.2  SARAN........................................................................... 93  DAFTAR PUSTAKA.................................................................. 95  BIODATA PENULIS .................................................................. 97 

xv

DAFTAR GAMBAR Gambar 2.1 Solusi dari sebuah VRP ............................................ 8  Gambar 2.2 Contoh metode Roulette Wheel .............................. 18  Gambar 2.3 Ilustrasi proses crossover ........................................ 19  Gambar 2.4 Ilustrasi proses mutation ......................................... 20  Gambar 2.5 Model populasi Panmictic Genetic Algorithm (normal) dan Cellular Genetic Algorithm ................................... 21  Gambar 2.6 Ilustrasi proses mutation ......................................... 22  Gambar 3.1 Arsitektur Sistem VRP Solver ................................ 28  Gambar 3.2 Pengkodean chromosome untuk VRP .................... 30  Gambar 3.3 Flowchart Proses Roulette Wheel Selection ........... 32  Gambar 3.4 Flowchart proses Simple Random CrossOver ........ 33  Gambar 3.5 Flowchart proses Random Swap Mutation ............. 35  Gambar 3.6 Flowchart proses Repair Operator .......................... 37  Gambar 3.7 Desain Class Diagram ............................................ 40  Gambar 3.8 Desain DFD level 0 ................................................ 41  Gambar 3.9 Desain DFD level 1 ................................................ 42  Gambar 3.10 Desain DFD level 0 .............................................. 43  Gambar 3.11 Desain Paralel Genetic Algotrithm menggunakan Island Model ................................................................................ 45  Gambar 5.1 Grafik Hasil Uji Coba Skenario 1 : Pengujian kualitas solusi dengan migrasi setiap 10 iterasi ........................... 86  Gambar 5.2Grafik Hasil Uji Coba Skenario 1 : Pengujian waktu eksekusi dengan migrasi setiap 10 iterasi .................................... 86  Gambar 5.3 Grafik Hasil Uji Coba Skenario 2 : Pengujian kualitas solusi dengan migrasi setiap 50 iterasi ........................... 88  Gambar 5.4 Grafik Hasil Uji Coba Skenario 2 : Pengujian waktu eksekusi dengan migrasi setiap 50 iterasi .................................... 88  Gambar 5.5 Grafik Hasil Uji Coba Skenario 3 : Pengujian kualitas solusi dengan migrasi setiap 100 iterasi ......................... 91  Gambar 5.6 Grafik Hasil Uji Coba Skenario 3 : Pengujian waktu eksekusi dengan migrasi setiap 100 iterasi .................................. 91  xvi

[Halaman ini sengaja dikosongkan]

xvii

DAFTAR TABEL Tabel 2.1 Daftar istilah pada GA beserta penjelasan.................. 13  Tabel 2.2 Daftar fungsi-fungsi utama pada MPI ........................ 25  Tabel 3.1 Daftar kata kunci file input VRP ................................ 47  Tabel 3.2 Daftar fungsi-fungsi utama pada MPI ........................ 49  Tabel 5.1 Hasil Uji Coba Parameter GA : Jumlah Iterasi .......... 83  Tabel 5.2 Hasil Uji Coba Parameter GA : Ukuran Populasi ...... 84  Tabel 5.3 Hasil Uji Coba Performa Skenario 1 : Pengujian kualitas solusi dengan migrasi setiap 10 iterasi ........................... 85  Tabel 5.4 Hasil Uji Coba Performa Skenario 1 : Pengujian waktu eksekusi dengan migrasi setiap 10 iterasi .................................... 85  Tabel 5.5 Hasil Uji Coba Performa Skenario 2 : Pengujian kualitas solusi dengan migrasi setiap 50 iterasi ........................... 87  Tabel 5.6 Hasil Uji Coba Performa Skenario 2 : Pengujian waktu eksekusi dengan migrasi setiap 50 iterasi .................................... 87  Tabel 5.7 Hasil Uji Coba Performa Skenario 3: Pengujian kualitas solusi dengan migrasi setiap 100 iterasi ......................... 90  Tabel 5.8 Hasil Uji Coba Performa Skenario 3 : Pengujian waktu eksekusi dengan migrasi setiap 100 iterasi .................................. 90 

xviii

[Halaman ini sengaja dikosongkan]

xix

BAB 1 PENDAHULUAN

Pada bab ini akan dibahas mengenai garis besar tugas akhir, yang meliputi Latar Belakang Masalah, Tujuan dan Manfaat Pembuatan, Permasalahan, Batasan Masalah, Metodologi Pembuatan Tugas Akhir, dan Sistematika Penulisan. 1.1

Latar Belakang

Permasalahan Vehicle Routing Problem (VRP) adalah sebuah permasalahan optimasi kombinatorial yang kompleks, yang didefinisikan sebagai berikut: Pencarian cara penggunaan yang efisien dari sejumlah vehicle (kendaraan) yang harus melakukan perjalanan untuk mengunjungi sejumlah tempat untuk mengantar dan/atau menjemput orang/barang [2]. Setiap tujuan hanya boleh dilayani oleh satu vehicle saja. Hal ini dilakukan dengan mempertimbangkan kapasitas vehicle dalam satu kali angkut, untuk meminimalkan biaya yang diperlukan. Biasanya, penentuan biaya minimal erat kaitannya dengan jarak yang minimal. Permasalahan VRP klasik menganggap kapasitas tiap vehicle yang digunakan sama semua. Pada kenyataannya, sebuah perusahaan tidak selalu mempunyai komposisi vehicle yang sama, sehingga metode penyelesaian VRP klasik kurang mengena untuk diterapkan. Karena itu muncul varian metode VRP klasik untuk menyelesaikan permasalahan VRP dengan komposisi vehicle yang berbeda, yang dikenal dengan Heterogeneous Fleet VRP. Lingkup permasalahan VRP pada praktiknya biasanya sangatlah luas (dalam hal banyaknya jumlah pelanggan), sehingga metode eksak tidak dapat digunakan untuk menyelesaikannya. Penekanan penyelesaian permasalahan optimasi tersebut akhirnya lebih ditekankan pada metaheuristic. Beberapa eksperimen telah membuktikan kehebatan Genetic Algorithm untuk menyelesaikan 1

2 VRP, yang membuatnya menjadi kandidat kuat untuk menjadi salah satu alternatif solusi yang ampuh untuk mencari optimasi VRP, sehingga semakin banyak orang mencoba meneliti metode ini. Genetic Altorithm (GA) diperkenalkan oleh John Holland dan para peneliti dari University of Michigan pada tahun 1970an [4], yang kemudian mulai digunakan secara luas ke berbegai bidang, termasuk untuk memecahkan permasalahan-permasalahan optimasi. Ide dasar dari GA adalah memodelkan seleksi alam menggunakan penurunan warisan genetika berdasarkan teori Darwin [5]. Proses utama dalam algoritma GA adalah memodelkan proses berkembang biak (crossover) untuk menghasilkan keturunan (offspring) dan mutasi genetik (mutation). Setelah melalui proses-proses tersebut, maka proses selanjutnya adalah seleksi alam (natural selection), dimana anggota-anggota populasi yang sifatnya jelek akan tersingkir dari populasi. Karena sifatnya yang blind, maka GA banyak bergantung kepada parameter-parameter inputan untuk menyelesaikan tugasnya. Semakin banyak generasi yang terjadi, keberhasilan GA untuk mendapatkan solusi optimum cenderung semakin tinggi. Namun untuk memproses generasi yang lebih banyak, kebutuhan komputasional yang diperlukan pun kemudian menjadi lebih tinggi, dan karena kemampuan komputasional terbatas, waktu yang dibutuhkan pun akan semakin lama, sehingga muncul ide untuk menggunakan teknik komputasi paralel. Beberapa teknik yang berbeda telah muncul untuk memparalelkan GA. Beberapa metode yang umum digunakan untuk memparalelkan GA adalah model island, fine grain, dan panmictic. Hal-hal di atas melatarbelakangi penulis untuk membuat aplikasi pencari rute optimal untuk VRP yang sifatnya heterogeneous, menggunakan Genetic Algorithm, dalam lingkungan komputasi paralel.

3 1.2

Rumusan Permasalahan Dari latar belakang yang telah dijelaskan diatas, dapat dirumuskan detail permasalahan sebagai berikut: 1. Bagaimana memodelkan permasalahan Heterogeneous Fleet VRP ke dalam Genetic Algorithm. 2. Bagaimana mengaplikasikan Genetic Algorithm untuk mencari nilai optimum dari suatu permasalahan Heterogeneous Fleet VRP. 3. Bagaimana merancang dan membuat perangkat lunak untuk menyelesaikan permasalahan Heterogeneous Fleet VRP menggunakan Genetic Algorithm. 4. Bagaimana memodifikasi aplikasi sehingga dapat berjalan secara paralel. 5. Bagaimana menganalisa perubahan kecepatan dalam waktu eksekusi antara eksekusi sekuensial dan eksekusi paralel. 1.3

Batasan Masalah Batasan dalam Tugas Akhir ini adalah sebagai berikut:

1. Pembuatan tugas akhir ini dibuat untuk Heterogeneous Fleet VRP dengan ketentuan: • • •

Jumlah vehicle (kendaraan) diinputkan oleh user, dimana tiap vehicle dapat mempunyai kapasitas yang berbedabeda Jumlah pelanggan diinputkan oleh user, dimana tiap pelanggan mempunyai variabel lokasi (x,y) dan permintaan (demand). Jumlah depot hanya ada satu.

2. Pemrosesan paralel dari Heterogeneous Fleet VRP dengan Genetic Algorithm ini dilakukan dengan sistem paralel menggunakan library MPI.

4 3. Sistem paralel yang dimaksudkan dalam tugas ini adalah sistem yang terdiri dari perangkat keras dan perangkat lunak yang memungkinkan terselenggaranya proses paralel. Karena sistem tersebut menggunakan library yang sudah ada (MPI), maka proses kerja aplikasi sehingga dapat menjalankan proses secara paralel dan sistem komunikasi serta pengiriman data secara paralel tidak akan dibahas dalam tugas akhir ini. 1.4

Tujuan dan Manfaat

Tujuan dari pembuatan Tugas Akhir ini adalah untuk merancang dan membuat suatu aplikasi yang dapat memecahkan permasalahan Heterogeneous Fleet VRP menggunakan Genetic Algorithm dalam lingkungan komputasi paralel. Adapun manfaat dari pembuatan tugas akhir ini adalah sebagai dasar dari pengembangan aplikasi-aplikasi lainnya yang menggunakan GA dalam lingkungan komputasi paralel menggunakan library MPI 1.5

Metodologi

Langkah-langkah yang ditempuh dalam pengerjaan Tugas Akhir ini adalah: 1.

Pemahaman Sistem dan Studi Literatur Tahap ini merupakan tahapan persiapan yang meliputi pengumpulan informasi yang diperlukan, dengan melakukan studi literatur mengenai permasalahan Vehicle Routing Problem (VRP), tipe lain permasalahan VRP yang menggunakan komposisi vehicle yang berbeda (heterogeneous fleet VRP), Genetic Algorithm (GA) dan penyelesaian permasalahan VRP menggunakan GA. Selain itu juga dilakukan penelitian mengenai cara mengimplementasikan GA dalam lingkungan komputasi paralel, dan library komputasi paralel yang digunakan, yaitu Message Passing Interface (MPI).

5 2.

Perancangan Aplikasi Tahap ini meliputi analisis dan desain sistem yang akan dibangun dengan mengacu pada hasil pemahaman sistem, studi literatur, penelitian, dan data yang telah diperoleh sebelumnya. Pada tahap perancangan aplikasi, desain model data, desain manajemen data, desain proses, dan desain antarmuka aplikasi didefinisikan.

3.

Implementasi Sistem Tahap implementasi sistem adalah tahap pembuatan perangkat lunak berdasar pada tahap perancangan sistem dengan algoritma dan bahasa pemrograman yang dipilih.

4.

Uji Coba dan Evaluasi Pada tahap uji coba dan evaluasi dilakukan pengujian terhadap perangkat lunak dengan data yang telah dipersiapkan sebelumnya. Uji coba dan evaluasi perangkat lunak dilakukan untuk mencari masalah yang mungkin timbul, mengevaluasi jalannya program, dan melakukan perbaikan jika terdapat kekurangan.

5.

Penyusunan Buku Tugas Akhir Tahap akhir dari proses pembuatan tugas akhir ini adalah penyusunan laporan atau dokumentasi secara lengkap dan menyeluruh dari semua kegiatan yang telah dilakukan. Pada tahap ini pula dirumuskan kesimpulan dan saran untuk pengembangan lebih lanjut.

1.6

Sistematika Penulisan

Buku tugas akhir ini terdiri dari beberapa bab, yang dijelaskan sebagai berikut: BAB I. PENDAHULUAN Bab ini berisi latar belakang masalah, tujuan dan manfaat pembuatan tugas akhir, permasalahan, batasan

6 masalah, metodologi yang digunakan, dan sistematika penyusunan tugas akhir. BAB II. TINJAUAN PUSTAKA Bab ini membahas beberapa teori penunjang yang berhubungan dengan pokok pembahasan dan mendasari pembuatan tugas akhir ini. BAB III. PERANCANGAN PERANGKAT LUNAK Bab ini membahas desain dari sistem yang akan dibuat meliputi : desain database, arsitektur, proses dan antarmuka perangkat lunak. BAB IV. IMPLEMENTASI PERANGKAT LUNAK Bab ini membahas implementasi dari desain sistem yang dilakukan pada tahap desain, disertai dengan potongan source code yang penting dalam aplikasi. BAB V. UJI COBA DAN EVALUASI Bab ini membahas uji coba dari aplikasi yang dibuat dengan melihat output yang dihasilkan oleh aplikasi, dan evaluasi untuk mengetahui kemampuan aplikasi. BAB VI. PENUTUP Bab ini berisi kesimpulan dari hasil uji coba yang dilakukan serta saran untuk pengembangan aplikasi selanjutnya.

BAB 2 TINJAUAN PUSTAKA

Pada bab ini akan dibahas mengenai tinjauan pustaka yang menjadi dasar dari pembuatan Tugas Akhir. Pokok-pokok permasalahan yang dibahas diantaranya mengenai Vehicle Routing Problem (VRP), termasuk tentang Heterogeneous Fleet VRP, serta Genetic Algorithm (GA) dan aplikasi GA dalam lingkungan komputasi paralel. 2.1

Vehicle Routing Problem

2.1.1

Permasalahan

Vehicle Routing Problem (VRP) diperkenalkan pertama kali oleh Dantziq dan Ramser pada tahun 1959 [1] dan semenjak itu telah dipelajari secara luas. Oleh Fisher [2], VRP didefinisikan sebagai berikut sebuah pencarian atas cara penggunaan yang efisien dari sejumlah vehicle yang harus melakukan perjalanan untuk mengunjungi sejumlah tempat untuk mengantar dan/atau menjemput orang/barang. Istilah customer digunakan untuk menunjukkan pemberhentian untuk mengantar dan/atau menjemput orang/barang. Setiap customer harus dilayani oleh satu vehicle saja. Penentuan pasangan vehicle-customer ini dilakukan dengan mempertimbangkan kapasitas vehicle dalam satu kali angkut, untuk meminimalkan biaya yang diperlukan. Biasanya, penentuan biaya minimal erat kaitannya dengan jarak yang minimal. VRP juga dapat dilihat sebagai kombinasi dari dua permasalahan optimasi lain, yaitu Bin Packing Problem (BPP) dan Travelling Salesman Problem (TSP). BPP dapat dideskripsikan sebagai berikut: “Diberikan sejumlah angka, yang melambangkan ukuran dari sejumlah item, dan sebuah konstanta 7

8 K, yang melambangkan kapasitas dari bin. Berapa jumlah bin minimum yang diperlukan?” [3] Tentu saja satu item hanya dapat berada dalam satu bin saja, dan total kapasitas item pada setiap bin tidak boleh melebihi kapasitas dari bin tersebut. Disamping itu, TSP adalah sebuah permasalahan tentang seorang salesman yang ingin mengunjungi sejumlah kota. Dia harus mengunjungi tiap kota sekali saja, dimulai dan diakhiri dari kota awal. Inti permasalahan adalah untuk menemukan jalur terpendek melalui semua kota yang ada. Hubungan keduanya dengan VRP adalah, vehicle dapat dihubungkan dengan customer menggunakan BPP, dan urutan kunjungan vehicle terhadap tiap customer diselesaikan menggunakan TSP. Gambar 2.1 menunjukkan solusi dari sebuah permasalahan VRP dalam bentuk graph. Pada gambar, node 0 melambangkan depot (kota asal), dan node 1-10 melambangkan customer.

Gambar 2.1 Solusi dari sebuah VRP

2.1.2

Model Matematis Heterogeneous VRP

Kebanyakan pemodelan integer programming pada permasalahan VRP klasik (Capacitated VRP) menggunakan variabel biner sebagai variabel yang melambangkan rute vehicle, untuk mengindikasikan apakah sebuah vehicle bergerak antara dua customer pada kondisi optimal. Formulasi ini pertama kali diajukan oleh Garvin et al. (1957) untuk memodelkan sebuah

9 permasalahan pengantaran minyak, yang dikembangkan oleh Gavish dan Graves (1982).

kemudian

Gheysens et al. (1984) membuat formulasi menggunakan variabel biner dengan tiga index xijk sebagai aliran vehicle yang bernilai 1 jika sebuah vehicle bertipe k melakukan perjalanan dari customer i ke customer j, dan 0 jika tidak. Disamping itu ada variabel lain yaitu y ij melambangkan jumlah barang yang dibawa ketika meninggalkan customer i menuju customer j. Formulasi matematis Heterogeneous Fleet VRP secara lengkap dapat dilambangkan sebagai berikut:

Pada formula diatas, konstrain (2) dan (3) memastikan tiap customer hanya dikunjungi sekali saja, dan jika sebuah vehicle mengunjungi seorang customer, dia juga harus berangkat meninggalkan customer tersebut. Jumlah maksimal vehicle yang tersedia untuk setiap tipe vehicle dibatasi dengan konstrain (4). Konstrain (5) merupakan konstrain pada arus item, dimana perbedaan jumlah barang pada sebuah vehicle sebelum dan setelah mengunjungi suatu customer haris sama dengan demand dari customer tersebut. Yang terakhir, konstrain (6) memastikan

10 bahwa jumlah barang yang dibawa sebuah vehicle tidak boleh melebihi kapasitas maksimal dari vehicle tersebut. 2.1.3

Aplikasi VRP Pada Kehidupan Nyata

Aplikasi VRP pada kehidupan nyata dapat ditemukan pada banyak hal, seperti pada permasalahan pengantaran produk dari suplier kepada agen, pengangkutan sampah, pengambilan surat pada kotak pos, pengantaran koran pada para pelanggan, dan sebagainya. Tentunya tidak semua perusahaan pengangkut sampah mempunya armada yang sama persis, tidak semua loper koran menggunakan kendaraan yang sama, dan tidak semua suplier menggunakan jenis pengangkutan yang sama, bisa menggunakan kendaraan darat, sepeda motor, mobil, truk, atau bahkan kapal laut dan pesawat terbang. Permasalahanpermasalahan tersebut diatas dapat diefisiensikan dengan dicari nilai optimalnya menggunakan pemodelan VRP. Sayangnya, parameter-parameter dari proses pengiriman barang tidak sesederhana itu. Pada aplikasinya, ada berbagai konstrain tambahan yang harus dipertimbangkan, seperti biaya perjalanan yang asimetris, depot yang lebih dari satu, jangka waktu pengiriman (misalnya pada pengiriman makanan), adanya penjemputan barang selain pengiriman, dan masih banyak lagi kemungkinan-kemungkinan lain yang spesifik pada aplikasi tertentu. Karena banyaknya kemungkinan yang bisa terjadi, dalam tugas akhir ini hanya dibahas penyelesaian VRP dengan beberapa tipe kendaraan yang mempunyai kapasitas yang berbeda, yang dikenal dengan Heterogeneous Fleet VRP. 2.1.4

Metode penyelesaian VRP

Pada bab 2.1.1 dijelaskan bahwa VRP dapat dianggap sebagai kombinasi dari BPP dan TSP. Baik BPP dan TSP, keduanya dikategorikan sebagai permasalahan NP-hard [3] dan [6], sehingga VRP juga dikategorikan sebagai NP-hard yang mungkin belum ditemukan metode eksak untuk mencari nilai optimalnya [3]. Karena itu digunakan metode selain eksak untuk

11 memecahkan VRP berskala besar. Untuk VRP skala kecil dengan beberapa customer dan homogeneous fleet (semua kendaraan mempunyai kapasitas yang sama), branch and bound terbukti sebagai metode terbaik untuk mencari solusi optimal [7]. Kebanyakan penyelesaian untuk VRP berskala besar menggunakan heuristic. Heuristic adalah algoritma yang berbasis kira-kira, yang berusaha mencari solusi optimal secepat mungkin. Secara garis besar, metode heuristic dapat dikategorikan menjadi dua bagian besar, yaitu heuristic klasik yang berkembang antara tahun 1960 dan 1990, dan metaheuristic yang berkembang mulai 1990 [1]. Metode heuristic klasik dapat dikategorikan lagi menjadi tiga kategori, yaitu Construction Method, Twophase method, dan Improvement methods [8]. Metode metaheuristic jauh lebih efektif dibandingkan metode heuristic klasik [9]. Metode-metode metaheuristic menggabungkan Neighbourhood Search, Memory Structure, dan Recombination pada tiap solusi untuk menghasilkan solusi yang lebih baik [10]. Akan tetapi, waktu proses yang dibutuhkan metaheuristic tidak dapat diketahui secara pasti, dan biasanya lebih lama dibandingkan heuristic klasic. Selain itu metaheuristic juga melibatkan lebih banyak parameter daripada heuristic klasik. Selama satu dekade terakhir, setidaknya ada enam metode metaheuristic untuk aplikasi VRP yang ditemukan, metodemetode tersebut adalah Simulated Annealing (SA), Deterministic Annealing (DA), Tabu Search (TS), Ant Systems (AS), Neural Network (NN), dan Genetic Algorithm [10]. Algoritma SA, DA, dan TS bergerak dari satu solusi ke solusi lain yang merupakan tetangganya, sampai memenuhi stopping criterion yang ditentukan. Algoritma AS menggunakan mekanisma konstruktif untuk menciptakan beberapa solusi pada tiap iterasi berdasarkan informasi yang didapat dari iterasi sebelumnya. Algoritma NN adalah algoritma pembelajaran, dimana serangkaian parameter secara bertahap diseusaikan nilainya sampai memenuhi solusi

12 yang sesuai keinginan. Dan yang terakhir, algoritma GA yang mempertahankan sejumlah solusi-solusi yang paling berkualitas, dan mengkombinasikannya untuk membentuk solusi baru. 2.2

Genetic Algorithm

2.2.1

Latar belakang Genetic Algorithm

Pada tahun 1859 Charles Darwin (1809 - 1882), seorang peneliti alam dari Inggris, mengumumkan teorinya yang berjudul “Theory of Natural Selection” [5]. Teori tersebut menyatakan bahwa individu-individu yang mempunyai karakteristik yang bagus (menurut kriteria-kriteria tertentu) akan mempunyai kemungkinan untuk bertahan hidup lebih besar dan bereproduksi dan menurunkan karakteristiknya kepada keturunanketurunannya. Berlaku sebaliknya, individu-individu dengan karakteristik yang kurang bagus secara perlahan akan tersingkir dari populasi. Pada alam ini, informasi genetik dari sebuah individu disimpan dalam chromosome, yang terdiri dari sekumpulan gen. Karakteristik dari setiap individu dikendalikan oleh gen-gen tersebut, yang kemudian akan diwariskan kepada keturunanketurunannya ketika individu tersebut berkembang biak. Selain faktor perkembangbiakan, suatu ketika juga terjadi peristiwa yang disebut mutasi, yang menyebabkan terjadinya perubahan informasi pada chromosome. Berdasarkan teori Darwin tersebut, nilai rata-rata karakteristik dari populasi akan meningkat setiap generasi, seiring dengan bertambahnya individu-individu yang mempunyai kriteria yang bagus dan punahnya individu-individu yang mempunyai kriteria yang buruk. Terinspirasi dari teori darwin tersebut, pada tahun 1975 John Holland dan timnya menciptakan teori Genetic Algorithm [4]. Ide utama dibalik Genetic Algorithm ini adalah memodelkan proses evolusi alami menggunakan warisan genetika seperti yang diumumkan oleh Darwin. Meskipun diperkenalkan oleh John

13 Holland, penggunaan Genetic Algorithm untuk memecahkan persoalan yang compleks baru didemonstrasikan kemudian (pada tahun yang sama) oleh De Jong, dan kemudian oleh Goldberg pada tahun 1989. Menyesuaikan dengan teori Darwin, dalam Genetic Algorithm digunakan istilah-istilah yang mewakili elemen-elemen dalam teori Darwin tersebut, yaitu seperti yang dapat dilihat pada tabel 2.1. Tabel 2.1 Daftar istilah pada GA beserta penjelasan

Istilah

Makna

Population

Merupakan sekumpulan solusi dari permasalahan yang akan diselesaikan menggunakan Genetic Algorithm. Population terdiri dari sekumpulan Chromosome.

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

Mewakili elemen-elemen yang ada dalam sebuah solusi.

Parent

Merupakan chromosome yang akan dikenai operasi genetik (crossover).

Offspring

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

Crossover

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

14 (keturunan).

Mutation

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

Selection Procedure

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

Fitness Value

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

Evaluation Function

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

Generation

Merupakan satuan dari populasi setelah mengalami operasi-operasi genetika, berkembang biak, dan menghasilkan keturunan. Pada akhir dari setiap generation, untuk menjaga agar jumlah chromosome dalam populasi tetap

15 konstan, chromosome-chromosome yang mempunya Fitness Value yang rendah dan memiliki peringkat dibawah nilai minimal akan dihapus dari populasi. Genetic Algorithm merupakan metode pembelajaran heuristic yang adaptif, karena itu bisa jadi terdapat beberapa versi dari Genetic Algorithm, yang menyesuaikan dengan permasalahan yang dihadapi. Genetic Algorithm juga merupakan algoritma yang efektif dan sederhana dan relatif mudah untuk diimplementasikan. Genetic Algorithm memiliki keunggulan-keunggulan dibandingkan dengan metode-metode heuristic yang lain, yaitu : -

GA menyelesaikan masalah dengan mengkodekan permasalah menjadi chromosome, bukan dengan menyelesaikan permasalahan itu sendiri. Karena itu diperlukan pemodelan chromosome yang baik dan efektif yang dapat mewakili solusi dari permasalahan yang dihadapi.

-

GA memulai prosesnya dengan sekumpulan initial solutions, berbeda dengan metaheuristic lain seperti Simulated Annealing dan Tabu Search yang memulai proses dengan sebuah solusi tunggal, dan berlanjut ke solusi lainnya melalui suatu transisi. Karena itu GA melakukan pencarian multidirectional dalam solution space, yang memperkecil kemungkinan berhentinya pencarian pada kondisi local optimum.

-

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

-

Genetic Algorithm merupakan algoritma yang ‘buta’, karena GA tidak mengetahui kapan dirinya telah mencapai solusi yang optimal.

Seperti yang telah disebutkan sebelumnya, Genetic Algorithm dapat dengan mudah beradaptasi dengan berbagai macam permasalahan, sehingga ada banyak versi dari Genetic

16 Algorithm, tergantung dari permasalahan yang ingin dipecahkan. Tapi secara umum Genetic Algorithm harus memenuhi kriteriakriteria dibawah ini untuk menghasilkan solusi yang optimal: -

Sebuah representasi yang tepat dari permasalahan, dalam bentuk chromosome.

sebuah

-

Pembangkit populasi awal. Umumnya populasi awal dibangkitkan secara acak, namun untuk beberapa kasus juga bisa dibangkitkan melalui metode-metode tertentu. Penggabungan keduanya (pembangkitan populasi awal secara acak dan menggunakan metode-metode tertentu) disebut dengan seeding. Populasi awal yang dihasilkan sebaiknya bersifat heterogen, karena jika populasi yang terbentuk terlalu homogen, Genetic Algorithm kehilangan kemampuannya untuk mencari dalam solution space, sampai populasi mempunyai variasi chromosome yang beragam melalui operasi genetik lain (mutation).

-

Sebuah evaluation function untuk menentukan fitness value dari tiap solusi.

-

Genetic Operator, mensimulasikan (perkembangbiakan) dan mutasi.

-

Parameter-parameter lain, seperti kapasitas populasi, probabilitas dari operasi-operasi genetik, dan semacamnya.

proses

solusi

reproduksi

Kapasitas populasi sangat mempengaruhi kemampuan Genetic Algorithm dalam mencari solusi. Kapasitas populasi yang terlalu kecil menyebabkan kurangnya variasi chromosome yang muncul, sehingga dapat menyebabkan hasil akhir yang buruk. Kapasitas populasi yang besar biasanya memberikan hasil yang lebih baik, dan mencegah terjadinya konvergensi yang prematur. 2.2.2

Fitness Value

Untuk melakukan seleksi alam, setiap individual i dievaluasi menggunakan nilai fitness value fi, yang ditentukan

17 dengan sebuah fungsi evaluasi. Fitness value mengukur kualitas dari sebuah solusi dan memungkinkan tiap solusi untuk dibandingkan. Memilih individual untuk proses reproduksi dan seleksi alam mempunyai efek yang sangat berpengaruh terhadap efisiensi GA. Seleksi yang berlebihan akan mengarahkan GA ke kondisi konvergen yang prematur, yang merupakan masalah utama pada GA [11]. Karena proses seleksi bergantung pada fitness value, maka penting dalam GA untuk membuat fungsi evaluasi dengan hati-hati. 2.2.3

Selection

Dari penelitian, terlihat bahwa keragaman populasi dan pemilihan seleksi merupakan faktor penting dalam pencarian genetik [11]. Keduanya saling berkaitan, karena penekanan pada proses seleksi akan menurunkan jumlah populasi dan sebaliknya. Jika anggota populasi menjadi terlalu homogen, mutasi merupakan satu-satunya faktor untuk menghasilkan variasi pada populasi, karena itu proses selection merupakan tahapan yang penting dalam GA. Individu yang lebih kuat akan mempunyai kemungkinan yang lebih besar untuk melakukan reproduksi. Salah satu metode selection yang banyak digunakan adalah metode Roulette Wheel. Pada metode ini, kemungkinan memilih sebuah individual berkaitan langsung dengan fitness value-nya. Gambar 2.2 mengilustrasikan sebuah cara sederhana untuk menentukan selection pada lima individu dalam sebuah populasi. Individu P1 punya fitness value f1, P2 punya f2, dan seterusnya. Bayangkan ada sebuah pin diatas roda tersebut, kemudian roda tersebut diputar sampai berhenti. Dari proporsi pembagian luas roda pada tiap individu, dapat diperkirakan bahwa individu P3 mempunyai kemungkinan terpilih paling besar, dan individu P4 mempunyai kemungkinan paling kecil. Kelemahan Roulette Wheel adalah, karena langsung menggunakan fitness value, akan menimbulkan permasalahan ketika perbedaan fitness value antar individu tidak terlalu besar, sehingga kemungkinan tiap individu menjadi hampir sama.

18

Gambar 2.2 Contoh metode Roulette Wheel

Metode lainnya adalah metode Ranking, yang telah memberikan hasil yang relatif lebih bagus [4]. Metode ini menggunakan perbandingan nilai relatif dari tiap individual, bukan nilai fitness itu sendiri. Karena jika menggunakan nilai fitness langsung, maka jika populasi mempunya beberapa individu yang dominan, individu-individu tersebut akan semakin mendominasi populasi dan menyebabkan konvergensi prematur. Metode lainnya adalah Tournament Selection, yang merupakan kombinasi dari selection dan ranking. Pada tournament selection, setiap individu dibandingkan dalam sebuah ‘turnamen’, dimana individu yang berkualitas lebih baik akan menang. Metode turnamen yang umum digunakan adalah pendekatan biner, dimana pada satu waktu dipilih dua pasang individu (secara acak), dan membandingkan masing-masing pasangan individu untuk mendapatkan dua individu yang terbaik dari masing-masing pasangan. 2.2.4

Crossover

Operator GA yang paling utama adalah crossover, yang mensimulasikan proses reproduksi antara dua individu. Cara kerjanya adalah menggabungkan dua buah individu (yang disebut parent) untuk menghasilkan satu atau lebih individu baru (yang disebut offspring). Offspring tersebut mewarisi sifat-sifat genetik dari offspring-nya, sehingga sifat-sifat baik dari parent-nya tetap

19 dipertahankan dan diharapkan dari dua parent yang baik dapat menghasilkan offspring/keturunan yang lebih baik. Ada beberapa proses crossover yang dapat diaplikasikan pada GA, bergantung pada tipe permasalahan dan tipe populasi yang ada, namun proses crossover sederhana dapat diilustrasikan sebagai berikut; ambil dua parent P1 dan P2 yang dipilih menggunakan proses selection (atau random), kemudian masingmasing parent tersebut dipecah menjadi dua bagian pada bagian yang sama. Kedua parent tersebut kemudian saling bertukar pasangan untuk menghasilkan dua offspring O1 dan O2, seperti ditunjukkan pada gambar 2.3. Offsprint O1 dihasilkan dari potongan kanan P1 dan potongan kiri P2, dan offspring O2 dihasilkan dari potongan kiri P2 dan potongan kanan P2.

Gambar 2.3 Ilustrasi proses crossover

2.2.5

Mutation

Operator lain yang juga berperan penting adalah mutation (mutasi), yang diaplikasikan pada sebuah individual tertentu. Proses ini merubah sedikit komposisi penyusun individual tersebut, dan menambahkan suatu karakteristik tertentu secara acak. Proses ini tidak boleh terlalu banyak dilakukan karena akan membuat GA menjadi seperti random search, sedangkan jika populasi GA ada pada kondisi yang sangat konvergen, mutasi justru diperlukan untuk membuat variasi-variasi baru pada populasi.

20

Gambar 2.4 Ilustrasi proses mutation

Contoh sederhana operasi mutation dapat dilihat pada gambar 2.4. Pada gambar tersebut terdapat sebuah data biner P yang merupakan parent individual. Kemudian dipilih sebuah bit secara acak untuk dilakukan proses mutasi. Pada contoh, dipilih bit pada posisi nomor 2, yang kemudian dirubah dari 0 menjadi 1 pada offspring-nya. 2.3

Genetic Algorithm Dalam Lingungan Paralel

Metode universal yang digunakan untuk memparalelkan GA disebut sebagai IIP Parallel, Identical and Independent Processing Parallel. Sederhananya, sejumlah prosesor menjalankan dan memproses GA yang sama, tapi nantinya ada satu prosesor yang mengumpulkan hasil dari prosesor-prosesor lainnya dan melaporkan hasilnya ke user. Aplikasi dari metode ini dapat diklasifikasikan menjadi tiga bagian, Global Model, Island Model, dan Cellular Model. Global Model hanya memecah populasi total menjadi sub-sub populasi dan menyebarnya di seluruh prosesor secara rata, tanpa adanya saling keterkaitan antar prosesor, sehingga tiap prosesor mengatur sub-populasinya masing-masing. Kesemua prosesor berusaha memecahkan masalah yang sama secara terpisah, namun simultan. Pada Island model, populasi total tidak hanya dipecah sama rata ke setiap prosesor, namun secara periodik, tiap prosesor juga saling bertukar sejumlah populasi yang dimilikinya, yang disebut sebagai proses migration. Individu yang dimigrasikan adalah individu-individu terbaik dalam tiap populasi, tetapi individu tersebut juga digunakan pada populasi asalnya pada iterasi berikutnya, jadi individu yang dimigrasikan tersebut tidak

21 kemudian dihapus dari populasi asal. Sedangkan Cellular Model membatasi interaksi sebuah individu hanya pada tetangganya saja, untuk lebih jelasnya dapat dilihat pada gambar 2.5. Hal ini membantu memudahkan pencarian dalam search space karena penyebaran yang lambat pada search space membuat eksplorasi menjadi lebih terarah [13].

Gambar 2.5 Model populasi Panmictic Genetic Algorithm (normal) dan Cellular Genetic Algorithm

Misalkan ada sejumlah N individual dalam sebuah populasi yang akan disebar di sejumlah M prosesor, maka jumlah individu yang berada pada tiap prosesor adalah sebanyak N/M individu. Selain pembagian populasi menjadi sub-populasi, sesuai dengan penjelasan diatas yang menjelaskan adanya proses migration, maka Island Model juga membutuhkan variabel lain yang disebut migration interval, yang menyatakan jumlah generasi (iterasi) yang membatasi antar setiap proses migration, dan migration size, yang menyatakan jumlah individu yang akan mengalami proses migration pada satu waktu. Island Model telah terbukti menghasilkan hasil pencarian yang lebih bagus, baik dari segi kualitas solusi yang dihasilkan, maupun dari segi kebutuhan komputasional yang diperlukan [12]. Penyebab terjadinya peningkatan dalam kualitas solusi yang dihasilkan adalah karena setiap island (pulau) mempunya derajat

22 independensi sendiri-sendiri, yang memungkinkan kesemuanya mencari solusi dalam lebih dari satu search space yang berbeda, sambil tetap saling bertukar informasi satu sama lain.

Gambar 2.6 Ilustrasi proses mutation

Penggunaan Island Model GA mengambil ide dari alam, dimana melalui penelitian didapatkan hasil bahwa pulau yang terisolasi dapat mengembangkan spesialisasi yang berbeda-beda tergantung pada kondisi lokal di pulau tersebut. Karena itu Darwin [5] mengamati populasi dari burung finch pada beberapa pulau yang berbeda di kepulauan Galapagos dan mendapati adanya perbedaan bentuk fisik pada paruh burung-burung tersebut. Hasil dari pengamatan tersebut dapat dilihat pada gambar 2.6; pada gambar 2.6 terdapat beberapa tipe paruh dari beberapa jenis burung finch, yaitu Geospiza Magnirostris (1), Geospiza Fortis (2), Geospiza Parvula (3), Certhidea Olivacea (4). Keragaman populasi tersebut disebabkan karena adanya variasi dari tumbuh-tumbuhan yang ada di setiap pulau tersebut, dan perbedaan makanan. Pada alam, populasi yang berbeda dari spesies asal dapat membuat spesies tersebut berevolusi secara

23 independen dan menghasilkan spesies baru yang berbeda jauh dari spesies asalnya. 2.4

Message Passing Interface

Message Passing Interface (MPI) adalah protokol komunikasi yang independen secara bahasa yang digunakan untuk memprogram komputasi paralel. Tujuan pembuatan MPI adalah untuk mendapatkan performa, skalabilitas, dan portabilitas yang tinggi. Keuntungan menggunakan MPI adalah portabilitas yang tinggi, karena MPI dapat dan telah diimplementasikan ke berbagai arsitektur. MPI juga telah mendukung arsitektur shared memory. Portabilitas tinggi memungkinkan para programmer tidak perlu merubah source code program mereka ketika memport aplikasi mereka ke platform lain yang didukung oleh MPI. Selain itu karena MPI pekerja langsung pada layer 5 (pada model network OSI), MPI mempunyai performa yang bagus dalam melakukan komunikasi antar komputer. MPI adalah sebuah spesifikasi, bukan implementasi. MPI mempunyai Language Independent Specification (LIS) dari fungsi-fungsi dasar untuk digunakan sesuai dengan bahasa penggunanya. Implementasi MPI pada tiap bahasa bisa berbeda, namun pada prinsipnya pasti sama dan sesuai dengan LIS. Implementasi awal pada MPI 1.x bernama MPICH yang dikembangkan oleh Argonne National Laboratory dan Mississippi State University. IBM juga merupakan salah satu implementator yang pertama kali mendukung standard MPI, dimana kebanyakan superkomputer keluaran IBM pada awal 1990an menggunakan MPICH sebagai core-nya atau menggunakan implementasi MPI lain buatan IBM sendiri. LAN/MPI dari Ohio Supercomputing Center merupakan salah satu implementasi dari MPI 1.x. Argonne National Laboratory terus mengembangkan MPICH dan kemudian mengeluarkan MPICH 2, yang merupakan implementasi dari MPI 2.1. LAM/MPI dan sejumlah peneliti MPI lainnya dari seluruh dunia kemudian bergabung dan

24 mengeluarkan Open MPI yang kemudian dikembangkan ke berbagai platform. 2.4.1

Terminologi Dasar Pemrograman Paralel

Pemrograman paralel merupakan cara pemecahan suatu masalah secara paralel menggunakan lebih dari satu komputer. Hal ini dilakukan dengan tujuan mempercepat proses komputasional yang dibutuhkan untuk menyelesaikan permasalahan tersebut. Salah satu alasan menggunakan komputasi paralel adalah karena harga sebuah supercomputer berkecepatan tinggi masih jauh lebih mahal daripada beberapa workstation yang diparalel. Langkah-langkah untuk membuat program yang berjalan secara paralel sederhananya adalah sebagai berikut: 1. Mempersiapkan konsep paralel (task partitioning, dependency analysis). 2. Mapping dan scheduling proses paralel. 3. Coding dan Debugging. 4. Mengevaluasi hasil paralelisasi. Sebuah komputasi tunggal yang akan dikerjakan oleh sebuah prosesor diistilahkan sebagai sebuah task. Sebuah task Tx dapat berupa sebuah statement, subroutine, atau bahkan keseluruhan program. Disini diasumsikan bahwa sebuah task bersifat convex, dimana setelah task tersebut dimulai, dia tidak akan meminta sebuah proses komunikasi. Diantara tiap task terdapat penghubung yang disebut dependence yang menyatakan ketergantungan sebuah task terhadap task yang lain, yang biasanya digambarkan dalam sebuah directed acyclic task graph (DAG). Sebuah task Tx juga mempunyai sebuah weight τx yang melambangkan waktu yang diperlukan untuk menyelesaikan task tersebut. Jika sebuah task Tx perlu melakukan komunikasi dengan task lain dalam prosesor yang berbeda, maka task tersebut juga akan mempunyai sebuah nilai cost cx.

25 Untuk mengevaluasi sebuah proses komputasi parallel, digunakan rumus standard sebagai berikut, dimana sebelunmnya diasumsikan terlebih dahulu sebuah nilai p yang menyatakan jumlah prosesor yang digunakan:

Speedup = 2.4.2

SequentialTime Speedup , Efficiency = ParallelTime p

Fungsi-fungsi dasar MPI

Fungsi-fungsi dasar MPI cukup sederhana dan meliputi fungsi inisialisasi dan fungsi dasar send/receive, untuk lengkapnya dapat dilihat pada tabel 2.2. Tabel 2.2 Daftar fungsi-fungsi utama pada MPI

Nama Fungsi

Tujuan Fungsi

MPI_Init

Inisialisasi lingkungan MPI. Fungsi ini hanya boleh dipanggil sekali, sebelum penggunakan fungsi-fungsi MPI yang lain.

MPI_Comm_size

Untuk menentukan jumlah prosesor yang tergabung dalam sebuah communicator (contohnya MPI_COMM_WORLD)

MPI_Comm_rank

Untuk menentukan rank dari prosesor yang memanggil fungsi ini dalam sebuah communicator (contohnya MPI_COMM_WORLD)

MPI_Abort

Untuk menghentikan semua proses MPI yang berjalan dalam communicator.

MPI_Wtime

Untuk melihat waktu yang telah berjalan semenjak panggilan terakhir terhadap fungsi

26 ini sebelumnya. MPI_Finalize

Untuk menghentikan lingkungan eksekusi MPI pada communicator.

MPI_Send

Fungsi dasar untuk mengirim data.

MPI_Recv

Fungsi dasar untuk memerintahkan komputer agar menunggu data yang akan masuk.

MPI_Bcast

Mem-broadcast sebuah pesan ke semua prosesor yang tergabung dalam sebuah communicator (contohnya MPI_COMM_WORLD)

BAB 3 PERANCANGAN PERANGKAT LUNAK

Pada bab ini akan dibahas mengenai perancangan perangkat lunak aplikasi, yang terdiri dari Deskripsi Umum, Rancangan Umum, Perancangan Database, Perancangan Arsitektur, dan Perancangan Antarmuka. 3.1

Deskripsi Umum Perangkat Lunak

Aplilasi Vehicle Routing Solver ini dibuat untuk menyelesaikan permasalahan VRP, khususnya yang bertipe heterogeneous, namun juga bisa digunakan untuk menyelesaikan homogeneous VRP. Metode yang digunakan adalah Genetic Algorithm, yang sudah terbukti kemampuannya untuk memecahkan permasalahan Integer Programming yang sifatnya NP-Hard. Karena Genetic Algorithm merupakan metode metaheuristic dan bukan merupakan metode eksak, maka semakin lama proses pencarian, solusi yang didapat cenderung semakin bagus. Karena itu, untuk mengefektifkan waktu yang digunakan untuk proses komputasi, maka digunakan arsitektur komputasi paralel menggunakan framework MPI dan software middleware DeinoMPI. 3.2

Rancangan Aplikasi Secara Umum

Pemodelan jaringan untuk lingkungan paralel pada aplikasi ini menggunakan model master-slave. Ada satu komputer yang disebut sebagai master, sedangkan sisanya bertindak sebagai prosesor. Tugas dari komputer master hanyalah menunggu solusi optimal dari setiap prosesor, kemudian menggabungkannya dan 27

28 mencari nilai yang paling optimal. Sedangkan komputer prosesor, seperti namanya, bertugas mencari solusi dengan melakukan serangkaian operasi GA pada populasinya sendiri-sendiri sesuai dengan parameter GA yang diinputkan oleh user. Setelah sebuah prosesor selesai melakukan tugasnya dan mendapatkan solusi optimal, komputer prosesor tersebut kemudian mengirimkan solusi optimal tersebut ke komputer master. Detail arsitektur jaringan aplikasi ini dapat dilihat seperti pada gambar 3.1.

Gambar 33.1 Arsitektur Sistem VRP Solver

Pada awal eksekusi, komputer master melihat jumlah prosesor yang tergabung dalam lingkungan paralelnya, kemudian melakukan proses listening sejumlah prosesor tersebut. Setelah semua prosesor melaporkan solusi optimal yang dihasilkannya, maka komputer master kemudian akan mengurutkan solusi-solusi optimal dari tiap prosesor, dan mengambil satu solusi yang paling optimal. Untuk komputer prosesor, pada awal eksekusi setiap prosesor membuat populasi sebesar hasil bagi dari populasi total yang diinputkan oleh user dengan banyaknya prosesor yang

29 tersedia. Setelah itu setiap komputer prosesor akan memproses populasinya sendiri-sendiri dengan algoritma GA. Setelah selesai, komputer prosesor akan mengirimkan hasil prosesnya ke komputer master. Pada akhir setiap iterasi (yang pada GA diistilahkan sebagai generasi), terjadi proses yang disebut dengan migrasi. Pada proses ini, sebuah prosesor mengirimkan solusi terbaiknya ke sebuah prosesor lainnya secara berurutan. Sebagai contoh, setelah iterasi pertama selesai, prosesor 1 akan mengirimkan populasi terbaiknya ke prosesor 2. Setelah iterasi kedua selesai, maka prosesor 1 akan mengirimkan populasi terbaiknya ke prosesor 3. Untuk iterasi berikutnya, prosesor 1 akan mengirimkan populasi terbaiknya ke prosesor 4, dan begitu seterusnya sampai sejumlah prosesor yang ada. Setelah semua prosesor yang ada pernah menerima kiriman solusi terbaik dari prosesor 1, maka untuk iterasi berikutnya prosesor 1 akan kembali melakukan pengiriman ke prosesor 2, prosesor 3, dan seterusnya, sampai stopping criterion yang ditentukan user terpenuhi. Sehubungan dengan proses migrasi yang telah dijelaskan sebelumnya, maka pada awal setiap iterasi, setiap prosesor akan memeriksa apakah ada solusi dari prosesor lain yang dikirimkan untuknya. Jika ada, maka solusi dari prosesor lain tersebut akan digabungkan terlebih dahulu dengan populasi miliknya sendiri, baru kemudian diproses dengan algoritma GA. 3.3

Pemodelan Chromosome

Dalam merancang model chromosome sebagai model solusi untuk suatu permasalahan VRP, perlu diawali dengan pertimbangan beberapa hal, diantaranya bahwa chromosome harus dapat mengandung informasi banyaknya vehicle pada solusi tersebut, serta informasi penugasan vehicle terhadap tiap customer. Karena VRP merupakan permasalahan yang berkaitan dengan rute, sebaiknya digunakan tipe chromosome yang nonrepetitive, oleh karena itu chromosome yang terdiri dari angka-

30 angka biner tidak dapat digunakan. Sehingga, digunakan chromosome yang berisi angka-angka numerik, yang setiap angkanya mewakili sebuah customer. Chromosome tersebut terdiri dari beberapa sub-rute yang mewakili rute yang dijalankan oleh tiap vehicle. Visualisasi chromosome tersebut dapat dilihat pada gambar 3.2.

Gambar 33.2 Pengkodean chromosome untuk VRP

Untuk menuliskannya dalam sebuah chromosome, digunakan sebuah gen khusus bernilai 0, yang merupakan pemisah antar setiap rute, dengan asumsi tidak boleh ada kota yang menggunakan id 0. Sehingga ilustrasi pada gambar 3.2 tersebut jika dituliskan dalam bentuk chromosome akan menjadi A {5, 1, 3, 6, 0, 9, 7, 2, 0, 8, 10, 4}. 3.4

Perancangan Operator-Operator Genetic Algorithm

Operator-operator Genetic Algorithm yang digunakan pada aplikasi VRP Solver ini adalah : -

Population Generator Population Generator pada aplikasi ini terdiri dari beberapa proses. Proses petama adalah meng-generate random route. Setelah itu dilakukan pengecekan apakah route hasil generate tersebut feasible atau tidak. Jika route tersebut feasible, maka route tersebut langsung dimasukkan ke dalam populasi. Jika route tersebut tidak feasible, ada kemungkinan sebesar 10% supaya route tersebut tetap dimasukkan dalam populasi. Proses ini diperlukan selain untuk memperkaya populasi dengan berbagai variasi chromosome (sehingga memperlebar search space), juga untuk mempersingkat waktu proses secara keseluruhan. Selain itu, memasukkan beberapa solusi-solusi yang tidak feasible seingkali membuat GA mendapatkan hasil yang lebih optimal.

31 Proses generate random route dilakukan menggunakan metode sebagai berikut: Pertama, terlebih dahulu di-list kotakota yang terdapat pada permasalahan VRP yang diinputkan user. Untuk setiap kota yang bukan termasuk depot, kota tersebut dimasukkan ke sebuah list baru. Pada saat memasukkan kota-kota tersebut ke list baru, disisipkan juga kota ber-ID 0, yang menjadi pemisah antar sub-rute, secara merata ke dalam list tersebut, sehingga membentuk sub-rute sebanyak jumlah kendaraan yang ada. Pengertian ‘secara merata’ adalah sebagai berikut: misalkan ada 12 kota dan 3 kendaraan, maka setiap kali fungsi memasukkan 4 kota disisipkan sebuah pemisah, begitu pula seterusnya sehingga totalnya akan dimasukkan sebanyak 2 buah pemisah (yang membentuk 3 rute). Setelah itu rute tersebut kemudian diacak menggunakan fungsi random. -

Selection Proses selection adalah proses pemilihan dua buah chromosome dari keseluruhan populasi untuk dikenakan operasi-operasi Genetic Algorithm lainnya. Pada aplikasi ini, proses selection yang digunakan adalah Roulette Wheel Selection. Flowchart dari proses Roulette Wheel tersebut dapat dilihat pada gambar 3.3. Penjelasan dari flowchar pada gambar 3.3 adalah sebagai berikut: Pertama cari terlebih dahulu nilai evaluasi (jarak total perjalanan) terbesar dari keseluruhan solusi yang ada pada populasi. Setelah itu hitung selisih dari nilai evaluasi terbesar dengan nilai evaluasi setiap chromosome. Nilai-nilai itu kemudian dijumlahkan. Hasilnya kemudian dikalikan dengan sebuah angka random dan menghasilkan sebuah nilai. Nilai tersebut kemudian dicari posisinya pada daftar selisih nilai evaluasi terbesar dengan nilai evaluasi tiap chromosome. Posisi tersebut kemudian dikembalikan sebagai hasil proses selection, yang menyatakan index dari chromosome hasil proses selection tersebut pada populasi keseluruhan.

32

Mulai

maxEvaluations = total jarak terpanjang

Foreach(population) as i

sumOfEvaluations += (maxEvaluations - i->TotalDistance)

f = sumOfEvaluations * random

Foreach(population) as i

f -= (maxEvaluations – I->TotalDistance)

f < (maxEvaluations - i->TotalDistance)

Return(i)

Gambar 33.3 Flowchart Proses Roulette Wheel Selection

-

CrossOver Operasi CrossOver yang digunakan dalam aplikasi ini adalah Simple Random Crossover. Flowchart dari proses ini dapat dilihat pada gambar 3.4. Input dari proses CrossOver ini adalah dua buah chromosome yang sebelumnya diambil lewat proses selection.

33

Gambar 33.4 Flowchart proses Simple Random CrossOver

Algoritma Simple Random CrossOver ini memerlukan chromosome yang bertipe non-repetitive, dimana tidak boleh ada lebih dari satu gen yang bernilai sama, sedangkan chromosme yang digunakan pada aplikasi ini bertipe repetitive (menggunakan lebih dari satu gen bernilai 0 sebagai penanda depot atau pemisah sub-rute), karena itu pada awal operasi CrossOver, dilakukan normalisasi pada kedua chromosome yang akan disilangkan. Proses tersebut dilakukan dengan mengganti gen-gen yang bernilai 0 (depot) dengan integer-integer negatif dekremental (-1, -2, -3, dsb), sehingga chromosome yang dihasilkan akan menjadi bertipe non-repetitive. Contoh proses normalisasi adalah sebagai berikut: Misalkan ada sebuah chromosome A {1, 0, 2, 3, 0, 4, 5} yang akan dikenai proses normalisasi. Maka hasil proses

34 normalisasi terhadap chromosome tersebut akan menjadi A’ {1, -1, 2, 3, -2, 4, 5}. Setelah chromosome tersebut dikenai proses persilangan, maka chromosome tersebut harus dikembalikan menjadi nilai asalnya dengan proses denormalisasi. Proses denormalisasi pada sebuah chromosome bertindak mencari gen-gen yang bernilai negatif (sesuai ketentuan sebelumnya pada proses normalisasi) dan kemudian mengganti nilainya menjadi 0 (depot). Setelah kedua chromosome inputan menjadi bertipe nonrepetitive, maka proses selanjutnya adalah memilih satu titik acak yang akan menjadi titik persilangan antara kedua chromosome tersebut. Kedua chromosome kemudian saling disilangkan pada titik acak tersebut. Contoh proses persilangan Simple Random Crossver adalah sebagai berikut: Misalkan ada chromosome A {1, 2, 3, 4, 5} dan B {6, 7, 8, 9, 10} yang akan disilangkan. Fungsi acak yang dipanggil untuk menentukan titik persilangan diasumsikan menghasilkan nilai yang menyatakan bahwa titik persilangan ada pada gen ke 3, maka hasil persilangan kedua chromosome tersebut akan menjadi A’ {1, 2, 3, 9, 10} dan B’ {6, 7, 8, 4, 5}. -

Mutation Proses mutasi pada umumnya adalah proses pergantian bit dari 1 menjadi 0 pada suatu titik tertentu yang didapatkan secara acak. Namun karena chromosome yang digunakan pada aplikasi ini adalah bertipe non-repetitive, maka operator mutasi yang digunakan adalah Random Swap Mutation, yaitu proses pertukaran dua buah gen dalam satu chromosome, dimana gen-gen yang akan ditukarkan tersebut didapatkan secara acak. Flowchart proses Random Swap Mutation dapat dilihat pada gambar 3.5.

35

Gambar 33.5 Flowchart proses Random Swap Mutation

Proses Random Swap Mutation bekerja sebagai berikut: Misalkan ada sebuah chromosome A {1, 2, 3, 4, 5, 6} yang akan dikenai proses mutation. Proses pertama adalah mendapatkan dua buah bilangan secara acak yang akan melambangkan titik pertukaran. Diasumsikan setelah melalui suatu proses random, kedua nilai acak tersebut adalah 2 dan 4. Maka gen pada urutan ke 2 dan ke 4 akan saling bertukar posisi, sehingga chromosome tersebut setelah dikenai proses mutation akan menjadi A’ {1, 4, 3, 2, 5, 6}. -

Fungsi Inversion Fungsi Inversion adalah fungsi untuk menginverse (membalik) urutan dari beberapa customer dalam sebuah solusi. Fungsi ini dijalankan pada sebuah chromosome. Cara kerja fungsi ini adalah sebagai berikut: pertama didapatkan dua buah titik potong secara acak, kemudian customercustomer yang berada diantara kedua titik tersebut urutan posisinya dibalik.

36 Contoh aplikasinya dapat dibayangkan debagai berikut: andaikan ada sebuah chromosome A {1, 2, 3, 4, 5, 6, 7} yang akan dikenai proses inversion. Diasumsikan kedua titik potong acak yang diperlukan bernilai 3 dan 6, sehingga chromosome tersebut setelah dikenai proses inversion akan menjadi A’ {1, 2, 6, 5, 4, 3, 7}. -

Fungsi Repair Representasi VRP menggunakan chromosome sangat rentan menghasilkan chromosome yang tidak feasible, dikarenakan banyaknya restriksi dan constraint/batasan pada permasalahan VRP. Selain itu penyebaran pemisah rute, yang jumlahnya hanya sebanyak jumlah vehicle, yang tidak merata sering menghasilkan chromosome yang tidak feasible karena penyebaran demand yang tidak merata. Oleh karena itu, digunakan sebuah operator bantuan yang disebut Repair Operator. Operator ini bekerja pada saat aplikasi akan menambahkan sebuah chromosome/solusi hasl proses operator Genetic Algorithm ke dalam populasi, diluar proses initial population generation. Flowchart dari operator repair ini dapat dilihat pada gambar 3.6. Penjelasan dan ilustrasi cara kerja dari operator repair ini adalah sebagai berikut: Diasumsikan ada sebuah chromosome A {1, 2, 0, 3, 4, 5, 6} yang akan dikenai proses reparasi. Misalkan sub-rute kedua {3, 4, 5, 6} diketahui mempunyai demand lebih besar dari sub-rute pertama {1, 2}, dan proses pencarian titik random pada sub-rute kedua menghasilkan index ke 5 (yaitu angka bernilai 4), sehingga proses repair akan mengambil kota 4 dari sub-rute kedua, dan memindahkannya ke akhir sub-rute pertama, sehingga chromosome A setelah proses reparasi akan menjadi A’ {1, 2, 4, 0, 3, 5, 6}. Proses reparasi ini dilakukan setiap kali ada chromosome/ route baru yang akan dimasukkan ke dalam populasi. Jika

37 pada sebuah proses pemasukan chromosome ke dalam populasi diketahui ada sebuah hasil operator GA yang menghasilkan solusi yang tidak feasible, maka solusi/chromosome tersebut akan dikenai proses reparasi chromosome sampai menghasilkan chromosome yang feasible.

Gambar 33.6 Flowchart proses Repair Operator

-

Fungsi Evaluasi Fungsi Evaluasi akan menghasilkan suatu nilai (yang disebut sebagai fitness value) yang dimana dari nilai tersebut bisa diukur kualitas dari suatu chromosome. User permasalahan VRP, kualitas sebuah chromosome (yang

38 mewakili sebuah solusi) dapat dilihat dari total jarak yang harus ditempun pada solusi tersebut. Selain jarak, sebenarnya ada parameter lain yang dapat digunakan sebagai fitness value, yaitu total cost, yang melambangkan biaya yang harus dikeluarkan pada suatu rute. Namun pada aplikasi ini, diasumsikan bahwa total cost yang diperlukan berbanding lurus dengan total distance (semakin jauh jarak tempuh, biaya perjalanan juga semakin mahal), sehingga fitness value dapat diasumsikan sama dengan total jarak pada sebuah rute (chromosome) 3.5

Perancangan Class

Untuk menunjang konsep Genetic Algorithm, maka perlu dibuat rancangan-rancangan class seperti dapat dilihat pada gambar 3.7. Entitas utama terkecil adalah class city dan class vehicle. Class city melambangkan customer dengan property id customer, koordinat x dan koordinat y, serta demand. Titik koordinat ini berguna untuk menghitung jarak antar customer, sedangkan demand merupakan variabel yang menandakan total permintaan barang yang harus diantarkan oleh sebuah vehicle ke customer tersebut. Entitas vehicle mewakili sebuah kendaraan, dimana sebuah vehicle mempunyai properti id dan capacity, yang merupakan daya tampung maksimal dari sebuah vehicle. Selain kedua class tersebut, ada juga class route, yang mewakili sebuah rute/sub-rute. Route mempunyai properti daftar city yang ada pada route tersebut, dan totalDistance yang melambangkan jarak tempuh total dari rute/sub-rute tersebut, serta totalDemand yang melambangkan permintaan total dari rute/sub-rute tersebut.

39 Class VRPInput merupakan class yang menampung parameter-parameter inputan dari user, termasuk didalamnya daftar vehicle dan daftar city yang dibaca dari file inputan. Parameter-parameter yang disimpan dalam class ini termasuk id dari depot, penanda iterasi sebelum terjadinya migrasi, ukuran populasi, jumlah iterasi total, kemungkinan terjadinya crossover, kemungkinan terjadinya mutasi, dan kemungkinan terjadinya inversi. Pada class ini terdapat sebuah fungsi untuk membaca file inputan, dan memvalidasi file inputan tersebut. Class Population merupakan class utama, yang menampung populasi GA. Class ini mengambil referensi dari class VRPInput untuk mendapatkan daftar vehicle dan daftar city. Populasi disimpan dalam sebuah List bertipe Route. Pada classclass ini terdapat fungsi-fungsi utama populasi, seperti fungsi untuk menghasilkan random route, menggenerate initial population, mengecek feasibilitas suatu rute (berdasarkan informasi dari class VRPInput), mendapatkan sub-rute dari sebuah rute (dengan memecah rute tersebut berdasarkan pemisah), fungsi migrasi antar pulau/island, dan yang terpenting adalah fungsi utama yaitu fungsi iterasi tiap generasi. Selain class-class utama tersebut, terdapat pula dua class pendukung, yaitu class DistanceMatrix dan VRPOperators. Class DistanceMatrix berisi matriks yang mengandung informasi jarak antar tiap kota dengan kota-lainnya. Class ini juga menyimpan informasi id dari depot, untuk menghitung jarak tiap sub-rute. Informasi jarak ini didapatkan dari koordinat masing-masing kota yang diambil ketika proses pembacaan file input. Class ini bertujuan untuk mengurangi biaya komputasi yang diperlukan ketika menghitung jarak antar kota sehingga penghitungan jarak cukup dilakukan sekali saja di awal. Sedangkan class VRPOperator hanya merupakan class tambahan yang berisi fungsi-fungsi operator Genetic Algorithm seperti Roulette Wheel Selection, Mutation function, dan Crossover function.

40 DistanceMatrix

VRPInput + + + + + +

DepotID NumberOfIterationBetweenMigration NumberOfPopulation NumberOfIteration MutationProbability CrossoverProbability

: int : int : int : int : float : float

+ + + + +

VRPInput () CheckFeasible () FindCityByID (int cityID) ReadInputFile (std::string inputPath) NormalizeLine (std::string inputLine)

: void : bool : City : VRPInput : std::string

1..1

1..1

+ distances : float[] + costs : float[] + DepotID : int

+ + + 1..1 + + + 0..1

DistanceMatrix () DistanceMatrix (int cityCount) SetDistance (int inputFrom, int inputTo GetDistance (int inputFrom, int inputT SetCost (int inputFrom, int inputTo, flo GetCost (int inputFrom, int inputTo) Vehicle

+ id : int + capacity : float

0..1 0..*

+ Vehicle () : void + Vehicle (float capacity) : void + Vehicle (float capacity, int id) : void City

0..* 1..1 VRPPopulation + + + +

IterationCounter MutationCounter CrossoverCounter rand

+ + + + + + + + + + + + + + + + + + + +

VRPPopulation (VRPInput vrp) CreateRandomRoute () CheckRouteFeasibility (Route routeToCheck) CountTotalDistance (Route routeToCount) CountTotalSubDistance (Route routeToCount) CountTotalDemand (Route routeToCount) GetSubRoutes (Route routeToProcess) AddRoute (char routeString[]) AddRoute (Route routeToAdd) AddRoute (Route routeToAdd, bool withCheckFeasible) GenerateInitialPopulation (int ammountToGenerate) GenerateInitialPopulation () DoIteration (int numberOfIteration) DoIteration () ProcessMutation () ProcessCrossover () RemoveInfeasibleRoutes () RemoveWorstRoutes () CheckAndRetreiveMigration () CheckAndProcessMigration ()

+ + + +

id x y demand

: int : int : int : float

+ City (int inputID, int inputX, int inputY, + City ()

: int : int : int : float : int : Route : bool : void : void : void : Route[] : bool : bool : bool : void : void : void : void : void : void : void : void : void : void

*

* Route

+ totalDemand : float + totalDistance : float + + + 0..* + 0..1 + +

Route (City cities[]) Route () AddCity (City city[]) Normalize () Denormalize () ToString ()

: void : void : bool : void : void : std::string

VRPOperators

+ + 1..1 + +

1..1

VRPOperators () DoRoulette (Route population[]) DoMutation (Route chromosome) DoCrossover (Route ch1, Route ch2)

Gambar 33.7 Desain Class Diagram

41 3.6

Perancangan Aliran Data

Secara umum, DFD level 0 dari aplikasi ini dapat dilihat pada gambar 3.8. Penjalasan umum DFD level 0 ini adalah sebagai berikut: Pertama user memasukkan inputan data awal melalui dua buah file input yang masih-masing berisi data awal VRP dan parameter-parameter Genetic Algorithm. Setelah itu aplikasi akan melakukan proses penyelesaian VRP dengan Algoritma Genetic Algorithm secara Paralel, yang akan menghasilkan output Rute Optimal, dan mengembalikannya kembali pada user. Pengguna

1

Masukan data awal VRP

Proses Penyelesaian VRP dengan Algoritma Genetika Secara Paralel

Rute Optimal

+ Pengguna

Gambar 33.8 Desain DFD level 0

Breakdown pada DFD level 0 ini akan menghasilkan DVD level 1 yang dapat dilihat pada gambar 3.9. Seperti yang sudah dijelaskan pada DFD level 0, proses diawali dengan membaca masukan data awal VRP dan GA melalui file input oleh user, kemudian dilanjutkan dengan inisialisasi lingkungan paralel dengan library MPI. Setelah itu baru dilakukan pencarian solusi optimal menggunakan algoritma Genetic Algorithm secara paralel, yang akan menghasilkan solusi optimal. Hasil dari solusi optimal tersebut akan dikembalikan dan ditampilkan kembali kepada user.

42

Pengguna

Pengguna

Masukan data awal VRP

1 Baca Masukan data awal VRP

Data awal VRP

2 Inisialisasi Lingkungan Parallel dengan MPI

Data awal VRP

3 Solusi Genetic Algorithm

Pencarian Solusi dengan Genetic Algorithm secara Paralel

+ Rute Optimal

Solusi Optimal

4 Tampilkan Solusi yang ditemukan

Rute Optimal

Gambar 33.9 Desain DFD level 1

Desain DFD level 1 pada gambar 3.9 dapat di-breakdown pada proses pencarian solusi dengan Genetic Algorithm, sehingga menjadi DFD level 2 seperti terlihat pada gambar 3.10. DFD ini

43 menjelaskan proses operator-operator GA yang terdapat pada aplikasi ini. 1 Generate Initial Population

Initial Population

Initial Population Initial Population

2 Genetic Algorithm

+ Optimized Population 5 Stopping Condition

Solusi Genetic Algorithm

Rute Optimal

Gambar 33.10 Desain DFD level 0

Pada DFD level 2 ini terlihat bahwa proses Genetic Algorithm terdiri dari proses Generate Initial Population di awal, yang bertujuan menghasilkan initial population yang kemudian diproses dengan Genetic Algorithm. Proses Genetic Algorithm sendiri, seperti yang sudah disebutkan pada bagian sebelumnya, terdiri dari proses CrossOver, Mutation, dan Inversion. Pada akhir iterasi, dilakukan proses yang disebut Remove Worst Ranked

44 Population Members, dimana proses ini bertujuan untuk menjaga ukuran populasi GA agar tetap sesuai dengan jumlah populasi awal, dan meningkatkan kekuatan proses seleksi alam dan kompetisi antar chromosome yang terjadi. Proses Genetic Algorithm ini kemudian diulangi terus-menerus sampai memenuhi stopping condition, yang berupa banyaknya iterasi/generasi yang diinputkan oleh user. Pada akhir proses, setelah memenuhi stopping condition, dilakukan proses yang disebut Remove Infeasible Routes, untuk menghapus rute-rute yang tidak feasible, sehingga populasi hanya akan terdiri dari rute-rute yang feasible saja. 3.7

Perancangan Konsep Paralel Genetic Algorithm

Aplikasi VRP Solver ini menggunakan konsep paralel Island Model, dimana Populasi total dipecah menjadi beberapa sub-populasi yang berdiri sendiri-sendiri dan saling independen. Setiap sub-populasi tinggal pada sebuah pulau, yang pada terminologi paralel, sebuah pulau merupakan sebuah prosesor. Proses kerja dari Island Model ini adalah sebagai berikut: Pada awal setiap iterasi, setiap pulau menerima kiriman chromosome yang ditujukan kepada dirinya (jika ada), kemudian menggabungkannya dengan populasinya sendiri, baru setelah itu pulau tersebut memproses populasi miliknya dengan Genetic Algorithm seperti biasa. Setelah proses Genetic Algorithm selesai, pada akhir iterasi sebelum berlanjut ke iterasi berikutnya, setiap pulau akan mengirimkan sebuah solusi terbaiknya ke pulau tetangganya, melalui algoritma sirkular seperti yang sudah dijelaskan pada bab sebelumnya. Seperti yang telah dijelaskan pada awal bab ini, ada dua tipe komputer yang digunakan dalam aplikasi ini, master dan prosesor. Komputer master hanya bertugas menunggu dan mengumpulkan solusi-solusi dari tiap prosesor, sedangkan setiap

45 prosesor memproses dan menyelesaikan permasalahan tiap VRP menggunakan algoritma GA secara paralel dan independen, dimana pada setiap jangka waktu sekali sebuah prosesor saling bertukar solusi terbaiknya dengan prosesor lain. Other Island

Other Island

Island's Best Population

1 Generate Initial Population

Island's Best Population

Initial Population 3 Migrate Best Population Member to Neighbor Island

Initial Population

Initial Population

4 Receive Neighbor Island's Best Population

Mized Optimized Population

Optimized Population Optimized Population : 1

Optimized Population : 2 2 Genetic Algorithm

Optimized Population

Mixed Optimized Population

+ Optimized Population

5 Stopping Condition Optimized Population

Solusi Genetic Algorithm

Rute Optimal

Gambar 33.11 Desain Paralel Genetic Algotrithm menggunakan Island Model

46 Untuk proses komunikasi pada tahapan migrasi, digunakan format tertentu untuk mengirim rute antar prosesor. Karena adanya keterbatasan tipe data yang dapat dikirim antar prosesor dalam lingkungan MPI, maka agar proses komunikasi dapat berjalan lancar, informasi yang akan dikirim dirubah terlebih dahulu ke format string, sehingga dapat dikirim menggunakan MPI. Karena setiap prosesor mempunyai informasi data masukan VRP yang sama, semua prosesor mempunyai informasi daftar kota, daftar jarak, dan daftar demand yang sama persis, sehingga data yang dikirim cukup berupa informasi rute saja. Sebagai contoh, jika ada chromosome A {1, 2, 3, 4, 5} hendak dikirim ke prosesor lain, maka chromosome tersebut terlebih dahulu dikodekan menjadi string “1,2,3,4,5” menggunakan pemisah tanda koma antar setiap kota, baru kemudian dikirim ke prosesor lain. Prosesor yang menerimanya kemudian akan merubah string tersebut menjadi chromosome dan menggabungkannya ke dalam populasi miliknya. 3.8

Perancangan Format File Input

Aplikasi VRP Solver ini tidak menggunakan User Interface sebagai media interaksi dengan user, dikarenakan sifat aplikasi yang menggunakan MPI, sehingga untuk menjalankannya dibutuhkan middleware dan menyulitkan untuk pengadaan sebuah User Interface/UI. Karena tidak menggunakan UI sebagai sarana interaksi dengan user, maka digunakan file input untuk memasukkan datadata permasalahan VRP dan parameter GA. Untuk memudahkan user memasukkan inputan VRP, maka aplikasi ini menggunakan format inputan VRP sesuai dengan standard VRP. 3.8.1

File Input Parameter Permasalahan VRP

Ada standard industri untuk menyimpan data permasalahan Vehicle Routing dalam sebuah file input, terlepas

47 dari tipe permasalahan Vehicle Routing tersebut. Pada sub-bab ini akan dijelaskan tentang spesifikasi format file input VRP yang digunakan, yang disesuaikan dengan tipe heterogeneous VRP yang digunakan dalam aplikasi. Daftar kata kunci pada file input instance VRP beserta penjelasannya dapat dilihat pada tabel 3.1. Tabel 3.1 Daftar kata kunci file input VRP

Kata Kunci

Jenis Variabel

Keterangan Syntax

NAME

{string}

Nama dari instance VRP tersebut, tidak digunakan termasuk dalam inti permasalahan.

COMMENT

{string}

Deskripsi dari instance VRP tersebut, tidak digunakan termasuk dalam inti permasalahan.

TYPE

{enum}

Menyatakan jenis dari permasalahan VRP tersebut. Isi variabel ini dapat berupa CVRP (Capacitated VRP), PDP (Pickup and Delivery Problem), dan sebagainya. Pada aplikasi ini digunakan instance VRP bertipe CVRP.

DIMENSION

{int}

Menyatakan banyaknya customer/ city dalam instance tersebut, termasuk depot.

EDGE_ WEIGHT_ TYPE

{enum}

Menyatakan jenis penulisan nodenode dalam instance tersebut. Beberapa pilihan yang tersedia antara lain adalah EUC_2D (Euclidian),

MAN_2D (Manhattan Mettric),

48

dsb. Pada aplikasi ini digunakan instance VRP bertipe EUD_2D. NUM_ VEHICLES

{int}

Menyatakan banyaknya vehicle/ kendaraan dalam instance VRP tersebut.

VEHICLE_ CAPACITY_ SECTION

{id} {real}

Kata kunci ini menyatakan bahwa baris-baris dibawahnya adalah informasi tentang kapasitas dari masing-masing vehicle, sejumlah sesuai dengan nilai dari variabel NUM_VEHICLES.

NODE_ COORD_ SECTION

{id} {x} {y}

Kata kunci ini menyatakan bahwa baris-baris dibawahnya adalah informasi tentang posisi/koordinat dari masing-masing city, sejumlah sesuai dengan nilai dari variabel DIMENSION. Format penulisan koordinat sesuai dengan EDGE_WEIGHT_TYPE, dimana pada aplikasi ini digunakan tipe koordinat euclidian.

DEMAND_ SECTION

{id} {real}

Kata kunci ini menyatakan bahwa baris-baris dibawahnya adalah informasi tentang demand dari masing-masing city, sejumlah sesuai dengan nilai dari variabel DIMENSION.

DEPOT_ SECTION

{int}

Kata kunci ini menyatakan bahwa baris-baris dibawahnya adalah informasi tentang depot. Pada VRP

49 bertipe heterogeneous, hanya digunakan satu buah depot, namun untuk tipe-tipe VRP lainnya, bisa digunakan lebih dari satu depot. Penulisan depot adalah id dari city yang menjadi depot, sesuai dengan nilai dari variabel NODE_COORD_SECTION. EOF

3.8.2

Menyatakan akhir dari file input instance VRP tersebut.

File Input Parameter Genetic Algorithm

Parameter-parameter inputan untuk Genetic Algorithm disimpan dalam sebuah file bernama parameters.txt yang disimpan pada directory yang sama dengan file executable aplikasi. File parameter GA ini berisi informasi probabilitas terjadinya crossover, inversion, maupun mutation. Selain itu file ini juga memuat informasi tentang banyaknya interasi/generasi yang akan dikerjakan oleh GA, sertai jumlah total keseluruhan populasi. Format selengkapnya dari file parameters.txt dapat dilihat pada tabel 3.2. Tabel 3.2 Daftar fungsi-fungsi utama pada MPI

Syntax Parameter

Keterangan Syntax

CROSSOVER_ PROBABILITY

Menyatakan nilai probabilitas dari kemungkinan terjadinya operator crossover. Nilai probabilitas dinyatakan dalam angka desimal yang bernilai antara 0.0 sampai dengan 1.0

INVERSION_

Menyatakan

nilai

probabilitas

dari

50 PROBABILITY

kemungkinan terjadinya operator inversion. Nilai probabilitas dinyatakan dalam angka desimal yang bernilai antara 0.0 sampai dengan 1.0

MUTATION_ PROBABILITY

Menyatakan nilai probabilitas dari kemungkinan terjadinya operator mutation. Nilai probabilitas dinyatakan dalam angka desimal yang bernilai antara 0.0 sampai dengan 1.0

NUMBER_OF_ ITERATION

Menyatakan banyaknya iterasi/generasi yang akan dijalankan oleh Genetic Algorithm. Nilai ini juga menjadi stopping criterion dari Genetic Algorithm yang digunakan pada aplikasi ini.

NUMBER_OF_ POPULATION

Menyatakan banyaknya populasi total secara keseluruhan. Jumlah populasi total ini akan dibagi sama rata ke setiap prosesor yang ada.

NUMBER_OF_ ITERATION_ BETWEEN_ MIGRATION

Satuan yang menyatakan jeda antara tiap sekian iterasi/generasi sebelum melakukan proses migrasi.

BAB 4 IMPLEMENTASI PERANGKAT LUNAK

Pada bab ini akan dibahas mengenai implementasi dari perancangan perangkat lunak yang telah dijabarkan pada bab 3. Pembahasan Implementasi meliputi Implementasi Arsitektur. Bab ini juga membahas mengenai Lingkungan Pembangunan Perangkat Lunak yang menjelaskan spesifikasi perangkat keras dan perangkat lunak yang digunakan dalam pembangunan sistem. 4.1

Lingkungan Pembangunan Perangkat Lunak Aplikasi dikembangkan dalam lingkungan pemrograman

dengan spesifikasi berikut ini : •

Notebook Acer Aspire 5552 NWXMi dengan spesifikasi prosesor Intel Core Duo T2300E 1.66GHz, dan 760 MB RAM.

•

Sistem Operasi Microsoft Windows XP SP 2.

•

Microsoft Visual Studio .NET 2005 sebagai IDE dan compiler.

•

DeinoMPI sebagai middleware untuk menjalankan aplikasi paralel.

•

Power Designer Process Analyst 6 dan Power Designer 11 sebagai modelling tools.

4.2

Implementasi Proses

Berikut adalah penjabaran implementasi dari tiap-tiap proses dari Process Diagram yang terdapat pada bab sebelumnya.

51

52 4.2.1

Implementasi Proses Membaca Data Input VRP

Proses pembacaan data masukan VRP dimulai dengan membuka file masukan. User memasukkan nama file masukan lewat parameter pertama command line ketika menjalankan aplikasi ini. Jika user hanya memasukkan nama file saja, tanpa path lengkap, maka diasumsikan file tersebut berada pada direktori yang sama dengan direktori executable. Sistem kemudian membaca isi file tersebut baris per baris dengan mencocokkkan keyword tiap baris dengan daftar keyword yang digunakan. Jika keyword cocok, maka dilakukan proses sesuai keyword tersebut. Jika keyword tidak ditemukan, maka sistem otomatis melanjutkan ke baris berikutnya. Berikut adalah potongan kode untuk membuka dan membaca file masukan .vrp dan memprosesnya berdasarkan keyword-keyword yang dibutuhkan dalam permasalahan heterogeneous fleet VRP. Pemisah utama adalah tanda titik dua (“:”), sesuai dengan standardisasi file masukan VRP, sedangkan pemisah untuk sub-data (seperti data kota atau kendaraan) menggunakan <spasi>. String^ filePath = gcnew String(argv[1]); if (!filePath->Contains("\\")) filePath = Application::StartupPath + "\\" + inputPath; if (!File::Exists(filePath)) return nullptr; StreamReader^ sr = gcnew StreamReader(filePath); array^ separator = { ':' }; array^ innerSeparator = { ' ' }; do { String^ line = sr->ReadLine();

53 /* kalo sudah sampai pada akhir file, selesai */ if (line == nullptr) break; String^ thisLine = NormalizeLine(line); array<String^>^ splittedLine = thisLine->Split(separator); String^ key = NormalizeLine(splittedLine[0]); if (key == "DIMENSION") { dimension = int::Parse(NormalizeLine(splittedLine[1])); } if (key == "NUM_VEHICLES") { num_vehicles = int::Parse(NormalizeLine(splittedLine[1])); } if (key == "NODE_COORD_SECTION") { for (int i = 0; i < dimension; i++) { String^ otherLine = NormalizeLine(sr->ReadLine()); array<String^>^ splittedInnerLine = otherLine->Split(innerSeparator); vrpInput->Cities->Add( gcnew City(int::Parse(splittedInnerLine[0]), int::Parse(splittedInnerLine[1]), int::Parse(splittedInnerLine[2]), 0)); } } if (key == "DEMAND_SECTION") { for (int i = 0; i < dimension; i++) { String^ otherLine = NormalizeLine(sr->ReadLine()); array<String^>^ splittedInnerLine = otherLine->Split(innerSeparator); City^ city = vrpInput->FindCityByID( int::Parse(splittedInnerLine[0]));

54 city->demand = int::Parse(splittedInnerLine[1]); } } if (key == "VEHICLE_CAPACITY_SECTION") { for (int i = 0; i < num_vehicles; i++) { String^ otherLine = NormalizeLine(sr->ReadLine()); array<String^>^ splittedInnerLine = otherLine->Split(innerSeparator); vrpInput->Vehicles->Add( gcnew Vehicle( int::Parse(splittedInnerLine[1]), int::Parse(splittedInnerLine[0]))); } } if (key == "DEPOT_SECTION") { String^ otherLine = NormalizeLine(sr->ReadLine()); vrpInput->DepotID = int::Parse(otherLine); } } while (true);

Setelah membaca data masukan permasalahan VRP, maka kemudian dilakukan proses penghitungan jarak antar tiap kota yang ada. Penghitungan jarak diselesaikan dengan cara cartesian, yaitu dengan mencari akar pangkat dua dari penjumlahan kuadrat selisih kedua titik pada sumbu X dan kuadrat selisih kedua titik pada sumbu Y. Hasil perhitungan kemudian di-cast ke integer. Hasilnya disimpan dalam sebuah class khusus untuk menampuk matriks jarak. Berikut adalah potongan kode proses penghitungan jarak antar tiap kota. DistanceMatrix^ matrix = gcnew DistanceMatrix(vrpInput->Cities->Count + 1); matrix->DepotID = vrpInput->DepotID; for (int i = 0; i < vrpInput->Cities->Count; i++) {

55 for (int j = 0; j < vrpInput->Cities->Count; j++) { int distance = 0; if (i != j) { int distanceX = vrpInput->Cities[j]->x - vrpInput->Cities[i]->x; int distanceY = vrpInput->Cities[j]->y - vrpInput->Cities[i]->y; distance = (int)Math::Floor(Math::Sqrt( distanceX * distanceX + distanceY * distanceY) + 0.5); } matrix->SetDistance( vrpInput->Cities[i]->id, vrpInput->Cities[j]->id, distance); } }

Langkah terakhir dalam proses pembacaan data masukan ini adalah membaca data masukan untuk parameter GA. Data masukan berupa parameter GA disimpan dalam sebuah file khusus yang bernama parameters.txt. File ini harus diletakkan dalam direktori yang sama dengan file executable utama aplikasi. File masukan data parameter ini menggunakan pemisah berupa <spasi> antar keyword dan nilainya. Berikut adalah potongan kode untuk membuka file parameters.txt dan membaca isinya berdasarkan keyword-keyword parameter GA. String^ paramPath = Application::StartupPath + "\\parameters.txt"; StreamReader^ paramSR = gcnew StreamReader(paramPath); do { String^ curLine = paramSR->ReadLine(); if (curLine == nullptr) break;

56

String^ thisLine = NormalizeLine(curLine); array<String^>^ splittedLine = thisLine->Split(innerSeparator); if (NormalizeLine(splittedLine[0]) == "MUTATION_PROBABILITY") { vrpInput->MutationProbability = Double::Parse(NormalizeLine(splittedLine[1])); } else if (NormalizeLine(splittedLine[0]) == "INVERSION_PROBABILITY") { vrpInput->InversionProbability = Double::Parse(NormalizeLine(splittedLine[1])); } else if (NormalizeLine(splittedLine[0]) == "CROSSOVER_PROBABILITY") { vrpInput->CrossoverProbability = Double::Parse(NormalizeLine(splittedLine[1])); } else if (NormalizeLine(splittedLine[0]) == "NUMBER_OF_ITERATION") { vrpInput->NumberOfIteration = Int32::Parse(NormalizeLine(splittedLine[1])); } else if (NormalizeLine(splittedLine[0]) == "NUMBER_OF_POPULATION") { vrpInput->NumberOfPopulation = Int32::Parse(NormalizeLine(splittedLine[1])); } else if (NormalizeLine(splittedLine[0]) == "NUMBER_OF_ITERATION_BETWEEN_MIGRATION") { vrpInput->NumberOfIterationBetweenMigration = Int32::Parse(NormalizeLine(splittedLine[1])); } } while(true);

57 Untuk menghindari adanya kesalahan penulisan dari user pada file masukan VRP dan GA, maka sebelum membaca tiap baris, dilakukan proses normalisasi baris, yaitu dengan mengganti semua spasi ganda dengan spasi tunggal. Proses normalisasi tersebut dilakukan dengan fungsi dibawah ini. String^ NormalizeLine(String^ inputLine) { String^ outputLine = inputLine->Trim(); outputLine = RegularExpressions::Regex::Replace( outputLine, "\s+", " "); return outputLine; }

Data-data hasil pembacaan file masukan VRP dan GA diatas semuanya disimpan dalam class VRPInput, sehingga class-class yang lain jika membutuhkan data tersebut, dapat mengaksesnya lewat class VRPInput. Sebelum melanjutkan ke proses berikutnya, terlebih dahulu dilakukan proses pengecekan data permasalahan VRP yang dimasukkan oleh user tersebut. Untuk itu digunakan fungsi pada potongan kode dibawah ini Boolean CheckFeasible() { /* pastikan jumlah kota > 0 */ if (this->Cities->Count == 0) return false; /* pastikan jumlah kendaraan > 0 */ if (this->Vehicles->Count == 0) return false; /* pastikan matriks jarak telah dihitung */ if (this->Distances == nullptr) return false; int totalDemand = 0;

58 int biggestDemand = 0; /* menghitung jumlah kota, total demand, dan biggest demand dari semua city */ for (int i = 0; i < this->Cities->Count; i++) { totalDemand += this->Cities[i]->demand; if (this->Cities[i]->demand > biggestDemand) biggestDemand = this->Cities[i]->demand; } int totalCapacity = 0; int biggestCapacity = 0; /* menghitung total capacity dan capacity terbesar dari semua vehicle */ for (int i = 0; i < this->Vehicles->Count; i++) { totalCapacity += this->Vehicles[i]->Capacity; if (this->Vehicles[i]->Capacity > biggestCapacity) biggestCapacity = this->Vehicles[i]->Capacity; } /* pastikan total demand tidak lebih besar dari total kapasitas kendaraan */ if (totalDemand > totalCapacity) return false; /* pastikan demand terbesar tidak lebih besar dari kapasitas kendaraan terbesar */ if (biggestDemand > biggestCapacity) return false; return true; }

Penjelasan proses fungsi diatas dapat dilihat pada komentar yang terdapat pada masing-masing statement. Setelah melalui tahapan ini, diharapkan variabel permasalahan VRP yang dimasukkan user benar-benar valid dan dapat dicari penyelesaiannya.

59 4.2.2

Implementasi Proses Inisialisasi MPI

Proses inisialisasi lingungan paralel dimulai dengan inisialisasi variabel-variabel yang dibutuhkan oleh fungsi-fungsi MPI dan variabel buffer untuk menyimpan hasil proses komunikasi. Karena pada proses komunikasi nantinya, yang dikirim adalah informasi rute, maka untuk mengantisipasi permasalahan-permasalahan VRP yang mempunyai jumlah kota banyak, digunakan variabel buffer untuk komunikasi sebanyak 1000 karakter. Berikut adalah potongan kode inisialisasi variabelvariabel MPI. int my_rank; int p; int tag = 0; char message[1000]; MPI_Status status; MPI_Request request;

/* /* /* /* /* /*

rank of process */ number of processes */ tag for messages */ storage for message */ return status for receive */ return status for receive */

Setelah itu dilanjutkan dengan proses inisialisasi lingkungan paralel MPI. Potongan kode berikut menunjukkan pemanggilan fungsi inisialisasi MPI. MPI_Init(&argc, (wchar_t***)&argv); MPI_Comm_rank(MPI_COMM_WORLD, &my_rank); MPI_Comm_size(MPI_COMM_WORLD, &p);

Setelah dilakukan fungsi MPI_Init diatas, maka aplikasi telah siap berjalan dalam lingkungan paralel. 4.2.3

Implementasi Proses Initial Population Generation

Setelah proses inisialisasi lingkungan paralel MPI selesai, maka tahapan selanjutnya adalah proses penyelesaian permasalahan VRP menggunakan Genetic Algorithm. Tahap pertama dalam proses ini adalah tahap inisialisasi populasi. Potongan kode dibawah memperlihatkan proses tersebut. void GenerateInitialPopulation(int ammountToGenerate) { /* to prevent infinite loops */

60 int numberOfTries = 0; Route^ newRoute; /* Perkirakan kemungkinan infinitie looping adalah lebih dari 100 kali jumlah Population yang diinginkan */ while (numberOfTries++ < ammountToGenerate * 100 && this->Routes->Count < ammountToGenerate) { newRoute = CreateRandomRoute(); /* kalo rute baru gak feasible, masih ada kemungkinan 1% untuk tetap dimasukkan dalam populasi */ if (!AddRoute(newRoute)) { Random^ rand = gcnew Random(); if (rand->NextDouble() < 0.01) AddRoute(newRoute, false); } } }

Inisialisasi populasi dilakukan dengan men-generate rute acak sejumlah sesuai dengan ukuran populasi. Rute acak yang dihasilkan tidak selalu merupakan rute yang feasible, karena itu untuk menjaga agar populasi pada search space merupakan solusi-solusi yang berkualitas, hanya rute-rute yang feasible yang akan dimasukkan dalam populasi. Namun karena sedikit adanya solusi-solusi infeasible pada search space dapat membantu GA mendapatkan hasil yang lebih optimal, dengan tidak mengurangi kualitas search space secara keseluruhan, maka terdapat 1% kemungkinan bagi rute acak hasil proses generate yang tidak feasible untuk tetap dapat dimasukkan ke dalam populasi. Detail proses generate rute acak dapat dilihat seperti pada potongan kode dibawah ini. Route^ CreateRandomRoute() { Route^ RandomRoute = gcnew Route(); List^ remainingCities = gcnew List();

61 int addedDepot = 0; /* buat daftar kota yang akan di random */ for (int i = 0; i < this->VRPProblem->Cities->Count; i++) { if (this->VRPProblem->Cities[i]->id != this->VRPProblem->DepotID) { remainingCities->Add(VRPProblem->Cities[i]); /* tambahkan kota 0 sbg penanda antar route */ if ((i % (this->VRPProblem->Cities->Count / this->VRPProblem->Vehicles->Count) == 0) && addedDepot < (this->VRPProblem->Vehicles->Count - 1)) { remainingCities->Add(gcnew City(0, 0, 0, 0)); addedDepot++; } } } while (remainingCities->Count != 0) { Random^ rand = gcnew Random(); int r = rand->Next(remainingCities->Count); RandomRoute->AddCity(remainingCities[r]); remainingCities->RemoveAt(r); } return RandomRoute; }

Pada proses tersebut, pertama kita buat daftar kota yang ada pada permasalahan VRP dalam sebuah variabel yang bernama remainingCities, pada waktu yang sama kita sisipkan kotakota dengan ID 0 (yang menandakan depot) secara merata ke dalam daftar kota pada remainingCities. Setelah itu baru daftar kota ini diacak, hasilnya merupakan rute acak yang siap diproses.

62 Sebelumnya telah dijelaskan bahwa rute acak yang dihasilkan tidak selalu merupakan rute yang feasible. Karena kemungkinan dihasilkannya rute yang tidak feasible pada kenyataannya jauh lebih besar daripada dihasilkannya rute yang feasible (karena sifat dari GA yang murni random), maka digunakan operator GA tambahan khusus untuk permasalahan TSP/VRP yang disebut Repair Operator. Ketika ditemukan sebuah rute yang ternyata tidak feasible, maka operator rute tersebut akan dikenai operator ini, kemudian diperiksa kembali apakah feasible atau tidak. Jika ternyata masih tetap tidak feasible, maka operator ini akan terus dijalankan pada rute tersebut sampai sejumlah kota yang ada. Jika tetap tidak feasible juga, maka rute tersebut akan terkena proses yang sudah sebelumnya, dimana diberi kemungkinan 1% untuk tetap masuk ke dalam populasi. Jika rute tersebut tidak termasuk ke dalam yang 1%, maka rute tersebut tidak dimasukkan ke dalam populasi. Operator tambahan ini terdapat dalam fungsi AddRoute. Selain operator tambahan tersebut, fungsi AddRoute juga berperan untuk memeriksa feasible atau tidaknya suatu rute, lalu menghitung total demand dan total distance dimana total distance ini merupakah nilai evaluasi dari solusi tersebut, dan ada atau tidak adanya rute tersebut pada populasi. Ketika sebuah rute dimasukkan melalui fungsi AddRoute, rute tersebut otomatis akan diurutkan berdasarkan fitness value-nya, dimana fitness value tersebut sama dengan total distance dari rute tersebut. Potongan kode dibawah menerangkan tentang fungsi AddRoute tersebut. bool AddRoute(Route^ routeToAdd, bool withCheck) { if (routeToAdd == nullptr) return false; if (withCheck) {

63 if (!CheckRouteFeasibility(routeToAdd)) { /* kalo tidak feasible, coba repair sampe feasible atau maksimal sebanyak jumlah kota */ int counter = 0; do { RepairRoute(routeToAdd); counter++; } while (!CheckRouteFeasibility(routeToAdd) && counter < this->VRPProblem->Cities->Count); /* kalo ttp tdk feasible, yo wis dibuwak ae */ if (!CheckRouteFeasibility(routeToAdd)) return false; } } CountTotalDemand(routeToAdd); CountTotalDistance(routeToAdd); if (this->Routes->Count == 0) { this->Routes->Add(routeToAdd); return true; } else { if (this->Routes->Contains(routeToAdd)) return false; int index = this->Routes->BinarySearch(routeToAdd, rComparer); if (index >= 0) // Item was found this->Routes->Insert(index, routeToAdd); else this->Routes->Insert(~index, routeToAdd); return true; } }

64 Fungsi AddRoute diatas mempunyai kemampuan untuk mengecek apakah rute yang dimasukkan telah ada pada populasi atau belum. Pengecekan tersebut dilakukan dengan meng-override operator ekualitas pada class Route. bool operator ==(Route^ r1, Route^ r2) { if (ReferenceEquals(r1, nullptr) || ReferenceEquals(r2, nullptr)) return false; if (ReferenceEquals(r1, r2)) return true; if (r1->Cities->Count != r2->Cities->Count) return false; for (int i = 0; i < r1->Cities->Count; i++) { if (!r1->Cities[i]->id.Equals(r2->Cities[i]->id)) return false; } return true; }

Feasible atau tidak nya suatu rute dapat dilihat dengan cara memeriksa apakah apakah total demand pada tiap rute tidak melebihi kapasitas kendaraan yang ditugaskan pada rute tersebut. Implementasi proses tersebut dapat dilihat pada kode dibawah. bool CheckRouteFeasibility(Route^ routeToCheck) { List^ subRoutes = GetSubRoutes(routeToCheck); if (subRoutes == nullptr) return false; int curVehicle = 0; for (int i=0; i < this->VRPProblem->Vehicles->Count; i++)

65 { if (subRoutes[i]->TotalDemand > this->VRPProblem->Vehicles[i]->Capacity) return false; } return true; }

Sebelumnya telah diperkenalkan tentang adanya proses Repair Operator. Proses ini merupakan operator tambahan GA khusus untuk permasalahan TSP/VRP. Cara kerja operator ini adalah mengambil sebuah kota secara acak pada rute dengan demand paling banyak, kemudian dimasukkan secara acak juga ke rute dengan demand paling sedikit. Proses reparasi ini dapat dilihat pada potongan kode dibawah. void RepairRoute(Route^ routeToRepair) { List^ subRoutes = GetSubRoutes(routeToRepair); City^ temp = nullptr; int bebanTerbanyak = 0; int bebanTersedikit = 0; for(int i = 0; i < subRoutes->Count; i++) { /* cari subRoute dengan beban terbanyak */ if (subRoutes[i]->TotalDemand > subRoutes[bebanTerbanyak]->TotalDemand) bebanTerbanyak = i; /* cari subRoute dengan beban tersedikit */ if (subRoutes[i]->TotalDemand < subRoutes[bebanTersedikit]->TotalDemand) bebanTersedikit = i; } /* cari batas bawah dan batas atas array pada rute dengan beban terbanyak */ int rangeTerbanyak1 = 0; int rangeTerbanyak2 = 0;

66 for (int i = 0; i < bebanTerbanyak; i++) { rangeTerbanyak1+=subRoutes[i]->Cities->Count + 1; rangeTerbanyak2=rangeTerbanyak1 + subRoutes[bebanTerbanyak]->Cities->Count - 1; } /* cari batas bawah dan batas atas array pada rute dengan beban tersedikit */ int rangeTersedikit1 = 0; int rangeTersedikit2 = 0; for (int i = 0; i < bebanTersedikit; i++) { rangeTersedikit1+=subRoutes[i]->Cities->Count + 1; rangeTersedikit2=rangeTersedikit1 + subRoutes[bebanTersedikit]->Cities->Count - 1; } /* ambil satu customer secara acak dari rute dengan beban terbanyak, lalu tambahkan secara acak ke rute dengan beban tersedikit */ Random^ rand = gcnew Random(); int indexToMove = rand->Next(rangeTerbanyak1, rangeTerbanyak2); temp = routeToRepair->Cities[indexToMove]; routeToRepair->Cities->RemoveAt(indexToMove);

routeToRepair->Cities->Insert( rangeTersedikit2, temp); }

4.2.4

Implementasi Proses Iterasi Genetic Algorithm

Setelah tahapan generate initial population selesai dan populasi telah terisi, maka selanjutnya populasi tersebut akan di proses dengan operator-operator Genetic Algorithm. Algoritma GA akan mengerjakan opearsi-operasi GA tersebut sejumlah seusai dengan nilai total iterasi/generasi yang dimasukkan oleh user. Proses utama GA ini dapat dilihat pada potongan kode dibawah.

67 void DoIteration(int numberOfIteration) { for (int i = 0; i < numberOfIteration; i++) { CheckAndRetreiveMigration(); ProcessCrossover(); ProcessMutation(); ProcessInversion(); RemoveWorstRoutes(); CheckAndProcessMigration(); } RemoveInfeasibleRoutes(); }

Proses iterasi diawali dengan memeriksa apakah ada masukan chromosome dari prosesor lain. Jika ada, chromosome tersebut akan diproses terlebih dahulu sebelum dilanjutkan dengan proses berikutnya. Setelah itu populasi akan diproses dengan operator-operator dengan urutan sebagai berikut: CrossOver, Mutation, lalu Inversion. Jika setelah melalui proses tersebut ukuran populasi melebihi kapasitas populasi yang dimasukkan oleh user, maka chromosome-chromosome yang berada pada peringkat bawah melebihi kapasitas populasi akan dihapus. Implementasi proses penghapusan ini dapat dilihat pada potongan kode dibawah ini. void RemoveWorstRoutes() { if (this->Routes->Count > this->VRPProblem->NumberOfPopulation) { int ammountToRemove = this->Routes->Count – this->VRPProblem->NumberOfPopulation; this->Routes->RemoveRange( this->VRPProblem->NumberOfPopulation, ammountToRemove); }

68 }

Setelah proses operasi-operasi GA selesai, maka sebuah prosesor kemudian akan mengirim chromosome terbaiknya ke pulau lain. Begitu seterusnya sampai sejumlah iterasi/generasi yang dimasukkan user. Setelah proses iterasi selesai, dilakukan proses pembersihan untuk memastikan hanya chromosomechromosome yang feasible yang berada pada populasi akhir. Implementasi proses pembersihan chromosome tersebut dapat dilihat pada potongan kode dibawah. void RemoveInfeasibleRoutes() { int i = 0; while (i < this->Routes->Count) { if (!CheckRouteFeasibility(this->Routes[i])) { this->Routes->RemoveAt(i); i--; } i++; } }

4.2.5

Implementasi Proses Selection

Proses Selection merupakan proses untuk mendapatkan sebuah chromosome secara acak berdasarkan nilai fitness valuenya untuk kemudian dikenai proses operasi GA berikutnya. Proses selection yang digunakan dalam aplikasi ini adalah Roulette Wheel Selection. Implementasi proses Roulette Wheel Selection ini dapat dilihat pada potongan kode dibawah. int DoRoulette(List^ population) { Random^ rand = gcnew Random(); int maxDistance =

69 population[population->Count - 1]->TotalDistance; maxDistance++; int sumOfEvaluations = 0; for (int i = 0; i < population->Count; i++) { sumOfEvaluations += (maxDistance - population[i]->TotalDistance); } double f = sumOfEvaluations * rand->NextDouble(); int i; for (i = 0; i < population->Count; i++) { if (f<(maxDistance-population[i]->TotalDistance)) break; f -= (maxDistance - population[i]->TotalDistance); } return i; }

4.2.6

Implementasi Proses CrossOver

Proses crossover merupakan proses utama dalam GA, dimana proses ini normalnya mempunyai probabilitas yang paling besar diantara operator-operator GA lainnya. Proses ini memerlukan dua chromosome yang didapatkan melalui proses selection, kemudian oeprasi crossover akan dijalankan pada kedua chromosome tersebut, yang akan menghasilkan dua chromosome baru yang kemudian dimasukkan ke dalam populasi. Proses crossover dapat dilihat pada potongan kode dibawah ini. void VRPPopulation::ProcessCrossover() { if (this->Routes->Count < 2) return; Random^ rand = gcnew Random(); if (rand->NextDouble() <=

70 this->VRPProblem->CrossoverProbability) { int p1 = 0, p2 = 0; List^ crossedRoutes = nullptr; /* perform selection */ do { p1 = Operators->DoRoulette(this->Routes); p2 = Operators->DoRoulette(this->Routes); } while (p1 == p2); crossedRoutes = Operators->DoCrossover(this->Routes[p1], this->Routes[p2]); AddRoute(crossedRoutes[0]); AddRoute(crossedRoutes[1]); } }

Sedangkan proses operasi crossover-nya dapat dilihat pada potongan kode dibawah ini. List^ DoCrossover(Route^ ch1, Route^ ch2) { ch1->Normalize(); ch2->Normalize(); List^ result = gcnew List(); result->Add(gcnew Route()); result->Add(gcnew Route()); Random^ rand = gcnew Random(); int pivot = (int)(ch1->Cities->Count / 2); int range = (int)(ch1->Cities->Count * 0.25); int partition = rand->Next(pivot - range, pivot + range); /* built the first portion of the crossed route */ for (int i = 0; i < partition; i++) { result[0]->AddCity(ch1->Cities[i]);

71 result[1]->AddCity(ch2->Cities[i]); } /* * AddCity function already include routine to * check repetitive cities, * so we can just call the function */ for (int j = 0; j < ch1->Cities->Count; j++) { result[0]->AddCity(ch2->Cities[j]); result[1]->AddCity(ch1->Cities[j]); } ch1->Denormalize(); ch2->Denormalize(); result[0]->Denormalize(); result[1]->Denormalize(); return result; }

Pada proses crossover ini, pertama dicari terlebih dahulu nilai pivot yang merupakan suatu titik untuk menyilangkan kedua chromosome tersebut. Nilai titik pivot ini didapatkan secara acak, namun disesuaikan dan dibuat agar tidak terlalu jauh dari titik tengah chromosome. Setelah nilai pivot didapatkan, kemudian kedua chromosome tersebut saling disilangkan pada titik pivot tersebut, sesuai dengan penjelasan tentang proses crossover yang sudah dijelaskan pada bab sebelumnya. Sebelum kedua chromosome tersebut di-cross, dilakukan proses normalisasi terlebih dahulu dengan cara mengganti id dari kota-kota yang bernilai 0 (yang merupakan penanda antar rute) dengan nilai-nilai negatif dekremental. Hal ini dilakukan supaya dalam chromosome tersebut tidak terdapat perulangan gen. Proses normalisasi tersebut dapat dilihat pada potongan kode dibawah. void Route::Normalize() { int newID = -1;

72

for each (City^ c in this->Cities) if (c->id <= 0) c->id = newID--; }

Setelah operasi crossover selesai, id dari kota-kota yang sebelumnya bernilai 0 dan dirubah menjadi nilai-nilai negatif harus dikembalikan ke nilai asalnya, untuk itu dijalankan proses denormalisasi. Implementasi dari proses denormalisasi dapat dilihat pada potongan kode dibawah ini. void Route::Denormalize() { for each (City^ c in this->Cities) if (c->id <= 0) c->id = 0; }

4.2.7

Implementasi Proses Mutation

Proses mutation melambangkan proses mutasi pada alam, dimana terdapat gen-gen dalam chromosome yang berubah nilai secara acak. Seperti pada proses operasi GA lainnya, proses mutation mempunyai nilai probabilitas dimana proses ini baru akan dijalankan ketika memenuhi nilai probabilitas tersebut. Proses ini hanya memproses satu chromosome pada satu waktu. Chromosome yang akan dimutasi didapatkan melalui proses selection. Implementasi proses mutation dalam aplikasi ini dapat dilihat pada potongan kode dibawah ini. void ProcessMutation() { if (rand->NextDouble() <= this->VRPProblem->MutationProbability) { int indexToMutate = 0; Route^ mutatedRoute; indexToMutate=Operators->DoRoulette(this->Routes); mutatedRoute = Operators->DoMutation(

73 this->Routes[indexToMutate]); AddRoute(mutatedRoute); this->MutationCounter++; } }

Sedangkan operasi mutation-nya dapat dilihat pada potongan kode dibawah ini. Route^ DoMutation(Route^ chromosome) { int r1 = 0; int r2 = 0; Random^ rand; Route^ output = gcnew Route(chromosome->Cities); City^ temp; do { rand = gcnew Random(); r1 = rand->Next(output->Cities->Count - 1); rand = gcnew Random(); r2 = rand->Next(output->Cities->Count - 1); } while (r1 == r2); temp = output->Cities[r1]; output->Cities[r1] = output->Cities[r2]; output->Cities[r2] = temp; return output; }

Operasi ini membutuhkan dua buah gen yang didapatkan secara acak, kemudian posisi kedua gen tersebut saling ditukar. 4.2.8

Implementasi Proses Inversion

Karena chromosome pada TSP/VRP merupakan sebuah rute, maka ada kemungkinan bahwa jika suatu bagian pada rute tersebut dibalik urutannya, maka jarak yang ditempuh akan

74 semakin pendek. Untuk itu memfasilitasi kemungkinan tersebut, maka digunakan sebuah operator GA yang bernama inversion. Proses ini bekerja dengan membalik urutan dari suatu bagian yang didapatkan secara acak dari sebuah rute. Seperti pada proses operasi GA lainnya, proses inversion mempunyai nilai probabilitas dimana proses ini baru akan dijalankan ketika memenuhi nilai probabilitas tersebut. Proses ini hanya memproses satu chromosome pada satu waktu. Chromosome yang akan diinversi didapatkan melalui proses selection. Implementasi proses inversion dalam aplikasi ini dapat dilihat pada potongan kode dibawah ini. void ProcessInversion() { if (rand->NextDouble() <= this->VRPProblem->InversionProbability) { int indexToInverse = 0; Route^ inversedRoute = nullptr; indexToInverse = Operators->DoRoulette(this->Routes); inversedRoute = Operators->DoInversion( this->Routes[indexToInverse]); AddRoute(inversedRoute); this->InversionCounter++; } }

Sedangkan operasi inversion-nya dapat dilihat pada potongan kode dibawah ini. Route^ VRPOperators::DoInversion(Route^ chromosome) { int r1 = 0; int r2 = 0; Random^ rand;

75 Route^ output = gcnew Route(chromosome->Cities); City^ temp; do { rand = gcnew Random(); r1 = rand->Next(output->Cities->Count - 1); rand = gcnew Random(); r2 = rand->Next(output->Cities->Count - 1); } while (r1 >= r2); while (r1 < r2) { temp = output->Cities[r1]; output->Cities[r1] = output->Cities[r2]; output->Cities[r2] = temp; r1++; r2--; } return output; }

Operasi ini membutuhkan dua buah pivot yang didapatkan secara acak, kemudian gen-gen yang berada diantara kedua pivot tersebut urutnya dibalik. 4.2.9

Implementasi Proses Migration

Proses migration merupakan inti dari proses paralel pada aplikasi ini. Proses ini memungkinkan terjadinya komunikasi antar prosesor dengan cara saling mengirim solusi terbaiknya pada setiap iterasi. Dengan mempertimbangan tingginya biaya komunikasi yang terjadi ketika mengirim pesan dari satu prosesor ke prosesor lain (karena jumlah data yang dikirim relatif besar), maka proses migrasi harus dilakukan secara efektif. Untuk itu, pada satu generasi sebuah prosesor hanya mengirim satu solusi terbaiknya ke satu buah prosesor lainnya saja.

76 Supaya setiap prosesor tetap dapat saling mengirim satu sama lain, maka proses migrasi dibuat bergantian dari satu prosesor ke prosesor lain. Misalkan terdapat 3 buah prosesor, maka prosesor ke-1 pada iterasi pertama akan mengirimkan solusi terbaiknya ke prosesor ke-2, kemudian pada iterasi berikutnya ke prosesor ke-3, dan karena sudah mengirim ke semua prosesor, maka pada iterasi berikutnya prosesor ke-1 tersebut akan kembali mengirim ke prosesor ke-2 dan seterusnya. Begitu pula halnya dengan prosesor-prosesor yang lain. Karena keterbatasan tipe data pada MPI yang tidak dapat mengirim object, maka object chromosome dirubah dahulu ke tipe data native yang dapat dikirim menggunakan MPI. Untuk itu, sebelum dikirim chromosome dirubah terlebih dahulu menjadi string dengan fungsi dibawah ini. String^ ToString() { StringBuilder^ sb = gcnew StringBuilder(); for (int i = 0; i < Cities->Count; i++) { sb->Append(Cities[i]->ToString())->Append(i Cities->Count - 1 ? "," : ""); } return sb->ToString(); }

<

Setelah itu baru dilakukan proses migrasi (pengiriman solusi terbaik) ke prosesor lain. Implementasi proses migrasi tersebut dapat dilihat pada potongan kode dibawah ini. void CheckAndProcessMigration() { if (this->IterationCounter % this->VRPProblem-> NumberOfIterationBetweenMigration == 0) { int my_rank, p; MPI_Comm_rank(MPI_COMM_WORLD, &my_rank); MPI_Comm_size(MPI_COMM_WORLD, &p);

77 /* minimal ada 3 processor (1 root, 2 worker) untuk melakukan proses migrasi */ if (p < 3) return; procToSend++; /* if target out of range, back to 1st island */ if (procToSend >= p) procToSend = 1; /* if target is itself, move to next island */ if (procToSend == my_rank) { procToSend++; /* if target out of range, back to 1st island */ if (procToSend >= p) procToSend = 1; } /* send best chromosome to neighbor island */ sprintf_s(ImsgSend, "%s", this->Routes[0]->ToString()); MPI_Isend(ImsgSend, (int)strlen(ImsgSend)+1, MPI_CHAR, procToSend, 0, MPI_COMM_WORLD, &sendRequest); } }

Untuk dapat menerima rute kiriman dari prosesor lain, maka pada awal tiap iterasi dijalankan fungsi dibawah ini yang bertugas memeriksa apakah ada pesan kiriman dari prosesor lain. void CheckAndRetreiveMigration() { /* check for incoming message */ if (!probeFlag) { /* probe for incoming message */ MPI_Iprobe(MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &probeFlag, &probeStatus); } else

78 { /* receive incoming message */ MPI_Irecv(ImsgRecv, MESSAGE_SIZE, MPI_CHAR, probeStatus.MPI_SOURCE, probeStatus.MPI_TAG, MPI_COMM_WORLD, &recvRequest); /* add incoming route to Route List */ AddRoute(ImsgRecv); /* reset probeFlag */ probeFlag = 0; } }

Jika ternyata terdapat pesan kiriman dari prosesor lain, maka pesan tersebut kemudian akan dirubah kembali menjadi bentuk object lalu dimasukkan ke dalam populasi. Untuk dapat mengembalikan kiriman yang berbentuk kode string tersebut menjadi object chromosome, digunakan fungsi dibawah ini. bool VRPPopulation::AddRoute(char* routeString) { String^ routeStr = gcnew String(routeString); array^ separators = {','}; /* pisah string inputan berdasarkan format xx,xx,xx:... */ array<String^>^ splittedRouteStr = routeStr->Split(separators); if (splittedRouteStr->Length == 1 && splittedRouteStr[0] == "") return false; /* buat route baru dan masukkan kota-kota yang didapat dari string inputan */ Route^ newRoute = gcnew Route(); for each(String^ cityStr in splittedRouteStr) { int newCityID = Int16::Parse(cityStr->Trim()); City^ newCity = VRPProblem->FindCityByID(newCityID); if (newCity != nullptr)

79 newRoute->AddCity(newCity); } return AddRoute(newRoute); }

80

[Halaman ini sengaja dikosongkan]

BAB 5 UJI COBA DAN EVALUASI

Pada bab ini akan dibahas mengenai uji coba dan evaluasi perangkat lunak. Perangkat lunak diuji coba dari segi fungsionalitas, kompatibilitas dan performa dengan berbagai skenario. Pada bab ini juga dibahas lingkungan uji coba. 5.1

Lingkungan Uji Coba

Uji coba dilakukan di Grid Computing Laboratory (GCL) Teknik Informatika ITS Surabaya. Komputer yang digunakan dalam cluster pada GCL adalah komputer-komputer workstation HP Compaq dx2700 dengan spesifikasi sebagai berikut. • • • • • • •

Processor Memory Chipset OS Middleware Compiler Switch

: Intel® Pentium® 4 Processors 3.0GHz : 1 GB : Broadwater Q963/ICH8 chipset : Microsoft Windows XP SP 2 : DeinoMPI 1.1.0 : Microsoft Visual Studio .NET 2005 : 3Com

Untuk pengujian aplikasi secara umum, digunakan instance VRP yang bersifat capacitated VRP dari dataset eugerat et al [14], sedangkan untuk pengujian aplikasi terhadap kemampuan memecahkan permasalahan heterogeneous, digunakan instance modifikasi dari instane capacitated VRP. Perbedaan antara capacitated VRP dan heterogeneous VRP hanya terletak pada jenis kendaraan yang digunakan, dimana pada capacitated VRP semua kendaraan yang digunakan mempunyai kapasitas yang sama/sejenis. Pada heterogeneous VRP, setiap kendaraan

81

82

dapat memiliki kapasitas yang berbeda. Karena kecilnya perbedaan tersebut, maka untuk pengujian aplikasi ini dapat digunakan instance VRP bertipe capacitated VRP. Karena sifat Genetic Algorithm yang menggunakan fungsi random, dimana solusi yang dihasilkan bisa sangat bervariasi untuk serangkaian parameter yang sama, maka untuk setiap pengujian pada serangkaian parameter yang sama, dilakukan percobaan sebanyak 10 kali, lalu diambil nilai ratarata dari hasil dari percobaan-percobaan tersebut. Waktu eksekusi yang ditulis pada laporan ini adalah waktu eksekusi pada percobaan yang menghasilkan kualitas solusi terbaik. 5.2

Uji Coba Parameter GA

Uji coba parameter GA dilakukan untuk melihat pengaruh dari parameter-parameter GA terhadap waktu eksekusi dan kualitas solusi yang dihasilkan. Seperti yang sudah disebutkan pada bab sebelumnya, terdapat beberapa parameter GA yang digunakan dalam aplikasi ini, yaitu crossover probability, mutation probability, inversion probability, number of iteration, dan population size. Untuk pengujian awal, digunakan nilai-nilai awal untuk parameter-parameter yang umum digunakan untuk Genetic Algorithm [15], yaitu seperti berikut. -

Crossover Probability (CP): 0.8

-

Inversion Probability (IP): 0.3

-

Mutation Probability (MP): 0.2

-

Number of Iteration (NI): 10000

-

Population Size (PS): 500 .

83 Karena uji coba ini bukan untuk mengukur performa paralel, maka untuk percobaan ini digunakan Genetic Algorithm menggunakan 1 processor saja. Percobaan ini dilakukan menggunakan VRP instance A-n32-k5 yang mempunyai rute optimal senilai 784. Hasil percobaan tersebut dapat dilihat pada tabel 5.1 dan tabel 5.2.

Dari hasil uji coba tersebut terlihat bahwa terdapat peningkatan waktu eksekusi yang sebanding dengan jumlah iterasi. Dimana jika jumlah iterasi ditingkatkan menjadi dua kali lipat, maka waktu eksekusi juga naik menjadi 2 kali lipat. Sedangkan kualitas solusi mengalami peningkatan hampir, seiring dengan bertambahnya iterasi yang dijalankan. Dari hasil uji coba kedua, terlihat bahwa tidak terjadi perubahan berarti pada waktu eksekusi ketika kapasitas populasi dinaikkan, namun kualitas solusi yang didapat cenderung menurun seiring dengan meningkatnya kapasitas populasi, hal ini terjadi karena semakin bertambahnya kapasitas populasi, search space yang terbentuk juga semakin besar, sehingga menurunkan kemampuan GA mencari solusi optimum. Tabel 5.1 Hasil Uji Coba Parameter GA : Jumlah Iterasi

No CP

IP

MP

NI

PS

Waktu Rata-rata

Hasil Rata-rata

1

0.8

0.3

0.2

100

500

00:00:10

1642

2

0.8

0.3

0.2

1000

500

00:00:53

1501

3

0.8

0.3

0.2

10000

500

00:08:20

964

4

0.8

0.3

0.2

100000

500

01:22:13

844

84

Tabel 5.2 Hasil Uji Coba Parameter GA : Ukuran Populasi

No CP

IP

MP

NI

PS

Waktu Rata-rata

Hasil Rata-rata

1

0.8

0.3

0.2

10000

100

00:08:18

900

2

0.8

0.3

0.2

10000

500

00:08:20

964

3

0.8

0.3

0.2

10000

1000

00:08:18

1100

4

0.8

0.3

0.2

10000

10000

00:08:35

1505

5.3

Uji Coba Performa

Uji coba performa ini dilakukan untuk melihat pengaruh beberapa skenario paralesasi GA terhadap kualitas solusi yang dihasilkan maupun waktu eksekusi yang dibutuhkan. Seperti yang sudah dijelaskan dalam bab sebelumnya, aplikasi ini menggunakan model arsitektur master-processor, dimana komputer master hanya bertindak sebagai penerima hasil solusi yang dikerjakan oleh para processor. Sesuai dengan rancangan arsitektur tersebut, maka jika pada uraian skenario tersebut bahwa digunakan satu processor, maka dalam testing, komputer yang digunakan ada dua, yaitu satu bertindak sebagai master, satu lagi bertindak sebagai processor. Begitu juga bila tersebut bahwa ada 2 processor, maka dalam kenyataannya ada tiga komputer yang bekerja, yaitu satu sebagai master, dua sisanya sebagai processor. 5.3.1

Skenario 1

Pada skenario ini aplikasi diujicoba pada dataset eugerat et al set A, B, dan P yang diambil sebanyak 5 buah secara acak.

85 Pengujian dilakukan menggunakan 1, 2, dan 4 processor dan menggunakan parameter-parameter dibawah ini: -

Crossover Probability (CP): 0.8

-

Inversion Probability (IP): 0.3

-

Mutation Probability (MP): 0.2

-

Number of Iteration (NI): 50000

-

Population Size (PS): 500

-

Jarak Antar Migrasi: 10

Uji coba dilakukan dengan mengukur lamanya waktu eksekusi aplikasi serta melihat kualitas solusi yang dihasilkan. Hasil uji coba dapat dilihat pada tabel 5.3 dan tabel 5.4. Tabel 5.3 Uji Coba Performa Skenario 1 : Hasil Rata-Rata Pengujian Kualitas Solusi Pada Dataset Eugerat et al

Instance\Processor A-n32-k5 A-n46-k7 B-n68-k9 B-n78-k10 P-n101-k4

1 957.8 1273.6 2036.4 2226.8 1583.2

2 858.9 1149.7 1748.0 1897.6 1353.0

4 845.2 1066.4 1526.5 1516.0 1212.1

Optimal 784 914 1272 1221 681

Tabel 5.4 Uji Coba Performa Skenario 1 : Hasil Rata-Rata Pengujian Waktu Eksekusi Pada Dataset Eugerat et al

Instance\Processor A-n32-k5 A-n46-k7 B-n68-k9 B-n78-k10 P-n101-k4

1 00:08:21 00:08:30 00:08:27 00:08:24 00:08:23

2 00:08:24 00:08:29 00:08:19 00:08:24 00:08:26

4 00:08:30 00:08:22 00:08:27 00:08:30 00:08:30

86

Gambar 5.1 Grafik Uji Coba Skenario 1 : Hasil Rata-Rata Pengujian Kualitas Solusi Pada Dataset Eugerat et al

Gambar 5.2 Grafik Uji Coba Skenario 1 : Hasil Rata-Rata Pengujian Waktu Eksekusi Pada Dataset Eugerat et al

Dari hasil uji coba, bisa dilihat bahwa terdapat peningkatan dari kualitas solusi yang dihasilkan seiring dengan penggunaan processor yang lebih banyak. Sedangkan waktu

87 eksekusi total yang dibutuhkan tidak menunjukkan suatu peningkatan ataupun penurunan, namun cenderung sama. 5.3.2

Skenario 2

Pada skenario ini aplikasi diujicoba untuk menyelesaikan VRP dengan skala besar, menggunakan dataset eugerat et al dengan instance P-n101-k4 menggunakan iterasi lebih banyak daripada skenario 1. Pengujian dilakukan menggunakan parameter-parameter dibawah ini: -

Crossover Probability (CP): 0.8

-

Inversion Probability (IP): 0.3

-

Mutation Probability (MP): 0.2

-

Number of Iteration (NI): 50000

-

Population Size (PS): 500

-

Jarak Antar Migrasi: 10

Uji coba dilakukan dengan mengukur lamanya waktu eksekusi aplikasi serta melihat kualitas solusi yang dihasilkan. Hasil uji coba dapat dilihat pada tabel 5.5 dan tabel 5.6. Tabel 5.5 Uji Coba Performa Skenario 2 : Hasil Rata-Rata Pengujian Kualitas Solusi Untuk VRP Skala Besar

Instance\Processor P-n101-k4

1 1133.7

2

4

954.3

892.8

Optimal 681

Tabel 5.6 Uji Coba Performa Skenario 2 : Hasil Rata-Rata Pengujian Waktu Eksekusi Untuk VRP Skala Besar

Instance\Processor P-n101-k4

1 00:41:03

2 0:40:56

4 0:41:01

88

Gambar 5.3 Grafik Uji Coba Skenario 2 : Hasil Rata-Rata Pengujian Kualitas Solusi Untuk VRP Skala Besar

Gambar 5.4 Grafik Uji Coba Skenario 2 : Hasil Rata-Rata Pengujian Waktu Eksekusi Untuk VRP Skala Besar

Dari hasil uji coba, bisa dilihat bahwa terdapat peningkatan dari kualitas solusi yang dihasilkan seiring dengan penggunaan processor yang lebih banyak. Sedangkan waktu eksekusi total yang dibutuhkan tidak menunjukkan suatu peningkatan ataupun penurunan, namun cenderung sama. Kualitas

89 solusi yang dihasilkan juga terbukti mengalami peningkatan dibandingkan dengan hasil pada uji coba skenario 1 5.3.3

Skenario 3

Pada skenario ini aplikasi diujicoba untuk memecahkan permasalahan VRP yang bertipe heterogeneous. Untuk itu digunakan dataset modifikasi berdasarkan dataset eugerat et al instance A-n32-k5. Jika pada dataset A-n32-k5 asli, terdapat 5 buah vehicle yang kesemuanya mempunyai kapasitas yang sama, yaitu sebesar 100, maka pada dataset ujicoba heterogeneous VRP ini, juga digunakan 5 buah vehicle dengan komposisi kapasitas masing-masing vehicle sebagai berikut: Vehicle 1: 90 Vehicle 2: 100 Vehicle 3: 110 Vehicle 4: 120 Vehicle 5: 130 Pengujian dilakukan menggunakan parameter-parameter Genetic Algorithm seperti dibawah ini: -

Crossover Probability (CP): 0.8

-

Inversion Probability (IP): 0.3

-

Mutation Probability (MP): 0.2

-

Number of Iteration (NI): 10000

-

Population Size (PS): 500

-

Jarak Antar Migrasi: 10

Uji coba dilakukan dengan mengukur lamanya waktu eksekusi aplikasi serta melihat kualitas solusi yang dihasilkan. Karena dataset yang diujicoba ini merupakan dataset modifikasi, maka hasil untuk percobaan skenario 3 ini tidak dapat

90 dibandingkan dengan solusi optimal untuk instance ujicoba tersebut. Hasil uji coba dapat dilihat pada tabel 5.7 dan tabel 5.8. Dari hasil uji coba, dibuktikan bahwa aplikasi mampu menyelesaikan permasalahan VRP bertipe heterogeneous. Selain itu juga bisa dilihat bahwa terdapat peningkatan dari kualitas solusi yang dihasilkan seiring dengan penggunaan processor yang lebih banyak. Sedangkan waktu eksekusi total yang dibutuhkan tidak menunjukkan suatu peningkatan ataupun penurunan, namun cenderung sama.

Tabel 5.7 Uji Coba Performa Skenario 3: Hasil Rata-Rata Pengujian Kualitas Solusi Untuk Permasalahan Heterogeneous VRP

Instance\Processor A-n32-k5_modif

1 932.4

2 861.33

4 763.5

Tabel 5.8 Uji Coba Performa Skenario 3 : Hasil Rata-Rata Pengujian Waktu Eksekusi Untuk Permasalahan Heterogeneous VRP

Instance\Processor A-n32-k5_modif

1 00:08:28

2 0:08:29

4 0:08:26

91

Gambar 5.5 Grafik Uji Coba Skenario 3 : Hasil Rata-Rata Pengujian Kualitas Solusi Untuk Permasalahan Heterogeneous VRP

Gambar 5.6 Grafik Uji Coba Skenario 3 : Hasil Rata-Rata Pengujian Waktu Eksekusi Untuk Permasalahan Heterogeneous VRP

92

[Halaman ini sengaja dikosongkan]

BAB 6 PENUTUP Pada bab ini akan dibahas mengenai kesimpulan yang dapat diambil dari tujuan pembuatan perangkat lunak, serta hasil uji coba yang telah dilakukan. Selain itu terdapat beberapa saran yang untuk pengembangan lebih lanjut. 6.1

KESIMPULAN

Dari hasil pengamatan selama perancangan, implementasi, dan proses uji coba perangkat lunak yang dilakukan, dapat diambil kesimpulan sebagai berikut : 1. Aplikasi yang dibuat telah mampu memenuhi kebutuhan untuk menyelesaikan permasalahan VRP, baik VRP bertipe capacitated maupun heterogeneous menggunakan Genetic Algorithm secara paralel. 2. Waktu yang dibutuhkan untuk menyelesaikan VRP dengan Genetic Algorithm dipengaruhi oleh banyaknya iterasi yang dilakukan, bukan dari ukuran permasalahan VRP. 3. Karena Genetic Algorithm tidak terpengaruh oleh besarnya permasalahan, GA merupakan metode yang cukup efektif untuk menyelesaikan VRP dengan skala besar. 4. Penggunaan Island Model sebagai akselerator dalam metode GA terbukti mampu menghasilkan solusi yang lebih baik dibandingkan dengan single mode GA. 6.2

SARAN

Berikut merupakan beberapa saran untuk pengembangan sistem di masa yang akan datang, berdasar pada hasil perancangan, implementasi, dan uji coba yang telah dilakukan.

93

94 1. Diberikan antar muka grafis untuk memasukkan inputan dari user, dan untuk menampilkan solusi optimal yang dihasilkan oleh aplikasi dalam bentuk koordinat, sehingga memudahkan pembacaan solusi hasil. 2. Dibutuhkan penelitian lebih lanjut untuk mencoba metodemetode lain dalam proses migrasi, sehingga bisa didapatkan perbedaan yang lebih signifikan dalam penggunaan Genetic Algorithm secara paralel.

DAFTAR PUSTAKA [1]

G. Laporte, M. Gendreau, J-Y. Potvin, and F. Semet. Classical and modern heuristics for the vehicle routing problem. International Transactions in Operational Research, 7:285-300, 2000.

[2]

M. Fisher. Vehicle routing. Handbooks of Operations Research and Management Science, chapter 1, 8:1-31, 1995.

[3]

E. Falkenauer. A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics, 2:5-30, 1996.

[4]

S.M. Sait and H. Youssef, editors. Iterative Computer Algorithms with Application in Engineering: Solving Combinatorial Optimization Problems, chapter 3. IEEE Computer Society, 1999.

[5]

Charles Darwin. Britannica concise encyclopedia from encyclopædia britannica., 2004. URL .

[6]

L.A. Wolsey, editor. Integer Programming. John Wiley and Sons, 1998.

[7]

F.B. Pereira, J. Tavares, P. Machado, and E. Costa. GVR: a new genetic representation for the vehicle routing problem. Prodeedings of the 13th Irish International Conference on Artificial Intelligence and Cognitive Science, pages 95-102, 2002.

[8]

G. Laporte and F. Semet. Classical heuristics for the vehicle routing problem. Technical Report G98-54, GERAD, 1999.

95

96 [9]

Evolutionary Algorithms. Lecture Evolutionary algorithms, 2004. .

slides: URL

[10]

M. Gendreau, G. Laporte, and J-Y. Potvin. Metaheuristics for the vehicle routing problem. Technical Report G-98-52, GERAD, 1999.

[11]

Z. Michalewicz, editor. Genetic Algorithm + Data Structures = Evolution Programs, 3rd, revised and extended edition. Springer-Verlag, 1996.

[12]

H. Muhlenbein. Evolution in Time and Space: The Parallel Genetic Algorithm. In G. Rawlins, editor, FOGA -1, pages 316-337. Morgan Kaufmann, 1991.

[13]

Whitley, D.: Cellular genetic algorithms. In Forrest, S., ed.: Proceedings of the 5th ICGA, Morgan-Kaufmann, CA (1993) 658

[14]

Augerat et al set A, B, and set P VRP Instances: http://www.branchandcut.org/VRP/data/

[15]

Áslaug Sóley Bjarnadóttir: Solving the Vehicle Routing Problem with Genetic Algorithms, 2004.

BIODATA PENULIS Bambang Eko Hendrawan, biasa dipanggil Hendra, dilahirkan dan dibesarkan di kota metoropolis yang biasa disebut sebagai kota Pahlawan, Surabaya, pada tanggal 21 Mei 1986. Penulis merupakan anak pertama dari dua bersaudara. Sejak SMU, penulis memiliki ketertarikan dengan benda bernama komputer, yang membuatnya memutuskan untuk kuliah di Teknik Informatika Institut Teknologi Sepuluh Nopember Surabaya. Selama berkuliah di Teknik Informatika ITS Surabaya, penulis aktif pada Laboratorium Pemrograman Informatika ITS sebagai Administrator, dimana pada tahun berikutnya penulis juga menjabat sebagai koordinator Administrator, dan pada tahun terakhir kuliahnya, penulis berpindah ke Grid Computing Laboratory. Selain itu penulis juga sempat menjadi asisten dan koordinator asisten Praktikum Pemrograman Terstruktur (PPT) pada Laboratorium yang sama. Selama 9 semester menuntut ilmu di Teknik Informatika ITS, penulis juga sempat menjadi staff divisi Portal HMTC, asisten PIKTI, dan karyawan paruh-waktu di beberapa perusahaan IT Consultant di Surabaya. Ketertarikan penulis pada dunia IT meliputi desain dan analisa jaringan komputer, perangkat lunak, maupun database. Penulis sangat menggemari bahasa pemrograman .NET dan PHP serta aktif mengikuti perkembangan teknologi IT terbaru lewat forum dan milis di internet. Penulis bisa dihubungi melalui email Yahoo!Messenger dengan ID [email protected].

97

atau

98