Fleet type assignment and robust airline scheduling with chance constraints under environmental emission considerations

Abstract

Filo tipi atama ve gürbüz havayolu çizelgelemesi, uçakların rotalara optimal bir şekilde atanması ve aksamalara karşı dayanıklı bir uçuş çizelgesi geliştirilmesi anlamına gelir. Bu çalışmada; yakıt tüketimi CO2 emisyonu, atıl zaman ve taşan yolcu maliyetlerini en aza indirmeyi hedefleyen ve yolcuların bağlantı hizmet seviyelerini sağlamak amacıyla, kontrol edilebilen seyir zamanı ve atıl zaman kullanılarak, Karma Tamsayılı Doğrusal Olmayan Programlama formulasyonu geliştirilmiştir. Modelin kritik katkısı, yetersiz oturma kapasitesinden kaynaklı taşan yolcu maliyetiyle birlikte atıl zaman yerleştirmeyi telafi etmek amacıyla uçağın yakıt verimliliğini hesaba katmasıdır. Kontrol edilebilir seyir süreleleriyle ilişkili yakıt tüketim fonksiyonundaki doğrusalsızlık, ikinci derece konik reformülasyonlarla işlenmiştir. Buna ek olarak, seyir dışı sürede bulunan bir raslantısal değişkeninden kaynaklanan belirsizlik, yolcu bağlanma hizmet seviyesini garanti etmek üzere şans kısıtlarında ortaya çıkmaktadır ve bu da, konik eşitsizliklere dönüştürülerek ele alınmıştır. Önerilen model tarafından oluşturulan planlamanın performansını ABD'li büyük bir havayolu şirketi tarafından yayımlanan planla karşılaştırdık. Yayımlanan plana kıyasla toplamda ortalama %20'lik bir maliyet tasarrufu sağlandı. Büyük ölçekli problemleri makul bir zamanda çözmek için de, problemi, filo tipi ataması ve gürbüz çizelgeleme gibi planlama aşamalarına ayıran ve sonra sırasıyla çözen iki aşamalı bir algoritma geliştirdik.Anahtar sözcükler: filo tipi atama, uçuş çizelgeleme, kontrol edilebilir seyir zamanları, konik eşitsizlikler, şans kısıtları

Fleet Type Assignment and Robust Airline Scheduling is to assign optimally aircraft to paths and develop a flight schedule resilient to disruptions. In this study, a Mixed Integer Nonlinear Programming formulation was developed using controllable cruise time and idle time insertion to ensure passengers' connection service level with the objective of minimizing the costs of fuel consumption, $CO_2$ emissions, idle time and spilled passengers. The crucial contribution of the model is to take fuel efficiency of aircraft into considerations to compensate for the idle time insertion as well as the cost of spilled passengers due to the insufficient seat capacity. The nonlinearity in the fuel consumption function associated with controllable cruise time was handled by second order conic reformulations. In addition, the uncertainty coming from a random variable of non-cruise time arises in chance constraints to guarantee passengers' connection service level, which was also tackled by transforming them into conic inequalities. We compared the performance of the schedule generated by the proposed model to the published schedule for a major U.S. airline. On the average, there exists a 20$/%$ total cost saving compared to the published schedule. To solve the large scale problems in a reasonable time, we also developed a two-stage algorithm, which decomposes the problem into planning stages such as fleet type assignment and robust schedule generation, and then solves them sequentially.Keywords: fleet type assignment, airline scheduling, cruise time controllability, second order conic programming, chance constraints