Solving the Air Conflict Resolution Problem under Uncertainty using an Iterative Bi-Objective Mixed Integer Programming Approach

Autor: François Soumis, Jérémy Omer, Guy Desaulniers, Moncef Ilies Nasri, Thibault Lehouillier
Přispěvatelé: École Polytechnique de Montréal ( EPM ), Groupe d’études et de recherche en analyse des décisions ( GERAD ), École Polytechnique de Montréal ( EPM ) -McGill University-HEC Montréal ( HEC Montréal ) -Université du Québec à Montréal ( UQAM ), Institut de Recherche Mathématique de Rennes ( IRMAR ), Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -AGROCAMPUS OUEST-École normale supérieure - Rennes ( ENS Rennes ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National des Sciences Appliquées ( INSA ) -Université de Rennes 2 ( UR2 ), Université de Rennes ( UNIV-RENNES ) -Centre National de la Recherche Scientifique ( CNRS ), Institut National des Sciences Appliquées - Rennes ( INSA Rennes ), This work was carried out under the project OPR-601 funded by the CRIAQ (Consortium on Research and Innovation in Aerospace in Quebec), École Polytechnique de Montréal (EPM), Groupe d’études et de recherche en analyse des décisions (GERAD), École Polytechnique de Montréal (EPM)-McGill University = Université McGill [Montréal, Canada]-HEC Montréal (HEC Montréal)-Université du Québec à Montréal = University of Québec in Montréal (UQAM), Institut de Recherche Mathématique de Rennes (IRMAR), AGROCAMPUS OUEST, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Université de Rennes 2 (UR2), Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA), Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-École normale supérieure - Rennes (ENS Rennes)-Université de Rennes 2 (UR2)-Centre National de la Recherche Scientifique (CNRS)-INSTITUT AGRO Agrocampus Ouest, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro), Institut National des Sciences Appliquées (INSA)
Jazyk: angličtina
Rok vydání: 2017
Předmět:
[ MATH.MATH-OC ] Mathematics [math]/Optimization and Control [math.OC]
Mathematical optimization
Air Traffic Management
Monte Carlo method
0211 other engineering and technologies
Minimum weight
Transportation
ComputerApplications_COMPUTERSINOTHERSYSTEMS
02 engineering and technology
Multi-objective optimization
Air Traffic Control
Control theory
0502 economics and business
Integer programming
Civil and Structural Engineering
Mathematics
[ INFO.INFO-RO ] Computer Science [cs]/Operations Research [cs.RO]
Clique
050210 logistics & transportation
021103 operations research
05 social sciences
[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Uncertainties
Expression (mathematics)
Mixed Integer Linear Programming
Multi-Objective Programming
Graph (abstract data type)
[MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
Zdroj: Transportation Science
Transportation Science, INFORMS, 2017, 〈10.1287/trsc.2016.0714〉
Transportation Science, INFORMS, 2017, 51 (4), pp.1242-1258. ⟨10.1287/trsc.2016.0714⟩
Transportation Science, 2017, 51 (4), pp.1242-1258. ⟨10.1287/trsc.2016.0714⟩
ISSN: 0041-1655
1526-5447
DOI: 10.1287/trsc.2016.0714〉
Popis: International audience; In this paper, we tackle the aircraft conflict resolution problem under uncertainties. We consider errors due to the wind effect, the imprecision on the aircraft speed prediction, and the delay in the execution of maneuvers. Using a geometrical approach, we derive an analytical expression for the minimum distance between aircraft, along with the corresponding probability of conflict. These expressions are incorporated into an existing deterministic model for conflict resolution. This model solves the problem as a maximum clique of minimum weight in a graph whose vertices represent possible maneuvers and where edges link conflict-free maneuvers of different aircraft. We then present a solution procedure focusing on two criteria, namely fuel efficiency and the probability of re-issuing maneuvers in the future: we iteratively generate solutions of the Pareto front to provide the controller with a set of possible solutions where he/she can choose the one corresponding the most to his/her preferences. Intensive Monte-Carlo simulations validate the expressions derived for the minimum distance and the probability of conflict. Computational results highlight that up to 10 different solutions for instances involving up to 35 aircraft are generated within three minutes.
Databáze: OpenAIRE
Externí odkaz: