网刊加载中。。。

使用Chrome浏览器效果最佳,继续浏览,你可能不会看到最佳的展示效果,

确定继续浏览么?

复制成功,请在其他浏览器进行阅读

应急物流优先的交通分配模型及算法  PDF

  • 丁蕾 1
  • 杭虹利 2
1. 上海交通大学 医学院,上海 200025; 2. 上海外国语大学 国际工商管理学院,上海 200083

中图分类号: U116

最近更新:2022-05-19

DOI:10.11908/j.issn.0253-374x.21605

  • 全文
  • 图表
  • 参考文献
  • 作者
  • 出版信息
EN
目录contents

摘要

提出了一种应急物流车辆优先通行的交通分配模型,并给出对应的求解方法。在交通网络上,应急物流车辆的路径选择服从Cournot‒Nash(CN)原则,具有优先通行权,同时构成一个应急物资运输总时间最小化的共同体;其他社会车辆充分配合应急物流车辆的优先权,在满足应急物流车辆优先通行的前提下,路径选择服从Wardrop用户均衡(UE)原则,实现个体通行成本最小化。所提出的UE‒CN混合交通分配模型解可能不唯一,因此设计了算法。最后,通过简单的算例验证了模型和算法的合理性。

新冠肺炎疫情是一次重大的全球公共卫生事件。这次疫情是对我国突发公共卫生事件应急能力的一次大考,也是对全社会供需关系的一次严峻考验。回顾疫情防控过程,发现多数问题最终都归结为供需矛盾问题,尤其是紧急医疗救援的物流系统无法满足快速迅捷的需求,应急物流系统的无序和缓慢一度阻碍了疫情防控的进展,成为制约疫情攻坚战的瓶

1

应急物流体系是国家应急管理体系的重要组成部分,在运送防疫物资、保障生活需要、维持经济运行方面发挥着积极作

2。此次新冠肺炎疫情的暴发,暴露出我国在应急物流体系中存在的问题,包括应急物资的储备不足、生产滞后,物流运行不畅、调度难度大,应急物资分发、配送效率低,疫区末端快递收派难,航空物流、医药物流、冷链物流基础薄弱。疫情下传统物流系统暴露出明显的脆弱性,很容易受到破坏。每一次天灾人祸都是对物流保障体系的一次考验,任何一个物流环节的断裂和要素的缺失,都会造成整条供应链的停摆。

国外对应急物流的研究起步较早,在20世纪70年代已运用运筹与管理方法对自然灾害的应急管理进行了初步研

3。Dasaklis4综述了应急供应链对流行病爆发控制方面的研究。Ekici5与美国红十字会合作,采用启发式方法研究了潜在的流感大流行期间的食品分配计划。Sakuraba6基于地震后道路应急修复对救援物资分发的重要性,研究了震后道路网络可达性问题和工作部队调度问题。Dasaklis7研究了天花爆发控制的应急供应链管理,评估了实施区域大规模疫苗接种的医疗物资需求。Balcik8提出了采用有效的禁忌搜索启发式方法解决路线评估问题。

虽然国内在应急物流领域起步较晚,但是已取得了一些研究成果。He

9基于修正的SEIR(susceptible,exposed,infected,recovered)传染病模型建立了医疗物资需求预测模型和救济分配线性规划模型。Liu10依据药物需求预测,建立了包含医院、配送中心以及制药厂在内的医疗资源规划系统。Huang11针对某些突发事件无历史数据的特点,基于不确定性理论建立了应急物流配送路径模型。刘明12基于传染病动力学模型以及应急选址分配重新定义了应急服务水平参数,并建立了基于服务水平的疫情应急物流网络优化模型。赵建有13在考虑医疗物资需求迫切度重要性的基础上,构建了含车辆运行费用、延误惩罚费用、无延误补贴费用的配送总费用,并建立了城市应急医疗物资配送路径优化模型。

