ADLN PERPUSTAKAAN UNIVERSITAS AIRLANGGA

ADLN – PERPUSTAKAAN UNIVERSITAS AIRLANGGA

RANCANG BANGUN SISTEM PENDUKUNG KEPUTUSAN UNTUK OPTIMASI TRAVELLING SALESMAN PROBLEM BERBASIS SISTEM INFORMASI GEOGRAFIS DENGAN MENGGUNAKAN ALGORITMA GENETIKA

SKRIPSI

GALIH GAHARDITAMA ANDAMORE

PROGRAM STUDI S1 SISTEM INFORMASI FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS AIRLANGGA SURABAYA 2016 SKRIPSI

RANCANG BANGUN SISTEM…

GALIH G. A.


RANCANG BANGUN SISTEM PENDUKUNG KEPUTUSAN UNTUK OPTIMASI TRAVELLING SALESMAN PROBLEM BERBASIS SISTEM INFORMASI GEOGRAFIS DENGAN MENGGUNAKAN ALGORITMA GENETIKA

SKRIPSI

ii RANCANG BANGUN SISTEM…

GALIH G. A.


LEMBAR PENGESAHAN NASKAH SKRIPSI

SKRIPSI

iii RANCANG BANGUN SISTEM…

GALIH G. A.


PEDOMAN PENGGUNAAN SKRIPSI

Skripsi ini tidak dipublikasikan, namun tersedia di perpustakaan dalam lingkungan Universitas Airlangga, diperkenankan untuk dipakai sebagai referensi kepustakaan, tetapi pengutipan harus seizin penyusun dan harus menyebutkan sumbernya sesuai kebiasaan ilmiah.

Dokumen skripsi ini merupakan hak milik Universitas Airlangga.

SKRIPSI

iv RANCANG BANGUN SISTEM…

GALIH G. A.


SURAT PERNYATAAN TENTANG ORISINALITAS

SKRIPSI

v RANCANG BANGUN SISTEM…

GALIH G. A.


KATA PENGANTAR Puji syukur kehadirat Allah Subhanahu Wa Ta’ala, yang telah melimpahkan anugerah-Nya, hingga penulis dapat menyelesaikan proposal skripsi yang berjudul “Rancang Bangun Sistem Pendukung Keputusan Untuk Optimasi Travelling Salesman Problem Berbasis Sistem Informasi Geografis Dengan Menggunakan Algoritma Genetika” dengan baik, serta Sholatu Wa Salam semoga tetap terlimpahkan kepada Rasulullah Muhammad SAW yang mengantarkan pada sebuah kehidupan yang penuh keselamatan di dunia dan di akhirat. Atas dukungan moral dan materil yang diberikan dalam penyusunan makalah ini, maka penulis mengucapkan banyak terima kasih kepada : 1. Taufik, S.T, M.Kom selaku dosen pembimbing I, 2. Ir. Dyah Herawatie, M.Si selaku dosen pembimbing II, 3. Keluarga dan teman-teman Sistem Informasi 2011, yang telah memberikan semangat dan dukungannya kepada penulis. Penulis mengharapkan kritik dan saran yang bersifat membangun demi kesempurnaan proposal skripsi ini. Semoga proposal skripsi ini dapat memberikan manfaat dan wawasan yang berguna. Amin.

Surabaya, 15 Agustus 2016

Penulis SKRIPSI

vi RANCANG BANGUN SISTEM…

GALIH G. A.


UCAPAN TERIMAKASIH

Segala puji syukur kehadirat Tuhan Yang Maha Esa atas limpahan rahmat dan ridho-Nya, sehingga saya dapat menyelesaikan penyusunan skripsi dengan judul RANCANG BANGUN SISTEM PENDUKUNG KEPUTUSAN UNTUK OPTIMASI TRAVELLING SALESMAN PROBLEM BERBASIS SISTEM INFORMASI GEOGRAFIS DENGAN MENGGUNAKAN ALGORITMA GENETIKA. Dalam pelaksanaan dan penyusunan skripsi ini, penulis banyak menemui kendala. Namun, dengan adanya bantuan dari berbagai pihak, akhirnya laporan penelitian ini dapat terselesaikan. Oleh karena itu, penulis tidak lupa mengucapkan terima kasih kepada: 1.

Allah SWT yang senantiasa memberikan segala rahmat, hidayah, dan karuniaNya serta Rasulullah Muhammad SAW yang selalu menjadi panutan dan suri tauladan terbaik dalam kehidupan penulis sehingga penulisan skripsi ini dapat terselesaikan dengan baik.

2.

Joko Darmono dan Retno Poedjanti, selaku ayah dan ibu tercinta yang telah memberikan dukungan secara penuh dalam bentuk doa dan kasih sayang sekaligus menjadi penyemangat dan motivasi penulis untuk dapat menyelesaikan studi dan skripsi dengan baik.

3.

B. Galuh R. T. A, selaku kakak kandung yang memberikan semangat dan doa kepada penulis untuk dapat menyelesaikan skripsi.

4.

Taufik, S.T, M.Kom, selaku dosen pembimbing I yang senantiasa memberikan banyak masukan ilmu pengetahuan kepada penulis, dan dengan sabar membimbing dan membantu penulis dalam melakukan penelitian hingga terselesaikannya skripsi ini.

5.

Ir. Dyah Herawatie, M.Si, selaku dosen pembimbing II yang dengan sabar membimbing, mengarahkan dan membantu memberikan ilmunya, sehingga penulis dapat menyusun skripsi ini dengan baik dan benar.

6.

Indah Werdiningsih, S.Si, M.Kom., selaku dosen wali yang dengan sabar membimbing penulis sejak awal masa perkuliahan hingga skripsi ini terselesaikan.

SKRIPSI

vii RANCANG BANGUN SISTEM…

GALIH G. A.


7.

Seluruh dosen program studi S1 Sistem Informasi yang telah banyak memberikan ilmu sehingga penulisan skripsi dapat terselesaikan dengan baik.

8.

Branch Manager PT. Sun Star Motor Cabang Surabaya, yang telah memberikan izin dan kemudahan penulis untuk melakukan penelitian di PT. Sun Star Motor. Serta kurir perusahaan yang telah membantu untuk pengambilan data penelitian sehingga penelitian ini dapat diselesaikan dengan baik.

9.

Muhammad Shofi Al Baaqi, Imam Wicaksono, Achmad Agoeh, Hendra Hanggar Kusuma, Brahmantyo Noviansyah Putro Rahardjo, Diaz Mahardika Wibisono, Miqdad Hasan, Arya Bayu, Abdullah Fakih, M. Zaky Erdiansyah, Agustinus Kurniawan, Alief Arsalan, M. Fikri Ramadhan, Nur Ardista, Gading Arum, Nadia Lutfiyah Sari, Pascalina Rakhmasari Putri, Fachrian Anugerah, yang telah memberikan banyak bantuan, keceriaan, hiburan, dan memberikan motivasi dalam penulisan skripsi ini.

10. Dewi Nawang Palupi, yang telah memberikan semangat, motivasi, dorongan, keceriaan, hiburan dalam masa penelitian hingga terselesaikannya skripsi ini. 11. Teman-teman S1 Sistem Informasi Universitas Airlangga angkatan 2011 yang telah mendukung dan membantu dengan berbagi ilmu dan pengalaman selama masa perkuliahan hingga penulisan skripsi ini. 12. Staf TU program studi Sistem Informasi yang telah membantu dalam keperluan administrasi dan penjadwalan sidang. 13. Teman-teman serta berbagai pihak yang tidak dapat disebutkan satu persatu yang telah memberikan bantuan, hiburan dan informasi selama proses penulisan skripsi ini.

SKRIPSI

viii RANCANG BANGUN SISTEM…

GALIH G. A.


Galih Gaharditama Andamore, 2016. Rancang Bangun Sistem Pendukung Keputusan untuk Optimasi Travelling Salesman Problem Berbasis Sistem Informasi Geografis dengan Menggunakan Algoritma Genetika. Skripsi ini dibawah bimbingan Taufik, S.T, M.Kom dan Ir. Dyah Herawatie, M.Si. Program Studi S1 Sistem Informasi. Fakultas Sains dan Teknologi, Universitas Airlangga.

ABSTRAK PT. Sun Star Motor cabang Surabaya merupakan perusahaan bisnis dalam bidang jasa penjualan otomotif. Salah satu divisinya adalah kurir, yang bertugas untuk mengambil kelengkapan administrasi ke beberapa pelanggan yang belum diberikan. Hal ini sesuai dengan problematika Travelling Salesman Problem yang bertujuan untuk mengoptimasikan jarak tempuh. Oleh karena itu, tujuan dari penelitian ini adalah untuk mengoptimasikan rute perjalanan kurir berbasis Sistem Informasi Geografis dengan menggunakan Algoritma Genetika. Rancang bangun sistem ini melalui beberapa tahap. Tahap pertama adalah pengambilan dan pengumpulan data dan informasi sebagai faktor yang mempengaruhi pengambilan keputusan. Pada pembangunan sistem ini menggunakan faktor jarak dan arah sebagai faktor yang mempengaruhi dalam pengambilan keputusan. Tahap kedua adalah pengolahan data dan informasi dengan menganalisa data yang telah didapat untuk mengetahui jarak antar lokasi dan lokasi awal dari perjalanan. Tahap ketiga adalah penentuan rute sub-optimal menggunakan Algoritma Genetika. Tahap keempat adalah perancangan sistem yang menggunakan use case diagram dan activity diagram, serta implementasi sistem dengan menggunakan bahasa java. Tahap kelima adalah pengujian sistem dengan menggunakan Black Box Testing dan evaluasi sistem untuk mengetahui apakah sistem telah berjalan sesuai dengan kebutuhan kurir. Hasil pengujian parameter Algoritma Genetika dari data daftar kunjungan kurir yang mempunyai 5 lokasi tujuan diperoleh rata-rata fitness sebesar 40,84 kilometer dengan menggunakan parameter ukuran populasi sebesar 60, jumlah generasi 10, probabilitas crossover 0,5 dan probabilitas mutation 0,1. Sedangkan data daftar kunjungan kurir dengan 7 lokasi tujuan diperoleh rata-rata fitness yang paling kecil sebesar 57,42 kilometer dengan menggunakan parameter ukuran populasi 80, jumlah generasi 10, probabilitas crossover 0,3 dan probabilitas mutation 0,3. Secara keseluruhan hasil dari evaluasi sistem mempunyai tampilan yang interaktif, mudah digunakan dan sesuai dengan kebutuhan. Kata Kunci: Optimasi, Travelling Salesman Problem, Algoritma Genetika, Sistem Informasi Geografis

SKRIPSI

ix RANCANG BANGUN SISTEM…

GALIH G. A.


Galih Gaharditama Andamore, 2016. Design and Implementation of a Decision Support System for Optimization Travelling Salesman Problem Based on Geographic Information System using Genetic Algorithm. This undergraduate thesis was under guidance of Taufik, S.T, M.Kom and Ir. Dyah Herawatie, M.Si. Major of S1Information System. Faculty of Science and Technology, Airlangga University.

ABSTRACT Sun Star Motor Inc. Surabaya is a business enterprise in the field of automotive sales services. One of its divisions is a courier service, whose job is to take the administrative requirements to some customers who have not been granted. This is in accordance with the problematic of Travelling Salesman Problem which aims in optimize the mileage. Therefore, the purpose of this study was to optimize the route trip courier service based on Geographic Information Systems using Genetic Algorithms. The design of this system is through several stages. The first stage is the retrieval and collection of data and information as a factor affecting the decision making. In the development of this system uses the distance and direction as the factors that influence the making of the decision. The second stage is the processing of data and information by analyzing the data that have been obtained to determine the distance between the location and the starting point of the trip. The third stage is the determination of the sub-optimal route by using Genetic Algorithm. The fourth stage is to design a system by using a use case diagrams and activity diagrams, as well as the implementation of the system by using the java’s language. The fifth stage is system testing by using the Black Box Testing and system’s evaluation to determine whether the system has been run in accordance with the needs of the courier. The test results of the courier’s visit real data which has 5 locations of interest earned the average fitness of 40,84 kilometers using the parameters of population size of 60, maximal generation of 10, crossover probability of 0,5 and mutation probability of 0,1. While courier’s visit with 7 locations of interest earned the smallest average fitness of 57,42 kilometers using the parameters of population size of 80, maximal generation of 10, crossover probability of 0,3 and mutation probability of 0,3. The overall results of the evaluation system has an interactive design, easy to use and as needed. Keyword: Optimization, Travelling Salesman Problem, Genetic Algorithm, Geographic Information System

SKRIPSI

x RANCANG BANGUN SISTEM…

GALIH G. A.


DAFTAR ISI Halaman HALAMAN JUDUL .............................................................................................. i LEMBAR PERNYATAAN .................................................................................. ii LEMBAR PENGESAHAN NASKAH SKRIPSI .............................................. iii LEMBAR PEDOMAN PENGGUNAAN SKRIPSI .......................................... iv SURAT PERNYATAAN TENTANG ORISINALITAS ................................... v KATA PENGANTAR .......................................................................................... vi UCAPAN TERIMAKASIH................................................................................ vii ABSTRAK ............................................................................................................ ix ABSTRACT ........................................................................................................... x DAFTAR ISI ......................................................................................................... xi DAFTAR GAMBAR .......................................................................................... xiv DAFTAR TABEL .............................................................................................. xvi DAFTAR LAMPIRAN ..................................................................................... xvii BAB I PENDAHULUAN ...................................................................................... 1 1.1

Latar Belakang .......................................................................................... 1

1.2

Rumusan Masalah ..................................................................................... 4

1.3

Tujuan ....................................................................................................... 4

1.4

Manfaat ..................................................................................................... 5

1.5

Batasan Masalah ....................................................................................... 5

BAB II TINJAUAN PUSTAKA........................................................................... 6 2.1

Konsep Sistem Informasi .......................................................................... 6

2.2

Google Maps ............................................................................................. 6

SKRIPSI

xi RANCANG BANGUN SISTEM…

GALIH G. A.


2.3

Google Maps API ..................................................................................... 7

2.4

Android ..................................................................................................... 8

2.5

Sistem Informasi Geografi ........................................................................ 9

2.6

Teori Graph ............................................................................................ 13

2.7

Optimasi Kombinatorial.......................................................................... 13

2.8

Travelling Salesman Problem ................................................................. 14

2.9

Algoritma Genetika ................................................................................. 15

2.10 JSON (JavaScript Object Notation)........................................................ 25 BAB III METODE PENELITIAN .................................................................... 27 3.1.

Lokasi dan Waktu Penelitian .................................................................. 27

3.2.

Objek Penelitian ...................................................................................... 27

3.3.

Tahapan Penelitian .................................................................................. 27

3.4.

Pengumpulan Data Dan Informasi .......................................................... 28

3.5.

Pengolahan Data Dan Informasi ............................................................. 29

3.6.

Penyelesaian Masalah dengan Algoritma Genetika ................................ 30

3.7.

Perancangan Sistem ................................................................................ 33

3.8.

Implementasi Sistem ............................................................................... 36

3.9.

Pengujian Sistem ..................................................................................... 36

3.10. Evaluasi Sistem ....................................................................................... 36 BAB IV HASIL DAN PEMBAHASAN ............................................................ 38 4.1.

Pengumpulan Data dan Informasi ........................................................... 38

4.2.

Pengolahan Data dan Informasi .............................................................. 39

4.3.

Penyelesaian Masalah dengan Algoritma Genetika ................................ 41

4.4.

Perancangan Sistem ................................................................................ 55

4.5.

Implementasi Sistem ............................................................................... 63

SKRIPSI

xii RANCANG BANGUN SISTEM…

GALIH G. A.


4.6.

Pengujian Sistem ..................................................................................... 70

4.7.

Evaluasi Sistem ....................................................................................... 90

BAB V KESIMPULAN DAN SARAN .............................................................. 92 5.1.

Kesimpulan ............................................................................................. 92

5.2.

Saran ....................................................................................................... 93

DAFTAR PUSTAKA .......................................................................................... 94 LAMPIRAN

SKRIPSI

xiii RANCANG BANGUN SISTEM…

GALIH G. A.


DAFTAR GAMBAR Gambar 2.1 Tampilan Google Maps ....................................................................... 7 Gambar 2.2 Tampilan Map View Google Maps ..................................................... 8 Gambar 2.3 Tipe Data Titik .................................................................................. 11 Gambar 2.4 Lokasi PT. Sun Star Motor di Jalan Ngagel, Surabaya ..................... 12 Gambar 2.5 Tipe Data Garis ................................................................................. 12 Gambar 2.6 Lokasi Jalan Bali ............................................................................... 12 Gambar 2.7 Contoh roulette-wheel dari tabel 2.2 ................................................. 21 Gambar 3.1 Alur penelitian ................................................................................... 28 Gambar 4.1 Tampilan directions pada Google Maps ........................................... 42 Gambar 4.2 Gambaran Umum Sistem .................................................................. 56 Gambar 4.3 Use Case Diagram Optimasi Travelling Salesman Problem ............ 57 Gambar 4.4 Activity Diagram Cari Alamat .......................................................... 59 Gambar 4.5 Activity Diagram Daftar Tujuan........................................................ 60 Gambar 4.6 Rancangan Form Home ..................................................................... 61 Gambar 4.7 Rancangan Form Cari Alamat ........................................................... 61 Gambar 4.8 Rancangan Form Daftar Tujuan ........................................................ 62 Gambar 4.9 Rancangan Form Tentang ................................................................. 62 Gambar 4.10 Algoritma Umum Optimasi Travelling Salesman Problem ............ 63 Gambar 4.11 Psuedocode Input Lokasi Tujuan .................................................... 64 Gambar 4.12 Psuedocode Menghitung jarak antar lokasi .................................... 65 Gambar 4.13 Psuedocode Perhitungan Algoritma Genetika ................................ 66 Gambar 4.14 Psuedocode Menampilkan Rute Hasil dari Algoritma Genetika .... 66 Gambar 4.15 Tampilan Awal Menu Home ........................................................... 69 Gambar 4.16 Tampilan Menu Cari Alamat........................................................... 69 Gambar 4.17 Tampilan Menu Daftar Tujuan ........................................................ 69 Gambar 4.18 Tampilan Rute Hasil Perhitungan Algoritma Genetika .................. 69 Gambar 4.19 Tampilan Menu Tentang ................................................................. 69 Gambar 4.20 Gagal menampilkan menu Cari Alamat .......................................... 73 Gambar 4.21 Gagal menampilkan menu Cari Alamat .......................................... 73 Gambar 4.22 Berhasil menampilkan menu Cari Alamat ...................................... 74

SKRIPSI

xiv RANCANG BANGUN SISTEM…

GALIH G. A.


Gambar 4.23 Tidak ditemukan hasil pencarian..................................................... 74 Gambar 4.24 Gagal menampilkan lokasi alamat .................................................. 74 Gambar 4.25 Berhasil menampilkan lokasi alamat dengan tanda pada peta ........ 74 Gambar 4.26 Berhasil menyimpan lokasi alamat ................................................. 74 Gambar 4.27 Gagal menyimpan lokasi alamat ..................................................... 74 Gambar 4.28 Gagal menampilkan menu Daftar Alamat ....................................... 75 Gambar 4.29 Gagal menampilkan menu Daftar Alamat ....................................... 75 Gambar 4.30 Berhasil menampilkan menu Daftar Tujuan ................................... 75 Gambar 4.31 Gagal memproses perhitungan jarak antar lokasi ........................... 75 Gambar 4.32 Berhasil memproses perhitungan jarak antar lokasi ........................ 76 Gambar 4.33 Berhasil menampilkan rute dan lokasi pengguna ............................ 76 Gambar 4.34 Semua lokasi tujuan telah dikunjungi ............................................. 76 Gambar 4.35 Konfirmasi apakah ingin menambah catatan .................................. 76 Gambar 4.36 Menampilkan catatan yang disimpan untuk diperbarui .................. 76 Gambar 4.37 Konfirmasi apakah ingin menutup aplikasi..................................... 76 Gambar 4.38 Rute Perjalanan Pertama Untuk 5 Lokasi Tujuan ........................... 81 Gambar 4.39 Rute Perjalanan Kedua dan Ketiga.................................................. 81 Gambar 4.40 Rute Perjalanan Keempat dan Kelima ............................................ 81 Gambar 4.41 Rute Perjalanan Terakhir ................................................................. 81 Gambar 4.42 Hasil Uji Coba Ukuran Populasi .................................................... 84 Gambar 4.43 Hasil Uji Coba Maksimal Generasi ................................................. 84 Gambar 4.44 Hasil Uji Coba Kombinasi Pc dan Pm ............................................ 84 Gambar 4.45 Rute Perjalanan Pertama Untuk 7 Lokasi Tujuan ........................... 87 Gambar 4.46 Rute Perjalanan Kedua dan Ketiga.................................................. 87 Gambar 4.47 Rute Perjalanan Keempat dan Kelima ............................................ 87 Gambar 4.48 Rute Perjalanan Keenam dan Ketujuh ............................................ 88 Gambar 4.49 Rute Perjalanan Terakhir (Kembali ke Lokasi Awal) ..................... 88 Gambar 4.50 Rute Perjalanan Pertama dan Rute Perjalanan Kedua ..................... 90 Gambar 4.51 Rute Perjalanan Ketiga dan Rute Perjalanan Keempat ................... 90 Gambar 4.52 Rute Perjalanan Kelima dan Rute Perjalanan Terakhir (Kembali ke Lokasi Awal) ......................................................................................................... 90

