需求点服务请求无法预知的应急物资配送路径选择研究

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

摘要/Abstract

摘要：

针对不能提前获知需求点服务请求且有送达时间要求的应急物资配送路径选择问题，以总通行费用与总延时费用之和尽可能小为目标，建立在线模型，在比较配送车在当前所在节点对正在前往需求点和提出请求需求点产生配送费用大小的基础上，设计在线比较策略，讨论不同情形下比较策略的竞争性能，计算策略的竞争比，最后结合应急物资配送实例验证策略的执行效果。

关键词: 无法预知, 配送路径选择, 在线策略

Abstract:

The unexpected disaster refers to a disaster that is difficult to prevent and has sudden and highly uncertain characteristics. After the outbreak of unexpected disasters， there will be a shortage of materials. Efficient distribution of emergency materials is the key to ensuring people’s life safety， maintaining their living needs and reducing disaster losses. In the complex and dynamic environment after the disaster， the demand for emergency materials at each demand point is highly uncertain， and the emergency management department cannot predict the demand in advance.The route selection problem for emergency materials distribution is proposed in this paper. The service requests with service time requirements are considered to be sent from each demand point in turn， and the objective is to make the total travel cost add total delay cost as small as possible. An on-line route selection model with unpredictable service requests is established. A comparison strategy is designed based on the comparison between the cost from the current point of the distribution vehicle to the first-to-go demand point and the cost from the current point of the distribution vehicle to the demand point with new service request. The competitive performance of the comparison strategy is discussed in two different cases， and the competition ratio of the comparison strategy is proved.Finally， the implementation of the comparison strategy is validation by a practical case based on the real road network in Jianghan district of Wuhan city. The ratio of the total cost of the online strategy to the optimal cost of the offline problem is 1.9， which shows that the implementation of the strategy is good. A reliable research idea for route selection for emergency materials distribution with unpredictable service requests of demand points is provided. Future research can investigate how to design a better online strategy.

Key words: unpredictable, route selection for distribution, online strategy

中图分类号:

C931

苏兵,耿雪韵,姬浩, 等. 需求点服务请求无法预知的应急物资配送路径选择研究[J]. 中国管理科学, 2025, 33(4): 197-203.

Bing Su,Xueyun Geng,Hao Ji, et al. Research on Route Selection for Emergency Materials Distribution with Unpredictable Service Requests of Demand Points[J]. Chinese Journal of Management Science, 2025, 33(4): 197-203.

图/表 8

表1

比较策略竞争比"

情形1	情形2
$2 + m 2 m 1$	$2 + m 2 m 1 + (1 + m 2 m 1) ⋅ α β$

表1

图1

图2

表2

表3

表4

图3

表5

参考文献 13

1	张杏雯，倪静.公平约束下的应急物资配送模型及算法［J］.统计与决策，2020，36（7）：179-182.
	Zhang X W， Ni J. Model and algorithm of emergency materials distribution under fair constraints［J］. Statistics & Decision， 2020， 36（7）： 179-182.
2	周桂姣，卢山，雷全胜.应急情况下需求和旅行时间不确定的车辆路径问题研究［J］.物流工程与管理，2016，38（10）：55-57.
	Zhou G J， Lu S， Lei Q S. Study on vehicle routing problem with uncertain demand and travel time in emergency［J］. Logistics Engineering and Management， 2016， 38（10）： 55-57.
3	堵丁柱.k车服务问题与竞争算法［J］.数学的实践与认识，1991（4）：36-40.
	Du D Z. K-train service problem and competition algorithm［J］. Mathematics in Practice and Theory， 1991（4）： 36-40.
4	Borodin A， El-Yaniv R. Onine computation and competitive analysis［M］. Cambridge： Cambridge University Press， 1998.
5	苏兵，林刚，程新峰，等.突发性片堵塞下两车信息共享的加拿大旅行者问题［J］.中国管理科学， 2018，26（7）：151-158.
	Su B， Lin G， Cheng X F， et al. Canadian travelers’problem of information sharing between two vehicles under sudden film jam［J］. Chinese Journal of Management Science， 2018， 26（7）： 151-158.
6	Wen X G， Xu Y F， Zhang H L. Online traveling salesman problem with deadlines and service flexibility［J］. Journal of Combinatorial Optimization， 2015， 30（3）： 545-562.
7	代文强，姜玉琦，郭贤.共享平台下实时任务分配的占线策略［J］.系统工程理论与实践，2021， 41（11）：2929-2936.
	Dai W Q， Jiang Y Q， Guo X. The busy strategy of real-time task allocation under shared platform［J］. Systems Engineering-Theory & Practice， 2021， 41（11）： 2929-2936.
8	衣方磊，徐寅峰，辛春林.局内动态配送车调度管理及其竞争策略［J］.管理科学学报，2007（4）：1-8.
	Yi F L， Xu Y F， Xin C L. Dynamic distribution vehicle scheduling management and its competitive strategy［J］. Journal of Management Sciences in China， 2007（4）： 1-8.
9	衣方磊，徐寅峰，辛春林.限制信息条件下基于时间窗的占线装-卸货问题及其竞争分析［J］.系统工程，2006（6）：35-39.
	Yi F L， Xu Y F， Xin C L. Online loading unloading problem based on time window under restricted information and its competition analysis［J］. Systems Engineering， 2006（6）： 35-39.
10	马军平，徐寅峰，陈聪，等.具有服务时长的在线TSP问题［J］.系统工程理论与实践，2015， 35（11）：2832-2839.
	Ma J P， Xu Y F， Chen C， et al. Online TSP problem with service duration［J］. Systems Engineering-Theory & practice， 2015， 35（11）： 2832-2839.
11	张玉州，张子为.考虑动态客户需求的物资配送问题求解方法［J］.西安交通大学学报，2020， 54（8）：124-131.
	Zhang Y Z， Zhang Z W. Material distribution problem with dynamic customer demand［J］. Journal of Xi’an Jiaotong University， 2020， 54（8）： 124-131.
12	余高辉.基于复杂网络的非常规灾害应急物流占线路径问题研究［D］.广州：华南理工大学，2012.
	Yu G H. Research on busy route problem of emergency logistics for unconventional disasters based on complex network［D］. Guangzhou：South China University of Technology， 2012.
13	Wu T Y， He L， Yu H Y. Online traveling salesman problem with time cost and non-zealous server［J］. Journal of Combinatorial Optimization，2020（5）：1-24.

	v₀	v₁	v₂	v₃	v₄	v₅	v₆	v₇	v₈	v₉	v₁₀	v₁₁	v₁₂	v₁₃	v₁₄	v₁₅
v₀	-	-	2.1	-	-	-	-	-	0.8	-	-	-	-	-	-	1.4
v₁		-	-	-	-	-	-	-	-	0.8	-	3.3	-	-	-	-
v₂			-	-	-	-	4.5	1.9	-	-	-	-	-	4.9	-	-
v₃				-	6.1	-	-	5.0	-	-	4.4	8.4	-	-	-	-
v₄					-	-	-	-	1.9	-	-	-	2.0	-	-	1.9
v₅						-	-	2.7	-	-	-	-	-	-	1.2	-
v₆							-	-	-	1.1	-	4.0	2.9	-	-	3.0
v₇								-	2.1	-	2.7	-	-	-	-	-
v₈									-	-	-	-	-	-	-	-
v₉										-	-	-	-	-	-	-
v₁₀											-	-	-	-	2.2	-
v₁₁												-	2.6	-	-	-
v₁₂													-	-	-	-
v₁₃														-	2.0	-
v₁₄															-	-
v₁₅																-

需求点名称	需求点符号	要求送达时间	提出服务请求时车辆所在位置
江汉区应急管理中心	v₀	-	-
武汉广爱医院	v₁	6	v₀
武汉麻塘中医院	v₂	9	v₆
华中科技大学附属同济医院	v₃	19	v₉
协和医院	v₄	4	v₇
新华街卫生服务中心	v₅	15	v₄
武汉市中心医院（后湖院区）	v₆	20	v₇
中医院台北分院	v₇	1	v₂
湖北省新华医院	v₈	3	v₂
汉兴街卫生服务中心	v₉	5	v₀
华中科技大学附属协和医院	v₁₀	11	v₉
武汉华茂医院	v₁₁	16	v₂
武汉市优抚医院	v₁₂	2	v₄
武汉市中心医院	v₁₃	17	v₁₂
武汉亚洲心脏病医院	v₁₄	6	v₂
武汉市红十字会医院	v₁₅	10	v₁₃

