Two-echelon vehicle routing problem for post-disaster aid - Nguyen, Dang Viet Anh (Nanyang Technological University, 2023)
Extreme weather events and natural disasters cause heavy damage to both human lives and infrastructure, creating isolated areas. The immediate response in the aftermath of a disaster is to provide essentials such as food, drinkable water, and medicine to the people in isolated areas. The problem of transporting relief goods and necessities to the affected area after a disaster deal with the multi level routing problem at the operational level. The challenge in this transportation problem comes from the disruption in the road network to reach the victim locations. The thesis develops a two-echelon vehicle routing problem for application in transportation and supply of necessities to affected areas in the response phase of disaster relief. The first echelon of the problem solves the routing decisions to transport supplies from the primary warehouse to intermediate warehouses or satellites located near the affected area. The second echelon concerns last-mile delivery from the intermediate warehouses to residential clusters in affected area. This research develops an intermodal network consisting of a fleet of trucks responsible for transferring supplies at the first level while drones perform the last-mile delivery task. The 2E-CTVRP helps to leverage the advantages of each type of vehicle to overcome difficulties caused by the disaster to achieve high operational efficiency. Due to the limited response time and equipment, the drones do not necessarily directly visit the demand nodes but deliver supplies to a predefined location in each affected area cluster. To ensure distribution equity, the K-means++ algorithm is utilized to cluster the victim location data and determine the drop-off positions of drones in affected areas. In this study, the mathematical model of 2E-CTVRP is formulated as MILP with the objective function of minimizing the sum of arrival time to solve small-size instances optimally. Moreover, A hybrid metaheuristic based on the Greedy Randomized Adaptive Search Procedure (GRASP) reinforced by path relinking is proposed to achieve solutions for larger instances in a reasonable computing time. The computational experiment on instances with two types of truck fleet sizes at the first echelon is analyzed and presented.