## 4 Review of Literature
### Evacuation in Routing Optimisation Problems
#### 4.2.2 Heuristics and Local Search in Evacuation VRPs
In this problem, the simulated demand is obtained through the population estimation algorithm that estimates both the criticality of the demand as well as the demand itself. However, the demand or the population is deemed to be uncertain, as in the case of the population in Phuket, which mostly consists of vacationers and locals, depending on the season. As such, the GIS enables the population estimation to be applied in order to execute the Monte Carlo sampling to estimate the demand of a node. In this model, the total distance travelled is minimised. The tsunami prone Phuket is identified as potential emergency location, where its population is estimated as a form of evacuation demand. The problem is solved by constructive heuristic while using the Clark and Wright Savings algorithm. Meanwhile the aerial vehicle routing for an evacuation plan is addressed in [124]. The characteristic of the helicopters as rescue vehicle and the urgency level of the victim is captured through the concept of agent-based modelling. Based on this concept, the rules of interaction between the rescue agent--also named as the vehicle agent--and the demand agent--or the victim--is proposed. A realistic representation of the problem is reflected based on these characteristics. A nonlinear optimisation problem is formulated, where the objective is to maximise the number of saved evacuees. This problem is solved by the proposed heuristic namely the Cooperative Multi Agent (CMA) based algorithm where the rules of interaction is considered in solving the problem. The initial solution computed by the vehicle agents based on the information obtained from the demand agents and the safe location is evaluated by the demand agents in order to improve the quality of the solution by means of replying what is to be removed or inserted in the task list. Vehicle agents then update its task list by means of removing or inserting demands into the task list and this new task list is further evaluated. This process continues for as long as there is a request of updating task list from the demand agents. A numerical experiment is performed in order to validate the model that is based on the 2011 earthquake and tsunami in Japan. The wild fire evacuation optimisation process is considered in [125], by taking the dynamic changes of the route due to spreading fire into consideration. Based on the flow model depiction, a single destination is considered from multiple evacuation locations. All of the evacuees are assumed to start evacuation at the same time, which is regarded as group evacuees, where they share the same computed route for evacuation. The Capacity Aware Shortest Path Evacuation Router (CASPER) is used interchangeably with the CapacityAware Reverse Map Analyser (CARMA) in order to compute the route for all evacuees. The objective is to minimise the final departure time of evacuees with CASPER being assigned to the load dynamic and static input of the problem, while CARMA transforms the network GIS data into a graphical network and seeks for the solution based on the single Dijkstra algorithm of each shortest path tree. While the computation is improved in searching for the routes, the observed egress time is not minimised, thus an iterative heuristic is proposed where a repair mechanism is applied to a pre-computed solution with disadvantages with a new paths until an applicable solution is obtained. In this heuristic, the conflicting and competing two potential paths over edges is defined. A worst case scenario of wild fire in California is adapted in order to test the model and algorithm. In [126], the problem of evacuating evacuees with disabilities is addressed based on their categories by a fleet of heterogeneous vehicles. Here, the vehicle ranged from ambulances, vehicles that are capable of carrying only normal evacuees, as well as vehicles for carrying evacuees with wheelchairs.