PENGEMBANGAN MODEL AIRLINE ROSTERING SYSTEM MENGGUNAKAN METODE DIFFERENTIAL EVOLUTION

Prosiding Seminar Nasional Manajemen Teknologi XI Program Studi MMT-ITS, Surabaya 6 Pebruari 2010

PENGEMBANGAN MODEL AIRLINE ROSTERING SYSTEM MENGGUNAKAN METODE DIFFERENTIAL EVOLUTION Andiek Sunarto1), Budi Santosa2), dan Arief Rahman3) Jurusan Teknik Industri, Institut Teknologi Sepuluh November (ITS) Surabaya Kampus ITS Sukolilo Surabaya 60111 Email : [email protected], [email protected], dan [email protected]

1,2,3)

ABSTRAK Airline crew rostering merupakan masalah penugasan anggota kru pesawat kepada sejumlah rotasi/pairing yang telah direncanakan untuk bulan tertentu. Maskapai penerbangan mempunyai tugas untuk menyusun jadwal individual bulanan (roster) bagi setiap anggota kru. Problem ini semakin kompleks dan rumit seiring dengan berkembangnya aspirasi/kriteria untuk menentukan kualitas roster yang baik dan meningkatnya fungsi kendala yang timbul dari aturan perusahaan maupun kebijakan pemerintah yang bertujuan untuk meningkatkan kenyamanan penumpang dan keamanan penerbangan. Paper ini mengusulkan metode differential evolution (DE) untuk memecahkan problem airline crew rostering. DE terdiri atas empat langkah utama yaitu, penentuan solusi awal, mutasi, crossover, dan seleksi. Ketepatan dalam menentuan parameter probabilitas mutasi dan crossover merupakan kunci sukses dari algoritma DE. Berbeda dengan penerapan DE pada umumnya, paper ini memperkenalkan random swap sebagai operator mutasi. Algoritma DE telah terbukti mampu menemukan solusi mendekati optimal dengan tingkat konvergensi yang cepat untuk problem optimasi. Melalui eksperimen numerik yang dilakukan dengan sejumlah dataset dari PT. Merpati Nusantara Airline, DE menunjukkan hasil yang lebih kompetitif dibandingkan dengan 2 metode lain, column generation dan MOSI. DE sangat baik untuk ukuran dataset kecil/sedang dan masih menunjukkan hasil yang baik untuk ukuran dataset yang besar. Kata kunci : Airline Rostering, Differential Evolution, Random Swap, Rotasi/pairing, Optimisasi

PENDAHULUAN Dalam banyak industri, staff scheduling dan rostering adalah masalah atau tugas yang esensial, komplek dan merupakan multistage planning. Manusia dalah faktor paling kritis yang harus dikelola dan dimanfaatkan dengan baik dalam bisnis. Karena itu perencanaan yang benar dan cukup bijaksana dapat menyebabkan peningkatan produktivitas secara signifikan. Dalam industri airline, yang menjadi prioritas dari departemen human resource adalah pengembangan crew rostering plan (rencana jadwal penerbangan kru) yang mampu menghasilkan utilitas yang tinggi, yang dimaksud crew pesawat disini adalah awak kokpit (pilot dan co-pilot) dan awak kabin (pramugari). Dalam Anbil et al., diestimasikan bahwa optimization software yang sudah dikembangkan untuk airline bisa menghemat lebih dari US $ 20 million pertahun. Penghematan 1% dalam crew utilization bisa menghemat biaya yang cukup besar. Pada umumnya penyelesaian airline crew scheduling dilakukan dengan pendekatan dekomposisi (Chu, S.C.K, 2007; Lučić, P dan Teodorović, D, 1999) dengan cara membagi permasalahan menjadi dua bagian yaitu crew pairing untuk membentuk


