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.