基于风险的考虑成本和允许等待的车辆运输调度问题研究

2009年　　6月ChineseJournalofManagementScienceJune.,　2009文章编号:1003-207(2009)03-0087-06

基于风险的考虑成本和允许等待的车辆

运输调度问题研究

孟庆春,张江华

(山东大学管理学院,山东济南　250100)

摘　要:本文同时考虑了成本约束和允许等待情形,研究了最小化风险的车辆运输调度问题,其中运输风险是随时间不同而变化的,即研究在时间依赖网络中基于风险的有约束的运输路径选择问题,以及在选定路径的顶点上决定的出发和等待时间的综合问题。建立了相应的混合整数规划模型,设计了相应的算法,并分析了算法复杂性,最后通过算例验证了该算法的有效性和可行性。关键词:车辆运输调度;交通网络;风险;算法中图分类号:O224　　　文献标识码:A

1　引言

车辆运输调度问题是现代物流系统优化中的一个关键环节,该问题涉及面广,需要考虑的因素多,对企业提高服务质量、降低物流成本、增加经济效益有着重要的影响。对于车辆运输调度问题的研究最早可以追溯到1959年,Dantzig和Ramser首次提出车辆运输调度优化问题,并提出了相应的数学规划模型及其求解算法[1]。此后,国内外学者从不同的方面进行了深入研究并取得了许多卓有成效的成果[2-10],例如:王晓博、李一军(2007)研究了电子商务下的有时间窗的车辆调度问题,并采用了改进的两阶段算法进行求解[9]。李昆鹏、马士华(2008)研究了JIT背景下由3PL主导的供应链中运输协调调度问题[10]。其中大多数研究都是从企业运营的角度考虑问题,以运营成本最小或行驶距离最短为目标。但在车辆运输过程中时有事故发生,这些事故不仅严重的危害了人民群众的生命和财产安全,而且还造成了严重的社会影响,例如,2005年3月29日一辆罐式半挂车在京沪高速公路江苏淮安段发生交通事故,引发车上罐装的液氯大量泄漏,造成29人死亡,10500多名村民被迫疏散转移;2008年6月3日北京某物流公司大货车在行至山西省朔州元

　　收稿日期:2008-12-15;修订日期:2009-03-15

基金项目:教育部高等学校博士点基金项目(20050422043)

作者简介:孟庆春(1973-),男(汉族),山东济阳人,山东大学管

理学院,副教授,硕士生导师,研究方向:物流与供应链管理,营销工程1

源公路时,与一辆依维柯客车相撞,造成22人死亡、2人受伤。因此,车辆运输调度问题涉及的利益攸

关体除了企业自身之外,至少还应包含社会与公众。

随着经济社会的发展,人们生活水平的提高,社会与公众的安全意识也越来越强烈,特别是在某些特殊物品(如石化产品、废弃物品等)运输时,其目标不应只考虑经济目标,更应该考虑运输安全或运输风险。早在1988年,Batta和Chiu在研究危化品车辆运输调度问题时就考虑了运输风险,设计了两种单目标的车辆运输调度模型,其中将危化品泄露影响的人员数量作为风险度量[11]。Leonelli等人(2000)将基于运输风险和运输成本的车辆运输调度问题转化为“最小费用流”问题,依据图论-网络理论进行调度优化[12]。Erkut和Ingolfsson(2000)提出各路段风险方差最小模型进行车辆运输调度规划[13]。但这些研究中都没有考虑风险的时间属性,即考虑的风险为静态风险。Nozick等人(1997)最早考虑了随时间变化的运输风险,提出了一种基于时变参数的多目标车辆运输调度模型,目标是最小化的路线长度,全路的总人口暴露和总事故概率[14]。Zografos等人(2004)提出了考虑时间参数情况下的最小化运输风险和最低运输成本的混合整数规划模型[15]。魏航等人(2006)和Erkut、Alp(2007)增加了完成运输的总时间限制约束条件和允

许停止等待来考虑车辆运输调度问题[16,17]。但就目前的研究来看,对时间依赖网络的车辆运输调度问题的研究还比较少,特别是对基于风险的车辆运

・88・中国管理科学　　　　　　　　　　　　　　　　　　　　2009年

输调度问题。因此,在上述文献的基础上,本文将同时考虑成本约束和运输总时间约束,研究最小化风

