基于多无人机的血液紧急配送问题研究

doi:10.16381/j.cnki.issn1003-207x.2023.1557

Abstract

Abstract:

Blood emergency delivery plays a crucial role in the treatment of wounded patients. The application of drones provides new opportunities for improving blood emergency delivery， yet many challenges， including blood perishability， poor drone range， and blood-to-injury correspondence， encountered in using drones for blood emergency delivery have been overlooked. A novel blood delivery problem is considered， distinct from current relevant research， which effectively avoids the impact of post-disaster road damage on blood emergency delivery and alleviates drone range anxiety while ensuring fairness in blood emergency delivery and the quality of blood transfusions for patients. During the scheduling period， there may be multiple wounded patients in need of blood transfusions in hospitals. Drones carrying blood products depart from temporary blood centers to hospitals for blood emergency delivery. Drones are required to deliver blood to hospitals within agreed-upon times as much as possible. Meanwhile， drones can choose to recharge at hospitals to extend their flight range. After completing all blood delivery tasks， drones must return to the blood center. The cumulative duration is minimized as the objective， considering the perishability of blood， the correspondence between blood and patients， the fairness of blood delivery， and the time cost of drone charging. A mixed-integer programming model is established， and effective inequalities are proposed based on the problem characteristics. Furthermore， based on the problem characteristics and through an adaptive mechanism combining Variable Neighborhood Search （VNS） and Adaptive Neighborhood Search （ANS）， an improved Adaptive Variable Neighborhood Simulated Annealing algorithm （I-AVNS-SA） is designed to solve the model. Finally， extensive computational experiments are conducted using datasets adapted from the Solomon VRPTW benchmark and the dataset of the Turkish earthquake. Experimental results show that， for small-scale instances， the I-AVNS-SA algorithm is comparable to solving the MIP model optimally， with significantly reduced computation time. In large-scale instances， the algorithm outperforms SA， LS， and GA algorithms recently used to solve related problems in terms of objective function value， CPU time， convergence， and stability. Additionally， through sensitivity analysis， scientific reference is provided for whether hospitals are equipped with drone charging facilities and the configuration of drone quantities. In conclusion， the study of the UAV blood delivery problem is refined through a comprehensive consideration of the challenges and the design of efficient models and algorithms.

Key words: drones, emergency blood delivery, MIP, VNS, adaptive mechanisms

CLC Number:

F252

Zhongbao Zhou,Enming Chen,Ruiyang Li, et al. Research on Emergency Blood Delivery Problem Based on Multiple Drones[J]. Chinese Journal of Management Science, 2025, 33(12): 171-184.

Figures/Tables 12

参数	数值
无人机速度（ $v$ ）	1（单位距离/秒）
无人机最大载荷（ $Q$ ）	150（千克）
无人机航程（ $L$ ）	900（单位距离）
无人机充电速率（ $c l$ ）	3（单位距离/秒）
无人机最大延时成本（ $T E$ ）	150
公平偏好系数（ $δ$ ）	n/2

参数	数值
最大迭代次数	30
未改进最大迭代次数	5
GVNS和ANS权重列表（ $W 0$ ）	0.5, 0.5
邻域权重列表（ $W 1$ ）	0.5, 0.5, 0.5, 0.5, 0.5
温度（ $t p 0$ ）	1000（℃）
温度（ $t p 0$ ）	300（℃）
冷却速率（ $r$ ）	3
邻域产生的解的数量	50

References 31

[1]	全球灾害数据平台.全球尺度灾害特征分析［EB/OL］.（2022-12-31）［2023-03-28］..
	Global Disaster Data Platform.Global-scale disaster characteristic analysis ［EB/OL］.（2022-12-31）［2023-03-28］..