运输作为应急物流系统中的基础组成部分,直接影响着系统的高效与通畅。突发事件下难免会出现应急物流车辆与一般社会车辆共用交通网络的情况,目前相关问题还没有得到广泛研究。因此,提出了一种应急物流车辆优先通行的交通分配模型。在交通网络中,应急物流车辆具有优先通行权,同时构成一个应急物资运输总体时间最小化的共同体。其他交通参与者充分配合应急物流车辆的优先权,在满足应急物流车辆优先通行的前提下实现个体通行成本最小化。

1 应急物流车辆优先的交通分配模型

假设交通网络中存在2类车辆,即一般社会车辆和应急物流车辆。一般社会车辆总是试图在现有流量分布的基础上寻找最短路径,这类车辆的路径选择服从Wardrop用户均衡(UE)原

14。除了一般社会车辆外,交通网络上还有一些以应急物流总体行驶时间最小化为目标的车辆,它们的路径选择服从Cournot‒Nash(CN)原15。因此,将车辆交通划分为2个不同群体,每个群体的用户路径选择行为要么服从UE原则要么服从CN原则。

应急物流和社会物流都包含多个O‒D(交通起止点)对,但为了标记方便,每个O‒D对都只由一个运输体控制。当同一物理O‒D对上具有几个博弈者时,就复制该O‒D对,将其作为一组O‒D对。这样,每个博弈者对该O‒D对的控制都可以清晰地表达出

16

U表示路网中的一般社会车辆群体,服从UE原则,即UE博弈者群体;用K表示路网中的应急物流车辆群体,服从CN原则,即CN博弈者群体。WU为用户服从UE原则的O‒D对集合,WK为用户服从CN原则的O‒D对集合。令WWUWKvUa表示集合WU中通过路段aA的路径流量之和,vKa为集合WK中通过路段aA的路径流量之和,vavUa+vKa,vU=avUa,vK=avKa

假设在交通网络中每条路段上的出行时间和费用都只与该路段上的流量相关,同其他路段上的流量无关。令ta(va)表示任意路段aA上的平均费用,它是与路段流量可分离的、二阶可微的、严格递增的凸函数。

经上述符号定义,同时假设所有O‒D需求都是固定的,则UE博弈者的可行路段流量集合ΩU如下所示:

ΩU=vUvU1~3
vUa=wWUpPwfwpδwap,aA (1)
pPwfwp=dw,wWU (2)
fwp0,pPw,wWU (3)

CN博弈者的可行路段流量集合ΩK如下所示:

ΩK=vKvK4~6
vKa=wWKpPwfwpδwap,aA (4)
pPwfwp=dw,wWK (5)
fwp0,pPw,wWK (6)

式(1)~(6)中:Pww代表的O‒D对的所有路径的集合;fwpw代表的O‒D对的路径p上的流量;dww代表的O‒D对的交通需求;δwap为0‒1变量,若路段a属于w代表的O‒D对的路径p,则δwap=1,否则δwap=0vU为一般社会车辆的路径流量;vK为应急物流车辆的路径流量。式(1)~(6)分别表示物流需求、一般社会车辆出行需求和网络连接性条件。

目标函数为应急物流总时间最小化,则应急物流费用最小化模型(A)如下所示:

minvKΩK aAta(vUa+vKa)vKa (7)
vKa=wWKpPwfwpδwap,aA (8)
pPwfwp=dw,wWK (9)
fwp0,pPw,wWK (10)
vUa=wWUpPwfwpδwap,aA (11)
pPwfwp=dw,wWU (12)
fwp0,pPw,wWU (13)

若要求解模型(A),则可将模型(A)分解为2个子模型,轮流求解这2个子模型。第1个子模型是在给定一般社会车辆交通量前提下的应急物流系统最优模型(B),如下所示:

minvKΩK aAta(vUa+vKa)vKa (14)
vKa=wWKpPwfwpδwap,aA (15)
pPwfwp=dw,wWK (16)
fwp0,pPw,wWK (17)

该模型的一阶条件如下所示:

