## 4 Review of Literature
### Evacuation in Routing Optimisation Problems
#### 4.2.2 Heuristics and Local Search in Evacuation VRPs  
An interesting problem is addressed by [121] where a livestock evacuation plan is optimised based on the heuristic version of a Lagrange Relaxation method. Inspired by the earthquake and tsunami events in Fukushima in 2011, the livestock is evacuated via vehicles to prevent contamination from radioactive exposure known for causing harmful effects on bone marrow and thyroid. The problem is formulated into two models each to maximise evacuated livestock as well as minimising the vehicle numbers respectively. The first model addressed both dynamic setting and uncertain road accessibility which is addressed through probability obtained by simulations. Meanwhile, the second model which is said to be more realistic is based on a deterministic VRP model employing graph theory as opposed to the network flow model of the first model. One decision variable is proposed namely the number of evacuated livestock traversing the arc at time \(t\) in the first model. Meanwhile, the second model addressed two decision variables where the decision of vehicle travelling an arc and decision to allocate capacity to each demand node are proposed respectively. In this research, ref. [121] further argued that in times of emergency, a sub-optimal evacuation plan would be more realistic as opposed to optimal solution computation which would consume valuable time. Thus, the complex integer programming models are both solved by utilising a modified Lagrange Multiplier heuristic which is considered simple yet efficient in solving the problem. This method solved the problem via Lagrange Relaxation partially until a satisfying evacuated livestock number is reached. The computation is then halted to allow for the rounding up phase where the fractional computed flow is rounded based on the worst-case scenario. A similar concept is also applied to solve the second model. The models and solutions are then validated through generated instances with comparisons made based on the solutions computed by [PERSON]. A case study based on the earthquake and tsunami events in Fukushima in 2011 is applied, where the transportation network and the number of livestock are referred to. A safety distance is determined as well as the time limit for evacuation in the first formulation. The second formulation, on the other hand, is based on a fixed fleet of vehicles that is determined based on the feasibility of the solution for the second model. Near-optimal solution quality is observed, which is comparable to the solution that is provided by [PERSON]. The evacuation planning focusing on both the routing and flow of evacuation on the generated optimised path is considered by [122]. An optimised flow of evacuation eliminates the occurrence of congestion that could hinder an effective evacuation plan as a whole, even if the routing is optimised. The problem is modelled through an evacuation graph with nodes representing evacuated node, safe nodes and transit nodes as well as edges representing roads. The objective is to maximise the number of evacuees reaching the safe nodes via vehicles. This problem is solved by a Conflict based Path Generation (CPG) heuristic that was developed to decouple the problem into sub-problem and master problem. Here, the sub-problem generates an optimised path and, as a result, adds a new column and row to the master problem. The master problem, on the other hand, solved the optimised flow in response to the generated path via the scheduling of the evacuation. The cycle of sub-problem and master problem iteration is repeated until convergence is observed based on a determined characteristic. The Hawkesbury Napeon case study is adopted, where a flood evacuation is necessary once every 200 years involving 70,000 victims. The CPG with and without contraflow is compared, showing greater improvement in the former. A CVRP with simulated demand as part of the three stages in developing a DSS integrating the GIS is studied in [123].