MODEL OPTIMISASI UNTUK PENJADWALAN TAXI BANDARA

MODEL OPTIMISASI UNTUK PENJADWALAN TAXI BANDARA

TESIS

Oleh

RIZKI ISMALINDA BATUBARA 077021068/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2009

Rizki Ismalinda Batubara : Model Optimisasi Untuk Penjadwalan Taxi Bandara, 2009.

MODEL OPTIMISASI UNTUK PENJADWALAN TAXI BANDARA

TESIS

Diajukan Sebagai Salah Satu Syarat untuk Memperoleh Gelar Magister Sains dalam Program Studi Magister Matematika pada Sekolah Pascasarjana Universitas Sumatera Utara

Oleh

RIZKI ISMALINDA BATUBARA 077021068/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2009


Judul Tesis

: MODEL OPTIMISASI UNTUK PENJADWALAN TAXI BANDARA Nama Mahasiswa : Rizki Ismalinda Batubara Nomor Pokok : 077021068 Program Studi : Matematika

Menyetujui, Komisi Pembimbing

(Dr. Saib Suwilo, M.Sc) Ketua

(Prof. Dr. Opim Salim Sitompul, M.Sc) Anggota

Ketua Program Studi

Direktur

(Prof. Dr. Herman Mawengkang)

(Prof. Dr. Ir. T.Chairun Nisa. B,M.Sc)

Tanggal lulus: 29 Mei 2009


Telah diuji pada Tanggal 29 Mei 2009

PANITIA PENGUJI TESIS Ketua

: Dr. Saib Suwilo, M.Sc

Anggota

: 1. Prof. Dr. Opim Salim Sitompul, M.Sc 2. Prof. Dr. Herman Mawengkang 3. Drs. Marihat Situmorang, M.Kom


ABSTRAK Tesis ini menyajikan Model Optimisasi untuk penjadwalan taxi bandara. Dengan menggunakan program Mixed-Integer untuk menggambarkan proses kedatangan dan keberangkatan pesawat, dengan tujuan agar permasalahan penjadwalan taxi dapat diminimalisir. Tulisan ini membicarakan sebuah implementasi untuk memecahkan problem optimisasi, dengan menghubungkan antara hasil numerik dengan data yang sebenarnya yang diperoleh dari bandara dalam satu algoritma, hal ini penting dilakukan guna mendapatkan hasil perhitungan yang efesien dan signifikan. Kata kunci : Penjadwalan taxi pesawat, program mixed-integer, heuristic.

i Rizki Ismalinda Batubara : Model Optimisasi Untuk Penjadwalan Taxi Bandara, 2009.

ABSTRACT This thesis gives an optimization model for airport taxi scheduling. This paper introduces a mixed-integer programming formulation to represent the movement of aircraft on the surface the airport. In the optimal schedule delay due to taxi conflicts are minimesed. This paper discuss about implementation issues for solving this optimization problem. Numerical results with real data from airport demonstrate that the algorithms lead to significant improvements of the efficiency with reasonable computational effort. Keywords : Aircraft taxi scheduling, mixed-integer programming, heuristic.

ii Rizki Ismalinda Batubara : Model Optimisasi Untuk Penjadwalan Taxi Bandara, 2009.

KATA PENGANTAR

Puji syukur penulis ucapkan kepada Allah s.w.t atas anugrah dan berkah yang telah diberikan sehinggal penulis dapat menyelesaikan tesis ini dengan judul: Model Optimisasi untuk penjadwalan Taxi Bandara. Tesis ini merupakan salah satu persyaratan penyelesaian studi pada program studi Magister Matematika SPs Universitas Sumatera Utara. Pada kesempatan ini, penulis menyampaikan terima kasih yang sebesarbesarnya kepada: Prof. dr. Chairuddin P. Lubis, DTM&H, Sp.A(K) selaku Rektor Universitas Sumatera Utara. Prof. Dr. Ir. T. Chairun Nisa B. M.Sc selaku Direktur Sekolah Pascasarjana Universitas Sumatera Utara. Kepala Dinas pendidikan Kota Medan yang telah memberikan kesempatan kepada penulis untuk mengikuti Program Studi Magister di Sekolah Pascasarjana Universitas Sumatera Utara. Prof. Dr. Herman Mawengkang, selaku Ketua Program Studi Magister Matematika SPs Universitas Sumatera Utara dan juga telah banyak memberikan masukan dan saran dalam penulisan tesis ini. Dr. Saib Suwilo, MSc, selaku Sekretaris Program Studi Magister Matematika SPs Universitas Sumatera Utara yang juga selaku Dosen Pembimbing I, yang telah banyak membantu dalam penulisan tesis ini.

iii Rizki Ismalinda Batubara : Model Optimisasi Untuk Penjadwalan Taxi Bandara, 2009.

Prof. Dr. Opim Salim Sitompul, MSc selaku Dosen Pembimbing II yang telah banyak memberikan masukan dan saran dalam penulisan tesis ini. Seluruh Staf Pengajar pada Program Studi Magister Matematika SPs Universitas Sumatera Utara, yang telah memberikan ilmunya selama masa perkuliahan. Seluruh Staf Pengajar Matematika FMIPA Universitas Sumatera Utara dan Rekan-rekan Mahasiswa Program Studi Magister Matematika Sps Universitas Sumatera Utara yang telah memberikan bantuan baik moril maupun materil serta motivasi kepada penulis dalam penyelesaian tesis ini, dan juga terima kasih kepada Ibu Misiani, SSi, selaku Staf Administrasi Program Studi Magister Matematika SPs Universitas Sumatera Utara yang telah memberikan pelayanan yang baik kepada penulis. Akhir kata, penulis hanya bisa berdoa kepada Allah SWT semoga Allah memberikan balasan atas semua jasa-jasa Bapak/Ibu dan Saudara/I yang telah diberikan kepada penulis.

Medan,

Mei 2009

Penulis,

Rizki Ismalinda Batubara

iv Rizki Ismalinda Batubara : Model Optimisasi Untuk Penjadwalan Taxi Bandara, 2009.

RIWAYAT HIDUP

A. Data Pribadi

Nama

: RIZKI ISMALINDA BATUBARA

Tempat/tanggal lahir : Medan / 10 Nopember 1971 Jenis kelamin

: Perempuan

Agama

: Islam

Alamat Rumah

: Jl. Kapten M. Jamil Lubis No.73 Bandar Selamat, Medan

B. Riwayat Pendidikan

1979-1985

: SD Islam Azizi ”A” Medan

1985-1988

: SMP XV Medan

1988-1990

: SMA Swasta Al-Azhar Medan

1990-1999

: FMIPA USU Medan

C. Pengalaman Kerja

1995-1998

: Staf Karyawan Harian PTP IX

2000-Sekarang

: Staf Pengajar Institut Teknologi Medan

2004-Sekarang

: Staf Pengajar SMA Swasta Al-Azhar Medan

v Rizki Ismalinda Batubara : Model Optimisasi Untuk Penjadwalan Taxi Bandara, 2009.

DAFTAR ISI Halaman ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

i

ABSTRACT

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ii

KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . .

iii

RIWAYAT HIDUP . . . . . . . . . . . . . . . . . . . . . . . . . .

v

DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

vi

DAFTAR TABEL . . . . . . . . . . . . . . . . . . . . . . . . . . .

viii

DAFTAR GAMBAR . . . . . . . . . . . . . . . . . . . . . . . . .

ix

BAB 1 PENDAHULUAN . . . . . . . . . . . . . . . . . . . . . . .

1

1.1 Latar Belakang . . . . . . . . . . . . . . . . . . . . . .

1

1.2 Perumusan Masalah . . . . . . . . . . . . . . . . . . . .

3

1.3 Tujuan Penelitian . . . . . . . . . . . . . . . . . . . . .

3

1.4 Kontribusi Penelitian . . . . . . . . . . . . . . . . . . .

4

1.5 Metodologi Penelitian . . . . . . . . . . . . . . . . . . .

4

BAB 2 TINJAUAN PUSTAKA . . . . . . . . . . . . . . . . . . . .

5

