1 Analisis Algoritma Pemilihan Lintasan Terpendek pada Penerbangan Domestik untuk Perancangan Airline Shortest Path Software Tugas Akhir Diajukan untu...
Analisis Algoritma Pemilihan “Lintasan Terpendek” pada Penerbangan Domestik untuk Perancangan
Airline Shortest Path Software Tugas Akhir Diajukan untuk Memenuhi Syarat Kelulusan Sarjana Strata 1
Oleh : Setyaka 13601012 Pembimbing : Ir. Mahardi Sadono, MT
PROGRAM STUDI TEKNIK PENERBANGAN FAKULTAS TEKNOLOGI INDUSTRI INSTITUT TEKNOLOGI BANDUNG 2007
ABSTRAKSI Laporan kecil ini menyajikan penelitian sederhana tentang penyelesaian permasalahan transportasi
udara
komersial
berjadwal
di
Indonesia
yang
menyangkut
ketakterhubungkannya kota satu dengan yang lainnya melalui suatu penerbangan langsung. Solusi permasalahan tersebut tentu saja dengan menggunakan penerbangan tidak langsung dengan melalui kota transit/antara yang menjembatani penerbangan dari kota asal menuju kota tujuan yang dikehendaki. Tidak hanya sampai disitu, penelitian ini mencoba membantu menciptakan solusi pencarian rute alternatif yang memanfaatkan kota transit dengan menambahkan pilihan yang didukung dengan pertimbangan pencarian rute dengan waktu tempuh yang tercepat atau rute penerbangan dengan biaya penerbangan yang termurah.
Rute penerbangan dengan waktu tempuh yang minimum atau biaya yang termurah dapat dikaji dengan memanfaatkan strategi pencarian dengan teori jaringan (network/graf) khususnya permasalahan shortest path (lintasan terpendek). Permasalahan shortest path sebenarnya mempunyai banyak pilihan solusi yang bisa digunakan, namun karena keterbatasan waktu, lingkup penelitian lebih difokuskan pada pemilihan algoritma shortest path yang menggunakan konsep penyelesaian Greedy. Algoritma Greedy yang paling populer terdiri dari Algoritma Djikstra, Bellman-Ford, dan Floyd-Warshall. Karena masing-masing memiliki kelebihan dan kekurangan, maka melalui pengkajian teori dan implementasi dipilih satu algoritma yang paling sesuai dengan permasalahan yang dihadapi.
Algoritma yang terpilih kemudian coba disajikan untuk contoh aplikasi sederhana yang dapat membantu pencarian rute penerbangan dengan pilihan waktu tercepat atau termurah dengan lebih praktis. Aplikasi ini selanjutnya kami namai dengan ASPS (Airline Shortest Path Software). Aplikasi ini memungkinkan para penumpang untuk mendapatkan informasi pendukung pemilihan rute penerbangan tidak langsung dengan lebih mudah. Karena baru pada tahap penelitian, ASPS dibuat dengan sederhana menggunakan pemrograman DELPHI dan absolute database.
KATA PENGANTAR
Segala puji dan syukur penulis persembahkan untuk Alloh SWT. atas limpahan kemurahan dan kebaikan yang bersumber dari perbendaharaan KemahakasihNya sehingga tugas akhir “ Analisis Algoritma ‘Lintasan Terpendek’ pada Penerbangan Domestik untuk Perancangan Airline Shortest Path Software” ini dapat terselesaikan. Dipenghujung fase, setelah tertatih-tatih penulis menyelesaikannya harus diakui bahwasanya ini semua dapat terjadi memang semata-mata atas kemudahan dan kebaikan Nya semata. Semoga dapat menjadi bekal pengalaman yang mengundang syukur yang kekal hingga dikemudian hari. Amin
Tidak terlupakan terima kasih juga penulis haturkan kepada setiap orang yang ikut berperan serta membantu proses pengerjaan penelitian ini. Rasa terima kasih
dan
penghormatan ini penulis persembahkan kepada : •
Ayah dan Bunda tercinta yang telah lama menanti sambil terus mencurahkan untaian doa dan restu.
•
Bapak Ir. Mahardi Sadono, MT. yang berkenan membimbing dengan penuh kesabaran dalam segala keterbatasan dan kekurangan penulis.
•
Brohan dan Brogempo atas segala bantuannya.
•
Dan Bapak Dr. Ir. Edy Suwondo beserta Bapak Ir. Khairul Ummah, MT. atas kesediaannya menguji penulis.
Karena keterbatasan penulis, mungkin tulisan ini masih sangat jauh dari kelayakan, namun semoga justru kekurangan itu mampu menjadi inspirasi bagi kawan-kawan yang tertarik untuk melanjutkan/mengembangkan penelitian ini ke tahap yang lebih baik lagi. Besar harapan penulis, agar kiranya tulisan ini , meskipun penuh kekurangan dan ketaksempurnaan dapat memberi manfaat bagi sebanyak-banyaknya orang khususnya bagi insan penerbangan di negeri ini.
Bandung, September 2007
Penulis
ii
DAFTAR ISI
ABSTRAK ……………...…………………………………………………………
i
KATA PENGANTAR ………………..…………………………………………..
ii
DAFTAR ISI ………………………………………………...………………..….. iii DAFTAR LAMPIRAN ……………..…………………………………………..... vi DAFTAR GAMBAR ……………………..………………………………….…… vii DAFTAR TABEL ……………………………..…………………………………. ix
BAB I PENDAHULUAN …………………………………………………………………. 1 1.1 Latar Belakang ………………..…………………………………………..... 1 1.2 Tujuan Penelitian ……………………………………………………........... 4 1.3 Rumusan Masalah ……………………………………………………...…... 4 1.4 Batasan Masalah ……………………………………………………….…… 5 1.5 Sistematika Penyusunan Laporan …………………………………………... 5
BAB II STUDI LITERATUR ……………………………………….…………………..... 7 2.1 Sumber Informasi Jadwal Penerbangan Komersial ………………………… 7 2.2 Kebutuhan Sumber Informasi Bagi Calon Penumpang ……………………. 8 2.3 Pemanfaatan Metoda Jaringan Kerja ………………………………………. 11 2.4 Metoda Pemilihan Lintasan Terpendek ……………………………………. 14 2.4.1 Definisi Lintasan Terpendek ………………………………………. 14 2.4.2 Macam-macam Tipe Lintasan Terpendek ………….…………….. 14 2.4.3 Strategi Greedy untuk Pemecahan Masalah Lintasan Terpendek …. 14 2.4.3.1 Definisi Strategi Greedy …………………………………. 15 2.4.3.2 Skema Umum Strategi Greedy …………………………… 16 2.4.4 Algoritma Penyelesaian Masalah Lintasan Terpendek ……………... 16
BAB III METODOLOGI PENELETIAN ……………………………………..………… 23
iii
3.1 Rumusan Masalah ……………..…………………………………………... 24 3.2 Batasan Masalah …………………………………………………………... 25 3.3 Metodologi Pengerjaan ……... ……………………………………………. 25
BAB IV ANALISIS PEMILIHAN ALGORITMA LINTASAN TERPENDEK DAN PENYELESAIAN KASUS RUTE PENERBANGAN DOMESTIK …… 28 4.1 Langkah Pemilihan dan Penerapan Algoritma ………………………….... 28 4.2 Penentuan Parameter Perbandingan Pemilihan Algoritma ………………... 29 4.3 Pemilihan Algoritma Lintasan Terpendek …………………………………. 30 4.4 Analisis Perbandingan Algoritma Penyelesaian Masalah Lintasan Terpendek pada Kasus Jaringan Penerbangan Domestik ………………….. 32 4.4.1 Algoritma Djikstra .......................................................................... 32 4.4.1.1 Intuisi dasar dalam Algoritma Djikstra ......................... 32 4.4.1.2 Konsep Langkah Penyelesaian Djikstra ....................... 33 4.4.1.3 Studi Implementasi Algoritma Djikstra ........................ 38 4.4.2 Algoritma Floyd-Warshall .............................................................. 39 4.4.2.1 Intuisi dasar dalam Algoritma Floyd-Warshall.............. 39 4.4.2.2 Konsep Langkah Penyelesaian dan Implementasi Floyd-Warshall ............................................................. 41 4.5 Hasil Akhir Pemilihan Algoritma Terpendek ……………………………… 44
BAB V IMPPLEMENTASI ALGORITMA LINTASAN TERPENDEK PADA PERANCANGAN AIRLINE SHORTEST PATH SOFTWARE (ASPS) ……… 45 5.1 Gambaran Umum Airline Shortest Path Software ……………………….... 45 5.2 Perancangan Airline Shortest Path Software …………………….………... 45 5.2.1 Data Context Diagram ………………………............................... 45 5.2.2 Data Flow Diagram ……………………………………………... 46 5.2.3 Diagram Alir Airline Shortest Path Software …………………… 46 5.2.4 Perancangan Database Airline Shortest Path Software ………… 49 5.2.4.1 Jenis Data ……………………………………………. 49 5.2.4.2 Penyimpanan/Storage Data ………………………….. 50 5.2.4.3 Metode Pengumpulan Data …………………………... 50 iv
5.2.4.4 Luas Cakupan Data …………………………………... 50 5.2.4.4.1 Jumlah Simpul dalam Graf …………….. 50 5.2.4.4.2 Jumlah Maskapai Penerbangan ………... 51 5.2.4.5 Metode Pengolahan Data …………………………….. 52 5.2.4.6 Parameter Keterhubungan ……………………………. 52 5.2.5 Penyusunan Antarmuka Airline Shortest Path Software ………… 54 5.2.5.1 Halaman Utama ……………………………………… 54 5.2.5.2 Pencarian Lintasan Terpendek ..................................... 54 5.2.5.3 Menu Informasi Jadwal Penerbangan Dasar ................ 55 5.2.5.4 Menu Informasi Terfilter …………………………….. 55 5.2.5.5 Input Data, Edit Data dan Direktori Penyimpanan …... 56 5.3 Analisis Hasil Perancangan Airline Shortest Path Software ……………….. 59 5.3.1 Analisis Perbandingan Hasil Pencarian Lintasan Terpendek dengan Menggunakan Airline Shortest Path Software ASPS dengan Cara Manual .…………………………………………….. 59 5.3.2 Analisis Perbandingan Hasil Pencarian Lintasan Terpendek dengan Menggunakan Airline Shortest Path Software ASPS dengan Cara Pencarian Manual Melalui Home Page Maskapai Tertentu ………………………………………………………….. 61 5.3.3 Pengujian Validasi Hasil ASPS ………………………………….. 61
BAB V KESIMPULAN DAN SARAN …………………………………………………… 65 6.1 Kesimpulan ……………..………………………………………….............. 65 6.2 Saran ……………………………………………………………………….. 65
DAFTAR PUSTAKA ……………………………………………………………... 66 LAMPIRAN ………………………………………………………………………. 67
v
DAFTAR LAMPIRAN Lampiran 1
DAFTAR BANDARA DAN KOTA TUJUAN PENERBANGAN
Lampiran 2
DAFTAR MASKAPAI PENERBANGAN
Lampiran 3
DAFTAR JADWAL PENERBANGAN
Lampiran 4
MANUAL BOOK AIRLINE SORTEST PATH SOFTWARE
vi
DAFTAR GAMBAR Gambar 1.1
Grafik Pengaruh Pertumbuhan Ekonomi Terhadap Demand Angkutan Udara di Indonesia............................................................. 1
Gambar 2.1
Home Page Garuda Indonesia ...........................................................
7
Gambar 2.2
Fitur Layanan Website Garuda Indonesia .........................................
8
Gambar 2.3
Peta Daftar Kota Tujuan Penerbangan Garuda Indonesia ................. 9
Gambar 2.4
Contoh suatu jaringan kerja ............................................................... 11
Gambar 4.1 (a) Diagram”Algorithm Engineering Cycle” .......................................... 28 Gambar 4.1 (b) Tahap Peneitian pada Bab IV ............................................................ 28 Gambar 4.2
Intuisi dasar algoritma Djiksra .......................................................... 33
Gambar 4.3
Intuisi dasar algoritma Djiksra .......................................................... 33
Gambar 4.4
Contoh Jaringan Sederhana ............................................................... 33
Contoh implementasi algoritma Djikstra dari kasus subpart gambar 2.3 ......................................................................................... 38
Gambar 4.18
Intuisi dasar Floyd-Warshall ............................................................. 40
Gambar 4.19
Graf untuk implementasi langkah inisiasi Floyd-Warshall ............... 41
Gambar 4.20
Eliminasi tahap 1 .............................................................................. 42
Gambar 4.21
Eliminasi tahap ke-2 ......................................................................... 42
vii
Gambar 4.22
Eliminasi tahap ke-3 .......................................................................... 43
Gambar 4.23
Eliminasi tahap ke-4 .......................................................................... 43
Gambar 4.24
Solusi final pencarian rute terdekat dari BTH – DPS ........................ 43
