sistem informasi jalur optimal ... - sinta.unud.ac.id awal.pdf · sistem informasi jalur optimal...
TRANSCRIPT
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
ii
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
iii
LEMBAR PENGESAHAN TUGAS AKHIR
iv
Judul : Sistem Informasi Jalur Optimal Transportasi Umum (Taksi)
Berbasis Mobile Menggunakan Metode Algoritma Genetika.
Studi Kasus: Denpasar Utara.
Nama : I Wayan Aditya Setiawan
Nim : 1208605057
Pembimbing I : I Gede Santi Astawa, S.T., M.Cs.
Pembimbing II : 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
v
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
vi
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. 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.
2. 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.
3. 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.
4. Bapak-bapak dan Ibu-ibu dosen di Jurusan Ilmu Komputer yang telah
memberikan masukan, saran, dan nasehat guna kelengkapan Tugas Akhir
ini.
5. 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.
6. Seluruh rekan-rekan mahasiswa di Jurusan Ilmu Komputer yang telah
memberikan motivasi dan doa dalam proses penelitian ini.
7. 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.
8. 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
vii
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
viii
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
ix
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
x
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
xi
Tabel 4.60 Percobaan 10 Pengujian Akurasi Algoritma Genetika ..................... 142
xii
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
xiii
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
xiv
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
xv
DAFTAR LAMPIRAN
Lampiran A Daftar Nama Persimpangan (Node) Di Denpasar Utara................. 149
Lampiran B Daftar Nama Edge (Bobot) Di Denpasar Utara .............................. 154