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
________________________________________________________
