Name
Title | ||
|---|---|---|
A New Variant of the Minimum-Weight Maximum-Cardinality Clique Problem to Solve Conflicts between Aircraft |
Abstract | ||
|---|---|---|
In this article, we formulate a new variant of the problem of finding a maximum clique of minimum weight in a graph applied to the detection and resolution of conflicts between aircraft. The innovation of the model relies on the cost structure: the cost of the vertices cannot be determined a priori, since they depend on the vertices in the clique. We apply this formulation to the resolution of conflicts between aircraft by building a graph whose vertices correpond to a set of maneuvers and whose edges link conflict-free maneuvers. A maximum clique of minimal weight yields a conflict-free situation involving all aircraft and minimizing the costs induced. We solve the problem as a mixed integer linear program. Simulations on a benchmark of complex instances highlight computational times smaller than 20 seconds for situations involving up to 20 aircraft. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-319-18161-5_1 | MODELLING, COMPUTATION AND OPTIMIZATION IN INFORMATION SYSTEMS AND MANAGEMENT SCIENCES - MCO 2015, PT 1 |
Keywords | Field | DocType |
Air Traffic Control,Conflict Resolution,Maximum Clique,Mixed Integer Linear Programming | Integer,Discrete mathematics,Mathematical optimization,Clique,Vertex (geometry),Computer science,A priori and a posteriori,Cardinality,Minimum weight,Linear programming,Clique problem | Conference |
Volume | ISSN | Citations |
359 | 2194-5357 | 1 |
PageRank | References | Authors |
0.36 | 7 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Thibault Lehouillier | 1 | 1 | 0.36 |
| Jérémy Omer | 2 | 13 | 3.80 |
| François Soumis | 3 | 821 | 97.64 |
| Guy Desaulniers | 4 | 874 | 62.90 |