[2]	Asadpour M， Olsen T L， Boyer O. An updated review on blood supply chain quantitative models： A disaster perspective［J］. Transportation Research Part E： Logistics and Transportation Review， 2022， 158： 102583.
[3]	Şahin G， Süral H， Meral S. Locational analysis for regionalization of Turkish Red Crescent blood services［J］. Computers & Operations Research， 2007， 34（3）： 692-704.
[4]	王恪铭，马祖军. 应急血液多阶段调剂优化［J］. 系统工程理论与实践， 2014， 34（7）： 1687-1696.
	Wang K M， Ma Z J. Optimization of multi-stage emergency blood transferring［J］. Systems Engineering-Theory & Practice， 2014， 34（7）： 1687-1696.
[5]	马祖军，周愉峰. 国家血液战略储备库选址—库存问题［J］. 管理科学学报， 2018， 21（3）： 54-68.
	Ma Z J， Zhou Y F. Location-inventory problem for national strategic blood reserves［J］. Journal of Management Sciences in China， 2018， 21（3）： 54-68.
[6]	周愉峰，李志，刘思峰. 基于随机p-鲁棒优化的国家血液战略储备库选址-库存模型［J］. 中国管理科学， 2018， 26（10）： 52-63.
	Zhou Y F， Li Z， Liu S F. Location-inventory model of national blood strategic reserves based on p-robustStochastic optimization method［J］. Chinese Journal of Management Science， 2018， 26（10）： 52-63.
[7]	Zahiri B， Pishvaee M S. Blood supply chain network design considering blood group compatibility under uncertainty［J］. International Journal of Production Research， 2017， 55（7）： 2013-2033.
[8]	Salehi F， Mahootchi M， Husseini S M M. Developing a robust stochastic model for designing a blood supply chain network in a crisis： A possible earthquake in Tehran［J］. Annals of Operations Research， 2019， 283（1）： 679-703.
[9]	Rezaei Kallaj M， Hasannia Kolaee M， Mirzapour Al-e-hashem S M J. Integrating bloodmobiles and drones in a post-disaster blood collection problem considering blood groups［J］. Annals of Operations Research， 2023， 321（1）： 783-811.
[10]	Bravo R Z B， Leiras A， Cyrino Oliveira F L. The use of UAVs in humanitarian relief： An application of POMDP-based methodology for finding victims［J］. Production and Operations Management， 2019， 28（2）： 421-440.
[11]	Amukele T. Using drones to deliver blood products in Rwanda［J］. The Lancet Global Health， 2022， 10（4）： e463-e464.
[12]	Ghelichi Z， Gentili M， Mirchandani P B. Drone logistics for uncertain demand of disaster-impacted populations［J］. Transportation Research Part C： Emerging Technologies， 2022， 141： 103735.
[13]	Dukkanci O， Koberstein A， Kara B Y. Drones for relief logistics under uncertainty after an earthquake［J］. European Journal of Operational Research， 2023， 310（1）： 117-132.
[14]	Ozkan O. Multi-objective optimization of transporting blood products by routing UAVs： The case of Istanbul［J］. International Transactions in Operational Research， 2023， 30（1）： 302-327.
[15]	Zailani M A H， Raja Sabudin R Z A， Ismail A， et al. Influence of drone carriage material on maintenance of storage temperature and quality of blood samples during transportation in an equatorial climate［J］. PLoS One， 2022， 17（9）： e0269866.
[16]	Cheraghi S， Hosseini-Motlagh S M. Responsive and reliable injured-oriented blood supply chain for disaster relief： A real case study［J］. Annals of Operations Research， 2020， 291（1）： 129-167.
[17]	Huang C， Ming Z， Huang H. Drone stations-aided beyond-battery-lifetime flight planning for parcel delivery［J］. IEEE Transactions on Automation Science and Engineering， 2023， 20（4）： 2294-2304.
[18]	Meng S， Guo X， Li D， et al. The multi-visit drone routing problem for pickup and delivery services［J］. Transportation Research Part E： Logistics and Transportation Review， 2023， 169： 102990.
[19]	Wang J， Song G， Liang Z， et al. Unrelated parallel machine scheduling with multiple time windows： An application to earth observation satellite scheduling［J］. Computers & Operations Research， 2023， 149： 106010.
[20]	Paradiso R， Roberti R， Laganá D， et al. An exact solution framework for multitrip vehicle-routing problems with time windows［J］. Operations Research， 2020， 68（1）： 180-198.
[21]	Cai J， Zhu Q， Lin Q. Variable neighborhood search for a new practical dynamic pickup and delivery problem［J］. Swarm and Evolutionary Computation， 2022， 75： 101182.
[22]	范厚明，刘鹏程，吴嘉鑫，等. 集货需求随机的同时配集货VRP及混合变邻域搜索算法［J］. 系统工程理论与实践， 2019， 39（10）： 2646-2659.
	Fan H M， Liu P C， Wu J X， et al. Hybrid genetic algorithm with variable neighborhood descent for the vehicle routing problem with simultaneous stochastic pickup and deterministic delivery［J］. Systems Engineering-Theory & Practice， 2019， 39（10）： 2646-2659.
[23]	孙卓，李一鸣. 考虑多仓库的共享单车重新配置问题研究［J］. 运筹与管理， 2021， 30（1）： 121-129.
	Sun Z， Li Y M. Solving a static bike repositioning problem with multiple depots［J］. Operations Research and Management Science， 2021， 30（1）： 121-129.
[24]	高佳静，镇璐. 多卡车多机器人联合配送系统路径问题研究［J］. 中国管理科学， 2023， 31（3）： 48-57.
	Gao J J， Zhen L. Research on routing problem for joint delivery system based on multiple trucks and robots［J］. Chinese Journal of Management Science， 2023， 31（3）： 48-57.
[25]	张建同，丁烨. 变邻域模拟退火算法求解速度时变的VRPTW问题［J］. 运筹与管理， 2019， 28（11）： 77-84.
	Zhang J T， Ding Y. Simulated annealing with variable neighborhood for time-dependent vehicle routing problem with time window［J］. Operations Research and Management Science， 2019， 28（11）： 77-84.
[26]	胡雪君，赵雁，单汩源，等. 基于自适应大邻域搜索的鲁棒多项目调度方法［J］. 中国管理科学， 2022， 30（9）： 217-231.
	Hu X J， Zhao Y， Shan M Y，et al. An adaptive large neighborhood search metaheuristic for robust multi-project scheduling［J］. Chinese Journal of Management Science， 2022， 30（9）： 217-231.
[27]	Xu B， Zhao K， Luo Q， et al. A GV-drone arc routing approach for urban traffic patrol by coordinating a ground vehicle and multiple drones［J］. Swarm and Evolutionary Computation， 2023， 77： 101246.
[28]	Lipowski A， Lipowska D. Roulette-wheel selection via stochastic acceptance［J］. Physica A： Statistical Mechanics and Its Applications， 2012， 391（6）： 2193-2196.
[29]	Solomon M M. Algorithms for the vehicle routing and scheduling problems with time window constraints［J］. Operations Research， 1987， 35（2）： 254-265.
[30]	Chin V， Cope S， Yeh C H， et al. Massive hemorrhage protocol survey： Marked variability and absent in one-third of hospitals in Ontario， Canada［J］. Injury， 2019， 50（1）： 46-53.
[31]	冷媚.强震已致土叙逾4000人丧生多国派遣搜救力量协助救援［EB/OL］.（2023-02-07）［2023-05-10］..
	Leng M. A powerful earthquake has killed more than 4 000 people in Turkey and Syria， and many countries have sent search and rescue forces to assist in the rescue ［EB/OL］.（2023-02-07）［2023-05-10］..

