A Look at Algorithm BEPtoPNST
Article Sidebar
The total or partial reproduction of the contents of the journal for educational, research, or academic purposes is authorized as long as the source is cited. For reproduction for other purposes, express authorization from the Sello Editorial Universidad de Medellín is required.
Main Article Content
Abstract
This work analyzes the computational complexity of algorithm BEPtoPNST which transforms a building-evacuation problem (BEP) into a time-ex-panded, process-network synthesis (PNST) problem. The solution of the latter is achieved by resorting to the P-graph method which exploits the combinatorial nature of a BEP. Unlike other approaches, the P-graph method provides not only the optimal solution (best evacuation route as a function of egress time), but also the best n sub-optimal solutions. For the complexity analysis, a generic processor, and a Random-access machine (RAM) model were deployed as well as a mathematical model to calculate the number and cost of the operations performed. It was observed that algorithm BEPtoPNST exhibits an asymptotic complexity of order O ( T | A | (| N | –k)). When solving a BEP, however, the total complexity grows exponentially with order O (T | A | (| N | –k)) + O (2h)) in the worst case; where h represents the total number of operating units specified in the corresponding PNST problem. Nevertheless, the computational comple-xity can be reduced significantly when the P-graph method is deployed.
Article Details
References
[2] T.J. Cova y J.P. Johnson, 'A network flow model for lane-based evacuation routing,' Transportation Research – Part A: Policy and Practice, vol. 37, n.° 7, pp. 579–604, 2003. DOI: 10.1016/S0965-8564(03)00007-7
[3] H.W. Hamacher y S.A. Tjandra, 'Mathematical modeling of evacuation problems: a state of the art,' en Pedestrian and Evacuation Dynamics, M. Schreckenberg y S.D. Sharma, eds., pp. 227–266, Berlin: Springer, 2002.
[4] M. Skutella, 'An introduction to network flows over time,'en Research Trends in Combinatorial Optimization, W. Cook et al., eds., pp. 451–482, Berlin: Springer, 2009.
[5] S. Kim et al., 'Contraflow transportation network reconfiguration for evacuation route planning,' IEEE Transactions on Knowledge and Data Engineering, vol. 20, n° 8, pp. 1115–1129, 2008. DOI: 10.1109/TKDE.2007.190722
[6] J.C. García-Ojeda et al., 'Identifying Evacuation Routes via the P-graph Methodology,' presentado en 10.° Congreso Colombiano de Computación, Bogotá, 2015.
[7] J.C. Garcia-Ojeda et al., 'Building-Evacuation-Route Planning via Time-Expanded Process-Network Synthesis,' Fire Safety Journal, vol. 61, pp. 338–347, 2013. DOI:10.1016/j.firesaf.2013.09.023
[8] J.C. Garcia-Ojeda et. al., 'Planning evacuation routes with the P-graph framework,' Chemical Engineering Transactions, vol. 29, pp. 1531-1536, 2012. DOI: 10.3303/CET1229256
[9] J.C. García-Ojeda et al., 'Multi-criteria Analysis of Building Evacuation Route Planning by Resorting to the P-graph Framework,' presentado en 5th Veszprem Optimisation Conference: Advanced algorithms, Veszprem, 2012.
[10] J.C. García-Ojeda et al., 'Planning evacuation routes with the P-graph framework,' presentado en 15th International Conferences on Process Integration, Modelling and Optimisation for Energy Saving and Pollution Reduction, Prague, 2012.
[11] J.C. Garcia-Ojeda, 'On Building Evacuation Route Planning by Resorting to P-graph,' Revista Colombiana de Computación, vol. 12, n° 1, pp. 111–125, 2011.
[12] F. Friedler et al., 'Combinatorially Accelerated Branch-and-Bound Method for Solving the MIP Model of Process Network Synthesis,' en Global Optimization, Computational Methods and Applications, State of the Art, C.A. Floudas y P.M. Pardalos, eds., pp. 609-626, Dordrecht, Netherlands: Kluwer Academic Publishers, 1996.
[13] F. Friedler et. al., 'Decision-mapping for design and synthesis of chemical processes: applications to reactor-network synthesis,' en Foundations of Computer-Aided Process Design, AIChE Symposium Series 91, L. T. Biegler y M. F. Doherty, eds. pp. 246 – 250, NY: American Institute of Chemical Engineers, 1995.
[14] F. Friedler et al., 'Graph-theoretic approach to process synthesis: axioms and theorems,' Chemical Engineering Science, vol. 47, n° 8, pp. 1972–1988, 1992. DOI: 10.1016/0009-2509(92)80315-4
[15] F. Friedler et al., 'Combinatorial Algorithms for Process Synthesis,' Computers & Chemical Engineering, vol. 16, n° 5, pp. S313–320, 1992. DOI: 10.1016/S0098-1354(09)80037-9
[16] F. Friedler et al., 'Process Network Synthesis: Problem Definition.' Networks, vol. 28, n° 2, pp. 119–124, 1998. DOI: doi.org/10.1002/(SICI)1097-0037(199803)31:2<119::AID-NET6>3.0.CO;2-K
[17] E.D. Kuligowski, y R.D. Peacock, A Review of Building Evacuation Models (1st ed.), National Institute of Standards and Technology, Technical Note 1471, 2005.
[18] E.D. Kuligowski et al., A Review of Building Evacuation Models (2nd ed.), National Institute of Standards and Technology, Technical Note 1680, 2010.
[19] M. Minoux, 'Networks synthesis and optimum network design problems: Models, solution methods and applications,' Networks, vol. 19, n° 3, pp. 313–360, 1989. DOI: doi.org/10.1002/net.3230190305
[20] L.R. Ford y D.R. Fulkerson, Flows in Networks. Princeton, NJ: Princeton University Press, 1962, 210 p.
[21] A.M. Turing, 'Rounding-off Errors in Matrix Processes,' The Quarterly Journal of Mechanics and Applied Mathematics, vol. 1, n° 1, pp. 287–308, 1948. DOI: 10.1093/qjmam/1.1.287
[22] T.H. Cormen et al., Introduction to Algorithms, 3a ed., Cambridge: MA, MIT Press, 2009, 1320 p.
[23] R.R., Howell, Algorithms: A Top-Down Approach, 9a ed., Dept. of Computing and Information Sciences: KS, Kansas State University, 2009, 617 p.
[24] D.E. Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3a ed., Redwood City: CA, Addison Wesley Longman Publishing Co., 1997, 672 pp.
[25] M.T. Goodrich y R. Tamassia, Algorithm Design and Applications, 1a ed., Hoboken: NJ, Wiley Publishing, 2014, 816 pp.
[26] A.V. Aho et al., The Design and Analysis of Computer Algorithms. Reading: MA, Addison Wesley, 1974, 470 pp.