SISTEM INFORMASI JALUR OPTIMAL TRANSPORTASI UMUM (TAKSI) BERBASIS MOBILE MENGGUNAKAN METODE ALGORITMA GENETIKA. (Studi Kasus: Denpasar Utara)

SISTEM INFORMASI JALUR OPTIMAL TRANSPORTASI UMUM (TAKSI) BERBASIS MOBILE MENGGUNAKAN METODE ALGORITMA GENETIKA (Studi Kasus: Denpasar Utara)

KOMPETENSI REKAYASA PERANGKAT LUNAK

SKRIPSI

I WAYAN ADITYA SETIAWAN NIM. 1208605057

PROGRAM STUDI TEKNIK INFORMATIKA JURUSAN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS UDAYANA BUKIT JIMBARAN 2016

SURAT PERNYATAAN KEASLIAN KARYA ILMIAH Yang bertanda tangan di bawah ini menyatakan bahwa naskah Skripsi dengan judul: ……………………………………………………………………………………… ……………………………………………………………………………………… Nama

: I Wayan Aditya Setiawan

NIM

: 1208605057

Program Studi : Teknik Informatika E-mail

: [email protected]

Nomor telp/HP : 089619920577 Alamat

: Jalan Ahmad Yani No.379 Peguyangan Denpasar

Belum pernah dipublikasikan dalam dokumen skripsi, jurnal nasional maupun internasional atau dalam prosiding manapun, dan tidak sedang atau akan diajukan untuk publikasi di jurnal atau prosiding manapun. Apabila di kemudian hari terbukti terdapat pelanggaran kaidah-kaidah akademik pada karya ilmiah saya, maka saya bersedia menanggung sanksi-sanksi yang dijatuhkan karena kesalahan tersebut, sebagaimana diatur oleh Peraturan Menteri Pendidikan Nasional Nomor 17 Tahun 2010 tentang Pencegahan dan Penanggulangan Plagiat di Perguruan Tinggi. Demikian Surat Pernyataan ini saya buat dengan sesungguhnya untuk dapat dipergunakan bilamana diperlukan.

Denpasar, Juni 2016 Yang membuat pernyataan,

Materai (I Wayan Aditya Setiawan) NIM. 1208605057

ii

LEMBAR PENGESAHAN TUGAS AKHIR

iii

Judul

Nama Nim Pembimbing I Pembimbing II

: Sistem Informasi Jalur Optimal Transportasi Umum (Taksi) Berbasis Mobile Menggunakan Metode Algoritma Genetika. Studi Kasus: Denpasar Utara. : I Wayan Aditya Setiawan : 1208605057 : I Gede Santi Astawa, S.T., M.Cs. : I Dewa Made Bayu Atmaja Darmawan, S.Kom.,M.Cs.

ABSTRAK Permasalahan yang dihadapi oleh sarana transportasi umum, khususnya taksi dalam mengantarkan penumpang adalah rute perjalanan yang dilalui tidak optimal dari posisi asal ke posisi tujuan. Dimana dalam pengoprasianya, taksi yang memiliki rute perjalanan yang tidak optimal, dapat menyebabkan waktu dan jarak tempuh menjadi tidak efisien, sehingga kenyamanan dan kelancaran penggunanya berkurang. Terdapat beberapa metode yang digunakan untuk menyelesaikan masalah optimasi jalur, salah satunya adalah Algoritma Genetika. Dipilihnya algoritma genetika dalam penyelesaian permasalahan jalur optimal dikarenakan jarak yang dihasilkan serta waktu yang dibutuhkan untuk melakukan perhitungan lebih baik untuk jumlah kota (search space) yang banyak, yang disertai dengan pemilihan parameter input yang tepat. Dari hasil pengujian yang telah dilakukan, metode algoritma genetika sudah mampu digunakan untuk memberikan jalur optimal berdasarkan waktu tempuh dari posisi asal ke posisi tujuan. Hal tersebut dilihat dari hasil pengujian akurasi algoritma genetika sebanyak 10 percobaan, di mana 8 dari 10 percobaan yang telah di lakukan dengan pemilihan parameter input untuk pop size adalah 60, probabilitas crossover (Pc) adalah 0.6, probabilitas mutasi (Pm) adalah 0.01, dan batas generasi untuk kriteria berhenti adalah 50, dapat diimplementasikan representasi jalur optimal yang diberikan telah sesuai dengan representasi jalur yang ada pada aplikasi pencarian Google Maps. Kata Kunci : Algoritma Gentetika, Optimasi Jalur, Taksi