规模	序号	MIP				A-MIP			I-AVNS-SA		N_d
规模	序号	F	CPU (秒)	ΔF₁\|ΔF₂（%）	ΔC₁（%）	F	CPU (秒)	ΔC₂（%）	F	CPU (秒)
IN-4	c	418.1	1.01	0.0	32.9	418.1	0.71	-6.6	418.1	0.76	1
	r	822.1	1.01	0.0	-49.8	822.1	0.71	-64.7	822.1	2.01	1
	rc	818.8	1.01	0.0	-54.3	818.8	0.71	-67.9	818.8	2.21	1
IN-5	c	424.1	1.32	0.0	-34.3	424.1	1.05	-47.8	424.1	2.01	1
	r	930.2	1.28	0.0	-42.1	930.2	1.02	-53.8	930.2	2.21	1
	rc	826.6	1.33	0.0	-38.7	826.6	1.05	-51.6	826.6	2.17	1
IN-6	c	434.2	2.45	0.0	-6.8	434.2	2.05	-22.1	434.2	2.63	1
	r	1194.8	2.41	0.0	-7.7	1194.8	2.03	-22.2	1194.8	2.61	1
	rc	842.7	2.45	0.0	-34.7	842.7	2.03	-45.9	842.7	3.75	1
IN-7	c	777.8	45.78	0.0	1186.0	777.8	23.12	549.4	777.8	3.56	2
	r	1348.1	36.52	0.0	654.5	1348.1	18.39	280.0	1348.1	4.84	2
	rc	1508.7	58.68	0.0	1636.1	1508.7	19.99	491.4	1508.7	3.38	2
IN-8	c	797.7	2799.72	0.0	63099.1	797.7	998.2	22432.7	797.7	4.43	2
	r	1560.2	717.04	0.0	17054.1	1560.2	563.7	13385.6	1560.2	4.18	2
	rc	1559.2	>3600	0.0	——	1559.3	985.4	22244.7	1559.3	4.41	2
IN-9	c	867.7	>3600	0.0	——	867.7	>3600	——	867.7	5.26	2
	r	1749.4	>3600	0.0	——	1749.4	1195.9	20273.1	1749.4	5.87	2
	rc	1792.5	>3600	0.0	——	1792.5	>3600	——	1792.5	6.11	2

规模	F	MIP			A-MIP			I-AVNS-SA		N_ d
规模	F	CPU (秒)	ΔF₁\|ΔF₂（%）	ΔC₁（%）	F	CPU (秒)	ΔC₁（%）	F	CPU (秒)
IN-6	1896.8	2.92	0.0	0.3	1896.8	1.71	-41.2	1896.8	2.91	2
IN-7	1934.3	14.35	0.0	240.9	1934.3	7.69	82.7	1934.3	4.21	2
IN-8	1956.6	812.13	0.0	10285.3	1956.6	435.35	5467.1	1956.6	7.82	3
IN-9	2236.8	>3600	0.0	——	2236.8	>3600	——	2236.8	8.51	3

规模	序号	I-AVNS-SA		SA		LS		GA		N_d
规模	序号	F	CPU (秒)	ΔF（%）	ΔC（%）	ΔF（%）	ΔC（%）	ΔF（%）	ΔC（%）	N_d
IN-30	c	3278.5	25.68	27.82	61.34	42.08	62.44	16.89	68.27	6
	r	5439.7	38.09	27.44	61.83	38.33	68.82	20.88	68.14	6
	rc	5689.6	42.54	27.34	56.43	39.49	60.55	16.23	67.86	6
IN-40	c	4345.2	59.79	26.72	56.98	40.54	68.33	20.80	70.08	6
	r	7067.8	48.85	27.12	60.09	36.56	68.73	17.55	60.04	6
	rc	7511.9	48.61	27.24	60.53	42.06	61.24	20.20	61.91	6
