Ant Algorithm for AP-N Aimed at Optimization of Complex Systems
DOI:
https://doi.org/10.7494/dmms.2010.4.2.29Keywords:
assignment problem, ant algorithm, optimizationAbstract
Assignment Problem (AP), which is well known combinatorial problem, has been studied extensively in the course of many operational and technical researches. It has been shown to be NP-hard for three or more dimensions and a few non-deterministic methods have been proposed to solve it. This paper pays attention on new heuristic search method for the n-dimensional assignment problem, based on swarm intelligence and comparing results with those obtained by other scientists. It indicates possible direction of solutions of problems and presents a way of behaviour using ant algorithm for multidimensional optimization complex systems. Results of researches in the form of computational simulations outcomes are presented.
References
Aiex R.M., Resende M.G.C., Pardalos P.M. & Toraldo G. (2005). GRASP with path relinking for three-index assignment. INFORMS Journal on Computing, 17(2), pp. 224–247. DOI: https://doi.org/10.1287/ijoc.1030.0059.
Balas E. & Saltzman M.J. (1991). An algorithm for the three-index assignment problem. Operations Research, 39(1), pp. 150–161. DOI: https://doi.org/10.1287/opre.39.1.150.
Burkard R.E., Rudolf R. & Woeginger G.J. (1996). Three-dimensional axial assignment problems with decomposable cost coefficients. Discrete Applied Mathematics, 65(1–3), pp. 123–139. DOI: https://doi.org/10.1016/0166-218X(95)00031-L.
Crama Y. & Spieksma F.C.R. (1992). Approximation algorithms for three-dimensional assignment problems with triangle inequalities. European Journal of Operational Research, 60(3), pp. 273–279. DOI: https://doi.org/10.1016/0377-2217(92)90078-N.
Escamilla-Ambrosio P.J. & Lieven N. (2004). A multiple-sensor multiple-target tracking approach for the Autotaxi system. In: Proceedings of the 2004 IEEE Intelligent Vehicles Symposium, Parma, Italy, June 14–17, 2004, pp. 601–606. IEEE. DOI: https://doi.org/10.1109/IVS.2004.1336452.
Filipowicz B. (1998). Matematyczne modelowanie zagadnień decyzyjnych. Część I. Kraków: Wydawnictwa Akademii Górniczo-Hutniczej.
Górecki H. (2006). Optymalizacja i sterowanie systemów dynamicznych. Kraków: Uczelniane Wydawnictwa Naukowo-Dydaktyczne AGH.
Huang G. & Lim A. (2006). A hybrid genetic algorithm for the three-index assignment problem. European Journal of Operational Research, 172(1), pp. 249–257. DOI: https://doi.org/10.1016/j.ejor.2004.09.042.
Karp R.M. (1972). Reducibility among combinatorial problems. In: Miller R.E., Thatcher J.W. & Bohlinger J.D. (Eds.), Complexity of Computer Computations, pp. 85–103. New York: Plenum Press. DOI: https://doi.org/10.1007/978-1-4684-2001-2_9.
Kuhn H.W. (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1–2), pp. 83–97. DOI: https://doi.org/10.1002/nav.3800020109.
Merkle D. & Middendorf M. (2005). Swarm intelligence. In: Burke E.K. & Kendall G. (Eds.), Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, pp. 401–435. Boston, MA: Springer. DOI: https://doi.org/10.1007/0-387-28356-0_14.
Owsiński J.W. & Straszak A. (Eds.) (2002). Społeczeństwo informacyjne a badania operacyjne i zarządzanie. Warszawa: Akademicka Oficyna Wydawnicza EXIT.
Zajdel M. & Filipowicz B. (2008). Multidimensional assignment problem as a tool for decision processes’ support in a company [in Polish]. In: Kopczewski M. (Ed.), Modele inżynierii teleinformatyki: wybrane zastosowania, vol. 3, p. 288. Koszalin: Politechnika Koszalińska. ISBN 978-83-7365-160-9.
