Pendekatan Linear Programming untuk Strategi Boarding pada Pesawat Riska Dhenabayu 5104100033
Pendekatan Linear Programming untuk Strategi Boarding pada Pesawat
Riska Dhenabayu 5104100033
Pembimbing I: Bilqis Amaliah, S.Kom, M.Kom Pembimbing II: Ary M. Shiddiqi Shiddiqi,, S. Kom Kom., ., M M..Comp.Sc
PENDAHULUAN
Latar Belakang Masalah Turnaround time besar = maskapai merugi Beberapa penyebab lamanya turnaround time: • Pengisian bahan bakar (rata-rata 10 menit) • Bongkar muat kargo (rata-rata 10-14 menit) • Boarding penumpang (rata-rata 30 menit!!) Boarding > Fueling dan bongkar muat kargo Boarding salah satu penyebab gate delays. Minimalkan boarding!
Rumusan Masalah • Bagaimana memodelkan sistem boarding dengan menggunakan metode linear programming? • Bagaimana menghasilkan model strategi boarding dengan pendekatan linear programming? • Bagaimana menghitung jumlah interferences, rata-rata interferences dan waktu boarding untuk memilih model strategi boarding pesawat terbang yang terbaik diantara model strategi boarding yang dihasilkan?
Batasan Masalah • Pesawat terbang A320 dengan layout:
• Menggunakan pendekatan Linear Programming
Tujuan • Memodelkan permasalahan boarding dengan menggunakan metode linear programming. • Menghasilkan model strategi boarding dengan pendekatan linear programming. • Menghitung jumlah interferences, ratarata interferences dan waktu boarding untuk memilih model strategi boarding pesawat terbang yang terbaik diantara model strategi boarding yang dihasilkan.
DASAR TEORI
Linear Programming • Penyelesaian masalah dengan menggunakan persamaan atau pertidaksamaan linear yang mempunyai banyak penyelesaian, dengan memperhatikan syarat-syarat agar diperoleh hasil yang maksimum/minimum (Handy A.Taha, 1987) • Maks atau Min Z= C1X1+C2X2,+CjXj+...+CnXn
AMPL • A Mathematical Programming Language • Bahasa pemrograman untuk pemodelan algebraik yang memungkinkan pemodelan dan penyelesaian permasalahan optimasi linear dan nonlinear • Inputnya: model AMPL (format .mod), data AMPL (.dat) dan command (.txt)
NEOS Server • NEOS Server adalah sebuah proyek kolaborasi dari komunitas optimasi yang menyediakan berbagai macam layanan solver baik dari akademisi maupun dari peneliti komersil (Dolan, 2002). • Terdiri dari banyak solver. Layanan solver gratis. • Seperti TORA tetapi dapat menangani lebih banyak variabel
Gurobi • Salah satu solver yang disediakan NEOS • Untuk Linear Programming • Alternatif lain dapat menggunakan solver MINTO pada NEOS atau solver-solver berbayar untuk Linear Programming (misal iLog)
Simulasi • Simulasi merupakan suatu teknik meniru operasi-operasi atau prosesproses yang terjadi dalam suatu sistem dengan bantuan perangkat komputer dan dilandasi oleh beberapa asumsi tertentu sehingga sistem tersebut bisa dipelajari secara ilmiah (Law and Kelton, 1991).
Simulasi Cont’d System
Eksperimen dengan model dari sistem
Model fisik
Eksperimen dengan sistem sesungguhnya
Model matematis
Solusi analitis
Simulasi
PERANCANGAN
Gambaran Umum Perancangan • Tahap perancangan diawali dengan menganalisa permasalahan pada proses boarding penumpang pesawat terbang. Kemudian membuat model matematika menggunakan pendekatan Linear Programming. • Model matematika ini nantinya akan dioptimasi untuk mendapatkan model strategi boarding.
Analisis Permasalahan • Untuk mendapatkan strategi boarding yang optimal interferences (hambatan) pada proses boarding penumpang pesawat harus diminimalkan. • Terjadi ketika seorang penumpang yang bergerak menuju tempat duduknya terhalangi oleh penumpang lain • Terdapat dua tipe interferences pada proses boarding yaitu seat interferences dan aisle interferences.
Ilustrasi interferences
Perancangan Model Matematika • Variabel-variabel yang dibutuhkan • Seat Interferences • Aisle Interferences
Variabel-variabel • N = {1,..,n} • baris, M = {1,2,3,4,5,6} • G = {1,..,g} • Model matematika ini menempatkan tiap penumpang di kursi (i,j) ke dalam suatu grup k dimana k Є G. Model mixed integer linear programming ini menggunakan variabel keputusan biner
Seat Interferences • TSW
• TSB
AisleInterferences • AWS
• AWL
• ABG
Parameter Bobot • Mean dari distribusi triangular yaitu 3.6 untuk seat interferences dan 2.4 untuk aisle interferences. • Maka bobot untuk TSW, TSB adalah: p1=p2=3.6 • Dan bobot untuk AWS,AWL dan ABG adalah: • P3=p4=p5=2.4
Perancangan Perangkat Lunak START Data Input (pattern.txt)
Membaca Data Input
Mengubah Model Strategi Boarding Menjadi Array Biner
Menulis Data Output Array Biner Data Output PMPattern (.txt)
Menghitung Interferences Menulis Data Output Jumlah Interferences Data Output Interferences Result (.txt)
END
Perancangan Perangkat Lunak • Input • Parameter • Parameter • Parameter • Parameter • Parameter • Parameter
Alpha FNrRows FNrRows FNrSeats FNrSeats FGroupSize Jumlah grup G
Perancangan Perangkat Lunak Cont’d • Proses ReadDataInput: Pada proses ini data input yang berbentuk file teks .txt dibaca oleh program. • Proses WriteOutput: Pada proses ini mengubah model strategi boarding menjadi array biner kemudian hasilnya disimpan ke file PMPattern.txt. PMPattern.txt ini nantinya akan menjadi file input pada proses simulasi. • Proses WriteResult: Proses ini memanggil dua sub-proses untuk menghitung interferences. Kemudian hasilnya ditampilkan di layar dan disimpan ke file InterferencesResult.txt. Adapun dua subproses penghitung interferences adalah: • CalculateNrSeatInterferences • CalculateNrAisleInterferences
Perancangan Simulasi • Membuat layout model sesuai layout A320 • Membuat model pergerakkan penumpang saat proses boarding • Membuat entitas, locations, variabel-variabel dan array input untuk simulasi
IMPLEMENTASI DAN ANALISIS
Implementasi • Implementasi Model Matematika • Model matematika diubah ke bahasa AMPL
• Implementasi Program • Membuat perangkat lunak • Untuk menghitung Seat Interferences • Untuk menghitung Aisle Interferences
• Implementasi Simulasi • Membuat model simulasi • Untuk menghitung rata-rata Interferences • Untuk menghitung rata-rata boarding time
Model Strategi Boarding yang Dihasilkan, untuk Grup=4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
A 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 α=0
B 1 1 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
C 1 1 1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
D 1 1 1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
E 1 1 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
F 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
A B 0 1 0 1 0 1 4 4 4 4 4 4 4 4 4 4 3 4 3 4 3 4 3 3 3 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 α=0.1
C 1 1 1 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 3 2 2 2
D 1 1 1 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 3 2 2 2
E 1 1 1 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2
F 0 0 0 4 4 4 4 4 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2
A B 0 1 0 1 0 1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3 4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 α=0.3
C 1 1 1 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2
D 1 1 1 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2
E 1 1 1 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2
F 0 0 0 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2
0 1 0 1 0 1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3 4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 α=0.7
1 1 1 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2
1 1 1 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2
1 1 1 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2
0 0 0 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2
0 1 0 1 0 1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3 4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 α=0.9
1 1 1 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2
1 1 1 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2
1 1 1 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2
0 0 0 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2
0 0 0 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 α=1
1 1 1 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2
1 1 1 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2
1 1 1 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2
0 0 0 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2
1 1 1 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2
A B 0 1 0 1 0 1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3 4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 α=0.5
C 1 1 1 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2
D 1 1 1 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2
E 1 1 1 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2
F 0 0 0 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2
Model Strategi Boarding yang Dihasilkan, untuk Grup=5
Model Strategi Boarding yang Dihasilkan, untuk Grup=6
KESIMPULAN DAN SARAN
Kesimpulan • Untuk mendapatkan model strategi boarding alternatif, yang pada tugas akhir ini disebut sebagai LP Solution, proses boarding penumpang pesawat terbang dimodelkan dengan metode linear programming yang akan menghasilkan model matematika. Model matematika ini digunakan sebagai fungsi objektif dan fungsi batasan fungsional pada saat optimasi.
Kesimpulan Cont’d 1 • Dari model-model strategi boarding LP Solution yang dihasilkan pada tugas akhir ini yang terbaik adalah model strategi boarding ketika jumlah grup=6 dan nilai alpha=0. • Konsisten menghasilkan total interferences dan waktu boarding relatif kecil pada saat nilai alpha sama dengan 0 dan 0.1.
Kesimpulan Cont’d 2 • Dapat mengurangi waktu boarding sebesar 20% sampai 23%. • Lebih baik dari model strategi boarding Reverse Pyramid namun belum sebaik Efficient Solution.
Saran • Pengintegrasian proses-proses yang dilakukan untuk mendapatkan model strategi boarding dan menguji model strategi boarding. • Mengoptimalkan pembagian jumlah penumpang per grup. • Menguji cobakan model strategi boarding pada sistem sesungguhnya. • Memodelkan strategi boarding dengan menggunakan jenis pesawat lainnya.
TERIMA KASIH