SKRIPSI

xv RANCANG BANGUN SISTEM…

GALIH G. A.


DAFTAR TABEL Tabel 2.1 Populasi Kromosom .............................................................................. 18 Tabel 2.2 Contoh kromosom hasil encoding......................................................... 19 Tabel 2.3 Contoh kromosom dengan nilai fitness-nya .......................................... 21 Tabel 4.1 Daftar Kunjungan Kurir (7 Lokasi Tujuan) .......................................... 40 Tabel 4.2 Kumpulan Data Alamat (1 Lokasi Awal dan 5 Lokasi Tujuan) ........... 40 Tabel 4.3 Data Jarak Antar Titik ........................................................................... 42 Tabel 4.4 Parameter Algoritma Genetika.............................................................. 42 Tabel 4.5 Kromosom Hasil Encoding ................................................................... 43 Tabel 4.6 Kumulatif dari Probabilitas, Nilai acak [0, 1], Calon induk Crossover 48 Tabel 4.7 Bilangan acak R dan hasil proses seleksi untuk crossover ................... 48 Tabel 4.8 Kumulatif dari Probabilitas, Nilai acak [0, 1], Calon induk mutation .. 49 Tabel 4.9 Bilangan acak R dan hasil proses seleksi untuk mutation .................... 49 Tabel 4.10 Hasil Offspring dari crossover ............................................................ 51 Tabel 4.11 Hasil Offspring dari mutation ............................................................. 52 Tabel 4.12 Penggabungan populasi awal, anak crossover, anak mutation, dan nilai fitness.................................................................................................. 53 Tabel 4.13 Hasil penggabungan populasi berdasarkan nilai fitness-nya............... 54 Tabel 4.14 Populasi untuk Generasi Berikutnya ................................................... 54 Tabel 4.15 Kromosom terbaik dari populasi ......................................................... 55 Tabel 4.16 Pengujian Sistem dengan Black Box Testing ...................................... 70 Tabel 4.17 Uji Coba Pengujian Ukuran Populasi ................................................. 80 Tabel 4.18 Uji Coba Pengujian Maksimal Generasi ............................................. 80 Tabel 4.19 Uji Coba Pengujian Pc dan Pm ........................................................... 80 Tabel 4. 20 Uji Coba Pengujian Ukuran Populasi ................................................ 81 Tabel 4.21 Uji Coba Pengujian Maksimal Generasi ............................................. 85 Tabel 4.22 Uji Coba Pengujian Pc dan Pm ........................................................... 85 Tabel 4.23 Daftar Alamat Secara Acak................................................................. 89

SKRIPSI

xvi RANCANG BANGUN SISTEM…

GALIH G. A.


DAFTAR LAMPIRAN Lampiran 1 : Outline Wawancara dengan kurir Lampiran 2 : Kuesioner Evaluasi Sistem Lampiran 3 : Wawancara untuk Pengambilan Data Daftar Kunjungan Kurir

SKRIPSI

xvii RANCANG BANGUN SISTEM…

GALIH G. A.


BAB I PENDAHULUAN 1.1

Latar Belakang Melihat semakin pesatnya perkembangan teknologi dalam dunia bisnis

sekarang ini, perusahaan-perusahaan berusaha untuk mampu bersaing dengan perusahaan lainnya. P.T. Sun Star Motor cabang Surabaya merupakan perusahaan bisnis yang bergerak dalam bidang jasa penjualan otomotif sejak tahun 1974, P.T. Sun Star Motor sudah mempunyai banyak cabang di kota-kota besar di Indonesia, seperti di Jakarta, Semarang, Solo, Malang, Denpasar, dan Surabaya. P.T. Sun Star Motor cabang Surabaya mempunyai banyak karyawan dengan berbagai macam divisi / bagian yang ada, salah satunya adalah kurir. Kurir dalam P.T. Sun Motor bukan untuk mengantar barang seperti halnya di perusahaan lain, melainkan, kurir membantu seorang salesman untuk mengambil kelengkapan administrasi pelanggan yang belum diberikan. Salesman dalam P.T. Sun Star Motor dibagi menjadi 2 bagian sales force dan sales counter. Tugas seorang sales force adalah memasarkan produk perusahaan di luar kantor, atau dengan kata lain memasarkan produk dengan mengunjungi tempat satu ke tempat yang lain (door to door), sedangkan sales counter melayani pelanggan yang datang langsung ke kantor untuk membeli atau hanya menanyakan produk perusahaan yang dijual, dengan kata lain sales counter tidak boleh keluar kantor atau memasarkan produk diluar kantor pada saat jam kerja.

SKRIPSI

1 RANCANG BANGUN SISTEM…

GALIH G. A.


2

Dengan begitu, tugas seorang kurir sangat membantu bagi sales counter, yang dimana jika pelanggan belum memenuhi persyaratan administrasi dengan lengkap, maka pelanggan tidak perlu mengunjungi ke P.T. Sun Star Motor yang hanya untuk melengkapi syarat administrasi tersebut. Karena akan ada kurir yang mengunjungi tempat pelanggannya, dimana dalam hal ini tempat atau tujuan kurir tidak hanya satu tempat melainkan beberapa tempat setiap harinya sesuai dengan permintaan sales counter. Dan cukup dikunjungi satu kali untuk setiap pelanggannya. Apabila terdapat 9 tempat/tujuan yang akan dikunjungi oleh kurir, maka terdapat 40.320 jalur yang mungkin. Hal ini yang menyebabkan kurir harus dapat mengatur urutan kunjungannya agar memperoleh jarak yang seminimum mungkin. Permasalahan yang sering terjadi adalah kurir terkadang menempuh jarak yang jauh dan terlalu berputar-putar untuk mengunjungi satu tempat ke tempat lainnya. Hal ini yang menyebabkan kurir menjadi kurang efisien dalam mengunjungi urutan tempat yang ingin ditujunya. Hal ini sesuai dengan problematika masalah Travelling Salesman Problem (TSP), menurut (Sadiq, 2012), TSP merupakan sebuah kategori dalam masalah optimasi kombinatorial. Masalah optimasi kombinatorial adalah masalah yang berusaha untuk menemukan sebuah obyek yang optimal dari himpunan obyek. Dalam permasalahan ini, tujuannya adalah untuk mengoptimalkan dari sebuah perjalanan keliling (jalan untuk mengunjungi kota) dengan diberikan semua kemungkinan jalur. Dalam pengertian ini, perjalanan keliling yang optimal adalah perjalanan dengan jarak yang minimal. Secara komputasi, TSP sulit untuk dipecahkan dengan sejumlah kota yang banyak sebagaimana meningkatnya waktu

SKRIPSI


GALIH G. A.


3

penyelesaian secara eksponensial untuk setiap bertambahnya dalam N. Dimana N dalam hal ini adalah jumlah kota. Pada penelitian ini menggunakan metode heuristik yang merupakan suatu metode untuk menemukan penyelesaian masalah optimasi sebatas dalam kadar cukup baik dan masuk akal untuk diterima. Walaupun penyelesaian yang ditemukan bukanlah terbaik, tetapi sudah dapat untuk diterima karena sudah mencapai kadar 90 persen daripada penyelesaian optimum. (Zukhri, 2014). Algoritma genetika merupakan sebuah algoritma yang meniru cara kerja proses genetika pada makhluk hidup, dimana terdapat proses seleksi, rekombinasi dan mutasi untuk mendapatkan kromosom terbaik pada suatu generasi. Dengan meniru teori evolusi, algoritma genetika dapat digunakan untuk mencari solusi permasalahan-permasalahan dalam dunia nyata. Sebelum algoritma dapat dijalankan, maka sebuah kode yang sesuai untuk permasalahan harus dirancang. Untuk masalah ini maka solusi yang layak dalam ruang permasalahan dikodekan dalam bentuk kromosom yang terdiri atas komponen genetika terkecil yaitu gen. Dengan teori evolusi dan teori genetika, di dalam penerapan algoritma genetika melibatkan beberapa operator, yaitu reproduksi, crossover, dan mutasi. Sebelumnya, penerapan algoritma genetika pada permasalahan Travelling Salesman Problem pernah dilakukan oleh Lukas pada tahun 2005 yang berjudul Penerapan Algoritma Genetika Untuk Travelling Salesman Problem Dengan Menggunakan Metode Order Crossover Dan Insertion Mutation penerapannya dilakukan menggunakan Desktop. Pada penelitian tersebut bertujuan untuk mengetahui bagaimana algoritma genetik dapat menyelesaikan masalah Travelling

SKRIPSI


GALIH G. A.


4

Salesman Problem dengan menggunakan metode order crossover dan insertion mutation yang digunakan pada algoritma genetik. Pada perancangan sistem yang akan dibuat, Sistem Informasi Geografis (SIG) berperan dalam penyampaian informasi kepada pengguna. Dengan menggunakan SIG sebagai media penyampaian informasi kepada pengguna, sistem juga dapat memberikan informasi mengenai jarak yang akan ditempuh, dapat membuat visualisasi rute yang akan ditempuh melalui SIG. Data yang akan diolah menjadi informasi ini adalah data geografis yaitu titik koordinat awal, dan beberapa titik koordinat tujuan. Berdasarkan permasalahan yang telah dijabarkan tersebut, diharapkan dengan dibuatnya sistem ini dapat membantu permasalahan yang terjadi pada kurir PT. Sun Motor. Dan diharapkan sistem dapat membantu pengguna dalam menentukan urutan kunjungan yang akan dituju dengan jarak yang sub-optimal khususnya di wilayah Surabaya. 1.2

Rumusan Masalah Berdasarkan latar belakang, maka rumusan masalah dari penelitian ini adalah

bagaimana membuat suatu aplikasi Sistem Pendukung Keputusan dengan melibatkan Algoritma Genetika yang digunakan untuk membantu menyelesaikan persoalan Travelling Salesman Problem Berbasis Sistem Informasi Geografis pada kurir perusahaan di PT. Sun Motor cabang Surabaya? 1.3

Tujuan Adapun tujuan yang ingin diperoleh dalam penelitian ini adalah dengan

membuat suatu aplikasi Sistem Pendukung Keputusan yang melibatkan Algoritma

SKRIPSI


GALIH G. A.


5

Genetika yang digunakan untuk membantu menyelesaikan persoalan Travelling Salesman Problem Berbasis Sistem Informasi Geografis pada kurir perusahaan di PT. Sun Motor cabang Surabaya. 1.4

Manfaat Dalam pembuatan sistem ini memberikan manfaat kepada pengguna

diantaranya adalah: 1.

Memberikan informasi kepada pengguna tentang informasi total jarak yang akan ditempuh.

2.

Memberikan output kepada pengguna berupa urutan tempat yang akan dikunjungi.

1.5

Batasan Masalah 1.

Rute yang digunakan adalah rute untuk wilayah kota Surabaya.

2.

Faktor-faktor yang diperhatikan adalah jarak.

3.

Jarak yang digunakan berasal dari perhitungan Google Maps dan jalur yang dipilih berdasarkan dari anjuran Google Maps.

4.

Komponen algoritma genetika yang digunakan adalah roulette wheel untuk tahap seleksi, order crossover untuk tahap pindah silang, swap mutation untuk tahap mutasi.

SKRIPSI


GALIH G. A.


BAB II TINJAUAN PUSTAKA 2.1

Konsep Sistem Informasi Menurut (Indrakarna, Sutanto, & Taufik, 2012), definisi sistem dapat dibagi

menjadi dua pendekatan, yaitu pendekatan secara prosedur dan pendekatan secara komponen. Berdasarkan pendekatan prosedur, sistem didefinisikan sebagai kumpulan dari beberapa prosedur yang mempunyai tujuan tertentu. Sedangkan berdasarkan pendekatan komponen, sistem merupakan kumpulan dari komponenkomponen yang saling berkaitan mencapai tujuan tertentu. Data adalah fakta-fakta atau kejadian-kejadian yang dapat berupa angkaangka atau kode-kode tertentu. Data masih belum mempunyai arti bagi penggunanya. Untuk dapat arti data diolah sedemikian rupa sehingga dapat digunakan oleh penggunanya. Hasil pengolahan data inilah yang disebut sebagai informasi. Secara ringkas, informasi adalah data yang telah diolah dan mempunyai arti bagi penggunanya. Sehingga sistem informasi dapat didefinisikan sebagai prosedur-prosedur yang digunakan untuk mengolah data sehingga dapat digunakan oleh penggunanya. (Indrakarna, Sutanto, & Taufik, 2012). 2.2

Google Maps Menurut (Ichtiara, 2008), Google Maps adalah layanan mapping online yang

disediakan

oleh

google.

Layanan

ini

dapat

diakses

melalui

situs

http://maps.google.com. Pada situs tersebut dapat melihat informasi geografis pada hampir semua wilayah di bumi. Layanan yang interaktif, karena di dalamnya peta dapat digeser sesuai keinginan pengguna, mengubah tingkat zoom,

SKRIPSI


GALIH G. A.


7

Serta mengubah tampilan peta. Tampilan yang akan muncul pada situs Google Maps dapat dilihat pada Gambar 2.1.

Gambar 2.1 Tampilan Google Maps Fasilitas yang terdapat pada Google Maps diantaranya adalah menjelajah peta, mencari lokasi tertentu, seperti hotel, perusahaan, tempat hiburan, dll. Google Maps juga menyediakan beberapa mode pada tampilan petanya. Pada gambar berikut, dapat dilihat tampilan dengan mode map. Mode map merupakan bentuk dasar, yang didalamnya terdapat informasi mengenai nama jalan, sungai, danau, dan lain-lain. Dapat dilihat pada gambar 2.2 2.3

Google Maps API API atau Application Programming Interface merupakan suatu dokumentasi

yang terdiri dari interface, fungsi, kelas, struktur dan sebagainya untuk membangun sebuah perangkat lunak. Dengan adanya API ini, maka memudahkan programmer untuk membongkar suatu software untuk kemudian dapat dikembangkan atau diintegrasikan dengan perangkat lunak lain.

SKRIPSI


GALIH G. A.


8

Gambar 2.2 Tampilan Map View Google Maps API dapat dikatakan sebagai penghubung suatu aplikasi dengan aplikasi lainnya yang memungkinkan programmer menggunakan system function. Proses ini dikelola melalui operating system. Keunggulan dari API ini adalah memungkinkan suatu aplikasi dengan aplikasi lainnya dapat saling berhubungan dan berinteraksi. Bahasa pemrograman yang digunakan oleh Google Maps terdiri dari HTML, Javascript, dan AJAX serta XML. Memungkinkan untuk menampilkan peta Google Maps di website lain. (Nughroho, 2011). Dengan menggunakan Google Maps API, Google Maps dapat ditampilkan pada website/aplikasi eksternal. Agar aplikasi Google Maps dapat muncul di project tertentu, diperlukan adanya APIkey. APIkey merupakan kode unik yang digenerasikan untuk suatu website atau aplikasi tertentu, agar server Google Maps dapat mengenali proyek tersebut. 2.4

Android Android adalah sistem operasi untuk telepon seluler yang berbasiskan linux.

Android menyediakan platform terbuka bagi pengembang untuk menciptakan berbagai macam aplikasi oleh beragam peranti bergerak. Untuk mengembangkan Android agar lebih baik lagi, oleh Google yang sebelumnya membeli Android Inc.

SKRIPSI


GALIH G. A.


9

dibentuklah Open Handset Alliance yang kemudian Open Handset Alliance mendukung dikembangkannya lagi standar terbuka di perangkat seluler. Tidak hanya itu saja, Google juga merilis kode-kode Android di bawah lisesnsi Apache, sebuah lisensi perangkat lunak dan standar terbuka perangkat seluler (Pratiwi, Shiddiqi, & Pratomo, 2012). Dalam pembuatan aplikasi ini, versi Android yang digunakan adalah Android versi 4.1.2. Versi ini telah memenuhi standar untuk aplikasi yang akan dibuat karena sudah mendukung Google Maps API yang dimana Google Maps API ini berfungsi agar pengguna dapat melihat posisi keberadaannya yang ditampilkan pada peta dan untuk menghitung jarak. 2.5

Sistem Informasi Geografi Menurut (Husein, 2007), SIG (Sistem Informasi Geografis) merupakan

sistem yang mengorganisir perangkat keras (hardware), perangkat lunak (software), dan data, serta dapat mendaya-gunakan sistem penyimpanan, pengolahan, maupun analisis data secara simultan, sehingga dapat diperoleh informasi yang berkaitan dengan aspek keruangan. SIG merupakan manajemen data spasial dan non-spasial yang berbasis komputer dengan tiga karakteristik dasar, yaitu: 1. Mempunyai fenomena aktual (variabel data non-lokasi) yang berhubungan dengan topik permasalahan di lokasi bersangkutan, 2. Merupakan suatu kejadian di suatu lokasi, 3. Mempunyai dimensi waktu. Menurut (Kurniawan, 2010) menyatakan bahwa komponen Sistem Informasi Geografis terbagi menjadi empat, sebagai berikut:

SKRIPSI


GALIH G. A.


1.

10

Perangkat Keras (Hardware) Sistem Informasi Geografis membutuhkan komputer untuk menyimpan data dan dalam melakukan pengolahan data. Semakin kompleks data yang ingin diolah, maka semakin besar juga kebutuhan memori dan kecepatan pengolah datanya.

2.

Perangkat Lunak (Software) Perangkat

lunak

dibutuhkan untuk

memasukkan, menyimpan dan

mengeluarkan data bila diperlukan. Perangkat lunak Sistem Informasi Geografis harus memiliki beberapa elemen seperti mampu melakukan input dan transformasi data geografis, sistem manajemen basis data, mampu mendukung query geografis, analisis dan visualisasi, dan memiliki Graphical User Interface (GUI) untuk memudahkan akses. 3.

Data Dalam SIG semua data dasar geografis harus diubah terlebih dahulu ke dalam bentuk digital untuk memudahkan dalam pengolahan data. Data dalam SIG dibagi menjadi dua bentuk yakni geographical atau data spasial, dan data atribut. Menurut (Kurniawan, 2010), data spasial adalah data hasil pengukuran, pencatatan dan pencitraan terhadap suatu unsur keruangan yang berada di bawah atau di atas permukaan bumi dengan posisi keberadaannya mengacu pada sistem koordinat nasional. Menurut (Kurniawan, 2010), data atribut adalah gambaran data yang terdiri dari informasi yang relevan terhadap suatu lokasi seperti kedalaman, ketinggian, lokasi penjualan dan lain-lain dan bisa dihubungkan dengan lokasi tertentu dengan maksud untuk

SKRIPSI


GALIH G. A.


11

memberikan identifikasi seperti alamat, kode pos, dan lain-lain. Dalam penelitian ini data yang digunakan adalah data spasial. Beberapa data spasial menurut (Nalloh, Sunandar, & Dimitra, 2013): a.

Titik Titik

merupakan

representasi

grafis

yang

paling

sederhana.

Representasi ini tidak memiliki dimensi tetapi dapat diidentifikasi di atas peta dan dapat ditampilkan pada layar monitor. Pada skala tertentu biasanya titik digunakan untuk menggambarkan letak suatu kota, letak suatu bangunan atau objek-objek lainnya. Format titik memiliki ciri-ciri yaitu koordinat tunggal, tanpa panjang, tanpa luasan. Contoh dari format titik: lokasi kecelakaan, letak pohon, lokasi gedung. Tipe data titik dapat dilihat pada Gambar 2.3.

Gambar 2.3 Tipe Data Titik Pada Google Maps setiap titik memiliki koordinat yang berfungsi untuk menentukan lokasi titik berada. Misalnya letak Kantor PT. Sun Star Motor dapat di tunjukkan pada Google Maps dengan koordinat -7.28197, 112.74695 dapat dilihat pada Gambar 2.4. b.

Garis Garis merupakan bentuk linier yang akan menghubungkan beberapa

titik atau paling sedikit dua titik. Biasanya digunakan untuk menggambarkan suatu objek berdimensi satu. Contoh penggunaan garis pada SIG adalah jaringan jalan, jaringan saluran air, jaringan telepon dan lain sebagainya. Format garis memiliki ciri-ciri yaitu koordinat titik awal dan akhir,

SKRIPSI


GALIH G. A.


12

mempunyai panjang, tanpa luasan. Tipe data garis dapat dilihat pada Gambar 2.5. Misalnya Jalan Bali dapat ditunjukkan pada Google Maps dengan dimulai dari titik A dengan koordinat -7.27449, 112.74681 dan diakhiri dengan titik B dengan koordinat -7.27495, 112.7495 yang dapat dilihat pada Gambar 2.6

