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.

Constraint-based aircraft routing / M. Paltrinieri, A. Momigliano, F. Torquati. - In: INTERNATIONAL JOURNAL OF EXPERT SYSTEMS. - ISSN 0894-9077. - 8:4(1995), pp. 349-373.

Constraint-based aircraft routing

A. Momigliano
Secondo
;
1995

Abstract

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.
engineering (all)
Settore INF/01 - Informatica
Article (author)
File in questo prodotto:
File Dimensione Formato  
1.ar.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 20.31 MB
Formato Adobe PDF
20.31 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/243458
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact