Research-Thesis: Disaster Response Improvement Using Heuristic Methods

Abstract

Disaster response operations require fast and reliable planning under uncertainty and time pressure. This thesis addresses this challenge by studying and developing a robust time-sensitive capacitated orienteering problem (RT-CTOP) tailored to humanitarian logistics. The objective is to maximize collected rewards representing disaster victims, while accounting for uncertain travel times, limited resources, and time-dependent service values. A robust optimization framework based on a budgeted uncertainty set is proposed to explicitly model travel-time variability. As is well known, exact methods such as Mixed-Integer Linear Programming (MILP) are NP-hard for this class of problems, meaning that they quickly become computationally intractable as instance size increases. To overcome this limitation, two metaheuristic approaches, Genetic Algorithm (GA) and Variable Neighborhood Search (VNS), are designed and adapted to the RT-CTOP formulation. The results show that GA and VNS consistently deliver high-quality and stable solutions while significantly outperforming the MILP in terms of scalability and computational behavior. In instances where the MILP is solvable, heuristic solutions closely approximate optimal values. Under tight runtime limits or increased uncertainty, heuristic methods maintain solution quality, whereas MILP performance degrades sharply. The findings confirm the effectiveness of metaheuristic approaches in addressing large-scale and time-critical disaster response routing problems under uncertainty, and establish a foundation for future research on adaptive and data-driven robust optimization frameworks.