优化烟花算法在医疗物资应急调度中的应用

doi:10.3778/j.issn.1002-8331.2106-0459

摘要/Abstract

摘要：

新冠肺炎疫情的爆发对医疗物资的应急管理提出了新的挑战，运输难、调度慢、中转效率低等问题普遍存在，严重影响了疫情排查和患者救治。为解决突发公共卫生事件下医疗物资应急调度问题，以需求点满意度最大化为主要目标，车辆行驶时间最小化为次要目标，建立了双目标医疗物资应急调度模型。为保证模型的准确性及简便性，采用了传染病模型（SEIR）预测需求点所需医疗物资数量，并利用理想点法将双目标问题转化为单目标问题。针对模型的特点，提出了一种优化烟花算法对模型进行求解，该算法通过改变变异策略增加其局部寻优能力，此外引入了禁忌表的概念，避免了算法陷入局部最优。最后通过仿真实验证明了优化烟花算法具有更加高效的性能，可以更好地突出模型的公平性及合理性，从而快速、合理地完成医疗物资分配，最大限度地保障患者生命安全。

关键词: 烟花算法, 应急调度, 医疗物资, 传染病模型, 禁忌搜索

Abstract:

The outbreak of the COVID-19 presents new challenges for emergency management of medical supplies. Epidemic investigation and patient treatment are severely affected by problems such as difficult transportation, slow dispatch, and low transfer efficiency. In order to solve the problem of emergency dispatch of medical supplies under public health emergencies, a dual-objective emergency dispatch model of medical supplies is established. It takes the maximization of demand point satisfaction as the main goal, and the minimization of vehicle travel time as the secondary goal. The SEIR model is used to predict the amount of medical supplies required at the demand point to ensure the accuracy and simplicity of the model. The model uses the ideal point method to transform the dual-objective problem into a single-objective problem. Aiming at the characteristics of the model, an optimized firework algorithm is proposed to solve the model. It increases the ability of local optimization by changing the mutation strategy. In addition, it introduces the concept of tabu table to avoid the algorithm from falling into the local optimum. Finally, the optimized firework algorithm is proved to have more efficient performance. It can better highlight the fairness and rationality of the model, so as to quickly and reasonably complete the distribution of medical supplies, and to maximize the safety of patients’ life.

Key words: fireworks algorithm, emergency dispatch, medical supplies, mathematical models of epidemic disease, tabu search

许德刚，李凡，王露，郭奕欣，邢奎杰，梁腾翔. 优化烟花算法在医疗物资应急调度中的应用[J]. 计算机工程与应用, 2021, 57(24): 249-258.

XU Degang, LI Fan, WANG Lu, GUO Yixin, XING Kuijie, LIANG Tengxiang. Application of Optimized Fireworks Algorithm in Emergency Dispatching of Medical Supplies[J]. Computer Engineering and Applications, 2021, 57(24): 249-258.

参考文献

