## 4 Review of Literature
### Evacuation in Routing Optimisation Problems
#### 4.2.1 Exact Methods in Evacuation VRPs  
The evacuation through bus routing optimisation is addressed in [108], which uniquely minimised the exposed risk of evacuees to danger by introducing a VRPTW. The objective is to minimise the time taken by evacuees to reach a safe place free from the risk of danger exposure. Similar to [109], a constructive heuristic approach is adapted in order to achieve an upper bound for the Lagrangian Relaxation (LR) method in solving the problem. The LR problem is converted into a min-cost flow problem by creating virtual arcs between pick up and delivery nodes representing potential visits. In conclusion, this work stressed the theoretical perspective of the work, rather than a practical solution, since the algorithm becomes prohibitive as the problem becomes larger, to which the application of the aforementioned heuristic is advocated. The dynamics of real time transit vehicle routing for evacuation operations is considered by [109], where the model is updated with real information that is obtained based on the conditions of the disaster in affecting the routing network. The PDVRP is extended in order to address the transit operation to evacuate victims without transportation to emergency shelters. The resulting model is embedded in the real time transit evaluation system, SmartEvac, for humanitarian operations minimising the total travel time. The model consists of both offline and online planning. One is applied before the operation begins as a static Capacitated VRP with Pickup and Delivery (CVRPPD), while the other is applied during the real time operation as Capacitated Dynamic VRP with Pickup and Delivery (CDVRPD), where the information updates are reflected within. In order to solve the problem, a few measures are taken in [109] to reduce the computation burden, such as introducing Column Generation to decompose the problem into master and sub-problem to address the exponential increase of variables, due to the constraint reduction. Furthermore, the dynamic multi-depot CDVRPD was also reduced to a single depot CDVRPD by merely introducing virtual pickup points and, eventually, a good initial solution was applied, computed by the Clarke and Wrights Saving Algorithm [110], which reduced the computation burden further. A real case study based on the Gustavo Hurricane evacuation in Gulfport was adopted and simulated while using the CORSIM network development to validate the model. An in-building evacuation problem is studied by [111]. The Building Information Model (BIM) is converted to a graph network in order to approach the evacuation problem from the perspective of Time Dependent VRP (TDVRP). In order to determine the closest exits for each evacuees, a single shortest path algorithm is applied, such as [PERSON]'s or the Dijkstra algorithm. The route from the group of evacuees to each of their exits is then computed from the TDVRP model. If the numbers of evacuees within the group is more than allowed, clustering method k-medoids is applied to partition evacuees in that particular group to each assigned exits. In this problem, the exit is considered as depots, while the demand points are where the evacuees are located. The problem is again solved by solving the TDVRP model formulated as a MIP with the objective of minimising the arrival of the last returning rescue team. A more complex evacuation problem is addressed in [112], where the stochasticity of a storm scenario and loss of life, as well as uncertain travel time, is considered. Focus is given in the two-stage stochastic programming apart from the proposed deterministic model for allocation budgets for various operations that are needed during the post wildfire debris flow. The objective function carries the objective from the deterministic model, which is to minimise the expected total damage for all clustered area, where probability distribution determines the uncertain storm.