AED placement optimisation

• Main Author: Lee, Qian Yu
• Other Authors: Cai Wentong
• Format: Final Year Project
• Language: English
• Published: Nanyang Technological University 2021
• Subjects: Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity
• Online Access: https://hdl.handle.net/10356/147945
• Institution: Nanyang Technological University

As Out-Of-Hospital Cardiac Arrest continues to be prevalent in Singapore’s society, the installation of Automated External Defibrillators is critical in serving as an emergency precaution solution. To better optimise the usage of these devices and benefit patients, facility allocation needs to be conducted to identify optimal locations to install them. Emergency facility placement has always been a very significant topic in Operations Research and researchers have been trying to discover a better solution by improving its accuracy or efficiency. Although the exact solution and maximum objective value can be obtained from existing Python libraries, this method is infeasible for large areas like the whole of Singapore, where the dataset is massive. In this report, the Maximal Survival Location Problem is selected as the mathematical model to calculate the objective value. To solve the problem of handling large datasets, mathematical optimisation models like Hill Climbing Algorithm and Simulated Annealing Algorithm are chosen and refined upon. Parallelisation of both algorithms is conducted using high-performance computing to improve efficiency and targets to improve objective value when there is a limited number of AEDs. Finally, comparisons are made based on the results obtained from test sets of different sizes, including the total time taken and the final objective value obtained. It was observed that both algorithms were able to provide a good solution for large datasets within an acceptable computational time taken. Additionally, there was an interesting finding on how the algorithms helped to reduce the total number of AEDs.