pencari jalur termurah kendaraan umum ...kc.umn.ac.id/1748/1/halaman awal.pdfgading serpong 201 3...

17
Team project ©2017 Dony Pratidana S. Hum | Bima Agus Setyawan S. IIP Hak cipta dan penggunaan kembali: Lisensi ini mengizinkan setiap orang untuk menggubah, memperbaiki, dan membuat ciptaan turunan bukan untuk kepentingan komersial, selama anda mencantumkan nama penulis dan melisensikan ciptaan turunan dengan syarat yang serupa dengan ciptaan asli. Copyright and reuse: This license lets you remix, tweak, and build upon work non-commercially, as long as you credit the origin creator and license it on your new creations under the identical terms.

Upload: others

Post on 05-Dec-2020

3 views

Category:

Documents


0 download

TRANSCRIPT

Team project ©2017 Dony Pratidana S. Hum | Bima Agus Setyawan S. IIP 

 

 

 

 

 

Hak cipta dan penggunaan kembali:

Lisensi ini mengizinkan setiap orang untuk menggubah, memperbaiki, dan membuat ciptaan turunan bukan untuk kepentingan komersial, selama anda mencantumkan nama penulis dan melisensikan ciptaan turunan dengan syarat yang serupa dengan ciptaan asli.

Copyright and reuse:

This license lets you remix, tweak, and build upon work non-commercially, as long as you credit the origin creator and license it on your new creations under the identical terms.

RANCANG BANGUN APLIKASI

PENCARI JALUR TERMURAH KENDARAAN UMUM

MENGGUNAKAN ALGORITMA DIJKSTRA BERBASIS WEB

SKRIPSI

Diajukan sebagai salah satu syarat

untuk memperoleh gelar Sarjana Komputer (S.Kom.)

Reza Fatahillah

NIM: 07110110030

PROGRAM STUDI TEKNIK INFORMATIKA

FAKULTAS TEKNOLOGI INFORMASI DAN KOMUNIKASI

UNIVERSITAS MULTIMEDIA NUSANTARA

GADING SERPONG

2013

PENGESAHAN SKRIPSI

RANCANG BANGUN APLIKASI

PENCARI JALUR TERMURAH KENDARAAN UMUM

MENGGUNAKAN ALGORITMA DIJKSTRA BERBASIS WEB

Oleh

Nama : Reza Fatahillah

NIM : 07110110030

Falkultas : Teknologi Informasi dan Komunikasi

Program Studi : Teknik Informatika

Tangerang, 21 Oktober 2013

Dosen Pembimbing, Ketua Program Studi,

( Maria Irmina P., S.Kom, M.T ) ( Maria Irmina P., S.Kom, M.T )

Ketua Sidang, Dosen Penyidang 1,

( Adhi Kusnadi, S.T.,M.Si. ) ( Dr. Ir. P. M. Winarno, M.Kom )

Rancang Bangun ..., Reza Fatahillah, FTI UMN, 2014

PERNYATAAN

Dengan ini saya:

Nama : Reza Fatahillah

NIM : 07110110030

Program Studi : Teknik Informatika

Dengan ini saya menyatakan bahwa skripsi ini adalah karya ilmiah saya sendiri,

bukan plagiat dari karya ilmiah yang ditulis oleh orang lain atau lembaga lain dan

semua karya ilmiah orang lain atau lembaga lain yang dirujuk dalam skripsi ini

telah disebutkan sumber kutipannya serta dicantumkan di dalam Daftar Pustaka.

Tangerang, 21 Oktober 2013

Reza Fatahillah

Rancang Bangun ..., Reza Fatahillah, FTI UMN, 2014

DEVELOPMENT OF WEB BASED

PUBLIC TRANSPORTATION CHEAPEST PATH SEARCH

APPLICATION USING DIJKSTRA ALGORITHM

ABSTRACT

This study aims to build applications that can be used all the people,

especially Jakarta people. Functional Application for search the cheapest path

public transportation, by implementing shortest path Dijkstra algorithm.

Applications built using PHP programming language and Codeigniter Framework.

The results of this study have been successfully carried out by determining the

cheapest routes every street of Jakarta. Application is packed with simple, user-

friendly and attractive appearance.

Keywords: Shortest path, Dijkstra, PHP, Codeigniter.