险的车辆运输调度问题,其中运输风险是依时间不同而变化的,并允许车辆在顶点处停靠等待以降低运输风险,从而使决策者可以根据自身的情况,选择合适的路径和出发、等待时间。本文共包括五个部分,第一部分为引言,给出了研究背景、意义与国内外研究现状;第二部分描述了本文将要研究的车辆运输调度问题;第三部分建立了基于风险的考虑成本和允许等待的车辆运输调度模型,构造了相应的算法,并对该算法进行了复杂性分析;第四部分给出了算例,验证了算法的有效性和可行性;第五部分对全文进行了总结,并就进一步的研究做了展望。

Ui表示在顶点vi的等待时间上界;ri表示在顶点vi等待的单位时间风险;ci表示在顶点vi等待的单位时间费用;ai表示在顶点vi的到达时间;lij表示弧eij的距离;

wi表示在顶点vi的等待时间;

cij(t)表示t时刻进入弧eij的单位运费;tij(t)表示t时刻出发通过弧eij所需的时间;rij(t)表示t时刻进入弧eij的风险;Xij(t)=

1,t时刻进入弧eij0,t时刻没有进入弧eij

选取顶点1为源点,N为目的地,建立下面的混合整数规划:

T

mins1t1T

2　问题描述

本文将研究交通网络中某一特定源点和目的地之间的车辆运输调度问题,其中运输风险是依赖于时间,并且主要取决于入弧的时间,即一旦车辆开始进入某一弧,风险由进入弧的开始时间决定。为了操作方便,假定时间是离散化的小单位(如1小时或更小的10分钟)。文献[16-18]中允许车辆在每一个顶点停靠等待,但顶点间的停靠是不允许的,其中在文献[17]中考虑了限制等待时间和驾驶时间的不同情形,但考虑到允许等待和现实中长途运输中多个司机随车的现象,本文只考虑有等待时间限制的情形,即顶点上等候时间必须是在零和上界之间。在此基础上,考虑到企业的实际运作情况,本文将增加成本约束和运输总时间约束来研究车辆运输调度问题,所以,本文研究的基于风险的车辆运输调度问题实际上是一个时间依赖网络中基于风险的有约束的运输路径选择问题,以及在选定路径的每个顶点上决定的出发和等待时间的综合问题。

t=1eij∈ET

∑∑r

t=1i∈S(1)

ij

(t)・Xij(t)+(t)=1

T

i∈V

r∑i

・wi

(1)

∑∑X

ij

1i

t=1j∈S(i)

∑∑X

T

(t)-

t=1j∈P(i)

∑∑X

ji

(t)=0,

　　　　　　　　　　　i=1,…,N-1(2)

t=1i∈P(N)T

∑∑X∑∑X

T

iN

(t)=1(3)(4)

ij

(t)≤1,i=1,…,N-1

ij

t=1j∈S(i)

t=1i∈P(j)

∑∑(t+t

T

(t))・Xij(t)-aj=0,

　　　　　　　　　　　j=2,…,N

t=1j∈S(i)

(5)

∑∑t・X

T

ij

(t)-ai-wi=0,

　　　　　　　　　　　i=1,…,N-1(6)

t=1eij∈E

c∑∑

ij

(t)・Xij(t)・lij+

i∈V

c∑

i

・wi≤C

(7)

a1=0,aN≤T(8)(9)(10)

3　模型与算法

311　基于风险的考虑成本和允许等待的车辆运输

0≤wi≤Ui,ai≥0,i=1,…,N

Xij(t)=0或1,eij∈E,t=1,…,T

调度模型

符号约定:

G=(V,E)表示交通网络图,其中:V=(vi)

为顶点集,V=N;E=(eij)为弧集,

P(i)表示顶点vi的前点集;S(i)表示顶点vi的后点集;

T表示完成运输的总时间上界;C表示完成运输的总费用上界;

E=m;

其中:约束(1)—(3)是流守恒的限制;约束(4)保证了只有一条路径;约束(5)—(6)保证了途径弧eij时弧eij的后节点到达时间等于前节点的到达时间加上等待时间和弧的旅行时间;约束(7)满足了在一定成本下进行运输活动的条件;约束(8)定义了整个运输活动的开始时间和最迟结束时间;约束(9)—(10)表示变量的取值范围。312　算法31211　定义及性质

第3期　　　　　　　　　孟庆春等:基于风险的考虑成本和允许等待的车辆运输调度问题研究・89・定义1:假设P=(s=1,…,l)为源点s到顶点

l的一条路径,di表示顶点vi的出发时间,t(i-1,i,di-1)表示di-1时刻出发通过弧ei-1,i所需的时间,

dj+t(j,i,dj)=aj+wj+t(j,i,dj),计算出t时刻

即:di=ai+wi,ai=di-1+t(i-1,i,di-1),d1=