initial feasible solution berupa rangkaian penerbangan yang berawal dan berakhir pada home base yang sama, dilanjutkan dengan crew rostering yaitu menugaskan pairing yang tersusun kepada crew yang ada berdasarkan kalender pribadinya. Pendekatan dekomposisi sangat efektif untuk menyelesaikan permasalahan dengan kompleksitas dan tingkat kesulitan yang tinggi. Banyak metode optimasi telah dikembangkan untuk menyelesaikan crew scheduling dengan tujuan untuk meningkatkan kualitas roster yang tersusun maupun memperbaiki computational time, misalkan simulated annealing (Lučić, P., dan Teodorić, D., 1999), genetic algorithm (Souai, N. and Thegem, J., 2009), tree search algorithm (Beasley, J.E. and Cao, B., 1996), hybrid genetic algorithm (Levine, D., 1996), dan GASA hybrid algorithm (Yinghui, Z., Yunbao, R., and Mingtian, Z., 2007). Riset ini akan memperkenalkan satu metode optimasi lagi untuk menyelesaikan airline crew rostering yaitu differential evolution. Metode ini merupakan evolusi dari genetic algorithm dengan mengganti operator string dan bit dengan floating points dan mengganti operator logika dengan operator matematis. Penggantian operator ini membuat metode differential evolution menjadi jauh lebih sederhana dan lebih mudah dalam pemakaian dibandingkan dengan genetic algorithm, dan diharapkan akan memperbaiki computational time dari genetic algorithm. Riset ini mengsumsikan bahwa pairing telah disediakan oleh maskapai penerbangan dan kru yang akan dijadwalkan rosternya adalah yang ber-home base di Surabaya. Ruang lingkup penleitian ini meliputi : (i) Penyusunan model mempertimbangkan single home base dan tipe armada campuran berdasarkan jenis dan ukuran pesawat. (ii) Roster yang disusun memuat roster crew cockpit (pilot dan copilot) dan cabin (pramugari) yang ber-home base di Surabaya. (iii) Pilot dan co-pilot memiliki kualifikasi menerbangkan pesawat tipe tertentu, sehingga tidak dijinkan menerbangkan pesawat dengan tipe lain, akan tetapi pramugari/awak kabin dapat terbang di setiap jenis pesawat. (iv) senioritas dan gaji per jam setiap anggota kru tidak dipertimbangkan dalam pembuatan roster. Dengan asumsi bahwa gaji per jam terbang dan senioritas sama maka biaya roster dapat diwakili dengan jam terbang aktual. METODOLOGI Pengembangan model matematis airline rostering system Model matematis yang disusun akan memuat aspirasi/kriteria-kriteria sebagai fungsi tujuan dan beberapa fungsi kendala. Fungsi tujuannya adalah multiobjective function yang terdiri atas jam terbang minimum, deviasi hari terbang, dan open time. Beberapa kendala yang harus dipertimbangkan dalam menyusun roster bulanan adalah tidak boleh overlap, kebutuhan pilot minimum setiap pairing, hari libur sebelum 7 hari penerbangan berturut-turut, jam terbang maksimum, hari terbang maksimum, dan jumlah takeoff maksimum. Pengumpulan data dan informasi Dataset dari PT. MNA digunakan untuk memvalidasi model dan beberapa informasi tambahan digunakan untuk meng-update model yang telah dibuat sehingga mencerminkan kondisi riil di PT. MNA. Dataset terdiri atas dataset ukuran kecil dan besar. Model yang dibuat akan dapat dilihat performansinya untuk setiap ukuran data set. Data yang terkumpul kemudian digunakan sebagai bahan untuk membuat parameter-parameter model yang akan digunakan pada ekseku program nantinya.

ISBN : 978-979-99735-9-7 A-8-2


Mengubah constrained model menjadi unconstrained model Seperti metode meta-heuristk lainya DE juga bekerja dengan model tanpa kendala, sehingga model matematis terkendala yang telah dibuat harus diubah menjadi persamaan tanpa kendala. Teknik yang digunakan untuk mentransformasikan constrained problem menjadi unconstrained problem adalah eksternal penalty function. Teknik ini akan memberikan penalty yang sangat besar ketika kendala dilanggar dan berusaha agar fungsi penalty menjadi 0. Pengembangan model DE Model DE dibuat sebagai algoritma untuk menyelesaikan problem rostering dalam penelitian ini. Tidak sama dengan aplikasi DE pada umumnya dalam penelitian ini diperkenalkan teknik random swap pada proses mutasi. DE bergerak dari solusi awal random sebanyak populasi tertentu dengan performansi kurang baik yang dirubah melalui proses mutasi dan crossover. Setiap iterasinya akan dipilih solusi terbaik sebagai induk dengan proses seleksi untuk membangkitkan solusi anak pada iterasi berikutnya. Pemrograman komputer Software yang digunakan untuk pemrograman komputer adalah matlab versi 6.5. pemrograman komputer perlu dilakukan karena problem restering adalah problem yang besar yang dalam penyelesaiannya membutuhkan ratusan sampai ribuan iterasi dan tidak mungkin dilakukan secara manual. Pemrograman dilakukan secara bertahap dengan memasukkan kendala satu-persatu ke dalam program dan me-running setiap kali untuk mengetahui bahwa program telah dibuat dengan benar. Setelah kendala dimasukkan semua baru fungsi tujuannya dimasukkan ke dalam program. Eksperimen dan analisa hasil Pada tahap ini akan ditampilkan hasil eksperimen dan dijelaskan kelebihan metode DE untuk airline rostering system dibandingkan dengan dua metode yang lainnya yaitu column generation dan MOSI. HASIL PENELITIAN DAN DISKUSI A. Percobaan Eksperimen dilakukan dengan dataset yang disediakan oleh PT. MNA. Dataset berupa pairing dan anggota kru untuk setiap jenis armada seperti ditunjukkan Tabel 1. Tabel 1 Karekteristik Data Percobaan