Rancang Bangun ..., Reza Fatahillah, FTI UMN, 2014

RANCANG BANGUN APLIKASI

PENCARI JALUR TERMURAH KENDARAAN UMUM

MENGGUNAKAN ALGORITMA DIJKSTRA BERBASIS WEB

ABSTRAKSI

Penelitian ini bertujuan untuk membangun aplikasi yang dapat digunakan

semua orang terutama masyarakat DKI Jakarta. untuk pencarian jalur termurah

kendaraan umum, dengan mengimplementasikan shortest path algoritma Dijkstra.

Aplikasi dibangun dengan menggunakan bahasa pemprograman PHP

menggunakan framework codeigniter. Hasil penelitian ini telah berhasil dilakukan

dengan menentukan rute-rute termurah setiap jalanan DKI-Jakarta. Aplikasi

dikemas dengan tampilan yang simple, user friendly dan menarik.

Kata Kunci: Shortest path, Dijkstra, PHP, Codeigniter.

Rancang Bangun ..., Reza Fatahillah, FTI UMN, 2014

KATA PENGANTAR

Puji dan syukur kepada Tuhan Yang Maha Esa atas segala berkat dan

rahmat yang diberikan kepada penulis untuk menyelesaikan tugas akhir ini.

Tugas akhir dengan judul “RANCANG BANGUN APLIKASI PENCARI

JALUR TERMURAH KENDARAAN UMUM MENGGUNAKAN

ALGORITMA DIJKSTRA BERBASIS WEB” ini ditunjukan untuk memenuhi

sebagai persyaratan akademik.

Penulis menyadari bahwa tanpa bantuan, doa dan bimbingan dari beberapa

pihak, baik berupa saran, kritik maupun dukungan tugask akhir ini tidak dapat

diselesaikan tepat pada waktunya. Oleh karena itu, pada kesempatan kali ini

penulis ingin menyampaikan ucapan terima kasih yang sebesar-besarnya kepada:

1. Ibu. Maria Irmina Prasetiyowati, S.Kom., M.T. selaku dosen pembimbing

dan Ketua Program Studi Teknik Informatika Universitas Multimedia

Nusantara yang telah memberikan banyak dukungan dan memberikan saran

kepada penulis selama kegiatan skripsi.

2. Bpk. Januar Wahjudi, S.Kom,. M.Sc., yang tidak sengaja telah memberikan

ide judul skripsi.

3. Seluruh dosen yang telah mengajar dan memberikan ilmunya kepada penulis

selama masa perkuliahan di Universitas Multimedia Nusantara.

4. Mama, Papa, Fadly Fadhillah, Faisal Hidayatullah dan keluarga Meruya Ilir

yang telah memberikan dukungan modal, doa dan cintanya kepada penulis

untuk menyelesaikan tugas akhir ini.

Rancang Bangun ..., Reza Fatahillah, FTI UMN, 2014

5. Staff Karyawan Universitas Multimedia Nusatara, terutama Nunik Arfiliani,

Diana Nurmila, dan lain-lain yang tidak dapat di sebutkan satu persatu dalam

membantu penulis dalam kegiatan administrative.

6. Staff Karyawan Perpustakaan, Terutama Reksa Anindya yang banyak

komentar dan memberikan dukungan mental agar penulis menyelesaikan

skripsi secepat mungkin.

7. Alfredo Gemilang, yang telah membantu penulis dalam pembuatan aplikasi.

8. Yuliana Halawa yang telah mendampingi selama ini dan memberikan

dukungan penuh hingga penulis menyelesaikan tugas akhir ini.

9. Muhammad Baresi, Boby Lawijaya yang telah banyak membantu

memperlihatkan contoh-contoh pembuatan tugas akhir yang baik kepada

penulis.

10. Silvester Renaldho, Araz Kahfi, Maulana sani, Yungky Hower, Lewis

Spancer yang membantu memberikan tumpangan, makanan serta internet

gratis untuk mencari bahan berguna bagi penulis.

11. Ke-dua puluh tujuh teman-teman Teknik Informatika angkatan 2007, yang

telah menjadi teman, sahabat, dan keluarga selama ini.

12. Teman-teman seperjuangan 2007 yang masih menempuh skripsi, Albert

Mario, Daniel Adhi, Nathan Sadeli, Maulana Sani.