IN-50	c	6032.1	69.15	23.54	60.65	40.49	62.54	19.10	60.39	8
	r	10123.1	68.33	24.44	60.06	39.88	62.45	15.63	67.60	8
	rc	9939.8	65.43	27.72	60.09	38.63	68.00	17.39	66.64	8
IN-60	c	7552.8	64.66	28.63	58.44	37.74	61.65	23.50	75.35	10
	r	13329.9	109.31	24.13	65.44	36.88	12.63	23.28	77.20	10
	rc	14091.4	89.77	23.75	67.73	41.33	24.02	17.27	79.02	10
IN-70	c	10178.1	178.99	31.62	63.86	43.55	22.57	25.24	75.43	12
	r	15945.5	203.64	30.95	66.58	38.32	16.67	24.59	78.04	12
	rc	18666.8	125.87	29.94	58.82	44.24	63.50	20.96	79.24	12
IN-80	c	11146.7	164.89	32.13	67.44	42.58	32.47	26.14	74.97	14
	r	17812.9	198.05	30.65	57.88	40.08	64.50	24.92	79.77	14
	rc	19096.9	156.72	32.53	64.29	41.56	45.61	25.18	78.19	14
IN-90	c	15079.2	162.90	29.83	61.78	44.72	67.94	23.30	76.26	16
	r	18899.5	199.79	27.52	68.39	44.24	53.97	21.82	79.49	16
	rc	24389.9	189.64	32.84	67.35	42.08	43.01	23.21	75.57	16
IN-100	c	17945.2	289.91	30.03	65.64	39.95	49.65	26.61	75.64	18
	r	20078.1	267.17	28.72	57.62	44.00	57.73	26.14	75.10	18
	rc	27679.4	294.69	31.63	55.69	44.17	41.90	15.49	79.04	18

规模	I-AVNS-SA		SA		LS		GA		N_d
规模	F	CPU (秒)	ΔF（%）	ΔC（%）	ΔF（%）	ΔC（%）	ΔF（%）	ΔC（%）	N_d
IN-10	2281.5	4.42	21.60	72.98	27.26	41.97	24.92	76.11	3
IN-15	3943.2	16.41	21.41	64.09	29.26	64.90	26.77	81.30	4
IN-20	5011.8	21.85	23.81	73.90	27.66	36.57	23.49	70.73	5
IN-30	8551.4	34.19	21.18	72.08	26.21	53.38	26.61	80.96	7
IN-35	9533.1	39.49	21.97	74.92	36.55	68.47	16.17	81.72	8
IN-40	10125.9	54.67	28.98	71.92	38.51	60.68	29.26	72.54	9

Research on Emergency Blood Delivery Problem Based on Multiple Drones

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 31

Related Articles 5

Metrics

Comments

Recommended 0

[1]	Keyi Zhang, Yong Shi, Haixiang Guo, Yongzheng Sun. Optimal Decision-Making for Dispatching Emergency Supplies for Natural Disasters in Mountainous Areas Based on Truck-Drone Collaboration [J]. Chinese Journal of Management Science, 2025, 33(2): 150-160.
[2]	CHENG Xing-qun, JIN Chun, YAO Qing-guo, WANG Cong. Research on Robust Optimization for Route Selection Problem in Multimodal Transportation under the Cap and Trade Policy [J]. Chinese Journal of Management Science, 2021, 29(6): 82-90.
[3]	ZHANG Li, DENG Li-ying, ZHOU Yong. Contrarian Effect of Semi-Parametric Alpha Strategy [J]. Chinese Journal of Management Science, 2016, 24(12): 30-38.
[4]	LAN Bo-xiong, WU Li-zhi. Optimization Model for Line Planning in Rail Passenger Transport Network [J]. Chinese Journal of Management Science, 2010, 18(6): 51-58.
[5]	XU Bing, ZHANG Shang-feng. China’s Nonlinear Philips Curve in Economic Transformation [J]. Chinese Journal of Management Science, 2008, 16(5): 37-41.