iv

Title

: Optimal Path Information System of Public Transport (Taxis) with Mobile-Based Method Using Genetic Algorithm. A Case Study: Northern Denpasar. Name : I Wayan Aditya Setiawan Registration : 1208605057 First Supervisor : I Gede Santi Astawa, S.T., M.Cs. Second Supervisor : I Dewa Made Bayu Atmaja Darmawan, S.Kom.,M.Cs.

ABSTRACT Problems faced by means of public transport, especially taxis in taking their passengers are the inefficient routes taken from the home positions to the destination positions. In the operations, taxis which have inefficient travel routes can lead to inefficient time and mileage, so the convenience and speed of service will decline. There are several methods used to solve optimization of path problems, one of which is through Genetic Algorithm. Genetic algorithms have in solving problems of optimal paths, due to the resulting distance and time needed to perform better calculation for the number of cities (search space), which is accompanied by the right input of parameter selection. From the testing that has been carried out, the method of genetic algorithms has been able to provide an optimal path based on the travel time from the home position to the destination position. It can be seen from the results of testing the accuracy of the genetic algorithm as many as 10 experiments, in which 8 of the 10 experiments that have been done with the selection of input parameters to pop size was 60, the probability of crossover (Pc) was 0.6, the probability of mutation (Pm) was 0:01, and the limit generation for stopping criteria was 50, it can be implemented representations of the provided optimal path in line with the representation of the existing path in the search application of Google Maps. Keywords: Genetic Algorithm, Optimization of Path, Taxis

v

KATA PENGANTAR Puji syukur penulis panjatkan kehadapan Tuhan Yang Maha Esa, karena berkat rahmat dan karunia-Nya, Tugas Akhir yang berjudul “Sistem Informasi Jalur Optimal Transportasi Umum (Taksi) Berbasis Mobile Menggunakan Metode Algoritma Genetika. Studi Kasus : Denpasar Utara” ini dapat diselesaikan tepat pada waktunya. Secara khusus penulis mengucapkan terima kasih dan penghargaan kepada berbagai pihak yang telah membantu penelitian ini, yaitu : 1.

2.

3.

4.

5.

6. 7.

8.

Bapak I Gede Santi Astawa, ST, M.Cs selaku Pembimbing I yang telah meluangkan waktu untuk memberikan bimbingan, saran dan masukan dalam penyempurnaan Tugas Akhir ini. Bapak I Dewa Made Bayu Atmaja Darmawan, S.Kom.,M.Cs selaku Pembimbing II yang telah banyak membantu dan meluangkan waktu untuk penyempurnaan Tugas Akhir ini. Bapak Agus Muliantara, S.Kom., M.Kom. selaku Ketua Jurusan Ilmu Komputer Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Udayana yang telah banyak memberikan masukan dan motivasi sehingga memperlancar dalam proses pelaksanaan penelitian ini. Bapak-bapak dan Ibu-ibu dosen di Jurusan Ilmu Komputer yang telah memberikan masukan, saran, dan nasehat guna kelengkapan Tugas Akhir ini. Bapak I Wayan Saniasa (Kepala) dan Dewa Putu Agus Widnyana (Staff) Rekayasa Lalu Lintas Dinas Perhubungan Kota Denpasar yang telah banyak membantu dalam proses penelitian data yang digunakan pada penelitian ini. Seluruh rekan-rekan mahasiswa di Jurusan Ilmu Komputer yang telah memberikan motivasi dan doa dalam proses penelitian ini. I Wayan Pio Pratama, S,Kom., IGA Surya Darmana, S.Kom., Sista Pradjna Paramitha, S.Kom., Ratna Sri Andi Yani, S.Kom., Agus Winartha, Dedik Amijaya sebagai sahabat yang sudah banyak membantu dalam memberikan saran, kritik, dan pemecahan masalah selama proses pelaksanaan penelitian. I Nyoman Suarcana, I Wayan Purniati, Ir. Sri. Suryadani, Siti Marlinda, Adina Striratna, SH, Herry Dwi Suputra, Ayu Sri Laksmi sebagai keluarga yang terus memberikan doa, semangat dan dukungan dalam penyelesaian penelitian ini.