13. Teman-teman kelapa dua tangerang atau kontrakan barbie house yaitu

charles, Yoseph Raharjo, Beno Sanjaya, Dhira Parama, Samuel Adhi, Daniel

Adhi yang selama ini menjadi keluarga susah senang bersama.

Rancang Bangun ..., Reza Fatahillah, FTI UMN, 2014

14. Teman-teman kontrakan sektor 7 gading serpong yaitu, wistanto wardana,

Ruby Hendrata, Silvester Renadlo, Oka Radity, Ersa Sony, Alfredo Gemilang

dan Denza yang selama ini menjadi keluarga baik dalam suka dan duka.

15. Semua pihak yang tidak bisa disebutkan satu persatu yang langsung maupun

tidak langsung menyelesaikan Tugas Akhir ini.

Akhir Kata, penulis meminta maaf apabila terdapat kesalahan penulisan

maupun banyak kekurangan dalam tugas akhir ini. Oleh karena itu, kritik dan

saran dari pembaca akan sangat bermanfaat bagi penulis. Semoga Tugas

Akhir ini dapat bermanfaat bagi semua pihak yang membacanya.

Tangerang 21 Oktober 2013

Penulis

Reza Fatahillah

Rancang Bangun ..., Reza Fatahillah, FTI UMN, 2014

DAFTAR ISI

PENGESAHAN SKRIPSI ....................................................................................... i

PERNYATAAN ...................................................................................................... ii

ABSTRACT ........................................................................................................... iii

ABSTRAKSI ......................................................................................................... iv

KATA PENGANTAR ............................................................................................ v

DAFTAR ISI ........................................................................................................ viii

DAFTAR GAMBAR ............................................................................................ xii

DAFTAR TABEL ................................................................................................ xiv

DAFTAR RUMUS ............................................................................................... xv

BAB I

PENDAHULUAN .................................................................................................. 1

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

1.2 Rumusan Masalah .................................................................................. 3

1.3 Batasan Masalah ..................................................................................... 3

1.4 Tujuan Penelitian .................................................................................... 4

1.5 Manfaat Penelitian .................................................................................. 4

1.6 Sistematika Penulisan ............................................................................. 4

BAB II

TINJAUAN PUSTAKA ......................................................................................... 6

2.1 DKI Jakarta ................................................................................................... 6

Rancang Bangun ..., Reza Fatahillah, FTI UMN, 2014

2.2 Angkutan Umum .......................................................................................... 7

2.3 Rute .............................................................................................................. 8

2.4 CodeIgniter ................................................................................................... 8

2.5 Graph ............................................................................................................ 9

2.5.1 Jenis Dan Istilah Umum Graph ......................................................... 10

2.6 Algoritma .................................................................................................... 12

2.6.1 Komponen Algoritma ........................................................................ 14

2.7 Algoritma Greedy ....................................................................................... 16

2.8 Algoritma Shortest Path ............................................................................. 17

2.8.1 Dijkstra .............................................................................................. 18

A Penerapan Algoritma Dijkstra Dengan Harga Termurah ................ 22

2.9 Penelitian Sebelumnya ............................................................................... 22

BAB III

METODOLOGI DAN PERANCANGAN SISTEM ............................................ 24

3.1 Metode Penelitian ............................................................................................... 24

3.2 Perancangan Sistem ............................................................................................ 25

3.2.1 Flow Chart Diagram .......................................................................... 25

A Flow Chart Diagram Algoritma Dijkstra ......................................... 25

B Flow Chart Diagram Menu Sistem .................................................. 26

3.2.2 Data Flow Diagram ........................................................................... 27

3.2.3 Perancangan Database ....................................................................... 28

3.3 Perancangan Antarmuka .................................................................................... 30

3.3.1 Design Interface ................................................................................. 30

Rancang Bangun ..., Reza Fatahillah, FTI UMN, 2014

BAB IV

IMPLEMENTASI DAN PENGUJIAN SISTEM ................................................. 32

4.1 Implementasi Sistem .................................................................................. 32

4.1.1 Implementasi Perangkat Keras .......................................................... 32

4.1.2 Implementasi Perangkat Lunak ......................................................... 32

4.2 Implementasi Aplikasi ............................................................................... 33

1 Koneksi Database ................................................................................... 33

2 Eksekusi File ........................................................................................... 33

