Shakessafe: optimizing disaster risk routes using breadth-first search algorithm and dynamic programming approach to the traveling salesman problem

Date

6-2024

Adviser

Kharisa Mae M. Pasion

Principal

Buela, Mabel S.

Abstract

Being located in the Pacific Ring of Fire, the Philippines experiences around 20 earthquakes a day, with the possibility of having the "big one any day. Due to this, the researchers developed ShakeSafe to suggest a safe and short route that can be taken by emergency response teams after an earthquake. ShakeSafe uses Breadth-First Search (BFS), a graph traversal algorithm with the time complexity OV + E), to define the distances between LGUs and Barangay Halls while dodging areas near and on fault lines, along with a Dynamic Programming approach to the Travelling Salesman Problem (TSP), a method with a time complexity of O(2^n*n^2) that solves complex problems by splitting it into subproblems, to create the optimal route to be taken. Shakesafe was used on a snapshot of two barangays in MuntinlupaCupang and Alabang, that were simplified into a 4lx41 grid. The BFS algorithm uses the grid to create an adjacency matrix containing the distances between all nodes; the Dynamic Programming approach to the TSP uses this adjacency matrix to calibrate the shortest safe path. ShakeSafe ofers a safer and more efficient way to reach areas and distribute relief goods after an earthquake.

Language

English

LC Subject

Capstone

Location

UP Rural High School

Document Type

Capstone

This document is currently not available here.

Share

COinS