PERBANDINGAN PERFORMANSI METODE METAHEURISTIK DALAM PENYELESAIAN PROBLEM AIRLINE CREW ROSTERING Farida Indriana dan Budi Santosa Jurusan Teknik Industri Institut Teknologi Sepuluh Nopember (ITS) Surabaya Kampus ITS Sukolilo Surabaya 60111 Email:
[email protected] ;
[email protected]
Abstrak Airline crew rostering merupakan bagian dari problem airline crew scheduling yaitu menjadwalkan crew pada beberapa pairing penugasan dengan tujuan untuk meminimumkan total biaya crew dengan memperhatikan kualitas hidup crew. Masalah yang dihadapi dalam proses rostering semakin kompleks karena adanya constrain dari aturan-aturan perusahaan. Oleh karena itu, pada penelitian ini dilakukan percobaan menggunakan beberapa algoritma metaheuristik yaitu Differential Evolution (DE), Particle Swarm Optimization (PSO),dan Harmony Search (HS) dalam penyelesaian crew rostering. Hasil dari ketiga metode heuristik dilakukan perbandingan performansinya dalam penyelesaian problem. Problem diselesaikan dengan mengembangkan algoritma metaheuristik dan diterjemahkan dalam bahasa pemrograman Matlab. Berdasarkan penelitian yang telah dilakukan maka terlihat bahwa dari ketiga metode heuristik yang diujikan, DE memiliki kualitas solusi yang lebih baik dari pada PSO dan HS. Metode PSO dan HS hanya mampu menghasilkan solusi yang baik pada tingkat pairing yang kecil, akan tetapi dari segi waktu komputasi HS memerlukan waktu yang lebih cepat dibanding metode lain. Kata Kunci : Metaheuristik, Differential Evolution, Particle Swarm Optimization, Harmony Search, Airline Crew Rostering ABSTRACT Airline crew rostering, part of airline crew scheduling problem is assign crew to the pairing has been done with have objective to minimize total cost and considering to airline’s quality of life for the crew. Airline crew rostering problem become more complex because of company’s rules and regulations constrain. So, in this research has been used several of metaheuristics algorithm, they are Differential Evolution (DE), Particle Swarm Optimization (PSO), and Harmony Search (HS) to solve crew rostering. The result of three method has been compared to show their performance to solve problem. Problem is solved by developing metaheuristics algorithm and decode to matlab. Based on research that has been done, it is known that DE has quality of solution well than both of PSO and HS. PSO and HS method only can produce good result at a few of pairing, but in the term of computing time, the HS algorithm performance on solving crew rostering is faster than the other algorithm. Key Words : Metaheuristics, Differential Evolution, Particle Swarm Optimization, Harmony Search, Airline Crew Rostering
1.
Pendahuluan
Problem crew scheduling merupakan permasalahan yang cukup kompleks bagi suatu maskapai penerbangan di Indonesia. Dari segi biaya yang harus dikeluarkan, biaya untuk penugasan kru (pilot, co-pilot, dan awak kabin) merupakan faktor biaya terbesar kedua setelah biaya bahan bakar (Kohl and Karish,2004). Dalam Kerati et.al.(2002) disebutkan bahwa proporsi biaya kru dari sebuah perusahaan penerbangan adalah 15-20% dari total biaya operasional. Sehingga hal ini membuat maskapai penerbangan melakukan efisiensi
dalam memanfaatkan kru agar tetap kompetitif. Oleh karena itu, perusahaan penerbangan secara kontinu terus mencari jalan terbaik untuk melakukan perbaikan sistem penjadwalan agar dapat memanfaatkan sumber daya kru yang efisien. Karena jika penjadwalan kru pada maskapai terganggu, maka akan terjadi peningkatan pada biaya kru yang harus ditanggung oleh maskapai penerbangan. Sebaliknya apabila perusahaan dapat menurunkan biaya kru, maka penghematan yang dihasilkan akan cukup besar.
Saat ini, penelitian mengenai crew scheduling telah banyak dilakukan, diantaranya Sangcham Kerati et.al.(2002), Kohl and Karish (2004), Abbink et.al. (2008), Medard and Sawhney (2005). Akan tetapi penelitian ini tetap menjadi topik yang menarik karena problem dalam crew scheduling merupakan problem optimasi kombinatorial yang bersifat kompleks dan sangat sulit untuk diselesaikan (Kerati et.al., 2002) dan di Indonesia penelitian ini belum banyak dilakukan. Hal ini juga berkaitan dengan adanya kebijakan dan aturan-aturan yang berbeda pada setiap perusahaan maskapai penerbangan. Untuk itu, berbagai penelitian tetap banyak dilakukan untuk mengembangkan metode untuk crew scheduling yang dapat menghasilkan output yang optimal dan memiliki kecepatan dalam computational time.
dari langkah-langkah pada ketiga algoritma ini tidak terlalu panjang.
Pada penelitian ini, metode metaheuristik yang dibandingkan yaitu Differential Evolution (DE), Particle Swarm Optimization (PSO) dan Harmony Search (HS). Metode DE pernah digunakan dan memiliki hasil yang cukup bagus dibandingkan dengan metode Column Generation dan Dekomposisi Eksak. Sedangkan PSO dan HS dipilih dipilih dalam penelitian ini karena kedua algoritma ini menunjukkan hasil yang bagus ketika digunakan untuk menyelesaikan beberapa masalah optimasi. Selain itu, algoritma ini memiliki beberapa keunggulan, yaitu mempunyai konsep sederhana, mudah diimplementasikan, dan efisien dalam perhitungan jika dibandingkan dengan algoritma matematika dan teknik optimisasi heuristik lainnya. Selain itu, penulis menggunakan metode ini karena dalam penelitian-penelitian sebelumnya, belum ada yang menggunakan metode PSO dan HS dalam menyelesaikan problem crew scheduling.
Problem crew rostering yang akan diselesaikan pada penelitian ini diformulasikan dalam fungsi tujuan dan beberapa fungsi kendala. Berdasarkan model matematis pada Thesis Andik Sunarto (2010), permasalahan dalam crew rostering dapat dituliskan sebagai berikut: Index k adalah indeks untuk kru pesawat. i adalah indeks untuk anggota tiap jenis kru (1,…,mk). j adalah indeks rotasi/pairing yang ditugaskan untuk setiap jenis kru (1,…,nk). l jumlah hari dalam 1 bulan penjadwalan.(1,…,31) Parameter djk adalah panjang rotasi ke j yang ditugaskan pada kru ke-k. panjang rotasi diekspresikan sebagai jam terbang. dmaks,k adalah panjang flight time maksimum kru-k dalam satu bulan vjk adalah jumlah take off dalam rotasi j yang ditugaskan pada kru-k vmax,k adalah jumlah take off maksimum kru-k dalam satu bulan. Dmin,jk adalah jumlah anggota kru-k minimum yang diperlukan untuk melengkapi rotasi-j tjk adalah jumlah total hari yang diperlukan kru-k untuk menyelesaikan rotasi j tmax,k adalah hari paling lama anggota kru-k terbang sbelum free day
Pada penelitian terdahulu, problem crew scheduling pernah dikerjakan dengan menggunakan metode Genetic Algorithm, akan tetapi algoritma ini memerlukan waktu komputasi yang sangat lama, sedangkan masalah penjadwalan crew merupakan masalah krusial dalam penerbangan dan kecepatan dalam pembentukan jadwal merupakan faktor penting yang diperhitungkan. Untuk itu dalam penelitian ini algoritma yang dibandingkan adalah DE, PSO dan HS yang dari beberapa penelitian yang banyak dilakukan menghasilkan waktu komputasi yang lebih cepat, hal ini terlihat juga
Penelitian ini dilengkapi batasan Fungsi optimasi yang akan digunakan yaitu meminimumkan biaya roster, meminimumkan deviasi jam terbang, dan meminimumkan total open time serta batasan roster yaitu Roster yang disusun memuat jadwal crew cockpit (pilot dan co-pilot) dengan single home base. Manfaat yang diharapkan pada penelitian ini adalah memberi alternatif metode untuk menyelesaikan masalah crew rostering problem pada maskapai penerbangan di Indonesia dan mengetahui metode yang memiliki performansi yang bagus dalam penyelesaian problem crew rostering. 2.
Model Permasalahan
2
ada tugas terbang. Jika jumlah hari dalam satu bulan penjadwalan adalah 31 hari, maka open time untuk anggota kru-k diformulasikan sebagai berkut: untuk k=1,..,8 (4) Costrain Constraint yang digunakan dalam problem ini berdasarkan aturan dari perusahaan. 1. Costrain flight time
Variabel Keputusan
Pada aturan perusahaan, terdapat batasan jam terbang maksimum. Jam terbang maksimum untuk pilot sebesar 110 jam per bulan. Sehingga dmax,k = 110 untuk k =1,…,7. Kendala jam terbang maksimum per bulan untuk anggota kruk diformulasikan sebagai berikut.
Variabel keputusan pada problem ini adalah
Fungsi Tujuan Fungsi tujuan dalam airline crew rostering adalam meminimumkan tiga hal, yaitu total biaya roster, deviasi jam terbang antar crew member, dan open time. 1. Total biaya roster Biaya roster yang dibayarkan oleh maskapai penerbangan kepada seorang kru adalah biaya variabel (gaji/jam), sehingga biaya ini dapat diwakili oleh jam terbang aktual masing-masing kru dengan asumsi bahwa gaji/jam semua kru adalah sama. Fungsi tujuan meminimumkan biaya roster dapat diformulasikan sebagai berikut: untuk k=1,…,8
(1)
2. Deviasi hari terbang antar crew member Jika adalah hari terbang rata-rata per bulan pada anggota kru-k, maka untuk k= 1,…,8
(2)
Sehingga fungsi minimasi deviasi total hari terbang per bulan antara anggota kru-k dapat diformulasikan sebagai berikut: untuk k=1,..,8 (3) Dimana p adalah bilangan bulat positif. Dalam penelitian ini ditentukan bahwa p=1
untuk i=1,…,mk dan (5)
k=1,…,8 2. Costrain duty period
Dalam aturan perusahaan, batasan hari terbang dari maksimum yang diperbolehkan bagi seorang anggota kru-k tidak lebih dari 21 hari. k=1,…,8
untuk i=1,…,mk dan (6)
3. Costrain jumlah take off total selama satu bulan Jumlah take off maksimum yang boleh dilakukan oleh seorang pilot tidak melebihi 90 kali, sehingga vmax,k=90 untuk pilot, sedangkan untuk awak kabin tidak ada batasan take off. Kendala jumlah take off maksimum untuk anggota kru-k adalah sebagai berikut: k=1,…,7
untuk i=1,…,mk dan (7)
4. Costrain jumlah kebutuhan kru minimum setiap rotasi Jumlah kru yang diperhitungkan dalam batasan ini yaitu kru yang ber-home base di tempat yang sama, sedangkan yang tidak ber-home base di tempat yang sama tidak diperhitungkan. untuk
i=1,…,mk
3. Open time
k=1,…,8
Open time merupakan hari dimana seorang anggota kru menganggur karena tidak
5. Costrain free day (hari libur)
dan (8)
3
Setelah melakukan penerbangan 7 hari berturut-turut, setiap anggota kru harus memiliki free day (hari libur). 1,…,23, dan k=1,…,8
untuk i=1,…,mk, p= (9)
6. Costrain rotasi free day
3.
Kendala ini mencerminkan bahwa angora kru-k tidak mendapatkan hari libur pada hari-hari pada saat rotasi-j yang sedang dilakukan belum selesai. untuk i=1,…,mk dan k=1,…,8
(10)
7. Costrain tidak boleh overlap Kendala ini digunakan untuk memastikan bahwa seorang kru tidak ditugaskan pada lebih dari satu penerbangan dalam waktu yang sama. j=1,…,nk, dan k=1,…,8 3.
4.
untuk i=1,…,mk (11)
Pengembangan Algoritma
Pada tahap ini dilakukan pengembangan algoritma untuk menyelesaikan permasalahan yang ada. Tahap pengembangan algoritma terbagi menjadi tahap penerapan algoritma dan tahap pembuatan model software.
5.
6.
3.1 Pengembangan Algoritma PSO Pada tahap ini dilakukan penerapan algoritma PSO agar dapat menyelesaikan crew rostering problem. Berikut ini merupakan tahapan dari pengembangan algoritma PSO untuk problem rostering. 1. Inisialisasi masalah Pada tahap ini diperkenalkan masalah yang akan diselesaikan. Masalah pada penelitian ini adalah crew rostering pada maskapai dengan fungsi tujuan yaitu meminimumkan biaya roster, meminimumkan deviasi hari terbang antar crew member dan meminimumkan open time. Sedangkan constrain/kendala yang dihadapi yaitu adanya batasan berupa jam terbang maksimum, hari terbang maksimum, jumlah take off total, jumlah kebutuhan kru minimum, kendala free day, dan kendala tidak boleh overlap. 2. Memasukkan parameter data maskapai.
7.
Data yang diperlukan untuk menyelesikan problem crew rostering ini antara lain availabilitas crew, parameter overlap antar pairing, parameter keberangkatan pairing, duty period setiap pairing, jam terbang setiap pairing, dan jumlah take off setiap pairing. Inisialisasi parameter algoritma PSO Beberapa parameter algoritma PSO yang digunakan yaitu: Ukuran swarm/jumlah partikel yang dibangkitkan sebanyak 25 Learning fator aspek kognitif (c1) =2 Learning fator aspek sosial (c2) =2 Kriteria pemberhentiannya adalah jumlah iterasi yang dilakukan sebanyak 100 iterasi. Inisialisasi posisi dan kecepatan awal partikel (x0 dan v0) Pada tahap ini akan, untuk posisi awal akan dibangkitkan matriks bilangan random biner (0 dan 1) dengan ukuran mk x nk sebanyak ukuran swarm yang digunakan. Untuk nilai kecepatan awal, akan dibangkitkan matriks bilangan random ukuran mk x nk sebanyak ukuran swarm yang digunakan dengan. Evaluasi nilai fungsi tujuan. Dari partikel yang dibangkitkan akan dihitung nilai fungsi tujuan untuk masingmasing partikel. Update nilai terbaik (Pbest dan Gbest). Dari nilai fungsi tujuan yang telah dihitung, dapat ditentukan nilai yang minimum untuk masing-masing partikel menjadi local best (Pbest) dan nilai yang paling minimum dari keseluruhan swarm menjadi nilai global best (Gbest). Melakukan update kecepatan untuk semua partikel. Perumusan update velocity menggunakan menggunakan model sebagai berikut: (12) Ketika melakukan update kecepatan, akan digunakan inersia untuk mengontrol dampak velocity terhadap perubahan posisi partikel. Bobot inersia nilainya mengecil dengan bertambahnya iterasi digunakan dengan formula: (13)
4
dimana dan masing-masing adalah nilai awal dan nilai akhir bobot inersia, imax adalah jumlah iterasi maksimum yang digunakan dan i adalah iterasi yang sekarang. Nilai yang digunakan adalah dan . 8. Melakukan update posisi untuk semua partikel. Karena problem crew rostering ini merupakan problem diskrit dengan output berupa nilai biner, maka digunakan update posisi dengan binary PSO, di mana posisi di update dengan menggunakan fungsi sigmoid (
2.
3.
), dengan cara membangkitkan
bilangan random berukuran mk x nk sebanyak ukuran swarm dan membandingkan dengan nilai dari funsi sigmoid. Nilai x akan ditentukan berdasarkan persamaan sebagai berikut: (14) 4. 9. Evaluasi nilai fitness function (fungsi tujuan). Dari partikel yang dibangkitkan akan dihitung nilai fungsi tujuan untuk masingmasing partikel. 10. Melakukan pengecekan terhadap keriteria pemberhentian yang ditentukan. Apabila kriteria pemberhentian yang telah ditentukan tercapai, maka proses komputasi akan dihentikan, apabila belum tercapai, maka kembali ke langkah 6. 3.2 Pengembangan Algoritma HS Pada tahap ini dilakukan penerapan algoritma HS agar dapat menyelesaikan Crew rostering Problem. Berikut ini merupakan pengembangan algoritma HS untuk problem rostering. 1. Inisialisasi masalah Pada tahap ini diperkenalkan masalah yang akan diselesaikan. Masalah pada penelitian ini adalah crew rostering pada maskapai dengan fungsi tujuan yaitu meminimumkan biaya roster, meminimumkan deviasi hari terbang antar crew member dan meminimumkan open time. Sedangkan constrain/kendala yang dihadapi yaitu adanya batasan berupa jam terbang
5.
maksimum, hari terbang maksimum, jumlah take off total, jumlah kebutuhan kru minimum, kendala free day, dan kendala tidak boleh overlap. Memasukkan parameter data maskapai. Data yang diperlukan untuk menyelesikan problem crew rostering ini antara lain availabilitas crew, parameter overlap antar pairing, parameter keberangkatan pairing, duty period setiap pairing, jam terbang setiap pairing, dan jumlah take off setiap pairing. Inisialisasi parameter algoritma HS Beberapa parameter algoritma HS yang digunakan yaitu: Harmony Memory Size (HMS) sebanyak 25 Harmony memory Considering Rate (HMCR) dengan interval 0.7-0.95 Pitch Adjusting Rate (PAR) dengan interval 0.1-0.5 Kriteria pemberhentiannya adalah jumlah iterasi yang dilakukan sebanyak 100 iterasi. Inisialisasi Harmony Memory Pada tahap ini akan dibangkitkan matriks bilangan random biner 0 dan 1 dengan ukuran mk x nk sebanyak HMS. Setelah itu, dilakukan perhitungan nilai fungsi tujuan dari Harmony Memory. Memperbaiki harmony yang baru Harmony yang baru diperbaiki dengan 3 cara, yaitu: Apabila bilangan random yang dibangkitkan untuk pertama kali memiliki nilai di atas HMCR, maka akan dibangkitkan variabel keputusan yang baru secara random. Apabila bilangan random yang dibangkitkan untuk pertama kali kurang dari HMCR dan bilangan random yang dibangkitkan untuk kedua kalinya lebih besar dari PAR, maka variabel keputusan akan diambil dari harmony memory. Pengambilan harmony memory ini menggunakan aturan. D1=int[1+(HMS-1)rand] D2=HM(D1,i) VKB(i)=D2 Dimana D1 = nilai yang menyatakan pemilihan lokasi pada
5
harmony memory secara random. Int = integer D2 = nilai variabel keputusan yang diambil dari harmoy memory. Apabila bilangan random yang dibangkitkan untuk pertama kali kurang dari HMCR dan bilangan random yang dibangkitkan untuk kedua kalinya lebih kecil dari PAR, maka variabel keputusan yang baru yaitu melakukan pitch adjusting (penyesuaian) pada variabel keputusan yang telah diambil dari harmony memory. Penyesuaian ini dilakukan sengan metode random swap dengan cara sebagai berikut. - Bangkitkan bilangan random antara 0-1, sebesar ukuran matriks variabel keputusan (mk x nk) - Pada elemen matriks tersebut misalnya, jika nilai bilangan random < PAR, maka berlaku aturan = (elemen matriks D2 +1)mod2, - Jika nilai bilangan random > PAR, elemen matriks D2 tidak berubah. 6. Meng-update harmony memory Langkah yang dilakukan untuk memperbaiki harmony memory yaitu sebagai berikut: Menghitung nilai fungsi tujuan dari variabel keputusan baru yang telah dipilih pada langkah ke-5. Melakukan pengecekan terhadap harmony memory yang baru. Apabila nilai fungsi tujuan pada variabel keputusan (harmony) yang baru lebih baik dari nilai fungsi tujuan terjelek pada harmony memory, maka harmony yang baru akan dimasukkan ke dalam harmony memory dan harmony terjelek akan dikeluarkan dari harmony memory. Tetapi, apabila nilai harmony yang baru lebih buruk dari pada nilai terjeleh pada harmony memory, maka tidak terjadi perubahan pada harmony memory. 7. Mengecek kriteria pemberhentian. Apabila kriteria pemberhentian yang telah ditentukan tercapai, maka proses komputasi akan dihentikan, apabila belum tercapai, maka kembali ke langkah 5.
4
Pengujian Algoritma
Algoritma PSO dan HS yang telah dikembangkan diterjemahkan dalam model software dan dibuat code-nya dalam bahasa pemrograman Matlab 7.0.4. Program di-run dengan menggunakan kombinasi parameterparameter algoritma yang terbaik (PAR=0.5, HMCR=0.85 untuk metode HS dan C1=2 ,C2=2). Program komputer dieksekusi dengan komputer Dual Core Processor 1,8 GHz dan RAM 896 MB dengan menggunakan data penelitian dari Thesis Andik Sunarto (2010). Data tersebut merupakan data pairing pesawat Cassa 212, DHC-6, CN-235, dan F-100 PT. Merpati Nusantara Airlines pada bulan Mei 2006. 4.1 Uji Performansi Algoritma DE, PSO, dan HS Pengujian terhadap performansi dari algoritma DE, PSO, dan HS dilakukan dengan melihat nilai fungsi tujuan dan waktu komputasi yang digunakan untuk menghasilkan output jadwal roster. Pengujian pertama dilakukan pada pilot pesawat Cassa 212 yang terdiri dari 6 orang pilot dengan 13 pairing penerbangan. Hasil output dari tiga algoritma dapat ditampilkan dalam Tabel 4.1. Tabel 4.1 Hasil Output Program Pesawat Cassa 212 Replikasi 1 2 3 4 5 6 7 8 9 10 Rata-rata
DE
HS 17)
PSO 17)
17) tm (detik) ftotx (x 10 tm (detik) ftotx (x 10 tm (detik) ftotx (x 10 5.42 0.01 5.06 3.12 6.94 1.28 5.52 0.20 5.66 4.14 6.92 10.98 5.91 0.14 5.08 6.53 6.92 1.20 5.81 0.05 5.13 3.87 6.95 1.70 5.70 0.10 5.08 3.76 6.92 2.66 5.38 0.10 5.08 12.94 6.95 11.30 5.41 0.12 5.05 7.39 6.94 14.22 5.38 0.15 5.08 4.67 6.94 1.48 5.42 0.14 5.09 4.90 6.95 6.90 5.39 0.11 5.11 8.64 6.92 2.30 5.53 0.11 5.14 6.00 6.94 5.40
Tabel 4.2 berikut ini merupakan hasil output program pada pesawat DHC-6 yang terdiri dari 3 pilot dengan 10 paring penerbangan. Program dijalankan dengan replikasi sebanyak 10 kali dan bagian dengan shading berwarna hijau merupakan hasil output dengan nilai terbaik.
6
Tabel 4.2 Hasil Output Program Pesawat DHC-6 Replikasi 1 2 3 4 5 6 7 8 9 10 Rata-rata
DE
HS 16)
Tabel 4.4 Hasil Output Program Pesawat F-100
PSO 16)
tm (detik) ftotx (x 10 tm (detik) ftotx (x 10 2.61 1.0193 2.02 7.33 2.59 0.0592 2.00 46.75 2.59 0.0592 2.00 18.30 2.59 1.0193 1.98 4.07 2.55 0.0292 2.03 3.05 2.59 1.0192 2.00 1.54 2.58 0.0192 2.00 2.21 2.58 0.0192 2.00 3.52 2.56 2.0094 2.00 2.53 2.53 0.0192 1.98 3.03 2.58 0.53 2.00 9.23
Replikasi 16)
tm (detik) ftotx (x 10 2.95 4.03 2.94 2.53 2.92 1.54 2.92 1.88 2.95 2.41 2.91 3.01 2.92 2.53 2.92 2.41 2.98 1.56 3.00 1.54 2.94 2.34
Pada Tabel 4.3 berikut ini ditampilkan hasil output program pada pesawat CN 235 yang terdiri dari 4 pilot dengan 8 paring penerbangan. Program dijalankan dengan replikasi sebanyak 10 kali dan bagian dengan shading berwarna hijau merupakan hasil output dengan nilai terbaik. Tabel 4.3 Hasil Output Program Pesawat CN-235 Replikasi 1 2 3 4 5 6 7 8 9 10 Rata-rata
DE
HS 16)
PSO
16) tm (detik) ftotx (x 10 tm (detik) ftotx (x 10 tm (detik) ftotx (x 10 3.50 0.30 2.67 4.46 3.89 3 3.22 0.01 2.63 5.09 3.83 17.72 3.20 0.01 2.66 6.26 3.83 9.71 3.23 0.40 2.63 4.67 3.86 16.32 3.22 0.40 2.64 2.75 3.81 3.01
3.22 3.20 3.17 3.16 3.20 3.23
0.01 0.01 0.01 0.01 0.01 0.12
16)
2.67 2.63 2.64 2.64 2.67 2.65
5.88 4.47 2.64 5.72 4.41 4.64
3.88 3.84 3.81 3.83 3.84 3.84
3.31 6.02 2.9 20.22 4.51 8.67
Pengujian keempat dilakukan pada pesawat F100 dengan 5 pilot dengan 4 paring penerbangan. Program dijalankan dengan replikasi sebanyak 10 kali dan bagian dengan shading berwarna hijau merupakan hasil output dengan nilai terbaik. Hasil output dari ketiga algoritma dapat dilihat pata Tabel 4.4.
DE tm (detik)
HS ftotx
tm (detik)
PSO tm (detik) ftotx
ftotx
1
3.16
661,577
2.25
4.5 x 1015
3.56
801,093
2 3 4
3.50 3.13 3.13
660,857 660,857 660,857
2.23 2.30 2.23
2x 1014 661,577 661,577
3.55 3.56 3.56
851,972 661,577 801,173
5
3.08
660,857
2.20
3.66
851,292
6
3.13
660,857
2.23
4.1 x 1015 1.82 x 1016
3.55
661,577
16
7
3.13
660,857
2.27
661,577
3.09
660,857
2.25
1.42 x 10 4.1 x 1015
3.56
8
3.53
801,093
9
3.13
660,857
2.23
8.1 x 1015
3.53
660,857
3.42
660,857
10 Rata-rata
660,857
2.23
4.1 x 10
15
3.16 660929.00
2.24
5.75 x 10
15
3.11
3.55 741306.80
Pada uji performansi algoritma ini, dilakukan perbandingan nilai fungsi tujuan yang dihasilkan dan waktu komputasi yang diperlukan oleh algoritma untuk menghasilkan solusi berdasarkan kriteria pemberhentian yang sama. Pada tahap ini masing-masing program di eksekusi dengan menggunakan kombinasi parameter yang baik dan dilakukan running sebanyak 10 replikasi. Analisa dilakukan dengan melihat nilai terbaik dari sepuluh kali replikasi serta menentukan rata-rata output dari masing algoritma. Nilai fungsi tujuan yang dihitung dari uji algoritma ini yaitu jumlah keseluruhan dari jam terbang crew, deviasi hari terbang dan open time. Pada masing-masing fungsi tujuan diberikan bobot sesuai kepentingannya. Fungsi tujuan jam terbang crew dijadikan prioritas utama sehingga diberi bobot 104, untuk deviasi hari terbang diberi bobot nilai 102, dan open time diberi bobot 1. Sedangkan untuk konstrain yang digunakan, dalam perhitungannya, setiap solusi yang melanggar konstrain dikenai penalty pelanggaran sebesar nilai penalty dikalikan dengan kuadrat dari nilai pelanggaran. Sehingga semakin banyak pelanggaran yang dilakukan, semakin besar biaya roster yang ditimbulkan. Dalam penelitian ini, penalty terkecil yang digunakan sebesar 1013. Penalty yang diberikan pada setiap konstrain berbeda-beda, tergantung dari kemungkinan kendala boleh dilanggar. Misalnya untuk overlap diberi nilai 103 kali nilai penalty terkecil. Pemberian penalty ini bertujuan agar solusi yang dihasilkan akan menuju solusi dengan jumlah pelanggaran yanag semakin sedikit seiring dengan bertambahnya iterasi yang digunakan, sehingga menghasilkan roster
7
dengan jumlah pelanggaran yang minimum dan biaya yang kecil. Dari hasil running program yang ditunjukkan oleh Tabel 4.1, Tabel 4.2, Tabel 4.3, dan Tabel 4.4 diketahui bahwa rata-rata hasil output algoritma pada semua roster menunjukkan performansi yang sama, yaitu nilai fungsi tujuan yang terbaik dapat diperoleh dengan algoritma DE, sedangkan waktu komputasi yang minimum dihasilkan oleh algoritma HS. Nilai fungsi tujuan dari ketiga algoritma antara replikasi yang satu dengan yang lain berfluktuasi. Akan tetapi dapat terlihat bahwa pencapaian nilai minimum dari sepuluh kali replikasi fungsi tujuan pada algoritma DE lebih unggul di sebagian besar jadwal crew, yaitu pada pesawat Cassa 212, DHC-6, dan CN 235. Fungsi tujuan terbaik kedua mampu dihasilkan oleh algoritma PSO, hal ini dapat dilihat pada output pesawat F-100. Pada output ini, nilai fungsi tujuan yang dihasilkan oleh algoritma PSO mampu mendekati output DE, dan bahkan pada replikasi ke 9 dan 10, nilai output PSO mampu menyamai output DE. Hal ini menandakan bahwa algoritma PSO bisa memperoleh hasil yang mendekati optimal untuk problen jadwal dengan jumlah crew dan pairing yang kecil. Untuk algoritma HS, output yang dihasilkan tidak terlalu bagus dibandingkan dengan algoritma PSO dan DE, akan tetapi untuk problem dengan jumlah crew dan pairing yang kecil HS juga mampu menghasilkan output yang mendekati nilai pada DE dan PSO. Output lain dari algoritma yang dianalisa adalah waktu komputasi yang diperlukan untuk menjalankan program. Dari masing-masing algoritma yang telah di-running 10 kali akan dibandingkan waktu komputasinya. Untuk masing-masing jadwal crew, waktu yang diperlukan untuk menghasilkan output bisa berbeda-beda terhantung jumlah crew dan pairing yang dijadwalkan. Dengan menggunakan jumlah populasi dan iterasi yang sama, waktu komputasi yang dibutuhkan oleh algoritma HS lebih cepat dari dua algoritma lainnya. Hal ini dikarenakan HS tidak menggunakan aturan mutasi dan crossover seperti pada algoritma DE. Sedangkan jika dibandingkan dengan algoritma PSO, algoritma HS lebih efisien waktu karena dalam setiap iterasi hanya ada 1 kandidat solusi yang dievaluasi dengan fungsi tujuan, hal ini berbeda dengan PSO yang semua populasinya dievaluasi
fungsi tujuannya sehingga membutuhkan waktu yang lebih lama sedangkan DE memerlukan waktu yang lama karena karena adanya mutasi sehingga solusi induk dan solusi mutan dievaluasi untuk memperoleh output. 4.2 Perbandingan Kualitas Roster yang Dihasilkan Algoritma DE, PSO, dan HS Perbandingan kualitas roster yang dihasilkan oleh masing-masing algoritma ini dilakukan dengan mengitung pencapaian masing-masing nilai fungsi tujuan, dalam permasalahan ini yang digunakan adalah total jam terbang 1 bulan, total deviasi hari terbang antar crew, dan total open time 1 bulan. Tabel 4.5, 4.6, 4.7 berikut ini menunjukkan nilai fungsi tujuan masing-masing algoritma. Tabel 4.5 Total Jam Terbang Ketiga Metode
Pesawat
Jam Terbang 1 Bulan DE
PSO
CASSA 212
267
465
492
DHC-6
156
176
156
CN-235
103
103
103
66
66
66
F-100
HS
Tabel 4.6 Total Deviasi Hari Terbang Ketiga Metode
Pesawat
Deviasi Hari Terbang DE
PSO
HS
23.0
19.0
32.0
DHC-6
7.3
14.0
9.3
CN-235
6
6
6
7.2
7.2
14.4
CASSA 212
F-100
Tabel 4.7 Total Open Time Ketiga Metode
Pesawat
Open Time DE
PSO
HS
115
63
56
DHC-6
37
30
37
CN-235
84
84
84
137
137
137
CASSA 212
F-100
Pada perbandingan kualitas roster ini, kualitas roster yang dihasilkan oleh masing-masing algoritma dilihat berdasarkan nilai masing-
8
masing fungsi tujuan yang dihasilkan, pada kasus ini yaitu total jam terbang selama 1 bulan, total deviasi hari terbang, serta total open time selama 1 bulan. Tabel 4.5 menunjukkan total jam terbang masing-masing pesawat yang dihasilkan oleh ketiga algoritma. Pada roster pesawat Cassa 212, DE mampu menghasilkan jumlah jam terbang yang lebih kecil dari algoritma yang lain, akan tetapi pada pesawat DHCperformansi DE sama dengan HS, sedangkan untuk pesawat CN 235 dan F-100, ketiga algoritma mampu memberikan performansi total jam terbang yang sama. Tabel 4.6 menunjukkan total deviasi jam terbang antar crew. Dilihat dari performansinya dalam menghasilkan roster yang memperhatikan faktor keadilan pada crew, ketiga algoritma memiliki tingkat performansi yang hampir sama. DE bagus pada roster pesawat DHC-6, CN 235, dan F-100 namun lemah dalam roster Cassa 212. Sedangkan PSO bagus pada roster pesawat Cassa 212, CN 235 dan F-100 namun lemah pada roster DHC-6. Sedangkan HS hanya bagus pada roster DHC-6 dan CN 235. Karena open time berlawanan dengan total jam terbang, maka tampak pada Tabel 4.7, DE yang bagus dalah hal jumlah jam terbang total yang minimum pada Cassa menghasilkan total hari menganggur yang lebih besar. 4.3 Perbandingan Output Algoritma DE, PSO, dan HS Terhadap Pemenuhan Kendala Penerbangan Cara lain yang digunakan untuk melihat kualitas roster yang dihasilkan oleh algoritma DE, PSO, dan HS yaitu dengan melihat pemenuhan terhadap kendala penerbangan yang menjadi constrain dari problem rostering ini. Pada Tabel 4.8, 4.9, dan 4.10 akan ditunjukkan nilai jam terbang, hari terbang, dan jumlah takeoff yang ditugaskan kepada masing-masing crew berdasarkan algoritma DE, PSO, dan HS.
Tabel 4.8 Jam Terbang Masing-masing Crew Pesawat
CASSA 212
DHC-6
CN-235
F-100
Pilot Irawan Yohanes Aji P. Nanang S Yudha AN Genggong Mofit A Erry HBP Jajag S Djoko Ishak Saptono Wakhid Eko Suryanto Bambang HP Agustinus NTB Mangunsong Sriyanto
Jam Terbang 1 bulan DE PSO HS 40 86 60 19 68 59 34 86 93 48 73 120 73 98 93 53 54 67 54 47 61 51 94 31 51 35 64 15 26 12 36 26 29 26 15 26 26 36 36 19 19 0 0 0 0 14 14 19 19 19 19 14 14 28
Tabel 4.9Total Hari Terbang Masing-masing Crew Pesawat
Pilot
Irawan Yohanes Aji P. CASSA 212 Nanang S Yudha AN Genggong Mofit A DHC-6 Erry HBP Jajag S Djoko Ishak CN-235 Saptono Wakhid Eko Suryanto Bambang HP F-100 Agustinus NTB Mangunsong Sriyanto
Hari Terbang 1 Bulan DE PSO HS 10 23 16 5 18 15 9 23 24 14 20 33 19 25 24 14 14 18 15 21 21 21 28 14 20 14 21 8 10 7 13 9 10 10 8 10 9 13 13 5 5 0 0 0 0 4 4 5 5 5 5 4 4 8
Tabel 4.10 Total Takeoff Masing-masing Crew Pesawat
Pilot
Irawan Yohanes Aji P. CASSA 212 Nanang S Yudha AN Genggong Mofit A DHC-6 Erry HBP Jajag S Djoko Ishak CN-235 Saptono Wakhid Eko Suryanto Bambang HP F-100 Agustinus NTB Mangunsong Sriyanto
Jumlah Take Off 1 Bulan DE PSO HS 39 82 58 16 71 53 37 83 87 52 70 118 69 89 89 52 55 69 15 21 21 21 28 14 20 14 21 24 30 14 40 26 36 30 24 30 26 40 40 13 13 0 0 0 0 11 11 13 13 13 13 11 11 22
Analisa pemenuhan kendala penerbangan ini perlu dilakukan untuk melihat seberapa besar biaya yang ditimbulkan dari adanya penalty pelanggaran dari masing-masing algoritma. Hal
9
yang dilakukan dalam hal ini yaitu dengan melihat nilai variabel yang menjadi kendala yang dihasilkan dari masing-masing algoritma. Pada dasarnya, algritma DE, PSO, dan HS dapat diaplikasikan untuk membentuk roster yang memenuhi kendala, karena dalam algoritma ini dilakukan evaluasi terhadap fitness function seperti pada problem pesawat F-100. Akan tetapi, pada problem yang terjadi pada penelitian ini, terdapat problem dimana crew yang tersedia tidak dapat memenuhi semua pairing penerbangan yang ada (problem yang diselesaikan merupakan problem yang melanggar aturan-aturan/konstrain) yaitu problem pada pesawat Cassa 212, CN 235 dan DHC-6. Algoritma DE, PSO, dan HS tetap dapat diterapkan untuk membentuk roster. Pada problem yang melanggar konstrain, ketiga algoritma ini dikembangkan untuk menghasilkan roster dengan meminimumkan pelanggaran konstrain. Dengan meminimumkan pelanggaran konstrain yang terjadi, maka akan meminimumkan biaya roster keseluruhan, karena tiap pelanggaran yang terjadi akan dikenai biaya penalty. Pada Tabel 4.8 terlihat bahwa algoritma DE dan PSO tidak melanggar aturan jam terbang maksimal untuk pilot yaitu 110 jam per bulan. Akan tetapi untuk algoritma HS, terdapat 1 pilot yang mengalami pelanggaran jam terbang, yaitu pada pilot pesawat cassa 212 sebesar 120 jam dalam 1 bulan. Untuk kendala total hari terbang, algoritma DE lebih unggul dari dua lagoritma yang lain karena tidak melanggar aturan hari terbang maksimum (21 hari), sedangkan pada algoritma PSO terdapat 4 orang yang melanggar dan untuk algoritma HS terdapat 3 orang yang melanggar, hal ini dapat dilihat pada Tabel 4.9. Sedangkan untuk kendala jumlah takeoff maksimum (90 kali dalam 1 bulan), hanya HS yang mengalami pelanggaran yaitu pada pilot pesawat Cassa 212. Dari pembentukan roster berdasarkan output program pada lampiran 2 dapat terlihat bahwa hampir semua kualitas roster terhadap pemenuhan kendala yang dihasilkan oleh DE lebih baik dari pada metode PSO dan DE. Hal ini terlihat bahwa DE hanya melanggar constrain kebutuhan day off (hari libur) crew dan jumlah kebutuhan pilot pada pesawat Cassa 212, CN 235 dan DHC-6, sedangkan untuk pesawat F-100, semua kendala dapat terpuaskan.
Sedangkan pada PSO dan HS, F-100 kendala juga dapat terpuaskan semua sedangkan untuk problem dengan jumlah pilot dan pairing yang lebih banyak (Cassa 212, CN 235 dan DHC-6) ada kendala yang tidak terpuaskan/dilanggar antara lain pada jam terbang crew, jumlah takeoff dan day off. 5 Kesimpulan dan Saran Bab ini berisi tentang kesimpulan hasil penelitian dan saran-saran yang berkaitan dengan penelitian selanjutnya. 5.1 Kesimpulan Berikut ini adalah beberapa kesimpulan yang bisa diberikan: 1. Perubahan parameter algoritma HS pada penyelesaian problem crew rostering tidak berpengaruh pada solusi yang dihasilkan. Sedangkan pada algoritma PSO, kombinasi dengan nilai bobot sosial yang besar menghasilkan solusi yang lebih baik dari pada kombinasi lain. 2. Di antara algoritma DE, PSO, dan HS, algoritma DE memiliki performansi yang lebih baik pada sebagian besar output roster, sedangkan jika dilihat dari waktu komputasi, algoritma HS memiliki waktu komputasi yang lebih cepat dari pada algoritma yang lain, tetapi solusi yang dihasilkan kurang memuaskan. 3. Algoritma PSO memiliki output yang optimal pada problem kecil dengan jumlah pilot dan pairing yang sedikit, tetapi untuk problem yang lebih besar, yaitu dengan 6 pilot dan 13 pairing, DE memiliki hasil yang lebih baik dari PSO dan HS. 5.2 Saran Penelitian tugas akhir ini memiliki potensi untuk dikembangkan lebih lanjut. Pada penelitian berikutnya disarankan untuk melakukan hybrid dengan algoritma lain pada algoritma PSO dan HS untuk dapat menghasilkan output yang lebih baik untuk problem dengan skala besar. 6
Daftar Pustaka
Abbink,E., dan Huisman, D. 2008. Solving Large Scale Crew Scheduling Problem by Iterative Partitioning. Erasmus
10
University Rosterdam, Econometric Institute Report EI 2008-03 Al-Betar, M.A., Khader, A.T., Gani,T.A., A harmony Search Algorithm fof University Course Timetabling. School of Computer Science,Universiti Sains Malaysia,11800 USM, Pinang. Ariani, D., Fahriza, A., dan Prasetyaningrum, I. Optimasi Penjadwalan mata Kuliah di Jurusan Teknik Informatika PENS dengan Menggunakan Algoritma Particle Swarm Optimization. Tugas Akhir Politeknik Elektronika Negeri Surabaya, ITS Butchers, E. R., Day, P. R., Goldie, A. P., Miller, S., Meyer, J., A., Ryan, D., M, Scott, A., C., dan Wallace, C., A. 2001. Optimized Crew Scheduling at Air New Zeland. Interfaces 31:30-56 Geem, Z. W. 2009. Music-Inspired Harmony Search Algorithm. Springer, Verlag, Berlin,Heidelberg. Geem,Z.W., Lee, K.S., dan Park, Y. 2005. Application of Harmony Search to Vehicle Routing. American Journal of Applied Science 2(12): 1552-1557 Kerati, S., Moudani, W. E. L., Coligny, M., dan Mora-Camino, F. 2002. A Heuristic Genetic Algorithm Approach for the Airline Crew Scheduling. www2.lifl.fr/PM2O/Reunions/ 04112002/kerati.pdf Kohl, N. 1999. The Use of Linear and Integer Programming in Airline Crew Scheduling. In Proceedings of the 3rd Scandinavian Workshop on Linear Programming, Lyngby, Denmark, August 26–28. Kohl,N. dan Karisch, S. 2004. Airline Crew Rostering : Problem Types, Modeling, and Optimization. Annals of Operations Research 127:223-257. Labiba, Zya. 2006. Aplikasi Metode Column Generation dalam Penyelesaian Penugasan Kru Maskapai Penerbangan: Studi Kasus di PT. Merpati Nusantara Airlines. Tesis Magister Teknik, Jurusan Teknik Industri ITS, Surabaya.
Masroeri, A. A. dan Indrawan, T. 2010. Optimasi Distribusi kapal Perang Armada Timur Menggunakan PSO Algoritma. Seminar Nasional Pascasarjana X-ITS Surabaya Medard, C. P., dan Sawhney, N., 2005. Airline Crew Scheduling From Planning to Operation. European Journal of Operational Research 183, 1013 – 1027. Pongchairerks, P. 2009. Particle Swarm Optimization Algorithm Applied to Scheduling Problem. Science Asia 35:89-94 Rusdiansyah, A., Mirenani, Y.D., dan Labiba, Z. 2007. Pemodelan dan Penyelesaian Permasalahan Penjadwalan Pilot dengan Metode Eksak Dekomposisi. Jurnal Teknik Industri vol. 9, no. 2. 112124. Sedighizadeh, D., dan Masehian, E. 2009. Particle Swarm Optimization Methods, Taxonomy and Applycations. International Journal of Computer Theory and Engineering 1:1793-8201 Sunarto, A. 2010. Pengembangan Model Airline Rostering System Menggunakan Metode Differential Evolution. Tesis Magister Teknik, Jurusan Teknik Industri ITS, Surabaya Tuegeh, M., Soeprijanto, dan Purnomo M. H., 2009. Modified Improved Particle Swarm Optimization for Optimal Generator Scheduling. Seminar Nasinal Aplikasi Teknologi Informasi. ISSN:1907-5022 Yang, C., dan Simon, D. _. A new Particle Swarm Optimization Technique. Electrical and Computer Engineering Department Cleveland State University Yen, J. W. __. A Stochastic Programming Approach to the Airline Crew Scheduling Problem. National Science Foundation under DMI-9523275
11
