Team applies variable reduction strategy to improve emergency material scheduling
When real-world disasters occur, logistics play a crucial role in emergency disaster management. Emergency material scheduling is a vital piece of the emergency logistics plan. Having a reasonable and efficient emergency material scheduling plan is essential in order to save lives and reduce property losses.
A research team has applied a variable reduction strategy to an emergency material scheduling problem. This accelerated the optimization process of the algorithms that were already being used and obtained better solutions by simplifying the corresponding emergency material schedule problem.
Their research is published in the journal Complex System Modeling and Simulation on June 20.
Emergency material scheduling is mainly focused on making the best plan to deliver emergency materials from supply points to demand points quickly and efficiently, so that casualties and property losses are minimized. However, real-world emergency material scheduling problems are often large-scale and involve complex constraints.
Researchers typically use an evolutionary algorithm as one of the effective methods for solving emergency material scheduling problems. Evolutionary algorithms, inspired by nature phenomena and biologic behaviors, show competitive performance in solving optimization problems. However, the existing evolutionary algorithms still face great challenges when dealing with large-scale emergency material scheduling problems or problems with equality constraints.
To solve the challenges that the existing evolutionary algorithms face, the research team began by defining an emergency material allocation and route scheduling model, with a variable neighborhood search and NSGA-II hybrid algorithm designed to solve the model. Next, they applied the variable reduction strategy to simplify the proposed emergency material scheduling model to allow a lower dimension and fewer equality constraints. (When using a variable reduction strategy, researchers are able to reduce some of variables and equations in order to reduce the complexity of the problem.) Taking it a step further, the team integrated the variable reduction strategy with the NSGA-II hybrid algorithm to solve the reduced emergency material scheduling model.
To prove the effectiveness of variable reduction strategy on the NSGA-II hybrid algorithm, the team constructed two test cases. One case was based on a multi-depot vehicle routing problem. The other case was based on the real-life initial emergency material support situation that occurred on May 12, 2008 when an earthquake devastated the Wenchuan area in the Sichuan Province of China.
"Experimental results show that variable reduction strategy can improve the performance of the standard NSGA-II hybrid algorithm, enabling better optimization efficiency and a higher-quality solution," said Guohua Wu, a professor at the Central South University in China.
The team proposed the variable reduction strategy initially because it allowed them to obtain a lower dimension of solution space and eliminate partial equality constraints. Variable reduction strategy explores the relationships among variables by using the general problem domain knowledge that is implied in an optimization problem. Based on relationships among variables, the team always used some of the variables to represent and calculate the rest of the variables during the repeated process of the algorithm. This means the optimization problem possessed a lower dimension of solution space and fewer variables.
Looking ahead to future research, the team notes that there are still limitations in this work. They acknowledge that the emergency material scheduling model they considered was slightly simple.
"Therefore, for future work, we can consider applying the variable reduction strategy to a more complex emergency material schedule model with dynamic demands, multiple materials, and different vehicle capacities," said Wu.
Additionally, the team notes that it would be worthwhile to conduct more research into integrating another potential evolutionary algorithm with variable reduction strategy in order to assist the evolutionary algorithm to perform better. While the team's current work provides a reference for employing the variable reduction strategy to effectively solve real-world problems, they might also focus on using the variable reduction strategy to solve more complicated real-world optimization problems in the future.
The research team includes Zhen Shu from the National University of Defense Technology, Changsha, China; Aijuan Song and Guohua Wu from the Central South University, Changsha, China; and Witold Pedrycz from the University of Alberta, Edmonton, Canada.
More information: Zhen Shu et al, Variable Reduction Strategy Integrated Variable Neighborhood Search and NSGA-II Hybrid Algorithm for Emergency Material Scheduling, Complex System Modeling and Simulation (2023). DOI: 10.23919/CSMS.2023.0006