Penulis menyadari bahwa Tugas Akhir ini masih belum sempurna, untuk itu kritik dan saran yang bermanfaat demi kesempurnaan Tugas Akhir ini sangat dihrapakan. Bukit Jimbaran, Juni 2016 Penulis vi

DAFTAR ISI

SURAT PERNYATAAN KEASLIAN KARYA ILMIAH .................................... ii LEMBAR PENGESAHAN TUGAS AKHIR ....................................................... iii ABSTRAK ............................................................................................................. iii ABSTRACT ............................................................................................................ v KATA PENGANTAR ........................................................................................... vi DAFTAR ISI ......................................................................................................... vii DAFTAR TABEL .................................................................................................. ix DAFTAR GAMBAR ............................................................................................ xii DAFTAR LAMPIRAN ......................................................................................... xv BAB I PENDAHULUAN ....................................................................................... 1 1.1 Latar Belakang .............................................................................................. 1 1.2 Rumusan Masalah ......................................................................................... 2 1.3 Batasan Masalah ............................................................................................ 3 1.4 Tujuan Penelitian........................................................................................... 3 1.5 Manfaat Penelitian......................................................................................... 3 1.6 Metodologi Penelitian ................................................................................... 4 BAB II TINJAUAN PUSTAKA............................................................................. 7 2.1 Graf…............................................................................................................ 7 2.2 Transportasi ................................................................................................... 8 2.3 Perlambatan Lalu Lintas ............................................................................. 10 2.4 Algoritma Genetika ..................................................................................... 12 2.5 Kota Denpasar ............................................................................................. 20 2.6 Sistem Operasi Android .............................................................................. 21 2.7 Metode Pengembangan Perangkat Lunak Waterfall ................................... 23 2.8 Strategi Pengujian Perangkat Lunak ........................................................... 24 2.9 Tinjauan Studi ............................................................................................. 25 2.10 Rangkuman Perbandingan Penelitian ……............................................... 27 BAB III ANALISIS DAN PERANCANGAN ..................................................... 29 3.1 Pemodelan Jalur Taksi ................................................................................ 29 3.2 Perancangan Sistem..................................................................................... 33 BAB IV HASIL DAN PEMBAHASAAN ........................................................... 69 vii

4.1 Lingkungan Implementasi ........................................................................... 69 4.2 Implementasi Basis Data ............................................................................. 69 4.3 Implmentasi Algoritma Genetika ................................................................ 71 4.4 Implementasi Antarmuka Sistem ................................................................ 85 4.5 Pengujian ..................................................................................................... 96 BAB V PENUTUP .............................................................................................. 144 5.1 Kesimpulan................................................................................................ 144 5.2 Saran….. .................................................................................................... 144 DAFTAR PUSTAKA ......................................................................................... 145 LAMPIRAN ........................................................................................................ 148

viii