Gambar 2.4 Lokasi PT. Sun Star Motor di Jalan Ngagel, Surabaya

Gambar 2.5 Tipe Data Garis

Gambar 2.6 Lokasi Jalan Bali 4.

Manusia

SKRIPSI


GALIH G. A.


13

Manusia dibutuhkan untuk mengendalikan seluruh Sistem Informasi Geografis. Adanya koordinasi dalam Sistem Informasi Geografis sangat diperlukan agar informasi yang diperoleh menjadi benar, tepat, dan akurat. 2.6

Teori Graph Graph merupakan suatu cabang ilmu yang memiliki banyak terapan. Banyak

sekali struktur yang bisa direpresentasikan dengan graph, dan banyak masalah yang bisa diselesaikan dengan bantuan graph. Seringkali graph digunakan untuk merepresentasikan suatu jaringan. Misalkan, jaringan jalan raya dimodelkan graph dengan kota sebagai simpul (vertex/node) dan jalan yang menghubungkan setiap kotanya sebagai sisi (edge) yang bobotnya (weight) adalah panjang dari jalan tersebut. Misalkan simpul merepresentasikan kota, sisi merepresentasikan jalan yang memungkinkan, dan bobot dari setiap sisi adalah biaya yang dikeluarkan dalam perjalanan yang memungkinkan, dan bobot dari setiap sisi adalah jarak yang ditempuh dalam perjalanan tersebut. Graph G didefinisikan sebagai pasangan himpunan (V, E), ditulis dengan notasi G = (V, E), yang dalam hal ini V adalah himpunan tidak kosong dari simpul-simpul (vertices atau node) dan E adalah himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul. V tidak boleh kosong, sedangkan E boleh kosong. (Hayati & Yohanes, 2014). 2.7

Optimasi Kombinatorial Menurut (Neuman & Witt, 2010) masalah optimasi kombinatorial muncul

dalam beberapa aplikasi. Contohnya tugas untuk menemukan jalur terpendek dari Paris menuju Roma dalam jaringan jalan di Eropa atau penjadwalan ujian yang diberikan di universitas. Secara alami, masalah optimasi dapat dibagi menjadi 2

SKRIPSI


GALIH G. A.


14

kategori. Kategori pertama terdiri dari masalah dengan variabel yang kontinu (terus-menerus). Masalah tersebut terkenal pada pelajaran matematika di sekolah. Contoh

sedehana

untuk

menemukan

fungsi

minimum

dari

𝑓: 𝑅 →

𝑅 dengan 𝑓(𝑥) = 𝑥 2 . Hal ini jelas bahwa x0 = 0 ini adalah solusi yang unik dari masalah ini. Dalam masalah optimasi kombinatorial, salah satu bertujuan meminimalkan atau memaksimalkan fungsi tujuan tertentu dibawah himpunan kendala. Secara formal, masalah optimasi kombinatorial dapat didefinisikan sebagai (𝑆, 𝑓, Ω) dimana S sebagai ruang pencarian, 𝑓 sebagai fungsi obyektif, yang harus dimaksimalkan atau diminimalkan dan Ω sebagai himpunan kendala yang harus dipenuhi untuk mendapatkan solusi yang layak. Tujuannya untuk menemukan solusi optimal secara global, pada kasus minimasi, mencoba untuk mendapatkan nilai obyektif yang terkecil pada kondisi bahwa semua kendala terpenuhi. 2.8

Travelling Salesman Problem Menurut (Hingrajiya, Gupta, & Chandel, 2012) Travelling Salesman Problem

(TSP) adalah sebuah masalah bagaimana menemukan sebuah tur terpendek dimana semua kota yang diberikan untuk dikunjungi. TSP adalah masalah yang terkenal dan secara ekstensif studi kasus yang tidak dapat diuraikan atau optimasi kombinatorial dan meminta perjalanan pulang pergi terpendek dengan jumlah biaya yang minimal untuk mengunjungi tiap kota (node) yang telah diberikan tepatnya satu kali. TSP merupakan sebuah masalah NP-hard dan begitu mudah untuk mendeskripsikan dan begitu sulit untuk diselesaikan. Definisi dari TSP, diberikan N kota, jika seorang sales memulai dari rumah kotanya untuk mengunjungi tiap

SKRIPSI


GALIH G. A.


15

kota tepat satu kali dan kemudian kembali ke rumah, cari urutan dari tur sehingga total jarak (biaya) perjalanan adalah minimum. Biaya bisa menjadi jarak, waktu, energi, dll. Sebuah graf berbobot lengkap G = (N, E) dapat di gunakan untuk menggambarkan sebuah TSP, dimana N adalah kota dan E adalah sisi (jalur) yang secara lengkap menghubungkan semua kota. Setiap sisi (i,j) E adalah menerangkan biaya dij, dimana jarak antara kota i dan j. Menurut (Suyanto, 2014), TSP dibagi menjadi 2 yaitu TSP asimetris dan simetris. Pada TSP simetris, biaya dari kota 1 ke kota 2 sama dengan biaya dari kota 2 ke kota 1. Sedangkan pada TSP asimetris, biaya dari kota 1 ke kota 2 tidak sama dengan biaya dari kota 2 ke kota 1. Untuk TSP asimetris, jumlah jalur yang mungkin adalah permutasi dari jumlah kota yang harus dilalui dibagi dengan jumlah kota yang harus dilalui. Hal ini dapat dipahami karena secara siklus, sebuah jalur dengan urutan 1-2-3 adalah sama dengan jalur 2-3-1 dan jalur 3-1-2. Tetapi jalur dengan 12-3 tidaklah sama dengan jalur 3-2-1. Untuk TSP asimetris jumlah jalur yang mungkin dapat diperoleh dengan menggunakan Persamaan 2.1: 𝑛 𝑃𝑘

=

𝑛! 𝑛

(2.1)

Keterangan: 𝑛 𝑃𝑘 = jumlah

n 2.9

jalur yang mungkin

= jumlah kota

Algoritma Genetika Menurut (Scrucca, 2013) Algoritma Genetika merupakan kelas dari algoritma

evolusioner yang dipopulerkan oleh John Hollan dan temannya selama tahun 1970an, dan telah diaplikasikan untuk pencarian keputusan atau solusi pendekatan untuk

SKRIPSI


GALIH G. A.


16

masalah pencarian dan optimasi. Algoritma genetika merupakan algoritma pencarian stochastic dimana yang dapat memecahkan masalah optimasi, baik untuk fungsi kontinyu (apakah terdiferensialkan atau tidak) dan fungsi diskrit. Algoritma Genetika menggunakan strategi evolusi yang terinspirasi dari prinsip dasar evolusi biologis. Pada tahap tertentu dari evolusi sebuah populasi terdiri dari sejumlah individu, yang disebut juga string atau kromosom. Ini terbuat dari unit (gen, fitur, karakter) yang mengatur warisan dari satu atau beberapa karakter gen dari karakter tertentu yang terletak sepanjang kromosom, dan posisi string yang sesuai disebut loci. Setiap genotipe akan menggambarkan sebuah potensial solusi untuk satu masalah. Variabel keputusan, atau phenotypes, dalam Algoritma Genetika diperoleh dengan mengaplikasikan beberapa pemetaan dari representasi ke dalam ruang variabel keputusan, yang dimana menggambarkan potensial solusi untuk sebuah masalah optimasi. Kecocokan fungsi decoding mungkin dibutuhkan untuk pemetaan kromosom ke dalam phenotypes. Fitness tiap individu dievaluasi dan individu yang terpilih direproduksi, untuk mewariskan informasi genetik kepada anak-anaknya. Dengan operator seleksi, Algoritma Genetika meniru perilaku alami dari organisme dalam lingkungan yang kompetitif, dimana yang paling berkualitas dan keturunan mereka yang bertahan hidup. Dua isu terpenting dalam proses evolusi pencarian Algoritma Genetika yaitu eksplorasi dan eksploitasi. Eksplorasi adalah menciptakan keragaman populasi dengan menjelajahi ruang pencarian, yang diperoleh dari operator genetika, seperti mutasi dan kawin silang. Kawin silang membentuk keturunan baru dari dua kromosom induk dengan menggabungkan masing-masing bagian informasi genetik. Mutasi adalah operator genetika yang

SKRIPSI


GALIH G. A.


17

secara acak mengubah nilai dari gen pada kromosom induk. Eksploitasi bertujuan mengurangi keragaman dalam populasi dengan memilih setiap tahap individu dengan fitness paling tinggi. Seringkali strategi elitis diterapkan, dengan individuindividu yang terbaik dipasang untuk bertahan di generasi berikutnya jika mereka tidak bertahan. Proses evolusi dihentikan atas dasar beberapa kriteria konvergensi. Yang sering digunakan adalah jumlah generasi yang didefinisikan. Secara alternatif, proses Algoritma Genetika dihentikan ketika telah mencapai sejumlah generasi tanpa adanya perbaikan nilai fitness terbaik. 2.9.1. Komponen-komponen dalam Algoritma Genetika Algoritma Genetika terdiri dari beberapa komponen yaitu sebagai berikut: 1.

Populasi Menurut (Sivanandam & Deepa, 2008), populasi adalah kumpulan dari

beberapa individu atau kromosom. Terdapat dua aspek yang penting pada populasi yang digunakan pada algoritma genetika, yaitu adalah inisiasi generasi populasi dan ukuran populasi. Untuk setiap masalah, ukuran populasi akan berpengaruh terhadap kompleksitas suatu masalah. Idealnya, populasi pertama harus mempunyai gen yang sebesar mungkin agar mampu mengeksplorasi ruang pencarian secara keseluruhan. Ukuran populasi juga dapat menimbulkan beberapa masalah juga. Populasi yang besar, akan lebih mudah untuk mengeksplorasi ruang pencarian. Menurut (Obitko, 1998), ukuran populasi yang terlalu besar tidak mempengaruhi performa dari algoritma genetika dalam hal ini berarti seberapa cepat algoritma genetika untuk menemukan sebuah solusi. Nilai yang direkomendasikan untuk

SKRIPSI


GALIH G. A.


18

ukuran populasi yang baik adalah bernilai antara 20 – 30 dalam satu populasi. Populasi hasil kombinasi dari berbagai kromosom dapat dilihat pada Tabel 2.1. Tabel 2.1 Populasi Kromosom Kromosom [1] BDEC Kromosom [2] BEDC Kromosom [3] EDCB Kromosom [4] BEDC 2.

Proses Encoding (Permutation Encoding) Menurut (Lukas, Anwar, & Yuliani, 2005), proses encoding adalah salah satu

proses yang sulit dalam algoritma genetika karena proses encoding untuk setiap permasalahan berbeda-beda karena tidak semua teknik encoding cocok untuk setiap permasalahan. Proses encoding menghasilkan string yang kemudian disebut kromosom. String terdiri dari sekumpulan bit. Bit ini dikenal sebagai gen. Jadi dalam satu kromosom terdiri dari sejumlah gen. Ada bermacam-macam teknik encoding yang dapat dilakukan dalam algoritma genetika. Beberapa teknik-teknik encoding antara lain binary encoding, permutation encoding, value encoding serta tree encoding. Teknik yang digunakan pada Travelling Salesman Problem adalah permutation encoding. Selain digunakan pada Travelling Salesman Problem, teknik ini juga dapat digunakan pada Task Ordering Problem. Pada permutation encoding, kromosom-kromosom adalah kumpulan angka yang mewakili posisi dalam sebuah rangkaian. Pada Travelling Salesman Problem, kromosom mewakili urutan kota yang dikunjungi salesman. Menurut (Zukhri, 2014), populasi awal dibentuk dari kromosom sebanyak ukuran populasi (UkPop). Setiap kromosom menyatakan urutan kota yang harus dikunjungi oleh salesman, maka representasi kromosom yang paling sederhana untuk menyelesaikan masalah TSP adalah dalam bentuk

SKRIPSI


GALIH G. A.


19

permutasi dari indeks kota dan dapat dinyatakan sebagai vektor v, vi = [g1, g2, …, gn] dengan 1≤ i ≤ UkPop. Contoh pengkodean untuk TSP dapat dilihat pada Tabel 2.2. Tabel 2.2 Contoh kromosom hasil encoding Kromosom [1] BDEC Kromosom [2] BEDC 3.

Evaluasi dan Seleksi (Roulette Wheel) Menurut (Baharuddin, Shididiqi, & Pratomo, 2012), di dalam algoritma

genetika, individu yang bernilai fitness tinggi akan bertahan hidup. Sedangkan individu yang bernilai fitness rendah akan mati. Pengertian nilai fitness adalah nilai yang menyatakan baik tidaknya suatu solusi (individu). Algoritma genetika bertujuan untuk mencari individu dengan nilai fitness yang paling tinggi. Umumnya kromosom yang memiliki fitness tinggi akan bertahan dan berlanjut ke generasi berikutnya. Kromosom yang telah terbentuk akan berevolusi secara berkelanjutan yang disebut dengan generasi. Kromosom yang telah diketahui sebelumnya akan dicari nilai fitness masing – masing. Nilai fitness didapatkan dari jumlah perhitungan nilai dari tour yang telah di bentuk di dalam kromosom. Menurut (Fitrah, Zaky, & Fitrasani, 2006), karena pada TSP merupakan masalah pencarian nilai minimum, maka fungsi fitness menggunakan Persamaan 2.2.

𝐹(𝑣) =

1 𝑓(𝑣)

(2.2)

Keterangan: 𝐹(𝑣) = Fungsi fitness

SKRIPSI


GALIH G. A.

20


Pada tahap ini, 𝑓(𝑣) merupakan nilai panjang ruas jalan setiap rute. Sehingga 𝑓(𝑣) dihitung dengan Persamaan 2.3:

𝑓(𝑣) = ∑𝑛𝑖=1 𝑥𝑖

(2.3)

Keterangan: 𝑓(𝑣)

= nilai fitness

𝑥𝑖

= panjang ruas jalan Sebelum memasuki tahap seleksi (roulette wheel), maka harus diketahui

nilai probabilitas dari tiap kromosom, yang dapat menggunakan Persamaan 2.4: 𝐹(𝑖)

𝑃[𝑖] = ∑

𝐹(𝑖)

(2.4)

Keterangan: 𝑃[𝑖]

= Probabilitas tiap kromosom

𝐹(𝑖)

= Fungsi fitness

∑ 𝐹(𝑖) = Total nilai keseluruhan dari fungsi fitness (𝐹(𝑖)) Dalam tahap seleksi akan menentukan individu-individu mana saja yang akan dipilih untuk dilakukan rekombinasi dan bagaimana kromosom anak terbentuk dari individu-individu terpilih tersebut. Metode seleksi yang akan digunakan pada penelitian ini adalah roulette-wheel. Sesuai dengan namanya, metode ini menirukan permainan roulette-wheel dimana masing-masing individu menempati potongan lingkaran pada roda-roulette secara proposional sesuai dengan nilai fitness-nya. Kromosom yang mengalami proses evaluasi diharapkan menghasilkan solusi paling optimal. Contoh kromosom dengan nilai fitness-nya dapat dilihat pada Tabel 2.3. Metode ini mudah digunakan, langkah pertama yang dilakukan adalah membuat interval nilai kumulatif dari perhitungan probabilitas menggunakan

SKRIPSI


GALIH G. A.


21

persamaan (2.4) dalam interval [0,1]. Sebuah kromosom akan terpilih jika bilangan random yang dibangkitkan berada dalam interval akumulatifnya. Pada Gambar 2.7, K 1 menempati interval nilai kumulatif [0; 0,25], K 2 berada dalam interval (0,25; 0,75), K 3 dalam interval (0,75; 0,875), dan K 4 dalam interval (0,875; 1). Misalkan, jika bilangan random yang dibangkitkan adalah 0,6 maka kromosom K 2 terpilih sebagai orang tua. Tetapi jika bilangan random yang dibangkitkan adalah 0,99 maka kromosom K 4 yang terpilih. (Atiyatna, 2012). Tabel 2.3 Contoh kromosom dengan nilai fitness-nya Kromosom Nilai Fitness K1 1 K2 2 K3 0,5 K4 0,5 Jumlah 4

Gambar 2.7 Contoh roulette-wheel dari tabel 2.2 Dari pernyataan yang telah dijelaskan sebelumnya, menurut (Zukhri, 2014) ketentuan dalam terpilihnya kromosom dapat pula ditulis menjadi Persamaan 2.5.

Kromosom pertama yang terpilih, jika 𝑟 < 𝑃[1]. Kromosom ke-i yang terpilih, jika 𝑃[𝑖 − 1] ≤ 𝑟 < 𝑃[𝑖] dan 𝑖 > 1. 4.

(2.5)

Pindah Silang (Order Crossover)

SKRIPSI


GALIH G. A.


22

Menurut (Atiyatna, 2012), pindah silang (Crossover) dilakukan atas 2 kromosom untuk menghasilkan kromosom anak (offspring). Kromosom anak yang terbentuk akan mewarisi sebagian sifat kromosom induknya. Crossover dalam penelitian ini menggunakan skema order crossover. Pada crossover ada satu parameter yang penting yaitu peluang crossover (pc). Menurut (Obitko, 1998), merekomendasikan bahwa nilai pc secara umum harus bernilai tinggi untuk beberapa masalah sebesar 60% (0,6). Pc menunjukkan rasio dari offspring yang dihasilkan dalam tiap generasi dengan ukuran populasi. Misalkan ukuran populasi (popsize = 100), sedangkan peluang crossover (pc= 0,25), maka diharapkan ada 25 kromosom dari 100 kromosom yang ada pada populasi tersebut akan mengalami crossover. Menurut (Fitrah, Zaky, & Fitrasani, 2006), sebelum melakukan order crossover, langkah yang dilakukan adalah membangkitkan bilangan acak R sebanyak jumlah kromosom dalam populasi. Kemudian kromosom ke-i dapat dipilih sebagai induk tetapi dengan syarat R[i] < pc. Setelah melakukan pemilihan induk, proses selanjutnya adalah menentukan posisi gen yang akan di-crossover. Menurut (Gen, Cheng, & Lin, 2008), langkah awal pada order crossover adalah membangkitkan dua bilangan acak. Kemudian gen pada induk (parent) pertama yang berada diantara kedua bilangan acak akan disalin ke anak (offspring) dengan posisi yang sama. Langkah berikutnya untuk mendapatkan offspring pertama adalah membandingkan gen yang berada pada parent kedua dengan offspring pertama, yang dimulai dari posisi gen yang pertama sampai dengan posisi gen yang terakhir. Apabila gen tersebut ada pada offspring pertama maka abaikan gen

SKRIPSI


GALIH G. A.


23

tersebut dari kromosom itu. Jika tidak ada, maka gen tersebut dimasukkan ke dalam gen offspring yang masih belum terisi secara berurutan mulai dari kiri hingga kanan. Sebagai contoh, bilangan acak 1= 2, bilangan acak 2=3. Dengan kromosom induk pertama dan kedua mempunyai gen sebagai berikut: Induk 1 = ( 2 3 4 5 6 ) ; Induk 2 = ( 4 5 6 2 3 ) Kemudian, gen ke-2 dan ke-3 pada induk pertama akan diduplikasi ke kromosom anak sesuai dengan gen yang sama. Sehingga kromosom anak menjadi: Induk 1 X Induk 2 Anak 23456 X 45623 = 03400 Gen anak yang masih kosong diisi dengan induk 2, sehingga kromosom anak menjadi: Induk 1 23456 5.

X X

Induk 2 45623

=

Anak 53462

Mutasi (Swap Mutation) Jumlah kromosom yang mengalami mutation dalam satu populasi ditentukan

oleh parameter probabilitas mutasi atau mutation rate (Pm). Menurut (Obitko, 1998), nilai Pm harus mempunyai nilai yang rendah antara 0,5% - 1% (0,05 – 0,1). Pada penelitian ini menggunakan skema swap mutation, sebagai proses mutation. Langkah yang dilakukan pada swap mutation adalah dengan cara memilih 2 posisi gen dalam kromosom secara acak, kemudian 2 posisi gen tersebut saling ditukarkan (Gen, Cheng, & Lin, 2008). Misalnya suatu kromosom {2, 3, 4, 1, 5, 6} dapat termutasi menjadi {4, 3, 2, 1, 5, 6}. Dalam hal ini gen ke-1 dan ke-3 dipilih secara acak, yang kemudian saling ditukarkan. Untuk memilih kromosom yang mengalami mutation dapat dilakukan dengan cara membangkitkan bilangan acak (R[i]) dengan nilai antara 0 – 1 sebanyak dari

SKRIPSI


GALIH G. A.


24

parameter ukuran populasi. Kemudian, bilangan acak yang sudah dibangkitkan, dibandingkan dengan pm. Jika bilangan acak kurang dari pm, maka kromosom tersebut akan mengalami mutasi, apabila tidak ada kromosom yang mengalami mutasi maka tidak akan mendapatkan anak hasil dari mutasi. 6.

