Optimization Model and Algorithm for Emergency Material Scheduling Considering Road Constraints
WANG Fuyua,b, ZHANG Kanga
a. School of Management Science and Engineering; b. Key Laboratory of Multidisciplinary Management and Control of Complex Systems of Anhui Higher Education Institutes, Anhui University of Technology, Maanshan 243002, China
Abstract：In order to make full use of emergency supplies and improve emergency response capacity, a multi-objective optimization model was established to minimize the average waiting time of disaster sites and the dispatching cost of emergency supplies, taking into account the constraints of road passage and transportation capacity in the initial stage of disaster. Population entropy and Gaussian function were introduced by the improved NSGA-II, based on adaptive mechanism, to dynamically adjust mutation and crossover probability, and combined mutation and crossover process with horizontal and vertical information of evolution to guide population evolution and improve evolution speed. A random variable neighborhood search operator based on greedy idea was designed to fully explore the solution space. The influence of the same on evolution in Pareto frontier was eliminated by adjusting the strategy. An example was given to verify the proposed algorithm, and the results shown that the proposed algorithm was superior to the traditional NSGA-II algorithm and the known literature algorithm, and maintained good convergence and obtained better diversity.
王付宇, 张康. 考虑道路约束的应急物资调度优化模型与算法[J]. 复杂系统与复杂性科学, 2022, 19(2): 53-62.
WANG Fuyu, ZHANG Kang. Optimization Model and Algorithm for Emergency Material Scheduling Considering Road Constraints. Complex Systems and Complexity Science, 2022, 19(2): 53-62.
[1] LIST G F, TURNQUIST M A. Routing and emergency response team siting for high-level radioactive waste shipments[J]. IEEE Transactions on Engineering Management,1998,45(2):141-152. [2] 王海军,王婧,马士华, 等. 模糊供求条件下应急物资动态调度决策研究[J]. 中国管理科学,2014,22(1):55-64. WANG H J,WANG J, MA S H,et al. Decision making for emergency materials dynamic dispatching based on fuzzy demand and supply[J]. Chinese Journal of Management Science,2014,22(1):55-64. [3] 段晓红,吴家新,周芷晴. 基于层次蝙蝠算法的应急车辆调度与交通疏散协同决策[J]. 交通运输系统工程与信息,2020,20(2):157-165. DUAN X H,WU J X, ZHOU Z Q. Collaborative decision making of emergency vehicle scheduling and traffic evacuation based on bi-level bat algorithm[J]. Journal of Transportation Systems Engineering and Information Technology, 2020,20(2):157-165. [4] 王付宇,丁杰. 基于改进天牛须算法的应急资源调度优化[J]. 安全与环境学报, 2020,20(6):2278-2285. WANG F Y, DING J. Research on optimization of emergency resource scheduling based on improved beetle antennae search algorithm[J]. Journal of Safety and Environment,2020,20(6):2278-2285. [5] YI W, ÖZDAMAR L. A dynamic logistics coordination model for evacuation and support in disaster response activities[J]. European Journal of Operational Research, 2007, 179(3): 1177-1193. [6] MORENO A, ALEM D, FERREIRA F.Heuristic approaches for the multiperiod location transportation problem with reuse of vehicles in emergency logistics[J]. Computers and Operations Research,2016,69:79-96. [7] HU Z H.A container multimodal transportation scheduling approach based on immune affinity model for emergency relief[J]. Expert Systems With Applications,2011,38(3):2632-2639. [8] FIKAR C,GRONALT M, HIRSCH P. A decision support system for coordinated disaster relief distribution[J]. Expert Systems With Applications,2016,57:104-116. [9] 陈雷雷,王海燕.大规模突发事件中基于满意度的应急物资优化调度模型[J].中国安全科学学报,2010,20(5):46-52. CHEN L L, WANG H Y. Optimal scheduling model for emergency logistics based on satisfaction under large scale emergencies[J]. China Safety Science Journal,2010,20(5):46-52. [10] 阮俊虎,王旭坪,杨挺.大规模灾害中基于FCMwNC的医疗物资联合运送优化[J].系统工程理论与实践,2015,35(10):2675-2686. RUAN J H, WANG X P, YANG T. A FCMwNC-based approach for medical supplies inter modal transportation in large-scale disasters[J]. Systems Engineering Theory & Practice,2015,35(10):2675-2686. [11] RUAN J H,WANG X P,CHAN F T S,et al. Optimizing the intermodal transportation of emergency medical suppl-ies using balanced fuzzy clustering[J]. International Journal of Production Research,2016,54(14):4368-4386. [12] ERDEMIR E T,BATTA R, ROGERSON P A, et al.Joint ground and air emergency medical services coverage models: a greedy heuristic solution approach[J]. European Journal of Operational Research,2010,207(2):736-749. [13] 王旭坪,马超,阮俊虎.运力受限的应急物资动态调度模型及算法[J].系统工程理论与实践,2013,33(6):1492-1500. WANG X P, MA C, RUAN J H. Model and algorithm of relief materials d-dynamic scheduling without sufficient vehicle quantity[J]. Systems Engineering Theory & Practice,2013,33(6):1492-1500. [14] 薛星群,王旭坪,韩涛,等. 考虑通行约束和运力限制的灾后应急物资联合调度优化研究[J].中国管理科学,2020,28(3):21-30. XUE X Q, WANG X P, HAN T, et al. Study on joint dispatch optimization of emergency materials considering traffic constraints and capacity limits[J]. Chinese Journal of Management Science, 2020,28(3):21-30. [15] 赖文星,邓忠民. 基于支配强度的NSGA2改进算法[J].计算机科学,2018,45(6):187-192. LAI W X, DENG Z M. Improved NSGA2 algorithm based on dominant strength[J]. Computer Science, 2018, 45(6):187-192. [16] 陈辅斌, 李忠学,杨喜娟. 基于改进NSGA-II算法的多目标柔性作业车间调度[J].工业工程,2018,21(2):55-61. CHEN F B, LI Z X, YANG X J. Multi-objective flexible job shop scheduling based on improved NSGA2 algorithm[J]. Industrial Engineering Journal, 2018,21(2):55-61. [17] 张国富,王永奇,苏兆品,等.应急救援物资多目标分配与调度问题建模与求解[J].控制与决策,2017,32(1):86-92. ZHANG G F, WANG Y Q, SU Z P, et al. Modeling and solving multi-objective allocation scheduling of emergency relief supplies[J]. Control and Decision,2017,32(1):86-92. [18] 李燕,赵红,牟亮,等.基于改进NSGA-Ⅱ的左转待行区交叉口配时优化控制[J].复杂系统与复杂性科学,2021,18(1):88-94. LI Y, ZHAO H, MOU L, et al. Optimal control of left turn waiting area intersection timing based on improved NSGA-Ⅱ[J]. Complex Systems and Complexity Science, 2021,18(1): 88-94. [19] 王付宇,汤涛,李艳,等.疫情事件下多灾点应急资源最优化配置研究[J].复杂系统与复杂性科学,2021,18(1):53-62. WANG F Y, TANG T, LI Y, et al. Study on optimal allocation of emergency resources at multiple disaster sites under epidemic events [J]. Complex Systems and Complexity Science, 2021,18(1): 53-62. [20] ALMANSOUR F M, ALROOBAEA R,GHIDUK A S. An empirical comparison of the efficiency and effectiveness of genetic algorithms and adaptive random techniques in data-flow testing[J].IEEE Access,2020,8:12884-12896. [21] SRINIVAS M, PATNAIK L M. Adaptive probabilities of crossover and mutation in genetic algorithms[J]. IEEE Transactions on Systems, Man, and Cybernetics, 1994,24(4): 656-667. [22] 任子武,伞冶.自适应遗传算法的改进及在系统辨识中应用研究[J].系统仿真学报,2006,18(1):41-43,66. REN Z W, SAN Y. Improvement of adaptive genetic algorithm and its application in system identification[J]. Journal of System Simulation, 2006,18(1): 41-43,66. [23] 王雷,李明.改进自适应遗传算法在移动机器人路径规划中的应用[J].南京理工大学学报,2017,41(5):627-633. WANG L, LI M. Application of improved adaptive genetic algorithm in mobile robot path planning[J]. Journal of Nanjing University of Technology, 2017,41(5): 627-633. [24] 张国强,彭晓明.自适应遗传算法的改进与应用[J].舰船电子工程,2010,30(1):83-84,159. ZHANG G Q, PENG X M. Improvement and application of adaptive genetic algorithm [J]. Naval Electronic Engineering, 2010,30(1): 83-84,159. [25] 邬峰,黄丽亚.自适应模拟退火遗传算法的改进与应用[J].微型机与应用,2010,29(9):84-86,90. WU F,HUANG L Y. Improvement and application of adaptive simulated annealing genetic algorithm[J]. Microcomputer and Application, 2010,29(9): 84-86,90. [26] 邵增珍,王洪国,刘弘.具有启发式探测及自学习特征的降维对称微粒群算法[J].计算机科学,2010,37(5):219-222. SHAO Z Z, WANG H G, LIU H. Dimensionality reduction symmetrical pso algorithm characterized by heuristic detection and self-learning[J]. Computer Science,2010,37(5):219-222. [27] 雷德明, 严新平. 多目标智能优化算法及其应用[M]. 北京: 科学出版社,2009:38-41.
