High level rule modelling language for airline crew pairing: Design and implementation

Abstract

Ekip eşleme problemi, uçuş ağındaki her bir uçuşu kapsayan en az maliyetli eşleme (tek bir ekip tarafından uçurulan ardışık uçuşlar) kümesinin arandığı bir havayolu optimizasyon problemidir. Bir eşleme, uluslararası ve ulusal kural koyucular ve havayolu şirketinin kendisi tarafından düzenlenen bir çok karmaşık geçerlilik kurallar kümesi kullanılarak tanımlanır. Bir eşlemenin maliyeti de bazı yine karmaşık kurallar kullanılarak tanımlanır. Ne var ki bu kurallar sabit değildir. Havayolu şirketleri her planlama döneminde çeşitli senaryolar denerler. Bu çalışmada, geçerlilik ve maliyet hesaplama kurallarının tanımlanmasında kullanılacak bir üst düzey dil tasarlanmıştır. Böyle bir alana özgü dil kullanılarak, havayolu şirketleri geçerlilik ve maliyet hesaplama kurallarını kolayca belirtebilir. Bu dil için, geçerlilik kontrolü ve maliyet hesaplama fonksiyonları sağlayan bir dinamik kütüphane oluşturan bir derleyici de gerçekleştirilmiştir.

The crew pairing problem is an airline optimization problem where a set of least costly pairings (consecutive flights to be flown by a single crew) that covers every flight in a given flight network is sought. A pairing is defined by using a complex set of feasibility rules imposed by international and national regulatory agencies, and also by the airline itself. The cost of a pairing is also defined using some complicated rules. When an optimization engine generates a sequence of flights from a given flight network, it has to check all these feasibility rules to understand if the sequence is a valid pairing, and has to calculate the cost of the pairing by using the cost calculation rules. However the feasibility and cost calculation rules are not usually stable. Airline companies try several scenarios in each planning period. In this work, a high level language for describing the feasibility and cost calculation rules is designed. Airline companies can use such a domain specific language to specify the rules for feasibility and cost calculation. A compiler for this language is also implemented which generates a dynamic library implementing the specified rules.