aA(vKata'(vUa+vKa)+ta(vUa+vKa))δwap=μw,
fwp>0,pPw,wWU (18)
aA(vKata'(vUa+vKa)+ta(vUa+vKa))δwapμw,
fwp=0,pPw,wWU (19)

式中:μw为O‒D对w间的实际出行时间。

第2个子模型为一般社会车辆交通量的分配模型(C),根据应急物流车辆优先的原则,目标函数为配合应急物流车辆的行程时间最小化,如下所示:

minvUΩU aAta(vUa+vKa)vKa (20)
vUa=wWUpPwfwpδwap,aA (21)
pPwfwp=dw,wWU (22)
fwp0,pPw,wWU (23)

该模型的一阶条件如下所示:

aA(vKata'(vUa+vKa))δwap=μw,
fwp>0,pPw,wWU (24)
aA(vKata'(vUa+vKa))δwapμw,
fwp=0,pPw,wWU (25)

式中: μw为O‒D对w间应急物流车辆的感知出行时间。

求解模型(C)只需求解一个交通分配问题,其中路段旅行时间函数更改为vKata'(vUa+vKa)。若一般社会车辆能够完全避开应急物流车辆使用的路段,即vKa>0的路段,则模型(C)的目标函数为零,可以做到一般社会车辆交通对应急物流车辆交通完全没有干扰。

需注意,在模型(B)、(C)中都使用了符号μw,因此需要根据连接O‒D对的用户类型(UE用户或者CN用户)区分方程中右边项实际表示的意义(实际出行时间或感知出行时间)。

已假设路段费用函数是凸函数且严格递增,因此最优化问题(B)具有唯一解。模型(C)是一个凸规划问题,但不是严格的凸规划,所以可能存在不同的解。同时满足最优化问题(B)和模型(C)的解称为UE‒CN混合均衡解。Harker

16用变分不等式来解决UE‒CN混合均衡问题。Bennett17则认为该混合均衡问题不能够用最优函数来表示。在均衡点,UE用户感知的费用为私人边际费用或实际费用ta(va),CN用户感知的费用为部分边际社会费用ta(va)+vKata'(va)

由于模型(C)可能存在路径流量不唯一的问题,因此求解该模型通常比较复杂。另外,在满足应急物流车辆优先通行的基础上,也应适当照顾一般社会车辆的通行费用。为此可将模型(A)修改为如下模型(D):

minvKΩK aAta(vUa+vKa)(vKa+pvUa) (26)
vKa=wWKpPwfwpδwap,aA (27)
pPwfwp=dw,wWK (28)
fwp0,pPwwWK (29)
vUa=wWUpPwfwpδwap,aA (30)
pPwfwp=dw,wWU (31)
fwp0,pPw,wWU (32)

模型(D)可分解为模型(E)和模型(F)。模型(E)如下所示:

minvKΩK aAta(vUa+vKa)(vKa+pvUa) (33)
vKa=wWKpPwfwpδwap,aA (34)
pPwfwp=dw,wWK (35)
fwp0,pPw,wWK (36)

模型(E)的一阶条件如下所示:

aA((vKa+pvUa)ta'(vUa+vKa)+ta(vUa+vKa))δwap=
μw,fwp>0,pPw,wWU (37)
aA((vKa+pvUa)ta'(vUa+vKa)+ta(vUa+vKa))δwap
μw,fwp=0,pPw,wWU (38)

模型(F)如下所示:

minvUΩU aA(ta(vUa+vKa)vKa+p0vUata(x+vKa)dx)) (39)
vUa=wWUpPwfwpδwap,aA (40)
pPwfwp=dw,wWU (41)
fwp0,pPw,wWU (42)

模型(F)的一阶条件如下所示:

aA(vKata'(vUa+vKa)+pta(vUa+vKa))δwap=μw,
fwp>0,pPw,wWU (43)
aA(vKata'(vUa+vKa)+pta(vUa+vKa))δwapμw,
fwp=0,pPw,wWU (44)

Harker

16已证明,在路段费用函数是线性且严格递增的条件下,模型(E)和模型(F)的解均是唯一的,混合均衡问题的解也是唯一的。

2 算例

在如图1所示的测试网络中,假设起点A和终点B之间由4条路线相连。路线的行程时间函数为

Ti(v)=ai+biv,i=1,2,3,4

式中:Ti为第i条路径的行程时间,是路径流量v的函数;aibi为与路径相关的参数,ai表示没有流量时的行程时间,bi表示路径的拥挤效应,即流量增加时行程时间上升的速度。aibi的值如表1所示。

图 1  测试网络

Fig. 1  Test network

表 1  路径行程时间函数的参数
Tab. 1  Parameters of path travel time function
路径编号aibi
1 0.12 326
2 0.08 303
3 0.09 209
4 0.06 103

假设如图1所示的网络中从起点A到终点B的物流需求为:500个单位的应急物流车辆流量(vK=500)和500个单位的一般社会车辆流量(vU=500)。利用模型(A)对流量进行分配,结果为:500个单位的应急物流车辆经过路径4,500个单位的一般社会车辆经过路径1、2或3,即vK4=500vU4=0vU1+vU2+vU3=500vK1=vK2=vK3=0。从计算结果看,模型(A)把应急物流车辆安排在路径4,并避免一般社会车辆使用该路段,可以保证应急物流车辆的优先通行。一般社会车辆共用路径1、2和3,避免了对应急物流车辆的干扰。然而,路径1、2和3的行程时间并不相等,所以在保证应急物流车辆优先的前提下模型(A)不能兼顾一般社会车辆的通行成本。

运用模型(D)对流量分配加以改进,模型参数e=0.001,计算结果如表2所示。结果表明,应急物流车辆全部选择最短路径4,一般社会车辆选择次短路径3。模型(D)不仅保证了应急物流车辆的优先,还使得一般社会车辆总行程时间最小。由此可见,相较于模型(A)而言,模型(D)可以在保证应急优先的情况下兼顾一般社会车辆的通行。

表 2  路径分配结果vK=500,vU=500
Tab. 2  Path assignment resultsvK=500,vU=500
路径编号应急物流车辆流量vKi一般社会车辆流量vUi
1 0 0
2 0 0
3 0 500
4 500 0

将应急物流车辆流量提高到1 000个单位,一般社会车辆流量不变仍为500个单位。运用模型D进行流量分配,结果如表3所示。应急物流车辆占用路径3和4,一般社会车辆占用路径1和2。

表 3  路径分配结果vK=1 000,vU=500
Tab. 3  Path assignment resultsvK=1 000,vU=500
路径编号应急物流车辆流量vKi一般社会车辆流量vUi
1 0 85
2 0 415
3 46.67 0
4 953.33 0

将应急物流车辆流量提高到3 000个单位,一般社会车辆流量仍然为500个单位。运用模型(D)进行流量分配,结果如表4所示。应急物流车辆占用路径2、3和4,一般社会车辆占用路径1。

表 4  路径分配结果vK=3 000,vU=500
Tab. 4  Path assignment resultsvK=3 000,vU=500
路径编号应急物流车辆流量vKi一般社会车辆流量vUi
1 0 500
2 251.72 0
3 745.98 0
4 2 002.30 0

改变模型参数e=1。将应急物流车辆流量设置为3 000个单位,一般社会车辆流量设置为500个单位。运用模型(D)进行流量分配,结果如表5所示。应急物流车辆占用路径1、3和4,一般社会车辆占用路径2。可见,采用过大的模型参数e会导致错误的计算结果。

表 5  路径分配结果vK=3 000,vU=500,e=1
Tab. 5  Path assignment resultsvK=3 000,vU=500,e=1
路径编号应急物流车辆流量vKi一般社会车辆流量vUi
1 113.46 0
2 0 500
3 801.28 0
4 2 085.26 0

3 结语

提出一种应急物流车辆优先通行的交通分配模型,并给出对应的求解方法。在交通网络上,应急物流车辆具有优先通行权,同时构成一个应急物资运输总时间最小化的共同体。其他交通充分配合应急物流车辆的优先权,在满足应急物流车辆优先通行的前提下实现个体通行成本最小化。因此,提出了混合交通分配模型,并对解的存在性和唯一性进行了说明。为解决解的唯一性问题,以及在应急物流车辆优先的前提下最大程度满足一般社会车辆的便捷通行,提出了改进的模型和算法。最后,通过简单的算例验证了模型和算法的合理性,可以兼顾应急物流车辆和一般社会车辆的通行需求。

作者贡献声明

丁 蕾:模型开发,软件编制,部分文稿撰写。

杭虹利:理论推导,算法设计,部分文稿撰写。

参考文献

1

吕婧张衍晗庄玉良. 公共卫生危机下基于智慧物流的应急物流能力优化研究[J]. 中国软科学2020S1): 16. [百度学术] 

LÜ JingZHANG YanhanZHUANG Yuliang. Research on optimization of emergency logistics capability based on smart logistics under the public health crisis[J]. China Soft Science2020S1): 16. [百度学术] 

2

陈慧. 我国应急物流体系存在的主要问题与优化建议[J]. 中国流通经济2014288): 20. [百度学术] 

CHEN Hui. Research on the optimization of emergency logistics system in China[J]. China Business and Market2014288): 20. [百度学术] 

3

吕程. 国内外物流研究现状、热点与趋势: 文献计量与理论综述[J]. 中国流通经济20173112): 33. [百度学术] 

LÜ Cheng. Current situation,hot spots and future trends of logistics research: bibliometrics and theoretical review [J]. China Business and Market20173112): 33. [百度学术] 

4

DASAKLIS T KPAPPIS C PRACHANIOTIS N P. Epidemics control and logistics operations: a review[J]. International Journal of Production Economics20121392): 393. [百度学术] 

