Airline Shortest Path Software

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 3.1

Metodologi Pengerjaan ...................................................................... 25

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

Gambar 4.5

Langkah penyelesaian algoritma Djikstra ......................................... 35

Gambar 4.6

Tahap Inisiasi Djikstra ...................................................................... 35

Gambar 4.7

Tahap identifikasi simpul sumberalgoritma Djikstra ........................ 35

Gambar 4.8

Langkah ke-2 Djikstra (Pencarian simpul terdekat) .......................... 36

Gambar 4.9

Langkah ke-3 Djikstra (Memilih simpul yang terdekat) ................... 36

Gambar 4.10

Langkah ke-4 Djikstra (Memperbarui C[K] pada simpul terdekat dari simpul terpilih)............................................................................ 36

Gambar 4.11

Langkah ke-5 Djikstra (Memilih simpul K terpilih yang terdekat) ... 37

Gambar 4.12

Langkah ke-6 Djikstra ....................................................................... 37

Gambar 4.13

Langkah ke-7 Djikstra ....................................................................... 37

Gambar 4.14

Langkah ke-8 Djikstra ...................................................................... 37

Gambar 4.15

Langkah ke-9 Djikstra ....................................................................... 37

Gambar 4.16

Langkah ke-10 Djikstra ..................................................................... 38

Gambar 4.17

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

Gambar 4.25

Rangkuman Seleksi Algoritma Shortest Path ................................... 44

Gambar 5.1

Data Context Diagram ASPS ............................................................ 46

Gambar 5.2

Data FlowDiagram ASPS .................................................................. 47

Gambar 5.3

Bagan Flow Chart ASPS ................................................................... 48

Gambar 5.4

Halaman Utama ASPS ...................................................................... 54

Gambar 5.5

Menu Rute Penerbangan ASPS ......................................................... 54

Gambar 5.6

Jadwal Penerbangan .......................................................................... 55

Gambar 5.7

Filter Data Maskapai Penerbangan ................................................... 56

Gambar 5.8

Input/Edit Jadwal Penerbangan ......................................................... 56

Gambar 5.9

Tabel Penyimpanan Data Jadwal Penerbangan ................................. 57

Gambar 5.10

Input/Edit Airport .............................................................................. 57

Gambar 5.11

Tabel Data Airport ............................................................................. 58

Gambar 5.12

Input/Edit Data Maskapai .................................................................. 58

Gambar 5.13

Tabel Data Maskapai ......................................................................... 59

viii

DAFTAR TABEL Tabel 2.1

Tabel Perbandingan Penggunaan Peristilahan dalam Jaringan Kerja ...

11

Tabel 4.1.

Contoh running time algoritma tertentu dengan N=100 .......................

30

Tabel 4.2.

Tabel Perbandingan antar Algoritma ....................................................

31

Tabel 5.1

Pengolahan data awal ..........................................................................

53

Tabel 5.2

Perbandingan ASPS Vs Manual ...........................................................

60

Tabel 5.3

Perbandingan ASPS Vs Home Page Maskapai Penerbangan ..............

62

ix

DAFTAR ISTILAH

- Graph /Graf

= Didefinisikan oleh himpunan verteks dan himpunan sisi (edge).

- Vertex/vertices/

= Komponen graph yang menyatakan entitas-entitas data

nodes/simpul - Sisi/busur/arch/ link/branch/edge - Graph Berarah

= Komponen graph yang menyatakan keterhubungan antara vertek-vertex dalam graph = Graph jika sisi-sisi pada graph, misalnya {x, y} hanya

(directed graph atau

berlaku pada arah-arah tertentu saja, yaitu dari x ke y

digraph)

tapi tidak dari y ke x; verteks x disebut origin dan vertex y disebut terminus dari sisi tersebut

- Graph Tak Berarah

= Graph yang mana pada setiap sisi {x, y} berlaku pada

(undirected graph atau

kedua arah: baik x ke y maupun y ke x. Secara grafis sisi

undigraph)

pada undigraph tidak memiliki mata panah dan secara notasional menggunakan kurung kurawal.

- Adjacency

= Dua verteks x dan y yang berlainan disebut berhubungan langsung (adjacent) jika terdapat sisi {x, y} dalam E.

- Path

= Sederetan verteks yang mana setiap verteks adjacent dengan verteks yang tepat berada disebelahnya

- Siklus

= Suatu path dengan panjang lebih dari satu yang dimulai dan berakhir pada suatu verteks yang sama

- Graph berbobot (weighted graph)

= Graph yang sisi-sisi nya disertai juga dengan suatu (atau beberapa) harga yang menyatakan secara unik kondisi keterhubungan tersebut

- Kapasitas busur

= Jumlah arus terbesar (mungkin tak hingga) yang dapat dibawa dalam suatu busur berarah