Penggantian Populasi Menurut (Sastry, Goldberg, & Kendall, 2005), penggantian populasi

dilakukan setelah keturunan baru dibuat menggunakan crossover dan mutation, perlu untuk memperkenalkan kedalam populasi lama. Kromosom induk dipilih berdasarkan nilai fitness-nya, sehingga yang diharapkan kromosom anak (offspring) lebih baik daripada kromosom induk. Pada tahap ini menggunakan steady-state untuk skema penggantian populasinya dengan cara mengurutkan kromosom parent dengan kromosom offspring berdasarkan nilai fitness-nya mulai dari yang terbaik sampai yang terburuk. Kromosom yang menempati urutan teratas akan menjadi populasi untuk generasi berikutnya, yang diambil sesuai dengan parameter ukuran populasi. 7.

Kriteria Penghentian Menurut (Suyanto, 2014), proses-proses pada Algoritma Genetika akan terus

berulang sampai mencapai suatu kriteria berhenti tertentu. Kriteria penghentian Algoritma Genetika yang digunakan adalah generations, yaitu Algoritma Genetika akan berhenti setelah mencapai batas generasi yang telah ditentukan, yang kemudian melaporkan individu dengan nilai fitness yang terendah sebagai solusi terbaik. 2.9.2. Langkah-langkah pada Algoritma Genetika

SKRIPSI


GALIH G. A.


25

Menurut (Sivanandam & Deepa, 2008) secara garis besar algoritma genetika dapat dilakukan dengan langkah-langkah sebagai berikut: 1.

Inisiasi Populasi, populasi acak sebanyak n kromosom (solusi untuk masalah),

2.

Evaluasi kromosom, menghitung evaluasi fitness tiap kromosom,

3.

Populasi baru, membuat populasi baru dengan mengulangi langkah-langkah berikut sampai populasi baru selesai. a.

Selection, pilih 2 kromosom induk dari populasi menurut nilai fitnessnya,

b.

Crossover, dengan Pc (crossover probability), kawin silangkan kromosom induk untuk membentuk kromosom anak. Jika tidak ada yang dikawin silangkan, kromosom anak sesuai dengan kromosom induk,

c.

Mutation, dengan Pm (mutation probability), mutasi gen tiap kromosom anak (posisi dalam kromosom),

d.

Accepting, kromosom anak menempati populasi baru,

4.

Replace, gunakan populasi baru untuk langkah algoritma selanjutnya,

5.

Test, jika kriteria penghentian sudah tercapai, berhenti dan menampilkan solusi yang terbaik/kromosom dengan nilai fitness yang terendah. Jika tidak, ulangi langkah ke-2.

2.10 JSON (JavaScript Object Notation) Menurut (Sriparasa, 2013), JSON (JavaScrit Object Notation) adalah format pertukaran data yang sangat populer yang dikembangkan oleh Douglas Crockford.

SKRIPSI


GALIH G. A.


26

JSON berbasis teks, ringan, dan formatnya mudah dibaca oleh manusia untuk pertukaran data antara klien dan server. JSON berasal dari JavaScript dan hampir sama dengan JavaScript objects, tetapi tidak tergantung dengan JavaScript. JSON merupakan bahasa-independen, dan dukungan format data JSON tersedia dalam semua bahasa pemrograman yang populer, seperti C#, PHP, Java, C++, Python, dan Ruby. JSON dapat digunakan pada aplikasi berbasis web untuk transfer data. Sebelum JSON, XML dipilih sebagai format pertukaran data. Untuk menguraikan XML diperlukan sebuah implementasi XML DOM pada sisi klien yang akan memperlambat respon XML, kemudian XPath digunakan untuk merespon query yang bertujuan untuk mengakses dan mengambil data. Secara umum, JSON digunakan untuk mentransmisikan data antara server dan aplikasi web. Jenis media internet yang resmi untuk JSON adalah aplikasi atau JSON. Format JSON sering digunakan untuk serialisasi dan mengirimkan data terstruktur melalui koneksi jaringan, terutama untuk melayani pengiriman data antara server dan aplikasi web sebagai alternatif dari XML.

SKRIPSI


GALIH G. A.


BAB III METODE PENELITIAN Metodologi penelitian merupakan cara atau prosedur besera tahapan-tahapan yang jelas dan sistematis untuk menyelesaikan suatu masalah yang sedang diteliti dengan landasan ilmiah. 3.1. Lokasi dan Waktu Penelitian Tempat yang digunakan pada penelitian adalah PT. Sun Star Motor yang lokasinya berada di Jalan Sulawesi nomor 33 – 37 Surabaya, Jawa Timur. Penelitian dilakukan mulai dari bulan November 2015 sampai dengan bulan April 2016. 3.2. Objek Penelitian Dalam penelitian ini yang menjadi subjek penelitian adalah peneliti, sedangkan yang menjadi objek penelitian adalah PT. Sun Star Motor cabang Surabaya. 3.3. Tahapan Penelitian Subbab ini menjelaskan alur pembangunan sistem. Tahapan pembangunan dalam penelitian dimulai dengan pengumpulan data dan informasi, pengolahan data dan informasi, perancangan sistem, dimana didalam perancangan sistem terdapat perancangan peta pada sistem informasi geografis, penentuan jarak optimal dengan Algoritma Genetika, implementasi sistem, pengujian sistem, dan evaluasi sistem. Bagan alur pembangunan sistem dapat dilihat pada Gambar 3.1.

SKRIPSI


GALIH G. A.


28

Pengumpulan data dan informasi melalui studi literatur dan wawancara

Analisis data hasil wawancara Pengolahan data dan informasi Penyelesaian Masalah dengan Algoritma Genetika Perancangan sistem Implementasi sistem Pengujian sistem Evaluasi sistem Gambar 3.1 Alur penelitian 3.4. Pengumpulan Data Dan Informasi Dalam penelitian ini dilakukan pendekatan kualitatif sehingga teknik pengumpulan data dan informasi yang digunakan adalah studi literatur dan wawancara. 1.

Studi literatur untuk mengetahui dan memahami lebih mendalam bagaimana Algoritma Genetika dapat menentukan jarak sub-optimal dalam Travelling Salesman Problem.

2.

Wawancara adalah merupakan suatu metode pengumpulan data dan informasi dengan cara bertanya langsung kepada pengguna. Wawancara

SKRIPSI


GALIH G. A.


29

dilakukan dengan seorang kurir PT. Sun Star Motor cabang Surabaya, pengumpulan data melalui wawancara tersebut bertujuan untuk: a.

Mengetahui kendaraan yang digunakan.

b.

Mengetahui titik awal dari perjalanan kurir.

c.

Kendala yang dihadapi oleh kurir

d.

Mengetahui jumlah tempat paling banyak yang pernah dikunjungi dalam satu hari.

3.

Pengambilan data daftar kunjungan kurir PT. Sun Star Motor melalui wawancara.

3.5. Pengolahan Data Dan Informasi Data yang telah terkumpul selanjutnya akan diproses melalui tahap pengolahan data. Pengolahan data dilakukan melalui kegiatan sebagai berikut: 1.

Hasil dari studi pustaka akan digunakan dalam langkah-langkah perhitungan Algoritma Genetika.

2.

Menganalisis hasil wawancara dan pengambilan data untuk menentukan data lokasi awal dan data lokasi tujuan. Data lokasi awal merupakan data yang menunjukkan lokasi awal dari perjalanan, beberapa data lokasi tujuan merupakan data yang menunjukkan lokasi tempat/tujuan yang dijadikan sebagai tujuan pengguna.

3.

Menganalisis hasil wawancara dan pengambilan data untuk melakukan penghitungan jarak antara lokasi awal dan beberapa lokasi tujuan menggunakan Google Maps guna memperoleh data input-an (data jarak) untuk penyelesaian masalah dengan Algoritma Genetika.

SKRIPSI


GALIH G. A.


30

3.6. Penyelesaian Masalah dengan Algoritma Genetika Proses analisis ini dilakukan dengan menggunakan Algoritma Genetika dengan menganalisis Algoritma Genetika, yaitu: 1.

Memasukkan data berupa jarak antar kota / tempat.

2.

Menginisiasi parameter Algoritma Genetika; ukuran populasi, pc, pm, dan maksimal generasi.

3.

Inisiasi populasi kromosom dengan setiap kromosomnya menyatakan urutan kota/tempat yang harus dikunjungi, teknik inisiasi ini menggunakan permutation encoding sebanyak ukuran populasi.

4.

Melakukan proses evaluasi kromosom, dengan menghitung nilai fitness dari tiap kromosom dengan Persamaan 2.3 yang telah dibuat,

5.

Melakukan penyeleksian kromosom dengan operasi seleksi menggunakan roulette wheel. a. Hitung nilai fungsi fitness di setiap kromosom dengan Persamaan 2.2. b. Hitung nilai probabilitas tiap kromosom dengan Persamaan 2.4. c. Membuat nilai kumulatif dari probabilitas dengan interval [0,1] d. Membuat bilangan acak riil r yang bernilai antara 0 sampai 1. e. Melakukan seleksi tiap kromosom dengan ketentuan Persamaan 2.5. f. Ulangi langkah “d” sampai n kali, dimana n adalah ukuran populasi. g. Maka akan terbentuk calon induk kromosom crossover. h. Melakukan proses seleksi untuk crossover, dengan cara membuat bilangan random (r) bernilai antara 0 sampai 1 sebanyak ukuran populasi,

SKRIPSI


GALIH G. A.


31

i. Membandingkan bilangan random (r) dengan probabilitas penyilangan (pc), j. Kromosom ke-i terpilih jika bilangan random ke-i kurang dari probabilitas penyilangan, k. Jika kromosom yang terpilih berjumlah genap, maka dapat dipasangkan satu sama lain. Jika kromosom yang terpilih berjumlah ganjil, maka kromosom yang paling akhir diabaikan/dibuang, l. Maka akan terbentuk induk kromosom untuk proses crossover, m. Untuk menentukan calon induk kromosom mutation, mengulangi langkah dari “d” hingga “f”. n. Maka akan terbentuk calon induk kromosom mutation. o. Kemudian melakukan proses seleksi untuk mutation, dengan cara membuat bilangan acak (R) antara 0 sampai dengan 1 sebanyak parameter dari ukuran populasi. p. Membandingkan bilangan acak (R) dengan probabilitas mutasi (pm), q. Kromosom ke-i terpilih jika bilangan random ke-i kurang dari probabilitas mutasi, r. Maka akan terbentuk induk kromosom untuk proses mutation. 6.

Dari hasil proses seleksi untuk crossover, dapat dilakukan operasi crossover menggunakan skema order crossover, a. Membuat dua bilangan acak (k1 dan k2), dimana bilangan acak pertama (k1) tidak boleh lebih besar dari bilangan acak kedua (k2) atau k1 tidak boleh bernilai sama dengan k2.

SKRIPSI


GALIH G. A.


32

b. Dari bilangan acak yang didapat, maka gen pada kromosom induk pertama mulai dari k1 sampai k2 disalin pada offspring pertama dengan posisi yang sama, c. Gen-gen yang kosong pada offspring pertama diisi oleh gen-gen kromosom induk kedua mulai dari posisi gen yang pertama sampai dengan yang terakhirdan yang belum ada pada offspring secara berurutan mulai dari kiri ke kanan, d. Pada offspring kedua, dapat mengulangi langkah f namun dengan peran kromosom induk yang terbalik, jumlah offspring sebanyak kromosom yang terpilih, e. Maka akan mendapatkan kromosom anak hasil dari crossover. 7.

Dari hasil proses seleksi untuk mutation, dilakukan operasi mutation menggunakan skema swap mutation, a. Pada kromosom yang terpilihakan dipilih 2 gen secara acak, kemudian saling ditukarkan. b. Maka akan mendapatkan kromosomanak hasil dari proses mutation. c. Apabila tidak ada kromosom yang terpilih, maka tidak mendapatkan kromosom anak dari proses mutation.

8.

Setelah offspring terbentuk dari hasil crossover dan mutation, kemudian melakukan

penggantian

populasi

menggunakan

steady-state,

yaitu

mengurutkan hasil dari populasi awal, crossover, dan mutation berdasarkan fitness mulai dari yang terkecil. Kromosom-kromosom yang menempati

SKRIPSI


GALIH G. A.


33

posisi atas akan diambil sebanyak dari parameter ukuran populasi untuk dijadikan populasi awal pada generasi berikutnya. 9.

Jika jumlah generasi sudah tercapai, maka melaporkan hasil GA dengan nilai fitness yang terbaik (terendah).

10.

Jika jumlah generasi belum tercapai, maka melakukan langkah nomor 4. Hasil dari perhitungan dengan Algoritma Genetika memberikan output

berupa urutan kunjungan tempat dengan jarak yang sub-optimal. 3.7. Perancangan Sistem Sebelum pembuatan aplikasi, dibuatnya rancangan sistem terlebih dahulu. Pembuatan rancangan ini diharapkan agar aplikasi tersebut dapat berfungsi seperti apa yang diharapkan yaitu dapat membantu permasalahan yang terjadi pada travelling kurir pada perusahaan. 1.

Pemanfaatan Google Maps API pada Sistem Informasi Geografis Pada tahap ini peneliti menggunakan fitur-fitur yang ada pada Google Maps

API, fitur yang digunakan untuk mengimplementasi pada aplikasi ini adalah fitur map untuk menampilkan peta pada aplikasi, fitur direction yang digunakan untuk mencari jalan antar tempat tujuan yang telah diatur oleh Google Maps, penggunaan fitur latitude dan longitude untuk menentukan titik tujuan yang telah dipilih serta untuk menentukan posisi seorang kurir, fitur marker berfungsi untuk membuat marker pada peta, yang berisikan koordinat lokasi dan keterangan dari marker tersebut, fitur distance untuk menghitung jarak antar dua lokasi yang berdasarkan longitude dan latitude.

SKRIPSI


GALIH G. A.


2.

34

Perancangan Proses Perancangan proses adalah dimana peneliti akan mendesain suatu sistem

dengan berbagai diagram. Pada tahap ini akan dibuat berbagai diagram untuk membantu pembangunan aplikasi. Dalam perancangan proses ini terdiri atas beberapa diagram yang dilakukan, yaitu pembuatan use case diagram, activity diagram, dan rancangan input dan output. A.

Use Case Diagram Dengan pembuatan use case diagram digunakan untuk mengetahui fungsi apa

saja yang ada di dalam sebuah sistem dan siapa saja yang berhak menggunakan fungsi-fungsi tersebut. Fungsi-fungsi tersebut diantaranya adalah: 1. Mencari alamat 2. Melihat tujuan B.

Activity Diagram Activity diagram menggunakan bagaimana alur sistem mulai berjalan hingga

sistem berakhir. Pembuatan activity diagram digunakan menunjukkan langkahlangkah proses dalam aliran kerja dan titik keputusan dalam aliran kerja. C.

Rancangan Input dan Output Desain input dan output merupakan hal yang penting dalam perancangan

pengembangan aplikasi ini. Dengan pembuatan rancangan input dan output, kita dapat mengetahui masukan apa saja yang dibutuhkan oleh sistem untuk melakukan proses pencarian rute dan keluaran yang dihasilkan oleh sistem yaitu visualisasi rute dan jarak yang akan ditempuh pengguna yang digunakan untuk pengambilan keputusan. Berikut adalah desain input dan output:

SKRIPSI


GALIH G. A.


1.

35

Rancangan Form Home Form home merupakan tampilan berupa menu utama pada aplikasi yang akan

dibuat, terdapat beberapa pilihan fitur utama, yaitu mencari alamat yang digunakan untuk mencari alamat yang akan dituju, melihat tujuan yang digunakan untuk daftar tujuan yang telah dipilih, Tentang yang berisikan tentang informasi pembuat. 2.

Rancangan Form Cari Alamat Form cari alamat merupakan sebuah fitur pada aplikasi yang akan dibuat yang

berguna untuk mencarikan alamat yang akan dituju. Pengguna diminta untuk mencari alamat yang ingin dituju dengan mengklik sebuah tombol, untuk mencari tujuannya, kemudian pengguna diminta untuk menekan suatu tombol untuk menyimpan lokasi tersebut. Jika masih ada lokasi yang ingin dicari, maka pengguna dapat mencari kembali. Jika sudah selesai, pengguna dapat kembali ke menu utama. 3.

Rancangan Form Daftar Tujuan Form daftar tujuan merupakan form yang berisikan alamat-alamat yang akan

dituju oleh pengguna. Pengguna dapat menambahkan tujuan dengan menekan sebuah tombol tambah, yang kemudian akan kembali ke halaman pencarian alamat. Dan pengguna dapat menghapus daftar tujuan dengan menekan dan tahan lokasi yang ingin dihapus, atau menekan tombol hapus untuk menghapus semua tujuan. Kemudian, jika sudah selesai maka pengguna dapat menekan tombol proses untuk melakukan proses pencarian rute yang hasilnya akan ditampilkan oleh sistem pada peta. 4.

Rancangan Form Tentang

SKRIPSI


GALIH G. A.


36

Form Tentang merupakan form yang berisikan mengenai informasi pembuat aplikasi dan beberapa informasi mengenai aplikasi. 3.8. Implementasi Sistem Pada penelitian ini akan dibuat suatu aplikasi yang dapat memberikan pandangan kepada pengguna dalam memilih rute dengan jarak yang sub-optimal yang akan dilaluinya. Aplikasi ini dapat dijalankan melalui platform android mobile dengan menggunakan bahasa Java sebagai bahasa pemrogramannya, SQLite Expert sebagai sistem manajemen database, Google Maps API digunakan untuk mengambil koordinat, mencari alamat, menghitung jarak antar lokasi, menggambar rute. 3.9. Pengujian Sistem Uji coba sistem dilakukan untuk menguji kinerja sistem yang telah dibuat. Pada penelitian ini pengujian sistem dilakukan dengan menguji parameter pada algoritma genetika yaitu ukuran populasi, kombinasi probabilitas crossover dan probabilitas mutation, dan jumlah generasi dengan cara mengubah parameter algoritma genetika secara bervariasi untuk mengetahui hasil dari algoritma genetika, serta menggunakan black box testing dengan menguji tiap fitur-fitur yang dimiliki sistem. Pengujian dengan black box testing terfokus pada implementasi dari sebuah aplikasi, untuk memastikan fungsional pada sistem telah terpenuhi dan sesuai dengan yang diinginkan. 3.10. Evaluasi Sistem Setelah memastikan semua fungsional sistem telah usai seperti yang diharapkan, maka selanjutnya akan dilakukan evaluasi sistem dengan menguji user

SKRIPSI


GALIH G. A.


37

interface dari aplikasi ini kepada user, tujuannya adalah untuk mengetahui apakah aplikasi sudah bersifat user friendly atau tidak. Teknik evaluasi yang dilakukan dengan cara memberikan kuisioner kepada pengguna mengenai sistem yang telah dibuat, responden dalam kuisioner ini yaitu kurir pada perusahaan P.T. Sun Star Motor.

SKRIPSI


GALIH G. A.


BAB IV HASIL DAN PEMBAHASAN 4.1. Pengumpulan Data dan Informasi Pengumpulan data dan informasi dilakukan pada bagian atau divisi kurir di PT. Sun Star Motor, Surabaya. Pengumpulan data dan informasi ini dilakukan dengan melakukan studi pustaka, wawancara, dan pengambilan data. Studi pustaka adalah berupa tinjauan pustaka yang diambil dari buku referensi, jurnal, skripsi, dan thesis yang diterbitkan oleh beberapa universitas di Indonesia mengenai teori, Google Maps API, Optimasi, Travelling Salesman Problem, Algoritma Genetika. Hasil studi pustaka yang dilakukan adalah diperolehnya langkah-langkah perhitungan Algoritma Genetika, dan data-data yang dibutuhkan untuk melakukan perhitungan optimasi Travelling Salesman Problem. Wawancara dilakukan dengan seorang kurir di perusahaan tersebut, yang dapat dilihat pada lampiran 1. Dari hasil wawancara yang dilakukan dengan kurir perusahaan, dapat diketahui tugas seorang kurir di perusahaan, yaitu membantu sales counter untuk mengambil kelengkapan administrasi pelanggan dari sales counter yang bersangkutan. Kendaraan kurir yang dipakai untuk bertugas yaitu adalah kendaraan roda dua atau sepeda motor. Kendala yang dihadapi kurir yaitu terkadang kurir menempuh perjalanannya terlalu jauh dan berputar-putar. Tempat kurir memulai perjalanannya adalah dari perusahaan dan diakhiri di perusahaan itu juga. Serta jumlah tempat yang pernah dikunjungi dalam satu hari paling banyak adalah berjumlah 8.

SKRIPSI


GALIH G. A.


39