w1,a1=0。

定义2:假设P=(s=1,…,l)为源点s到顶点

l的一条路径,C(i,t)表示t时刻到达顶点vi所花

到达顶点vi所花费成本C(i,t)=C(j,aj)+C(j)+

C(j,i,dj),wj=0,…,Uj;

Step4(判断费用约束):若C(i,t)≤C成立,则转Step5,否则,令r(i,t)=∞;

Step5(计算风险值):对t时刻顶点vi的所有可行路,计算r(i,t)=

minmin{r(j,aj)+r(j)+r(j,i,dj)};()Φ()

j∈Si

P∈={Ps,i,t}

费成本,C(i)表示顶点vi等待所花费成本,C(i-1,i,di-1)表示di-1时刻出发通过弧ei-1,i所花费成

Step6(计算最小风险值):计算r3(N)

0≤t≤T

=

本,即:C(i,t)=C(i-1,ai-1)+C(i-1)+C(i-1,i,di-1),其中t=ai-1+wi-1+t(i-1,i,di-1)=

di-1+t(i-1,i,di-1),C(1,0)=0,C(i)=ci・wi

minr(N,t);

Step7(回溯最小风险路):根据目标值向后回

,C(i-1,i,di-1)=ci-1,i(di-1)・li-1,i。

定义3:源点s到顶点i的一条路径P=(s=1,…,i),若是满足C(i,t)≤C,t=di-1+t(i-1,i,

di-1)≤T和0≤wi≤Ui,则称这条路径为t时刻溯,得到最小风险路。31213　算法复杂性分析定理:基于风险的考虑成本约束和时间限制,顶点可以停靠等待的车辆运输调度问题算法的计算复杂性为O(T2n(m+n))。

证明:第一步初始化赋值需要的时间为O(Tn),第二步对每一个可能的出发时间dj=0,1,…,T,计算dj+t(j,i,dj),共有m条有向边,所以需要的时间为O(Tm),第三步对于顶点vi的等待时间需满足0≤wi≤Ui因此,对于整个问题,其算法计算复杂性为2

O(Tn(m+n))。

到达顶点vi的可行路,记为P(s,i,t),并令Φ={P(s,i,t)}。

定义4:在t时刻顶点vi的可行路集Φ={P(s,

i,t)}中,称风险值最小的可行路为最小风险路,记

为P(i,t)。

定义5:r(s,i,t)表示t时刻顶点vi的可行路

P(s,i,t)的风险值,r(i)表示顶点vi等待过程中的

风险值,r(i-1,i,di-1)表示di-1时刻出发通过弧

ei-1,i的风险值,即:r(s,i,t)=r(s,i-1,ai-1)+r(i-1)+r(i-1,i,di-1),r(i)=ri・wi。最小风险

路P(i,t)的风险值记为r(i,t),若不存在t时刻到达顶点vi的可行路,则r(i,t)=∞。

性质1:对网络G(V,E),令r(1,0)=0,当i≠1,i∈V时,令r(i,0)=∞,则对于i≠1,i∈

V,t=1,2,…,T,有

r(i,t)=

Φ={P(s,i,t)}j∈S(i)P∈

4　算例

下面将通过算例来验证算法的有效性和可行

性。

例:交通网络如图1所示,其中,顶点1代表源点,顶点10代表终点,其余顶点代表路段交叉点。边上的第一个数字为相应弧的旅行时间,第二个数字为相应弧的长度。车辆须从顶点1运往顶点10,顶点1最早可能出发时间为8:00,在每个顶点的等

minmin{r(j,aj)+r(j)+r(j,i,dj)}。

定义6:r3(i)表示时间不超过T由源点s到达顶点vi的最小风险值。

性质2:r3(i)=minr(i,t)。

0≤t≤T

31212　算法

Step1(初始化):令r(1,0)=0,对于i≠1,i∈

V,令r(i,0)=∞,Πi,Πt>0,令r(i,t)=∞;

Step2(计算到达时间):对所有有向边(j,i)∈

E,计算出所有可能的顶点vi的到达时间ai=dj+t(j,i,dj),其中,dj=0,1,…,T;

Step3(计算费用):t=1,2,…,T,dj满足t=

图1　交通网络图

・90・中国管理科学　　　　　　　　　　　　　　　　　　　　2009年

待时间最多不超过2小时,最迟20:00运到终点10。不同路段不同时间段的风险值如表1所示,不

成本为50元/小时,运输总成本不超过1300元,单位时间的等待风险为10-4,计算出顶点1至顶点10

的最小风险值及其相应的最小风险路。

