UNA TÉCNICA DE RESOLUCIÓN PARA EL BUS EVACUATION PROBLEM. APLICACIÓN A LA REGIÓN DE VALPARAÍSO

LOYOLA VITALI, JAVIERA PILAR (2016)

Catalogado desde la version PDF de la tesis.

Tesis Pregrado

El Bus Evacuation Problem (BEP) es un problema de planificaci´on de rutas, dentro delcontexto de una evacuaci´on en una situaci´on de emergencia. Considerando que se cuentacon transporte p´ublico para realizar la evacuaci´on, el objetivo del problema es determinarlas mejores rutas de cada uno de los veh´iculos, para llevar a todas las personas dentro de lazona de riesgo a refugios habilitados, de modo que la evacuaci´on dure lo menos posible.En este trabajo, se presenta un estudio de los distintos enfoques que existen en la literaturapara resolver el problema, para luego proponer un m´etodo basado en Greedy RandomizedAdaptive Search Procedure (GRASP), con el objetivo de abordar un escenario real basadoen el Gran Incendio de Valpara´iso (Chile, 2014). En experimentos computacionales,se muestra que el algoritmo propuesto permite resolver instancias de tama˜no real, adem´asde superar en rendimiento a un solver comercial MIP.

The Bus Evacuation Problem (BEP) is a route planning problem, in the context of anevacuation in an emergency situation. Considering that public transport is available tosupport the evacuation, the objective of the problem is to determine the best route foreach one of the vehicles, to move all the people from a risk zone to available shelterslocated in safe zones, so that the evacuation time is minimized. In this work, a study ofthe different approaches used on the literature to solve the problem is presented, to laterpropose a method based on Greedy Randomized Adaptive Search Procedure (GRASP),in order to solve a real scenario based on the Great Fire of Valpara´iso (Chile, 2014). Incomputational experiments, it is shown that the proposed algorithm is effective to solvereal-world size problems, and able to outperform a commercial MIP solver.