[1] CHEN Y，WANG Y，WANG H，et al.Controlling urban traffic-one of the useful methods to ensure safety in Wuhan based on COVID-19 outbreak[J].Safety Science，2020，131：104938.
[2] VENKATESH V.Impacts of COVID-19：a research agenda to support people in their fight[J].International Journal of Information Management，2020，55：102197.
[3] LIU M，QIAN X，LIU Z，et al.Emergency resource optimized dispatch model among multiple disaster places under one way maximum transport-capacity constraint condition[C]//2011 International Conference on Remote Sensing，Environment and Transportation Engineering，2011：1170-1174.
[4] GENG L，XIAO R，CHEN J.Resilience design of healthcare resources supply network based on self-organized criticality[J].Healthcare，2020，8（3）：245.
[5] JAGTENBERG C J，VAN DEN BERG P L，VAN DER MEI R D.Benchmarking online dispatch algorithms for emergency medical services[J].European Journal of Operational Research，2017，258（2）：715-725.
[6] LIU S，TAN W J，YU G D，et al.An emergency dispatch model considering the urgency of the requirement for reliefs in different disaster areas[J].Journal of Industrial Engineering and Management，2015，8（5）：1576-1601.
[7] SHEU J B.Challenges of emergency logistics management[J].Transportation Research Part E：Logistics and Transportation Review，2007，43（6）：655-659.
[8] HU F，BAI W，TIAN C H.Two-level dispatch system of emergency supplies with multiple objective functions using genetic algorithms[C]//2015 Sixth International Conference on Intelligent Systems Design and Engineering Applications（ISDEA），2015：906-911.
[9] AKBARI V，SALMAN F S.Multi-vehicle synchronized arc routing problem to restore post-disaster network connectivity[J].European Journal of Operational Research，2017，257（2）：625-640.
[10] RIVERA J C，AFSAR H M，PRINS C.Mathematical formulations and exact algorithm for the multitrip cumulative capacitated single-vehicle routing problem[J].European Journal of Operational Research，2016，249（1）：93-104.
[11] LEI L，PINEDO M，QI L，et al.Personnel scheduling and supplies provisioning in emergency relief operations[J].Annals of Operations Research，2015，235（1）：487-515.
[12] WANG H，XU R，XIONG Z，et al.Research on the optimized dispatch and transportation scheme for emergency logistics[J].Procedia Computer Science，2018，129：208-214.
[13] CHAKRABORTY P S，TIWARI A，SINHA P R.Adaptive and optimized emergency vehicle dispatching algorithm for intelligent traffic management system[J].Procedia Computer Science，2015，57：1384-1393.
[14] QI C，HU L.Optimization of vehicle routing problem for emergency cold chain logistics based on minimum loss[J].Physical Communication，2020，40（2）：101085.
[15] DORIGO M，GAMBARDELLA L M.Ant colony system：a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation，1997，1（1）：53-66.
[16] FENG J，GAI W，LI J Y，et al.Location selection of emergency supplies repositories for emergency logistics management：a variable weighted algorithm[J].Journal of Loss Prevention in the Process Industries，2020，63：104032.
[17] LAKSONO P，WULAN S R，SUPANGKAT S H，et al.AHP and dynamic shortest path algorithm to improve optimum ambulance dispatch in emergency medical response[C]//2017 International Conference on ICT for Smart Society（ICISS），2017：1-6.
[18] TLILI T，HARZI M，KRICHEN S.Swarm-based approach for solving the ambulance routing problem[J].Procedia Computer Science，2017，112：350-357.
[19] RENAUD J，BOCTOR F F，LAPORTE G.An improved petal heuristic for the vehicle routeing problem[J].Journal of the Operational Research Society，1996，47（2）：329-336.
[20] LI X，TAN Q.Particle swarm optimization algorithm for emergency resources dispatch scheduling[J].Recent Patents on Mechanical Engineering，2014，7（3）：237-240.
[21] GHOSH S，VARAKANTHAM P.Dispatch guided allocation optimization for effective emergency response[C]//Thirty-Second AAAI Conference on Artificial Intelligence，2018.
[22] ISSAM Z，AL-OMANI M，ALDHAFEERI K.A new approach based on the hybridization of simulated annealing algorithm and tabu search to solve the static ambulance routing problem[J].Procedia Computer Science，2019，159：1216-1228.
[23] RAMESH C，KAMALAKANNAN R，KARTHIK R，et al.A lot streaming based flow shop scheduling problem using simulated annealing algorithm[J].Materials Today：Proceedings，2020.
[24] 蔡延光，戚远航，蔡颢，等.物流运输调度问题的混沌烟花算法——基于多车型供应链[J].计算机工程与应用，2019，55（3）：238-244.
CAI Y G，QI Y H，CAI H，et al.Chaotic fireworks algorithm for multi-type vehicle routing problem in supply chain[J].Computer Engineering and Applications，2019，55（3）：238-244.
[25] ZARKESHZADEH M，ZARE H，HESHMATI Z，et al.A novel hybrid method for improving ambulance dispatching response time through a simulation study[J].Simulation Modelling Practice and Theory，2016，60：170-184.
[26] ZHOU R，WANG T，WANG Y.United programming model for dispatch of emergency rescue teams and road reconstruction under earthquake disaster[J].Journal of Southwest Jiaotong University，2017（2）：13.
[27] FAN Y，JIA P，GUO W，et al.Emergency dispatch optimization of engineering vehicles in disaster rescue activities[C]//2019 Chinese Control Conference（CCC），2019：2001-2005.
[28] LIU M，LIANG J.Dynamic optimization model for allocating medical resources in epidemic controlling[J].Journal of Industrial Engineering and Management（JIEM），2013，6（1）：73-88.
[29] PIOVELLA N.Analytical solution of SEIR model describing the free spread of the COVID-19 pandemic[J].Chaos，Solitons & Fractals，2020，140：110243.
[30] SHEU J B.An emergency logistics distribution approach for quick response to urgent relief demand in disasters[J].Transportation Research Part E：Logistics and Transportation Review，2007，43（6）：687-709.
[31] TAN Y，ZHU Y.Fireworks algorithm for optimization[C]//International Conference in Swarm Intelligence.Berlin，Heidelberg：Springer，2010：355-364.
[32] YU C，KELLEY L C，TAN Y.Dynamic search fireworks algorithm with covariance mutation for solving the CEC 2015 learning based competition problems[C]//2015 IEEE Congress on Evolutionary Computation（CEC），2015：1106-1112.
[33] HE L，LI W，ZHANG Y，et al.A discrete multi-objective fireworks algorithm for flowshop scheduling with sequence-dependent setup times[J].Swarm and Evolutionary Computation，2019，51：100575.
[34] 徐力，刘云华，王启富.自适应遗传算法在机器人路径规划的应用[J].计算机工程与应用，2020，56（18）：36-41.
XU L，LIU Y H，WANG Q F.Application of adaptive genetic algorithm in robot path planning[J].Computer Engineering and Applications，2020，56（18）：36-41.