Journal Home > Volume 3 , Issue 2
Complex System Modeling and Simulation 2023, 3(2): 83-101 https://doi.org/10.23919/CSMS.2023.0006
Open Access | Issue | Published: 20 June 2023

Variable Reduction Strategy Integrated Variable Neighborhood Search and NSGA-II Hybrid Algorithm for Emergency Material Scheduling

Show Author's Information Zhen Shu1,  Aijuan Song2,  Guohua Wu2( ),  Witold Pedrycz3
College of Systems Engineering, National University of Defense Technology, Changsha 410073, China
School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China
Department of Electrical and Computer Engineering, University of Alberta, Edmonton, AB T6G 2V4, Canada, and also with the Systems Research Institute, Polish Academy of Sciences, Warsaw 01447, Poland
Keywords:
evolutionary algorithm, emergency material scheduling, variable reduction strategy
Cite this article:
Shu Z, Song A, Wu G, et al. Variable Reduction Strategy Integrated Variable Neighborhood Search and NSGA-II Hybrid Algorithm for Emergency Material Scheduling. Complex System Modeling and Simulation, 2023, 3(2): 83-101. https://doi.org/10.23919/CSMS.2023.0006
Download citation
EndNote(RIS)
BibTeX

692

Views

59

Downloads

Citations

0

Crossref

N/A

WoS

1

Scopus

N/A

CSCD

Abstract Full text About this article

Developing a reasonable and efficient emergency material scheduling plan is of great significance to decreasing casualties and property losses. Real-world emergency material scheduling (EMS) problems are typically large-scale and possess complex constraints. An evolutionary algorithm (EA) is one of the effective methods for solving EMS problems. However, the existing EAs still face great challenges when dealing with large-scale EMS problems or EMS problems with equality constraints. To handle the above challenges, we apply the idea of a variable reduction strategy (VRS) to an EMS problem, which can accelerate the optimization process of the used EAs and obtain better solutions by simplifying the corresponding EMS problems. Firstly, we define an emergency material allocation and route scheduling model, and a variable neighborhood search and NSGA-II hybrid algorithm (VNS-NSGAII) is designed to solve the model. Secondly, we utilize VRS to simplify the proposed EMS model to enable a lower dimension and fewer equality constraints. Furthermore, we integrate VRS with VNS-NSGAII to solve the reduced EMS model. To prove the effectiveness of VRS on VNS-NSAGII, we construct two test cases, where one case is based on a multi-depot vehicle routing problem and the other case is combined with the initial 5∙12 Wenchuan earthquake emergency material support situation. Experimental results show that VRS can improve the performance of the standard VNS-NSGAII, enabling better optimization efficiency and a higher-quality solution.


menu
Abstract
Full text
Outline
About this article

Variable Reduction Strategy Integrated Variable Neighborhood Search and NSGA-II Hybrid Algorithm for Emergency Material Scheduling

Show Author's information Zhen Shu1, Aijuan Song2, Guohua Wu2( ), Witold Pedrycz3
College of Systems Engineering, National University of Defense Technology, Changsha 410073, China
School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China
Department of Electrical and Computer Engineering, University of Alberta, Edmonton, AB T6G 2V4, Canada, and also with the Systems Research Institute, Polish Academy of Sciences, Warsaw 01447, Poland

Abstract

Developing a reasonable and efficient emergency material scheduling plan is of great significance to decreasing casualties and property losses. Real-world emergency material scheduling (EMS) problems are typically large-scale and possess complex constraints. An evolutionary algorithm (EA) is one of the effective methods for solving EMS problems. However, the existing EAs still face great challenges when dealing with large-scale EMS problems or EMS problems with equality constraints. To handle the above challenges, we apply the idea of a variable reduction strategy (VRS) to an EMS problem, which can accelerate the optimization process of the used EAs and obtain better solutions by simplifying the corresponding EMS problems. Firstly, we define an emergency material allocation and route scheduling model, and a variable neighborhood search and NSGA-II hybrid algorithm (VNS-NSGAII) is designed to solve the model. Secondly, we utilize VRS to simplify the proposed EMS model to enable a lower dimension and fewer equality constraints. Furthermore, we integrate VRS with VNS-NSGAII to solve the reduced EMS model. To prove the effectiveness of VRS on VNS-NSAGII, we construct two test cases, where one case is based on a multi-depot vehicle routing problem and the other case is combined with the initial 5∙12 Wenchuan earthquake emergency material support situation. Experimental results show that VRS can improve the performance of the standard VNS-NSGAII, enabling better optimization efficiency and a higher-quality solution.

