Two decomposition algorithms for solving a minimum weight maximum clique model for the air conflict resolution problem

Thibault Lehouillier, Jérémy Omer, François Soumis and Guy Desaulniers

European Journal of Operational Research, 2017, vol. 256, issue 3, 696-712

Abstract: In this paper, we tackle the conflict resolution problem using a new variant of the minimum-weight maximum-clique model. The problem involves identifying maneuvers that maintain the required separation distance between all pairs of a set of aircraft while minimizing fuel costs. We design a graph in which the vertices correspond to a finite set of maneuvers and the edges connect conflict-free maneuvers. A maximum clique of minimal weight yields a conflict-free situation that involves all the aircraft and minimizes the costs induced. The model uses a different cost structure compared to classical clique search problems: the costs of the vertices cannot be determined a priori, since they depend on the vertices in the clique. We formulate the problem as a mixed integer linear program. Since the modeling of the aircraft dynamics and the computation of trajectories is separated from the solution process, our mathematical framework is valid for any hypotheses on the aircraft dynamics and any choice of the available maneuvers. In particular, the aircraft can perform dynamic velocity, heading, and flight-level changes. To solve instances involving a large number of aircraft spread over several flight levels, we introduce two decomposition algorithms. The first is a sequential mixed integer linear programming procedure that iteratively refines the discretization of the maneuvers to yield a trade-off between computational time and cost. The second is a large neighborhood search heuristic that uses the first procedure as a subroutine. The best solutions for the available set of maneuvers are obtained in less than ten seconds for instances with up to 250 aircraft randomly allocated to bisten flight levels.

Keywords: Air traffic control; Conflict resolution; Mixed integer linear optimization; Minimum weight maximum clique; Decomposition methods (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221716305458
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:256:y:2017:i:3:p:696-712

DOI: 10.1016/j.ejor.2016.07.008

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().