3 Menu Cari Rute....................................................................................... 34

4 Menu Credit ............................................................................................ 36

5 Menu Login ............................................................................................ 37

6 Menu Admin ........................................................................................... 37

7 Menu Upload Peta .................................................................................. 37

8 Menu Jalan .............................................................................................. 38

9 Menu Rute .............................................................................................. 40

10 Menu Profile .......................................................................................... 42

4.3 Pengujian ................................................................................................... 43

4.3.1 Data Pengujian ................................................................................... 43

4.3.2 Pengujian Yang Dilakukan ................................................................ 46

4.3.3 Evaluasi Hasil Pengujian ................................................................... 47

BAB V

SIMPULAN DAN SARAN .................................................................................. 48

Rancang Bangun ..., Reza Fatahillah, FTI UMN, 2014

5.1 Simpulan ..................................................................................................... 48

5.2 Saran ........................................................................................................... 48

DAFTAR PUSTAKA .......................................................................................... xvi

RIWAYAT HIDUP .............................................................................................. xix

DAFTAR LAMPIRAN ......................................................................................... xx

Rancang Bangun ..., Reza Fatahillah, FTI UMN, 2014

DAFTAR GAMBAR

Gambar 2.1 Rute Pada Graph 11

Gambar 2.2 Contoh Sederhana Algoritma Membuat Mie Instan 13

Gambar 2.3 Pseudocode Sederhana 15

Gambar 2.4 Algoritma Sederhana Greedy 16

Gambar 2.5 Label Pada Dijkstra 19

Gambar 2.6 Penerapan Algoritma Dijkstra 20

Gambar 2.7 Mengetahui Rute Yang Di Lewati Dijkstra 21

Gambar 2.8 Penerapan Rute Termurah Dijkstra Pada Lintasan 22

Gambar 3.1 Flow Chart Dijkstra 25

Gambar 3.2 Flow Chart Aplikasi 26

Gambar 3.3 Contex Diagram atau Level 0 27

Gambar 3.4 Data Flow Diagram Level 1[ Bagian 1 ] 27

Gambar 3.5 Data Flow Diagram Level 1[ Bagian 2 ] 28

Gambar 3.6 Relation Database 30

Gambar 3.7 Design Interface 31

Gambar 4.1 Screenshot Halaman Home Aplikasi Pencari Jalur Termurah 34

Gambar 4.2 Screenshot Halaman Cari Rute 35

Gambar 4.3 Screenshot Halaman Cari Rute – Lihat Rute 35

Gambar 4.4 Screenshot Halaman Cari Rute – Lihat Peta 36

Gambar 4.5 Screenshot Halaman Credit 36

Gambar 4.6 Screenshot Halaman Login 37

Gambar 4.7 Screenshot Halaman Admin Upload Peta 38

Gambar 4.8 Screenshot Halaman Admin Jalan 39

Gambar 4.9 Screenshot Halaman Admin Jalan – Tambah Jalan 39

Gambar 4.10 Screenshot Halaman Admin Jalan – Edit Jalan 40

Gambar 4.11 Screenshot Halaman Admin Rute 41

Gambar 4.12 Screenshot Halaman Admin Rute – Tambah Rute 41

Gambar 4.13 Screenshot Halaman Admin Rute – Edit Rute 42

Rancang Bangun ..., Reza Fatahillah, FTI UMN, 2014

Gambar 4.14 Screenshot Halaman Admin Profile 43

Gambar 4.15 Screenshot Data Harga Perjalanan 44

Gambar 4.16 Lintasan Pengujian 45

Gambar 4.17 Screenshot Pengujian Sebelum GUI 46

Gambar 4.18 Screenshot Pengujian Aplikasi GUI 47

Rancang Bangun ..., Reza Fatahillah, FTI UMN, 2014

DAFTAR TABLE

Tabel 3.1 Admin 29

Tabel 3.2 Jalan 29

Tabel 3.3 Rute 29

Tabel 4.1 Pencarian Jalur Dengan Dijkstra 45

Rancang Bangun ..., Reza Fatahillah, FTI UMN, 2014

DAFTAR RUMUS

Rumus 2.1 Graph 9

Rumus 2.2 Dijkstra 18

Rancang Bangun ..., Reza Fatahillah, FTI UMN, 2014