BAB 3 LANDASAN TEORI . . . . . . . . . . . . . . . . . . . . .

7

BAB 4 MODEL OPTIMISASI PENJADWALAN TAXI BANDARA . .

18

4.1 Per-Proses

. . . . . . . . . . . . . . . . . . . . . . . .

18

4.2 Putaran Mendatar (Rolling Horizon) . . . . . . . . . . . .

19

4.2.1 Rolling Horizon Variant 1 . . . . . . . . . . . . . .

20

4.2.2 Rolling Horizon Variant 2 . . . . . . . . . . . . . .

21

vi Rizki Ismalinda Batubara : Model Optimisasi Untuk Penjadwalan Taxi Bandara, 2009.

4.2.3 Rolling Horizon Variant 3 (Sliding Window) . . . . .

22

4.3 Hasil Implementasi . . . . . . . . . . . . . . . . . . . .

23

BAB 5 KESIMPULAN . . . . . . . . . . . . . . . . . . . . . . . .

30

DAFTAR PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . .

32

vii Rizki Ismalinda Batubara : Model Optimisasi Untuk Penjadwalan Taxi Bandara, 2009.

DAFTAR TABEL

Nomor

Judul

Halaman

4.1 Contoh perkiraan 30 menit hasil dari 12 contoh pesawat pada Amsterdam Airport Schiphol. Sumber : Smeltink, dkk., ”An Optimisation Model for Airport Taxi Scheduling” . . . . . . . . . 4.2

Penggunaan 3 (tiga) variant yang berbeda yang ditunjukkan dalam waktu rata-rata dan Standard deviasi. Sumber : Smeltink, dkk., ”An Optimisation Model for Airport Taxi Scheduling” . . . . .

viii Rizki Ismalinda Batubara : Model Optimisasi Untuk Penjadwalan Taxi Bandara, 2009.

25

26

DAFTAR GAMBAR

Nomor 3.1

3.2 4.1 4.2

4.3

4.4

Judul

Halaman

Illustrasi dari 3 (tiga) tipe letak berhenti (parkir) pesawat. Sumber : Smeltink, dkk., ”An Optimisation Model for Airport Taxi Scheduling” . . . . . . . . . . . . . . . . . . . . . . . . .

8

Illustrasi Bandara Schiphol Amsterdam. Sumber : Smeltink, dkk., ”An Optimisation Model for Airport Taxi Scheduling” .

9

Skema contoh Rolling Horizon Varian 1 dan 2. Sumber : Smeltink, dkk., ”An Optimisation Model for Airport Taxi Scheduling” .

21

Grafik keterlambatan per pesawat dalam detik yang diperoleh dengan variant pertama rolling horizon. Sumber : Smeltink, dkk., ”An Optimisation Model for Airport Taxi Scheduling” .

27

Grafik keterlambatan per pesawat dalam detik diperoleh dengan perhitungan rolling horizon variant kedua. Sumber : Smeltink, dkk., ”An Optimisation Model for Airport Taxi Scheduling” .

28

Grafik keterlambatan per pesawat dalam detiknya diperoleh dengan perhitungan rolling horizon variant ketiga (sliding window). Sumber : Smeltink, dkk., ”An Optimisation Model for Airport Taxi Scheduling” . . . . . . . . . . . . . . . . . .

29

ix Rizki Ismalinda Batubara : Model Optimisasi Untuk Penjadwalan Taxi Bandara, 2009.

BAB 1 PENDAHULUAN

1.1 Latar Belakang Perkembangan pesawat terbang sebagai alat trasportasi telah cukup baik dan memenuhi standart kelayakan. Pengaturan oleh pihak bandara terus dilakukan mulai dari meningkatkan pelayanan, kapasitas pesawat, serta penambahan rute. Pengaturan bandara tidak terlepas dengan apa yang kita sebut proses bandara, Proses bandara merupakan hal-hal yang menyangkut kedatangan, keberangkatan dan parkirnya pesawat. Pengaturan proses bandara ini harus dilakukan dengan sistem yang baik guna peningkatan mutu dan layanan bandara itu sendiri. Saat terjadi lonjakan penumpang, maka dengan sendirinya kapasitas bandara juga akan meningkat, untuk mengatasi hal ini diperlukan pengaturan yang baik oleh pihak bandara yakni dengan melakukan integrasi antara sistem bandara dengan proses bandara itu sendiri yang kita kenal dengan nama CDM (Collaboration Decision Making), dengan harapan apabila terjadi lonjakan penumpang, maka penumpang yang tidak terlayani pada satu waktu penerbangan, dapat dialihkan pada penerbangan berikutnya. Hal ini tentunya tidak terlepas dari kerjasama pihak bandara dengan pihak pemilik maskapai penerbangan. Proses taxi merupakan bagian dari total proses bandara. Proses taxi adalah proses perjalanan atau pergerakan pesawat secara perlahan dari landasan menuju tempat berhenti (parkir) pada saat mendarat maupun proses perjalanan atau perge-

1 Rizki Ismalinda Batubara : Model Optimisasi Untuk Penjadwalan Taxi Bandara, 2009.

2 rakan pesawat secara perlahan dari tempat parkir menuju landasan ketika hendak berangkat (take off), dengan lain perkataan, proses ini dimulai dari tahap ketika pesawat dipandu pada waktu tiba di landasan, setelah mendarat pesawat akan bergerak menuju tempat berhenti (posisi parkir), posisi parkir ini biasa kita kenal dengan sebutan Apron. Di Apron inilah pesawat akan menaikkan dan menurunkan penumpang, membongkar dan memuat bagasi untuk mempersiapkan keberangkatan berikutnya, serta keadaan dimana ketika pesawat siap dan diberi izin untuk bergerak menuju landasan pacu untuk terbang menuju tujuan berikutnya. Dalam keadaan normal, proses taxi tidak akan membawa pengaruh bagi proses bandara, proses taxi akan sangat berpengaruh apabila terjadi lonjakan penumpang yang tentunya berakibat pada lonjakan kapasitas bandara. Bagi perusahaan penerbangan dan operator bandara, penjadwalan proses taxi akan sangat berguna untuk kepentingan ekonomis. Studi tentang proses taxi ini telah mulai dilakukan pada tahun 1990-an, dimana Cheng (1998) dan Pitfield, dkk memperkenalkan simulasi pergerakan pesawat selama berjalan dari apron menuju landasan dan sebaliknya. Kemudian Andersson, dkk (2000) menjabarkan bahwa proses taxi berinteraksi dengan proses kedatangan pesawat. Berikutnya Carr, dkk (2002), Idris, dkk (2002), Anagnostakis dan Clarke (2003), kembali memaparkan bahwa proses taxi berinteraksi dengan proses keberangkatan. Tulisan-tulisan terdahulu ini sangat mempertimbangkan tentang rute taxi, akan tetapi optimisasi dilakukan adalah dengan memilih alternative rute taxi dan bukan pertimbangan lainnya seperti jadwal waktu pesawat melintasi rutenya.


3 Dalam tulisan ini, penulis mencoba untuk menyajikan sebuah model dan algorithma untuk mengoptimisasi penjadwalan taxi dengan mengambil waktu pesawat melintasi rutenya sebagai deterministik

1.2 Perumusan Masalah Rumusan permasalahan yang akan dikupas dalam tesis ini nantinya adalah model optimisasi mengenai penjadwalan taxi. Model dan algoritma yang diambil untuk mengoptimisasi jadwal taxi dipergunakan untuk menentukan jam terbang pesawat, pengamanan, kecepatan dan efesiensi penerbangan dimulai dari pesawat lepas landas sampai pada pendaratan. Untuk mendapatkan hasil yang signifikan dan layak, maka hal-hal yang menjadi permasalahan adalah bagaimana proses taxi yang dikaitkan dengan interaksi proses kedatangan, keberangkatan dan berhentinya pesawat (parkir) serta optimisasi model dari penjadwalan taxi tersebut.

1.3 Tujuan Penelitian Tujuan penelitian ini adalah mencari model optimisasi atas proses penjadwalan taxi bandara dengan mengaitkan proses interaksi kedatangan, keberangkatan dan parkirnya pesawat pada suatu bandara guna menekan masalah yang timbul apabila kapasitas bandara mengalami lonjakan.


