PENYELESAIAN MASALAH CREW PAIRING MASKAPAI PENERBANGAN DENGAN 0-1 INTEGER PROGRAMMING
ANNE YULIANA UTAMI DEWI
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2014
PERNYATAAN MENGENAI SKRIPSI DAN SUMBER INFORMASI SERTA PELIMPAHAN HAK CIPTA Dengan ini saya menyatakan bahwa skripsi berjudul Penyelesaian Masalah Crew Pairing Maskapai Penerbangan dengan 0-1 Integer Programming adalah benar karya saya dengan arahan dari komisi pembimbing dan belum diajukan dalam bentuk apa pun kepada perguruan tinggi mana pun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di bagian akhir skripsi ini. Dengan ini saya melimpahkan hak cipta dari karya tulis saya kepada Institut Pertanian Bogor. Bogor, Juni 2014 Anne Yuliana Utami Dewi NIM G54090033
ABSTRAK ANNE YULIANA UTAMI DEWI. Penyelesaian Masalah Crew Pairing Maskapai Penerbangan dengan 0-1 Integer Programming. Dibimbing oleh PRAPTO TRI SUPRIYO dan BIB PARUHUM SILALAHI. Crew pairing adalah urutan penerbangan yang berawal dari suatu pangkalan kru dan berakhir di pangkalan kru yang sama yang akan dilayani oleh anggota kru. Penentuan crew pairing merupakan salah satu bagian dari upaya efisiensi biaya operasional pesawat komersil. Tujuannya adalah meminimumkan jumlah crew pairing dan waktu tunggu total di antara dua penerbangan (sit time). Masalah ini dimodelkan sebagai 0-1 Integer Programming. Implementasi pada maskapai Air Asia dengan 25 jadwal penerbangan dalam periode satu hari memberikan 9 crew pairing dengan total sit time 2075 menit. Kata kunci: crew scheduling, crew pairing, kru pesawat, maskapai penerbangan
ABSTRACT ANNE YULIANA UTAMI DEWI. The Solution of Airline Crew Pairing Problem Using 0-1 Integer Programming. Supervised by PRAPTO TRI SUPRIYO and BIB PARUHUM SILALAHI. Crew pairing is a sequence of flights that begins from a crew base and ends at the same crew base that will be served by a member of crew. Determination of crew pairing is one part of the operational cost efficiency efforts on commercial airline. The purpose of this study is to minimize the number of crew pairing and the total waiting time between two flights (i.e., sit time). This problem is formulated as 0-1 Integer Programming. Implementation on the airline of Air Asia with 25 flights schedule within a period of one day provides 9 crew pairing with the total sit time 2075 minutes. Keyword: airline, crew, crew scheduling, crew pairing
PENYELESAIAN MASALAH CREW PAIRING MASKAPAI PENERBANGAN DENGAN 0-1 INTEGER PROGRAMMING
ANNE YULIANA UTAMI DEWI
Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Departemen Matematika
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2014
Judul Skripsi : Penyelesaian Masalah Crew Pairing Maskapai Penerbangan dengan 0-1 Integer Programming Nama : Anne Yuliana Utami Dewi NIM : G54090033
Disetujui oleh
Drs Prapto Tri Supriyo, MKom Pembimbing I
Dr Ir Bib Paruhum Silalahi, MKom Pembimbing II
Diketahui oleh
Dr Toni Bakhtiar, MSc Ketua Departemen
Tanggal Lulus:
PRAKATA Puji dan syukur penulis panjatkan kepada Allah subhanahu wa ta’ala atas segala karunia-Nya sehingga karya ilmiah ini dapat diselesaikan. Judul karya ilmiah yang dikerjakan sejak bulan Februari 2013 ini ialah Penyelesaian Masalah Crew Pairing Maskapai Penerbangan dengan 0-1 Integer Programming. Terima kasih penulis ucapkan kepada Bapak Drs Prapto Tri Supriyo, MKom dan Bapak Dr Ir Bib Paruhum Silalahi, MKom selaku pembimbing serta Bapak Drs Siswandi, MSi sebagai penguji yang telah memberikan saran, bimbingan dan motivasi dalam proses penyelesaian karya ilmiah ini. Ungkapan terima kasih juga saya sampaikan kepada ayah, ibu, seluruh keluarga, serta teman-teman, atas segala dukungan, doa dan kasih sayang yang telah diberikan. Semoga karya ilmiah ini bermanfaat.
Bogor, Juni 2014 Anne Yuliana U.D
DAFTAR ISI DAFTAR TABEL
vi
DAFTAR GAMBAR
vi
DAFTAR LAMPIRAN
vi
PENDAHULUAN
1
Latar Belakang
1
Tujuan Penelitian
1
TINJAUAN PUSTAKA
2
DESKRIPSI DAN FORMULASI MASALAH
3
Deskripsi
3
Formulasi Masalah
4
STUDI KASUS Hasil Studi Kasus SIMPULAN DAN SARAN
7 10 14
Simpulan
14
Saran
14
DAFTAR PUSTAKA
15
LAMPIRAN
16
RIWAYAT HIDUP
31
DAFTAR TABEL 1 Jadwal penerbangan Air Asia dalam periode satu hari 2 Crew pairing hasil Tahap 1 3 Crew pairing hasil Tahap 2
7 11 12
DAFTAR GAMBAR 1 Network yang merepresentasikan model masalah crew pairing 2 Time windows setiap crew pairing
4 13
DAFTAR LAMPIRAN 1 Syntax dan hasil komputasi program LINGO 11.0 untuk masalah penentuan crew pairing pada Tahap 1 2 Syntax dan hasil komputasi program LINGO 11.0 untuk masalah penentuan crew pairing pada Tahap 2
16 22
PENDAHULUAN Latar Belakang Maskapai penerbangan sebagai salah satu industri jasa transportasi udara memiliki permasalahan yang kompleks dipandang dari segi operasional. Permasalahan itu di antaranya adalah permasalahan operasi perawatan, kru, pelayanan dan pelanggan, pesawat, inventory, pengadaan, serta pembelian bahan bakar dan suku cadang (Bazargan 2010). Di antara permasalahan-permasalahan tersebut, biaya pengeluaran untuk penugasan kru (pilot dan awak kabin) merupakan pengeluaran terbesar setelah pengeluaran bahan bakar, sehingga diperlukan perencanaan biaya kru yang lebih efisien. Salah satu yang dapat membuat biaya kru lebih efisien adalah perencanaan penjadwalan kru yang optimal. Penjadwalan kru (crew scheduling) dapat dibagi menjadi dua tahap yaitu tahap penentuan crew pairing dan tahap penugasan kru (crew rostering). Penentuan crew pairing merupakan penentuan aktivitas penerbangan tanpa memperhatikan nama-nama kru (anonim). Daftar jam penerbangan dibuat sebagai input untuk membentuk urutan penerbangan yang disebut crew pairing. Tujuan utama pada tahap ini adalah penggunaan jumlah sumber daya kru yang minimum pada suatu perjalanan dengan semua daftar jam penerbangan dapat terpenuhi. Tahap selanjutnya yaitu penentuan pasangan kru yang ditugaskan pada setiap crew pairing untuk menjalankan berbagai aktivitas seperti tugas dasar, tugas pelayanan, dan lain-lain yang disebut crew rostering. Tujuannya agar mendapatkan penugasan yang layak dengan meminimumkan biaya kru. Kedua masalah tersebut dapat didekatkan dengan dua metode yaitu metode matematis dan artificial intelligent. Pada metode matematis, masalah ini dapat diformulasikan sebagai Integer Programming. Penelitian ini akan fokus pada tahap penentuan kelompok kru (crew pairing) dengan menggunakan 0-1 Integer Programming. Tujuan Penelitian Tujuan penulisan karya ilmiah ini adalah memodelkan masalah crew pairing maskapai penerbangan dengan metode matematis menggunakan 0-1 Integer Programming dan mengimplementasikannya dalam penentuan jumlah crew pairing yang optimal dengan waktu tunggu total di antara dua penerbangan minimum.
2
TINJAUAN PUSTAKA Perencanaan operasional maskapai penerbangan dapat dibagi menjadi empat tahapan dimana hasil dari suatu tahapan akan menjadi input bagi tahapan lain. Tahapan-tahapan tersebut adalah schedule planning, fleet assignment, aircraft routing, dan crew scheduling. Pertama, tahap schedule planning. Tahap ini bersumber pada perkiraan permintaan penumpang (pengguna jasa maskapai penerbangan). Output dari tahap ini menghasilkan flight schedule hari dan frekuensi penerbangan. Tahap 2 adalah fleet assignment. Tahapan ini memasangkan setiap jadwal penerbangan dengan spesifik jenis dari armada yang mempertimbangkan kapasitas armada dan karakteristik penerbangan (domestik dan internasional). Pada Tahap 3 yaitu aircraft routing menguraikan penjadwalan armada yang diatur agar penerbangan dilakukan armada pada kondisi kerja terbaik dan memenuhi regulasi yang ada serta waktu penerbangan memungkinkan untuk memenuhi permintaan pelanggan. Crew scheduling adalah tahapan terakhir dari perencanaan operasional maskapai penerbangan. Pada tahap ini, jadwal penerbangan dan penugasan digunakan untuk menentukan alokasi tugas untuk masing-masing anggota kru sehingga semua penerbangan dilayani dengan memenuhi standar tenaga kerja, operasional, dan regulasi pemerintah. Tahap crew scheduling memiliki dua sub masalah yang saling berhubungan. Kedua masalah tersebut adalah Airline Crew Pairing Problem (ACPP) dan Airline Crew Rostering Problem (ACRP). ACPP menentukan jumlah minimum dari anonim kru yang harus melayani semua penerbangan yang sudah direncanakan dengan mempertimbangkan tenaga kerja, operasional, dan regulasi pemerintah. Hasil dari ACPP diperlukan pada masalah ACRP. Pada ACRP, masing-masing anggota kru ditugaskan pada kru anonim (Barnhart 2003). Pada Airline Crew Pairing Problem, crew pairing yang fisibel adalah dimana kota tujuan dari suatu leg sama dengan kota asal dari leg berikutnya. Selain itu crew pairing harus berawal dan berakhir pada pangkalan kru (crew base) yang sama. Tujuan dari masalah ini adalah untuk mendapatkan crew pairing yang dapat memenuhi semua legs dengan biaya yang minimum (Vargas et al 2009). Crew pairing yang akan dicari harus memperhatikan sejumlah tenaga kerja, operasional dan regulasi yang ada di perusahaan maupun negara di mana maskapai tersebut beroperasi. Pada peraturan maskapai penerbangan dan pemerintah, crew pairing harus memenuhi kondisi sebagai berikut: (1) crew pairing dimulai dan berakhir tugasnya pada pangkalan kru yang sama, (2) tidak ada crew pairing yang melebihi flying time, service time, maksimum landing, dan maksimum duties (Diana et al 2009). Tugas akhir ini membahas tentang Airline Crew Pairing Problem (masalah crew pairing maskapai penerbangan) di mana model bersumber dari paper Miguel A. Vargas dkk yang berjudul “Hybrid Approach to Airline Crew Pairing Optimization for Small Carries” yang akan diselesaikan menggunakan 0-1 Integer Programming.
3
DESKRIPSI DAN FORMULASI MASALAH Deskripsi Crew pairing adalah urutan penerbangan yang berawal dari suatu pangkalan kru (crew base) dan berakhir di pangkalan kru yang sama yang akan dilayani oleh sejumlah kru tanpa memperhatikan nama-nama kru (anonim). Tujuan dari masalah ini adalah untuk menemukan crew pairing yang melayani semua jadwal penerbangan dalam rangkaian perjalanan dengan biaya minimum. Jadwal satu penerbangan yang memuat informasi kota asal, kota tujuan, waktu keberangkatan dan waktu kedatangan disebut leg. Crew pairing terdiri dari leg-leg yang tersusun berurut. Dalam masalah ini tidak diperhatikan perbedaan antar personel kru yang terdiri atas awak kokpit (pilot dan co-pilot) dan awak kabin (flight attendant). Selain itu semua kru dianggap dapat melayani semua tipe/jenis pesawat. Dalam suatu crew pairing didefinisikan beberapa istilah berikut: flying time : lamanya pelayanan oleh kru di udara pada setiap leg briefing time : lamanya persiapan kru di bandara sebelum penerbangan pertama dari crew pairing debriefing time : lamanya kru menetap di bandara setelah penerbangan terakhir dari crew pairing ground time : waktu yang dibutuhkan pesawat untuk mendarat ditambah dengan waktu yang dibutuhkan kru untuk meninggalkan pesawat sit time : lamanya kru menunggu di bandara untuk melakukan penerbangan selanjutnya service time : durasi total kru melakukan tugas yang berhubungan dengan pelayanan penerbangan. Service time terdiri atas flying time, briefing dan debriefing time, ground time serta sit time Crew pairing yang dibuat harus berdasarkan peraturan maskapai penerbangan dan pemerintah tempat maskapai penerbangan tersebut beroperasi. Aturan-aturan tersebut antara lain: 1 total flying time dalam setiap crew pairing tidak melebihi maksimum total flying time 2 service time dalam setiap crew pairing tidak melebihi maksimum service time
4 Sebagai ilustrasi, perhatikan network pada gambar berikut
Gambar 1 Network yang merepresentasikan model masalah crew pairing Pada network ini, simpul (nodes) {2,3,4…n} adalah simpul yang merepresentasikan legs sedangkan simpul {1} merepresentasikan pangkalan kru (crew base) dimana crew pairing dimulai dan berakhir. Panah (arc) merepresentasikan alur atau urutan leg. Contohnya, arc (1,2) menyatakan leg 2 berawal dari pangkalan, arc (2,5) menyatakan leg 5 dilakukan setelah leg 2, dan arc (5,1) menyatakan leg 5 berakhir di pangkalan kru. Contoh satu crew pairing, berawal dari arc (1,2), dilanjutkan arc (2,5) terakhir arc (5,1). Formulasi Masalah Masalah crew pairing dapat diformulasikan sebagai suatu ILP. Sebelum model dikaji secara terperinci, maka perlu ditentukan parameter dan variabel keputusannya. Himpunan N = himpunan dari node = {1,2,…,n} dengan node 1 merepresentasikan pangkalan kru = himpunan node yang merepresentasikan leg penerbangan = N-{1} A = himpunan arcs yang merepresentasikan pasangan leg yang mungkin Indeks = indeks untuk menyatakan leg = indeks untuk menyatakan crew pairing Parameter = maksimum banyaknya crew pairing = maksimum service time = maksimum total flying time = flying time pada leg i = ground time di bandara kota tujuan pada leg i, dengan adalah briefing time = waktu keberangkatan pada leg i
5 = waktu kedatangan pada leg i = debriefing time = sit time antara leg i dan leg j = konstanta positif yang nilainya relatif besar
M
Variabel keputusan
(
l
{
) berada pada c w a n
Tahap 1 Fungsi Objektif Fungsi objektif dari Tahap 1 pada masalah ini adalah meminimumkan jumlah crew pairing untuk memenuhi semua penerbangan. Minimumkan ∑
∑ *
(
)
+
Kendala 1. Setiap penerbangan (leg) hanya dapat dilayani oleh satu crew pairing. ∑
∑ *
(
)
+
2. Crew pairing harus kontinu. Artinya setelah melayani suatu leg pada suatu crew pairing, kru akan melayani leg berikutnya tanpa mengulangi leg yang sama. ∑ *
(
∑ )
+
*
(
)
+
3. Setiap penerbangan yang berawal dari pangkalan dilayani paling banyak sekali dalam setiap crew pairing. ∑ *
(
)
+
4. Crew pairing dimulai dari suatu pangkalan kru dan berakhir di pangkalan kru yang sama. ∑ *
(
∑ )
+
*
(
)
+
6 5. Selisih waktu kedatangan pada leg i dengan waktu mulainya briefing pada setiap crew pairing tidak boleh melebihi maksimum service time. ∑ ( (
)
)
∑ ( (
(
)
)
)
6. Waktu kedatangan ditambah ground time pada leg i lebih kecil dari waktu keberangkatan pada leg j. (
)
7. Total flying time dalam setiap crew pairing lebih kecil dari maksimum total flying time. ∑ (
)
8. Semua variabel keputusan bernilai nol atau satu. *
+, (
)
Tahap 2 Fungsi Objektif Fungsi objektif pada Tahap 2 adalah untuk meminimumkan jumlah waktu kru menunggu di bandara untuk melakukan penerbangan selanjutnya (sit time). Minimumkan ∑ ∑ (
)
Kendala 1. Jumlah crew pairing optimal adalah sebanyak ∑
∑ *
2. Kendala 1-8 pada Tahap 1.
(
)
+
.
7
STUDI KASUS Dalam permasalahan ini misalkan diberikan jadwal penerbangan suatu maskapai penerbangan. Maskapai penerbangan ini ingin meminimumkan jumlah crew pairing agar biaya untuk kru dapat diminimalkan. Perusahaan perlu membuat jadwal kru agar jumlah crew pairing minimum dan waktu tunggu diantara dua leg (sit time) juga minimum dengan memenuhi aturan pembatasan flying time dan service time pada setiap crew pairing. Menurut FAA (The Federal Aviation Administration), maksimum total flying time untuk kru (terutama pilot) melayani setiap penerbangan dalam satu hari adalah 8 jam dan maksimum service time dalam sehari adalah 14 jam. Dengan model 0-1 Integer Programming, akan ditentukan jumlah minimum crew pairing yang akan melayani semua penerbangan tersebut. Asumsi yang digunakan dalam karya ilmiah ini ialah sebagai berikut: 1. Bandara yang menjadi pangkalan kru awal dan pangkalan kru akhir sama. Dalam kasus ini diasumsikan Cengkareng, Jakarta (CGK) sebagai pangkalan kru. 2. Satu periode sama dengan 1 hari. Artinya setiap crew pairing berawal dan berakhir di pangkalan kru dalam hari yang sama. 3. Semua kru dianggap dapat melayani semua jenis pesawat. 4. Semua bandara berada pada wilayah waktu yang sama. 5. Keterlambatan penerbangan pada keberangkatan ataupun kedatangan tidak dipertimbangkan. Data jadwal penerbangan yang diberikan merupakan data maskapai penerbangan Air Asia yang sudah disesuaikan. Data dapat dilihat pada Tabel 1. Tabel 1 Jadwal penerbangan Air Asia dalam periode satu hari No penerbangan 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
QZ 7510 QZ 7526 QZ 7520 QZ 7516 QZ 7558 QZ 7556 QZ 7552 QZ 8063 QZ 7680 QZ 7682 QZ 7511 QZ 7523 QZ 7521 QZ 7515 QZ 7517
Tempat keberangkatankedatangan CGK-DPS CGK-DPS CGK-DPS CGK-DPS CGK-JOG CGK-JOG CGK-JOG CGK-KNO CGK-SUB CGK-SUB DPS-CGK DPS-CGK DPS-CGK DPS-CGK DPS-CGK
Waktu
06:00-07:40 08:45-10:25 09:55-11:35 19:35-21:15 05:20-06:25 05:50-06:55 10:30-11:35 10:40-13:05 07:40-08:55 08:45-10:00 08:20-10.00 11:35-13:15 12:00-13:40 17:20-19:00 21:55-23:35
8 16 17 18 19 20 21 22 23 24 25
QZ 8621 QZ 7557 QZ 7551 QZ 8609 QZ 8098 QZ 7685 QZ 7689 QZ 8620 QZ 7831 QZ 8862
DPS-SUB JOG-CGK JOG-CGK JOG-DPS KNO-CGK SUB-CGK SUB-CGK SUB-DPS SUB-UPG UPG-SUB
13:15-14:05 12:55-14:00 16:05-17:10 10:10-11:20 16:50-19:15 17:10-18:25 20:35-21:50 12:00-12:50 11:55-13:25 14:45-16:15
Berdasarkan permasalahan yang ada, formulasi matematik dari masalah tersebut dapat ditulis sebagai berikut: Himpunan N = himpunan dari node = {1,2,3,…,26} dengan node 1 merepresentasikan pangkalan kru = himpunan node yang merepresentasikan leg penerbangan = {2,3,…,26} A = himpunan arcs yang merepresentasikan pasangan leg yang mungkin Indeks = indeks untuk menyatakan leg = indeks untuk menyatakan crew pairing Parameter = maksimum banyaknya crew pairing = 10 = maksimum service time = 14 jam = maksimum total flying time = 8 jam = flying time pada leg i = ground time di bandara kota tujuan pada leg i = 25 menit, dan adalah briefing time = 25 menit = waktu keberangkatan pada leg i = waktu kedatangan pada leg i = debriefing time = 20 menit = sit time antara leg i dan leg j M = konstanta positif yang nilainya relatif besar Variabel keputusan {
l
(
) berada pada c w a n
Tahap 1 Fungsi Objektif Fungsi objektif dari Tahap 1 pada masalah ini adalah meminimumkan jumlah crew pairing untuk memenuhi semua penerbangan.
9 Minimumkan ∑∑ Kendala 1. Setiap penerbangan (leg) hanya dapat dilayani oleh satu crew pairing. ∑∑
2. Crew pairing harus kontinu. Artinya setelah melayani suatu leg pada suatu crew pairing, kru akan melayani leg berikutnya tanpa mengulangi leg yang sama. ∑
∑
3. Setiap penerbangan yang berawal dari pangkalan dilakukan paling banyak sekali dalam setiap crew pairing. ∑
4. Crew pairing dimulai dari suatu pangkalan dan berakhir di pangkalan yang sama. ∑ *
(
∑ )
+
*
(
)
+
5. Selisih waktu kedatangan pada leg i dengan waktu mulainya briefing pada setiap crew pairing tidak boleh melebihi maksimum service time. ∑ ( (
)
∑ ( (
)
(
)
)
)
.
6. Waktu kedatangan ditambah ground time pada leg i lebih kecil dari waktu keberangkatan pada leg j. ( )
10 7. Total flying time pada setiap crew pairing lebih kecil dari maksimum total flying time. ∑ (
)
8. Semua variabel keputusan bernilai nol atau satu. *
+, (
)
Tahap 2 Fungsi Objektif Fungsi objektif pada Tahap 2 adalah untuk meminimumkan jumlah waktu kru menunggu di bandara untuk melakukan penerbangan selanjutnya (sit time). Minimumkan ∑ ∑ (
)
Kendala 1. Jumlah crew pairing optimal adalah sebanyak
.
∑∑ 2. Kendala 1-8 pada Tahap 1
Hasil Studi Kasus Penyelesaian masalah penentuan crew pairing pada karya ilmiah ini dilakukan dengan bantuan software LINGO 11.0. Syntax program dan hasil komputasi dicantumkan pada Lampiran 1 dan 2. Tahap 1 melakukan proses komputasi selama 13 detik sedangkan tahap 2 selama 32 detik. Tahap 1 memberikan solusi minimum dengan jumlah crew pairing sebanyak 9 dengan rincian diberikan pada Tabel 2. Sebagai contoh, crew pairing 1 melakukan penerbangan dengan urutan leg: 1 - 2 - 12 - 8 - 19 - 1. Crew pairing 1 mengawali tugasnya dengan melayani penerbangan JakartaDenpasar pada pukul 06:00 dan tiba pada pukul 07:40. Tiba di Denpasar, kru melanjutkan tugasnya melayani penerbangan Denpasar-Jakarta dengan waktu keberangkatan pukul 08:20 dan tiba pukul 10:00. Setelah kembali ke pangkalan kru (Jakarta), kru melanjutkan tugasnya dengan melayani penerbangan JakartaYogyakarta, pada pukul 10:30 sampai pukul 11:35. Kru melayani penerbangan terakhir, yaitu penerbangan Yogyakarta-Jakarta dengan waktu keberangkatan pada pukul 16:05, dan berakhir pada pukul 17:10.
11 Tabel 2 Crew pairing hasil tahap 1 Crew pairing 1
Crew pairing 2
Crew pairing 3
Crew pairing 4
Crew pairing 5
Crew pairing 6
Crew pairing 7
Crew pairing 8
Crew pairing 9
Leg No Kota Waktu Leg No Kota Waktu Leg No Kota Waktu Leg No Kota Waktu Leg No Kota Waktu Leg No Kota Waktu Leg No Kota Waktu Leg No Kota Waktu Leg No Kota Waktu
2 QZ 7510 CGK-DPS 06:00-07:40 3 QZ 7526 CGK-DPS 08:45-10:25 4 QZ 7520 CGK-DPS 09:55-11:35 5 QZ 7516 CGK-DPS 19:35-21:15 6 QZ 7558 CGK-JOG 05:20-06:25 7 QZ 7556 CGK-JOG 05:50-06:55 9 QZ 8063 CGK-KNO 10:40-13:05 10 QZ 7680 CGK-SUB 07:40-08:55 11 QZ 7682 CGK-SUB 08:45-10:00
Solusi 12 8 QZ 7511 QZ 7552 DPS-CGK CGK-JOG 08:20-10:00 10:30-11:35 13 QZ 7523 DPS-CGK 11:35-13:15 17 22 QZ 8621 QZ 7685 DPS-SUB SUB-CGK 13:15-14:05 17:10-18:25 16 QZ 7517 DPS-CGK 21:55-23:35 20 14 QZ 8609 QZ 7521 JOG-DPS DPS-CGK 10:10-11:20 12:00-13:40 18 QZ 7557 JOG-CGK 12:55-14:00 21 QZ 8098 KNO-CGK 16:50-19:15 24 15 QZ 8620 QZ 7515 SUB-DPS DPS-CGK 12:00-12:50 17:20-19:00 25 26 QZ 7831 QZ 8862 SUB-UPG UPG-SUB 11:55-13:25 14:45-16:15
19 QZ 7551 JOG-CGK 16:05-17:10
23 QZ 7689 SUB-CGK 20:35-21:50
Pada tahap 2, model ditujukan untuk mendapatkan crew pairing dengan total sit time minimum yaitu 2075 menit dengan rincian crew pairing terdapat pada Tabel 3. Tabel 3 menunjukkan crew pairing yang didapatkan memiliki total sit time sama seperti pada tahap 1 namun crew pairing yang didapatkan berbeda. Crew pairing yang berbeda antara lain crew pairing 3, 5, dan 6. Sebagai contoh, crew pairing 3 pada tahap 2 memenuhi penerbangan dengan urutan leg: 1 - 4 - 14 - 1 sedangkan pada tahap 1, crew pairing 3 memenuhi penerbangan dengan urutan leg: 1 - 4 - 17 - 22 - 1.
12 Tabel 3 Crew pairing hasil tahap 2 Crew pairing 1
Crew pairing 2
Crew pairing 3
Crew pairing 4
Crew pairing 5
Crew pairing 6
Crew pairing 7
Crew pairing 8
Crew pairing 9
Leg No Kota Waktu Leg No Kota Waktu Leg No Kota Waktu Leg No Kota Waktu Leg No Kota Waktu Leg No Kota Waktu Leg No Kota Waktu Leg No Kota Waktu Leg No Kota Waktu
2 QZ 7510 CGK-DPS 06:00-07:40 3 QZ 7526 CGK-DPS 08:45-10:25 4 QZ 7520 CGK-DPS 09:55-11:35 5 QZ 7516 CGK-DPS 19:35-21:15 6 QZ 7558 CGK-JOG 05:20-06:25 7 QZ 7556 CGK-JOG 05:50-06:55 9 QZ 8063 CGK-KNO 10:40-13:05 10 QZ 7680 CGK-SUB 07:40-08:55 11 QZ 7682 CGK-SUB 08:45-10:00
Solusi 12 8 QZ 7511 QZ 7552 DPS-CGK CGK-JOG 08:20-10:00 10:30-11:35 13 QZ 7523 DPS-CGK 11:35-13:15 14 QZ 7521 DPS-CGK 12:00-13:40 16 QZ 7517 DPS-CGK 21:55-23:35 18 QZ 7557 JOG-CGK 12:55-14:00 20 17 QZ 8609 QZ 8621 JOG-DPS DPS-SUB 10:10-11:20 13:15-14:05 21 QZ 8098 KNO-CGK 16:50-19:15 24 15 QZ 8620 QZ 7515 SUB-DPS DPS-CGK 12:00-12:50 17:20-19:00 25 26 QZ 7831 QZ 8862 SUB-UPG UPG-SUB 11:55-13:25 14:45-16:15
19 QZ 7551 JOG-CGK 16:05-17:10
22 QZ 7685 SUB-CGK 17:10-18:25
23 QZ 7689 SUB-CGK 20:35-21:50
Crew pairing yang dihasilkan dari proses komputasi memberikan gambaran waktu pelayanan oleh kru untuk setiap crew pairing. Hal tersebut dapat dilihat pada Gambar 2. Crew pairing 1 pada Gambar 2 menunjukkan kru memulai tugasnya dengan mengikuti briefing di pangkalan kru selama 25 menit. Kru mulai melayani leg 2 selama 100 menit saat pesawat di udara. Setelah mendarat kru perlu waktu untuk meninggalkan pesawat (ground time ) yaitu selama 25 menit. Kemudian setelah menunggu selama 15 menit, kru melayani leg 12 selama 100 menit dan 25 menit untuk meninggalkan pesawat. Kru menunggu selama 5 menit sebelum melayani leg 8. Kru melayani leg 8 selama 65 menit ditambah waktu ground 25 menit. Setelah menunggu selama 245 menit, kru melayani leg terakhir yaitu leg 19 selama 65 menit. Di pangkalan kru, kru mengakhiri tugasnya di hari tersebut dengan mengikuti debriefing selama 20 menit. Dengan demikian, service
13 time crew pairing 1 adalah 715 menit. Gambar 2 juga menunjukkan bahwa service time setiap crew pairing dari hasil komputasi, tidak melebihi maksimum service time yaitu selama 14 jam (840 menit).
Gambar 2 Time windows setiap crew pairing
14
Keterangan: i
: flying time pada leg i : sit time : waktu briefing dan debriefing : waktu ground
SIMPULAN DAN SARAN Simpulan Masalah penentuan crew pairing maskapai penerbangan dapat dimodelkan dengan 0-1 Integer Programming. Masalah ini bertujuan meminimumkan jumlah crew pairing dan meminimumkan waktu tunggu total diantara dua penerbangan (sit time) dengan memenuhi kendala yang ada. Studi kasus pada maskapai penerbangan Air Asia mendapatkan 9 crew pairing yang optimal untuk memenuhi jadwal penerbangan yang ada.
Saran Pada karya tulis ini, asumsi yang digunakan mengenai periode crew pairing adalah selama satu hari. Agar lebih mendekati kenyataan sebaiknya untuk penelitian selanjutnya digunakan periode selama tujuh hari.
15
DAFTAR PUSTAKA Barnhart C, Cohn AM, Johnson EL, Klabjan D, Nemhauser GL, Vance PH. 2003. Airline Crew Scheduling. Di dalam R. Hall, editor. Handbook of Transportation Science. Kluwer Academic Publishers, pp.517-560. Bazargan M. 2010. Airline Operations and Scheduling ed ke-2. Surrey (UK): Ashgate Publishing Limited. Florez DC, Jose LW, Miguel AV, Andres LM, Nubia V. 2009. A Mathematical Programming Approach to Airline Crew Pairing Optimization. Tersedia pada: http://www.agifors.org/award/submissions2009/DianaFlorez_ paper.pdf Vargas MA, Jose LW, Andres LM, Nubia V. 2009. Hybrid Approach to Airline Crew Pairing Optimization for Small Carries. Di dalam: Miguel A, Jose LW, Andres L, Nubia V, editor. IIE Annual Conference Proceedings of the 2009 Industrial Engineering Research Conference [Internet].[Waktu dan tempat pertemuan tidak diketahui]. Norcross (US): Institute of Industrial EngineersPublisher.hlm 1-7; [diunduh 2013 Feb 7]. Tersedia pada: http://search.proquest.com/docview/192459457/fulltextPDF/129F7BA16C4A4 F82PQ/1?accountid=32819
16 Lampiran 1 Syntax dan hasil komputasi program LINGO 11.0 untuk masalah penentuan crew pairing pada Tahap 1 !MODEL CREW PAIRING; model: sets: pairing/1..10/; leg:Tf,Tg,Ta,Td; links1(leg,leg,pairing): X; endsets data: Tsd=840; Tdb=20; Fmax=480; M=1000000; leg,Tf,Ta,Td=@OLE('D:\anne\skripsi\lingo\FIX\DATACP2.xlsx'); enddata !FUNGSI OBJEKTIF; min= @sum(links1(i,j,k)|i#EQ#1:X(i,j,k)); @for(leg(i)|i#NE#1:Tg(i)=25); Tg(1)=25; @for(pairing(k):@for(leg(j)|j#GT#11:X(1,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#12:X(2,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#17:X(2,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#12:X(3,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#17:X(3,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#12:X(4,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#17:X(4,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#12:X(5,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#17:X(5,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#18:X(6,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#20:X(6,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#18:X(7,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#20:X(7,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#18:X(8,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#20:X(8,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#21:X(9,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#21:X(9,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#22:X(10,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#25:X(10,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#22:X(11,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#25:X(11,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#11:X(12,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#11:X(13,j,k)=0));
17 @for(pairing(k):@for(leg(j)|j#GT#11:X(14,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#11:X(15,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#11:X(16,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#22:X(17,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#25:X(17,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#11:X(18,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#11:X(19,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#12:X(20,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#17:X(20,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#11:X(21,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#11:X(22,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#11:X(23,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#12:X(24,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#17:X(24,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#26:X(25,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#22:X(26,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#25:X(26,j,k)=0)); !KENDALA 1 !SETIAP PENERBANGAN (LEG) DAPAT DILAYANI OLEH HANYA SATU CREW PAIRING; @for(leg(i)|i#NE#1:@sum(pairing(k):@sum(leg(j)|j#NE#i:X(i,j,k)))=1); !KENDALA 2; !CREW PAIRING DIMULAI DARI PANGKALAN KRU DILANJUTKAN MELALUI LEG YANG FISIBEL DAN BERAKHIR DI PANGKALAN KRU YANG SAMA; @for(pairing(k):@for(leg(i):@sum(leg(j)|j#NE#i:X(i,j,k))@sum(leg(j)|j#NE#i:X(j,i,k))=0)); !KENDALA 3; !MASING-MASING PENERBANGAN YANG BERAWAL DARI PANGKALAN DILAKUKAN PALING BANYAK SEKALI DALAM SETIAP CREW PAIRING; @for(pairing(k):@sum(leg(j)|j#NE#1:X(1,j,k))<=1); !KENDALA 4; !CREW PAIRING DIMULAI DARI SUATU PANGKALAN DAN BERAKHIR DI PANGKALAN YANG SAMA; @for(pairing(k):@for(leg(i):@sum(leg(j)|j#NE#1:X(1,j,k))@sum(leg(j)|j#NE#1:X(j,1,k))=0)); @for(pairing(k):@for(leg(i):@sum(leg(j)|j#NE#1:X(1,j,k))+@sum(leg(j)|j#NE#1: X(j,1,k))<=2)); !KENDALA 5; !SERVICE TIME PADA SETIAP CREW PAIRING TIDAK BOLEH MELEBIHI MAKSIMUM SERVICE TIME;
18 @for(pairing(k):@for(leg(i)|i#NE#1:Ta(i)+Tdb-Tsd-@sum(leg(n):(Td(n)Tg(1))*X(1,n,k))+M*X(i,1,k)<=M)); @for(pairing(k):@for(leg(i)|i#NE#1:@for(leg(j)|j#NE#i:Ta(i)+Tdb-Tsd@sum(leg(n):(Td(n)-Tg(1))*X(1,n,k))+M*X(i,j,k)<=M))); !KENDALA 6; !WAKTU KEDATANGAN PADA LEG I LEBIH KECIL DARI WAKTU KEBERANGKATAN PADA LEG J; @for(pairing(k):@for(leg(j)|j#NE#1:@for(leg(i)|i#NE#1:Td(i)+Tf(i)+Tg(i)Td(j)+M*X(i,j,k)<=M))); !KENDALA 7; !TOTAL FLYING TIME PADA SETIAP CREW PAIRING LEBIH KECIL DARI MAKSIMUM TOTAL FLYING TIME; @for(pairing(k):@sum(leg(i):@sum(leg(j):Tf(i)*X(i,j,k)))<=Fmax); !KENDALA 8; !SEMUA VARIABEL KEPUTUSAN BERNILAI NOL ATAU SATU; @for(links1(i,j,k):@bin(X(i,j,k)));
Hasil yang diperoleh adalah sebagai berikut: (Tidak semua hasil ditampilkan, hanya untuk variabel yang tidak bernilai nol yang ditampilkan)
Global optimal solution found. Objective value: Objective bound: Infeasibilities: Extended solver steps: Total solver iterations:
9.000000 9.000000 0.000000 0 1776
19
Variable TSD TDB FMAX M TF( 2) TF( 3) TF( 4) TF( 5) TF( 6) TF( 7) TF( 8) TF( 9) TF( 10) TF( 11) TF( 12) TF( 13) TF( 14) TF( 15) TF( 16) TF( 17) TF( 18) TF( 19) TF( 20) TF( 21) TF( 22) TF( 23) TF( 24) TF( 25) TF( 26) TG( 1) TG( 2) TG( 3) TG( 4) TG( 5) TG( 6) TG( 7) TG( 8) TG( 9) TG( 10) TG( 11) TG( 12) TG( 13) TG( 14) TG( 15) TG( 16) TG( 17)
Value 840.0000 20.00000 480.0000 1000000. 100.0000 100.0000 100.0000 100.0000 65.00000 65.00000 65.00000 145.0000 75.00000 75.00000 100.0000 100.0000 100.0000 100.0000 100.0000 50.00000 65.00000 65.00000 70.00000 145.0000 75.00000 75.00000 50.00000 90.00000 90.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000
Reduced Cost 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
20 TG( 18) TG( 19) TG( 20) TG( 21) TG( 22) TG( 23) TG( 24) TG( 25) TG( 26) TA( 2) TA( 3) TA( 4) TA( 5) TA( 6) TA( 7) TA( 8) TA( 9) TA( 10) TA( 11) TA( 12) TA( 13) TA( 14) TA( 15) TA( 16) TA( 17) TA( 18) TA( 19) TA( 20) TA( 21) TA( 22) TA( 23) TA( 24) TA( 25) TA( 26) TD( 2) TD( 3) TD( 4) TD( 5) TD( 6) TD( 7) TD( 8) TD( 9) TD( 10) TD( 11) TD( 12) TD( 13) TD( 14) TD( 15)
25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 460.0000 625.0000 695.0000 1275.000 385.0000 415.0000 695.0000 785.0000 535.0000 600.0000 600.0000 795.0000 820.0000 1140.000 1415.000 845.0000 840.0000 1030.000 680.0000 1155.000 1105.000 1310.000 770.0000 805.0000 975.0000 360.0000 525.0000 595.0000 1175.000 320.0000 350.0000 630.0000 640.0000 460.0000 525.0000 500.0000 695.0000 720.0000 1040.000
0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
21 TD( 16) TD( 17) TD( 18) TD( 19) TD( 20) TD( 21) TD( 22) TD( 23) TD( 24) TD( 25) TD( 26) X( 1, 2, 1) X( 1, 3, 3) X( 1, 4, 7) X( 1, 5, 6) X( 1, 6, 9) X( 1, 7, 8) X( 1, 9, 2) X( 1, 10, 10) X( 1, 11, 4) X( 2, 12, 1) X( 3, 13, 3) X( 4, 17, 7) X( 5, 16, 6) X( 6, 20, 9) X( 7, 18, 8) X( 8, 19, 1) X( 9, 21, 2) X( 10, 24, 10) X( 11, 25, 4) X( 12, 8, 1) X( 13, 1, 3) X( 14, 1, 9) X( 15, 1, 10) X( 16, 1, 6) X( 17, 22, 7) X( 18, 1, 8) X( 19, 1, 1) X( 20, 14, 9) X( 21, 1, 2) X( 22, 1, 7) X( 23, 1, 4) X( 24, 15, 10) X( 25, 26, 4) X( 26, 23, 4) Row 2
1315.000 795.0000 775.0000 965.0000 610.0000 1010.000 1030.000 1235.000 720.0000 715.0000 885.0000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000
0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
Slack or Surplus Dual Price 0.000000 0.000000
22 3 4 5 6 7 8 9 10
0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
Lampiran 2 Syntax dan hasil komputasi program LINGO 11.0 untuk masalah penentuan crew pairing pada Tahap 2 !MODEL CREW PAIRING; model: sets: pairing/1..10/; leg:Tf,Tg,Ta,Td; links1(leg,leg,pairing): X; links2(leg,leg):T; endsets data: Tsd=840; Tdb=20; Fmax=480; M=100000000; leg,Tf,Ta,Td=@OLE('D:\anne\skripsi\lingo\FIX\DATACP2.xlsx'); T= 00000000000000000000000000 0 0 0 0 0 0 0 0 0 0 0 15 210 235 555 830 310 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 45 70 390 665 145 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 320 595 75 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 365 555 200 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 335 525 170 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 55 245 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 200 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 470 675 160 155 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 405 610 95 90 0 0 0 0 0 550 0 0 5 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 355 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 330 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00000000000000000000000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 160 365 0 0 0 0 0 0 0 310 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
23 0 0 0 0 120 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 335 610 70 0 0 0 0 0 0 0 0 0 00000000000000000000000000 0 0 0 0 45 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00000000000000000000000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 245 520 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 55 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 30 235 0 0 0; enddata !FUNGSI OBJEKTIF; min= @sum(pairing(k):@sum(leg(i):@sum(leg(j)|j#NE#i:T(i,j)*X(i,j,k)))); @for(leg(i):Tg(i)=25); Tg(1)=25; @for(pairing(k):@for(leg(j)|j#GT#11:X(1,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#12:X(2,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#17:X(2,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#12:X(3,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#17:X(3,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#12:X(4,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#17:X(4,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#12:X(5,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#17:X(5,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#18:X(6,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#20:X(6,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#18:X(7,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#20:X(7,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#18:X(8,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#20:X(8,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#21:X(9,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#21:X(9,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#22:X(10,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#25:X(10,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#22:X(11,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#25:X(11,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#11:X(12,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#11:X(13,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#11:X(14,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#11:X(15,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#11:X(16,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#22:X(17,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#25:X(17,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#11:X(18,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#11:X(19,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#12:X(20,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#17:X(20,j,k)=0));
24 @for(pairing(k):@for(leg(j)|j#GT#11:X(21,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#11:X(22,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#11:X(23,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#12:X(24,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#17:X(24,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#26:X(25,j,k)=0)); @for(pairing(k):@for(leg(j)|j#LT#22:X(26,j,k)=0)); @for(pairing(k):@for(leg(j)|j#GT#25:X(26,j,k)=0)); !KENDALA 1 !JUMLAH CREW PAIRING OPTIMAL ADALAH SEBANYAK 9; @sum(pairing(k):@sum(leg(j)|j#NE#1:@sum(leg(i)|i#EQ#1:X(i,j,k))))=9; !KENDALA 2 !SETIAP PENERBANGAN (LEG) DAPAT DILAYANI OLEH HANYA SATU CREW PAIRING; @for(leg(i)|i#NE#1:@sum(pairing(k):@sum(leg(j)|j#NE#i:X(i,j,k)))=1); !KENDALA 3; !CREW PAIRING DIMULAI DARI PANGKALAN KRU DILANJUTKAN MELALUI LEG YANG FISIBEL DAN BERAKHIR DI PANGKALAN KRU YANG SAMA; @for(pairing(k):@for(leg(i):@sum(leg(j)|j#NE#i:X(i,j,k))@sum(leg(j)|j#NE#i:X(j,i,k))=0)); !KENDALA 4; !MASING-MASING PENERBANGAN YANG BERAWAL DARI PANGKALAN DILAKUKAN PALING BANYAK SEKALI DALAM SETIAP CREW PAIRING; @for(pairing(k):@sum(leg(j)|j#NE#1:X(1,j,k))<=1); !KENDALA 5; !CREW PAIRING DIMULAI DARI SUATU PANGKALAN DAN BERAKHIR DI PANGKALAN YANG SAMA; @for(pairing(k):@for(leg(i):@sum(leg(j)|j#NE#1:X(1,j,k))@sum(leg(j)|j#NE#1:X(j,1,k))=0)); @for(pairing(k):@for(leg(i):@sum(leg(j)|j#NE#1:X(1,j,k))+@sum(leg(j)|j#NE#1: X(j,1,k))<=2)); !KENDALA 6; !SERVICE TIME PADA SETIAP CREW PAIRING TIDAK BOLEH MELEBIHI MAKSIMUM SERVICE TIME; @for(pairing(k):@for(leg(i)|i#NE#1:Ta(i)+Tdb-Tsd-@sum(leg(n):(Td(n)Tg(1))*X(1,n,k))+M*X(i,1,k)<=M)); @for(pairing(k):@for(leg(i)|i#NE#1:@for(leg(j)|j#NE#i:Ta(i)+Tdb-Tsd@sum(leg(n):(Td(n)-Tg(1))*X(1,n,k))+M*X(i,j,k)<=M))); !KENDALA 7;
25 !WAKTU KEDATANGAN PADA LEG I LEBIH KECIL DARI WAKTU KEBERANGKATAN PADA LEG J; @for(pairing(k):@for(leg(j)|j#NE#1:@for(leg(i)|i#NE#1:Td(i)+Tf(i)+Tg(i)Td(j)+M*X(i,j,k)<=M))); !KENDALA 8; !TOTAL FLYING TIME PADA SETIAP CREW PAIRING LEBIH KECIL DARI MAKSIMUM TOTAL FLYING TIME; @for(pairing(k):@sum(leg(i):@sum(leg(j):Tf(i)*X(i,j,k)))<=Fmax); !KENDALA 9; !SEMUA VARIABEL KEPUTUSAN BERNILAI NOL ATAU SATU; @for(links1(i,j,k):@bin(X(i,j,k)));
Hasil yang diperoleh adalah sebagai berikut: (Tidak semua hasil ditampilkan, hanya untuk variabel yang tidak bernilai nol yang ditampilkan)
Global optimal solution found. Objective value: Objective bound: Infeasibilities: Extended solver steps: Total solver iterations: Variable Value Reduced Cost TSD 840.0000 0.000000 TDB 20.00000 0.000000 FMAX 480.0000 0.000000 M 0.1000000E+09 0.000000
2075.000 2075.000 0.000000 0 1378
26 TF( 2) TF( 3) TF( 4) TF( 5) TF( 6) TF( 7) TF( 8) TF( 9) TF( 10) TF( 11) TF( 12) TF( 13) TF( 14) TF( 15) TF( 16) TF( 17) TF( 18) TF( 19) TF( 20) TF( 21) TF( 22) TF( 23) TF( 24) TF( 25) TF( 26) TG( 1) TG( 2) TG( 3) TG( 4) TG( 5) TG( 6) TG( 7) TG( 8) TG( 9) TG( 10) TG( 11) TG( 12) TG( 13) TG( 14) TG( 15) TG( 16) TG( 17) TG( 18) TG( 19) TG( 20) TG( 21) TG( 22) TG( 23)
100.0000 100.0000 100.0000 100.0000 65.00000 65.00000 65.00000 145.0000 75.00000 75.00000 100.0000 100.0000 100.0000 100.0000 100.0000 50.00000 65.00000 65.00000 70.00000 145.0000 75.00000 75.00000 50.00000 90.00000 90.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000 25.00000
0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
27 TG( 24) TG( 25) TG( 26) TA( 2) TA( 3) TA( 4) TA( 5) TA( 6) TA( 7) TA( 8) TA( 9) TA( 10) TA( 11) TA( 12) TA( 13) TA( 14) TA( 15) TA( 16) TA( 17) TA( 18) TA( 19) TA( 20) TA( 21) TA( 22) TA( 23) TA( 24) TA( 25) TA( 26) TD( 2) TD( 3) TD( 4) TD( 5) TD( 6) TD( 7) TD( 8) TD( 9) TD( 10) TD( 11) TD( 12) TD( 13) TD( 14) TD( 15) TD( 16) TD( 17) TD( 18) TD( 19) TD( 20) TD( 21)
25.00000 25.00000 25.00000 460.0000 625.0000 695.0000 1275.000 385.0000 415.0000 695.0000 785.0000 535.0000 600.0000 600.0000 795.0000 820.0000 1140.000 1415.000 845.0000 840.0000 1030.000 680.0000 1155.000 1105.000 1310.000 770.0000 805.0000 975.0000 360.0000 525.0000 595.0000 1175.000 320.0000 350.0000 630.0000 640.0000 460.0000 525.0000 500.0000 695.0000 720.0000 1040.000 1315.000 795.0000 775.0000 965.0000 610.0000 1010.000
0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
28 TD( 22) TD( 23) TD( 24) TD( 25) TD( 26) X( 1, 2, 3) X( 1, 3, 7) X( 1, 4, 8) X( 1, 5, 2) X( 1, 6, 1) X( 1, 7, 5) X( 1, 9, 9) X( 1, 10, 4) X( 1, 11, 10) X( 2, 12, 3) X( 3, 13, 7) X( 4, 14, 8) X( 5, 16, 2) X( 6, 18, 1) X( 7, 20, 5) X( 8, 19, 3) X( 9, 21, 9) X( 10, 24, 4) X( 11, 25, 10) X( 12, 8, 3) X( 13, 1, 7) X( 14, 1, 8) X( 15, 1, 4) X( 16, 1, 2) X( 17, 22, 5) X( 18, 1, 1) X( 19, 1, 3) X( 20, 17, 5) X( 21, 1, 9) X( 22, 1, 5) X( 23, 1, 10) X( 24, 15, 4) X( 25, 26, 10) X( 26, 23, 10) T( 2, 12) T( 2, 13) T( 2, 14) T( 2, 15) T( 2, 16) T( 2, 17) T( 3, 13) T( 3, 14) T( 3, 15)
1030.000 1235.000 720.0000 715.0000 885.0000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 15.00000 210.0000 235.0000 555.0000 830.0000 310.0000 45.00000 70.00000 390.0000
0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 15.00000 45.00000 0.000000 15.00000 365.0000 170.0000 245.0000 200.0000 160.0000 90.00000 5.000000 0.000000 0.000000 0.000000 0.000000 160.0000 0.000000 0.000000 70.00000 0.000000 0.000000 0.000000 245.0000 55.00000 235.0000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
29 T( 3, 16) T( 3, 17) T( 4, 15) T( 4, 16) T( 4, 17) T( 5, 16) T( 6, 18) T( 6, 19) T( 6, 20) T( 7, 18) T( 7, 19) T( 7, 20) T( 8, 18) T( 8, 19) T( 9, 21) T( 10, 22) T( 10, 23) T( 10, 24) T( 10, 25) T( 11, 22) T( 11, 23) T( 11, 24) T( 11, 25) T( 12, 5) T( 12, 8) T( 12, 9) T( 13, 5) T( 14, 5) T( 15, 5) T( 17, 22) T( 17, 23) T( 18, 5) T( 19, 5) T( 20, 14) T( 20, 15) T( 20, 16) T( 20, 17) T( 22, 5) T( 24, 15) T( 24, 16) T( 25, 26) T( 26, 22) T( 26, 23) Row 2 3 4
665.0000 145.0000 320.0000 595.0000 75.00000 15.00000 365.0000 555.0000 200.0000 335.0000 525.0000 170.0000 55.00000 245.0000 200.0000 470.0000 675.0000 160.0000 155.0000 405.0000 610.0000 95.00000 90.00000 550.0000 5.000000 15.00000 355.0000 330.0000 10.00000 160.0000 365.0000 310.0000 120.0000 15.00000 335.0000 610.0000 70.00000 45.00000 245.0000 520.0000 55.00000 30.00000 235.0000
Slack or Surplus 0.000000 0.000000 0.000000
0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 Dual Price 0.000000 0.000000 0.000000
30 5 6 7 8 9 10
0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
31
RIWAYAT HIDUP Penulis dilahirkan di Bogor pada tangga 17 Juli 1991 sebagai anak pertama dari pasangan Mumu Bahrul Muhit dan Euis Husniah. Penulis lulus SMA di tahun 2009 dan pada tahun yang sama penulis diterima sebagai mahasiswa di Institut Pertanian Bogor (IPB) program studi Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam melalui jalur Undangan Seleksi Masuk IPB (USMI). Selama di Institut Pertanian Bogor, penulis pernah meraih Peringkat III lomba Pengantar Matematika se-IPB yang diadakan Gugus Mahasiswa Matematika IPB (GUMATIKA) pada tahun 2009. Penulis juga menjadi asisten mata kuliah Pemrograman Linear program S1 pada semester genap tahun ajaran 2013 dan asisten mata kuliah Analisis Model Empirik pada semester ganjil tahun ajaran 2013/2014. Selain itu, penulis juga aktif berorganisasi di himpunan mahasiswa Gugus Mahasiswa Matematika (GUMATIKA) IPB sebagai anggota Biro Kewirausahaan di tahun 2011 dan 2012 dan juga aktif di organisasi di luar kampus yaitu Forum Komunikasi Alumni Muslim SMAN 1 Bogor (Forkom Alim’s) sebagai koordinator bidang Human Resource Development pada tahun 2012/2013. Penulis juga aktif sebagai pengajar bimbingan belajar Katalis Corp. pada tahun 2013/2014.