Nilai probabilitas mutasi terbaik, cm = 0.1 dan probabilitas crossover, cr = 0.5. Penalty kendala overlap dan rotasi tanpa free day diambil 1015, penalty kendala kebutuhan pilot 1013, penalty day off sebesar 1011, sedangkan kendala hari terbang, jam

ISBN : 978-979-99735-9-7 A-8-3


terbang, dan jumlah take off mendapat penalty 106. Bobot fungsi obyektif dipilih 104 untuk jam terbang minimum, 100 utuk deviasi hari terbang dan 1 untuk open time. Dataset dibagi dalam dua kelompok berdasarkan ukurannya yaitu dataset kecil dan besar. Dataset kecil terdiri atas penugasan pilot F-100, CN-235, DHC-6, dan Cassa 212. Sedangkan dataset besar terdiri atas penugasan pilot Boeing 737-200 dan penugasan awak kabin pesawat Boeing 737-200. Contoh output model untuk pesawat Cassa 212 ditunjukaan oleh Tabel 2. Tabel 2 Ouput Penugasan Pilot Cassa 212 pada Pairing yang Disediakan

Ouput bernilai 1 berarti pilot-i ditugaskan pada pairing-j, dan output 0 berarti pilot-i tidak ditugaskan pada pairing-j. Roster/jadwal individual dapat dibuat dengan menggunakan output dari model, data hari keberangkatan pairing, dan duty period pairing. Tabel 3 menunjukkan penjadwalan pilot Cassa 212 berdasarkan output model pada Tabel 2. Tabel 3 Roster untuk Pilot Pesawat Cassa 212

ISBN : 978-979-99735-9-7 A-8-4


B. Analisa hasil Hasil eksperimen menunjukkan bahwa metode DE, column generation, dan MOSI memberikan performansi yang sama dalam hal pemenuhan kendala roster, keculai untuk pesawat Cassa 212. Pada penugasan pesawat Cassa 212 metode DE tidak melanggar kendala kebutuhan pilot ideal sedangkan metode column generation dan MOSI melanggar kendala ini, yaitu hanya menugaskan 1 pilot pada pairing 8981 sedangkan kebutuhan pilot sebenarnya adalah 2 orang pilot. Pada kriteria jam terbang minimum DE inferior hanya pada penugasan Cassa 212 sedangkan untuk ketiga pesawat lain sama seperti ditunjukkan Tabel 2. Tabel 4 Total jam Terbang Ketiga Metode

Pada kriteria deviasi hari terbang metode DE superior di tiga jenis pesawat dan inferior dibandingkan MOSI pada pesawat Cassa 212 seperti ditunjukkan Tabel 3. Tabel 5 Total Deviasi Hari Terbang Tiga Metode

Sedangkan pada kriteria open time DE menunjukkan hasil yang superior dibandingkan kedua metode lainnya pada penugasan Cassa 212 seperti ditunjukkan Tabel 4. Tabel 6 Open Time Setiap Metode Rostering

Dataset untuk penugasan pilot dan awak kabin jenis Boeing 737-200 berukuran sangat besar (17 pilot dengan 82 pairing) sehingga akan membutuhkan iterasi, jumlah

ISBN : 978-979-99735-9-7 A-8-5


populasi, dan waktu komputasi yang sangat besar untuk mendapat solusi near optimal jika diselesaikan langsung dengan algoritma DE pada umumnya. Penelitian ini mengusulkan metode berurutan antara partial optimization dan total optimization. Pada partial optimization dataset dipecah menjadi beberapa kelompok dan diselesaikan dengan metode DE. Pada kasus rostering pilot Boeing 737-200 permasalahan dipecah menjadi 3 kelompok . Kemudian solusi dari ketiga kelompok ini digabung menjadi satu sebagai solusi awal untuk total optimization. Dengan solusi awal yang telah mendekati optimal membuat proses pada total optimisasi lebih efisien. Pada penugasan pilot dan awak kabin Boeing 737-200 ketiga metode melanggar kendala jumlah kebutuhan pilot ideal. Metode DE tidak melanggar kendala hari terbang, sedangkan kedua metode lain melanggar kendala ini, tercatat 6 pilot dan 6 awak kabin ditugaskan melebihi batas hari terbang per bulan maksimum 21 hari. Sedangkan 7 pilot dan 7 awak kabin ditugaskan melebihi batas hari terbang per bulan oleh MOSI. Tabel 5 menunjukkan pelanggaran kendala roster oleh ketiga metode. Tabel 7 Pelanggaran Kendala pada Penugasan Pilot dan Awak Kabin Boeing 737-200