DAFTAR TABEL Tabel 2.1 Pengkodean Biner ................................................................................. 14 Tabel 2.2 Pengkodean Permutasi .......................................................................... 15 Tabel 2.3 Pengkodean Nilai .................................................................................. 15 Tabel 2.4 Tabel Tinjauan Studi ............................................................................. 25 Tabel 3.1 Rata – Rata Kecepatan Kendaraan Umum ............................................ 32 Tabel 3.2 Analisis Kebutuhan Fungsional ............................................................ 33 Tabel 3.3 Kecepatan Proses Pencarian Jalur Optimal ........................................... 36 Tabel 3.4 Skenario Pengujian Blackbox Testing .................................................. 67 Tabel 3.5 Skenario Pengujian Algoritma Genetika............................................... 67 Tabel 3.6 Skenario Pengujian Akurasi Algoritma Genetika ................................. 68 Tabel 4.1 Source Code Proses Inisialisasi Populasi .............................................. 71 Tabel 4.2 Source Code Proses Representasi Kromosom ...................................... 72 Tabel 4.3 Source Code Proses Perbaikan Random ............................................... 73 Tabel 4.4 Source Code Proses Evaluasi Fungsi Fitness ........................................ 74 Tabel 4.5 Source Code Proses Menghitung Total Fitness .................................... 75 Tabel 4.6 Source Code Menghitung Probabilitas Kumulatif ................................ 75 Tabel 4.7 Source Code Proses Interval Kumulatif ................................................ 76 Tabel 4.8 Source Code Proses Membangkitkan Bilangan Random ..................... 76 Tabel 4.9 Source Code Proses Penempatan Kromosom Menurut Interval ........... 76 Tabel 4.10 Source Code Daftar Populasi Orang Tua ............................................ 77 Tabel 4.11 Source Code Proses Crossover ........................................................... 78 Tabel 4.12 Source Code Proses Mutasi................................................................. 79 Tabel 4.13 Source Code Proses Validasi Jalur...................................................... 80 Tabel 4.14 Source Code Proses Pengabungan Kromosom Orang Tua dan Anak 81 Tabel 4.15 Source Code Proses Evaluasi Fitness, Pembentukan Populasi Baru .. 82 Tabel 4.16 Source Code Proses Kriteria Berhenti ................................................ 83 Tabel 4.17 Source Code Proses Pemilihan Jalur Optimal..................................... 84 Tabel 4.18 Checklist Kebutuhan Pengujian Black Box ........................................ 96 Tabel 4.19 Pengujian Kebutuhan Input Persimpangan ......................................... 97 Tabel 4.20 Pengujian Kebutuhan Input Wilayah .................................................. 98 Tabel 4.21 Pengujian Kebutuhan Mencari Jalur Optimal ..................................... 99 Tabel 4.22 Pengujian Proses Melihat Daftar Persimpangan ............................... 100 Tabel 4.23 Pengujian Proses Melihat Panduan ................................................... 102

ix

Tabel 4.24 Pengujian Validasi Input Proses Login ............................................. 103 Tabel 4.25 Pengujian Proses Create Data Node ................................................. 104 Tabel 4.26 Pengujian Proses Create Data Edge .................................................. 105 Tabel 4.27 Pengujian Proses Create Data Jalan .................................................. 106 Tabel 4.28 Pengujian Proses Create Data Wilayah ............................................. 107 Tabel 4.29 Pengujian Proses Read Data Node .................................................... 108 Tabel 4.30 Pengujian Proses Read Data Edge .................................................... 108 Tabel 4.31 Pengujian Proses Read Data Jalan .................................................... 109 Tabel 4.32 Pengujian Proses Read Data Wilayah ............................................... 109 Tabel 4.33 Pengujian Proses Read Data Admin ................................................. 109 Tabel 4.34 Pengujian Proses Update Data Node ................................................ 110 Tabel 4.35 Pengujian Proses Update Data Edge ................................................. 110 Tabel 4.36 Pengujian Proses Update Data Jalan ................................................. 111 Tabel 4.37 Pengujian Proses Update Data Wilayah ........................................... 112 Tabel 4.38 Pengujian Proses Update Data Admin .............................................. 112 Tabel 4.39 Pengujian Proses Delete Data Node ................................................. 113 Tabel 4.40 Pengujian Proses Delete Data Edge .................................................. 113 Tabel 4.41 Pengujian Proses Delete Data Jalan .................................................. 114 Tabel 4.42 Pengujian Proses Delete Data Wilayah ............................................. 115 Tabel 4.43 Pengujian Proses Melihat Laporan ................................................... 115 Tabel 4.44 Pengujian Agen Proses Representasi Kromosom ............................. 116 Tabel 4.45 Pengujian Agen Proses Inisialisasi Populasi ..................................... 118 Tabel 4.46 Pengujian Agen Proses Menghitung Fungsi Fitness ......................... 120 Tabel 4.47 Pengujian Agen Seleksi Roullete Wheel .......................................... 120 Tabel 4.48 Pengujian Agen Proses Crossover .................................................... 124 Tabel 4.49 Pengujian Agen Proses Mutasi ......................................................... 127 Tabel 4.50 Pengujian Agen Proses Pembentukan Populasi Baru ....................... 130 Tabel 4.51 Percobaan 1 Pengujian Akurasi Algoritma Genetika ....................... 134 Tabel 4.52 Percobaan 2 Pengujian Akurasi Algoritma Genetika ....................... 135 Tabel 4.53 Percobaan 3 Pengujian Akurasi Algoritma Genetika ....................... 136 Tabel 4.54 Percobaan 4 Pengujian Akurasi Algoritma Genetika ....................... 137 Tabel 4.55 Percobaan 5 Pengujian Akurasi Algoritma Genetika ....................... 138 Tabel 4.56 Percobaan 6 Pengujian Akurasi Algoritma Genetika ....................... 139 Tabel 4.57 Percobaan 7 Pengujian Akurasi Algoritma Genetika ....................... 140 Tabel 4.58 Percobaan 8 Pengujian Akurasi Algoritma Genetika ....................... 140 Tabel 4.59 Percobaan 9 Pengujian Akurasi Algoritma Genetika ....................... 141 x