4 1.4 Kontribusi Penelitian Adapun kontribusi dalam penelitian ini adalah dapat membantu pihak bandara membuat keputusan untuk menentukan solusi problem dalam kondisi bandara ketika mengalami lonjakan kapasitas.

1.5 Metodologi Penelitian Penelitian ini dilakukan dengan metode tinjauan pustaka. Adapun langkahlangkah yang akan dilakukan adalah sebagai berikut:

1. Menjelaskan tentang proses taxi 2. Menjelaskan tentang model optimisasi penjadwalan taxi 3. Menjelaskan tentang implementasi dari model optimisasi penjadwalan taxi. 4. Mencari hasil numerik yang akan dicapai 5. Menarik kesimpulan dari hasil penelitian.


BAB 2 TINJAUAN PUSTAKA

Model Optimisasi merupakan metode atau rumus yang dapat dipakai untuk menjelaskan berbagai variabel keruanglingkup yang sederhana serta merupakan proses pengambilan keputusan dengasn maksud mengoptimalkan fungsi objektif. Persoalan penjadwalan dalam pelaksanaan proses bandara tidak terelakkan dalam pengoptimalan sumber daya bandara itu sendiri, salah satu persoalan proses bandara tersebut adalah penjadwalan taxi. Dalam setiap problem optimisasi terdapat objektifitas keputusan untuk diambil, ketersediaan sumberdaya dan kendala terkait. Problem penjadwalan taxi adalah hal yang berhubungan dengan proses kedatangan dan keberangkatan serta parkirnya pesawat yang dikaitkan dengan waktu, dimana hal-hal tersebut merupakan suatu penyelesaian yang harus dikelompokkan secara bersama-sama untuk menghasilkan suatu jadwal taxi dengan memperhatikan kondisi tertentu. Proses taxi adalah proses perjalanan atau pergerakan pesawat secara perlahan dari landasan menuju tempat berhenti (parkir) pada saat mendarat maupun proses perjalanan atau pergerakan pesawat secara perlahan dari tempat parkir menuju landasan ketika hendak berangkat (take off), dengan lain perkataan, proses ini dimulai dari tahap ketika pesawat dipandu pada waktu tiba di landasan, setelah mendarat pesawat akan bergerak menuju tempat berhenti (posisi parkir), posisi parkir ini biasa kita kenal dengan sebutan Apron. Di Apron inilah pesawat akan menaikkan dan menurunkan penumpang, membongkar dan memuat bagasi


6 untuk mempersiapkan bekerangkatan berikutnya, serta keadaan dimana ketika pesawat siap dan diberi izin untuk bergerak menuju landasan pacu untuk terbang menuju tujuan berikutnya (Smeltink, dkk., 2004 ) Nemhauser dan Wolsey (1988) menyatakan dengan menggunakan kecepatan maksimum dan minimum taxi, kemungkinan waktu tercepat dan terlama sebuah pesawat adalah kemampuan untuk mencapai node dari rute yang dapat dihitung. Jika jarak 2 (dua) pesawat overlap (bersamaan), maka model ditentukan atas urutan mereka pada node, tapi jika jarak ini tidak bersamaan (not overlap), maka urutan mereka dapat diketahui dengan melihat node sebelumnya. Sebagai contoh : jika ditentukan perjalanan pesawat i akan menjangkau node u lebih cepat dari pesawat j dalam setiap jadwal, maka akan didapat formulasi Ziju = 1 dan Zjiu = 0, dalam setiap proses akan membentuk rumus persamaan untuk mendapatkan formulasi mana yang dapat mengurangi komputasi (perhitungan) waktu. Program Integer yang digunakan dalam penyelesaian masalah penjadwalan taxi pesawat adalah program yang mengharuskan pada semua nilai variable keputusannya harus berupa bilangan 0 atau 1. Bentuk umum model program integer 0-1 adalah: Maksimum ( Minimum ) Z =

n X

cj xj

j=1

Dengan kendala :

n X

aij xj (≤, =, ≥)bi(i = 1, 2, . . . , m)

j=1

xj = 0 atau 1 (j = 1, 2, . . . , n)


BAB 3 LANDASAN TEORI

Penekanan waktu sebagai variabel bagi sebuah pesawat dalam melakukan proses taxi merupakan bagian yang tidak terpisahkan dengan ETA (Estimated Time of Arrival), ATA (Actual Time of Arrival), TTD (Target Time of Departure) dan OBT (Off-Block Time ). Pada waktu pesawat minta izin pada pengawas untuk mendarat, maka fase perkiraan waktu mendarat ini kita misalkan sebagai Estimated Time of Arrival (ETA), sedangkan waktu yang sebenarnya yang diperlukan untuk fase ini kita misalkan sebagai Actual Time of Arrival (ATA). ATA dan ETA merupakan batas waktu yang disediakan untuk pergerakan taksi selama pesawat mendarat. Pada posisi pesawat parkir kita mengambil pemisalan Target Time of Departure (TTD) dan Off-Block Time (OBT), dimana TTD adalah waktu yang dibutuhkan pesawat dari apron menuju landasan pacu pada saat lepas landas, sedangkan OBT adalah waktu tunggu pesawat pada tempatnya sebelum lepas landas dari landasan pacu Waktu yang disediakan oleh Ground Control untuk proses taksi adalah kirakira 15 sampai dengan 30 menit, skala waktu inilah yang dapat diasumsikan untuk memperoleh hasil yang akurat dari ETA, OBT dan TTD. Secara tidak langsung terjadi hubungan antara penjadwalan waktu taxi dengan posisi parkir pesawat. Untuk menentukan hal ini pertimbangan letak atau posisi pesawat pada waktu berhenti (parkir), dan untuk menghindari arah yang 7 Rizki Ismalinda Batubara : Model Optimisasi Untuk Penjadwalan Taxi Bandara, 2009.

8 mengakibatkan tabrakan pesawat, maka dengan ini diberikan 3 (tiga) posisi parkir pasawat yang dapat dipertimbangkan yakni:

1. Saling menyeberang, dimana pesawat menggunakan titik potong jalur taksi pada waktu yang sama. 2. Searah, hal ini akan menimbulkan masalah jika pesawat yang disampingnya berkecepatan lebih tinggi. 3. Saling berhadapan

Gambar 3.1

Illustrasi dari 3 (tiga) tipe letak berhenti (parkir) pesawat. Sumber : Smeltink, dkk., ”An Optimisation Model for Airport Taxi Scheduling”

Dengan membuat pemisalan jalur taksi sebagai G = (V, E), dimana V adalah kumpulan node dan E adalah kumpulan panjang sisi, maka didapat, fungsi l : E → R+ yang merupakan panjang sisi. Berikut disajikan illustrasi gambar bandara Schiphol Amsterdam, yang mana bandara schiphol Amsterdam inilah yang dijadikan model bandara untuk optimisasi penjadwalan taxi oleh Smeltink, dkk. Bandara ini diambil sebagai sampel karena pada waktu tertentu bandara ini dapat mengalami lonjakan kapasitas yang cukup signifikan.


9

Gambar 3.2

Illustrasi Bandara Schiphol Amsterdam. Sumber : Smeltink, dkk., ”An Optimisation Model for Airport Taxi Scheduling”