Pada penugasan pilot Boeing 737-200, metode DE superior pada kriteria minimum jam terbang, tetapi inferior pada kriteria deviasi hari terbang dan open time seperti ditunjukkan Tabel 6. Tabel 8 Kualitas Roster Penugasan Pilot Boeing 737-200

Penugasan awak Boeing 737-200 menghasilkan kualitas roster yang berbeda dengan penugasan pilot. Metode DE superior pada kriteria deviasi hari terbang tetapi inferior pada kriteria jam terbang minimum dan open time minimum seperti ditunjukkan Tabel 7.

ISBN : 978-979-99735-9-7 A-8-6

Prosiding Seminar Nasional Manajemen Teknologi XI Program Studi MMT-ITS, Surabaya 6 Pebruari 2010 Tabel 9 Kualitas Roster Penugasan Awak Boeing 737-200

KESIMPULAN Permasalahan penjadwalan roster PT. MNA secara umum memiliki karakteristik yang tidak berbeda dengan maskapai penerbangan lain dalam hal kriteria performansi dan kendala roster. Pemilihan probabilitas mutasi dan crossover merupakan kunci sukses penerapan DE, terpilih cm = 0.1 dan cr = 0.5 sebagai kombainasi terbaik. Berbeda dengan penerapan DE secara umum, karena variabel keputusanya biner, pada paper ini diperkenalkan random swap sebagai operator mutasi. Untuk dataset berukuran kecil DE membuktikan lebih kompetitif dibandingkan kedua metode baik dari pemenuhan kendala roster maupun kualitas roster. Sedangakan pada dataset berukuran besar, metode DE memberikan pemenuhan kendala roster lebih baik dan sama baik dalam kualitas roster dibandingkan metode column generation dan MOSI. DAFTAR PUSTAKA Andiek, S., Santosa, B., and Rahman, A. (2010). “ Pengembangan model airline rostering system menggunakan metode differential evolution “. Tesis. Box, M. J. (1965). “ A new method of constrained optimization and a comparison with other methods ”. Computer journal, Vol. 8, No. 1, pp. 42-52. Fahle, T., U. Junker, S.E. Karisch, N. Kohl, M. Sellmann, and B. Vaaben. (2002). “Constraint Programming Based Column Generation for Crew Assignment.” Journal of Heuristics 8(1), 59–81 Fox, R.L. (1971). “ Optimization Methods for Engineering Design “. Addison-Wesley, Reading, Mass. Kennet, V., Rainer, M., and Jouni, A. (2005). “ Differential Evolution : A practical approach to global optimization“. Springer-Verlag, Berlin, Germany. Labiba, Z. (2006). “ Penjadwalan roster kru pesawat dengan metode column generation : studi kasus di PT. Merpati Nusantara Airlines ”. Tesis. Levine, D., (1996). “ Application of a hybrid genetic algorithm to airline crew scheduling “. Compputer Operations Research, volume 23, no. 6, pp. 547-558 Lučić, P. and Teodorović, D. (1999). “ Simulated annealing for the multi-objective aircrew rostering problem “. Transportation Research Part A 33, 19 – 45.

ISBN : 978-979-99735-9-7 A-8-7


Medard, C. P. and Sawhney, N., (2005). ” Airline crew scheduling from planning to operation “. European Journal of Operational Research 183, 1013 – 1027. Sellmann, M., K. Zervoudakis, P. Stamatopoulos, and T. Fahle. (2002). “Crew Assignment via Constraint Programming: Integrating Column Generation and Heuristic Tree Search.” Annals of Operations Research 115, 207–225 Souai, N. and Thegem, J. (2009). “Genetic algorithm based approach for the integrated airline crew-pairing and rostering problem”. European Journal of Operational Research 199, 674-683. Wood, D. C.(1969), A Technique for Colouring a Graph Application to Large Scale Timetabling Problem, The Computer Journal, 12, 317-319 Yinghui, Z., Yunbao, R., and Mingtian, Z., (2007). “ GASA hybrid algorithm applied in airline crew rostering system ”. Tsinghua Science and Thechnology ISSN 10070214 46/49 pp. 225-259, volume 12, number S1.

ISBN : 978-979-99735-9-7 A-8-8

PENGEMBANGAN MODEL AIRLINE ROSTERING SYSTEM MENGGUNAKAN METODE DIFFERENTIAL EVOLUTION

Recommend Documents