需求点	配送路径	送达时间	延时费用
v₁	v₀-v₁₅-v₆-v₉-v₁	6.3	24
v₂	v₆-v₉-v₁-v₉-v₆-v₂	8.3	-
v₃	v₉-v₆-v₂-v₇-v₈-v₄-v₃	17.6	-
v₄	v₇-v₈-v₄	4.0	-
v₅	v₄-v₃-v₇-v₅	13.8	-
v₆	v₇-v₅-v₇-v₂-v₇-v₂-v₀-v₈-v₀-v₁₅-v₆	19.2	-
v₇	v₂-v₇	1.9	72
v₈	v₂-v₀-v₈	2.9	-
v₉	v₀-v₁₅-v₆-v₉	5.5	40
v₁₀	v₉-v₆-v₂-v₇-v₁₀	10.2	-
v₁₁	v₂-v₇-v₁₀-v₇-v₈-v₄-v₁₂-v₁₁	15.9	-
v₁₂	v₄-v₁₂	2.0	-
v₁₃	v₁₂-v₁₁-v₆-v₂-v₁₃	16.0	-
v₁₄	v₂-v₁₃-v₁₄	6.9	72
v₁₅	v₁₃-v₁₄-v₅-v₇-v₈-v₀-v₁₅	10.2	16

对比项目	行驶费用	延时费用	总费用
在线策略	9510	224	9734
离线最优	3540	1560	5100
			9734/5100=1.9

[1]	曹端阳, 张旭梅, 但斌. 考虑订单可拆分的第三方共享制造平台产能匹配策略[J]. 中国管理科学, 2025, 33(10): 225-235.
[2]	冯宇, 党耀国, 王俊杰, 杨章程. 基于2-可加Choquet积分的混合信息灰关联决策方法及其应用[J]. 中国管理科学, 2025, 33(9): 189-200.
[3]	戢守峰, 刘红玉, 王丽洁, 戢媛媛. PI环境下考虑保鲜努力的冷链产品生产-库存-运输联合优化模型与求解[J]. 中国管理科学, 2025, 33(8): 166-176.
[4]	毛照昉, 袁锐莹, 张清然. 考虑捆绑销售的在线课程免费试听策略研究[J]. 中国管理科学, 2025, 33(8): 238-249.
[5]	陈晓红, 杨志慧, 胡东滨. 数字化全渠道客户行为：研究热点与知识框架[J]. 中国管理科学, 2025, 33(7): 1-10.
[6]	刘嘉, 袁欣, 阮伟乔, 白晋宇. 呼吸道传染病疫情下地铁站行人感染风险控制[J]. 中国管理科学, 2025, 33(5): 236-246.
[7]	丁黎黎, 赵忠超, 张凯旋. 感知价值对个人碳账户绿色信贷发展的作用机制研究[J]. 中国管理科学, 2025, 33(5): 344-355.
[8]	谷炜, 刘亚金, Lu Feng Susan, 闫相斌. 人工智能驱动管理决策：应用、感知与偏见[J]. 中国管理科学, 2025, 33(5): 99-112.
[9]	卞亦文, 程文超. 平台供应链线下渠道策略与运营模式选择研究[J]. 中国管理科学, 2025, 33(4): 165-174.
[10]	巩在武, 阳佳琦. 考虑灾民心理的多周期应急物资调度不确定规划建模研究[J]. 中国管理科学, 2025, 33(3): 209-222.
[11]	柴一栋, 刘昊鑫, 姜元春, 刘业政. 基于重要性最大化与社区划分的图神经网络推荐系统对抗攻击方法[J]. 中国管理科学, 2025, 33(2): 95-104.
[12]	杨善林, 李霄剑, 莫杭杰, 张强, 唐孝安. 科技战略供应链的基本特征与关键科学问题[J]. 中国管理科学, 2025, 33(1): 1-13.
[13]	陈晓红, 许冠英, 徐雪松, 易国栋, 唐加乐, 刘天朔. 新质生产力视域下管理科学变革：内涵特征、现实挑战与发展路径[J]. 中国管理科学, 2025, 33(1): 14-21.
[14]	胡勋锋, 单而芳, 李登峰. 联盟结构和交流网络限制下合作博弈的Shapley值研究进展[J]. 中国管理科学, 2025, 33(1): 140-152.
[15]	朱庆华, 陈宇潇, 陈国玉. 循环供应链管理研究发展与展望[J]. 中国管理科学, 2025, 33(1): 221-231.