Mixed-integer nonlinear programming for aircraft conflict avoidance by sequentially applying velocity and heading angle changes.

*(English)*Zbl 1402.90094Summary: We consider the problem of aircraft conflict avoidance in air traffic management systems. Given an initial configuration of a number of aircraft sharing the same airspace, the main goal of conflict avoidance is to guarantee that a minimum safety distance between each pair of aircraft is always respected during their flights. We consider aircraft separation achieved by heading angle deviations, and propose a mixed 0-1 nonlinear optimization model, that is then combined with another one which is based on aircraft speed regulation. A two-step solution approach is proposed, where the two models are sequentially solved using a state-of-the-art mixed-integer nonlinear programming solver. Numerical results validate the proposed approach and clearly show the benefit of combining the two considered separation maneuvers.

##### MSC:

90C11 | Mixed integer programming |

90C30 | Nonlinear programming |

90C90 | Applications of mathematical programming |

90C26 | Nonconvex programming, global optimization |

##### Keywords:

air traffic management; conflict avoidance; mixed-integer nonlinear programming; deterministic global optimization; modeling
PDF
BibTeX
Cite

\textit{S. Cafieri} and \textit{R. Omheni}, Eur. J. Oper. Res. 260, No. 1, 283--290 (2017; Zbl 1402.90094)

Full Text:
DOI

##### References:

[1] | Achterberg, T., SCIP: solving constraint integer programs, Mathematical Programming Computation, 1, 1, 1-41, (2009) · Zbl 1171.90476 |

[2] | Alonso-Ayuso, A.; Escudero, L. F.; Martín-Campo, F. J., Collision avoidance in air traffic management: A mixed-integer linear optimization approach, IEEE Transactions on Intelligent Transportation Systems, 12, 1, 47-57, (2011) |

[3] | Alonso-Ayuso, A.; Escudero, L. F.; Martín-Campo, F. J., A mixed 0-1 nonlinear optimization model and algorithmic approach for the collision avoidance in ATM: velocity changes through a time horizon, Computers & Operations Research, 39, 12, 3136-3146, (2012) · Zbl 1349.90641 |

[4] | Alonso-Ayuso, A.; Escudero, L. F.; Martín-Campo, F. J., An exact multi-objective mixed integer nonlinear optimization approach for aircraft conflict resolution, TOP, 24, 2, 381-408, (2016) · Zbl 1342.90108 |

[5] | Alonso-Ayuso, A.; Escudero, L. F.; Martn-Campo, F. J., Exact and approximate solving of the aircraft collision resolution problem via turn changes, Transportation Science, 50, 1, 263-274, (2016) |

[6] | Belotti, P.; Lee, J.; Liberti, L.; Margot, F.; Wachter, A., Branching and bounds tightening techniques for non-convex MINLP, Optimization Methods Software, 24, 4-5, 597-634, (2009) · Zbl 1179.90237 |

[7] | Brochard, M., Erasmus - en route air traffic soft management ultimate system, Technical Report, (2006), Eurocontrol Experimental Centre |

[8] | Bussieck, M. R.; Drud, A. S.; Meeraus, A., Minlplib - A collection of test models for mixed-integer nonlinear programming, INFORMS Journal on Computing, 15, 1, 114-119, (2003) · Zbl 1238.90104 |

[9] | Bussieck, M. R.; Vigerske, S., MINLP solver software, (Cochran, J.; Cox, L.; Keskinocak, P.; Kharoufeh, J.; Smith, J., Wiley encyclopedia of operations research and management science, (2011), John Wiley & Sons, Inc) |

[10] | Cafieri, S., MINLP in air traffic management: aircraft conflict avoidance, in advances and trends in optimization with engineering applications, (Terlaky, T.; Anjos, M. F.; Ahmed, S., MOS-SIAM Book Series on Optimization, (2017), SIAM Philadelphia) |

[11] | Cafieri, S., Maximizing the number of solved aircraft conflicts through velocity regulation, Proceedings of the 12th global optimization workshop, MAGO 2014, 1-4, (2014), Málaga Spain |