Setelah melakukan wawancara, tahap selanjutnya adalah tahap pengambilan data melalui wawancara yang dilakukan pada bulan Maret 2016. Wawancara pengambilan data dapat dilihat pada Lampiran 3. Data yang dipakai dalam penelitian ini yaitu data daftar kunjungan kurir pada tanggal 22 Maret dan 24 Maret 2016. Data daftar kunjungan pada tanggal 22 Maret diketahui terdapat 5 lokasi tujuan. Sedangkan data daftar kunjungan pada tanggal 24 Maret terdapat 7 lokasi tujuan. 4.2. Pengolahan Data dan Informasi Data yang didapatkan dari hasil wawancara yaitu data alamat perusahaan yang berada di Jalan Sulawesi No. 33 – 37, Surabaya. Data alamat perusahaan ini berfungsi sebagai titik awal dan titik akhir dari perjalanan kurir. Kemudian, data yang didapatkan dari hasil pengambilan data adalah data daftar kunjungan kurir, yang berfungsi sebagai titik tujuan kurir selama perjalanannya. Terdapat 2 data daftar kunjungan kurir yaitu pada tanggal 22 Maret yang mempunyai 5 lokasi tujuan dan pada tanggal 24 Maret yang mempunyai 7 lokasi tujuan. Data daftar kunjungan dengan 7 lokasi tujuan dapat dilihat pada Tabel 4.1. Data daftar kunjungan yang mempunyai 5 lokasi tujuan diolah secara manual untuk contoh perhitungan manual dan juga pengujian sistem. Kemudian data daftar kunjungan yang mempunyai 7 lokasi tujuan dijadikan hanya sebagai pengujian sistem. 4.2.1. Persiapan Data untuk Penyelesaian Masalah dengan Algoritma Genetika Data daftar kunjungan yang mempunyai 5 lokasi tujuan dan data alamat perusahaan dapat dijadikan sebuah tabel, yang dapat dilihat pada Tabel 4.2.

SKRIPSI


GALIH G. A.


40

Kemudian dari data-data alamat yang terdapat pada Tabel 4.2 dan informasi yang telah didapat akan diolah dengan menggunakan Google Maps untuk mencari jarak masing-masing antar tempat mulai dari alamat perusahaan sampai lokasi tujuan yang terakhir. Tabel 4.1 Daftar Kunjungan Kurir (7 Lokasi Tujuan) No.

Nama Tempat

Alamat

1.

Mulyati Guyadi

Jalan Bumi Marina Emas Selatan E82

2.

Hadi Ciputra

Jalan Darmahusada Indah III / L-50

3.

Suharsono Lasa

Jalan Tidar No. 194

4.

Indriaty Latief

Jalan Villa Bukit Emas N-8

5.

PT. Rimba Ria Rekawira

Jalan Kedinding Tengah II/6

6,

PT. Artha Dinamis Sentosa

Jalan Anjasmoro No. 64

7.

PT. Wira Bhumi Sejati

Jalan Tenggilis Timur VI.1 (AA-25)

Tabel 4.2 Kumpulan Data Alamat (1 Lokasi Awal dan 5 Lokasi Tujuan) No.

Nama Tempat

Alamat

1.

PT. Sun Star Motor

Jl. Sulawesi Nomor 33 – 37, Surabaya

2.

P.T. Mikatasa Agung

Jl. Rungkut Industri No. 2 – 4, Surabaya

3.

P.T. Superindo Utama

Jl. Arief Rahman Hakim No. 139, Surabaya

4.

P.T. Wira Bhumi Sejati

Jl. Tenggilis Timur VI/1 (AA-25), Surabaya

5.

CV. Wonokusumo Indah

Jl. HR. Muhammad No. 49 – 55, Surabaya

6.

P.T. Alvindo

Jl. Margorejo Indah XIV/C-603, Surabaya

Pada Tabel 4.2, nomor 1 merupakan tempat awal dari perjalanan kurir, nomor 2 dan seterusnya merupakan tempat tujuan yang akan dikunjungi kurir. Dari Tabel 4.2 tersebut dapat dilakukan pencarian jarak masing-masing lokasi dengan menggunakan fungsi directions yang telah disediakan oleh Google Maps. Pada fungsi direction tersebut terdapat beberapa pilihan kendaraan, mode driving, mode bycle, mode walking, dan lain-lain. Dalam hal ini mode yang dipilih adalah mode SKRIPSI


GALIH G. A.


41

driving, serta terdapat pilihan opsi hindar (avoid) yang dipilih yaitu avoid highways, dan avoid tolls. Setelah pilihan kendaraandan opsi hindar dipilih, maka dapat diketahui jaraknya, yang dapat dilihat pada Gambar 4.1. Pada Gambar 4.1 dapat dilihat bahwa terdapat 3 jalur yang dianjurkan oleh Google Maps, akan tetapi Google Maps lebih menyarankan untuk melewati jalur pertama dengan jarak sebesar 9,2 kilometer. Pada anjuran inilah yang dijadikan pilihan untuk mendapatkan jarak masing-masing antar lokasi. Setelah semua jarak antar titik dicari dengan Google Maps, maka dapat dijadikan tabel seperti pada Tabel 4.3, pada Tabel 4.3 dapat dilihat terdapat 2 kolom yaitu kolom awal dan kolom tujuan, kolom awal merupakan asal perjalanan, dan kolom tujuan merupakan tempat yang dituju. Pada kolom awal terdapat beberapa angka yang merupakan representasi angka dari Tabel 4.3, misalnya pada kolom awal terdapat angka 1 dan kolom tujuan terdapat angka 2, maka dapat diartikan bahwa angka 1 yang merupakan tempat PT. Sun Star Motor dengan alamat Jl. Sulawesi No. 33 – 37 menuju ke angka 2 yang merupakan tempat PT. Mikatasa Agung dengan alamat Jl. Rungkut Industri No. 2 – 4 mempunyai jarak 9,2 kilometer. Setelah tabel terisi semua, kemudian dapat diselesaikan dengan Algoritma Genetika untuk mendapatkan hasil yang sub-optimal. 4.3. Penyelesaian Masalah dengan Algoritma Genetika Pada Algoritma Genetika yang digunakan adalah menentukan proses inisiasi populasi (encode), menghitung fitness, melakukan proses seleksi menggunakan roulette-wheel, melakukan proses penyilangan (order crossover), melakukan proses mutasi (swap mutation), penggantian populasi (steady-state). Sebelum melakukan proses inisiasi, perlu diketahui jarak antar titik terlebih dahulu yang SKRIPSI


GALIH G. A.


42

dapat dilihat pada Tabel 4.3. Kemudian, menentukan parameter-parameter dalam algoritma Genetika, sebagai contoh parameter yang digunakan untuk perhitungan manual ini dapat dilihat pada Tabel 4.4. Gambar 4.1 Tampilan directions pada Google Maps

Awal 1 2 3 4 5 6

Tabel 4.3 Data Jarak Antar Titik Tujuan 1 2 3 4 5 9.2 6.7 8.3 7.5 0 10.4 8.7 4 13.6 0 5.3 8.9 7.1 12.9 0 8.5 2.3 7.9 13 0 9.4 12.6 14.7 13.1 0 7.4 5.9 10.2 6.2 10.1

6 6.7 6.3 7.2 2.8 10.1 0

Tabel 4.4 Parameter Algoritma Genetika Parameter Algoritma Genetika

Nilai

Ukuran Populasi

20

pc (probabilitas Crossover)

0.6

pm (probabilitas Mutation)

0.1

Maksimal Generasi

1

4.3.1.

Proses Inisiasi Populasi (Permutation Encoding)

SKRIPSI


GALIH G. A.


43

Pada proses ini merupakan pembentukan kromosom-kromosom pada populasi, dimana setiap kromosom-kromosomnya berisi angka-angka atau disebut juga dengan gen, gen-gen tersebut merupakan representasi dari rangkaian suatu perjalanan kurir. Pembentukan gen-gen tiap kromosom dilakukan secara acak tetapi, di dalam setiap kromosomnya tidak boleh ada gen yang kembar dengan gen lainnya. Pada satu populasi terdapat beberapa kromosom yang dibentuk, jumlah kromosom yang dibentuk tergantung dari parameter ukuran populasi yang sudah ditentukan, dalam hal ini terdapat 20 buah kromosom dalam satu populasi. Hasil pembentukan kromosom dapat dilihat pada Tabel 4.5. Pada tabel tersebut tidak terdapat angka 1, yang merupakan representasi dari titik awal (PT. Sun Star Motor). Hal ini disebabkan karena titik awal merupakan tempat yang pasti dan tidak berubah-ubah dimana kurir akan berangkat untuk mengunjungi titik tujuannya. Kromosom k1 k2 k3 k4 k5 k6 k7 k8 k9 k10

4.3.2.

Tabel 4.5 Kromosom Hasil Encoding 2 4 2 6 3 5 3 3 4 2

3 2 3 3 2 6 2 2 2 3

Gen 4 3 5 2 4 3 5 5 3 4

5 6 4 4 5 2 4 6 5 6

6 5 6 5 6 4 6 4 6 5

Kromosom k11 k12 k13 k14 k15 k16 k17 k18 k19 k20

4 4 5 3 5 5 6 2 6 6

3 5 4 2 2 6 2 3 4 5

Gen 2 6 3 4 3 3 3 5 5 4

5 3 2 6 4 2 4 6 3 2

6 2 6 5 6 4 5 4 2 3

Proses Evaluasi Pada proses ini, tiap kromosom dalam populasi dihitung nilai fitness-nya.

Dalam hal ini menghitung total jarak dari representasi kromosom yang telah dibangkitkan. Pada proses evaluasi, dapat menggunakan Persamaan 2.3 untuk dapat

SKRIPSI


GALIH G. A.


44

mengetahui total jarak dari tiap-tiap kromosom. Contoh perhitungan nilai fitness pada kromosom 1 adalah sebagai berikut: Kromosom 1 berisi gen-gen: 2 3 4 5 6, yang berarti titik awal / titik nomor 1 akan mengunjungi titik nomor 2, kemudian dari titik nomor 2 akan mengunjungi titik nomor 3, kemudian dari titik nomor 3 akan mengunjungi titik nomor 4, kemudian dari titik nomor 4 akan mengunjungi titik nomor 5, kemudian dari titik nomor 5 akan mengunjungi titik nomor 6, kemudian dari titik nomor 6 akan mengunjungi titik nomor 1 atau kembali lagi ke titik nomor 1. Pada titik 1 ke titik 2 yang terdapat pada Tabel 4.5, mempunyai jarak 9,2 km, titik 2 ke titik 3 mempunyai jarak 8,7 km, dan seterusnya sampai kembali ke titik 1. Langkah ini diulang-ulang sampai semua kromosom pada populasi terhitung nilai fitness-nya. Yang dapat dituliskan sebagai berikut: Kromosom 1: 9,2 + 8,7 + 7,1 + 13 + 10,1 + 7,4 = 55,5 Kromosom 2: 8,3 + 2,3 + 8,7 + 7,2 + 10,1 + 9,4 = 46 Kromosom 3: 9.2 + 8,7 + 12,9 + 13,1 + 2,8 + 7,4 = 54,1 … Kromosom 20: 6,7 + 10,1 + 13,1 + 2,3 + 8,7 + 5,3 = 46,2 4.3.3.

Proses Seleksi (Roulette Wheel) Sebelum melakukan penyeleksian kromosom, terlebih dahulu menghitung

nilai fungsi fitness, probabilitas kromosom, dan kumulatif dari probabilitas untuk tiap kromosom. Sebelum menghitung fungsi fitness, terlebih dahulu menentukan fungsi fitness yang akan digunakan, dalam kasus Travelling Salesman Problem ini hasil yang diinginkan kromosom yang mempunyai nilai fungsi fitness yang kecil /

SKRIPSI


GALIH G. A.


45

rendah. Maka fungsi fitness yang digunakan seperti pada Persamaan 2.2. Yang dapat dilakukan perhitungan sebagai berikut: F(1) = F(2) = F(3) =

1 55,5 1 46

= 0,018018018

= 0,02173913

1 54,1

= 0,018484288

… F(20) =

1 46,2

= 0,021645022

Setelah semua fungsi fitness dihitung, maka menjumlahkan semua fungsi fitness-nya, hasilnya adalah 0,391412846. Kemudian, selanjutnya menghitung probabilitas tiap kromosom dengan menggunakan Persamaan 2.3, dapat dilakukan perhitungan sebagai berikut: P[1] = P[2] = P[3] =

0,018018018 0,391412846 0,02173913 0,391412846

= 0,046033282 = 0,055540156

0,018484288 0,391412846

= 0,047224532

… P[20] =

0,021645022 0,391412846

SKRIPSI

= 0,055299722


GALIH G. A.


46

Setelah semua probabilitas diketahui, maka langkah selanjutnya menghitung nilai kumulatif dari probabilitas kromosom, dapat dilakukan perhitungan sebagai berikut: K1 = 0 + 0,046033282 = 0,046033282 K2 = K1 (0,046033282 ) + 0,055540156 = 0,101573438 K3 = K2 (0,101573438 ) + 0,047224532 = 0,14879797 … K20 = K19 (0,944700278) + 0,055299722 = 1 Setelah nilai kumulatif diketahui, maka langkah selanjutnya adalah proses menentukan calon induk crossover dan mutation dengan cara: Langkah 1: Membuat bilangan acak R dengan interval [0, 1] Langkah 2: membandingkan nilai kumulatif dari probabilitas, dengan syarat seperti pada Persamaan 2.5. Langkah 3: kromosom yang terpilih merupakan calon kromosom induk. Langkah 4: mengulangi langkah 1, sebanyak n. Dimana n merupakan nilai ukuran populasi. Setelah langkah tersebut selesai dilakukan, maka akan didapatkan hasil calon kromosom induk crossover yang dapat dilihat pada Tabel 4.6. Dari hasil tersebut, akan dilakukan proses seleksi untuk crossover. Pada proses seleksi untuk crossover dapat dilakukan dengan cara membuat bilangan acak R [0, 1] sebanyak ukuran populasi yaitu berjumlah 20 buah dimana bilangan acak R ini berfungsi untuk menyeleksi kromosom calon induk crossover sebagai kromosom induk crossover. Setelah bilangan acak R dibuat, maka langkah selanjutnya adalah membandingkan bilangan acak R dengan parameter algoritma genetika yaitu probabilitas crossover SKRIPSI


GALIH G. A.


47

(PC). Jika bilangan acak R lebih rendah daripada PC (0.6), maka kromosom tersebut terpilih sebagai induk, sebaliknya jika bilangan acak lebih besar daripada PC, maka kromosom tersebut tidak terpilih sebagai induk. Bilangan acak R dan hasil proses seleksi untuk crossover dapat dilihat pada Tabel 4.7. Kromosom yang tidak terpilih, dapat diabaikan saja. Jika jumlah induk berjumlah ganjil, maka induk yang paling terakhir dihapus, dalam hal ini kromosom yang dihapus adalah k14. Dari hasil seleksi untuk crossover ini, kromosom-kromosom tersebut akan dikenakan proses genetika, yaitu proses crossover. Untuk menentukan calon induk mutation dapat dilakukan langkah 1 sampai dengan langkah 4 yang sama seperti menentukan calon induk crossover. Setelah langkah tersebut selesai dilakukan, maka akan didapatkan hasil calon kromosom induk mutation yang dapat dilihat pada Tabel 4.8. Pada proses mutation dapat dilakukan dengan cara membangkitkan bilangan acak R sebanyak parameter ukuran populasi yaitu berjumlah 20 buah. Bilangan acak R ini berfungsi untuk menyeleksi kromosom calon induk mutation sebagai kromosom induk mutation. Setelah bilangan acak R dibangkitkan, maka langkah selanjutnya adalah membandingkan bilangan acak R dengan parameter algoritma genetika yaitu probabilitas mutation (PM). Jika bilangan acak R lebih rendah daripada PM (0.1), maka kromosom tersebut terpilih sebagai induk, sebaliknya jika bilangan acak lebih besar daripada PM, maka kromosom tersebut tidak terpilih sebagai induk. Bilangan acak R dan hasil seleksi untuk mutation dapat dilihat pada Tabel 4.9. Dari hasil seleksi untuk mutation ini, kromosom-kromosom tersebut akan dikenakan proses genetika, yaitu proses mutation.

SKRIPSI


GALIH G. A.


48

Tabel 4.6 Kumulatif dari Probabilitas, Nilai acak [0, 1], Calon induk Crossover Bilangan Kumulatif dari Calon Induk Nilai Acak R Acak keProbabilitas Crossover 1 0,046033 0,547599367 k12 2 0,101573 0,811915138 k17 3 0,148798 0,26652063 k6 4 0,197094 0,348320342 k7 5 0,248089 0,216362901 k5 6 0,300016 0,547235276 k12 7 0,34868 0,411120851 k9 8 0,395992 0,046972999 k2 9 0,447398 0,234602314 k5 10 0,500075 0,503730768 k11 11 0,545535 0,120116407 k3 12 0,587486 0,759858969 k16 13 0,637483 0,525614531 k11 14 0,698458 0,434052877 k9 15 0,753878 0,290458616 k6 16 0,805806 0,548716378 k12 17 0,856098 0,221565064 k5 18 0,902048 0,166095885 k4 19 0,9447 0,153396038 k4 20 1 0,644392699 k14 Tabel 4.7 Bilangan acak R dan hasil proses seleksi untuk crossover Nilai Kromosom Nilai Kromosom Kromosom Kromosom Acak R Induk Acak R Induk k12 0,178296 Ya k3 0,846975 Tidak k17 0,042934 Ya k16 0,330228 Ya k6 0,36223 Ya k11 0,06974 Ya k7 0,133739 Ya k9 0,487728 Ya k5 0,9873 Tidak k6 0,068987 Ya k12 0,044988 Ya k12 0,936868 Tidak k9 0,169261 Ya k5 0,762258 Tidak k2 0,2434 Ya k4 0,748981 Tidak k5 0,44723 Ya k4 0,660063 Tidak k11 0,812423 Tidak k14 0,200311 Ya

SKRIPSI


GALIH G. A.


49

Tabel 4.8 Kumulatif dari Probabilitas, Nilai acak [0, 1], Calon induk mutation Bilangan Kumulatif dari Hasil Calon Nilai Acak R Acak keProbabilitas Induk Mutation 1 0,046033 0,547599367 k14 2 0,101573 0,811915138 k13 3 0,148798 0,26652063 k15 4 0,197094 0,348320342 k18 5 0,248089 0,216362901 k19 6 0,300016 0,547235276 k2 7 0,34868 0,411120851 k7 8 0,395992 0,046972999 k5 9 0,447398 0,234602314 k15 10 0,500075 0,503730768 k3 11 0,545535 0,120116407 k20 12 0,587486 0,759858969 k20 13 0,637483 0,525614531 k12 14 0,698458 0,434052877 k11 15 0,753878 0,290458616 k9 16 0,805806 0,548716378 k15 17 0,856098 0,221565064 k3 18 0,902048 0,166095885 k15 19 0,9447 0,153396038 k1 20 1 0,644392699 k1 Tabel 4.9 Bilangan acak R dan hasil proses seleksi untuk mutation Nilai Kromosom Nilai Kromosom Kromosom Kromosom Acak R Induk Acak R Induk k14 0,856931 Tidak k20 0,345112 Tidak k13 0,281256 Tidak k20 0,421754 Tidak k15 0,079763 Ya k12 0,80612 Tidak k18 0,120881 Tidak k11 0,098499 Ya k19 0,716904 Tidak k9 0,00754 Ya k2 0,631134 Tidak k15 0,848903 Tidak k7 0,133437 Tidak k3 0,797054 Tidak k5 0,92297 Tidak k15 0,81341 Tidak k15 0,613068 Tidak k1 0,279322 Tidak k3 0,575412 Tidak k1 0,056571 Ya

SKRIPSI


GALIH G. A.


4.3.4.

50

Proses Crossover (Order Crossover) Dari hasil Tabel 4.7, dapat diketahui terdapat 6 pasangan kromosom yang

akan dilakukan proses crossover. Pasangan kromosom tersebut adalah k12 dengan k17, k6 dengan k7, k12 dengan k9, k2 dengan k5, k16 dengan k11, dan k9 dengan k6. Proses crossover ini menggunakan teknik Order Crossover untuk menghasilkan kromosom baru / anak baru (offspring). Untuk teknik Order Crossover, dapat mengikuti langkah-langkah berikut: Langkah 1: membangkitkan 2 bilangan acak, bilagan acak pertama tidak boleh lebih dari bilangan acak kedua dan kedua bilangan acak tersebut kurang dari lebar kromosom, dalam hal ini lebar kromosom adalah 5. Contoh bilangan acak 1= 3, dan bilangan acak 2= 4. Langkah 2: setelah bilangan acak dibangkitkan, gen induk pertama pada bilangan acak pertama sampai dengan bilangan acak kedua, diduplikasi ke offspring pertama dengan gen yang sama. k12

X

k17

45632

X

62345

Anak 1 =

00630

