RUTE DAN JADWAL PESAWAT UNTUK MEMENUHI PERMINTAAN PENUMPANG : KASUS AIRASIA
AVFITRIYANA G54102034
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2007
ABSTRACT AVFITRIYANA. Routing and Scheduling Aircraft to Fulfill Passenger Demand : AirAsia Case. Directed by AMRIL AMAN and PRAPTO TRI SUPRIYO. An operation of flight industry is a complex management problem. Commonly, the carrier faces problems to fulfill passenger demand and this should be done in order to maximize profit. One of problem is how the carrier solve fleet routing and flight scheduling problem with minimum aircraft quantity usage. Fleet routing and flight scheduling are critical activities in airline operations because both of them extremely affect aircraft usage efficiency, establishment of timetables, aircraft maintenance and crew scheduling. All of these will determine carrier’s profitability, its level of service and its competitive capability in the market. The flight scheduling process consists of two dependent phases, 1) the schedule construction phase and 2) the schedule evaluation phase. In schedule construction phase a timetable is developed based on the projected demand and the market share. Then, the drafted timetable is examined during the schedule evaluation phase for operating feasibility, cost and performance considerations. The feasibility checks in this evaluation phase is conducted to aspects related to fleet route, fleet size, crew scheduling, and maintenance arrangements. This research applies a time-space network technique in the formulation a model for fleet routing and flight scheduling problems. This solution of the problem is obtained using LINGO 8.0’s software with Branch and Bound method.
ABSTRAK AVFITRIYANA. Rute dan Jadwal Pesawat untuk Memenuhi Permintaan Penumpang : Kasus AirAsia. Dibimbing oleh AMRIL AMAN dan PRAPTO TRI SUPRIYO . Operasi suatu industri penerbangan merupakan suatu permasalahan manajemen yang kompleks. Secara umum, perusahaan dihadapkan pada persoalan dalam memenuhi permintaan calon penumpang dan upaya untuk memaksimumkan keuntungan. Salah satu dari masalahnya adalah bagaimana perusahaan memecahkan menentukan masalah rute armada dan jadwal penerbangan dengan penggunaan jumlah pesawat yang minimum. Rute armada dan jadwal penerbangan adalah aktifitas penting dalam operasi perusahaan penerbangan karena sangat mempengaruhi efisiensi penggunaan pesawat, pembuatan jadwal penerbangan, perawatan pesawat dan penjadwalan awak. Hal tersebut menentukan keuntungan perusahaan, tingkat pelayanan dan kemampuan bersaing di pasar. Proses penjadwalan penerbangan terdiri dari dua tahap yang saling bergantung, 1) tahap pembuatan jadwal dan 2) tahap evaluasi jadwal. Pada tahap pembuatan jadwal dikembangkan konsep jadwal berdasarkan perkiraan permintaan dan penguasaan pasar. Konsep jadwal tersebut diuji selama tahap evaluasi untuk kelayakan operasi, pertimbangan biaya dan performa. Pemeriksaan kelayakan pada tahap evaluasi terutama mencakup hal yang berkaitan dengan rute armada, ukuran armada, jadwal awak dan pengaturan perawatan. Penelitian ini menggunakan teknik jaringan ruang-waktu dalam memformulasikan model untuk masalah rute armada dan jadwal penerbangan. Penyelesaian masalah ini menggunakan software LINGO 8.0 dengan metode Branch and Bound.
RUTE DAN JADWAL PESAWAT UNTUK MEMENUHI PERMINTAAN PENUMPANG : KASUS AIRASIA
Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor
Oleh : AVFITRIYANA G 54102034
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2007
Judul : RUTE DAN JADWAL PESAWAT UNTUK PERMINTAAN PENUMPANG : KASUS AIRASIA Nama : Avfitriyana NRP : G 54102034
MEMENUHI
Menyetujui,
Pembimbing I
Dr. Ir. Amril Aman, Msc. NIP 130 937 092
Pembimbing II
Drs. Prapto Tri Supriyo, M.Kom NIP 131 878 952
Mengetahui, Dekan Fakultas Matematika dan Ilmu pengetahuan Alam Institut Pertanian Bogor
Prof. Dr. Ir. Yonny Koesmaryono, M.S. NIP 131 473 999
Tanggal Lulus :
RIWAYAT HIDUP Penulis dilahirkan di Jakarta pada tanggal 20 April 1984 sebagai anak kedua dari pasangan bapak Amri Sulaiman dan ibu Maniar Idris. Pada tahun 1990 penulis mulai bersekolah di SDN Pasar Manggis 03 Pagi, Jakarta Selatan, dan penulis melanjutkan sekolah ke SLTP 145 Jakarta sampai tahu 1999. Pada tahun 2002 penulis lulus dari SMUN 3 Setiabudi, Jakarta dan berhasil menjadi mahasiswa Departemen Matematika, Fakultas Matematika dan Ilmu pengetahuan Alam, Institut Pertanian Bogor melalui jalur USMI (Undangan Seleksi Masuk IPB). Selama mengikuti kegiatan perkuliahan, penulis pernah menjadi asisten dosen pada mata kuliah Pengantar Matematika (2003), Matematika Dasar (2003), dan Kalkulus 1 (2004). Penulis juga aktif pada kegiatan kemahasiswaan Gumatika (Gugus Mahasiswa Matematika) pada periode 2003/2004.
PRAKATA Assalamualaikum, Wr. Wb., Alhamdulillahi Rabbil Alamin, segala puji dan syukur penulis panjatkan kepada Allah, Rabb semesta alam, yang atas karunia dan kemurahanNya akhirnya penulis dapat menyelesaikan karya ilmiah ini. Tanpa dukungan, bantuan, dan doa dari berbagai pihak, penulis juga tidak dapat menyelesaikan tugas akhir dan perkuliahan di IPB. Penulis ingin mengucapkan terima kasih yang sedalam-dalamnya kepada : 1 Bapak Dr. Ir. Amril Aman, Msc. selaku dosen pembimbing I, terima kasih atas segala bimbingan, pengarahan, saran dan masukan yang diberikan serta bantuan yang tak terbalaskan sehingga pada akhirnya tugas akhir ini dapat terselesaikan. Bapak Drs. Prapto Tri Supriyo, M.Kom. selaku dosen pembimbing II, yang telah sangat mempermudah penyelesaian tugas akhir ini. Bapak Drs. Siswandi, M.Si. selaku dosen penguji luar, tanpa bapak, ujian tidak akan bisa berjalan. 2 Bapak dan Mama yang telah memberikan kasih sayang yang tak terkira, bantuan dan dorongan serta doa yang tak henti sehingga penulis bisa menjalankan tugas sebagai mahasiswa sampai pada tahap akhr ini. 3 Kakakku, Ria, yang selalu menanyakan sampai mana skripsinya, kapan seminar ? Pertanyaan itulah yang membuat aku terus semangat menyelesaikan tugas akhir, walaupun semangat itu sempat hilang. Adikku, Mei, yang cuek tapi perhatian walaupun sedikit. 4 Anakku Ralvien, yang selalu menghibur dikala sedih dengan kelucuanmu dan yang selalu membuatku ingin cepat pulang ke rumah. 5 Irwan yang telah banyak membantu dalam mengerjakan Lingo. Desi, teman suka dan duka dalam mengerjakan tugas akhir ini, terima kasih atas kebersamaan dan semangatnya ketika keputusasaan mulai datang. 6 Dina, Eryt, Ade, Arif, Febi dan Ardi yang telah memberikan warna dalam hidup. Bagiku kalian tetap sahabat terbaik. 7 Temanku angkatan 39 yang telah pergi mencari cita-citanya masing-masing. Terima kasih atas kebersamaan dalam perjalanan selama 4 tahun. 8 Terima kasih untuk Mayang, Tiwi, dan Mita atas kesediaannya menjadi pembahas, terima kasih juga untuk Desi dan Neli atas konsumsinya. 9 Kepada para dosen Departemen Matematika yang telah banyak memberikan ilmunya hingga penulis lulus dari IPB. Juga kepada staf Departemen Matematika, khususnya Ibu Susi yang telah banyak memberikan masukan, bantuan dan nasehatnya. 10 Kepada pihak-pihak yang telah membantu dalam menyelesaikan tugas akhir ini yang tidak dapat disebutkan satu per satu. Semoga karya ilmiah ini dapat bermanfaat bagi yang membacanya, khususnya bagi penulis sendiri. Wassalamualaikum Wr. Wb. Bogor, Februari 2007 Avfitriyana
Untuk Bapak dan Mama tercinta, serta anakku yang kusayangi…
DAFTAR ISI halaman DAFTAR TABEL ......................................................................................................................
ix
DAFTAR GAMBAR ................................................................................................................
ix
DAFTAR LAMPIRAN .............................................................................................................
ix
I PENDAHULUAN .......................................................................................................... 1.1 Latar Belakang .................................................................................................................. 1.2 Tujuan .................................................................................................................................
1 1 1
II 2.1 2.2 2.3 2.4
1 1 3 3 5
LANDASAN TEORI ........................................................................................................ Linear Programming .......................................................................................................... Integer Linear Programming ............................................................................................ Graf .................................................................................................................................... Metode Branch and Bound umtuk Menyelesaikan Masalah Integer Programming ........
III DESKRIPSI DAN FORMULASI MASALAH RUTE DAN JADWAL PESAWAT UNTUK MEMENUHI PERMINTAAN PENUMPANG ....................... 8 3.1 Jaringan Aliran Ruang-Waktu Armada ............................................................................ 8 3.2 Jaringan Aliran Ruang-Waktu Penumpang ....................................................................... 9 3.3 Notasi Simbol .................................................................................................................... 10 3.4 Formulasi Model ............................................................................................................... 11 IV STUDI KASUS MASALAH RUTE DAN JADWAL PESAWAT UNTUK MEMENUHI PERMINTAAN PENUMPANG ............................................................. 12 4.1 Data dari Perusahaan Penerbangan AirAsia ..................................................................... 12 4.2 Penyelesaian Masalah Rute dan Jadwal Pesawat untuk Memenuhi Permintaan Penumpang pada Perusahaan Penerbangan AirAsia ................................................................................ 12 V SIMPULAN DAN SARAN .............................................................................................. 16 5.1 Simpulan ............................................................................................................................. 16 5.2 Saran ................................................................................................................................... 16 DAFTAR PUSTAKA ............................................................................................................... 17 LAMPIRAN .............................................................................................................................. 18
DAFTAR TABEL halaman 1 Data rute dan biaya penerbangan domestik pada perusahaan AirAsia ................................ 13 2 Daftar aktifitas penerbangan AirAsia .................................................................................. 14
DAFTAR GAMBAR halaman 1 2 3 4 5 6 7 8 9 10 11
Graf G = (V, E) ...................................................................................................................... 4 Digraf G ' = (V , A) ................................................................................................................. 4 Sisi berarah menjauhi atau mendekati, suksesor dan predesesor ......................................... 5 Graf berbobot G = (V , A ∪ L ) ............................................................................................. 5 Daerah fisibel untuk LP-relaksasi dari IP(9) ........................................................................ 6 Daerah fisibel untuk subproblem 2 dan subproblem 3 dari IP(9) ........................................ 6 Metode branch and bound dengan subproblem yang tidak dicabangkan lagi .................... 7 Pencabangan keseluruhan pada metode branch and bound ................................................. 8 Jaringan aliran ruang-waktu armada ..................................................................................... 9 Jaringan aliran ruang-waktu penumpang .............................................................................. 10 Jaringan dari armada tipe B737-300 ..................................................................................... 15
DAFTAR LAMPIRAN halaman 1 Contoh penyelesaian suatu LP dengan algoritma simpleks ............................................... 19 2 Program LINGO 8.0 untuk formulasi masalah .................................................................... 21 3 Hasil dari program LINGO 8.0 ............................................................................................ 24
I PENDAHULUAN 1.1 Latar Belakang Manajemen operasi suatu industri penerbangan merupakan suatu permasalahan Operations Research yang kompleks. Secara umum, perusahaan dihadapkan pada berbagai persoalan dalam memenuhi permintaan calon penumpang dan upaya untuk memaksimumkan keuntungan. Misalnya, perusahaan harus memecahkan masalah menentukan rute armada dan jadwal penerbangan. Rute armada dan jadwal penerbangan adalah aktifitas penting dalam operasi perusahaan penerbangan. Keduanya sangat mempengaruhi efisiensi penggunaan pesawat, pembuatan jadwal, perawatan pesawat dan penjadwalan awak. Hal tersebut sangat penting bagi keuntungan perusahaan, tingkat pelayanan dan kemampuan bersaing di pasar. Untuk peningkatan efisiensi penggunaan pesawat, maka dikembangkan kerangka kerja untuk penjadwalan penerbangan dan rute penerbangan yang jumlahnya besar. Kerangka kerja ini tersusun dari beberapa model strategis yang memberi nilai pada rancangan jadwal, jumlah pesawat yang siap, biaya pesawat dan data lain yang digunakan sebagai masukan sehingga tercapai pemecahan untuk keuntungan maksimum. Proses penjadwalan penerbangan terdiri dari dua tahap yang saling bergantung, yaitu tahap pembuatan jadwal dan tahap evaluasi jadwal. Pada tahap pembuatan jadwal dikembangkan konsep jadwal berdasarkan perkiraan permintaan dan penguasaan pasar. Konsep jadwal tersebut diuji selama tahap evaluasi untuk kelayakan operasi, pertimbangan biaya dan performa. Pemeriksaan kelayakan pada tahap evaluasi terutama mencakup hal yang berkaitan dengan rute armada, ukuran armada, jadwal awak dan pengaturan perawatan. Proses penjadwalan penerbangan dilaksanakan dengan dua tahap tersebut sampai diperoleh jadwal yang diharapkan.
Ada beberapa jenis model penjadwalan penerbangan yang dikembangkan, seperti model integer linear programming untuk penerbangan dengan waktu keberangkatan tetap (Abara, 1989), model multikriteria untuk menentukan frekuensi penerbangan di bawah kondisi kompetitif (Teodorovic dan Krcmar-Nozic, 1989), model mixed integer programming untuk rute penerbangan jauh (Balakrishnan et al, 1990), model aliran jaringan multikomoditas untuk memecahkan daily aircraft routing and scheduling problem (DARSP) tanpa diketahui waktu keberangkatan (Hane et al, 1995), model set partitioning type dan model aliran jaringan multikomoditas dengan kendala waktu untuk memecahkan masalah DARSP berdasarkan pada serangkaian penerbangan yang diketahui waktu keberangkatannya (Desaulniers et al, 1997). Lingkup penelitian ini terbatas pada subjek dari rute penerbangan murni operasi jadwal penerbangan dengan OriginDestination (OD) yang diketahui, berbagai jenis pesawat, ukuran armada dan yang berhubungan dengan biaya data. Walaupun proses penjadwalan dalam prakteknya berhubungan erat dengan pemeliharaan pesawat terbang dan proses penjadwalan awak kapal, proses ini umumnya dipisahkan untuk memudahkan pemecahan masalah. Model rute armada dan jadwal penerbangan diformulasikan sebagai integer network flow problem with side constraints (NFPWS) yang dikarakteristikan sebagai masalah NP-Complete (Garey dan Johnson, 1979). Penelitian ini menggunakan teknik jaringan ruang-waktu dalam memformulasikan model untuk masalah rute armada dan jadwal penerbangan. 1.2 Tujuan Tujuan penulisan karya ilmiah ini adalah mempelajari model jaringan terintegrasi untuk membantu perusahaan penerbangan dalam penjadwalan dan rute penerbangan.
II LANDASAN TEORI Untuk membuat model masalah rute armada dan jadwal penerbangan serta mencari solusinya diperlukan beberapa pemahaman teori seperti linear programming, integer linear programming,
graf dan metode branch and bound untuk menyelesaikan masalah integer programming. Berikut ini akan dibahas satu persatu.
2.1 Linear Programming Linear programming (LP) adalah suatu model optimasi dimana fungsi tujuannya mempunyai bentuk linear dan kendalanya memiliki bentuk persamaan atau pertidaksamaan linear. Pada tulisan ini, suatu LP mempunyai bentuk standar seperti yang didefinisikan sebagai berikut : Definisi 1 (Bentuk Standar Suatu LP) Suatu linear programming didefinisikan mempunyai bentuk standar: z = cT x Minimumkan Terhadap Ax = b x≥0 (1) dengan x dan c berupa vektor berukuran n, vektor b berukuran m, sedangkan A berupa matriks berukuran m × n , yang disebut juga sebagai matriks kendala. (Nash & Sofer, 1996) 2.1.1 Solusi suatu Linear Programming Untuk menyelesaikan suatu masalah Linear Programming (LP), metode simpleks merupakan salah satu metode yang dapat menghasilkan solusi optimum. Metode ini mulai dikembangkan oleh Dantzig tahun 1947. Sejak perkembangannya, metode ini adalah metode yang paling umum digunakan untuk menyelesaikan LP, yaitu berupa metode iteratif untuk menyelesaikan masalah LP dalam bentuk standar. Pada linear programming (1), vektor x yang memenuhi kendala Ax = b disebut sebagai solusi LP (1). Misalkan matriks A dapat dinyatakan sebagai A = (B N), dengan B adalah matriks berukuran m × m yang merupakan matriks yang elemennya berupa koefisien variabel basis dan N merupakan matriks yang elemennya berupa koefisien variabel nonbasis pada matriks kendala. Matriks B disebut matriks basis untuk LP. Berikut definisi matriks basis: Definisi 2 (Matriks Basis) Matriks B disebut matriks basis untuk LP (1) jika B adalah matriks tak singular, yaitu matriks yang determinannya tidak sama dengan nol. (Garfinkel & Nemhausher, 1972) Misalkan x dapat dinyatakan sebagai ⎛ xB ⎞ vektor x = ⎜⎜ ⎟⎟ , dengan xB adalah vektor ⎝ xN ⎠ variabel basis dan xN adalah vektor variabel
nonbasis. Maka sebagai ⎛x Ax = (B N ) ⎜⎜ B ⎝ xN
Ax = b dapat dinyatakan
⎞ ⎟⎟ ⎠ = Bx B + Nx N = b (2) karena B adalah matriks taksingular, maka B memiliki invers, sehingga dari (2) xB dapat dinyatakan sebagai : xB = B-1b - B-1 NxN (3)
Definisi 3 ( Solusi Basis ) Solusi dari suatu linear programming disebut solusi basis jika memenuhi : xB = B-1b, xN = 0 (4) (Garfinkel & Nemhausher, 1972) Definisi 4 (Solusi Fisibel Basis) x disebut solusi fisibel basis jika x merupakan solusi basis dan x ≥ 0 (Nash & Sofer, 1996) Ilustrasi solusi basis dan solusi fisibel basis dapat dilihat dalam contoh berikut: Contoh 1 Misalkan diberikan linear programming berikut : Minimumkan z = −2 x1 − 3x 2 −2 x1 + x 2 + x 3 = 4 terhadap − x1 + 2 x 2 + x 4 = 11 x1 + x 5 = 5 (5) x1 , x 2 , x 3 , x 4 , x 5 ≥ 0 Dari linear programming tersebut didapatkan : 1 0 0 ⎞ ⎛− 2 1 ⎛4⎞ ⎟ ⎜ ⎜ ⎟ A = ⎜ −1 2 0 1 0 ⎟ , b = ⎜11⎟ ⎜ 1 ⎜5⎟ 0 0 0 1 ⎟⎠ ⎝ ⎝ ⎠
Misalkan dipilih
x B = (x 3 x 4 x 5 )T dan maka matriks basis ⎛1 0 ⎜ B = ⎜0 1 ⎜0 0 ⎝
x N = (x1
x 2 )T
0⎞ ⎟ 0⎟ 1 ⎟⎠
Dengan menggunakan matriks basis tersebut, diperoleh
x B = B −1b = (4 11 5)T , x N = (0 0 )T (6) Solusi (6) merupakan solusi basis, karena solusi tersebut memenuhi kendala pada LP (5) dan kolom-kolom pada matriks kendala yang berkorespondensi dengan komponen taknol dari (6) yaitu B adalah bebas linear (kolom yang satu bukan merupakan kelipatan
dari kolom yang lain). Solusi (6) juga merupakan solusi fisibel basis, karena nilainilai variabelnya lebih dari atau sama dengan nol. ■ LP (1) dapat dinyatakan dalam xB dan xN sebagai berikut: z = cB xB + c N xN Bx B + Nx N = b x≥0 dengan c B adalah koefisien variabel basis T
Minimumkan Terhadap
pada fungsi objektif, c N
T
adalah koefisien
variabel nonbasis pada fungsi objektif. Jika persamaan (3) disubstitusikan ke persamaan Z maka akan didapat : z = cB
T
(B
)
z = cB
T
B −1b + c N T − c B T B −1 N x N
−1
b − B −1 Nx n + c N T x N
(
)
Jika didefinisikan
(
)
T
y = c B T B −1 = B −T c B maka z dapat dinyatakan dalam y :
(
Jika cˆ N T < 0 , pilih variabel xt yang memenuhi cˆt < 0 sebagai entering variable yaitu variabel xt yang akan masuk ke dalam basis. •
Langkah tertentu (t) Hitung Aˆ t = B −1 At , yaitu koefisien kendala yang berhubungan dengan entering variable ke t. Tentukan indeks s pada kolom kendala yang berhubungan dengan entering variable yang memenuhi min ⎧⎪ bˆi bˆs ⎫ (8) = : aˆ i ,t > 0 ⎬ . ⎨ aˆ s ,t 1 ≤ i ≤ m ⎪⎩ aˆ i ,t ⎭ Memilih indeks dengan cara tersebut disebut dengan minimum ratio test. Variabel yang menjadi leaving variable (variabel yang akan keluar dari basis, tergantikan oleh entering variable) dan pivot entry adalah variabel yang berhubungan dengan aˆ s ,t .
Jika aˆ i ,t ≤ 0 , (1 ≤ i ≤ m) , untuk semua i,
)
z = y b + cN − y N xN (7) Vektor y disebut vektor simplex multiplier. Untuk suatu solusi basis x N = 0 dan x = bˆ = B −1b , maka zˆ = c T B −1b .
maka masalah LP disebut unbounded. • Pivot Update matriks basis B dan vektor basis xB. Kembali ke tes keoptimalan.
Notasi zˆ adalah notasi untuk z optimal. Koefisien cˆ j disebut reduced cost dari xj
Berikut contoh penggunaan algoritma simpleks :
T
T
T
B
B
dengan
(
cˆ j
adalah elemen dari vektor
)
cˆ N T = c N T − c B T B −1b . Reduced cost adalah penambahan nilai fungsi objektif jika suatu variabel nonbasis dijadikan variabel basis (artinya menjadi solusi taknol) pada suatu linear programming. Maka z dapat dinyatakan sebagai z = zˆ + cˆ N T x N .
Contoh 2 Misalkan diberikan linear programming (5) seperti pada Contoh 1, maka dengan menggunakan algoritma simpleks akan diperoleh solusi : x1 = 5, x 2 = 8, x 3 = 6, x 4 = x 5 = 0 dengan z = −34 (lihat Lampiran 1).
2.1.2 Penyelesaian Linear Programming dengan algoritma simpleks Solusi suatu linear programming dapat diketahui optimal atau tidak untuk LP tersebut melalui algoritma sebagai berikut:
2.2 Integer Linear Programming Model Integer Linear Programming (ILP) atau disebut juga Integer Programming (IP), adalah suatu model linear programming dengan variabel yang digunakan berupa bilangan bulat (integer). Jika semua variabel harus berupa integer, maka masalah tersebut disebut pure integer programming. Jika hanya sebagian yang harus integer, maka disebut mixed integer programming. IP dengan semua variabelnya harus bernilai 0 atau 1 disebut 0-1 IP.
•
Tes Keoptimalan
Vektor y = c B T B −1 dihitung, kemudian dapat dihitung pula nilai reduced cost cˆ N T = c N T − y T b .
(
)
Jika cˆ N ≥ 0 maka solusi diperoleh adalah solusi optimal. T
yang
Definisi 5 (Linear Programming Relaksasi) LP-relaksasi dari suatu IP merupakan linear programming yang diperoleh dari IP
tersebut dengan menghilangkan kendala integer atau kendala 0-1 pada variabelnya. (Winston, 1995) 2.3 Graf Definisi 6 (Graf) Suatu graf adalah pasangan terurut (V,E), dengan V himpunan takkosong dan hingga dan E adalah himpunan pasangan takterurut yang menghubungkan elemen-elemen V dan dinotasikan dengan G = (V , E ) . Elemen V dinamakan simpul (vertex/node), dan elemen E dinamakan sisi (edge), dinotasikan sebagai {i, j} , yaitu sisi yang menghubungkan simpul i dengan simpul j, dengan i, j ∈ V . (Foulds, 1992)
Ilustrasi graf dapat dilihat pada Contoh 3 berikut: Contoh 3 G: v1
v5
Contoh 4 G’ : v1
v5 v4
v2
v3
Gambar 2. Digraf G ' = (V , A) . Pada Gambar 2, digraf G’ memiliki V = {v1 , v 2 , v 3 , v 4 , v 5 } dan A = {(v1 , v 2 ), (v1 , v 5 ), (v 2 , v 3 ), (v 2 , v 5 ), (v 3 , v 4 ), (v 3 , v 5 ), (v 4 , v 5 )} . Definisi 8 (Walk) Suatu walk pada graf G = (V , E ) adalah suatu barisan simpul dan sisi dari G dengan bentuk v1 , {v1 , v 2 }, v 2 , {v 2 , v3 },..., {v n −1 , v n }, v n , atau
ditulis dengan ringkas : v4
v2
v3
Gambar 1. Graf G = (V, E). Pada Gambar 1, V = {v1 , v 2 , v 3 , v 4 , v 5 } dan E = {{v1 , v 2 }, {v1 , v 5 }, {v 2 , v 3 }, {v 2 , v 5 }, {v 3 , v 4 }
{v3 , v5 }, {v 4 , v5 }} . Definisi 7 (Digraf) Digraf (directed graf/graf berarah) adalah pasangan terurut (V, A) dengan V adalah himpunan takkosong dan hingga, dan A adalah himpunan pasangan terurut dari elemen-elemen di V. Elemen dari A disebut sisi berarah (arc) dan dituliskan sebagai (i, j ) dengan i, j ∈ V . (Foulds, 1992)
Ilustrasi digraf dapat dapat dilihat pada Contoh 4 berikut :
v1 , v 2 ,..., v n atau
v1 , v 2 ,..., v n . Walk tersebut menghubungkan simpul v1 dengan v n . (Foulds, 1992)
Definisi 9 (Path) Path pada suatu graf G adalah suatu walk dengan semua simpulnya berbeda. (Foulds, 1992) Berikut diberikan ilustrasi dari walk dan path. Pada graf G yang terdapat pada Gambar 1 salah satu contoh walk adalah v1 , v 2 , v 5 , v 4 , v 3 . Sedangkan v1 , v 2 , v 5 , v 4 adalah salah satu contoh path.
Definisi 10 (Cycle) Suatu cycle pada graf G = (V , E ) atau digraf G ' = (V , A) adalah suatu path yang dimulai dan diakhiri oleh simpul yang sama dan terdiri atas sedikitnya tiga simpul yang berbeda pada graf G = (V , E ) atau dua simpul yang berbeda pada digraf G ' = (V , A) . Cycle disebut juga path tertutup. (Foulds, 1992)
Definisi 11 (Sisi Berarah Menjauhi atau Mendekati, Suksesor dan Predesesor) Misalkan diberikan digraf D = (V , A) . Jika a = vi , v j ∈ A maka sisi berarah ini
(
)
dikatakan menjauhi vi dan mendekati v j . Simpul vi disebut predesesor bagi simpul v j , simpul v j disebut suksesor bagi simpul vi .
(Foulds, 1992) Definisi tersebut dapat digambarkan dalam digraf seperti berikut : vj
vi
Gambar 3. Sisi berarah menjauhi atau mendekati, suksesor, dan predesesor.
Definisi 12 (Graf Berbobot) Suatu graf G = (V , E ) atau digraf D = (V , A) dikatakan berbobot jika terdapat fungsi w : E → ℜ atau ϑ : A → ℜ (dengan ℜ himpunan bilangan real) yang memberikan bobot pada setiap elemen E atau A. (Foulds, 1992) Ilustrasi graf berbobot dapat dilihat pada Contoh 5 berikut:
Contoh 5 Misalkan diberikan w : A → ℜ untuk graf berbobot G = (V , A ∪ L ) pada Gambar 4, maka w((v4,v5)) atau secara ringkas ditulis wv5v4 = −1, wv1v5 = wv3v4 = 2, wv1v2 = wv2v3 = 0, wv5v3 = 3.
G: v1
v5
2
0
-1 v4
3 2 v2
0
v3
Gambar 4. Graf berbobot G = (V , A ∪ L ) . Terdapat kasus khusus dari graf berbobot yaitu network. Beberapa konsep dalam network :
Definisi 13 (Source) Source adalah suatu simpul dengan tidak ada sisi berarah yang mendekati simpul tersebut. (Foulds, 1992) Definisi 14 (Sink) Sink adalah suatu simpul sehingga tidak ada sisi berarah yang menjauhi simpul tersebut. (Foulds, 1992) Definisi 15 (Network) Network adalah suatu digraf yang mempunyai tepat satu source dan satu sink. (Foulds, 1992) 2.4 Metode Branch and Bound umtuk menyelesaikan masalah Integer Programming Dalam penulisan karya ilmiah ini, untuk memperoleh solusi optimal dari masalah IP digunakan software Lingo 8.0 yaitu sebuah program yang didesain untuk membangun dan menentukan solusi model linear, nonlinear dan optimisasi integer menjadi lebih cepat, mudah dan lebih efisien dengan prinsip pemecahannya berdasarkan metode branch and bound. Prinsip dasar metode branch and bound adalah memecah daerah fisibel dari masalah LP-relaksasi dengan membuat subproblemsubproblem. Daerah fisibel linear programming adalah daerah yang memenuhi semua kendala linear programming. • Branch Membuat partisi daerah solusi kedalam subproblem. Tujuannya untuk menghapus daerah solusi yang tidak fisibel. Hal ini dicapai dengan menentukan kendala yang penting untuk menghasilkan solusi IP, secara tidak langsung titik integer yang tidak fisibel terhapus. Dengan kata lain, hasil pengumpulan dari subproblem-subproblem yang lengkap menunjukkan setiap titik integer yang fisibel dari masalah asli. Karena sifat alami partisi itu, maka dinamakan Branching. ● Bound Asumsikan masalahnya merupakan tipe maksimisasi, nilai objektif yang optimal untuk setiap subproblem dibuat dengan membatasi percabangan dengan batas atas dari nilai objektif yang dihubungkan dengan sembarang nilai integer yang fisibel. Hal ini sangat penting untuk mengatur dan menempatkan solusi optimum. Operasi ini yang menjadi alasan dinamakan Bounding. (Taha, 1975)
Metode branch and bound (pencabangan dan pembatasan) dimulai dengan menyelesaikan LP-relaksasi dari integer programmingnya. Jika sudah diperoleh semua variabel keputusan solusi optimal integer, maka solusi tersebut juga merupakan solusi optimal IP. Jika tidak, maka akan dilakukan pencabangan dan penambahan batasan pada LP-relaksasinya, kemudian diselesaikan.
Contoh 6 Misalkan diberikan integer programming berikut : Maksimumkan z = 8 x1 + 5 x 2 terhadap x1 + x 2 ≤ 6 9 x1 + 5 x 2 ≤ 45 x1 , x 2 ≥ 0 x1 , x 2 integer (9)
x2
9 8 7 6 5 4 3 2 1 0
1
2
3
4
5
6
x1
Gambar 5. Daerah fisibel untuk LP-relaksasi dari IP(9). Ket : ● = solusi fisibel untuk IP ■ = solusi optimal untuk LP-relaksasi Solusi optimal LP-relaksasinya adalah x1 = 3,75 , x 2 = 2,25 dengan z = 41,25 . Karena nilai optimal untuk IP ≤ nilai optimal untuk LP-relaksasi (masalah maksimisasi), maka nilai optimal LP-relaksasi merupakan batas atas untuk nilai optimal IP.
x2 9 8 7 6 5 4 3 2 1 0
1
2
3
4
5
6
x1
Gambar 6. Daerah fisibel untuk subproblem 2 dan subproblem 3 dari IP(9). Langkah berikutnya adalah mempartisi daerah fisibel LP-relaksasi (lihat Gambar 6) menjadi dua bagian berdasarkan pada variabel yang masih dalam bentuk pecahan. Karena dua variabel diatas bukan integer, maka dipilih salah satu variabel untuk dasar pencabangan. Misalkan disini dipilih x1 . Jika masalah LP-relaksasi diberi nama Subproblem 1, maka pencabangan tersebut menghasilkan dua subproblem, yaitu : • Subproblem 2 : Subproblem 1 ditambah kendala x1 ≥ 4 . • Subproblem 3 : Subproblem 1 ditambah kendala x1 ≤ 3 . Dari gambar 6 terlihat bahwa setiap titik (solusi) fisibel dari IP (9) termuat dalam daerah fisibel subproblem 2 atau subproblem 3. Juga setiap subproblem ini saling lepas. Subproblem 2 dan subproblem 3 ini dikatakan dicabangkan atas x1 . Sekarang dipilih subproblem yang belum diselesaikan. Misalkan dipilih subproblem 2, kemudian diselesaikan dengan menggunakan metode simpleks, sehingga diperoleh solusi optimal untuk subproblem 2 ini adalah x1 = 4 , x 2 = 1,8 dengan z = 41 . Karena solusi optimal subproblem 2 bukan solusi integer, maka pilih pencabangan pada subproblem 2 atas x 2 , sehingga diperoleh dua subproblem lagi. • Subproblem 4 : Subproblem 2 ditambah kendala x 2 ≥ 2 .
• Subproblem 5 : subproblem 2 ditambah kendala x 2 ≤ 1 . Sekarang, subproblem yang belum diselesaikan adalah subproblem 3, 4 dan 5. Pilih salah satu subproblem, misalnya dengan aturan LIFO (Last In First Out). Dengan aturan ini berarti pilih subproblem 4 atau subproblem 5. Karena subproblem 4 takfisibel, maka subproblem 4 tidak dapat menghasilkan solusi optimal. Tinggal subproblem 3 dan 5. Aturan LIFO membuat kita memilih subproblem 5 kemudian diperoleh solusi optimalnya x1 = 4,44 , x 2 = 1 dengan z = 40,556 . Demikian seterusnya, sehingga dilakukan x1 , sehingga pencabangan lagi atas diperoleh: • Subproblem 6 : Subproblem 5 ditambah kendala x1 ≥ 5 . • Subproblem 7 : Subproblem 5 ditambah kendala x1 ≤ 4 . Misalkan dipilih subproblem 7 dan kemudian diselesaikan sehingga diperoleh solusi optimal x1 = 4 , x 2 = 1 dengan z = 37 . Karena solusi ini sudah berupa integer, maka solusi ini merupakan calon solusi (candidate solution) untuk solusi optimal IP (9). Dengan demikian nilai optimal subproblem 7 (yaitu 37) merupakan batas bawah dari nilai optimal IP (9) dan diberi notasi LB = 37.
Subproblem yang belum diselesaikan tinggal subproblem 6 dan 3, sehingga dengan aturan LIFO dipilih subproblem 6 dengan solusi optimalnya x1 = 5 , x 2 = 0 dengan z = 40 . Ini juga merupakan candidate solution untuk IP (9) dan nilai batas bawah (LB) berubah menjadi LB = 40. Tinggal subproblem 3 yang harus diselesaikan dan diperoleh solusi optimalnya adalah x1 = x 2 = 3 dengan z = 39 . Karena subproblem 3 tidak dapat menghasilkan nilai optimal yang lebih baik dari LB = 40, maka subproblem 3 tidak dicabangkan lagi (fathomed) dan disini diberi tanda × (perhatikan Gambar 7). Demikian dilakukan dengan cara serupa sehingga diperoleh pencabangan keseluruhan yang diperlihatkan pada gambar 8. Dengan cara ini diperoleh solusi optimal untuk IP (9) adalah x1 = 5 , x 2 = 0 dengan z = 40 . Perlu diperhatikan bahwa situasi dimana subproblem dihentikan pencabangannya (fathomed) antara lain adalah : subproblemnya takfisibel (seperti subproblem 4 pada IP (9)), subproblem tersebut menghasilkan solusi optimal dengan semua variabelnya integer, atau nilai optimal subproblem tersebut tidak lebih bagus dari batas bawah (untuk masalah maksimisasi) atau batas atasnya (untuk masalah minimisasi).
________________________________________________________ t=1
SUBPROBLEM 1 x1 = 3,75 , x 2 = 2,25 , z = 41,25
x1 ≥ 4
SUBPROBLEM 2 x1 = 4 , x 2 = 1,8 , z = 41
t=2
SUBPROBLEM 4 TAK FISIBEL
SUBPROBLEM 3
x2 ≤ 1
x2 ≥ 2
t=3
x1 ≤ 3
×
SUBPROBLEM 5
Gambar 7. Metode branch and bound dengan subproblem yang tidak dicabangkan lagi.
SUBPROBLEM 1 x1 = 3,75 , x 2 = 2,25 , z = 41,25
t=1 x1 ≥ 4
t=2
SUBPROBLEM 2 x1 = 4 , x 2 = 1,8 , z = 41
t=7
SUBPROBLEM 4 TAK FISIBEL
×
×
SUBPROBLEM 5 x1 = 4,44 , x 2 = 1 , z = 40,556
x1 ≥ 5
t=6
SUBPROBLEM 3 x1 = x 2 = 3 , z = 39 , LB = 40
x2 ≤ 1
x2 ≥ 2
t=3
x1 ≤ 3
SUBPROBLEM 6 x1 = 5 , x 2 = 0 , z = 40 candidate solution
x1 ≤ 4
t=5
SUBPROBLEM 7 x1 = 4 , x 2 = 1 , z = 37 candidate solution
×
Gambar 8. Pencabangan keseluruhan pada metode branch and bound. _____________________________________________________________________
III DESKRIPSI DAN FORMULASI MASALAH RUTE DAN JADWAL PESAWAT UNTUK MEMENUHI PERMINTAAN PENUMPANG Teknik jaringan ruang-waktu (time-space network) digunakan untuk membuat model penjadwalan dan rute penerbangan dengan tujuan memaksimumkan keuntungan perusahaan penerbangan. Model ini membangun manajemen optimal dari pesawat dan pergerakan penumpang dalam jaringan dari penerbangan langsung dan berbagai penerbangan. Teknik jaringan ini dibagi menjadi dua, yaitu jaringan aliran ruangwaktu armada dan jaringan aliran ruangwaktu penumpang. Berikut ini adalah penjelasannya. 3.1 Jaringan Aliran Ruang-Waktu Armada (The fleet-flowtime-space network) Jaringan aliran ruang-waktu armada digunakan untuk memformulasikan masalah berbagai rute penerbangan dan jadwal penerbangan. Tiap jaringan (network) menunjukkan satu tipe khusus pergerakan potensial dengan periode waktu dan lokasi airport tertentu, ditunjukkan pada Gambar 9. Sumbu horizontal menunjukkan lokasi airport; sumbu vertikal menunjukkan durasi waktu. Node dan arc adalah dua komponen
penting pada jaringan. Suatu node menunjukkan suatu airport pada waktu tertentu, sedangkan arc menunjukkan aktivitas, seperti penerbangan, landasan, atau tinggal semalaman (overnight stay). Aliran arc menunjukkan aliran pesawat pada jaringan. Tiga jenis arc dijelaskan sebagai berikut. 3.1.1 Flight leg arc Flight leg arc menunjukkan suatu penerbangan antara dua airport yang berbeda. Sebagai contoh yaitu pada Gambar 9, flight leg arc ditunjukkan oleh nomor 1. Salah satu contohnya adalah ada penerbangan dari airport 1 pada pukul 01:00 sampai ke airport 2 pada pukul 02:00. Biaya penerbangan adalah biaya arc pada jaringan. Upperbound dari aliran arc adalah satu, artinya bahwa penerbangan dapat dilayani paling banyak sekali. Lowerbound dari aliran arc adalah nol, menunjukkan bahwa tidak ada pesawat yang melayani penerbangan.
3.1.2 Ground arc 3.1.3 Cycle arc Suatu ground arc menggambarkan Sebuah cycle arc berfungsi untuk lamanya pesawat tinggal di airport dalam menunjukkan kontinuitas antara dua periode (jangka waktu) perencanaan berurut. time window. Time window adalah jangka Menghubungkan akhir periode pertama waktu yang telah ditentukan atau disebut juga dengan awal periode kedua untuk masingdengan kendala waktu. Sebagai contoh yaitu masing airport. Sebagai contoh yaitu pada pada Gambar 9, ground arc ditunjukkan oleh nomor 2. Salah satu contohnya adalah ada Gambar 9, cycle arc ditunjukkan oleh nomor 3. Salah satu contohnya adalah ada pesawat pesawat yang tinggal di airport 2 dari pukul yang tinggal di airport 1 dari pukul 24:00 02:00 sampai pukul 03:00. Pukul 02:00 sampai pukul 03:00 disebut dengan time pada hari pertama sampai pukul 00:00 pada hari berikutnya. Pukul 24:00 pada hari window. Biaya arc merupakan biaya yang pertama disebut akhir periode pertama. terjadi untuk menempatkan satu pesawat di Sedangkan pukul 00:00 pada hari berikutnya airport dalam time window. Upperbound dari disebut awal periode kedua. Aliran arc aliran arc adalah kapasitas yang sesuai (atau tanpa batas, jika kapasitas besar), upperbound dan lowerbound dari aliran arc menunjukkan jumlah maksimum pesawat seperti halnya biaya arc adalah sama pada yang dapat ditampung di airport selama time ground arc. window. Lowerbound dari aliran arc adalah nol, menunjukkan bahwa tidak ada pesawat yang ditampung di airport pada time window. _____________________________________________________________________
Gambar 9. Jaringan aliran ruang-waktu armada.
3.2
Jaringan Aliran Ruang-Waktu Penumpang (The passenger-flow time-space network) Teknik jaringan ruang-waktu juga digunakan untuk menunjukkan pergerakan penumpang terhadap waktu dan lokasi tertentu, sebagaimana ditunjukkan pada Gambar 10. Masing-masing jaringan menunjukkan pasangan OD spesifik dari tabel asal-tujuan (dikenal dengan tabel OD). Sumbu horizontal dan vertikal adalah sama dengan sumbu pada jaringan aliran ruangwaktu armada. Suatu node disini juga menunjukkan suatu airport pada waktu tertentu. Suatu arc menunjukkan suatu aktivitas pergerakan penumpang. Secara keseluruhan, ada tiga tipe arc dijelaskan berikut ini.
3.2.2 Holding arc Suatu holding arc menunjukkan bahwa penumpang tinggal di airport pada time window. Sebagai contoh yaitu pada Gambar 10, holding arc ditunjukkan oleh nomor 2. Salah satu contohnya adalah ada penumpang yang tinggal di airport 2 dari pukul 02:00 sampai pukul 03:00. Biaya menunggu (atau penalti) adalah biaya arc untuk time window. Upperbound dari aliran arc adalah kapasitas stasiun pelayanan penumpang dengan jaringan interval waktu minimum, menunjukkan bahwa jumlah maksimum penumpang dapat ditampung pada airport ini selama time window. Lowerbound dari aliran arc adalah nol, menunjukkan tidak ada penumpang dari OD bersangkutan tinggal di airport selama time window.
3.2.3 Demand arc 3.2.1 Delivery arc Suatu demand arc menghubungkan stasiun keberangkatan dan stasiun kedatangan Suatu delivery arc menunjukkan dari pasangan OD bersangkutan. Sebagai penumpang yang diberangkatkan dari satu contoh yaitu pada Gambar 10, demand arc airport ke airport lainnya pada suatu penerbangan. Sebagai contoh yaitu pada ditunjukkan oleh nomor 3. Salah satu Gambar 10, delivery arc ditunjukkan oleh contohnya adalah ada penumpang yang nomor 1. Salah satu contohnya adalah ada diberangkatkan dari airport 2 pada pukul penumpang yang diberangkatkan dari airport 06:00 pada hari pertama sampai ke airport 1 3 pada pukul 00:00 sampai ke airport k pada pada pukul 00:00 pada hari berikutnya.. pukul 02:00. Biaya arc adalah biaya variabel Demand arc merupakan permintaan untuk melayani penumpang (misalnya biaya pelayanan untuk pasangan OD yang akan catering). Upperbound dari aliran arc adalah secara nyata dilayani pada jaringan. Biaya kapasitas pesawat (khususnya jenis paling arc adalah nilai dari harga rata-rata tiket. Upperbound dari aliran arc adalah besar), artinya bahwa aliran maksimum permintaan yang sudah diperhitungkan untuk dalam arc adalah kapasitas muatan pesawat. Lowerbound dari aliran arc adalah nol, pasangan OD. Lowerbound dari aliran arc artinya bahwa tidak ada penumpang dari OD adalah nol, artinya bahwa tidak ada pasangan yang berhubungan diantarkan pada OD penumpang dilayani pada jaringan. penerbangan. _____________________________________________________________________
Gambar 10. Jaringan aliran ruang-waktu penumpang. ______________________________________________________________________ 3.3 Notasi Simbol Notasi simbol yang digunakan dalam formulasi model adalah sebagai berikut : X ij : Aliran arc (i,j) dalam jaringan armada Yij : Aliran
arc
(i,j)
dalam
Biaya
arc
(i,j)
dalam
jaringan
penumpang NF : Himpunan semua node dalam jaringan armada NP : Himpunan semua node dalam jaringan penumpang K : Kapasitas pesawat dalam jaringan armada U ij : Upperbound dari aliran arc (i,j) dalam jaringan armada
dalam jaringan penumpang AF : Jumlah pesawat yang tersedia dalam jaringan armada
jaringan
penumpang C ij : Biaya arc (i,j) dalam jaringan armada Tij :
Vij : Upperbound dari aliran arc (i,j)
3.4 Formulasi Model Berdasarkan jaringan aliran ruang-waktu armada dan penumpang yang dijelaskan di atas, formulasi modelnya sebagai masalah aliran jaringan integer. Ada beberapa persoalan yang perlu dipertimbangkan secara hati-hati, yaitu : 1. Jumlah pesawat yang diperlukan dalam jaringan seharusnya tidak melebihi jumlah pesawat yang bisa dipakai untuk masing-masing armada. 2. Masing-masing penerbangan dapat dilayani paling banyak sekali dalam jaringan aliran armada.
3.
Jumlah penumpang yang diangkut seharusnya tidak pernah melebihi kapasitas pesawat. Oleh karena itu, tiga jenis kendala dibuat berhubungan dengan formulasi masalah, yaitu : 1. Jumlah siklus aliran arc pada masingmasing jaringan aliran armada tidak akan lebih besar daripada jumlah pesawat yang tersedia. 2. Jumlah seluruh aliran arc berhubungan dengan penerbangan yang sama seharusnya sama dengan satu atau nol. 3. Jumlah seluruh aliran delivery arc berhubungan dengan penerbangan yang sama tidak seharusnya melebihi jumlah masing-masing aliran arc penerbangan dikalikan dengan kapasitas pesawat. Tujuan model ini adalah maksimalisasi profit sehingga model diformulasikan sebagai berikut. Maksimalkan Z = ∑ Tij Yij − ∑ C ij X ij ij∈NP
ij∈NF
3. jumlah pesawat yang digunakan pada jaringan armada seharusnya tidak melebihi jumlah pesawat yang tersedia ∑ X ij ≤ AF ij∈NF
4. masing-masing penerbangan paling banyak sekali X ij ≤ 1, ∀ij ∈ NF
dilakukan
5. banyaknya pengangkutan penumpang tidak melebihi kapasitas pesawat Yij ≤ KX ij , ∀ij ∈ NF 6. jika ada penerbangan ke suatu airport, maka harus ada pesawat yang tinggal di airport tersebut X ij − X jk = 0, ∀ij ∈ NF , ∀ij ∈ NF 7. menjaga semua aliran arc armada dengan batasannya 0 ≤ X ij ≤ U ij , ∀ij ∈ NF 8. menjaga semua aliran arc penumpang dengan batasannya 0 ≤ Yij ≤ Vij , ∀ij ∈ NP
terhadap 1. banyaknya pesawat yang pergi sama dengan banyaknya pesawat yang datang ∑ X ij − ∑ X ki = 0, ∀i ∈ NF
9. semua aliran arc armada merupakan integer X ij ∈ integer, ∀ij ∈ NF
2. banyaknya penumpang yang pergi sama dengan banyaknya penumpang yang datang ∑ Yij − ∑ Yki = 0, ∀i ∈ NP
10. semua aliran arc penumpang merupakan integer Yij ∈ integer, ∀ij ∈ NP
ij∈NF
ij∈NP
ki∈NF
ki∈NP
________________________________________________________
IV STUDI KASUS MASALAH RUTE DAN JADWAL PESAWAT UNTUK MEMENUHI PERMINTAAN PENUMPANG 4.1 Data dari Perusahaan Penerbangan AirAsia Studi kasus yang dilakukan penulis untuk karya ilmiah ini yaitu pada perusahaan penerbangan AirAsia, yang datanya diperoleh pada tanggal 7 Agustus 2006. Penerbangan yang dibahas hanya meliputi operasi domestik dengan melayani tujuh kota di Indonesia. Tujuh kota tersebut antara lain adalah Jakarta (CGK), Surabaya (SUB), Medan (MES), Padang (PDG), Batam (BTH), Denpasar (DPS) dan Balikpapan (BPN). Perusahaan penerbangan AirAsia hanya menggunakan satu armada untuk rute penerbangan domestik, yaitu armada Boeing 737-300 dengan kapasitas 148 penumpang dan memiliki persediaan 26 pesawat. Lamanya pesawat tinggal di airport setelah melakukan penerbangan minimal 25 menit. Jadwal penerbangan, waktu keberangkatan dan kedatangan serta biaya diberikan pada Tabel 1. Perusahaan penerbangan ini dihadapkan pada masalah bagaimana menentukan rute armada dari jadwal penerbangan yang tersedia dengan menggunakan jumlah pesawat yang minimum. Hal ini bertujuan agar perusahaan menghasilkan keuntungan yang maksimum. Asumsi yang digunakan dalam permasalahan ini adalah : 1. Biaya flight leg arc dikonversi dari block hours, yaitu lamanya waktu penerbangan, bahwa biaya satu jam block hours sama dengan dua juta rupiah.
2. Biaya ground arc dan cycle arc adalah dua ratus ribu rupiah. 3. Semakin lama waktu penerbangan, maka biaya delivery arc (biaya catering) semakin mahal. 4.2 Penyelesaian Masalah Rute dan Jadwal Pesawat untuk Memenuhi Permintaan Penumpang pada Perusahaan Penerbangan AirAsia Penyelesaian masalah ini dipecahkan dengan menggunakan program LINGO 8.0 yaitu suatu software linear progamming yang dapat memecahkan suatu model optimisasi dengan cepat dan efisien. Dari perhitungan pada LINGO 8.0 diperoleh hasil, yaitu terdapat 40 flight leg arc, 33 ground arc, 7 cycle arc, 40 delivery arc (setiap delivery arc ada 148 penumpang) dan 40 demand arc serta fungsi objektifnya adalah 527080 (dalam ribuan). Program dan hasil dapat dilihat pada Lampiran 3 dan 4. Hal ini berarti perusahaan penerbangan AirAsia akan memperoleh keuntungan yang maksimum sebesar 527.080.000 rupiah jika semua demand dipenuhi. Hasil perhitungan pada LINGO 8.0 dituliskan dalam bentuk tabel (lihat Tabel 2) dan gambar jaringan (lihat Gambar 11). Dari Gambar 11 terlihat bahwa jumlah optimal pesawat yang digunakan sebanyak tujuh untuk memenuhi sejumlah jadwal penerbangan.
No.
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40.
Origin Destination (OD) CGK-SUB CGK-SUB CGK-SUB CGK-SUB CGK-SUB CGK-MES CGK-MES CGK-MES CGK-MES CGK-MES CGK-PDG CGK-PDG CGK-PDG CGK-BTH CGK-BTH CGK-BTH CGK-DPS CGK-DPS CGK-DPS CGK-BPN SUB-CGK SUB-CGK SUB-CGK SUB-CGK SUB-CGK MES-CGK MES-CGK MES-CGK MES-CGK MES-CGK PDG-CGK PDG-CGK PDG-CGK BTH-CGK BTH-CGK BTH-CGK DPS-CGK DPS-CGK DPS-CGK BPN-CGK
Waktu
Harga Tiket (dalam ribuan)
Biaya Catering (dalam ribuan)
06:50 - 08:10 11:15 – 12:35 15:25 – 16:45 19:30 – 20;50 20:35 – 21:55 06:00 – 08:15 10:45 – 13:00 14:40 – 16:55 16:25 – 18:40 18:50 – 21:05 06:35 – 08:15 11:30 – 13:10 15:40- 17:20 07:15 – 08:50 11:25 – 13:00 15:30 – 17:05 11:15 – 14:00 16:10 – 18:55 19:50 – 22:35 06:40 – 09:40 13:00 – 14:15 14:45 – 16:00 17:10 – 18:25 21:15 – 22:30 22:20 – 23:35 08:40 – 11:00 13:25 – 15:45 19:05 – 21:25 20:10 – 22:30 21:30 – 23:50 08:40 – 10:20 13:35 – 15:15 17:45 – 19:25 09:15 – 10:50 13:25 – 15:50 17:30 – 19:05 14:25 – 15:05 19:20 – 20:00 23:00 – 23:40 10:05 – 11:05
229 129 219 219 179 329 329 329 329 299 199 199 149 329 249 249 415 315 299 325 179 219 219 99 99 379 369 299 299 199 329 219 199 99 219 199 315 315 199 345
44 44 44 44 44 47 47 47 47 47 46 46 46 45 45 45 49 49 49 50 43 43 43 43 43 48 48 48 48 48 46 46 46 42 42 42 40 40 40 41
Biaya Penerbangan (dalam ribuan) 2700 2700 2700 2700 2700 4500 4500 4500 4500 4500 3300 3300 3300 3200 3200 3200 5500 5500 5500 6000 2500 2500 2500 2500 2500 4700 4700 4700 4700 4700 3300 3300 3300 2200 2200 2200 1400 1400 1400 2000
Tabel 1. Data rute dan biaya penerbangan domestik pada perusahaan AirAsia.
No. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40.
FLIGHT LEG ARC CGK11_15, DPS14_00 CGK16_10, DPS18_55 CGK19_50, DPS22_35 CGK07_15, BTH08_50 CGK11_25, BTH13_00 CGK15_30, BTH17_05 CGK06_00, MES08_15 CGK10_45, MES13_00 CGK14_40, MES16_55 CGK16_25, MES18_40 CGK18_50, MES21_05 CGK06_35, PDG08_15 CGK11_30, PDG13_10 CGK15_40, PDG17_20 CGK06_40, BPN09_40 CGK06_50, SUB08_10 CGK11_15, SUB12_35 CGK15_25, SUB16_45 CGK19_30, SUB20_50 CGK20_35, SUB21_55 BTH09_15, CGK10_50 BTH13_25, CGK15_50 BTH17_30, CGK19_05 MES08_40, CGK11_00 MES13_25, CGK15_45 MES19_05, CGK21_25 MES20_10, CGK22_30 MES21_30, CGK23_50 PDG08_40, CGK10_20 PDG13_35, CGK15_15 PDG17_45, CGK19_25 BPN10_05, CGK11_05 SUB13_00, CGK14_15 SUB14_45, CGK16_00 SUB17_10, CGK18_25 SUB21_15, CGK22_30 SUB22_20, CGK23_35 DPS14_25, CGK15_05 DPS19_20, CGK20_00 DPS23_00, CGK23_40
GROUND ARC DPS14_00, DPS14_25 DPS18_55, DPS19_20 DPS22_35, DPS23_00 BTH08_50, BTH09_15 BTH13_00, BTH13_25 BTH17_05, BTH17_30 MES08_15, MES08_40 MES13_00, MES13_25 MES16_55, MES19_05 MES18_40, MES20_10 MES21_05, MES21_30 PDG08_15, PDG08_40 PDG13_10, PDG13_35 PDG17_20, PDG17_45 BPN09_40, BPN10_05 SUB08_10, SUB13_00 SUB12_35, SUB14_45 SUB16_45, SUB17_10 SUB20_50, SUB21_15 SUB21_55, SUB22_20 CGK10_50, CGK11_15 CGK15_50, CGK16_25 CGK19_05, CGK19_30 CGK11_00, CGK11_25 CGK15_45, CGK16_10
CYCLE ARC
CGK21_25, CGK06_00 CGK22_30, CGK07_15 CGK23_50, CGK15_25 CGK10_20, CGK10_45 CGK15_15, CGK15_40 CGK19_25, CGK06_40 CGK11_05, CGK11_30 CGK14_15, CGK14_40 CGK16_00, CGK19_50 CGK18_25, CGK18_50 CGK22_30, CGK06_50 CGK23_35, CGK06_35 CGK15_05, CGK15_30 CGK20_00, CGK20_35 CGK23_40, CGK11_15
Tabel 2. Daftar aktifitas penerbangan AirAsia.
CGK
SUB
MES
PDG
BTH
DPS
06:00
BPN 06:35
06:40 07:15
06:50
08:15
08:10
08:50
08:40
09:40
09:15
10:20 10:50 11:05 11:25 12:35 13:10 13:35
10:05 10:45 11:00 11:15 11:30 13:00 13:25 14:00 14:25 14:45
14:15 14:40 15:05 15:25
15:15 15:30
15:40
15:45
15:50
16:00
16:10
16:25
16:45
16:55
17:05
17:10
17:20
17:30
17:45
18:25
18:40
18:50
18:55
19:05
19:20
19:25
19:30
19:50
20:00
20:10
20:35
20:50
21:05
21:15
21:25
21:30
21:55
22:20
22:30
22:35
23:00
23:35
23:40
23:50 Gambar 10. Jaringan dari armada tipe B737-300.
V SIMPULAN DAN SARAN 5.1 Simpulan Masalah jadwal penerbangan dan rute armada merupakan hal penting dalam operasi perusahaan penerbangan yang menghasilkan kontribusi besar dalam meminimumkan biaya mengingat biaya penerbangan adalah salah satu biaya terbesar dalam perusahan penerbangan. Perusahaan harus dapat mengalokasikan sejumlah pesawat dengan biaya minimum untuk memenuhi jadwal penerbangan yang tersedia. Untuk memformulasikan masalah ini digunakan teknik jaringan ruang-waktu, yaitu jaringan ruang-waktu armada dan jaringan ruang-waktu penumpang. Penyelesaian masalah ini menggunakan LINGO 8.0 dengan metode branch and bound. Prinsip dasar metode branch and bound adalah memecah daerah fisibel dari masalah LP-
relaksasi dengan membuat subproblemsubproblem. Daerah fisibel linear programming adalah daerah yang memenuhi semua kendala linear programming. Metode branch and bound menghasilkan banyaknya pesawat yang dibutuhkan dengan jumlah optimal untuk menjalankan jadwal penerbangan yang telah ditentukan. 5.2 Saran Pada tulisan ini telah dibahas mengenai masalah menentukan jumlah pesawat yang digunakan untuk jadwal penerbangan domestik. Akan lebih baik lagi jika ada yang dapat menindaklanjuti penelitian ini dengan masalah yang lebih kompleks, yaitu masalah jadwal penerbangan dan rute armada dalam lingkup internasional.
DAFTAR PUSTAKA Airasia.http://www.airasia.com/site/in/home. jsp 7 Agustus 2006. Airasia.http://www.airasia.com/skylights/cgi -bin/skylights.cgi 7 Agustus 2006.
Nash, S.G. & A. Sofer. 1996. Linear and Nonlinear Programming. McGrawHill, New York. Taha, H.A. 1975. Integer Programming. Academic Press, New York.
Foulds, L.R. 1992. Graph Theory Applications. Springer-Verlag, New York.
Winston, W.L. 1995. Introduction to Mathematical Programming 2nd ed. Duxbury, New York.
Garfinkel, R.S & G.L. Nemhauser. 1972. Integer Programming. John Wiley & Sons, New York.
Yan, S & Tseng, C.H. 2002. A Passenger Demand Model for Airline Flight Schedulling and Fleet Routing. Computer & Operatins Research 29 : 1559 – 1581.
LAMPIRAN
Lampiran 1 Contoh Penyelesaian Suatu LP dengan Algoritma Simpleks
Dari LP pada contoh 2, dapat diketahui ⎛ − 2 1 1 0 0⎞ ⎛4⎞ ⎟ ⎜ ⎜ ⎟ bahwa A = ⎜ − 1 2 0 1 0 ⎟ , b = ⎜11⎟ , ⎜ 1 0 0 0 1⎟ ⎜5⎟ ⎠ ⎝ ⎝ ⎠
dan c T = (− 2 − 3 0 0 0 ) .
Iterasi 1 Misalkan dipilih sebagai basis adalah x B = (x 3 c TB
x4
x 5 )T dan x N = (x1
x 2 )T ,
B = I = B −1 , = (0 0 0 ) , c TN = (− 2 − 3) dan
⎛− 2 1⎞ ⎜ ⎟ N = ⎜ −1 2⎟ . ⎜ 1 0⎟ ⎝ ⎠ Nilai dari x B = bˆ = B −1b = (4 11 5)T . Dengan basis ini nilai simplex multiplier y T = c TB B −1 = (0 0 0 ) dan nilai reduced costnya adalah cˆ TN = c TN − y T N = (− 2 − 3) . Keduanya bernilai negatif, jadi basis ini belum optimal. Nilai cˆ TN 2 , yaitu nilai elemen baris
( )
kedua dari cˆ TN , memiliki nilai negatif yang lebih besar, maka pilih x 2 (variabel nonbasis kedua) sebagai entering variable. Untuk ratio test, hitung ⎛1⎞ ˆA = B −1 A = ⎜⎜ 2 ⎟⎟ , 2 2 ⎜ 0⎟ ⎝ ⎠ maka perbandingannya adalah : 4 11 bˆ1 / aˆ1, 2 = dan bˆ2 / aˆ 2, 2 = . 1 2 Perbandingan pertama bernilai lebih kecil, maka x 3 (variabel basis pertama) merupakan variabel yang akan meninggalkan basis (leaving variable). Iterasi 2 Pada iterasi ini, x 2 menggantikan x 3 dalam basis. Jadi x B = (x 2
x4
x 5 )T dan x N = (x1
x 3 )T ,
⎛ 1 0 0⎞ ⎛ 1 0 0⎞ ⎜ ⎜ ⎟ ⎟ −1 B = ⎜ 2 1 0⎟ , B = ⎜ − 2 1 0⎟ , ⎜ 0 0 1⎟ ⎜ 0 0 1⎟ ⎝ ⎝ ⎠ ⎠
c TB = (− 3 0 0 ) , c TN = (− 2 0 ) dan ⎛− 2 ⎜ N = ⎜ −1 ⎜ 1 ⎝ Sehingga dapat dihitung x = bˆ = B −1b = (4 B T
1⎞ ⎟ 0⎟ . 0 ⎟⎠ 3 5)T
y = c TB B −1 = (− 3 0 0 )
cˆ TN = c TN − y T N = (− 8 3) . Reduced cost pertama bernilai negatif, maka basis ini belum optimal, dan x1 (variabel nonbasis pertama) sebagai entering variable. Kolom yang berpadanan dengan entering variable adalah ⎛ − 2⎞ ˆA = B −1 A = ⎜⎜ 3 ⎟⎟ . 1 1 ⎜ 1 ⎟ ⎝ ⎠ Dari minimum ratio test, yaitu hasil dari min bˆ2 / aˆ 2,1 = 1, bˆ3 / aˆ 3,1 = 5 , variabel x 4
{
}
yang merupakan variabel basis kedua akan menjadi leaving variable. Iterasi 3 Pada iterasi ini, x1 menggantikan x 4 dalam basis. Jadi x B = (x 2
x1
x 5 )T dan x N = (x 4
⎛ − 13 ⎛1 − 2 0⎞ ⎜ ⎜ ⎟ −1 B = ⎜ 2 − 1 0 ⎟ , B = ⎜ − 23 ⎜⎜ 2 ⎜0 1 1⎟ ⎝ ⎠ ⎝ 3
x 3 )T ,
2 3 1 3
− 13
0⎞ ⎟ 0⎟ , ⎟ 1 ⎟⎠
c TB = (− 3 − 2 0) , c TN = (0 0) dan
⎛0 1⎞ ⎜ ⎟ N = ⎜1 0⎟ . ⎜ 0 0⎟ ⎝ ⎠ Sehingga dapat dihitung x = bˆ = B −1b = (6 1 4)T B
) cˆ TN = c TN − y T N = (83 − 73 ) . y T = c TB B −1 =
(73
− 83
0
Reduced cost pertama bernilai negatif, maka basis ini belum optimal, dan x 3 (variabel nonbasis pertama) sebagai entering variable. Kolom yang berpadanan dengan entering variable adalah
⎛ − 13 ⎞ ⎜ ⎟ ˆA = B −1 A = ⎜ − 2 ⎟ . 3 3 3 ⎜⎜ 2 ⎟⎟ ⎝ 3 ⎠ Calon untuk minimum ratio test hanya satu, yaitu bˆ3 / aˆ 3, 2 = 6 , maka x 5 sebagai
leaving variable.
x1
⎛ 0 0⎞ ⎟ ⎜ N = ⎜1 0⎟ . ⎜0 1⎟ ⎠ ⎝ Sehingga dapat dihitung x = bˆ = B −1b = (8 5 6)T B
Iterasi 4 Pada iterasi ini, x 3 menggantikan x 5 dalam basis. Jadi x B = (x 2
c TB = (− 3 − 2 0) , c TN = (0 0) dan
x 3 ) dan x N = (x 4 T
⎛0 ⎛1 − 2 1⎞ ⎜ ⎟ ⎜ −1 B = ⎜ 2 −1 0⎟ , B = ⎜ 0 0 ⎜⎜ ⎜ 0 1 0⎟ 1 ⎠ ⎝ ⎝1 − 2 1 2
x5 ) , T
1⎞ 2⎟
1⎟ , 3⎟ ⎟ 2⎠
(
y T = c TB B −1 = 0 − 32 cˆ TN = c TN − y T N =
− 72
(32 72 ) .
)
Nilai reduced cost dengan menggunakan basis ini bernilai positif. Hal ini berarti basis telah optimal. Jadi solusi optimalnya adalah x1 = 5, x 2 = 8, x 3 = 6, x 4 = x 5 = 0 , dengan nilai fungsi objektif optimal z = −34 .
Lampiran 2 Program LINGO 8.0 untuk Formulasi Masalah MODEL : TITLE Flight Schedulling; SETS : AIRPORT1 ; AIRPORT2 ; LINKS(AIRPORT1, AIRPORT2) : FLIGHT, GROUND, CYCLE, DEMAND, DELIVERY, BIAYA_F, BIAYA_G, BIAYA_C, BIAYA_DM, BIAYA_DL; ENDSETS !FUNGSI OBJEKTIF; MAX = @SUM(LINKS(I,J) : (DEMAND(I,J) * BIAYA_DM(I,J) + DELIVERY(I,J) * BIAYA_DL(I,J)) - (FLIGHT(I,J) * BIAYA_F(I,J) + GROUND(I,J) * BIAYA_G(I,J) + CYCLE(I,J) * BIAYA_C(I,J))); !KENDALA; !(1) BANYAKNYA PESAWAT YANG DATANG SAMA DENGAN BANYAKNYA PESAWAT YANG PERGI; @FOR(AIRPORT1(I) : @SUM(LINKS(I,J) : FLIGHT(I,J)) @SUM(LINKS(K,I) : FLIGHT(K,I)) = 0); !(2) BANYAKNYA PENUMPANG YANG DATANG SAMA DENGAN BANYAKNYA PENUMPANG YANG PERGI; @FOR(AIRPORT1(I) : @SUM(LINKS(I,J) : DELIVERY(I,J)) @SUM(LINKS(K,I) : DELIVERY(K,I)) = 0); !(3) JUMLAH PESAWAT YANG DIGUNAKAN TIDAK BOLEH MELEBIHI PESAWAT YANG TERSEDIA; @SUM(LINKS(I,J) : CYCLE(I,J)) <= 26; !(4) MASING-MASING PENERBANGAN DILAKUKAN PALING BANYAK SEKALI; @FOR(LINKS(I,J) : FLIGHT(I,J) <= 1); !(5) BANYAKNYA PENUMPANG YANG DIANGKUT TIDAK MELEBIHI KAPASITAS PESAWAT; @FOR(LINKS(I,J) : DELIVERY(I,J) <= (148 * FLIGHT(I,J))); !(6) JIKA ADA FLIGHT, MAKA HARUS ADA GROUND ATAU CYCLE ; @FOR(LINKS(I,J) |I#LE#20: FLIGHT(I,J) = GROUND(I+20,J)); @FOR(LINKS(I,J) |I#EQ#21: FLIGHT(I,J) = GROUND(8,J)); @FOR(LINKS(I,J) |I#EQ#22: FLIGHT(I,J) = GROUND(19,J)); @FOR(LINKS(I,J) |I#EQ#23: FLIGHT(I,J) = GROUND(10,J)); @FOR(LINKS(I,J) |I#EQ#26: FLIGHT(I,J) = GROUND(15,J)); @FOR(LINKS(I,J) |I#EQ#27: FLIGHT(I,J) = GROUND(18,J)); @FOR(LINKS(I,J) |I#EQ#31: FLIGHT(I,J) = GROUND(7,J)); @FOR(LINKS(I,J) |I#EQ#32: FLIGHT(I,J) = GROUND(13,J)); @FOR(LINKS(I,J) |I#EQ#34: FLIGHT(I,J) = GROUND(2,J)); @FOR(LINKS(I,J) |I#EQ#35: FLIGHT(I,J) = GROUND(9,J)); @FOR(LINKS(I,J) |I#EQ#36: FLIGHT(I,J) = GROUND(4,J)); @FOR(LINKS(I,J) |I#EQ#37: FLIGHT(I,J) = GROUND(16,J)); @FOR(LINKS(I,J) |I#EQ#38: FLIGHT(I,J) = GROUND(5,J)); @FOR(LINKS(I,J) |I#EQ#40: FLIGHT(I,J) = GROUND(12,J));
@FOR(LINKS(I,J) @FOR(LINKS(I,J) @FOR(LINKS(I,J) @FOR(LINKS(I,J) @FOR(LINKS(I,J) @FOR(LINKS(I,J) @FOR(LINKS(I,J)
|I#EQ#24: |I#EQ#25: |I#EQ#28: |I#EQ#29: |I#EQ#30: |I#EQ#33: |I#EQ#39:
FLIGHT(I,J) FLIGHT(I,J) FLIGHT(I,J) FLIGHT(I,J) FLIGHT(I,J) FLIGHT(I,J) FLIGHT(I,J)
= = = = = = =
CYCLE(6,J)); CYCLE(11,J)); CYCLE(1,J)); CYCLE(14,J)); CYCLE(3,J)); CYCLE(20,J)); CYCLE(17,J));
!(7) BATASAN UNTUK SETIAP ALIRAN ARC ARMADA; @FOR(LINKS(I,J) : FLIGHT(I,J) >= 0); @FOR(LINKS(I,J) : FLIGHT(I,J) <= 1); @FOR(LINKS(I,J) : GROUND(I,J) >= 0); @FOR(LINKS(I,J) : GROUND(I,J) <= 1); @FOR(LINKS(I,J) : CYCLE(I,J) >= 0); @FOR(LINKS(I,J) : CYCLE(I,J) <= 1); !(8) BATASAN UNTUK SETIAP ALIRAN ARC PENUMPANG; @FOR(LINKS(I,J) : DELIVERY(I,J) >= 0); @FOR(LINKS(I,J) : DELIVERY(I,J) <= 148); @FOR(LINKS(I,J) : DEMAND(I,J) >= 0); @FOR(LINKS(I,J) : DEMAND(I,J) <= 40); !(9) ALIRAN ARC @FOR(LINKS(I,J) @FOR(LINKS(I,J) @FOR(LINKS(I,J)
ARMADA MERUPAKAN INTEGER; : @GIN(FLIGHT(I,J))); : @GIN(GROUND(I,J))); : @GIN(CYCLE(I,J)));
!(10) ALIRAN ARC PENUMPANG MERUPAKAN INTEGER ; @FOR(LINKS(I,J) : @GIN(DELIVERY(I,J))); @FOR(LINKS(I,J) : @GIN(DEMAND(I,J))); DATA : AIRPORT1, AIRPORT2, BIAYA_F, BIAYA_G, BIAYA_C, BIAYA_DM, BIAYA_DL = @OLE('C:\DATA\BIAYA.XLS'); ENDDATA
Lampiran 3 Hasil dari Program LINGO 8.0 Global optimal solution found at iteration: Objective value: Model Title: Flight Schedulling
FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( FLIGHT( GROUND( GROUND( GROUND( GROUND( GROUND( GROUND( GROUND( GROUND( GROUND( GROUND( GROUND(
CGK06_50, CGK11_15, CGK15_25, CGK19_30, CGK20_35, CGK06_00, CGK10_45, CGK14_40, CGK16_25, CGK18_50, CGK06_35, CGK11_30, CGK15_40, CGK07_15, CGK11_25, CGK15_30, CGK11_15, CGK16_10, CGK19_50, CGK06_40, SUB13_00, SUB14_45, SUB17_10, SUB21_15, SUB22_20, MES08_40, MES13_25, MES19_05, MES20_10, MES21_30, PDG08_40, PDG13_35, PDG17_45, BTH09_15, BTH13_25, BTH17_30, DPS14_25, DPS19_20, DPS23_00, BPN10_05, CGK11_15, CGK19_30, CGK20_35, CGK10_45, CGK14_40, CGK16_25, CGK18_50, CGK11_30, CGK15_40, CGK11_25, CGK15_30,
Variable SUB08_10) SUB12_35) SUB16_45) SUB20_50) SUB21_55) MES08_15) MES13_00) MES16_55) MES18_40) MES21_05) PDG08_15) PDG13_10) PDG17_20) BTH08_50) BTH13_00) BTH17_05) DPS14_00) DPS18_55) DPS22_35) BPN09_40) CGK14_15) CGK16_00) CGK18_25) CGK22_30) CGK23_35) CGK11_00) CGK15_45) CGK21_25) CGK22_30) CGK23_50) CGK10_20) CGK15_15) CGK19_25) CGK10_50) CGK15_50) CGK19_05) CGK15_05) CGK20_00) CGK23_40) CGK11_05) CGK10_50) CGK19_05) CGK20_00) CGK10_20) CGK14_15) CGK15_50) CGK18_25) CGK11_05) CGK15_15) CGK11_00) CGK15_05)
Value 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 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
80 527080.0
Reduced Cost 2700.000 2700.000 2700.000 2700.000 2700.000 4500.000 4500.000 4500.000 4500.000 4500.000 3300.000 3300.000 3300.000 3200.000 3200.000 3200.000 5500.000 5500.000 5500.000 6000.000 2500.000 2500.000 2500.000 2500.000 2500.000 4700.000 4700.000 4700.000 4700.000 4700.000 3300.000 3300.000 3300.000 2200.000 2200.000 2200.000 1400.000 1400.000 1400.000 2000.000 200.0000 200.0000 200.0000 200.0000 200.0000 200.0000 200.0000 200.0000 200.0000 200.0000 200.0000
GROUND( GROUND( GROUND( GROUND( GROUND( GROUND( GROUND( GROUND( GROUND( GROUND( GROUND( GROUND( GROUND( GROUND( GROUND( GROUND( GROUND( GROUND( GROUND( GROUND( GROUND( GROUND( CYCLE( CYCLE( CYCLE( CYCLE( CYCLE( CYCLE( CYCLE( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND(
CGK16_10, CGK19_50, SUB13_00, SUB14_45, SUB17_10, SUB21_15, SUB22_20, MES08_40, MES13_25, MES19_05, MES20_10, MES21_30, PDG08_40, PDG13_35, PDG17_45, BTH09_15, BTH13_25, BTH17_30, DPS14_25, DPS19_20, DPS23_00, BPN10_05, CGK06_50, CGK15_25, CGK06_00, CGK06_35, CGK07_15, CGK11_15, CGK06_40, CGK06_50, CGK11_15, CGK15_25, CGK19_30, CGK20_35, CGK06_00, CGK10_45, CGK14_40, CGK16_25, CGK18_50, CGK06_35, CGK11_30, CGK15_40, CGK07_15, CGK11_25, CGK15_30, CGK11_15, CGK16_10, CGK19_50, CGK06_40, SUB13_00, SUB14_45, SUB17_10, SUB21_15, SUB22_20, MES08_40, MES13_25, MES19_05, MES20_10, MES21_30,
CGK15_45) CGK16_00) SUB08_10) SUB12_35) SUB16_45) SUB20_50) SUB21_55) MES08_15) MES13_00) MES16_55) MES18_40) MES21_05) PDG08_15) PDG13_10) PDG17_20) BTH08_50) BTH13_00) BTH17_05) DPS14_00) DPS18_55) DPS22_35) BPN09_40) CGK21_25) CGK23_50) CGK22_30) CGK23_35) CGK22_30) CGK23_40) CGK19_25) SUB08_10) SUB12_35) SUB16_45) SUB20_50) SUB21_55) MES08_15) MES13_00) MES16_55) MES18_40) MES21_05) PDG08_15) PDG13_10) PDG17_20) BTH08_50) BTH13_00) BTH17_05) DPS14_00) DPS18_55) DPS22_35) BPN09_40) CGK14_15) CGK16_00) CGK18_25) CGK22_30) CGK23_35) CGK11_00) CGK15_45) CGK21_25) CGK22_30) CGK23_50)
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 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000
200.0000 200.0000 200.0000 200.0000 200.0000 200.0000 200.0000 200.0000 200.0000 200.0000 200.0000 200.0000 200.0000 200.0000 200.0000 200.0000 200.0000 200.0000 200.0000 200.0000 200.0000 200.0000 200.0000 200.0000 200.0000 200.0000 200.0000 200.0000 200.0000 229.0000 129.0000 219.0000 219.0000 179.0000 329.0000 329.0000 329.0000 329.0000 299.0000 199.0000 199.0000 149.0000 329.0000 249.0000 249.0000 415.0000 315.0000 299.0000 325.0000 179.0000 219.0000 219.0000 99.00000 99.00000 379.0000 369.0000 299.0000 299.0000 199.0000
DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DEMAND( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY( DELIVERY(
PDG08_40, PDG13_35, PDG17_45, BTH09_15, BTH13_25, BTH17_30, DPS14_25, DPS19_20, DPS23_00, BPN10_05, CGK06_50, CGK11_15, CGK15_25, CGK19_30, CGK20_35, CGK06_00, CGK10_45, CGK14_40, CGK16_25, CGK18_50, CGK06_35, CGK11_30, CGK15_40, CGK07_15, CGK11_25, CGK15_30, CGK11_15, CGK16_10, CGK19_50, CGK06_40, SUB13_00, SUB14_45, SUB17_10, SUB21_15, SUB22_20, MES08_40, MES13_25, MES19_05, MES20_10, MES21_30, PDG08_40, PDG13_35, PDG17_45, BTH09_15, BTH13_25, BTH17_30, DPS14_25, DPS19_20, DPS23_00, BPN10_05,
CGK10_20) CGK15_15) CGK19_25) CGK10_50) CGK15_50) CGK19_05) CGK15_05) CGK20_00) CGK23_40) CGK11_05) SUB08_10) SUB12_35) SUB16_45) SUB20_50) SUB21_55) MES08_15) MES13_00) MES16_55) MES18_40) MES21_05) PDG08_15) PDG13_10) PDG17_20) BTH08_50) BTH13_00) BTH17_05) DPS14_00) DPS18_55) DPS22_35) BPN09_40) CGK14_15) CGK16_00) CGK18_25) CGK22_30) CGK23_35) CGK11_00) CGK15_45) CGK21_25) CGK22_30) CGK23_50) CGK10_20) CGK15_15) CGK19_25) CGK10_50) CGK15_50) CGK19_05) CGK15_05) CGK20_00) CGK23_40) CGK11_05)
40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000 148.0000
329.0000 219.0000 199.0000 99.00000 219.0000 199.0000 315.0000 315.0000 199.0000 345.0000 44.00000 44.00000 44.00000 44.00000 44.00000 47.00000 47.00000 47.00000 47.00000 47.00000 46.00000 46.00000 46.00000 45.00000 45.00000 45.00000 49.00000 49.00000 49.00000 50.00000 43.00000 43.00000 43.00000 43.00000 43.00000 48.00000 48.00000 48.00000 48.00000 48.00000 46.00000 46.00000 46.00000 42.00000 42.00000 42.00000 40.00000 40.00000 40.00000 41.00000