Keywords: evolutionary algorithm, emergency material scheduling, variable reduction strategy

References(42)

[1]

S. J. Pettit and A. K. C. Beresford, Emergency relief logistics: An evaluation of military, non-military and composite response models, International Journal of Logistics:Research and Applications, vol. 8, no. 4, pp. 313–331, 2005.
DOI Google Scholar
[2]

H. Hu, J. He, X. He, W. Yang, J. Nie, and B. Ran, Emergency material scheduling optimization model and algorithms: A review, Journal of Traffic and Transportation Engineering (English Edition), vol. 6, no. 5, pp. 441–454, 2019.
DOI Google Scholar
[3]

S. Nayeri, R. Tavakkoli-Moghaddam, Z. Sazvar, and J. Heydari, A heuristic-based simulated annealing algorithm for the scheduling of relief teams in natural disasters, Soft Computing, vol. 26, pp. 1825–1843, 2022.
DOI Google Scholar
[4]

Z. Su, G. Zhang, Y. Liu, F. Yue, and J. Jiang, Multiple emergency resource allocation for concurrent incidents in natural disasters, International Journal of Disaster Risk Reduction, vol. 17, pp. 199–212, 2016.
DOI Google Scholar
[5]

T. Chen, S. Wu, J. Yang, G. Cong, and G. Li, Modeling of emergency supply scheduling problem based on reliability and its solution algorithm under variable road network after sudden-onset disasters, Complexity, vol. 2020, no. 1, pp. 1–15, 2020.
DOI Google Scholar
[6]

K. G. Zografos and K. N. Androutsopoulos, A decision support system for integrated hazardous materials routing and emergency response decisions, Transportation Research Part C:Emerging Technologies, vol. 16, no. 6, pp. 684–703, 2008.
DOI Google Scholar
[7]

F. Wex, G. Schryen, S. Feuerriegel, and D. Neumann, Emergency response in natural disaster management: Allocation and scheduling of rescue units, European Journal of Operational Research, vol. 235, no. 3, pp. 697–708, 2014.
DOI Google Scholar
[8]

B. Bodaghi, E. Palaneeswaran, S. Shahparvari, and M. Mohammadi, Probabilistic allocation and scheduling of multiple resources for emergency operations; a Victorian bushfire case study, Computers,Environment and Urban Systems, vol. 81, p. 101479, 2020.
DOI Google Scholar
[9]

C. -C. Lu, K. -C. Ying, and H. -J. Chen, Real-time relief distribution in the aftermath of disasters—A rolling horizon approach, Transportation Research Part E:Logistics and Transportation Review, vol. 93, pp. 1–20, 2016.
DOI Google Scholar
[10]

T. Vidal, T. G. Crainic, M. Gendreau, and C. Prins, A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows, Computers &Operations Research, vol. 40, no. 1, pp. 475–489, 2013.
DOI Google Scholar
[11]

R. Das, Disaster preparedness for better response: Logistics perspectives, International Journal of Disaster Risk Reduction, vol. 31, pp. 153–159, 2018.
DOI Google Scholar
[12]
B. K. Mishra, K. Dahal, and Z. Pervez, Dual-mode round-robin greedy search with fair factor algorithm for relief logistics scheduling, in Proc. 2017 4th International Conference on Information and Communication Technologies for Disaster Management (ICT-DM), Münster, Germany, 2017, pp. 1–7.
DOI
[13]

