## 4 Review of Literature
### Evacuation in Routing Optimisation Problems
#### 4.2.2 Heuristics and Local Search in Evacuation VRPs
A DVRP is considered for this problem, which is formulated as an MILP with the aim to minimise the total evacuation time, where, for the case of multiple optimal route, the route with the least travel cost is opted. The problem is solved by a proposed heuristic that is based on two concepts. The first concept develops route sequentially for vehicles according to their capacities in descending order until every vehicle exhausts its capacity. On the other hand, the second concept assigns vehicles to pickup nodes in parallel with descending capacity to corresponding descending demand at pick up nodes. The two concept heuristics are compared in both experimental instances as well as a real case of a forest fire in Teruel, Spain. The results shows that the first concept is better in terms of the total distance covered, while the second concept is more efficient in minimising the total evacuation time. A complex representation in addressing the evacuation during a bush fire is shown in [127] through the Multi Destination Capacitated Dynamic VRPTW (MDCDVRPTW). In this study, the problem of evacuating late evacuees to a safe shelter with the aim of maximising the numbers of late evacuees through a low risk route is addressed. The late evacuees reflect a realistic view on the event, where not all evacuees could board the vehicle to the shelter within the specific time window, due to the capacity of the vehicle. A GA and two heuristics are presented to solve for this complex problem. A comparison made shows that the constructive based heuristic exceeds the GA in terms of solution quality. Additionally, the exact algorithms are applied to be served as a comparative test, which again highlights the advantages of heuristic over exact solutions when dealing with larger instances. This work could also be classified under the Metaheuristic in Section 4.2.4 because this work applied both GA and heuristics as the solution methods. The evacuation planning between the warning time of flood and the time when the flood occurred is addressed in [128]. In this problem, the evacuees are evacuated via public transit bus to a safer locations with the aim of maximising the number of evacuees saved with minimum cost. Two models are presented based on the planning steps that are divided as pre- and during the flood event addressing the problem of choosing a pickup location as well as the problem of computing an optimal route from the pickup location to a safer place. In the FLP, a few candidates from a pickup location are considered, such as the bus stop, which everyone is familiar with, the location where huge population is detected, and a minimum number of existing bus stops. The FLP is formulated, such that the distance between pickup locations and their corresponding shelter is minimised. Meanwhile, the routing problems are formulated as the Split Delivery VRP, where one single shelter is denoted as the depot. Pickup locations corresponding to the shelter are the demand points and the bus is only allowed to return when its capacity is full. The problem is solved via sweep heuristic algorithm, where the simulations are executed and the performance is evaluated. In [129], a two-stage problem is formulated in order to address the issue of locating, scheduling, and routing evacuees during evacuation. The first stage dealt with determining the optimal pickup location based on the distance of the depot and safe shelter. The second stage then solved the problem of scheduling and routing of the vehicle in transporting evacuees from the computed pickup locations to the shelters. Three objectives are achieved through this solution approach, where, in the first stage, the walking time of the evacuees to the pickup locations is minimised. While, in the second stage, the total transportation time and the number of vehicles used are minimised. The first stage solution stems from clustering method that clusters the evacuees into pickup points.