Constraint-based aircraft routing

This paper gives a formal description of the problem of aircraft routing and its solution developed in OMAR (Operative Management of Aircraft Routing), a system implemented with Bull HN for Alitalia. Aircraft routing is an example of vehicle scheduling, a problem for which no polynomial exact solution is known. Our basic philosophy is to look at aircraft routing as a Constraint Satisfaction Problem (CSP) and to adapt the most effective CSP techniques to solve it under the response time required by an interactive system. Constraints relevant to the problem are formulated as relations between flights. They are divided into two subclasses: structural constraints are demonstrated to be characteristic of all solutions; technical constraints exhibit the conditions of the problem at hand. Joins of constraints are defined and propagated through the network of relations to restrict variable domains. Some of the relevant properties of the simplified network are deduced. Routing is then represented as a search process in the state spaces of partial schedules performed by a branch-and-bound algorithm. We provide a lower bounding function of very easy computation that, in absence of technical constraints, is also a criterion sufficient for the process to be backtrack free. Otherwise, it is used to control the search in conjunction with heuristics inspired to the first fail principle.