Tabel 4.60 Percobaan 10 Pengujian Akurasi Algoritma Genetika ..................... 142

xi

DAFTAR GAMBAR Gambar 2.1 Graf Sederhana .................................................................................... 7 Gambar 2.2 Graf Tidak Berarah.............................................................................. 8 Gambar 2.3 Graf Berarah ........................................................................................ 8 Gambar 2.4 Diagram Standar Algoritma Genetika ............................................... 14 Gambar 2.5 Pengkodean Pohon ............................................................................ 15 Gambar 2.6 Activity Diagram Proses Probabilitas Crossover .............................. 18 Gambar 2.7 Activity Diagram Proses Probabilitas Mutasi ................................... 19 Gambar 2.8 Perspektif Kota Denpasar .................................................................. 21 Gambar 2.9 Metode Pengembangan Perangkat Lunak Waterfall ......................... 23 Gambar 3.1 Pemodelan Graf Denpasar Utara ....................................................... 31 Gambar 3.2 Use Case Diagram ............................................................................. 38 Gambar 3.3 Activity Diagram Login Admin ........................................................ 40 Gambar 3.4 Activity Diagram Insert Data ............................................................ 41 Gambar 3.5 Activity Diagram Update Data .......................................................... 42 Gambar 3.6 Activity Diagram Delete Data ........................................................... 43 Gambar 3.7 Activity Diagram Melihat Report Data ............................................. 44 Gambar 3.8 Activity Diagram Mencari Jalur Optimal.......................................... 45 Gambar 3.9 Activity Diagram Daftar Persimpangan ............................................ 46 Gambar 3.10 Activity Diagram Melihat Panduan................................................. 47 Gambar 3.11 Activity Diagram Algoritma Genetika ............................................ 47 Gambar 3.12 Sequence Diagram Proses Login..................................................... 50 Gambar 3.13 Sequence Diagram Insert Data ........................................................ 51 Gambar 3.14 Sequence Diagram Update Data ..................................................... 51 Gambar 3.15 Sequence Diagram Delete Data....................................................... 52 Gambar 3.16 Sequence Diagram Mencari Jalur Optimal ..................................... 53 Gambar 3.17 Sequence Diagram Melihat Daftar Persimpangan .......................... 54 Gambar 3.18 Sequence Diagram Melihat Panduan .............................................. 55 Gambar 3.19 Class Diagram ................................................................................. 56 Gambar 3.20 Entitiy Relationship Diagram .......................................................... 57 Gambar 3.21 Tampilan Halaman Login................................................................ 58 Gambar 3.22 Tampilan Header dan Home Screen................................................ 59 Gambar 3.23 Tampilan Data Access dan Feature ................................................. 60 Gambar 3.24 Tampilan Help, Dinas Perhubungan, dan Footer ............................ 61

xii