L. Chen, Y. Li, Y. Chen, N. Liu, C. Li, and H. Zhang, Emergency resources scheduling in distribution system: From cyber-physical-social system perspective, Electric Power Systems Research, vol. 210, p. 108114, 2022.
DOI Google Scholar
[14]

J. M. Ferrer, F. J. Martín-Campo, M. T. Ortuño, A. J. Pedraza-Martínez, G. Tirado, and B. Vitoriano, Multi-criteria optimization for last mile distribution of disaster relief aid: Test cases and applications, European Journal of Operational Research, vol. 269, no. 2, pp. 501–515, 2018.
DOI Google Scholar
[15]

Y. Wang, S. Peng, and M. Xu, Emergency logistics network design based on space–time resource configuration, Knowledge-Based Systems, vol. 223, p. 107041, 2021.
DOI Google Scholar
[16]
Z. Li, C. Xie, P. Peng, X. Gao, and Q. Wan, Multi-objective location-scale optimization model and solution methods for large-scale emergency rescue resources, Environmental Science and Pollution Research,
[17]

Z. Ding, X. Xu, S. Jiang, J. Yan, and Y. Han, Emergency logistics scheduling with multiple supply-demand points based on grey interval, Journal of Safety Science and Resilience, vol. 3, no. 2, pp. 179–188, 2022.
DOI Google Scholar
[18]

F. Wan, H. Guo, J. Li, M. Gu, W. Pan, and Y. Ying, A scheduling and planning method for geological disasters, Applied Soft Computing, vol. 111, p. 107712, 2021.
DOI Google Scholar
[19]

A. Zahedi, M. Kargari, and A. H. Kashan, Multi-objective decision-making model for distribution planning of goods and routing of vehicles in emergency multi-objective decision-making model for distribution planning of goods and routing of vehicles in emergency, International Journal of Disaster Risk Reduction, vol. 48, p. 101587, 2020.
DOI Google Scholar
[20]

F. -S. Chang, J. -S. Wu, C. -N. Lee, and H. -C. Shen, Greedy-search-based multi-objective genetic algorithm for emergency logistics scheduling, Expert Systems with Applications, vol. 41, no. 6, pp. 2947–2956, 2014.
DOI Google Scholar
[21]

L. Gouveia, M. Leitner, and M. Ruthmair, Extended formulations and branch-and-cut algorithms for the black-and-white traveling salesman problem, European Journal of Operational Research, vol. 262, no. 3, pp. 908–928, 2017.
DOI Google Scholar
[22]

Y. Wang and B. Sun, Multiperiod optimal emergency material allocation considering road network damage and risk under uncertain conditions, Operational Research, vol. 22, no. 3, pp. 2173–2208, 2022.
DOI Google Scholar
[23]
J. H. Holland, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. Cambridge, MA, USA: MIT Press, 1992.
DOI
[24]

M. Dorigo, V. Maniezzo, and A. Colorni, Ant system: Optimization by a colony of cooperating agents, IEEE Transactions on Systems,Man,and Cybernetics,Part B (Cybernetics), vol. 26, no. 1, pp. 29–41, 1996.
DOI Google Scholar
[25]
R. Eberhart and J. Kennedy, A new optimizer using particle swarm theory, in Proc. Sixth International Symposium on Micro Machine and Human Science, Nagoya, Japan, 1995, pp. 39–43.
[26]

R. Storn and K. Price, Differential evolution—A simple and efficient heuristic for global optimization over continuous spaces, Journal of Global Optimization, vol. 11, no. 4, pp. 341–359, 1997.
DOI Google Scholar
[27]

H. -G. Beyer and H. -P. Schwefel, Evolution strategies—A comprehensive introduction, Natural Computing, vol. 1, pp. 3–52, 2002.
DOI Google Scholar
[28]

T. Wang, K. Wu, T. Du, and X. Cheng, Adaptive weighted dynamic differential evolution algorithm for emergency material allocation and scheduling, Computational Intelligence, vol. 38, no. 3, pp. 714–730, 2022.
DOI Google Scholar
[29]