[12] | Cafieri, S.; Durand, N., Aircraft deconfliction with speed regulation: new models from mixed-integer optimization, Journal of Global Optimization, 58, 4, 613-629, (2014) · Zbl 1301.90062 |

[13] | Christodoulou, M.; Costoulakis, C., Nonlinear mixed integer programming for aircraft collision avoidance in free flight, Proceedings of the 12th IEEE mediterranean electrotechnical conference, 2004, MELECON 2004, vol. Vol. 1, 327-330, (2004) |

[14] | Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profiles, Mathematical Programming, 91, 2, 201-213, (2002) · Zbl 1049.90004 |

[15] | Dupré, C.; Bonini, D.; Granger, G., How erasmus can support an increase in capacity in 2020, Proceedings of the 7th international conference on computing, communications and control technologies, CCCT, (2009) |

[16] | EUROCONTROL, Eurocontrol long-term forecast: IFR flight movements, Technical report, (2010), Eurocontrol-Air Traffic Statistics and Forecast |

[17] | Fourer, R.; Gay, D. M.; Kernighan, B. W., AMPL: A modeling language for mathematical programming, (2002), Brooks/Cole |

[18] | Hansman, J., Impact of nextgen integration on improving efficiency and safety of operations, Proceedings of TRB: the 91st annual meeting of the transportation research board, (2012), Washington D.C, USA |

[19] | Kuchar, J.; Yang, L., A review of conflict detection and resolution modeling methods, IEEE Transactions on Intelligent Transportation Systems, 1, 4, 179-189, (2000) |

[20] | Liberti, L.; Cafieri, S.; Tarissan, F., Reformulations in mathematical programming: A computational approach, Foundations of Computational Intelligence Volume 3, Vol. 203 of Studies in Computational Intelligence, 153-234, (2009), Springer Berlin, Heidelberg |

[21] | Lin, Y.; Schrage, L., The global solver in the LINDO API, Optimization Methods and Software, 24, 4-5, 657-668, (2009) · Zbl 1177.90325 |

[22] | Misener, R.; Floudas, C. A., Antigone: algorithms for continuous/integer global optimization of nonlinear equations, Journal of Global Optimization, 59, 2, 503-526, (2014) · Zbl 1301.90063 |

[23] | Pallottino, L.; Feron, E. M.; Bicchi, A., Conflict resolution problems for air traffic management systems solved with mixed integer programming, IEEE Transactions on Intelligent Transportation Systems, 3, 1, 3-11, (2002) |

[24] | Peyronne, C.; Conn, A. R.; Mongeau, M.; Delahaye, D., Solving air traffic conflict problems via local continuous optimization, European Journal of Operational Research, 241, 2, 502-512, (2015) · Zbl 1339.90356 |

[25] | Rey, D.; Rapine, C.; Fondacci, R.; Faouzi, N.-E. E., Minimization of potential air conflicts through speed regulation, Transportation Research Record: Journal of the Transportation Research Board, 2300, 59-67, (2012) |

[26] | Rey, D.; Rapine, C.; Fondacci, R.; Faouzi, N.-E. E., Subliminal speed control in air traffic management: optimization and simulation, Transportation Science, 50, 1, 240-262, (2016) |

[27] | Sahinidis, N. V., Baron: A general purpose global optimization software package, Journal of Global Optimization, 8, 2, 201-205, (1996) · Zbl 0856.90104 |

[28] | SESAR consortium, The European ATM master plan, Technical Report, (2009), European Commission and EUROCONTROL |

[29] | Vela, A.; Solak, S.; Clarke, J.; Singhose, W.; Barnes, E.; Johnson, E., Near real-time fuel-optimal en route conflict resolution, IEEE Transactions on Intelligent Transportation Systems, 11, 4, 826-837, (2010) |

[30] | Vela, A.; Solak, S.; Singhose, W.; Clarke, J.-P., A mixed integer program for flight-level assignment and speed control for conflict resolution, in: decision and control, Proceedings of the 48th IEEE conference held jointly with the 2009 28th Chinese control conference, CDC/CCC 2009., 5219-5226, (2009) |

[31] | Wächter, A.; Biegler, L. T., On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Mathematical Programming, 106, 1, 25-57, (2006) · Zbl 1134.90542 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.