Gambar 3.25 Tampilan Halaman Datatable .......................................................... 61 Gambar 3.26 Tampilan Insert Data ....................................................................... 62 Gambar 3.27 Tampilan Edit Data ......................................................................... 62 Gambar 3.28 Tampilan Delete Data...................................................................... 63 Gambar 3.29 Tampilan Halaman Report Data ...................................................... 63 Gambar 3.30 Tampilan Splash Screen dan Halaman Awal .................................. 64 Gambar 3.31 Tampilan Halaman Pencarian Rute Optimal ................................... 65 Gambar 3.32 Tampilan Halaman Daftar Persimpangan ....................................... 66 Gambar 3.33 Tampilan Halaman Melihat Panduan .............................................. 66 Gambar 4.1 Implementasi Basis Data ................................................................... 69 Gambar 4.2 Implementasi Halaman Login ........................................................... 86 Gambar 4.3 Implementasi Halaman Awal (Home)............................................... 87 Gambar 4.4 Implementasi Halaman Datatable ..................................................... 89 Gambar 4.5 Implementasi Tampilan Pop-Up Insert Data ..................................... 90 Gambar 4.6 Implementasi Tampilan Pop-Up Update Data .................................. 90 Gambar 4.7 Implementasi Tampilan Pop-Up Delete Data ................................... 91 Gambar 4.8 Implementasi Halaman Report Data ................................................. 91 Gambar 4.9 Implementasi Splash Screen Dan Halaman Awal ............................. 92 Gambar 4.10 Implementasi Halaman Mencari Jalur Optimal .............................. 93 Gambar 4.11 Implementasi Halaman Simulasi Jalur Optimal .............................. 94 Gambar 4.12 Implementasi Halaman Daftar Persimpangan ................................. 94 Gambar 4.13 Implementasi Halaman Panduan ..................................................... 95 Gambar 4.14 Implementasi Tampilan Konten Menu Panduan ............................. 96 Gambar 4.15 Hasil Proses Membangkitkan Kromosom Acak ........................... 117 Gambar 4.16 Hasil Proses Perbaikan Random Kromosom ................................ 117 Gambar 4.17 Jalur Pada Kromosom Yang Valid ................................................ 118 Gambar 4.18 Jalur Pada Kromosom Yang Tidak Valid ..................................... 118 Gambar 4.19 Hasil Proses Inisialisasi Populasi .................................................. 119 Gambar 4.20 Hasil Proses Menghitung Nilai Fitness ......................................... 120 Gambar 4.21 Hasil Proses Total Nilai Fitness .................................................... 122 Gambar 4.22 Hasil Proses Probabilitas Kumulatif ............................................. 122 Gambar 4.23 Hasil Proses Interval Kumulatif .................................................... 122 Gambar 4.24 Hasil Proses Membangkitkan Bilangan Acak ............................... 123 Gambar 4.25 Hasil Proses Pemetaan Kromosom Hasil Bilangan Random ........ 123 Gambar 4.26 Daftar Populasi Orang Tua Terpilih .............................................. 124 Gambar 4.27 Hasil Kromosom Terpilih Secara Acak ........................................ 125 xiii

Gambar 4.28 Random Posisi Gen & Random PC .............................................. 125 Gambar 4.29 Hasil Proses Crossover Tidak Valid.............................................. 125 Gambar 4.30 Hasil Proses Crossover Valid ........................................................ 126 Gambar 4.31 Daftar Hasil Proses Crossover....................................................... 127 Gambar 4.32 Hasil Proses Pemilih Kromosom Secara Acak ............................. 128 Gambar 4.33 Hasil Proses Pemilihan Dua Gen Secara Acak ............................. 128 Gambar 4.34 Hasil Proses Mutasi Valid ............................................................. 128 Gambar 4.35 Hasil Proses Mutasi Tidak Valid ................................................... 129 Gambar 4.36 Daftar Hasil Proses Mutasi ............................................................ 129 Gambar 4.37 Hasil Proses Validasi Jalur Mutasi ................................................ 130 Gambar 4.38 Daftar Populasi Orang Tua Dan Anak .......................................... 132 Gambar 4.39 Hasil Nilai Fitness Populasi Orang Tua Dan Anak ....................... 132 Gambar 4.40 Daftar Populasi Untuk Generasi Pertama...................................... 133 Gambar 4.41 Hasil Jalur Optimal Menggunakan Algoritma Genetika ............... 133

xiv

DAFTAR LAMPIRAN Lampiran A Daftar Nama Persimpangan (Node) Di Denpasar Utara................. 149 Lampiran B Daftar Nama Edge (Bobot) Di Denpasar Utara .............................. 154

xv