Langkah 3: gen-gen pada offspring yang masih kosong diisi dengan gen awal pada induk kedua yang belum ada pada offspring, sampai pada gen yang terakhir secara berurutan mulai dari kiri sampai kanan. Sehingga akan menjadi:

SKRIPSI

k12

X

k17

45632

X

62345


Anak 1 =

24635

GALIH G. A.


51

Langkah 4: pada offspring yang kedua dapat dilakukan kembali langkah ke3. Namun, dengan peran induk yang terbalik. Dengan bilangan acak 1 dan 2 sama seperti sebelumnya, maka hasil anak menjadi. k17

X

k12

62345

X

45632

Anak 2 =

56342

Jika masih ada pasangan kromosom yang belum terkena proses crossover, ulangi langkah 1 sampai dengan langkah 4. Hasil offspring dari proses crossover dapat dilihat pada Tabel 4.10. Tabel 4.10 Hasil Offspring dari crossover Kromosom Gen Kromosom Gen k21 24635 k27 42365 k22 56342 k28 32456 k23 56324 k29 63254 k24 32546 k30 45326 k25 45632 k31 56342 k26 42356 k32 42356 4.3.5.

Proses Mutation (Swap Mutation) Dari hasil Tabel 4.9, dapat diketahui terdapat 4 buah kromosom yang akan

dilakukan proses mutation, kromosom tersebut adalah k15, k11, k9, dan k1. Proses mutation ini menggunakan teknik swap mutation untuk menghasilkan kromosom baru / anak baru (offspring). Untuk teknik swap mutation dapat dilakukan langkah sebagai berikut: Langkah 1: membangkitkan 2 bilangan acak, dimana bilangan acak pertama dan kedua tidak boleh sama. Contoh bilangan acak 1= 5, bilangan acak 2= 1. Langkah 2: setelah bilangan acak dibangkitkan, posisi gen pada induk mutation yang sesuai dengan bilangan acak pertama dan SKRIPSI


GALIH G. A.


52

bilangan acak kedua akan saling ditukarkan. Dalam hal ini angka yang tercetak tebal merupakan posisi dari bilangan acak pertama dan bilangan acak kedua. k1 =

23456

Hasil anak yang didapatkan dari proses swap mutation dapat dilihat pada Tabel 4.11. Setelah mendapatkan hasil offspring dari mutation, maka langkah selanjutnya adalah proses replacement. Tabel 4.11 Hasil Offspring dari mutation Kromosom Gen k33 63452 k34 42536 k35 46253 k36 52436 4.3.6.

Proses Replacement (Weak Parent Replacement) Pada proses ini, langkah yang dilakukan adalah mengganti kromosom-

kromosom pada populasi awal dengan kromosom-kromosom yang baru berdasarkan nilai fitness-nya atau diurutkan berdasarkan nilai fitness yang terbaik. Langkah awal yang dilakukan adalah menggabungkan semua kromosom pada populasi awal, hasil anak crossover, dan hasil anak mutation. Setelah semua digabungkan, kemudian kromosom-kromosom tersebut dievaluasi / dihitung nilai fitness-nya dengan menggunakan Persamaan 2.3. Maka, hasil yang didapatkan dapat dilihat pada Tabel 4.12. Setelah digabungkan, maka langkah selanjutnya adalah mengurutkan berdasarkan nilai fitness-nya, hasil yang didapatkan dapat dilihat pada Tabel 4.13. Dari hasil populasi penggabungan, maka langkah selanjutnya adalah memilih kromosom teratas, sebanyak dari ukuran populasi untuk dijadikan sebagai populasi awal pada generasi berikutnya. Pada proses berikutnya SKRIPSI


GALIH G. A.


53

hanya mengulangi proses-proses sebelumnya yaitu proses evaluasi, proses selection, proses crossover, dan proses mutation sampai kriteria penghentian tercapai. Dari hasil Tabel 4.13, maka langkah selanjutnya adalah mengambil kromosom-kromosom teratas dengan jumlah yang sesuai dengan parameter ukuran populasi. Kromosom-kromosom tersebut akan dijadikan sebagai populasi awal untuk generasi berikutnya, yang dapat dilihat pada Tabel 4.14. 4.3.7.

Kriteria Penghentian (Generations) Kriteria penghentian ini menggunakan beberapa kali pengulangan atau

disebut juga generasi (generations), yang dimana proses algoritma genetika dihentikan apabila telah mencapai batas generations yang telah ditentukan pada parameter awal, dalam hal ini maksimal generasi untuk perhitungan manual adalah sebanyak 1 kali. Jika jumlah generations sudah tercapai, maka yang akan dilakukan adalah menampilkan kromosom dengan nilai fitness yang paling baik / terendah dari sebuah populasi. Contoh kromosom terbaik dari populasi seperti pada Tabel 4.15. Tabel 4.12 Penggabungan populasi awal, anak crossover, anak mutation, dan nilai fitness Penggabungan Populasi Nilai Nilai Kromosom Gen Kromosom Gen Fitness Fitness k1 23456 55,5 k19 64532 59,9 k2 42365 46 k20 65423 46,2 k3 23546 54,1 k21 24635 48,5 k4 63245 52,9 k22 56342 47,6 k5 32456 50,1 k23 56324 49,2 k6 56324 49,2 k24 32546 52,5 Nilai Nilai Kromosom Gen Kromosom Gen Fitness Fitness k7 32546 52,5 k25 45632 60,9

SKRIPSI


GALIH G. A.


k8 k9 k10 k11 k12 k13 k14 k15 k16 k17 k18

32564 42356 23465 43256 45632 54326 32465 52346 56324 62345 23564

54 49,7 48,5 56,2 60,9 51,1 41,9 46,1 49,2 50,8 55,6

k26 k27 k28 k29 k30 k31 k32 k33 k34 k35 k36

42356 42365 32456 63254 45326 56342 42356 63452 42536 46253 52436

54

49,7 46,1 50,1 61 58,6 47,6 49,7 60 53,5 50,6 46,6

Tabel 4.13 Hasil penggabungan populasi berdasarkan nilai fitness-nya Populasi Setelah Diurutkan Nilai Nilai Kromosom Gen Kromosom Gen Fitness Fitness k14 32465 41,9 k35 46253 50,6 k2 42365 46 k17 62345 50,8 k15 52346 46,1 k13 54326 51,1 k27 42365 46,1 k7 32546 52,5 k20 65423 46,2 k24 32546 52,5 k36 52436 46,6 k4 63245 52,9 k22 56342 47,6 k34 42536 53,5 k31 56342 47,6 k8 32564 54 k10 23465 48,5 k3 23546 54,1 k21 24635 48,5 k1 23456 55,5 k6 56324 49,2 k18 23564 55,6 k16 56324 49,2 k11 43256 56,2 k23 56324 49,2 k30 45326 58,6 k9 42356 49,7 k19 64532 59,9 k26 42356 49,7 k33 63452 60 k32 42356 49,7 k12 45632 60,9 k5 32456 50,1 k25 45632 60,9 k28 32456 50,1 k29 63254 61

Tabel 4.14 Populasi untuk Generasi Berikutnya Populasi Untuk Generasi Berikutnya k1 32465 k11 56324 SKRIPSI


GALIH G. A.


k2 k3 k4 k5 k6 k7 k8 k9 k10

42365 52346 42365 65423 52436 56342 56342 23465 24635

k12 k13 k14 k15 k16 k17 k18 k19 k20

55

56324 56324 42356 42356 42356 32456 32456 46253 62345

Tabel 4.15 Kromosom terbaik dari populasi Kromosom Gen Hasil Evaluasi k1 32465 41,9 4.4. Perancangan Sistem 4.4.1 Pemanfaatan Google Maps Pada Sistem Informasi Geografis Dalam rancang bangun sistem ini terlebih dahulu memanfaatkan fitur Google Maps Android API. Dengan fitur Google Maps API, maka peta dapat ditampilkan pada perangkat / device pengguna. Google Maps Direction API, berfungsi agar sistem dapat mengetahui jarak antara titik awal dengan titik tujuan. Dengan cara, sistem mengirimkan sebuah link ke server Google Maps API, link tersebut bertujuan untuk meminta (request) keserver Google Maps API agar memberikan informasi mengenai jarak antar titik yang ingin diketahui, kemudian Google Maps API membalas atau merespon (respond) dengan mengirimkan sebuah file bernama JSON, file tersebut berisi data-data yang diinginkan melalui link yang telah dikirimkan. Kemudian, Google Place API bertujuan untuk mencari tempat yang diinginkan pengguna dengan mengetikkan sebuah alamat atau nama tempat. Dengan memanfaatkan fitur ini sistem akan melakukan pertukaran data dengan server Google Maps API, sistem akan mengirimkan nama tempat yang dipilih oleh pengguna. Kemudian server Google Maps API akan mengirimkan data berupa SKRIPSI


GALIH G. A.


56

nama tempat, alamat tempat, latitude dan longitude. Dari data yang diperoleh kemudian sistem mengolah data latitude dan longitude untuk ditampilkan pada peta. Dengan menggunakan fitur marker sebagai penanda pada peta, maka sistem dapat menampilkan hasil dari pencarian pada peta dengan memanfaatkan data latitude dan longitude yang telah diperoleh. Jika marker tersebut di-klik maka akan memunculkan informasi nama tempat, dan alamat tempat yang telah dipilih. 4.4.2 Perancangan Proses Gambaran umum dari aplikasi yang dibuat dapat dilihat pada Gambar 4.2.

USER

INPUT

SISTEM PENDUKUNG KEPUTUSAN + ALGORITMA GENETIKA + SISTEM INFORMASI GEOGRAFIS

OUTPUT

Gambar 4.2 Gambaran Umum Sistem User merupakan pengguna dari aplikasi optimasi Travelling Salesman Problem, dalam kasus ini adalah seorang kurir pada PT. Sun Star Motor Surabaya yang mempunyai beberapa alamat tujuan dan ingin mengoptimalkan jarak antar tujuannya. Input sistem yang diperlukan berupa nama alamat atau titik lokasi tujuan yang nanti akan diolah oleh sistem, sehingga dari input tersebut dapat diketahui jarak antara lokasi awal dengan beberapa lokasi tujuan. Hasil olahan tersebut akan diproses kembali oleh sistem dengan menggunakan algoritma genetika. Hasil dari proses algoritma Genetika tersebut berupa output sistem yang dapat menunjukkan rute pada peta dan urutan lokasi tujuan yang harus dikunjungi terlebih dahulu. 1.

Use Case Diagram

SKRIPSI


GALIH G. A.


57

Use Case diagram merupakan diagram yang menggambarkan interaksi antara sistem dengan aktor. Adapun desain use case yang dirancang untuk aplikasi ini dapat dilihat pada Gambar 4.3.

Gambar 4.3 Use Case Diagram Optimasi Travelling Salesman Problem Pengguna merupakan seseorang yang memiliki tujuan untuk menemukan rute dari posisi titik awal menuju ke beberapa tempat tujuannya dengan jarak yang suboptimal. Didalam use case diagram optimasi travelling salesman problem terdapat dua use case yaitu: 1.

Cari Alamat Pada use case ini berfungsi untuk mencari beberapa alamat dengan

memasukkan nama alamat atau memilih titik lokasi tujuan yang diinginkan. 2.

Daftar Tujuan Pada use case ini berfungsi untuk menghapus atau menambah alamat

tujuan yang diinginkan, dan menambahkan catatan pada setiap tujuan yang ada. Serta, dapat memproses algoritma Genetika untuk menghasilkan rute perjalanan pengguna. 2.

Activity Diagram Activity Diagram menggambarkan berbagai aliran aktivitas dari sistem yang

dirancang, diawali dari bagaimana masing-masing aliran berawal hingga aliran SKRIPSI


GALIH G. A.


58

berakhir. Pembuatan activity diagram ini berdasarkan pada fungsi yang dibuat pada use case diagram optimasi travelling salesman problem. Activity Diagram Cari Alamat dapat dilihat pada Gambar 4.4, dan Activity Diagram Daftar Tujuan dapat dilihat pada Gambar 4.5. 3.

Rancangan Input dan Output Dengan pembuatan rancangan input dan output, kita dapat mengetahui

masukan apa saja yang dibutuhkan oleh sistem untuk melakukan proses pencarian rute dan keluaran yang dihasilkan sistem yaitu informasi rute untuk pengguna yang digunakan untuk pengambilan keputusan. Berikut adalah desain input dan output: 1.

Rancangan Form Home Pada form home tersedia tiga pilihan fitur yang tersedia pada aplikasi, yaitu

cari alamat yang digunakan untuk mencari alamat yang ingin dituju, daftar tujuan yang digunakan untuk melihat daftar alamat mana saja yang ingin dikunjungi serta dapat menambahkan catatan untuk tiap tujuannya, dan Tentang yang berisikan tentang informasi pembuat. Rancangan form home dapat dilihat pada Gambar 4.6. 2.

Rancangan Form Cari Alamat Setelah masuk ke form cari alamat, pengguna akan menginputkan alamat

yang akan dituju, atau dengan cara mengklik dan tahan pada peta. Kemudian sistem akan menampilkan sebuah tanda pada peta (marker) yang merupakan hasil dari pencarian tersebut. Rancangan form cari alamat dapat dilihat pada Gambar 4.7. 3.

Rancangan Form Daftar Tujuan Setelah masuk ke form daftar tujuan, pengguna dapat melihat alamat apa saja

yang akan menjadi tujuannya. Pengguna dapat menghapus tujuan yang tidak

SKRIPSI


GALIH G. A.


59

diinginkan, serta pengguna dapat menambahkan catatan untuk setiap tujuannya, kemudian pengguna diminta untuk menekan tombol proses untuk melakukan proses pencarian rute yang hasilnya akan ditampilkan oleh sistem pada peta. Rancangan form daftar alamat dapat dilihat pada Gambar 4.8. 4.

Rancangan Form Tentang Pada form ini berisikan mengenai informasi pembuat. Rancangan form

Tentang dapat dilihat pada Gambar 4.9.

Gambar 4.4 Activity Diagram Cari Alamat

SKRIPSI


GALIH G. A.


60

Gambar 4.5 Activity Diagram Daftar Tujuan

SKRIPSI


GALIH G. A.


61

Travelling Salesman Problem

CARI ALAMAT

DAFTAR TUJUAN

TENTANG

Gambar 4.6 Rancangan Form Home

Tombol Cari

√

Tombol Dengan ikon Centang

PETA

Gambar 4.7 Rancangan Form Cari Alamat SKRIPSI


GALIH G. A.


62

Daftar Tujuan

Tujuan 1

Tujuan 2

Tambah

Hapus Semua

Proses

Gambar 4.8 Rancangan Form Daftar Tujuan Tentang

Travelling Salesman Problem Galih Gaharditama A. Sistem Informasi Universitas Airlangga

Gambar 4.9 Rancangan Form Tentang

SKRIPSI


GALIH G. A.


63

4.5. Implementasi Sistem Setelah dilakukan perancangan sistem maka Rancang Bangun Sistem Pendukung Keputusan Untuk Optimasi Travelling Salesman Problem Berbasis Sistem Informasi Geografis dengan Menggunakan Algoritma Genetika akan diimplementasikan dalam bentuk aplikasi platform android mobile yang menggunakan Java sebagai bahasa pemrograman dan SQLite Expert sebagai database. Pada implementasi sistem akan dibahas mengenai General User Interface (GUI) dari aplikasi rancang bangun sistem pendukung keputusan untuk optimasi Travelling Salesman Problem berbasis sistem informasi geografis dengan menggunakan algoritma genetika. Sebelum membahas GUI, akan dijabarkan terlebih dahulu algoritma genetika yang digunakan dalam proses pencarian rute sub-optimal. Berikut ini merupakan algoritma umum optimasi Travelling Salesman Problem yang dapat dilihat pada Gambar 4.10. BEGIN Input lokasi tujuan Perhitungan jarak antar lokasi Perhitungan Algoritma Genetika Menampilkan rute END

. Gambar 4.10 Algoritma Umum Optimasi Travelling Salesman Problem Sebelum melakukan perhitungan dengan algoritma Genetika, diperlukan input lokasi tujuan. Pada proses ini membutuhkan input berupa nama atau alamat atau koordinat lokasi tujuan, yang kemudian akan diolah dengan Google Place API agar mendapatkan informasi berupa nama, alamat, dan koordinat lokasi tujuan yang

SKRIPSI


GALIH G. A.


64