A. B. Amiri, M. Akbari, and I. Dadashpour, A routing-allocation model for relief logistics with demand uncertainty: A genetic algorithm approach, Journal of Industrial Engineering and Management Studies, vol. 8, no. 2, pp. 93–110, 2021.
Google Scholar
[30]

M. E. Shafiee and E. Z. Berglund, Agent-based modeling and evolutionary computation for disseminating public advisories about hazardous material emergencies, Computers,Environment and Urban Systems, vol. 57, pp. 12–25, 2016.
DOI Google Scholar
[31]

J. Liu and K. Xie, Emergency materials transportation model in disasters based on dynamic programming and ant colony optimization, Kybernetes, vol. 46, no. 4, pp. 656–671, 2017.
DOI Google Scholar
[32]

Q. Zhang and S. Xiong, Routing optimization of emergency grain distribution vehicles using the immune ant colony optimization algorithm, Applied Soft Computing, vol. 71, pp. 917–925, 2018.
DOI Google Scholar
[33]

Y. Zhou, J. Liu, Y. Zhang, and X. Gan, A multi-objective evolutionary algorithm for multi-period dynamic emergency resource scheduling problems, Transportation Research Part E:Logistics and Transportation Review, vol. 99, pp. 77–95, 2017.
DOI Google Scholar
[34]

Q. Zhang and H. Li, MOEA/D: A multiobjective evolutionary algorithm based on decomposition, IEEE Transactions on Evolutionary Computation, vol. 11, no. 6, pp. 712–731, 2007.
DOI Google Scholar
[35]

G. Wu, W. Pedrycz, P. N. Suganthan, and R. Mallipeddi, A variable reduction strategy for evolutionary algorithms handling equality constraints, Applied Soft Computing, vol. 37, pp. 774–786, 2015.
DOI Google Scholar
[36]

G. Wu, W. Pedrycz, P. N. Suganthan, and H. Li, Using variable reduction strategy to accelerate evolutionary optimization, Applied Soft Computing, vol. 61, pp. 283–293, 2017.
DOI Google Scholar
[37]

A. Song, G. Wu, W. Pedrycz, and L. Wang, Integrating variable reduction strategy with evolutionary algorithms for solving nonlinear equations systems, IEEE/CAA Journal of Automatica Sinica, vol. 9, no. 1, pp. 75–89, 2021.
DOI Google Scholar
[38]

X. Shen, G. Wu, R. Wang, H. Chen, H. Li, and J. Shi, A self-adapted across neighborhood search algorithm with variable reduction strategy for solving non-convex static and dynamic economic dispatch problems, IEEE Access, vol. 6, pp. 41314–41324, 2018.
DOI Google Scholar
[39]
A. Song, G. Wu, P. Suganthan, and W. Pedrycz, Automatic variable reduction, IEEE Transactions on Evolutionary Computation,
[40]

J. Li, P. M. Pardalos, H. Sun, J. Pei, and Y. Zhang, Iterated local search embedded adaptive neighborhood selection approach for the multi-depot vehicle routing problem with simultaneous deliveries and pickups, Expert Systems with Applications, vol. 42, no. 7, pp. 3551–3561, 2015.
DOI Google Scholar
[41]

J. -Y. Potvin and J. -M. Rousseau, An exchange heuristic for routeing problems with time windows, Journal of the Operational Research Society, vol. 46, no. 12, pp. 1433–1446, 1995.
DOI Google Scholar
[42]

B. Zheng, Z. Ma, and S. Li, Integrated optimization of emergency logistics systems for post-earthquake initial stage based on bi-level programming, (in Chinese), Journal of Systems Engineering, vol. 29, no. 1, pp. 113–125, 2014.
Google Scholar
Publication history
Copyright
Rights and permissions

Publication history

Received: 09 January 2023
Revised: 05 March 2023
Accepted: 11 March 2023
Published: 20 June 2023
Issue date: June 2023

Copyright

© The author(s) 2023.

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return