DIJKSTRA-ANT COLONY OPTIMIZATION ALGORITHM FOR SHORTEST AND SAFEST EVACUATION IN HIGH RISE BUILDING

Nor Amalina Mohd Sabri, Abd Samad Hasan Basari, Burairah Hussin, Khyrina Airin Fariza Abu Samah

Abstract


The successfulness of evacuation is defined by the ability of the evacuees to escape from the danger place safely in a short time. The three problems highlighted in this study are evacuees do not know the right route should they take to safe themselves especially in high rise building due to the complexity of the building. Moreover, the provided evacuation map in the building is commonly not showing the shortest and safest path to assist evacuees in choosing the best route. Furthermore, the shortest path algorithm needs additional features to support the directed graph in order to obtain the best result. The objectives of this study are to design and develop the evacuation route via the shortest path algorithm and to evaluate the evacuation route model in high rise building evacuation maps. The methods used are modelling the evacuation route from the original floor plan into 2D floor plan, and then generating the directed graph based on the distance between nodes and coordinate of nodes to generate the shortest and safest path based on the utilisation of Dijkstra’s algorithm and Dijkstra-Ant Colony Optimization (DACO). The results obtained are proven consistent in generating the shortest and safest path with the same distance.


Keywords


Dijkstra’s algorithm, Dijkstra-Ant Colony Optimization, Evacuation, Safest Path, Shortest Path

Full Text:

PDF

References


Ekizoğlu, B. 2009. Emergency Evacuation Simulation In Istanbul Technical University. 370-376.

Song, X., Q. Zhang, Y. Sekimoto, T. Horanont, S. Ueyama, and R. Shibasaki. 2013. Modeling And Probabilistic Reasoning Of Population Evacuation During Large-Scale Disaster. Proc. 19th ACM SIGKDD Int. Conf. Knowl. Discov. data Min. - KDD ’13. 1231.

Li, Q., Z. Fang, Q. Li, and X. Zong. 2010. Multiobjective Evacuation Route Assignment Model Based on Genetic Algorithm. 18th Int. Conf. Geoinformatics. 1-5.

Kruminaite, M., and S. Zlatanova. 2014. Indoor Space Subdivision for Indoor Navigation. ISA’14. 25-31.

Khyrina, A. F. A. S., H. Burairah, and H. B. Abd Samad. 2013. A Systems Thinking in Natural Disaster Management : Evacuation Preparedness. 384-389.

Sabri, N. A. M., A. S. H. Basari, B. Husin, and A. F. A. S. Khyrina. 2014. Simulation Method of Shortest and Safest Path Algorithm for Evacuation in High Rise Building. Appl. Math. Sci. 8(104): 5163-5172.

Goodwin, M., O. C. Granmo, J. Radianti, P. Sarshar, and S. Glimsdal. 2013. Ant Colony Optimisation For Planning Safe Escape Routes. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7906: 53-62.

Wu, C. H. and L.-C. Chen. 2012. 3D Spatial Information For Fire-Fighting Search And Rescue Route Analysis Within Buildings. Fire Saf. J. 48: 21-29.

Goetz, M., and A. Zipf. 2012. Using Crowdsourced Geodata for Agent-Based Indoor Evacuation Simulations. ISPRS Int. J. Geo-Information. 1(3): 186-208.

Koh, W. L., and S. Zhou. 2011. Modeling And Simulation Of Pedestrian Behaviors In Crowded Places. ACM Trans. Model. Comput. Simul. 21(3): 1-23.

Hadzic, T., K. N. Brown, and C. J. Sreenan. 2011. Real-Time Pedestrian Evacuation Planning during Emergency. 2011 IEEE 23rd Int. Conf. Tools with Artif. Intell. 597-604.

Ribeiro, J. and J. Almeida. 2012. Using Serious Games To Train Evacuation Behaviour. 2012 7th Iber. Conf. Inf. Syst. Technol.

Kamkarian, P., and H. Hexmoor. 2012. Crowd Evacuation for Indoor Public Spaces Using Coulomb’s Law. Adv. Artif. Intell. 2012: 1-16.

Aedo, I., S. Yu, P. Díaz, P. Acuña, and T. Onorati. 2012. Personalized Alert Notifications And Evacuation Routes In Indoor Environments. Sensors (Basel). 12(6): 7804-27.

Sacharidis, D. and P. Bouros. 2013. Routing Directions: Keeping it Fast and Simple. in SIGSPATIAL ’13:Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 164-173.

Bu, F. and H. Fang. 2010. Shortest Path Algorithm Within Dynamic Restricted Searching Area In City Emergency Rescue. 2010 IEEE Int. Conf. Emerg. Manag. Manag. Sci. v: 371-374.

Gupta, M., M. Dua, and N. Kumar. 2011. CNS Using Restricted Space Algorithms For Finding A Shortest Path. 48-54.

Kang, W., F. Zhu, Y. Lv, G. Xiong, L. Xie, and B. Xi. 2013. A Heuristic Implementation Of Emergency Traffic Evacuation In Urban Areas. Proceedings of 2013 IEEE International Conference on Service Operations and Logistics, and Informatics. SOLI 2013. 40-44.

Wang, T., R. Huang, L. Li, W. Xu, and J. Nie. 2011. The Application of the Shortest Path Algorithm in the Evacuation System. Appl. Shortest Path Algorithm Evacuation Syst. 250-253.

Zhang, H., H. Liu, K. Zhang, and J. Wang. 2010. Modeling of Evacuations to No-Notice Event by Public Transit System. 480-484.

Xu, Y., Z. Wang, Q. Zheng, and Z. Han. 2012. The Application of Dijkstra’s Algorithm in the Intelligent Fire Evacuation System. 2012 4th Int. Conf. Intell. Human-Machine Syst. Cybern. 3-6.

Kaitao, C., G. Quanbo, and D. Shenan. 2012. Research And Design For Emergency Evacuation Instructions System Based On Wireless Sensor Network. 2012 24th Chinese Control Decis. Conf. 3849-3854.

Biswas, S. S., B. Alam, and M. N. Doja. 2014. a Refinement of Dijkstra’s Algorithm for Extraction of Shortest Paths in Generalized Real Time-Multigraphs. J. Comput. Sci. 10(4): 593-603.

Sabri, N. A. M., A. S. H. Basari, B. Husin, and A. F. A. S. Khyrina. 2015. The Utilisation of Dijkstra’ s Algorithm to Assist Evacuation Route in Higher and Close Building. J. Comput. Sci.




DOI: http://dx.doi.org/10.11113/jt.v79.5912

Refbacks

  • There are currently no refbacks.


Copyright © 2012 Penerbit UTM Press, Universiti Teknologi Malaysia.
Disclaimer : This website has been updated to the best of our knowledge to be accurate. However, Universiti Teknologi Malaysia shall not be liable for any loss or damage caused by the usage of any information obtained from this web site.
Best viewed: Mozilla Firefox 4.0 & Google Chrome at 1024 × 768 resolution.