## 4 Review of Literature
### Evacuation in Routing Optimisation Problems
#### 4.2.1 Exact Methods in Evacuation VRPs
In addition, the numbers of casualties and cost for picking up evacuees are added in the former objectives function in the two stage stochastic programming model. The model is then solved with Baron solvers from GAMS in order to obtain an exact solution, where a case study based on Santa Barbara Jesusita fire in 2009 is adopted. Another location and routing problem could be found in [113], which addresses the problem of rescuing victims in post-disaster scenario. In the multi-agent system, the agents represent the centre of coordination, centre of emergency, fire station including the fire engines, ambulances, and the wounded victims. The allocations of emergency centres to the wounded are performed based on the proposed Multiplicatively Weighted Network Voronoi Diagram (MWNVD) where the number of ambulances of the emergency centre are considered as the weight of the emergency centre. A PSO-MWNVD is proposed in order to further optimise the allocation of ambulance as well as minimising the gap between the estimated victim and the expected population in the Voronoi Diagram. Based on this assignment, the ambulance is dispatched from each of emergency centre to cover the service, which are denoted by the PSO-MWNVD via the optimise path computed by the Bi Level Dijkstra algorithm. District 5 in Tehran is taken as an example of rescue implementation in order to validate the solution and model. Ref. [114] focused on providing more than one optimal path while combining GIS information as well as the DSS framework. In this DSS, the spatial danger rating computed based on three different models (McArthur Fire Danger Index, Carvill Hurricane Index, and Earthquake Damage Estimation) is applied to the GIS for each three different disasters: fire, hurricane, and earthquake. From the danger rating, a buffer zone can be generated and overlapped onto the road network in order to determine which roads are compromised and blocked as well as possible safe destination to route to. Only the chosen road based on these considerations are taken for computation while using shortest path Dijkstra algorithm. The weight or cost reflecting the changing travel time is updated, depending on the parameters affecting the road conditions. The application of Autonomous Vehicles (AVs) for evacuation is considered in [115]. The deterministic model describes a set of AVs, persons to be evacuated, as well as a set of safe shelters. The problem is formulated as an integer linear programming aiming to minimise the evacuation time where a Dynamic Programming (DP) approach is applied to solve the problem. A divide and conquer strategy is utilised, making use of the fact that a small problem can be solved to optimality exactly. The division is achieved through clustering via K-means algorithm, where the evacuees are divided into groups, depending on the capacity of the AV and each group is served akin to TSP problem with one AV. This TSP problem is then solved by DP. Ref. [116] extended the work of [117] in addressing both the vehicle routing as well as the flow of arrival of evacuees pattern similar to [118], which, according to the author, would improve the effectiveness of the evacuation planning. A network consisting of two sub-network is proposed where the former addressed the maximum flow as well as the earliest arrival pattern flow of evacuees, while the latter is attributed to the vehicle routing of buses in transporting evacuees to a safe shelters with limited capacity. The objective is to minimise the total time that is taken to evacuate victims from various known pickup locations. The problem is solved through the branch and bound algorithm making use of various versions of greedy heuristic in determining the upper bound in order to improve the computation time as opposed to the conventional branch and bound algorithm. An agent based modelling is adopted by [119] in modelling the evacuation of both pedestrian and vehicle putting more focus on the evacuation by vehicle.