The application of ant algorithm in the assignment problem of aircrafts to stops points on the apron

• Autorzy: Gołda P. , Izdebski M. , Szczepański E.

Identyfikatory

DOI

10.5604/01.3001.0012.7845

• Języki publikacji: EN

Abstrakty

EN

The article refers to the problem of assigning the aircrafts to stops points on the apron. The aim of this paper is to develop the algorithm, which will be used to this assignment. The assignment problem of aircrafts to stops points is the complex decision problems, which refer to the problems of designating the minimal path in the graph. The assignment model was described, i.e. decision variables, constraints and the criterion function. Decision variables take the binary form and determine the connections between the elements of infrastructure of the apron, i.e. touchdown points, intermediate points and stop points. Constraints take into account the number of aircrafts in the given period, the number of unoccupied stop points. The criterion function determines the minimum driving time of the aircraft on the apron. In order to designate the routes in international transport the heuristic algorithm, i.e. ant algorithm was developed. The steps of building this algorithm were presented. This algorithm was verified in the C# programming language. The results generating by the presented algorithm were compared with the results generating by the random algorithm.

Słowa kluczowe

EN

air transportation; air traffic control; aircraft operation; airport

• Wydawca: Łukasiewicz Research Network - Institute of Aviation ; European Science Society of Powertrain and Transport KONES Poland ; Wydawnictwo Instytutu Technicznego Wojsk Lotniczych
• Czasopismo: Journal of KONES
• Rocznik: 2018
• Tom: Vol. 25, No. 4
• Strony: 479--487
• Opis fizyczny: Bibliogr. 27 poz., rys.

Twórcy

autor

Gołda P.

• Air Force Institute of Technology Ksiecia Boleslawa 6, 01-494 Warszawa, Poland tel.: [phone], fax: [phone]

autor

Izdebski M.

• Warsaw University of Technology, Faculty of Transport Department of Logistics and Transport Systems Koszykowa Street 75, 00-662 Warsaw, Poland tel.: [phone], fax: [phone]

autor

Szczepański E.

• Warsaw University of Technology, Faculty of Transport Koszykowa 75, 00-662 Warsaw, Poland tel.: [phone]

Bibliografia

• [1] Aickelin, U., Dowsland, K. A. An indirect Genetic Algorithm for a nurse-scheduling problem. Comput. Oper. Res. 2004, 31, 761-778.
• [2] Akgül, M. A genuinely polynomial primal simplex algorithm for the assignment problem. Discret. Appl. Math. 1993, 45, 93-115.
• [3] Bollobas, B. Modern graph theory. In Graduate Texts in Mathematics; Springer: New York, NY, USA, 1998.
• [4] Bondy, J. A. Murty, U. S. R. Graph Theory with Applications. Elsevier Science Ltd.: North-Holland, The Netherlands, 1976.
• [5] Burkhard, R.; Dell’Amico, M., Marttelo, S. Assignment Problems. Society for Industrial and Applied Mathematics. Philadelphia, PA, USA, 2009.
• [6] Chmielewsk i, A., Naujoks, B., Janas, M., Clausen, U. Optimizing the Door Assignment inLTL-Terminals. Transp. Sci. 2009, 43, 198-210. The Application of Ant Algorithm in the Assignment Problem of Aircrafts to Stops Points on the Apron
• [7] Dorigo M., Blum Ch. Ant Colony Optimization Theory: a survey, Theoretical Computer science, Vol.344m, 243-278, 2005.
• [8] Dorigo M., Caro D., Gambardela L. M. Ant Algorithms for Discrete Optimization, artificial Life, Vol.5 (2), pp. 137-172, 1999.
• [9] Dorigo M., Gambardela L. M.Ant Colonies for the Travelling Salesman Problem, BioSystems, pp. 73-81, Vol.43 (1997).
• [10] Dorigo M., Gambardela L. M. Ant Colony System: A cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation, 53-66, Vol.1(1)(1997).
• [11] Etschmaier, M. M., Mathaisel, D.F.X. Airline Scheduling. An Overview. Transp. Sci. 1985, 19, 127–138, 10.1287/trsc.19.2.127.
• [12] Feillet D., Dejax P., Gendreau M., Gueguen C. An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems. Networks, 44/2004, pp. 216-229.
• [13] Fu L., Sun D., Rilett L. R. Heuristic shortest path algorithms for transportation applications: state of the art. Computers & Operations Research, 33(11)/2006, pp. 3324-3343.
• [14] Goldberg A. V., Harrelson C. Computing the shortest path: A search meets graph theory, [in] Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, 01/2005, pp. 156-165.
• [15] Gołda P., Manerowski J. Model systemu operacji kołowania samolotów na płycie lotniska. Logistka 3/2014, str. 7240-7246.
• [16] Irnich S., Desaulniers G. Shortest path problems with resource constraints. Column generation, 6730, pp. 33-65, 2005.
• [17] Izdebski M., Jacyna-Gołda I., Jakowlewa I. Planning international transport using the heuristic algorithm, in Integration as Solution for Advanced Smart Urban Transport Systems / Sierpiński Grzegorz (red.), Advances in Intelligent Systems and Computing, vol. 844, 2018, Springer International Publishing, ISBN 978-3-319-99476-5, ss. 229-241
• [18] Jacyna M., Izdebski M., Szczepański E. Gołda P. The task assignment of vehicles for a production company, w Symmetry-Basel, vol. 11, nr 10, 2018, pp. 1-19. [19] Jonker, R., Volgenant, A.T. Improving the Hungarian assignment algorithm. Oper. Res. Lett. 1986, 5, 171–175.
• [19] Jonker, R., Volgenant, A.T. Improving the Hungarian assignment algorithm. Oper. Res. Lett. 1986, 5, 171–175.
• [20] Klincewicz, J. G., Rosenwein, M. B. The Airline Exception Scheduling Problem. Transp. Sci. 1995, 29, 4–16, doi:10.1287/trsc.29.1.4.
• [21] Lohatepanont, M., Barnhart, C. Airline Schedule Planning: Integrated Models and Algorithms for Schedule Design and Fleet Assignment. Transp. Sci. 2004, 38, 19-32.
• [22] Sysło M., Deo N., Kowalik S. Algorytmy optymalizacji dyskretnej. PWN, Warszawa 1999.
• [23] Szczepański E., Jacyna-Gołda I., Murawski J. Genetic algorithms based approach for transhipment HUB location in urban areas. Archives of Transport, vol. 31, iss. 3, 2014, pp. 73-82,
• [24] Wang, Y. Z. An application of genetic algorithm methods for teacher assignment problems. Expert Syst. Appl. 2002, 22, 295-302,
• [25] Wilson, J. M. A genetic algorithm for the generalised assignment problem. J. Oper. Res. Soc. 1997, 48, 804-809.
• [26] Yu, E., Sung, K. S., A genetic algorithm for a university weekly courses timetabling problem. Int. Trans. Oper. Res. 2002, 9.
• [27] Zieja M., Smoliński H., Gołda P., Information systems as a tool for supporting the management of aircraft flight safety. Archives of Transport 4(36), 2015, DOI:10.5604/08669546.1146993.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).