Keeping order of vessels in problem of safe merging aircraft flows

A. A. Spiridonov ; S. S. Kumkov

Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 32 (2022) no. 3, pp. 433-446

Résumé

Nowadays, the problem of creating an optimal safe schedule for arrival of aircraft coming in several flows to a checkpoint, where these flows join into one, is very important for air-traffic management. Safety of the resultant queue is present if there is a safe interval between neighbor arrivals to the merge point. Change of an arrival instant of an aircraft is provided by changing its velocity and/or usage of fragments of the air-routes scheme, which elongate or shorten the aircraft path. Optimality of the resultant queue is considered from the point of some additional demands: minimization of the deviation of the actual aircraft arrival instant from the nominal one, minimization of order changes in the resultant queue in comparison with the original one, minimization of fuel expenditures, etc. The optimality criterion to be minimized, which reflects these demands, is often taken as a sum of penalties for deviations of the assigned arrival instants from the nominal ones. Each individual penalty is considered in almost all papers as either the absolute value of the difference between the assigned and nominal arrival instants or a similar function with asymmetric branches (which punishes delays and accelerations of an aircraft in different ways). The problem can be divided into two subproblems: one is a search for an optimal order of aircraft in the resultant queue, and the other is a search for optimal arrival instants for a given order. The second problem is quite simple since it can be formalized in the framework of linear programming and solved quite efficiently. However, the first one is very difficult and now is solved by various methods. The paper suggests sufficient conditions for the problem, which guarantee that the order of the optimal assigned instants is the same as the order of the nominal ones and, therefore, exclude the first subproblem.

Détail

Keywords: aircraft, airway merge point, non-conflict flows merging, assigned arrival instants, joined aircraft queue.
Mots-clés : nominal arrival instants

Bibliographie

[1] Bayen A., Callantine T., Tomlin C., Ye Y., Zhang J., “Optimal arrival traffic spacing via dynamic programming”, AIAA Guidance, Navigation, and Control Conference and Exhibit, American Institute of Aeronautics and Astronautics, 2004, 2232–2242 | DOI

[2] Beasley J. E., Krishnamoorthy M., Sharaiha Y. M., Abramson D., “Scheduling aircraft landings — the static case”, Transportation Science, 34:2 (2000), 180–197 | DOI | Zbl

[3] Bennell J. A., Mesgarpour M., Potts C. N., “Airport runway scheduling”, 4OR, 9:2 (2011), 115–138 | DOI | MR

[4] Bennell J. A., Mesgarpour M., Potts C. N., “Airport runway scheduling”, Annals of Operations Research, 204:1 (2013), 249–270 | DOI | MR | Zbl

[5] Bennell J. A., Mesgarpour M., Potts C. N., “Dynamic scheduling of aircraft landings”, European Journal of Operational Research, 258:1 (2017), 315–327 | DOI | MR | Zbl

[6] Bianco L., Rinaldi G., Sassano A., “A combinatorial optimization approach to aircraft sequencing problem”, Flow Control of Congested Networks, Springer, Berlin–Heidelberg, 1987, 323–339 | DOI

[7] Boursier L., Favennec B., Hoffman E., Trzmiel A., Vergne F., Zeghal K., “Merging arrival flows without heading instructions”, 7th USA/Europe Air Traffic Management Research and Development Seminar (2007), Curran Associates, 2015, 403–410

[8] d'Apice C., de Nicola C., Manzo R., Moccia V., “Optimal scheduling for aircraft departures”, Journal of Ambient Intelligence and Humanized Computing, 5:6 (2014), 799–807 | DOI

[9] d'Ariano A., Pacciarelli D., Pistelli M., Pranzo M., “Real-time scheduling of aircraft arrivals and departures in a terminal maneuvering area”, Networks, 65:3 (2015), 212–227 | DOI | MR

[10] Eltoukhy A. E. E., Chan F. T. S., Chung S. H., “Airline schedule planning: a review and future directions”, Industrial Management and Data Systems, 117:6 (2017), 1201–1243 | DOI

[11] Hong Y., Choi B., Kim Y., “Two-stage stochastic programming based on particle swarm optimization for aircraft sequencing and scheduling”, IEEE Transactions on Intelligent Transportation Systems, 20:4 (2019), 1365–1377 | DOI

[12] Liang M., Delahaye D., Maréchal P., “Integrated sequencing and merging aircraft to parallel runways with automated conflict resolution and advanced avionics capabilities”, Transportation Research. Part C: Emerging Technologies, 85 (2017), 268–291 | DOI

[13] Lieder A., Briskorn D., Stolletz R., “A dynamic programming approach for the aircraft landing problem with aircraft classes”, European Journal of Operational Research, 243:1 (2015), 61–69 | DOI | MR | Zbl

[14] Lieder A., Stolletz R., “Scheduling aircraft take-offs and landings on interdependent and heterogeneous runways”, Transportation Research. Part E: Logistics and Transportation Review, 88 (2016), 167–188 | DOI

[15] Montoya J., Rathinam S., Wood Z., “Multiobjective departure runway scheduling using dynamic programming”, IEEE Transactions on Intelligent Transportation Systems, 15:1 (2014), 399–413 | DOI

[16] Salehipour A., “An algorithm for single- and multiple-runway aircraft landing problem”, Mathematics and Computers in Simulation, 175 (2020), 179–191 | DOI | MR | Zbl

[17] Simão H. P., Day J., George A. P., Gifford T., Nienow J., Powell W. B., “An approximate dynamic programming algorithm for large-scale fleet management: A case application”, Transportation Science, 43:2 (2009), 178–197 | DOI

[18] Solak S., Solveling G., Clarke J.-P. B., Johnson E. L., “Stochastic runway scheduling”, Transportation Science, 52:4 (2018), 917–940 | DOI

[19] Sölveling G., Clarke J.-P., “Scheduling of airport runway operations using stochastic branch and bound methods”, Transportation Research. Part C: Emerging Technologies, 45 (2014), 119–137 | DOI

[20] Soomer M. J., Franx G. J., “Scheduling aircraft landings using airlines' preferences”, European Journal of Operational Research, 190:1 (2008), 277–291 | DOI | MR | Zbl

[21] Veresnikov G. S., Egorov N. A., Kulida E. L., Lebedev V. G., “Methods for solving of the aircraft landing problem. I. Exact solution methods”, Automation and Remote Control, 80:7 (2019), 1317–1334 | DOI | MR | Zbl

[22] Veresnikov G. S., Egorov N. A., Kulida E. L., Lebedev V. G., “Methods for solving of the aircraft landing problem. II. Approximate solution methods”, Automation and Remote Control, 80:8 (2019), 1502–1518 | DOI | MR | Zbl

[23] Vié M. S., Zufferey N., Leus R., “Aircraft landing planning: past, present and future”, Proceedings of the 19th annual congress of the french operations research society, 2018 https://archive-ouverte.unige.ch/unige:104854 | Zbl

[24] Xu B., “An efficient Ant Colony algorithm based on wake-vortex modeling method for aircraft scheduling problem”, Journal of Computational and Applied Mathematics, 317 (2017), 157–170 | DOI | MR | Zbl

[25] Zulkifli A., Aziz N. A. A., Aziz N. H. A., Ibrahim Z., Mokhtar N., “Review on computational techniques in solving aircraft landing problem”, Proceedings of International Conference on Artificial Life and Robotics, 23 (2018), 128–131 | DOI