telah dimasukkan. Dari hasil olahan tersebut maka akan menampilkan marker pada peta. Psuedocode input lokasi tujuan dapat dilihat pada Gambar 4.11. Selanjutnya adalah melakukan perhitungan jarak mulai dari lokasi awal sampai lokasi tujuan yang paling terakhir. Input yang digunakan dalam perhitungan ini adalah koordinat masing-masing lokasi (Latitude dan Longitude) yang telah disimpan. Psuedocode perhitungan jarak antar lokasi dapat dilihat pada Gambar 4.12. Setelah didapatkan hasil dari perhitungan jarak antar lokasi, maka dapat melakukan proses Algoritma Genetika. Input yang digunakan pada proses ini adalah id_lokasi, dan jarak yang telah disimpan. Psuedocode Perhitungan Algoritma Genetika dapat dilihat pada Gambar 4.13. Setelah ditemukannya kromosom terbaik dari hasil perhitungan algoritma Genetika, maka sistem akan melakukan proses pembuatan rute dan membuat sebuah tanda pada peta (marker). Marker tersebut bertujuan untuk megetahui titik dari lokasi tersebut. Psuedocode menampilkan rute dapat dilihat pada Gambar 4.14. Nama : Input lokasi tujuan Fungsi : untuk menyimpan lokasi tujuan Input : nama atau alamat atau koordinat lokasi Output : menampilkan marker pada peta BEGIN pushButton(){ // method apabila mengklik suatu tombol String text = getText() //method untuk mengambil input nama atau alamat findPlaceAPI(text) // method untuk memanggil fungsi Google Place API marker() //method untuk membuat tanda pada peta } pushSave() // method apabila mengklik suatu tombol untuk menyimpan lokasi END

Gambar 4.11 Psuedocode Input Lokasi Tujuan

SKRIPSI


GALIH G. A.


65

Nama : Perhitungan Jarak Antar Lokasi Fungsi : untuk menghitung jarak tiap lokasi yang disimpan Input : koordinat lokasi Output : Nilai Jarak (km) BEGIN int jmlData = getJmlData() // jumlah banyaknya data double latAwal, lngAwal // inisialiasi variabel koordinat lokasi awal double latTuj, lngTuj // inisialiasi variabel koordinat lokasi tujuan double jarak for (int i=1;i<=jmlData;i++){ latAwal = getLat() // method untuk mengambil nilai latitude lokasi awal yang disimpan lngAwal = getLng() // method untuk mengambil nilai longitude lokasi awal yang disimpan for(int j=1;j<=jmlData;j++){ if(i == j){ jarak = 0 simpanJarak() // method untuk menyimpan jarak } else{ latTuj = getLat() // method untuk mengambil nilai latitude lokasi tujuan yang disimpan lngTuj = getLng() // method untuk mengambil nilai longitude lokasi tujuan yang disimpan jarak = getJarak() // method untuk memanggil fungsi Google Maps Direction API jarak = jarak / 1000 simpanJarak() // method untuk menyimpan jarak } } } END

Gambar 4.12 Psuedocode Menghitung jarak antar lokasi

SKRIPSI


GALIH G. A.


66

Nama : Perhitungan Algoritma Genetika Fungsi : untuk mendapatkan urutan rute Input : id_lokasi, jarak Output : daftar urutan rute BEGIN double pc, pm int ukPop, maxGen, gen setParameter() inisialisasiKromosom() // method utk inisialisasi kromosom setPopulasi() // method untuk menyimpan kromosom dalam satu array while(gen <= maxGen){ evaluasi() // method untuk evaluasi tiap kromosom seleksi() // method untuk menyeleksi kromosom crossover() // method untuk crossover kromosom mutation() // method untuk mutasi kromosom relace() // method untuk mengganti populasi lama gen++ } bestKrom() // method untuk mengambil kromosom terbaik END

Gambar 4.13 Psuedocode Perhitungan Algoritma Genetika Nama : Menampilkan Rute Fungsi : untuk menampilkan rute pada peta Input : array urutan rute Output : rute pada peta BEGIN int index = 0 getBestKrom() // method untuk mengambil kromosom terbaik int sizeArray = // variabel ukuran array dari kromosom terbaik pushButton(){ // method apabila ada aksi meng-klik suatu tombol if (index < sizeArray){ index++ showRute() // method untuk menampilkan rute pada peta } else{ showWarning() // method untuk menampilkan pemberitahuan } } END

Gambar 4.14 Psuedocode Menampilkan Rute Hasil dari Algoritma Genetika

SKRIPSI


GALIH G. A.


67

Saat pengguna menjalankan aplikasi, GUI Home akan ditampilkan. Halaman home Sistem Pendukung Keputusan Untuk Optimasi Travelling Salesman Problem Berbasis Sistem Informasi Geografis Dengan Menggunakan Algoritma Genetika dapat dilihat pada Gambar 4.15. Pada tampilan home terdiri dari tiga menu utama, yaitu menu Cari Alamat, menu Daftar Tujuan, dan Tentang. 1.

Menu Cari Alamat Pada menu ini pengguna akan diberikan sebuah tampilan peta, dan beberapa

tombol. Untuk mencari alamat, pengguna dapat meng-klik sebuah tombol kemudian memasukkan sebuah nama lokasi atau alamat yang diinginkan. Setelah itu, sistem akan menampilkan sebuah tanda pada peta (marker), yang dimana marker merupakan hasil dari pencarian lokasi tersebut. Serta, pengguna dapat meng-klik dan tahan pada peta untuk membuat marker, yang kemudian sistem akan mencari informasi alamat tentang lokasi yang telah diberi marker tersebut. Apabila, lokasi tersebut dirasa benar, maka pengguna harus meng-klik tombol dengan ikon “tambah” agar informasi mengenai nama, alamat, dan koordinat lokasi tersebut dapat tersimpan pada database sistem. Tampilan menu Cari Alamat dapat dilihat pada Gambar 4.16. 2.

Menu Daftar Tujuan Pada

menu

ini

pengguna

dapat

menambahkan

atau

menghapus,

menambahkan catatan pada tiap lokasi, dan memproses algorima Genetika untuk melakukan proses penghitungan. Untuk menambahkan alamat, pengguna dapat meng-klik tombol “tambah”, yang kemudian sistem akan menampilkan menu cari

SKRIPSI


GALIH G. A.


68

alamat. Jika ingin menghapus salah satu tujuan pengguna dapat meng-klik dan tahan tujuan yang ingin dihapus atau pengguna juga dapat menghapus semua tujuannya dengan meng-klik tombol “hapus semua”. Penambahan catatan pada lokasi berfungsi sebagai pengingat apabila pengguna lupa jika ada keperluan lain yang ingin disampaikan. Penambahan catatan dapat dilakukan dengan cara mengklik lokasi yang diinginkan kemudian memasukkan catatan yang ingin disimpan pada lokasi tersebut. Setelah semua lokasi yang diinginkan dirasa sudah cukup, maka pengguna meng-klik tombol “proses” untuk memproses perhitungan algoritma Genetika oleh sistem. Kemudian, setelah perhitungan algoritma Genetika selesai, maka sistem akan menampilkan peta dan rute untuk lokasi pertama yang harus dikunjungi terlebih dahulu. Setelah lokasi pertama sudah dikunjungi, maka pengguna meng-klik tombol “Jalan” agar sistem memproses lokasi selanjutnya yang harus dikunjungi, begitu seterusnya sampai semua lokasi terkunjungi. Apabila semua lokasi sudah terkunjungi, maka sistem akan menampilkan peringatan. Tampilan menu Daftar Tujuan dapat dilihat pada Gambar 4.17 dan tampilan rute hasil perhitungan algoritma Genetika dapat dilihat pada Gambar 4.18. 3.

Tentang Pada menu ini pengguna akan mengetahui informasi tentang pembuat dari

sistem ini. Tampilan menu Tentang dapat dilihat pada Gambar 4.19.

SKRIPSI


GALIH G. A.


Gambar 4.15 Tampilan Awal Menu Home

Gambar 4.16 Tampilan Menu Cari Alamat

Gambar 4.17 Tampilan Menu Daftar Tujuan

Gambar 4.18 Tampilan Rute Hasil Perhitungan Algoritma Genetika

69

Gambar 4.19 Tampilan Menu Tentang

SKRIPSI


GALIH G. A.


70

4.6. Pengujian Sistem Uji coba sistem bertujuan untuk memastikan bahwa aplikasi telah dibuat dengan benar sesuai dengan kebutuhan dan tujuan yang diharapkan. Salah satunya dengan cara melakukan pengujian terhadap fitur-fitur dalam sistem dengan menggunakan pengujian Black Box Testing. Pengujian Black Box Testing dapat dilihat pada Tabel 4.16.

No.

1.

2.

3.

4.

5.

6.

Tabel 4.16 Pengujian Sistem dengan Black Box Testing Output yang Output Tujuan Input diharapkan Sistem Klik “Cari Muncul Menampilkan Alamat” Menampilkan peringatan, menu Cari dengan menu Cari tidak ada akses Alamat internet tidak Alamat internet aktif Klik “Cari Alamat” Muncul Menampilkan Menampilkan dengan peringatan, menu Cari menu Cari internet aktif, tidak ada GPS Alamat Alamat GPS tidak aktif aktif Klik “Cari Menampilkan Alamat” Menampilkan Menu Cari menu Cari dengan menu Cari Alamat Alamat internet dan Alamat ditampilkan GPS aktif Muncul Menampilkan Memasukkan Menampilkan pemberitahuan lokasi alamat alamat lokasi alamat , tidak ada tujuan dengan salah tujuan hasil Memasukkan Muncul Menampilkan alamat Menampilkan pemberitahuan lokasi alamat dengan benar lokasi alamat , alamat tujuan tetapi diluar tujuan tersebut berada area batas diluar batas Memasukkan Lokasi alamat Menampilkan alamat Menampilkan ditampilkan lokasi alamat dengan benar lokasi alamat dengan tanda tujuan dan didalam tujuan pada peta batas

SKRIPSI


Keteranga n Gambar 4.20

Gambar 4.21

Gambar 4.22

Gambar 4.23

Gambar 4.24

Gambar 4.25

GALIH G. A.


7.

Menyimpan lokasi alamat tujuan

SKRIPSI

Klik tombol “tambah” dan lokasi alamat dapat ditampilkan

Menyimpan lokasi alamat tujuan

Muncul pemberitahuan , lokasi berhasil disimpan


71

Gambar 4.26

GALIH G. A.


No.

8.

9.

10.

11.

12.

13.

14.

15.

Tujuan

Input

Output yang diharapkan

Output Sistem

Klik tombol Muncul “tambah” dan Menyimpan pemberitahuan lokasi alamat lokasi alamat , harus mencari tidak dapat tujuan alamat dahulu ditampilkan Klik “Daftar Muncul Menampilkan Tujuan” Menampilkan peringatan, menu Daftar dengan menu Daftar tidak ada akses Tujuan internet tidak Tujuan internet aktif Klik “Daftar Tujuan” Menampilkan Menampilkan Muncul dengan menu Daftar menu Daftar peringatan, internet aktif, Tujuan Tujuan GPS tidak aktif GPS tidak aktif Klik “Daftar Menampilkan Tujuan” Menampilkan Menu Daftar menu Daftar dengan menu Daftar Tujuan Tujuan internet dan Tujuan ditampilkan GPS aktif Muncul Melakukan Klik tombol Melakukan peringatan, proses “proses” dan proses harus perhitungan tidak ada perhitungan menambahkan jarak lokasi tujuan jarak alamat dahulu Melakukan Klik tombol Melakukan Proses proses “proses” dan proses perhitungan perhitungan terdapat perhitungan jarak jarak lokasi tujuan jarak dilakukan Rute ditampilkan Menampilkan Klik tombol pada dengan rute setelah Menampilkan “Jalan” dan garis berwarna perhitungan rute pada terdapat biru, dan titik Algoritma peta lokasi tujuan berwarna biru Genetika sebagai lokasi pengguna Menampilkan Muncul Klik tombol rute setelah Menampilkan pemberitahuan “Jalan” dan perhitungan rute pada , semua tujuan tidak terdapat Algoritma peta sudah lokasi tujuan Genetika dikunjungi Menyimpan lokasi alamat tujuan

SKRIPSI


72

Keteranga n Gambar 4.27

Gambar 4.28

Gambar 4.29

Gambar 4.30

Gambar 4.31

Gambar 4.32

Gambar 4.33

Gambar 4.34

GALIH G. A.


No.

Tujuan

16.

Menyimpan catatan pada lokasi tujuan

17.

Mengubah catatan pada lokasi tujuan

18.

Menutup Aplikasi

Input Klik tujuan yang diinginkan dan tidak terdapat catatan yang tersimpan Klik tujuan yang diinginkan dan terdapat catatan yang tersimpan Klik tombol back pada menu utama

73

Output yang diharapkan

Output Sistem

Keteranga n


Muncul konfirmasi, apakah ingin menambah catatan

Gambar 4.35


Muncul catatan yang disimpan untuk diperbarui

Gambar 4.36

Keluar dari aplikasi

Muncul konfirmasi, apakah ingin keluar dari aplikasi

Gmbar 4.37

Gambar 4.20 Gagal menampilkan menu Gambar 4.21 Gagal menampilkan menu Cari Alamat Cari Alamat

SKRIPSI


GALIH G. A.


74

Gambar 4.22 Berhasil menampilkan menu Cari Alamat

Gambar 4.23 Tidak ditemukan hasil pencarian

Gambar 4.24 Gagal menampilkan lokasi alamat

Gambar 4.25 Berhasil menampilkan lokasi alamat dengan tanda pada peta

Gambar 4.26 Berhasil menyimpan lokasi alamat

Gambar 4.27 Gagal menyimpan lokasi alamat

SKRIPSI


GALIH G. A.


75

Gambar 4.28 Gagal menampilkan menu Gambar 4.29 Gagal menampilkan menu Daftar Alamat Daftar Alamat

Gambar 4.30 Berhasil menampilkan menu Daftar Tujuan

SKRIPSI

Gambar 4.31 Gagal memproses perhitungan jarak antar lokasi


GALIH G. A.


76

Gambar 4.32 Berhasil memproses perhitungan jarak antar lokasi

Gambar 4.33 Berhasil menampilkan rute dan lokasi pengguna

Gambar 4.34 Semua lokasi tujuan telah dikunjungi

Gambar 4.35 Konfirmasi apakah ingin menambah catatan

Gambar 4.36 Menampilkan catatan yang disimpan untuk diperbarui

Gambar 4.37 Konfirmasi apakah ingin menutup aplikasi

Setelah dilakukan pengujian Black Box Testing, maka selanjunya adalah melakukan uji coba untuk mengetahui hasil dari Algoritma Genetika dengan menggunakan data daftar kunjungan kurir PT. Sun Star Motor dengan lokasi tujuan sebanyak 5 dan 7 lokasi. Pengujian dilakukan dengan cara mengubah nilai parameter secara satu persatu yaitu ukuran populasi, probabilitas crossover (pc) dan probabilitas mutation (pm) dan maksimal generasi. SKRIPSI


GALIH G. A.


77

Pada pengujian pertama menggunakan lokasi tujuan sebanyak 5 lokasi dan nilai parameter untuk ukuran populasi diujikan nilai sebesar 60, 70, 80, 90, dan 100. Untuk pc sebesar 0,5, pm sebesar 0,1, dan maksimal generasi sebesar 10. Pengujian dilakukan masing-masing 10 kali. Hasil pengujian ukuran populasi dapat dilihat pada Tabel 4.17, pada tabel tersebut dapat dilihat bahwa ukuran populasi 60, 80, 90 dan 100 mempunyai rata-rata fitness yang sama yaitu 40,86. Hal ini disebabkan karena dengan menggunakan Persamaan 2.1 diketahui hanya terdapat 120 kemungkinan yang ada, dimana jumlah kemungkinan tersebut dianggap kecil. Sedangkan ukuran populasi yang diuji cobakan sudah cukup untuk menghasilkan keragaman individu yang banyak sehingga hasil yang didapatkan selalu sama. Pada pengujian ini, yang dipilih untuk pengujian berikutnya adalah ukuran populasi 60. Untuk pengujian generasi, parameter ukuran populasi menggunakan sebesar 60, untuk pc sebesar 0,5, pm sebesar 0,1, dan parameter generasi yang diuji coba mulai dari 10, 15, 20, 25, 30. Pengujian dilakukan dilakukan masing-masing 10 kali. Hasil pengujian generasi dapat dilihat pada Tabel 4.18, pada tabel tersebut dapat dilihat bahwa setiap generasi mempunyai rata-rata fitness yang sama yaitu 40,86. Hal ini disebabkan karena dengan menggunakan Persamaan 2.1 diketahui hanya terdapat 120 kemungkinan yang ada, dimana jumlah kemungkinan tersebut dianggap kecil. Sedangkan banyak jumlah generasi berpengaruh terhadap meningkatnya kemampuan algoritma genetika dalam mencari solusi terbaik. Pada pengujian ini, yang dipilih parameter generasi untuk pengujian selanjutnya yaitu pengujian kombinasi probabilitas crossover (pc) dan probabilitas mutation (pm) adalah 10. Untuk pengujian kombinasi probabilitas crossover (pc) dan probabilitas

SKRIPSI


GALIH G. A.


78

mutation (pm), parameter ukuran populasi menggunakan sebesar 60, parameter generasi sebesar 10, untuk pc dan pm digunakan pengujian berturut-turut yaitu 0,5:0,1; 0,4:0,2; 0,3:0,3; 0,2:0,4; 0,1:0,5. Pengujian dilakukan dilakukan masingmasing 10 kali. Hasil pengujian kombinasi pc dan pm dapat dilihat pada Tabel 4.19, pada tabel tersebut parameter pc dan pm yang bernilai 0,5:0,1; 0,3:0,3; 0,2:0,4; 0,1:0,5 mempunyai rata-rata fitness yang sama yaitu 40,86. Hal ini disebabkan karena dengan menggunakan Persamaan 2.1 diketahui hanya terdapat 120 kemungkinan yang ada, dimana jumlah kemungkinan tersebut dianggap kecil. Sedangkan kombinasi pc dan pm berfungsi untuk mengeksplorasi daerah pencarian. Sehingga, hasil yang didapatkan mempunyai hasil yang sama. Hasil yang diperoleh dari pengujian ini, total jarak yang didapatkan dari pengujian ini sebesar 40,84 kilometer, hasil perolehan sistem dapat dilihat pada Gambar 4.38 sampai Gambar 4.40. Pada Gambar 4.38, dapat dilihat bahwa lokasi awal yang berada di Jalan Sulawesi, sistem menganjurkan untuk mengunjungi lokasi tujuan yang pertama adalah Jalan HR. Muhammad. Kemudian pada Gambar 4.39, dari lokasi awal yang berada di Jalan HR. Muhammad, sistem menganjurkan untuk mengunjungi lokasi tujuan yang kedua adalah Jalan Margorejo Indah XIV No. 603. Kemudian pada Gambar 4.40, dari lokasi awal yang berada di Jalan Margorejo Indah XIV No. 603, sistem menganjurkan untuk mengunjungi lokasi tujuan yang ketiga adalah Jl. Rungkut Industri No. 2 – 4, Surabaya. Kemudian pada Gambar 4.40, dari lokasi awal yang berada di Jl. Rungkut Industri No. 2 – 4, sistem menganjurkan untuk mengunjungi lokasi tujuan yang keempat adalah Jl. Tenggilis Timur VI/1 (AA-25), Surabaya. Kemudian pada Gambar 4.41, dari lokasi awal

SKRIPSI


GALIH G. A.


79

yang berada di Jl. Tenggilis Timur VI/1 (AA-25), sistem menganjurkan untuk mengunjungi lokasi tujuan yang kelima adalah Jl. Arief Rahman Hakim No. 139, Surabaya. Kemudian pada Gambar 4.42, merupakan rute perjalanan yang terakhir dari Jl. Arief Rahman Hakim No. 139, untuk kembali lagi ke lokasi awal dengan alamat Jalan Sulawesi, Gubeng.

SKRIPSI


GALIH G. A.

80


Tabel 4.17 Hasil Uji Coba Pengujian Ukuran Populasi Dengan 5 Lokasi Tujuan Uji Coba keUkuran Populasi PC / PM Maks. Generasi 1 2 3 4 5 6 7 8 60 40,84 40,84 40,84 40,84 40,84 40,84 40,84 40,84 70 41,99 40,84 40,84 40,84 40,84 40,84 40,84 40,84 80 0,5 / 0,1 10 40,84 40,84 40,84 40,84 40,84 40,84 40,84 40,84 90 40,84 40,84 40,84 40,84 40,84 40,84 40,84 40,84 100 40,84 40,84 40,84 40,84 40,84 40,84 40,84 40,84 Tabel 4.18 Hasil Uji Coba Pengujian Maksimal Generasi Dengan 5 Lokasi Tujuan Uji Coba keUkuran Populasi PC / PM Maks. Generasi 1 2 3 4 5 6 7 8 10 40,84 40,84 40,84 40,84 40,84 40,84 40,84 40,84 15 40,84 40,84 40,84 40,84 40,84 40,84 40,84 40,84 60 0,5 / 0,1 20 40,84 40,84 40,84 40,84 40,84 40,84 40,84 40,84 25 40,84 40,84 40,84 40,84 40,84 40,84 40,84 40,84 30 40,84 40,84 40,84 40,84 40,84 40,84 40,84 40,84 Tabel 4.19 Hasil Uji Coba Pengujian Pc dan Pm Dengan 5 Lokasi Tujuan Uji Coba keUkuran Populasi PC / PM Maks. Generasi 1 2 3 4 5 6 7 0,5 / 0,1 40,84 40,84 40,84 40,84 40,84 40,84 40,84 0,4 / 0,2 41,99 40,84 40,84 40,84 40,84 40,84 40,84 60 0,3 / 0,3 10 40,84 40,84 40,84 40,84 40,84 40,84 40,84 0,2 / 0,4 40,84 40,84 40,84 40,84 40,84 40,84 40,84 0,1 / 0,5 40,84 40,84 40,84 40,84 40,84 40,84 40,84 SKRIPSI


8 40,84 40,84 40,84 40,84 40,84

GALIH G. A.

9 40,84 40,84 40,84 40,84 40,84

9 40,84 40,84 40,84 40,84 40,84

9 40,84 40,84 40,84 40,84 40,84

10 40,84 40,84 40,84 40,84 40,84

Rata-rata niai fitness 40,84 40,96 40,84 40,84 40,84

10 40,84 40,84 40,84 40,84 40,84

Rata-rata nilai fitness 40,84 40,84 40,84 40,84 40,84

10 40,84 40,84 40,84 40,84 40,84



81

Gambar 4.38 Rute Perjalanan Pertama Untuk 5 Lokasi Tujuan

Gambar 4.39 Rute Perjalanan Kedua dan Ketiga

Gambar 4.40 Rute Perjalanan Keempat dan Kelima

Gambar 4.41 Rute Perjalanan Terakhir SKRIPSI


GALIH G. A.


82

Pada pengujian kedua menggunakan data lokasi tujuan sebanyak 7 lokasi, untuk parameter ukuran populasi yang diuji coba sebesar 60, 70, 80, 90, 100. Untuk pc sebesar 0,5, pm sebesar 0,1, dan maksimal generasi sebesar 10. Pengujian dilakukan masing-masing 10 kali. Hasil pengujian ukuran populasi dapat dilihat pada Tabel 4.20 untuk perolehan hasil tiap percobaan atau pada Gambar 4.42, pada gambar tersebut dapat dilihat bahwa dari ukuran populasi 60 hingga 90 rata-rata nilai fitness mengalami penurunan. Kemudian pada ukuran populasi 100 rata-rata nilai fitness-nya mengalami kenaikan. Pada umumnya, dengan penambahan ukuran populasi akan meningkatkan nilai fitness karena akan menghasilkan keragaman individu yang lebih banyak, sehingga akan lebih membuka peluang untuk menghasilkan individu yang memiliki nilai fitness yang kecil. Namun dengan ukuran populasi yang besar tersebut waktu untuk komputasi atau menemukan solusi akan lebih lama. Sebaliknya, jika ukuran populasi kecil, maka semakin rendah peluang untuk menemukan individu dengan nilai fitness yang kecil, tetapi waktu untuk menemukan solusi akan lebih cepat. Pada pengujian ini, didapatkan parameter ukuran populasi yang mempunyai rata-rata minimum adalah 80 yang akan digunakan pada pengujian berikutnya yaitu pengujian generasi. Untuk pengujian generasi, parameter ukuran populasi menggunakan sebesar 80, untuk pc sebesar 0,5, pm sebesar 0,1, dan parameter generasi yang diuji coba mulai dari 10, 15, 20, 25, dan 30. Pengujian dilakukan dilakukan masing-masing 10 kali. Hasil pengujian generasi dapat dilihat pada Tabel 4.21 untuk perolehan hasil tiap percobaan atau pada Gambar 4.43, pada gambar tersebut dapat dilihat bahwa ratarata nilai fitness yang dihasilkan dari ukuran generasi 10 hingga 20 mengalami

SKRIPSI


GALIH G. A.


83

kenaikan. Kemudian pada ukuran generasi 25 dan 30 rata-rata fitness-nya mengalami kenaikan. Pada penelitian ini tingginya jumlah generasi belum tentu menghasilkan nilai yang minimum. Selain itu hal tersebut akan membutuhkan waktu lama untuk prosesnya. Pada ukuran generasi 10 merupakan rata-rata fitness yang terendah karena tidak terjadi lagi penurunan rata-rata nilai fitness setelah ukuran generasi diatas 10. Pada pengujian ini didapatkan parameter ukuran generasi yang minimum adalah 10, maka untuk pengujian selanjutnya akan digunakan ukuran generasi sebesar 10. Untuk pengujian kombinasi probabilitas crossover (pc) dan probabilitas mutation (pm), parameter ukuran populasi menggunakan sebesar 80, parameter generasi sebesar 10, untuk pc dan pm digunakan pengujian berturutturut yaitu 0,5:0,1; 0,4:0,2; 0,3:0,3; 0,2:0,4; 0,1:0,5. Pengujian dilakukan dilakukan masing-masing 10 kali. Hasil pengujian kombinasi pc dan pm dapat dilihat pada Tabel 4.22 untuk perolehan hasil tiap percobaan atau pada Gambar 4.44, pada gambar tersebut rata-rata nilai fitness yang paling minimum adalah 57,42 yaitu pada kombinasi pc sebesar 0,3 dan pm sebesar 0,3. Maka dapat disimpulkan kombinasi pc dan pm terbaik pada uji coba ini adalah 0,3 dan 0,3. Apabila menggunakan nilai pc yang rendah dan nilai pm yang rendah maka algoritma genetika akan bekerja seperti random search dan tidak mampu untuk mengeksplorasi daerah pencarian secara efektif. Tetapi jika nilai pc rendah dan pm tinggi maka algoritma genetika tidak akan mampu memperlebar area pencarian.

SKRIPSI


GALIH G. A.


84

Rata - Rata Nilai Fitness (km)

Pengujian Ukuran Populasi (7 Lokasi Tujuan) 59,00 58,50 58,00 57,50 57,00

58,17

58,05

58,05 57,59

60

70

57,59

80 90 Ukuran Populasi

100

Gambar 4.42 Hasil Uji Coba Ukuran Populasi


Pengujian Maksimal Generasi (7 Lokasi Tujuan) 59,00 58,50 58,00 57,50 57,00

57,47

57,59

10

15

57,86

57,52

20 25 Maksimal Generasi

57,76

30

Gambar 4.43 Hasil Uji Coba Maksimal Generasi


Pengujian Kombinasi Pc & Pc (7 Lokasi Tujuan) 59,00 58,50 58,00 57,50 57,00

57,75

57,76

0,5 / 0,1

0,4 / 0,2

57,99

57,94

0,2 / 0,4

0,1 / 0,5

57,42 0,3 / 0,3 Pc / Pm

Gambar 4.44 Hasil Uji Coba Kombinasi Pc dan Pm

SKRIPSI


GALIH G. A.

85

ADLN – PERPUSTAKAAN UNIVERSITAS AIRLANGGA Tabel 4.20 Hasil Uji Coba Pengujian Ukuran Populasi Dengan 7 Lokasi Tujuan Uji Coba keUkuran Populasi PC / PM Maks. Generasi 1 2 3 4 5 6 7 8 60 58,25 57,28 59,09 57,13 58,18 58,18 57,28 60,41 70 57,13 57,13 58,17 60,26 57,28 57,28 57,28 60,42 80 0,5 / 0,1 10 57,13 57,13 57,13 58,17 58,64 58,17 57,13 58,17 90 59,09 57,13 58,17 57,28 58,17 57,28 57,13 57,28 100 57,13 57,13 59,09 57,13 58,17 58,40 58,18 59,85 Tabel 4.21 Hasil Uji Coba Pengujian Maksimal Generasi Dengan 7 Lokasi Tujuan Uji Coba keUkuran Populasi PC / PM Maks. Generasi 1 2 3 4 5 6 7 8 57,28 57,28 58,17 58,17 58,17 57,13 57,13 57,13 10 57,28 57,13 58,25 58,25 57,13 57,13 57,13 58,17 15 58,17 57,13 57,13 57,13 58,17 58,17 58,17 58,17 80 0,5 / 0,1 20 58,17 57,13 57,13 57,13 58,64 58,17 57,28 57,13 25 57,13 58,25 57,13 57,13 57,13 58,25 57,13 58,17 30 Tabel 4.22 Hasil Uji Coba Pengujian Pc dan Pm Dengan 7 Lokasi Tujuan Uji Coba keUkuran Populasi PC / PM Maks. Generasi 1 2 3 4 5 6 7 57,28 57,13 57,13 58,18 57,28 57,13 58,17 0,5 / 0,1 57,13 57,28 58,17 60,26 57,13 57,13 59,09 0,4 / 0,2 57,13 57,28 57,13 57,13 58,64 57,28 57,13 80 0,3 / 0,3 10 58,18 58,40 58,64 57,13 58,17 58,17 57,28 0,2 / 0,4 57,28 58,25 58,80 58,40 58,17 58,64 57,28 0,1 / 0,5 SKRIPSI


8 57,28 57,13 58,18 57,13 57,13

GALIH G. A.

9 57,28 58,40 57,13 57,28 57,28

9 57,13 58,25 58,17 57,13 58,64

9 59,09 57,13 57,13 58,17 57,28

10 58,64 57,13 57,13 57,13 58,17


10 57,13 57,13 58,17 57,28 58,64


10 58,80 57,13 57,13 58,64 58,17



86

Hasil yang diperoleh dari pengujian ini, total jarak yang didapatkan adalah sebesar 57,13 kilometer, hasil perolehan sistem dapat dilihat pada Gambar 4.45 sampai Gambar 4.49. Pada Gambar 4.45, dapat dilihat bahwa lokasi awal yang berada di Jalan Sulawesi, sistem menganjurkan untuk mengunjungi lokasi tujuan yang pertama adalah PT. Wira Bhumi Sejati dengan alamat Jalan Tenggilis Timur VI.1 (AA-25). Kemudian pada Gambar 4.46, dari lokasi awal yang berada di Jalan Tenggilis Timur VI.1 (AA-25), sistem menganjurkan untuk mengunjungi lokasi tujuan yang kedua adalah Jalan Bumi Marina Emas Selatan E82. Kemudian pada Gambar 4.46, dari lokasi awal yang berada di Jalan Bumi Marina Emas Selatan E82, sistem menganjurkan untuk mengunjungi lokasi tujuan yang ketiga adalah Jalan Darmahusada Indah III / L-50. Kemudian pada Gambar 4.47, dari lokasi awal yang berada di Jalan Darmahusada Indah III / L-50, sistem menganjurkan untuk mengunjungi lokasi tujuan yang keempat adalah Jalan Kedinding Tengah II/6. Kemudian pada Gambar 4.47, dari lokasi awal yang berada di Jalan Kedinding Tengah II/6, sistem menganjurkan untuk mengunjungi lokasi tujuan yang kelima adalah Jalan Tidar No. 194. Kemudian pada Gambar 4.48, dari lokasi awal yang berada di Jalan Tidar No. 194, sistem menganjurkan untuk mengunjungi lokasi tujuan yang keenam adalah Jalan Anjasmoro No. 64. Kemudian pada Gambar 4.48, dari lokasi awal yang berada di Jalan Anjasmoro No. 64, sistem menganjurkan untuk mengunjungi lokasi tujuan yang ketujuh adalah Jalan Villa Bukit Emas N-8. Kemudian pada Gambar 4.49, merupakan rute perjalanan yang terakhir dari alamat Jalan Villa Bukit Emas N-8 untuk kembali lagi ke lokasi awal dengan alamat Jalan Sulawesi, Gubeng.

SKRIPSI


GALIH G. A.


87

Gambar 4.45 Rute Perjalanan Pertama Untuk 7 Lokasi Tujuan

Gambar 4.46 Rute Perjalanan Kedua dan Ketiga

Gambar 4.47 Rute Perjalanan Keempat dan Kelima

SKRIPSI


GALIH G. A.


88

Gambar 4.48 Rute Perjalanan Keenam dan Ketujuh

Gambar 4.49 Rute Perjalanan Terakhir (Kembali ke Lokasi Awal) Setelah dilakukan pengujian pada Algoritma Genetika, maka selanjutnya adalah menguji untuk mengetahui output atau respon dari sistem dengan menggunakan data lokasi tujuan yang diperoleh secara acak dan masih berada di wilayah Surabaya. Data-data lokasi tujuan tersebut mewakili perwilayah untuk kota Surabaya. Jumlah data acak tersebut berjumlah 5 lokasi tujuan, karena untuk menyesuaikan jumlah wilayah Surabaya yang terdapat 5 wilayah (Surabaya Utara, Surabaya Barat, Surabaya Timur, Surabaya Selatan, dan Surabaya Pusat). Data acak ini dapat dilihat pada Tabel 4.23. Hasil

yang diperoleh dari pengujian ini, bahwa sistem mampu

mengoptimasikan urutan kunjungan yang harus dikunjungi terlebih dahulu agar memperoleh total jarak yang sub-optimal. Total jarak yang didapatkan dari

SKRIPSI


GALIH G. A.


89

pengujian ini sebesar 67,15 kilometer, hasil perolehan sistem dapat dilihat pada Gambar 4.50 sampai Gambar 4.52. Pada Gambar 4.50, dapat dilihat bahwa lokasi awal yang berada di Jalan Sulawesi, sistem menganjurkan untuk mengunjungi lokasi tujuan yang pertama adalah Jalan Tegalsari No.19, Tegalsari. Kemudian pada Gambar 4.50, dari lokasi awal yang berada di Jalan Tegalsari No. 19, Tegalsari, sistem menganjurkan untuk mengunjungi lokasi tujuan yang kedua adalah Jalan Rajawali No. 34, Krembangan. Kemudian pada Gambar 4.51, dari lokasi awal yang berada di Jalan Rajawali No.34, Krembangan, sistem menganjurkan untuk mengunjungi lokasi tujuan yang ketiga adalah Jalan Raya Sememi Surabaya No. 8, Benowo. Kemudian pada Gambar 4.51, dari lokasi awal yang berada di Jalan Raya Sememi Surabaya No. 8, Benowo, sistem menganjurkan untuk mengunjungi lokasi tujuan yang keempat adalah Jalan Pagesangan IIA No. 41, Jambangan. Kemudian pada Gambar 4.52, dari lokasi awal yang berada di Jalan Pagesangan IIA No.41, Jambangan, sistem menganjurkan untuk mengunjungi lokasi tujuan yang kelima adalah Jalan Pandugo No.91, Rungkut. Kemudian pada Gambar 4.52, merupakan rute perjalanan yang terakhir dari alamat Jalan Pandugo No. 91 untuk kembali lagi ke lokasi awal dengan alamat Jalan Sulawesi, Gubeng. Nomor 1 2 3 4 5

SKRIPSI

Tabel 4.23 Daftar Alamat Secara Acak Alamat Wilayah Jalan Tegalsari No. 19, TegalSari Surabaya Pusat Jalan Pandugo No. 91, Rungkut Surabaya Timur Jalan Pagesangan II A No.41, Surabaya Selatan Jambangan Jalan Raya Sememi Surabaya No. 8, Surabaya Barat Benowo Jalan Rajawali No. 34, Krembangan Surabaya Utara


GALIH G. A.


90

Gambar 4.50 Rute Perjalanan Pertama dan Rute Perjalanan Kedua

Gambar 4.51 Rute Perjalanan Ketiga dan Rute Perjalanan Keempat

Gambar 4.52 Rute Perjalanan Kelima dan Rute Perjalanan Terakhir (Kembali ke Lokasi Awal) 4.7. Evaluasi Sistem Pada evaluasi sistem dilakukan untuk menilai seberapa baik kinerja dari aplikasi yang telah dibuat. Setelah dilakukan beberapa kali percobaan, tahap selanjutnya yang dilakukan adalah mengevaluasi kinerja dari sistem untuk melihat tanggapan atau respon pengguna terhadap fungsionalitas, fitur-fitur, dan tampilan

SKRIPSI


GALIH G. A.


91

antarmuka pada aplikasi ini. Untuk melihat tanggapan atau respon pengguna dilakukan pemberian kuesioner kepada kurir perusahaan. Hasil dari evaluasi sistem yang dapat dilihat pada Lampiran 2 yaitu, antarmuka sistem dari segi desain dan tampilan aplikasi dinilai baik dan cukup interaktif. Dari segi kemudahan penggunaan sistem yang dibuat mudah untuk digunakan. Dan dari segi kesesuaian kebutuhan sistem yang dibuat sudah sesuai dengan kebutuhan.

SKRIPSI


GALIH G. A.


BAB V KESIMPULAN DAN SARAN 5.1. Kesimpulan Rancang Bangun Sistem untuk Optimasi Travelling Salesman Problem Berbasis Sistem Informasi Geografis dapat diambil kesimpulan bahwa rancang bangun sistem dilakukan melalui beberapa tahap sebagai berikut: 1. Melakukan pengumpulan dan pengolahan dengan menggunakan studi literatur, wawancara, dan pengambilan data. Studi literatur digunakan untuk mengetahui proses dalam menggunakan metode Algoritma Genetika. Wawancara digunakan untuk menggali informasi guna mengetahui lokasi awal dari perjalanan, kendaraan yang digunakan, kendala yang dihadapi, serta jumlah lokasi paling banyak yang pernah dilalui. Sedangkan pengambilan data digunakan untuk mengambil data daftar kunjungan yang pernah dilakukan. 2. Menentukan total jarak yang sub-optimal dengan menggunakan Algoritma Genetika. 3. Perancangan sistem menggunakan use case diagram, activity diagram, dan perancangan antarmuka. 4. Implementasi sistem dilakukan dengan menulis algoritma dan membuat antarmuka aplikasi. 5. Pengujian dilakukan dengan pengujian Black Box Testing yang diperoleh hasil bahwa sistem yang telah dibuat dengan benar. Fitur-fitur yang ada telah mencapai tujuan yang diharapkan. Untuk menentukan

SKRIPSI


GALIH G. A.


93

parameter algoritma genetika yang digunakan pada sistem ini maka dilakukan pengujian tiap parameternya diantaranya ukuran populasi, kombinasi antara probabilitas crossover (pc) dan probabilitas mutation (pm), dan jumlah generasi. Hasil dari pengujian parameter untuk data daftar kunjungan kurir dengan 5 lokasi didapatkan hasil ukuran populasi 60, jumlah generasi 10, pc 0,5 dan pm 0,1 yang memiliki rata-rata nilai fitness terendah sebesar 40,84 kilometer. Sedangkan untuk data daftar kunjungan kurir dengan 7 lokasi didapatkan hasil ukuran populasi 80, generasi 10, pc 0,3 dan pm 0,3 yang memiliki rata-rata nilai fitness terendah sebesar 57,42 kilometer. 6. Evaluasi sistem dilakukan dengan kuesioner yang diisi oleh pihak kurir perusahaan diperoleh bahwa secara keseluruhan sistem sesuai dengan kebutuhan dan mudah digunakan. 5.2. Saran Dalam penelitian ini diperlukan pengembangan untuk penelitian selanjutnya. Hal ini dilakukan untuk meningkatkan kinerja dari sistem yang telah dibuat. Halhal yang dapat dikembangkan lebih lanjut adalah: 1. Penyempurnaan antarmuka dan menambah fitur-fitur pendukung untuk kurir. 2. Aplikasi dapat ditambahkan dengan fitur petunjuk arah, dapat melalui suara ataupun berupa tulisan.

SKRIPSI


GALIH G. A.


DAFTAR PUSTAKA Atiyatna, V. (2012). Penyelesaian Travelling Salesman Problem (TSP) Asimetris Dengan Algoritma Genetik Commonality. Jember: Universitas Jember. Baharuddin, A., Shididiqi, A. M., & Pratomo, B. A. (2012). Travelling Salesman Problem Menggunakan Algoritma Genetika Via GPS Berbasis Android. Surabaya: Institut Teknologi Sepuluh Nopember. Devi, O. C., Mahmudy, W. F., & Setiawan, B. D. (2015). Penerapan Algoritma Genetika untuk Penjadwalan Asisten Praktikum. Malang: Universitas Brawijaya. Fitrah, A., Zaky, A., & Fitrasani. (2006). Penerapan Algoritma Genetika Pada Persoalan Pedagang Keliling (TSP). Bandung: Institut Teknologi Bandung. Gen, M., Cheng, R., & Lin, L. (2008). Network Models and Optimization. London: Springer. Hayati, E. N., & Yohanes, A. (2014). Pencarian Rute Terpendek Menggunakan Algoritma Greedy. Semarang: Universitas Stikubank Semarang. Hingrajiya, K. H., Gupta, R. K., & Chandel, G. S. (2012). An Ant Colony Optimization Algorithm for Solving Travelling Salesman Problem. Bhopal: University of Rajiv Gandhi Proudyogiki Vishwavidyalaya. Husein, R. (2007, Januari 27). Konsep Dasar Sistem Informasi Geografis. Retrieved from IlmuKomputer.Com: http://ilmukomputer.org/2007/01/27/konsep-dasar-sig/ Ichtiara, C. (2008). Implementasi Aplikasi Sistem Informasi Geografis (SIG) Universitas Indonesia (UI) Berbasis Web Dengan Menggunakan Google Maps API. Depok: Universitas Indonesia. Indrakarna, P. A., Sutanto, T., & Taufik, V. M. (2012). Rancang Bangun Sistem Informasi Pelacakan Dan Pemantauan Paket Kiriman Berbasis Web Dengan Bantuan Mobile Android. Surabaya: Sekolah Tinggi Manajemen Informatika & Teknik Komputer. Kurniawan, I. (2010). Sistem Informasi Geografis Berbasis Web Sebagai Penentu Shortest Path Dengan Menggunakan Algoritma Dijkstra. Medan: Universitas Sumatera Utara. Lukas, S., Anwar, T., & Yuliani, W. (2005). Penerapan Algoritma Genetika Untuk Travelling Salesman Problem Dengan Menggunakan Metode Order

SKRIPSI


GALIH G. A.


95

Crossover Dan Insertion Mutation. Tangerang: Universitas Pelita Harapan. Nalloh, A. A., Sunandar, A., & Dimitra, D. I. (2013). Analisis dan Perancangan Sistem Informasi Geografis Berbasis Web Untuk Lokasi Tempat Wisata Di DKI Jakarta. Jakarta: Universitas Bina Nusantara. Neuman, F., & Witt, C. (2010). Bioinspired Computation in Combinatorial Optimization. Saarbrucken: Springer. Nughroho, H. F. (2011). Aplikasi Mobile Pencarian Lokasi Distro di Yogyakarta Berbasis Android. Yogyakarta: Sekolah Tinggi Manajemen Informatika dan Komputer Amikom Yogyakarta. Obitko, M. (1998, August). Recommendations: Introduction to Genetic Algorithm - Tutorials with Interactive Java Applets. Retrieved from Introduction to Genetic Algorithms: http://obitko.com/tutorials/geneticalgorithms/recommendations.php Pratiwi, R., Shiddiqi, A. M., & Pratomo, B. A. (2012). Aplikasi Mobile Pencarian Rute Transport Umum Dengan Algoritma Best-Path Planning Pada Platform Android. Surabaya: Institut Teknologi Sepuluh Nopember. Sadiq, S. (2012). The Travelling Salesman Problem: Optimizing Delivery Route Using Genetic Algorithm. Chicago: SAS Global Forum. Sari, K. (2005). Algoritma Genetik Dengan Order Crossover Pada Travelling Salesman Problem. Surabaya: Universitas Airlangga. Sastry, K., Goldberg, D., & Kendall, G. (2005). Search Methodologies. Introductory Tutorials in Optimization and Decision Support Techniques. New York: Springer. Scrucca, L. (2013). GA: A Package for Genetic Algoruthms in R. Perugia: Universitas Degli Studi. Sivanandam, S. N., & Deepa, S. N. (2008). Introduction to Genetic Algorithm. New York: Springer Berlin Heidelberg. Sriparasa, S. S. (2013). JavaScript And JSON Essentials. Birmingham: Packt. Suyanto. (2014). Artificial Intelligence. Bandung: Informatika. Zukhri, Z. (2014). Algoritma Genetika Metode Komputasi Evolusioner Untuk Menyelesaikan Masalah Optimasi. Yogyakarta: ANDI.

SKRIPSI


GALIH G. A.

Lampiran 1-1 ADLN – PERPUSTAKAAN UNIVERSITAS AIRLANGGA

LAMPIRAN Lampiran 1 : Outline Wawancara dengan kurir

SKRIPSI


GALIH G. A.


SKRIPSI


GALIH G. A.


Lampiran 2 : Kuesioner Evaluasi Sistem

SKRIPSI


GALIH G. A.


SKRIPSI


GALIH G. A.

Lampiran 3-1 ADLN – PERPUSTAKAAN UNIVERSITAS AIRLANGGA Lampiran 3 : Wawancara untuk Pengambilan Data Daftar Kunjungan Kurir

SKRIPSI


GALIH G. A.


SKRIPSI


GALIH G. A.

ADLN PERPUSTAKAAN UNIVERSITAS AIRLANGGA

Recommend Documents