5

EKICI AKESKINOCAK PSWANN J L. Modeling influenza pandemic and planning food distribution[J]. Manufacturing & Service Operations Management2014161): 11. [百度学术] 

6

SAKURABA C SSANTOS A CPRINS Cet al. Road network emergency accessibility planning after a major earthquake[J]. EURO Journal on Computational Optimization201643): 381. [百度学术] 

7

DASAKLIS T KRACHANIOTIS NPAPPIS C. Emergency supply chain management for controlling a smallpox outbreak: the case for regional mass vaccination[J]. International Journal of Systems Science: Operations and Logistics201741): 27. [百度学术] 

8

BALCIK B. Site selection and vehicle routing for post-disaster rapid needs assessment[J]. Transportation Research, Part E: Logistics and Transportation Review, 201710130. [百度学术] 

9

HE YLIU N. Methodology of emergency medical logistics for public health emergencies[J]. Transportation Research, Part E: Logistics and Transportation Review, 201579178. [百度学术] 

10

LIU MZHANG D. A dynamic logistics model for medical resources allocation in an epidemic control with demand forecast updating[J]. Journal of the Operational Research Society2016676): 841. [百度学术] 

11

HUANG XSONG L. An emergency logistics distribution routing model for unexpected events[J]. Annals of Operations Research20182691): 223. [百度学术] 