Pada gambar 3.2, dapat diillustrasikan bagaimana sebuah pesawat yang melakukan taxi dari mulai apron menuju landasan pacu dengan melewati node-node sesuai dengan rute perjalanan taxi pesawat tersebut pada saat proses keberangkatan pesawat dan sebaliknya taxi pesawat mulai dari landasan pacu menuju apron dengan melewati node-node sesuai dengan rute perjalanan taxi pesawat tersebut pada saat proses kedatangan pesawat. Misalkan A = {1, . . . , n} merupakan kumpulan pesawat, bagian ini menjadi pembagi. Kedatangan pesawat dimisalkan Aarr ⊂ A dan proses keberangkatan pesawat dinyatakan dengan Adep ⊂ A. Bagian R = {R1, R2 , . . . , Rn } merupakan kumpulan rute taksi, dimana taksi Ri adalah rute taksi pada pesawat i. Sebuah i ), dengan Uji ∈ V untuk rute taxi Ri adalah perkiraan node (U1i , U2i , U3i , . . . , Uki i ) ∈ E untuk j = 1, . . . , ki − 1. j = 1, . . . , ki sama dengan (Uji , Uj+1

Maka dapat disederhanakan, notasi (U, V ) ∈ Ri dapat digunakan jika sisi (U, V ) adalah bagian dari rute pesawat i, dan juga U ∈ Ri digunakan untuk menunjukkan bahwa node u adalah rute pesawat i.


10 Untuk setiap node dalam rute, harus ditentukan yang mana waktu yang seharusnya dimiliki oleh sebuah pesawat untuk menjangkau node, hal ini dapat dinyatakan dengan: tiu ∈ R+ dimana i ∈ A dan u ∈ Ri

Variabel ini menunjukkan jadwal waktu ketika pesawat i menjangkau node u masuk dalam rute. Jika node yang sama berisikan 2 atau lebih rute pesawat, kita harus menentukan yang mana lintasan pesawat dalam node tersebut, oleh karena itu program integer yang dipakai adalah program integer 0-1 dimana program integer 0-1 yakni:

a. Variabel yiju = 1 jika pesawat i bertemu node u secara tepat sebelum pesawat j dan Varibel yiju = 0 jika pesawat i tidak bertemu node u secara tepat sebelum pesawat j. b. Variabel Ziju = 1 jika pesawat i menjangkau node u sebelum pesawat j. Serta Variabel Ziju = 0 jika pesawat i tidak menjangkau node u sebelum pesawat j.

Jika satu pesawat lebih dahulu berada pada node dan diikuti pesawat lain, maka model pesawat ini menunjukkkan hasil dan pengganti seluruh pesawat lainnya. Model pesawat ini ditunjukkan sebagai pesawat 0 dan A0 = A ∪ {o}.


11 Berikut disajikan beberapa rumus: X

yiju = 1

∀j ∈ A0, ∀u ∈ Ri ∩ Rj

(3.1)

yiju = 1

∀i ∈ A0 , ∀u ∈ Ri ∩ Rj

(3.2)

tju > yiju tiu

∀i, j ∈ A, i 6= j, ∀u ∈ Ri ∩ Rj

(3.3)

tiu > y0ju tju

∀i, j ∈ A, i 6= j, ∀u ∈ Ri ∩ Rj

(3.4)

tiu > yi0u tju

∀i, j ∈ A, i 6= j, ∀u ∈ Ri ∩ Rj

(3.5)

ziju ≥ yiju

∀i, j ∈ A0, i 6= j, ∀u ∈ Ri ∩ Rj

(3.6)

zjiu ≥ y0ju

∀i, j ∈ A, i 6= j, ∀u ∈ Ri ∩ Rj

(3.7)

y0ju + ziju ≤ 1

∀i, j ∈ A, i 6= j, ∀u ∈ Ri ∩ Rj

(3.8)

zjiu ≥ yi0u

∀i, j ∈ A, i 6= j, ∀u ∈ Ri ∩ Rj

(3.9)

yi0u + ziju ≤ 1

∀i, j ∈ A, i 6= j, ∀u ∈ Ri ∩ Rj

(3.10)

∀i, j, k ∈ A, i 6= j 6= k,

∀u ∈ Ri ∩ Rj ∩ Rk

(3.11)

ziju , yiju ∈ {0, 1}

∀i, j ∈ A, i 6= j, ∀u ∈ Ri ∩ Rj

(3.12)

tiu ∈ R+ ∀i ∈ A,

∀u ∈ Ri

(3.13)

i∈A0

X j∈A0

Rumus (3.1) dan (3.2) diyakini bahwa tiap pesawat hanya mempunyai satu pengganti dan hanya satu pesawat sebelumnya (dengan kemungkinan model pesawat) sebagai node u; Rumus (3.3) diyakini bahwa jika yiju = 1, pesawat i dengan nyata menjangkau node u sebelum pesawat j; Rumus (3.4) diyakini bahwa jika y0ju = 1, pesawat j dengan nyata menjangkau node u sebelum seluruh pesawat lainnya; Rumus (3.5) diyakini bahwa jika yi0u = 1, pesawat i dengan nyata menjangkau


12 node u setelah seluruh pesawat lainnya; Rumus (3.1)-(3.5) menjamin bahwa yiju = 1 jika dan hanya jika pesawat j adalah pesawat yang pertama sekali menjangkau node u setelah pesawat i, jika pesawat j diikuti pesawat i secara tepat pada node u(yiju = 1); Rumus (3.6) diyakini bahwa ziju = 1 jika pesawat j adalah pesawat pertama yang menjangkau node u(y0ju = 1); Rumus (3.7) diyakini bahwa zjiu = 1 untuk tiap pesawat i menjangkau node u; Rumus (3.8) ditetapkan bahwa jika pesawat j adalah pesawat pertama yang menjangkau node u, kemudian pesawat j tidak akan diikuti beberapa pesawat lain. Sama halnya dengan humus (3.7) dan (3.8); Rumus (3.9) dan (3.10) ditetapkan bahwa jika pesawat i adalah pesawat terakhir yang menjangkau node u, pesawat i akan mengikuti beberapa pesawat j berikutnya, dan tidak ada pesawat j lainnya yang akan mengikuti pesawat i; Rumus (3.11) dipastikan bahwa jika pesawat j mengikuti pesawat i dengan segera pada node u, kemudian pesawat j juga mengikuti seluruh pesawat k yang kemudian diikuti dengan pesawat i pada node u; Rumus (3.6)-(3.11) didapat sebagai ziju = 1, jika dan hanya jika pesawat j menjangkau node u belakangan dari pesawat i. Jadwal waktu harus mengacu pada kemungkinan kecepatan taxi sebuah pemax sawat, selain itu, untuk sebagian sisi rute Ri , konstanta dmin iuv (dan diuv ) adalah

menunjukkan perolehan waktu minimum (maximum) yang dibutuhkan selama pesawat i berjalan sepanjang sisi (u, v) pada rutenya. Konstanta ini dapat dihitung dengan menggunakan kecepatan minimum (maximum) pesawat i, dan panjang sisi (edge), dimana kecepatan maximum dan minimum dapat berubah jika tepi


13 (edge) adalah berbelok atau lurus, ini menghasilkan ketidaksamaan: max tiu + dmin iuv ≤ tiv ≤ tiu + diuv , ∀(u, v) ∈ Ri , i = 1, . . . , n

(3.14)

Meskipun waktu maximum taxi selama berjalan pada sisinya tidak sesuai dengan kebutuhan, kecepatan waktu taxi dapat dihitung. Untuk menghindari konflik, maka ditentukan jarak pemisah yang ditentukan dengan dsep dimana jarak tersebut dibutuhkan untuk menjaga ujung sayap pesawat dari persinggungan baik dari depan maupun bagian belakang atau bagian lain pesawat pada waktu menyeberang jalur taxi. Dalam kasus dua pesawat searah, pesawat kedua harus dilindungi dari akibat ledakan mesin pesawat yang pertama yang mungkin saja terjadi. Demikian juga jika pemisahan tersebut dilakukan secara visual (atau melalui radar) oleh pengawas dan pilot. Jarak pemisah juga harus mempertimbangkan type pesawat dan juga kondisi jarak pandang. Meskipun ketentuan baku jarak pemisah telah ditentukan dengan dsep = 200m tetapi juga harus mengikuti seluruh peraturan demi terselenggaranya keamanan dan keselamatan seluruh sarana dan prasarana bandara. Untuk tipe konflik searah dan seling menyeberang, hal itu harus cukup menjamin jarak pemisah dari node (titik seberang). Jika 2 pesawat berjalan dalam sisi yang sama (dalam jalur taxi) antara 2 node, pemisahan node ini akan dijalankan untuk 2 pesawat yang saling searah, maka dapat diasumsikan bahwa perjalanan mereka akan menempuh kecepatan yang konstan pada sisinya. Dengan demikian, waktu pemisah yang digunakan adalah Siju = (tiv − tiu ) /l (u, v). dsep menunjukkan perbedaan waktu minimal antara pesawat i dan j menjangkau node u, jika pesawat i menjangkau node u sebelum pesawat j, maka rumus yang dipakai untuk pemisahan tersebut adalah: ziju tju ≥ ziju (tiu + siju ) , ∀i, j ∈ A, i 6= j, ∀u ∈ Ri ∩ Rj


(3.15)

14 Jika jadwal waktu t adalah perhitungan node pada rute, tambahan rumus yang dibutuhkan untuk mencegah konflik akibat kecepatan pesawat yang menyusulnya dari belakang, dirumuskan dengan: ziju − zijv = 0, ∀i, j ∈ A, ∀ (u, v) ∈ Ri ∩ Rj

(3.16)

Rumus ini menyatakan bahwa jika pesawat i menjangkau node u lebih cepat dari pesawat j, kemudian pesawat i tersebut harus menjangkau node v lebih cepat dari pesawat j, dimana kedua pesawat yang memakai jalur taxi (u, v), maka untuk menghindari konflik type head-on (kepala saling berhadapan) maka rumus yang digunakan adalah: ziju − zijv = 0, ∀i, j ∈ A, ∀ (u, v) ∈ Ri with (v, u) ∈ Rj

(3.17)

Jika pesawat i menjangkau node u lebih cepat dari pesawat j, pesawat i harus menjangkau node v lebih cepat dari pesawat j, ketika pesawat i sedang melakukan taxing dari u ke v dan pesawat j dari v ke u. Terdapat nilai maximum dari pesawat yang dapat digunakan dalam posisi menunggu pada tempat parkir (holding point). Model holding point adalah rentetan model ( dan node ) dimana pengaturan sisi E hold dengan length (panjang) 0. Nilai sisi adalah equal (sama) untuk kapasitas tempat parkir (holding point). Terdapat waktu maximum dari satu pesawat pada satu sisi dari sebuah holding point, maka rumus yang dipakai adalah: ziju tju > ziju tiv , ∀i, j ∈ A, ∀ (u, v) ∈ Ri ∩ Rj ∩ E hold

(3.18)

Jika pesawat i menjangkau node u sebelum pesawat j, dan sisi (u, v) adalah bagian dari holding point, kemudian pesawat i harus menjangkau node v sebelum


15 pesawat j menjangkau node u, pada saat pesawat tiba di landasan pacu dan mulai taxing, landasan harus segera dikosongkan, estimasi waktu kedatangan (ETA) dirumuskan dengan: tiui1 = ET Ai, ∀i ∈ Aarr

(3.19)

Pesawat yang berangkat tidak dapat memulai waktu taxinya sebelum pesawat tersebut berada pada Off Block-Time (OBTi ): tiui1 ≥ OBTi ,

∀i ∈ Adep

(3.20)

Pesawat yang akan berangkat harus menyelesaikan taxingnya terlebih dahulu (dan juga harus menjangkau landasan pacu, target waktu pesawat berangkat adalah: tiuik ≤ T T Di,

∀i ∈ Adep

(3.21)

i

Perlu diingat bahwa ui1 adalah node pertama dari rute pesawat i dan uik node terakhir dari rute pesawat i, hal tersebut akan lebih disukai untuk disesuaikan pada skedul (penjadwalan) perjalanan keberangkatan secara sempurna. Pada rumus (21) ketidaksamaan dapat kemudian diganti dengan sebutan persamaan secara luas, hal tersebut dapat dimungkinkan bahwa dengan proses take-off (keberangkatan) sebenarnya dapat ditentukan oleh perintah pada bagian perencanaan keberangkatan, perintah ini dapat diperoleh dari bagian TTD. Untuk membuat kemungkinan ini, seluruh keberangkatan pesawat pada bagian terakhir node (titik keluar landasan pacu) dari rute taxi mereka yang seharusnya dijangkau node dalam keadaan yang sebenarnya. Rumus-rumus dapat ditambah untuk memastikan hal ini. Juga jika mengikuti perencanaan keberangkatan, pesawat j adalah pesawat pertama yang masuk ke landasan pada node u setelah pesawat i, rumus yang ditetapkan adalah yiju = ziju = 1 dan yjiu = zjiu = 0 adalah tambahan.


16 Maka dengan demikian jelaslah, rumus (3.3), (3.4), (3.5), (3.15) dan (3.18) adalah non linear, dimana linear ini dapat dinotasikan dengan nama M , yakni: tiu < tju + (1 − yiju ) M

∀i, j ∈ A, i 6= j, ∀u ∈ Ri ∩ Rj

(3.22)

tiu > tju − (1 − y0ju ) M

∀i, j ∈ A, i 6= j, ∀u ∈ Ri ∩ Rj

(3.23)

tiu > tju − (1 − yi0u ) M

∀i, j ∈ A, i 6= j, ∀u ∈ Ri ∩ Rj

(3.24)

tju − tiu ≥ siju − (1 − ziju ) M

∀i, j ∈ A, i 6= j, ∀u ∈ Ri ∩ Rj

(3.25)

tju > tiv − (1 − ziju ) M

∀i, j ∈ A, ∀ (u, v) ∈ Ri ∩ Rj ∩ E hold

(3.26)

Jika y dan z adalah variabel binari, rumus diatas hanya efektif jika variabel adalah 1, sebaliknya, M jika terpilih cukup luas, sebab rumus ini akan menjadi tidak efektif (misalnya dengan penetapan tiu −tju < M) untuk menjamin bahwa M adalah cukup luas, satu hal dapat diambil untuk penjumlahan dari kemungkinan waktu terlambat dari jangkauan pesawat saat menyelesaikan proses taxi. Dalam meminimalisir penggunaan sumber daya bandara, sasarannya adalah meminimalisir penambahan total waktu taxi untuk seluruh pesawat: min t

X

tiuik − tiui1

i∈A

(3.27)

i

Dimana t adalah faktor penentu seluruh tiu dengan i ∈ A dan u ∈ Ri . Fungsi objektif ini akan menjamin bahwa jalur taxi akan menghabiskan waktu sekecil mungkin. Penggunaan fungsi objektif dapat menjadi penyebab yang tak diingini dari penjadwalan terutama yang berkenaan dengan perencanaan keberangkatan. Waktu keberangkatan sebuah pesawat dapat dicapai sepanjang pesawat tersebut Belum berada pada posisi target waktu keberangkatan pesawat (TTD) pada landasan (holding point/tempat parkir), dimana hal tersebut sering yang menjadi penyebab kemacetan, ini dapat dihindari dengan menetapkan waktu tunggu


17 kedatangan pesawat pada landasan (titik masuk), dengan meminimalisir total waktu yang dihabiskan dari saat pesawat memulai taxi sampai pada TTD (target waktu keberangkatan), maka selama proses kedatangan pesawat tidak akan terjadi konflik serupa. Berikut diberikan fungs objektif: min t

X

X T T Di − tiui1 + tiuik − tiui1

i∈Adep

i∈Aarr

i

Catatan bahwa konstanta T T Di dapat dihilangkan.


(3.28)

BAB 4 MODEL OPTIMISASI PENJADWALAN TAXI BANDARA

Implementasi dari model optimisasi penjadwalan taxi bandara dapat diberikan dalam dua bentuk, yakni per- proses dan rolling horizon (putaran mendatar). Berikut akan dijelaskan kedua implementasi tersebut.

4.1 Per-Proses Problem model taxi telah digambarkan pada bagian sebelumnya, dalam perhitungan seperti dengan memakai Mixed Integer Programming ( MIP ), yang dapat ditunjukkan dengan keputusan yang berubah-ubah dari problem taxi adalah dengan NP-Complete yang mana keputusan ini diambil dari bagian penjadwalan. Dengan data yang bebas NP-Complete dapat diketahui. Pesawat digambarkan bekerja dan saling menyilang. Jika 2 pesawat yang berbeda berjalan pada rute yang berbeda, jika pesawat model kita hubungkan ke job-shop model, maka analisis optimal jadwal taxi mempunyai problem yang berbeda secara tersendiri, dimana kecepatan taxi yang sangat rendah jarang terjadi, dengan sendirinya kecepatannya lebih rendah dari 8 knots (15 km/jam) tidak dapat dijalankan. Sebagian besar waktu pesawat melakukan taxi pada waktu maximum pesawat atau kecepatan minimum pesawat lebih lambat di depan mereka. Pesawat yang hanya bertahan pada jalur taxi tidak akan terjadi. Ini memberi kesan bahwa kecepatan minimum dapat dijalankan. Jika pilihan cukup rendah, ini tidak akan mempengaruhi jadwal optimal. Tanpa kecepatan minimum, dmax iuv akan tidak ter18 Rizki Ismalinda Batubara : Model Optimisasi Untuk Penjadwalan Taxi Bandara, 2009.

19 batas pada kecepatan minimum, oleh karena itu batas sempurna jatuh pada variabel yang dapat menurunkan perhitungan waktu sedemikian rupa. Untuk menurunkan perhitungan waktu tanpa pelaksanaan ketidakmungkinan dan solusi di bawah optimal. Kecepatan minimum 5 knots (≈ 9 km/jam) tampaknya tepat, untuk solusi optimal ini diperlukan pengujian bahwa batas yang dibuat adalah tidak ketat. Mixed Integer problem dapat menyelesaikan perhitungan lebih cepat dan akurat, ketidaksamaan dengan menggunakan kecepatan maximum dan minimum taxi, kemungkinan waktu pesawat tercepat dan terlambat untuk menjangkau node pada rutenya dapat dihitung. Jika jarak ini terjadi pada 2 pesawat yang saling bersamaan waktu (overlap), maka model dapat digunakan sebagai penentu dalam rangkaian node ini. Tapi jika jarak ini tidak overlap, maka rangkaian dapat diketahui dengan mengambil model sebelumnya, sebagai contoh, jika ditentukan perjalanan pesawat i akan menjangkau node u lebih cepat dari pesawat j, dalam setiap kemungkinan jadwal, kita dapat menjumlahkan rumus berikut kedalam perhitungan Ziju = 1 dan Zjiu = 0, dalam langkah per-proses kita akan menambahkan persamaan kedalam rumus untuk mendapatkan perhitungan yang tepat yang diharapkan dapat mengurangi perhitungan waktu.

4.2 Putaran Mendatar (Rolling Horizon) Penggunaan CPLEX (7,5) adalah solusi bagi permasalahan taxi.

Pada

penelitian sebelum yang dilakukan oleh Smeltink dkk pada 2004, yang mengambil sampel dari bandara Schiphol (Amsterdam), dibandara ini ditunjukan sekitar 20 pesawat yang melakukan taxi secara serentak dalam satu waktu. Pada hari sibuk


20 di bandara ini terdapat sekitar 1000 pesawat. Problem jadwal taxi ini dapat diselesaikan dengan menggabungkan beberapa contoh kecil dan menggunakan apa yang disebut dengan rolling horizon algorithm, hal ini diperkirakan dapat memberikan solusi dari permasalahan jadwal taxi. Dalam praktek pendekatan ini sangat berguna, karena pendekatan ini memungkinkan pembaharuan dan rekomputasi. Pendekatan ini juga konsisten dengan sifat penjadwalan taxi secara taktis, yang mana biasanya jadwal dibuat selama 15 sampai 30 menit. Untuk masalah ini tiga variant dari algoritma rolling horizon diimplementasikan sebagai pemecahannya.

4.2.1 Rolling Horizon Variant 1 Variant pertama ini dilakukan dengan perencanaan waktu yang terbagi dalam serangkaian yang terpisah, dengan panjang waktu yang sama dinotasikan dengan T . Jarak interval pesawat didasarkan pada waktu tercepat yang mungkin mereka capai pada waktu proses taxi (OBT untuk keberangkatan, ETA untuk kedatangan). Pesawat dijadwalkan per interval, dan setiap interval dibuat berurutan. Dalam setiap perulangan, interval pesawat terbang dijadwalkan menggunakan MIP formulasi dan CPLEX, dengan perhitungan ini maka rencana interval tercepat dapat dilakukan. Dengan tetap mengambil jadwal taxi pesawat secara berulang-ulang, maka nilai dari variabel keputusan waktu dapat diambil yang mana yang mewakili waktu yang tetap untuk pesawat dalam mencapai node pada rutenya dengan cepat


21 Dalam gambar 4.1 contoh algoritma di sajikan. Dalam i-th interval (dari (i+1) untuk T (i+2)T. sebuah pesawat terbang, c dan d dianggap dalam variant 1, dan c yang dinggap sebagai tetap karena memiliki tumpang tindih dengan interval sebelumnya dan hanya pesawat terbang d dijadwalkan.

Gambar 4.1

Skema contoh Rolling Horizon Varian 1 dan 2. Sumber : Smeltink, dkk., ”An Optimisation Model for Airport Taxi Scheduling”

4.2.2 Rolling Horizon Variant 2 Variant yang kedua adalah sama dengan sebelumnya, tetapi lebih sedikit sulit dan variabel lebih banyak. Interval pesawat telah dijadwalkan akan tetapi pesawat yang dijadwalkan adalah pesawat sebelumnya yakni pesawat yang akan mencapai node pada rutenya. Pada gambar 4.1 ditunjukkan skema contoh Rolling Horizon Varian 1 dan 2. Dalam interval i-th dari (i + 1)T ke (i + 2)T dengan pertimbangan pesawat a, c dan b benar-benar diperhitungkan. Dalam variant 1, a dan c menampakkan kesulitan jika a dan c overlap dan hanya pesawat d yang sesuai dengan jadwal. Pada variant 2, hanya bagian a2 dari a dan c2 dari c yang dijadwal ulang, pesawat d merupakan jadwal yang sempurna.


22 Sebagian rute pesawat ini akan tidak sesuai dengan interval waktu dan ini memungkinkan dibuat penjadwalan ulang. Waktu penjadwalan dapat ditetapkan pada node awal akan tetapi akan sulit dalam penjadwalan pada node akhir.

4.2.3 Rolling Horizon Variant 3 (Sliding Window) Variant yang ketiga, sering disebut sebagai Sliding Window, dalam varian sebelumnya (sebagian) dari pesawat terbang tetap bergantung pada jadwal optimal. Hal ini dapat menimbulkan situasi sulit untuk pesawat terbang lainnya. Sliding Window algoritma akan mencoba untuk menguraikan kesulitan yang tidak dikehendaki ini dan tentunya mempunya efek bagi semua pesawat terbang. Hal ini dilakukan dengan penyortiran daftar pesawat sesuai dengan setiap perulangan m pesawat terbang. Perulangan pesawat pertama 1, . . . , m sudah dijadwalkan. Pada perulangan berikutnya Sliding Window tetap satu pesawat terbang kemudian pesawat terbang 2, . . . , m + 1 dijadwalkan. Hal ini berulang sampai akhirnya pesawat terbang n − m + 1, . . . , n dijadwalkan. Dari keseluruhan jadwal, maka hasil dari salah satu variant tidak perlu dioptimalkan. Bila interval panjang atau Sliding Window dipilih dengan baik, maka ini bisa diambil sebagai ikutan, hal ini disebabkan karena, pertama, rumusan ini dapat digunakan untuk semua pesawat, kemudian jadwal yang dihasilkan valid, aman dan cocok dengan jadwal kedatangan dan keberangkatan pesawat, kedua, pesawat terpisah oleh periode jarak waktu yang hampir signifikan jauh, penjadwalan taxi pesawat akan selalu dapat diatur dalam 2 (dua) jam lebih cepat.


23 Sebuah pesawat terbang yang melakukan proses taxi sesuai dengan jadwal biasanya tidak akan dipengaruhi oleh pesawat terbang yang melakukan proses taxi dua jam sebelumnya. Pesawat yang melakukan proses taxi dalam interval waktu kecil (dan mereka terbagi dalam beberapa bagian dari rute). Meskipun algoritma jadwal interval sekarang optimal, akan tetapi hal ini tidak bisa dijamin tetap untuk pesawat terbang pada waktu berikutnya dan dengan demikian pesawat terbang ini tergantung pada pesawat terbang berikutnya. interval yang terlalu kecil akan relatif memberikan kesulitan bagi pesawat. Dan ini memungkinkan jadwal pesawat terbang lainnya mustahil dilakukan tetap seperti semula, jika panjang interval yang dipilih terlalu besar, maka model MIP kemungkinan akan menghasilkan perhitungan yang besar pula.

4.3 Hasil Implementasi Penganalisaan formulasi MIP dan efek per-proses telah dilakukan oleh J.W. Smeltink dkk, dengan mengambil sampel Bandara Schipol msterdam. Penganalisaan ini dilakukan dengan mengambil 12 sampel dimana waktu yang diambil sekitar 30 menit pada persamaan min t

X i∈Adep

(T T Di − tiui1 ) +

X i∈Aarr

(tiuik

i

−tiui

)

1

digunakan sebagai waktu minimum taxi, kecepatan ditetapkan sampai 5 knots dan jarak pemisahan sekitar 200 meter. Waktu keberangkatan (TTD) ditetapkan sebagai pilihan. Sebagaimana diterangkan dalam sub 4.1 per-proses maka langkah dan formulasi dilakukan pada tahap ini adalah dengan memasukkan beberapa variabel


24 binary z, dengan menambahkan formulasi MIP kedalam perhitungan. Smeltink dkk menyebutnya sebagai Envolved Varibel (Variabel Sulit) dan variabel binary lainnya sebagai variabel bebas. Jika beberapa persamaan dapat ditambahkan maka perhitungan waktu diharapkan menjadi lebih rendah. Semua perhitungan dilakukan dengan program dengan sistem operasinya pada Linux sedangkan program pemecahannya dengan menggunakan program CPLEX, yang menggunakan cabang yang terikat dan memotong cabang dan algoritma. Hasilnya dapat dilihat dalam Tabel 4.1. Hasil per-proses merupakan hasil perbaikan yang signifikan dalam perhitungan waktu, apabila jumlah urutan variabel tetap besar. Hasilnya menunjukkan bahwa per kasus yang diproses sampai berisi sekitar 2000 urutan variabel bebas dapat dijadwalkan dalam waktu yang wajar. Setelah jumlah urutan variabel bebas menjadi terlalu besar (contoh 4,8 dan 12 pada Tabel 4.1) dari optimal. Solusi tidak dapat ditemukan dalam 1000 detik. Kejadian dengan kurang dari 20 pesawat terbang tidak mungkin berisi lebih dari 2000 urutan variabel bebas, maka yang akan digunakan adalah jumlah pesawat terbang yang praktis mendekati batas tertinggi (upperlimit) sebagai contoh, dengan catatan, bahwa perhitungan waktu juga dipengaruhi oleh faktor-faktor yang tidak diketahui (seperti pilihan percabangan variabel oleh CPLEX). Waktu yang padat merupakan saat yang tepat yang dapat dijadikan test pada masalah ini. Dimisalkan oleh Smeltink, dkk., yakni dengan mengambil contoh Bandara Schiphol Amsterdam yang digunakan untuk menguji rolling horizon algoritma. Pada hari Minggu pada bulan september 2002 antara 11.30 sampai dengan 17.00 merupakan hari yang dijadikan test bagi kelompok ini, dimana ka-


25 pasitas bandara meningkat tajam yang terdiri dari 406 pesawat : 189 pesawat yang tiba dan 217 pesawat yang berangkat. Permasalahannya dapat ditest secara realistis tetapi kenyataannya masalah besar masih yang didapati. Perbedaan jadwal, adalah waktu ideal yang dimiliki pesawat pada waktu melakukan proses taxi dibandara dengan waktunya dibutuhkan ketika pesawat berada di Airport, dan tidak aktif. Perhitungannya dapat dilihat sebagai berikut:

Tabel 4.1

Contoh 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12.

Contoh perkiraan 30 menit hasil dari 12 contoh pesawat pada Amsterdam Airport Schiphol. Sumber : Smeltink, dkk., ”An Optimisation Model for Airport Taxi Scheduling” Proses Keberang- Kedatangan katan 11 14 14 17 15 24 19 31 20 12 19 14 18 16 24 30 22 9 17 13 19 4 21 3

Variabel Tetap bebas 2156 3024 2984 7124 4942 3704 4012 9432 3832 3916 2064 1096

1324 1192 1164 3980 976 1228 1312 3820 1604 840 808 2868

Waktu Tidak Per-Proses Per-Proses 18,35 39,35 33,05 33,05 27,18 16,75 (***) (***) 20,88 11,64 74,39 36,6 37,14 6,11 (***) (***) 590 96,76 18,45 9,7 6,08 1,95 (***) (***)

Kolom kedua dan ketiga menunjukkan urutan kedatangan dan keberangkatan pesawat. Kolom keempat dan relima menunjukkan urutan variabel sulit dan variabel bebas (integer) variabel dalam formulasi MIP. Dua kolom terakhir menunjukkan perhitungan waktu dalam detik dengan dan tanpa per-proses. (***) diindikasikan sebagai problem yang tidak terpecahkan dalam 1000 detik.


26 Dalam simulasi ini, tibanya pesawat pada ETA dan pesawat di OBT. Komplik potensial diselesaikan dengan yang pertama datang yang pertama dilayani, dari penggunaan tipe ini diperoleh hasil keputusannya rata-rata 20% lebih rendah dari jadwal ideal pesawat. Pada variant 1 pada rolling horizon algoritma hasil tidak mungkin didapat pada panjang jarak T selama 10 menit, indikasinya bahwa panjang jarak begitu rendah, karena perhitungan jarak relatif panjang dalam interaksi ini, panjang jarak yang dimungkinkan untuk jadwal pesawat lainnya sangat sukar diambil, ditentukan panjang jarak T dari 15 menit diberikan sebagai solusi. Algoritma yang dibentuk kira-kira 24 item dan hasilnya 17 pesawat dijadwalkan setiap itemnya, Total perhitungan waktu adalah 1300 detik. Satu rincian diberikan lebih panjang 500 detik, karena ada beberapa variabel bebas dalam bagian ini, hasil dari hitungan pada bagian ini adalah kira-kira 30 detik, diberikan pada Tabel 4.2 hasil waktu taxi hanya 4 detik lebih tinggi daripada yang lainnya, hasil hitungan waktu pesawat hanya 2% lebih rendah daripada jadwal yang diidealkan dalam situasi ini, dimunculkan simulasi data, kira-kira 20% standard deviasinya lebih kecil, artinya, keterlambatan akan lebih tinggi dari situasi ini.

Tabel 4.2

Penggunaan 3 (tiga) variant yang berbeda yang ditunjukkan dalam waktu rata-rata dan Standard deviasi. Sumber : Smeltink, dkk., ”An Optimisation Model for Airport Taxi Scheduling”

Total Taxi Time Ideal Taxi Time

Variant 1 Variant 2 Variant 3 Simulasi Rata- Std. Rata- Std. Rata- Std. Rata- Std. Rata Rata Rata Rata 1,02 0,11 1,02 0,10 1,02 0,08 1,2 0,4


27 Pada gambar 4.2 keterlambatan TTD sampai kelihatan. 339 dari 406 pesawat direncanakan berikutnya untuk jadwal waktu yang ideal, sisanya 67 dihabiskan pada rata-rata hampir 10 detik lebih pada waktu pesawat melakukan taxi (atau menunggu pada landasan pacu), kemudian dalam jadwal ideal mereka, keterlambatan paling besar adalah 79 detik.

Gambar 4.2

Grafik keterlambatan per pesawat dalam detik yang diperoleh dengan variant pertama rolling horizon. Sumber : Smeltink, dkk., ”An Optimisation Model for Airport Taxi Scheduling”

Untuk rolling horizon 2 jarak interval dari 10 menit menjadi tidak mungkin dilakukan, yang mana T adalah sekitar 15 menit, algoritma kira-kira dibutuhkan 24 perulangan dengan jumlah perhitungan kira 844 detik, yang mana hasilnya lebih 30 detik perulangan. Statistik yang ditunjukkan pada variant 2 sebagai daftar Tabel 4.2 hampir berbeda dari variant 1, pada gambar 4.3 keterlambatan TTD terlihat 388 dari 406 pesawat dijadwalkan. Jadwalnya diidealkan (disamakan). Jadwal ini adalah salah satu kekurangan dari pesawat pada variant 1, 68 yang diterbangkan hasilnya hampir 9 detik lebih cepat dari pada jadwal yang diidealkan, meskipun pesawat satu lebih terlambat, hasil keterlambatnya rendah, keterlambatannya lebih tinggi kira-kira 79 detik pada variant 1.


28

Gambar 4.3

Grafik keterlambatan per pesawat dalam detik diperoleh dengan perhitungan rolling horizon variant kedua. Sumber : Smeltink, dkk., ”An Optimisation Model for Airport Taxi Scheduling”

Dengan sliding window algoritma (variant 3), nomor perulangan dan perhitungan waktu akan lebih besar daripada variant sebelumnya, yang mana penggunaan sliding window (m) dari 15 pesawat, perhitungan waktunya sekitar 9453 detik, hasilnya per-perulangan kira-kira 23 detik, kecuali keterlambatan yang sama diluar jalur pesawat dari pada variant sebelumnya, ini dapat dilihat dengan standar deviasinya menurun dari ratio antara total dan waktu ideal. Gambar 4.4 menunjukkan bahwa keterlambatan adalah 332 dari 406 pesawat penjadwalan variant 3 (sliding window) menjadi ideal dibanding variant 1 dan variant 2 yakni 339 dan 338 dari 406 pesawat. Rata-rata keterlambatan pesawat lain sekarang hanya 8 detik (9 dan 10 detik dengan metode lain), keterlambatan sekarang sekitar 69 detik, 10 detik lebih pendek dari variant sebelumnya.


29

Gambar 4.4

Grafik keterlambatan per pesawat dalam detiknya diperoleh dengan perhitungan rolling horizon variant ketiga (sliding window). Sumber : Smeltink, dkk., ”An Optimisation Model for Airport Taxi Scheduling”

15 menit dapat menjadi pilihan untuk interval waktu pada metode pertama dan kedua, masa 10 menit menjadi tidak mungkin terlaksana, waktu pada umumnya menghasilkan perhitungan lebih panjang. Terdapat 15 pesawat yang terpilih dari sliding window untuk alasan yang sama. Semua metode mempunyai kelebihan dan kekurangan. Rata-rata waktu pesawat yang diperhitungkan adalah 2 % lebih panjang daripada jadwal yang diidealkan. Simulasi yang ditunjukkan sekitar 20%. Lebih dari 80% pesawat yang melakukan proses taxi mengikuti jadwal ideal yang dipakai umumnya. Pesawat lainnya menghabiskan waktu yang banyak untuk taxi, tetapi tidak lebih dari 80 detik per pesawat. Meskipun sliding window menghasilkan penjadwalan yang mana keterlambatan pesawat hampir semua sama, perhitungan waktu dari algoritma ini lebih luas dari 2 methode lain hal ini disebabkan karena perulangan juga lebih besar.


BAB 5 KESIMPULAN

Dalam studi ini, ada 3 varian dari algoritma yang dibuat dan diteliti dan digunakan untuk memecahkan masalah penjadwalan taxi. Algoritma ini dapat digunakan untuk taktik penjadwalan taxi. Dari 3 variant tersebut, rolling horizon algoritma menjadi pilihan, dimana problem dibagi kedalam bagian tersendiri dari nomor terkecil pesawat. Untuk membuat penjadwalan selama sehari penuh, solusinya adalah menggabungkan beberapa sub-problem, sub-problem dipecahkan dengan menggunakan formulasi MIP. Dengan formulasi dan per-proses, CPLEX dapat digunakan untuk memecahkan contoh-contoh kasus sampai pada 20 pesawat dengan waktu yang layak. Dua variant pertama menggunakan interval waktu yang sulit untuk dipecahkan ke dalam bagian dari masalah. Varian ke 3 adalah sliding window algoritma. Keuntungan dari rolling horizon algoritma adalah bahwa tanpa beberapa upaya, penjadwalan dapat direncanakan ulang, dari point waktu yang pasti untuk diikuti dengan situasi terkini dari bandara. Sebagai studi kasus digunakan oleh Smeltink dkk adalah sebuah bandara di msterdam yang bernama Schiphol, dengan mengambil sampel pada hari tersibuk dari contoh ini. Dari 406 jadwal pesawat dalam kurun waktu 5,5 jam. Penggunaan optimisasi algoritma sangat mungkin untuk menurunkan keterlambantan pesawat dari 20% sampai 2%, dimana waktu ideal taxi digunakan sebagai batas terendah


31 untuk solusi yang diperoleh. Penurunan dari keterlambatan taxi ini membuat proses taxi lebih effesien, dan juga berpengaruh pada lingkungan (terutama emisi) yang mana penurunannya sampai pada level yang layak (ramah lingkungan). Ketiga variant tersebut menunjukkan hasil yang sama dengan yang ditunjukkan fungsi objektif, yang pertama, 2 variant dengan interval waktu yang sulit, diperoleh hasil terbaik dengan penghitungan waktu dari variat ketiga (sliding window) : 1300, 844 dan 9453 detik yang memenuhi. Sejak studi ini digunakan untuk inisial model dan algoritma, maka diharapkan perhitungan waktu dapat diturunkan. Pendekatan rolling horizon adalah layak untuk dinamika lingkungan dan operasional pada bandara, dimana umumnya terlihat bahwa waktu tidak menjadi pertimbangan dalam perencanaan semula. Dengan studi ini penjadwalan selalu dapat diubah dengan sempurna (seperti pelaksanaan delay-delay pesawat). Terlebih lagi demonstratif contoh masalah dipisahkan dalam sub problem terkecil dan juga tidak berakibat pada kualitas dari keseluruhan pemecahan masalah yang diperoleh.


DAFTAR PUSTAKA

Anagnostakis. I., J-P Clarke, 2003 Runway Operations Planning : A Two-Stage Solution Methodology, Hawaii International Conference on System Sciences (HICSS’03) -36. Andersson. K., F. Carr, E. Feron, dan W.D. Hall, 2000, Analysis and Modeling of Ground Operations at Hub Airports, USA/Europe Air Traffic Management R&D Seminar, Napoli-3. Bolat A., 2001., Model and a genetic algorithm for a static aircraft-gate assignment problems, J. Oper. Res. Soc, 52 : 1107-1120. Carr F, A Evans, J-P, Clarke and E. Feron., 2002., Modeling and Control of Airport Queueing Dynamics under Server Flow Restrictions, American Control Conference. Cheng Y., 1998., Solving push-out conflicts in apron taxiways of airports by a network based simulation, Computer Industrial Engineering 2 : 351-369 Garey M.R., and D.S. Johnson., 1979., Computers and Intractability : A Guide to the Theory of NP-Completences, W.H. Freeman, New York. Idris H., J-P. Clarke, R. Bhuva, and L Kang., 2002., Queuing Model for Taxi Time Estimation, ATC Quarterly, 10 : 1-22. Nemhauser G.L., L.A. Wolsey., 1988., Integer and Combinatorial Optimization, John Wiley and Sons, New York. Papadimitrion C.H and K. Steiglitz., 1982., Combinatorial Optimizations : Algorithms and Complexity, Prentice-Hall, Englewood Cliffs. Pitfield D.E., A.S. Brooke dan E.A. Jerrard., 1998., A Monte-Carlo simulation of potentially conflicting ground movements at a new international airport, Journal of Air Transport Management 4 : 3-9. Smeltink, J.W., M.J. Soomer., P.R. de Waal dan R.D. van der Mei., 2004., An Optimisation Model for Airport Taxi Scheduling. Williams H.P., 1993., Model Building in Mathematical Programming, 3rd edition, John Wiley and Sons, Chichester,


MODEL OPTIMISASI UNTUK PENJADWALAN TAXI BANDARA

Recommend Documents