交通限制条件下城市物流配送路线优化选择精.doc

第28卷　第3期2004年6月
武汉理工大学学报(交通科学
与工程版
Jou rnal of W uhan U n iversity of T echno logy
(T ran spo rtati on Science&Engineering
V o l.28　N o.3
June2004
交通限制条件下城市物流配送路线优化选择
①
朱永升　韩伯棠　夏　平　李振键
(北京理工大学管理和经济学院　北京　100081
摘要:物流配送网络中最优路线的选择问题一直都是配送中心关注的焦点,对于长途配送而言,交通阻塞和道路拥堵状况可以忽略不计,但对于城市配送而言,由于受交通堵塞和各种交通管制的影响,导致配送路径寻优更具复杂性.文中通过对具有动态的交通堵塞和交通拥挤限制信息及静态禁止通行等限制信息的实际配送网络的描述,提出解决两种限制情况下配送网络寻优的方法,建立了配送网络图中权重确定模型,并提出将交通限制条件下城市物流配送网络转化成无限制的有向图网络,运用D ijk stra算法对其寻优,并对此算法进行了应用举例.
关键词:物流配送;成本系数;D ijk stra算法
中图法分类号:F506
　　物流配送路线优化问题,是配送过程中最重要的问题之一,它直接影响到配送的效率、服务质量和配送的成本.配送路径寻优以最短路为基础,可以归结为正费用网络的最短路问题.K ing等人研究表明,现实配送中距离的6%和时间的12%被浪费掉[1,2].
城市物流配送以城市为配送范围,配送路线繁多复杂,在配送过程中各路段受各种交通信息的影响较大,节点之间的可达性受到制约.通常存在两类交通限制信息:第一类是动态交通限制信息,其特点是随时间变化而动态变化,如交通堵塞;第二类是静态交通限制信息,这类限制信息随时间变化较慢,如交管部门制定出的一系列限速、禁行、禁止转弯和单向行驶等交通规则或交通管制.文中通过对这两类交通限制信息进行分析,进而提出解决两类交通限制的途径,最终探讨交通限制条件下城市物流配送路线优化方法.
1　解决物流配送过程中交通限制信息的途径
对于第一类交通限制信息——动态交通限制,文中拟基于建立配送网络权重模型加以解决.权重是配送网络中最重要的元素之一,它能表明网络中任意节点间距离相对远近、时间相对长短、费用相对大小以及效率相对高低.对于不同的物流配送而言,由于自身专注和所处地位不同,以及所受外界环境影响不同,对配送网络配以不同的权重表达方式.对配送路径配以权重,即相当于对网络图G=(V,E,W中的路线配以权重.式中:V 为网络中的节点集,代表现实中配送中心和各个配送店面;E为节点间的弧集,代表各个节点之间的路径;W为各弧上的权重集,它是确定网络最短路即确定最优配送路径的依据.
在涉及交通最短路和运输最短路问题时,多数文章只是简单地将地理距离或花费时间作为各弧的权重,求最短路问题或者最优路径问题即是求空间距离最短的路线或所用时间最少的路线.这种确定权重的方式,其最直接的好处就是方便快捷,容易操作,便于理解.但它存在明显的缺陷.对于配送问题而言,它不是简单的单目标规划,它涉及到很多因素,而且各种影响因素还是动态变化的,因而,配送路径优化问题实质上是一个多目标动态规划问题.单以距离或时间为权重,不能获得配送过程整体最优.有时地理距离可能很短,但由于交通拥挤或者路况不佳,也会花很长的时间
①收稿日期:20040227
　　　　朱永升:男,28岁,博士生,主要研究领域为供应链和物流配送、信息管理
和很高的费用,降低了配送的效率.相反,对于交通顺畅的路段而言,尽管距离较长,但所用的时间可能很短,同时还涉及到过路费、过桥费等问题.
文献[3]给出一种改进的权重确定方法,根据道路拥挤的程度对给定路段要素加权,用路段长度乘以加权系数作为路段加权长度,路段交通越堵塞,此路段的加权系数越大.该权重确定方法较前两种有所改进,但文中没有具体说明加权系数如何确定?也没有说明权重为定值还是为变值.因为交通拥挤程度是动态的,受意外事件影响较大,所以加权系数不易确定,其参照基准也不易确定.同时,没有考虑可能附加的额外成本费用问题,所以对配送路径优化的可行性值得探讨.综上所述,以地理距离和时间决定权重,以及文献[3]给出的方法确定权重,都具有片面性,存在不同程度的缺陷.
文中通过对影响权重的各种因素的深入剖析,建立基于成本的权重模型.这里的成本包括配送费用和时间成本,由于配送费用最小化与最短路问题实质相类似,所以基于成本最小路径寻优实质上是基于距离、费用和时间综合最小的路线选择.该方法尽管看起来比较繁琐,但其客观、全面,充分包含地理距离、时间距离、路况信息以及附加费用等信息,而且它还是一个动态变化控制方法,根据不同的时段、不同的路段,确定不同的加权系数,反映了道路的实际情况.
为了达到城市物流配送路线的最优化,将各路段的配送成本系数作为各段弧的权重,求解的最优路线即是成本系数最小的路线.在确定权重(成本系数时,为体现交通堵塞对配送的动态影响,将物流配送成本主要划分成耗油成本F 1,人工和运输工具时间占用机会成本F 2以及附加成本F 3三大部分.其中F 1不仅反映配送的距离,而且也反映路况信息;F 2主要反映不同路段、不同时段的道路拥挤状况;F 3主要指前面提到的过路费、过桥费等额外费用,一般依据路段比较固定.各费用表达式如式(1,(2.
F i 1=Y ×L i ×(1+Ηi
(1F i 2=(C H +C T T ϖi (1+Κij =
　(C H +C T (L i v λi (1+Ηi (1+Κij
(2
式中:F i 1为第i 路段耗油成本;F i 2为第i 路段时间
占用机会成本;F i 3为第i 路段附加成本;Y 为单位距离耗油成本;L i 为第i 路段Euclid 直线距离;Ηi 为第i 路段实际距离与直线距离修正系数;C H 为单位时间人工成本;C T 为单位时间运输工具机会
成本;T
ϖi 为通过第i 路段的平均时间;v λi 为通过第i 路段的平均速度;Κ
ij 为第i 路段第j 时段道路拥挤状况修正系数.
其中,参数Ηi 可根据城市道路交通经验值加以确定,文献[4]给出将直线距离近似换算成公路、铁路和城市街道实际距离的换算系数,分别增加21%,24%和42%.Κij 可以根据历史数据回归分析得到,或通过经验值判断,若道路通畅即车流
速度等于V ϖi 时,Κij 取0
.同时,考虑费用和时间的权衡,建立配送网络权重模型,第i 路段的成本权重为
w i =Αi ×F i 1+(1-Αi ×F i 2+F i 3
(3式中:Αi 为第i 路段费用偏好系数;(1-Αi 为第i 路段时间偏好系数.
对于第二类交通限制信息——静态交通限制,将其反映到图论中可以分为两种情况:(1某些路段限制车速.这种情况下,该路段的空间距离没有变化,但由于车速的限制,使得配送车辆通过该路段的时间发生了变化,所以可以通过修正权重模型式(2中的Κij 对权重加以调整;(2某段时间某些路段禁止通行、某些路口禁止转弯、某些路段单向行驶和临时管制等.可以看作是含有禁止路段的配送路线优化问题.
2　含有禁止路线物流配送网络的最
优路线问题的数学描述
对于禁止通行、禁止转弯和单向行驶等情况,在配送网络图中,相当于图中某一条弧为禁止路线,如图1中e 3或e 5为禁止通行,在寻找最优路线时只要将e 3或e 5删除即可.但如果e 5和e 8同
时为禁止路线(相当于“禁止左转弯”
或e 5和e 6同时为禁止路线(相当于“禁止右转弯”,这时不能同时删除e 5和e 8或e 5和e 6,否则其他路线也会
成为禁止路线.文中主要介绍含有两条禁止路线的情况

.
图1　配送网络图
定义1　含有禁止路线的有向网络为一个四
・293・武汉理工大学学报(交通科学与工程版2004年　第28卷
元组N=(V,E,B,D.式中:V={V1,V2,…,V n}为节点集;E={e1,e2,…,e m}为弧集,E中的任意元素e k为V中某两个元素V i,V j的有序对,记为e k=V i V j,k=1,2,…,m,V i和V j分别为弧e k的头和尾,对于弧e i=V i1V i2,e j=V j1V j2,都属于E,如果e i的尾与e j的头重合,即V i2=V j1,则称e j为e i的直接后续;B为禁止路线,B={b1,b2,…,b l}, B中每一元素b r是V中某3个元素V i,V j,V k的有序集,记为b r=V i V j V k,其中V i V j,V j V k∈E,表示节点V i经有向弧V i V j到达节点V j,再经过有向弧V j V k到达节点V k的路线是禁止路线;D是距离矩阵,D=(d ijn×n,d ij≥0,
d ij=V i V j的弧长当V i V j∈E ∞当V i V j|E
0当i=j时
3　含有禁止路线物流配送网络的最优路线问题求解
在不含有禁止路线的配送网络中,最优路线的求解基本上采用D ijk stra算法.D ijk stra算法诞生于1959年,也被称为标号法.由于其计算点到点之间的最短路径时效率较高,算法简单明了,易于学习和掌握,而且计算直观,所以至今仍被认为是计算最短路径的有效方法之一[5].文献[6]中给出用类PA SCAL语言描述的D ijk stra的最短路径算法.
定义2　给定含有禁止路线网络N=(V,E, B,D,按下述方式确定有向网络N′=(V′,E′,
D′,以原网络N=(V,E,B,D中的弧集E为转换网络N′=(V′,E′,D′的节点集,即V′=E.按下述规则确定弧集E′以及距离矩阵D′=(d′ijm×m:对于节点e i=V i1V i2∈V′,e j=V j1V j2∈V′,如果e j 是e i的直接后继,V i2=V j1,且V i1V i2V j2|B,则e i e j∈E′,d′ij=d i1,i2,否则e i e j|E′,d′ij=∞,i,j,…, m.称为N′=(V′,E′,D′为网络N=(V,E,B,D的转换网络.
以下给出在含有禁止路线网络N=(V,E,
B,D中,以V s为起点,V t为终点的合法s-t最短路(成本系数最小算法:
step1　在网络N=(V,E,B,D中,添加两个虚拟节点V0,V n+1,以及两条虚拟有向弧V s V0, V t V n+1,令
d0j=
0　j=s
∞　其它
　d i,n+1=
0　j=t
∞　其它
将添加了虚拟节点和虚拟有向弧之后的网络记为N
δ.
step2　生成N
δ的转换网络
N ne w
step3　在网络N ne w中运用D ijk stra算法从起点V s V0到终点V t V n+1的最短路线.
按上述算法得到的N ne w网络中从起点V s V0到终点V t V n+1的最短路线(N ne w中的一个节点序列,即是N=(V,E,B,D中的一个有向弧序列,在去掉头尾的虚拟有向弧V s V0和V t V n+1后,

即是含有禁止路线网络N=(V,E,B,D中从起点V s 到终点V t的合法成本系数最短路(用有向弧序列表示[7].
4　例　　证
假设存在一个简化的城市物流配送网络图,在图中假设从市中心到海淀之间修路,所以该路段为禁止通行路段,另外由于某些交通管制原因从丰台到达市中心后,车辆禁止左转驶向石景山,所以丰台—市中心—石景山为禁止路线.现在有一批货物将要从房山运送到通州,该如何确定最优路线(如图2.
图2　假设城市物流配送网络图
按照上述方法,将图2转化为含有禁止路段的有向图N=(V,E,B,D(图3,各路段e i的权重w i=(i=1,2,…,12由式(3确定,如图3所示,则配送最优路线问题即转化为求V1到V8之间权重最小路线问题.
　　计算步骤如下.
step1　给有向图3添加虚拟节点V0和V9,以及虚拟有向弧e0和e13.
step2　再依据转换法则,生成图3的转换网络,得到图4.
step3　在图4中,以e0为起点,e13为终点,由D ijk stra算法可以容易地计算出最短路线为e0e2e4e8e11e13,反馈到图3中,可以看出用节点表示
・
3
9
3
・
　第3期朱永升等:交通限制条件下城市物流配送路线优化选择

图3

　含有禁止路段的有向图
图4　生成图3的转换网络图
为V 0V 1V 3V 5V 7V 8V 9,去掉虚拟节点V 0和V 9,即
得原配送问题的最优路线V V 1V 3V 5V 7V 8,该最短路径是考虑了静态和动态两类交通限制信息而得到的.该方法较文献[3]、[6]相比,对各种交通限制信息考虑更周全,解决的方法更科学实用,为城市物流配送在限制条件下的路径选择提供了可靠的方法.
5　结束语
在实际配送业务流程中,可能经常遇到静态
和动态交通限制信息,采用文中所介绍的解决途径,一方面能够精确合理地确定各配送路径基于成本的权重,以便于确定成本系数最小的优化配送路线,另一方面,对于禁止通行等静态交通限制信息,在权重模型确定出权重的基础上,依据文中的优化方法,模拟实际的交通状况,通过计算机模拟,从而能够快速地满足物流配送中心实际优化物流配送路径的需要.
参考文献
1　K ing G F .D river perfo r m ance in h ighw ay task s .
T ranspo rtati on R esearch R eco rd ,1986,1093:1
~112　王英涛,李春澜,傅　彦.基于效用理论的出行前最优
路径算法研究.武汉理工大学学报(交通科学与工程版,2003,27(5:705~707
3　邹旭东,郑四发,班学钢等.具有交通限制约束的道路
网络最优路径算法.公路交通科技,2002,(8:82~84
4　宋　柏.物流系统单个设施的定点决策方法.集装箱
化,2000(7:5~8
5　蔡淑兰.最短路径算法在铁路客运系统中应用的研
究.燕山大学学报,1998(4:157~159
6　储理才,郭英雄.含有禁止路线网络中的最短路问题.
集美大学学报,2002(3:86~89
7　王朝瑞.图论.北京:北京理工大学出版社,2001.12
Rou ting 2op ti m izati on of C ity L ogistics
D istribu ti on U nder T raffic R estrict Conditi on s
Zhu Y ongsheng 　Han Botang 　X i a P i ng 　L i Zhen j i an
(S chool of M anag e m en t and E cono m ics ,B eij ing Institu te of T echnology ,B eij ing 100081
Abstract
T he rou ting 2op ti m izati on p rob lem of logistics distribu ti on netw o rk is the focu s concerned by dis 2tribu ti on cen ter all the ti m e .Generally ,traffic jam o r rou te crow d i m pact distribu ti on in long distance can be igno red ,bu t the effect can no t be igno red in city distribu ti on ,becau se the actual distribu ti on p rocess is frequen tly i m pacted by traffic jam ,traffic crow d and m any traffic con tro ls ,the p rob lem of seek ing op ti m al rou te is m o re com p lex ity .T he pap er describes the real distribu ting netw o rk that w as restricted by li m it info ,such as dynam ic traffic jam and traffic crow d ,and static fo rb id 2p ass ,and p u ts fo r w ard the m ethod of seek ing op ti m al so lu ti on under these li m it conditi on s ,and estab lishes the m odel to m ake the distribu ti on netw o rk w eigh t ,and b rings fo r w ard to tran sfo r m the li m it netw o rk in to the un li m ited o rien tati on netw o rk ,and then finds the op ti m al rou te by u sing D ijk stra algo rithm ,and gives an exam p le to p rove the arithm etic .
Key words :logistics distribu ti on ;co st coefficien t ;D ijk stra arithm etic
・493・武汉理工大学学报(交通科学与工程版2004年　第28卷