12

刘明李颖祖曹杰. 突发疫情环境下基于服务水平的应急物流网络优化设计[J]. 中国管理科学2020283): 11. [百度学术] 

LIU MingLI YingzuCAO Jieet al. An optimal design of emergency logistics network for epidemic controlling based on service level[J]. Chinese Journal of Management Science2020283): 11. [百度学术] 

13

赵建有韩万里郑文捷. 重大突发公共卫生事件下城市应急医疗物资配送[J]. 交通运输工程学报2020203): 168. [百度学术] 

ZHAO JianyouHAN WanliZHENG Wenjieet al. Distribution of emergency medical supplies in cities under major public health emergency[J]. Journal of Traffic and Transportation Engineering2020203): 168. [百度学术] 

14

WARDROP J G. Some theoretical aspects of road traffic research[J]. Proceedings of the Institution of Civil Engineers195213): 325. [百度学术] 

15

NOVSHEK W. On the existence of Cournot equilibrium[J]. The Review of Economic Studies1985521): 85. [百度学术] 

16

HARKER P T. Multiple equilibrium behaviors on networks[J]. Transportation Science19882239. [百度学术] 

17

BENNETT L D. The existence of equivalent mathematical programs for certain mixed equilibrium traffic assignment problems[J]. European Journal of Operational Research199371177. [百度学术]