A Look at Algorithm BEPtoPNST
Copyright (c) 2023 Revista Ingenierías Universidad de Medellín
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
- Articles
- Submitted: January 26, 2020
-
Published: September 9, 2020
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.
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.
