Sidang Tugas Akhir

Evi Noviani
G54101003

Penyelesaian Masalah Crew Pairing dengan Menggunakan Teknik Pembangkitan Kolom

Perusahaan penerbangan merupakan salah satu industri yang kompleks. Perusahaan ini dihadapkan pada berbagai persoalan dalam memenuhi permintaan calon penumpang dan upaya untuk memaksimumkan keuntungan. Perusahaan harus menghadapi masalah penjadwalan pesawat terbang yang akan digunakan, menentukan jadwal penerbangan, menentukan jadwal crew (pekerja) yang akan menjalankannya, dan lain sebagainya. Salah satu masalah pada perusahaan penerbangan adalah masalah penjadwalan penerbangan yang dilaksanakan oleh sejumlah crew (pekerja). Masalah penjadwalan penugasan crew pada penerbangan disebut masalah crew scheduling (Airline Crew Scheduling Problem) yang berkaitan dengan penjadwalan dalam skala besar. Suatu perusahaan penerbangan harus memenuhi sejumlah jadwal penerbangan dalam periode waktu tertentu. Jadwal penerbangan berupa sejumlah flight segment, yaitu penerbangan nonstop dari suatu tempat ke tempat lain. Beberapa flight segment tersebut dapat disusun menjadi suatu flight service. Flight service adalah penerbangan yang merupakan rangkaian dari beberapa flight segment yang berurutan. Untuk melaksanakan semua jadwal penerbangan, perusahaan tersebut memerlukan sejumlah crew dan menygaskannya pada crew pairing. Crew pairing adalah sebuah rangkaian penerbangan (flight service) yang harus dilaksanakan oleh crew, berangkat dan tiba pada sebuah pangkalan (base) tertentu. Pemilihan rangknaian penerbangan yang dilakukan oleh sejumlah perkerja tersebut dapat dimodelkan sebagai set covering problem dengan banyaknya variabel jauh lebih besar dibandingkan dengan banyaknya kendala yang jika diselesaikan dengan metode simpleks akan menghabiskan waktu yang lama. Penyelesaian masalah set covering dalam skala besar diantaranya dapat menggunakan teknik pembangkitan kolom (column generation). Teknik pembangkitan kolom ini merupakan teknik penyelesaian masalah yang hanya menggunakan sebagian variabel saja untuk menghasilkan solusi optimal dari maslah utama. Dari teknik pembangkitan kolom akan dihasilkan suatu himpunan crew pairing dengan biaya minimum yang dapat menjalankan seluruh penerbangan yang telah dijadwalkan.