同时间段的运输费率如表2所示,所有顶点的等待

表1　各路段不同时间的风险(10-4)

路段

(1,2)(1,3)(1,4)(2,4)(2,5)(3,4)(3,6)(4,5)(4,6)(4,7)(5,8)(6,9)(7,8)(7,9)(7,10)(8,10)(9,10)

时间段

8-91912915124128311531564155710931561113141661861413315686151414199-10916181558165315621623156317951572185101211511411142138381491611413

10-1171215194418121851189218511824105211461786109671611934164181915

11-1291613156318421382112138214331811715165713161865171166481171698155

12-1314144175712131811053156310361332156814712128157815521855717121413

13-14125194517721381126315631794156218561789174511411143156481191611114

14-15418131841812185115721382143310411424152713161868155211428187121915

15-1641323156517711921121141182215311715165610967162114281881658155

16-1741814128418121141189119115221031128313981534129517114328187121517

17-18916151947121213811572138212731811715108917451148155213857171414915

18-19191271131241282113156310361332185101212126141331565717121711

19-2014146118816531561157218521433182114617811511411142185761991611413

表2　不同时间段的运输费率

时间段

运输费率(元/公里)

0-45

4-84

8-122

12-163

16-203

20-244

　　根据上一小节所给算法计算出考虑成本约束和允许等待的最小风险路为1-3-6-9-10,成本为1270元,其中在顶点1处等待1小时后出发,风险

值为43108×10-4。

下面比较一些典型路线在允许等待和不允许等待情况下风险和成本情况,具体计算结果见表3。

表3　典型路线的不同策略下的风险和成本对照表

序号

12345678

线路

1-2-5-8-101-3-4-6-9-101-3-6-9-101-4-5-8-101-4-6-9-101-4-7-8-101-4-7-9-101-4-7-10

风险(10-4)

5419645172491357145501467312466127107148

不能等待成本

10301300116010301180109010601000

总时间

79888998

风险(10-4)421434517243108

4941199621745911999145

有等待时间等待时间成本

30112311

13601300127011401400144011601100

总时间

109991012109

　　下面比较不同约束条件下最短路的成本、风险

和总时间:

1)无任何约束条件下,最小成本最短路为1-4-7-10,成本为1000元,总时间为8小时,风险为107148×10-4;

2)无任何约束条件下,最短时间路为1-2-5

-8-10,成本为1030元,总时间为7小时,风险为54196×10-4;

3)无任何约束条件下,最小风险最短路为1-3-4-6-9-10,成本为1300元,总时间为9小时,

风险为45172×10-4;

4)如果顶点允许停靠等待,而不考虑成本约束

第3期　　　　　　　　　孟庆春等:基于风险的考虑成本和允许等待的车辆运输调度问题研究・91・条件下,最小风险最短路为1-4-6-9-10,成本为1400元,其中在顶点1处等待2小时后出发,风险为41199×10-4;

5)如果要考虑企业的成本不超过无任何约束条件下的最小风险最短路的成本,即不超过1300元,顶点允许停靠等待情形下的最小风险最短路为1-3-6-9-10,成本为1270元,其中在顶点1处等待1小时后出发,风险为43108×10

-4

andStudies[M].Amsterdam:ElsevierSciencePublish2ersB.V.,1998.

[4]Zhong,YJ.,Michael,H.C..Avehicleroutingproblem

withbackhaulsandtimewindows:Aguidedlocalsearchsolution[J].TransportationResearchPartE,2005,41(2):131-144.

[5]郎茂祥,胡思继.用混合遗传算法求解物流配送路径优

化问题的研究[J].中国管理科学,2002,10(2):51-56.

[6]谢秉磊,安实,郭耀煌.随机车辆路径问题的多回路优

。

通过以上分析可以清晰地看出,允许停靠等待将使得运输风险得到明显降低;另外,从以上不同约束条件下的最短路看,成本和风险是基本成反比关系,因此,在车辆运输调度优化过程中需要在成本和风险二者间进行权衡,使得既能满足社会与公众的利益,又能符合企业的利益。

化策略[J].系统工程理论与实践,2007,27(2):167-171.

[7]潘震东,唐加福,韩毅.带货物权重的车辆路径问题及

遗传算法[J].管理科学学报,2007,10(3):23-29.

[8]侯立文,谭家美,赵元.求解带时间窗的客户需求可分条件下的车辆路径问题[J].中国管理科学,2007,15

(6):46-51.[9]王晓博,李一军.电子商务下基于改进两阶段算法的有

5　结语

