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

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

摘要/Abstract

摘要：

本文提出一个基于多无人机的血液紧急配送问题（emergency blood delivery problem with drones， EBDP-D），与当前相关的研究不同，该问题可以有效避免灾后道路受损对血液紧急配送的影响，同时可以缓解无人机里程焦虑以及保障血液紧急配送的公平性和具有不同输血需求的伤员所用血液的质量。本文以累计时长最小化为目标，考虑血液的易腐性、血液与伤员的对应关系、血液配送的公平性以及无人机充电带来的时间成本，建立了混合整数规划模型，并根据问题特性提出了相应的有效不等式。此外，本文根据问题特性，通过自适应机制结合变邻域搜索（VNS）和自适应邻域搜索（ANS）设计了一种改进的自适应变邻域模拟退火算法（I-AVNS-SA）求解模型。最后，利用以Solomon VRPTW为基准所改编的数据集、土耳其地震的数据集验证了模型和算法的有效性，并通过敏感性分析为医院是否配备无人机充电设施和无人机数量配置提供了科学的参考依据。

关键词: 无人机, 血液紧急配送, 混合整数规划, 变邻域搜索算法, 自适应机制

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

中图分类号:

F252

周忠宝,陈恩铭,李瑞阳, 等. 基于多无人机的血液紧急配送问题研究[J]. 中国管理科学, 2025, 33(12): 171-184.

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.

图/表 12

图1

图2

表1

模型相关参数设定"

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

表1

表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

表2

表3

表4

表5

表6

图3

图4

图5

图6

参考文献 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