Vehicle Route Planning for Relief Item Distribution under Flood Uncertainty

Abstract

Flooding, a pervasive and severe natural disaster, significantly damages environments and infrastructure and endangers human lives. In affected regions, disruptions to transportation networks often lead to critical shortages of essential supplies, such as food and water. The swift and adaptable delivery of relief goods via vehicle is vital to sustain life and facilitate community recovery. This paper introduces a novel model, the Vehicle Routing Problem for Relief Item Distribution under Flood Uncertainty (VRP-RIDFU), which focuses on optimizing the speed of route generation and minimizing waiting times for aid delivery in flood conditions. The Genetic Algorithm (GA) is employed because it effectively handles the uncertainties typical of NP-Hard problems. This model features a dual-population strategy: random and enhanced populations, with the latter specifically designed to manage uncertainties through anticipated route performance evaluations, incorporating factors like waiting times and flood risks. The Population Sizing Module (PSM) is implemented to dynamically adjust the population size based on the dispersion of affected nodes, using standard deviation assessments. Introducing the Complete Subtour Order Crossover (CSOX) method improves solution quality and accelerates convergence. The model’s efficacy is validated through simulated flood scenarios that emulate various degrees of uncertainty in road conditions, affirming its practicality for real-life rescue operations. Focusing on prioritizing waiting times over travel times in routing decisions has proven effective. The model has been tested using standard CVRP problems with 20 distinct sets, each with varying node numbers and patterns, demonstrating superior performance and efficiency in generating vehicle routing plans compared to the shortest routes, which serve as the benchmark for optimal solutions. The results highlight the model’s capability to deliver high-quality solutions more rapidly across all tested scenarios.

Keywords

• vehicle routing
• relief distribution
• uncertainty
• genetic algorithms
• disasters
• floods