目前对于基于风险的车辆运输调度问题的研究还比较少,特别是风险依赖于时间,使得在求解的过程中相对比较困难。本文在前人研究的基础上,对基于风险的考虑成本和允许等待的车辆运输调度问题进行了研究,建立了相应的混合整数规划模型,设计了相应的算法,并进行了算法复杂性分析,算例结果验证了算法的有效性和可行性。当运输企业在运输某些特殊物品且其目标为最小化运输风险时,本文的研究可使决策者根据自身的情况,选择合适的运输路径和出发、等待时间,进而降低整个运输过程的运输风险。典型的应用包括石油石化企业的油品配送、医疗卫生机构的医疗废弃物品的运输,等等。对于本文提出的基于风险的考虑成本和允许等待的车辆运输调度问题,在大型复杂网络环境下降低计算复杂性和开发快速有效的算法将是进一步需要解决的问题,未来可探讨利用动态规划算法、分枝定界法或启发式算法来求解该类运输调度问题,并在此基础上,从政府监管部门的视角出发,应用双层规划方法研究符合企业、公众和社会及政府监管部门三方面利益的车辆运输调度问题。参考文献:

[1]Dantizig,G.,Ramser,J1.Thetruckdispatchingprob2

lem[J]1ManagementScience,1959,6(1):80-911[2]Laport,G1.Thevehicleroutingproblem:Anoverview

ofexactandapproximatealgorithms[J]1EuropeanJour2nalofOperationalResearch,1992,59(4):345-3581[3]Golden,B.L.,Assad,A..VehicleRouting:Methods

时间窗车辆调度优化[J].中国管理科学,2007,15(6):

52-59.

[10]李昆鹏,马士华.基于JIT配送的3PL运输协调调度

问题建模与分析[J].中国管理科学,2008,16(1):73

-79.

[11]Batta,R.,Chiu,S..Optimalobnoxiouspathsonanet2

work:transportationofhazardousmaterials[J].Oper2ationsResearch,1988,36(1):84-92.

[12]Leonelli,P.,Bonvicini,S.,Spadoni,G..Hazardous

materialstransportation:ariskanalysisbasedroutingmethodology[J].JournalofHazardousMaterial,2000,71(1):283-300.

[13]Erkut,E.,Ingolfsson,A..Catastropheavoidance

modelsforhazardousmaterialsrouteplanning[J].TransportationScience,2000,34(2):165-179.[14]Nozick,L.K.,G.F.List,M.A.Turnquist.Inte2

gratedroutingandschedulinginhazardousmaterialstransportation[J].TransportationScience,1997,31:200-215.

[15]Zografos,K.G.,Routsopoulos.,K.N..Aheuristic

algorithmforsolvinghazardousmaterialsdistributionproblems[J].EuropeanJournalofOperationalRe2search,2004,152(2):507-519.

[16]魏航,李军,蒲云.时变条件下有害物品运输的路径

问题研究[J].系统工程理论与实践,2006,26(10):

107-112.

[17]Erkut,E.,Alp,O..Integratedroutingandscheduling

ofhazmattruckswithstopsenroute[J].Transporta2tionScience,2007,41(1):107-122.

[18]Cai,X.,Kloks,T.,Wong,C.K..Timevaryingshor2

・92・中国管理科学　　　　　　　　　　　　　　　　　　　　2009年

B沃林.网络流—理论、算法与应用(英文版)[M].北

testpathproblemsalgorithmforproblemswithcon2straints[J].Networks,1998,31:193-204.[19]拉文德拉・K・阿胡亚,托马斯・L・马南提,詹姆斯

京:机械工业出版社,2005.

AStudyonRisk2basedVehicleSchedulingProblemundertheCostConstraintsandAllowingforWaiting

MENGQing2chun,ZHANGJiang2hua

(SchoolofManagement,ShandongUniversity,Ji’nan250100,China)

Abstract:Thispaperstudiesthevehicleschedulingproblemofminimizationofthetransportationrisksvar2iedwithtime,takingintoaccountthecaseofthecostconstraintsandallowingforwaitingatthenodesofthenetwork.Thatis,anintegratedrisk2basedpath2selectionproblemtogetherwiththedeterminationofthedepartureandwaitingtimeeachnodeontheselectedpathinthetime2dependentnetworks.Afteramixedintegerprogrammingmodelisproposed,anovelalgorithmisgiven.Thecomputationalcomplexityofthealgorithmisalsoanalyzed.Finally,anumericalexampleispresentedtoshowtheeffectivenessandfeasibilityofthisalgorithm.

Keywords:vehicleschedulingproblem;transportationnetwork;risk;algorithm