第 9卷第 1期
2006年 2月
管 理 科 学 学 报
JOURNAL OF MANAGEMENT SCIENCES IN CHINA
V01．9 No．1
Feb．20()6
动态车辆路径问题排队模型分析①
郭耀煌，钟小鹏
(西南交通大学经济管理学院，成都 610031)
摘要：分析了一类动态车辆路径问题，其中顾客需求以泊松流形式出现，现场服务时间服从一
般分布。提 出解决该问题的两种策略：顺序服务策略和中点改进策略，利用排队论、几何概率论
等领域的知识分别求出了这两种策略的系统时间，并通过仿真数据实验验证了这两种策略的
有效性．
关键词：动态车辆路径问题；旅行商问题；排队论；几何概率
中图分类号：U116．2；0221．2 文献标识码：A 文章编号：10ft／一9807(2006)01—0033—05
0 引 言
车辆路径问题(vehicle routing problem，Ⅵ )
将运筹学理论与交通运输中的实际问题紧密联系
在一起，被认为是运筹学领域4o多年来研究最活
跃、成果最精彩的方向之一_1 J．Ⅵ 可以大致描
述为一组车辆从单个或多个车场出发，沿着一定
的路径去不同地点执行运输服务，如装货、卸货、
运货或其它现场服务l2,3j．传统的vRP研究多集
中在静态模型，近 lO年来，由于通讯技术和信息
技术的发展，明显区别于传统静态模型的动态车
辆路径问题引起了人们的广泛重视[ ．与静态
vRP相对应，动态VRP模型的特征表现为：1)计
划者在制定车辆路线时并不完全知道所有相关的
信息；2)新的信息会在路线安排过程以及执行过
程中到来，原有的信息也可能发生改变；3)计划者
不可能仅通过一次调度就得到确定的执行的行车
路线．本文以顾客等待时间最小化作为系统目标，
研究了一类动态vRP的实时优化策略，计算出其
期望系统时问，通过数据仿真试验验证，表明它比
传统的先来先服务策略更好．
① 收稿 日期：2003—10—31；修订日期：2005～04—03，
基金项目：国家自然科学基金资助项目(70071~8)．
作者简介：郭耀煌(1937一 )，男，河南偃师人，教授，博士生导师
1 背景知识
1．1 几个几何概率公式
设 z1( )、Z2( ， 厶)，是边长为 a的
正方形区域A内服从均匀分布的两个随机点，并
且相互独立．
为了便于计算 l z。z2 l的均值和方差，先假
设zl为定点 Z ( l，Y1)，从而
E(1 z Z2 l )=Il(( 丑一X1) +
j
( 一 1) )d dg毛=
』 号d J- 号 j c c 一 +
( 一 。) )dgz2=( a2+ {+ )
现用 Z1替换 Z ：
E(1 Z1 Z2 1 2)：
』 号d 』 号ja一2f＼ 6+ 2 + )d ，
从而得到
E(1 z1 z2 l )： a2 (1)
维普资讯
管 理 科 学 学 报 2OO6年 2月
类似地，可以求得
E(1 zl z2 1)一0．52a (2)
Vat(1 z1 z2 1)=E(1 z1 z2 I‘)一
(I zIz2 I) 0．06a (3)
设 z为／1内服从均匀分布的一个随机点，zn为 A
的中点，用上面的方法可以得到
E(1 z0z l )： (4)
E(i ()z I)一0．38a (5)
r(1 oz 1)=E(1 zoz l‘)一
(I zoz I‘) 0．02a (6)
1．2 M／G／1排 队模 型的 Pollaczek-Khinchin
(P-K)公式
在一个排队模型中，定义：
⋯ 一 单位时问内有一个顾客到达的概率，
简称概率强度；
s——一单个顾客的平均服务时间；
lD～ 一服务强度，即忙碌时间比，』D： ；；
⋯ 一 平均等待时间，即顾客到达时刻与服
务机构开始对其服务时刻之间的时间段的均值；
— — 平均系统时间， ： + ；
一 系统中的平均顾客数，包括正被服务
的顾客和等待服务中的顾客，根据 Little公式有
Ⅳ = ．
列‘于单服务台的M／G／1模型，若输入过程为
泊松过程，服务时间s的分布为一般任意分布(但
是要求s及Var(s)都存在)，则有
Ⅳ =l0+ (7)
这就是M／G／1排队模型的P．K公式[13I。引．
2 动态车辆路径问题排队论模型的
系统时间
动态车辆路径问题可描述如下：一辆货车以
恒定速度 在一个边K为 的正方形区域A内执
行送货任务．为r简化分析，假设这辆货车拥有足
够的载能，即货车无需返回货场重新装载货物．且
假设需求全部为动态需求，需求点的位置在区域
A内服从独立均匀分布，相邻需求的时间间隔 “
1 '
服从负指数分布，并有 “： 1，Var(“)： ．设
^ ^。
货车在送货点停留的时间s 的分布是一般的，其
平均值s 和方差Var(s )都存在．定义 为需求
完成时刻与到来时刻之间的时间间隔， 为需求
开始被服务时刻 i与到来时刻之间的时间间隔，
所 以有 = 一s ；稳态 系统 时间 ：
limE[Ti]，稳态等待时间 = — ．研究的目的
l—0 ∞
是找到一个服务策略来最小化 ，记为 ．
根据上述定义，该动态车辆路径问题可以看
作是一个 M／G／1排队模型．需要注意的是，对于
某个需求 来说，服务时间si应包括货车在 点的
停留时间s 和货车收到需求信息f后驶向 点的
时间 di／V，其中，d 为行驶的距离， 为货车行驶
的速度．对于稳态系统，有
lira 毒 n一∞凡●■ y
： +-fd (8) s=s +
r(s)= r(s )+ r( ) (9)
= ( + )+
一 ， 2 ( (了+ ))
3 动态车辆路径问题的实时策略
3．1 顺序服务策略
顺序服务策略是最简单也最自然的一种动态
调整策略，可描述为：1)当需求连续出现时，货车
将按照先到先服务的顺序从一个服务地点直接转
向下一个地点；2)当货车服务完一个需求后没有
新的需求到来时，它将停留在原地直到下一个需
求到来．
由于各需求点的位置在区域 A内服从独立、
S ∑
l 一凡
n ∞
．
Ⅱ牛
1l
=
S ∑
1 一凡
n ∞
．
+
1l n
即
维普资讯
第 1期 郭耀煌等：动态车辆路径问题排队模型分析
均匀分布，所以根据式(2)、(3)有
『d=E(I Z1 Z2 I)一0．52a
【 r(d)=liar(I Z1 Z2 I)一0．06a
因为E(I z。 z。I)= (÷一z )≥ ( 妻～ )，
(11) 所以有
把式(11)代入式(10)，得到顺序服务策略的系统
时间
序服务策略 =(了+ )+
+
o．5 2a／ + (s )+ O．06a2
(1一 +0．5 2a~／) (12)
3．2 中点重定位策略
不同于静态车辆路径问题，在动态模型中减
小动态需求的等待时间往往比减小货车行驶的总
距离或时间更为重要．
考虑在没有新的需求时调整货车停留地的策
略以减小顾客等待时间．图 1中，由定义可知
I z1 z2 I=d，并设 d =I z1 z2 I．当货车执行完
z 点的任务后，如果已有需求 z2排队，则货车立即
从z 驶向Z2；如果队列中没有需求，则货车返回中
点z0．返回途中如果在某点Z，’接收到新的需求Z2，
则立即驶向z：，否则返回到 zn待命．此时有
J i
Z0
田1 动态车辆路径问题的中点重定位策略
Fig．1 Median strategy of dynamic vehicle routing problem
点重定位策略 =(了+ )+
|=L
_ _ _— —
2
( + ) + s『)+一Var (d'~
J Zl'Zo J
- I啊％t
0 38a ：％ ． Zl— zl
， ： ⋯ - (14)
0．38凸一 一T1
、 ^ ／
按照公式(1)，(2)的推导方法，可以求得
E((d，) )：(1+C2)竿 D
--= ( ·
、 ．
‘ 5
dxz
2dy )d dy
Var(d )：E((d ) )一( )
要显性地求出式(15)中的d 比较麻烦，实际
计算时可运用计算软件(如 Mathematica)求得具
体数据．
4 一个仿真例子
表 1给出了例子的系统参数．
裹1 一个动态车辆路径问题例子的系统参数
Table l Parameters of the example
————T—————r—————广————————————～ 一
f 1 I 服从[0，o．5]内的均匀分布，
a=l 1 V=1 l =0．91一 一 l } J 0．25． 1iar( ) 0．02
由式(9)，可以求出顺序服务策略的系统时问
序服务策略 1．76，而由式(10)、(11)、(12)，得至0中点
重定位策略的系统时问 点重定位策略一1．65．
根据表l中的系统参数，用Minitab软件生成
仿真数据 ，由所生成的数据可计算出
3
l
／ L
lI-，
lI-， 一 ～
+
～
， J - l
＼
—
I
， ， - _ l
＼
维普资讯
一 36 一 管 理 科 学 学 报 2006年 2月
匝序服务策略 =
5O
序月睹 策略
一 ．
税 = 耋 一黼 ∞
误差率
序服务策略 一 匝序服务策略
———————— ：==————————————— 一
顺序服务策略
X 10o％ 1．15％
I × 3
．12％
l中点重毫
可以看出仿真结果 匝序服务策略、 中点重定位策略
都与各自理论计算值基本保持一致．中点重定位
策略的系统时间比顺序服务策略的系统时间减少
率为
点重定位铘 一 卿芋服务策略
————————一 ：= ————————————— ～ 一 TeeA~ X 100％ 8．05％
仿真结果表明了中点重定位策略比顺序策略
参 考 文献：
更能减小顾客的平均等待时间
5 结束语
与静态模型相比，动态车辆路径问题的研究
更具有实际意义．本文应用排队论、几何概率论等
理论导出r一类动态车辆路径问题系统时间的公
式．虽然在公式推导过程中作了一些简化，但这一
结果可以推广到更为一般的情形，如多车型有限
载荷，任意凸有界区域等．本文还给出了顺序服务
和中点重定位这两种实时策略的各自的系统时
间．需要注意的是为了使动态车辆路径问题的排
， 一
、
队模型稳定，一定要满足P= (s +号)<l的条
、 ／
件．当 增大时，如果s 和 受客观条件制约不能
改变，这时调度人员可以减小 d，即通过把整个服
务区域分解成若干个子区域来实现．
[1]Canen A G，Scott L G．Bridging theory and practice in vRP[j]．Journal of the Operational Society，1995，46(1)：1—8．
[2]郭耀煌，李 军．车辆优化调度[M]．成都：成都科技大学出版社，1994．
Guo Yao-hnang，Li Jun．Optimum Scheduling ofVehicleslM]．Chengdu：Chengdu Science and Technology University Press，1994．
(in Chinese)
[3]李 军，郭耀煌．物流配送车辆优化调度理论与方法[M]．北京：中国物资出版社，2001．
Li Jun，Guo Yao-huang．Theory and Method of Vehicle Optimum Scheduling in Logistics Distribution[M]．Beijing：The Goods and
materials Press of China，2001．(in Chinese)
[4]Psaraftls H．Dynamic vehicle routing：Slatus and prospects[J]．Annals．of Operations Research，1995，61：143--164．
[5]谢秉磊，郭耀煌，郭 强．动态车辆路径问题：现状与展望[J]．系统工程理论方法应用，2002，11(2)：116—12o．
Xie Bing-lei，Guo Yao-huang，Guo Qiang．The dy~mmic vehicle routing problem：Status and prospects[J]．Systems Engineering：
Theory，Methodology，Applications，2002，ll(2)：ll 1加．(in Chine~se)
l6]Bertsimas D J．Ryfin G V．A stochastic and dynamic vehicle muting problem in the euclidean plane[J]．Operations Research，
1991，39(4)：601--615、
[7]Bertsimas D J，Ryzin G V、Stochastic and dynamic vehicle routing in the euclidean plane with multiple capacltated vehicle[J]．Op．
erations Research，1993，41(1)： 76．
[8 J Bertsimas D J，Simchi—levi D、A new generation of vehicle routing research：Robust algorithms，addressing uncertainty[J]．()pem．
fions Research，1996，44(2)：286--304．
19JDejtm H．Dynamic Routing Problem with Service Pime Windows．Doctor Dissertation[D]、 File Hong Kong University ot’Scien e and
Technology，20OO．
[10]Minkoff A S．A Markov decision model and decomposition heuristic for dynamic vehicle dispatching[J]．Operations Researet1．
1993，41(1)：77—91．
[11]Swihart M R，Papastavmu J D．A stochastic and dynamic model for the single-vehicle pick-up and delivery problem[J]．European
Joumal of Operational Research，1999，114(3)：4471464．
[12]Xiangwen L．DylIBI~c and Stochastic Routing Optimization：Algorithms Development and Analysis[D]
． Doctor I)issertation Unive卜
slty ofCalifornia，2001．
维普资讯
第 1期 郭耀煌等：动态车辆路径问题排队模型分析
[13]宋卫斌，苏 秦．虚拟顾客服务系统排队模型[J]．管理科学学报，2001，4(3)：52—57．
Song Wei_b．m，Su Qin．Queueing model of service for invented customer system[J]．Journal of Management Sciences in China，
2001，4(3)：52～57．(in Chinese)
[14]钱颂迪，郭耀煌，等．运筹学(修订版)[M]．北京：清华大学出版社，1990．
Qian Song-di，Guo Y日D．huang，et ．Operations Research(revised edition)[M]．Beijing：Tsinghua University Press，1990．(in
Chinese)
[15]钟小鹏．动态车辆路径问题实时策略与技术支撑分析[D]．成都：西南交通大学经济管理学院，2003．
Zhong Xiao-peng．Analysis of Real Time Strategies and Supporting Techniques on Dyna~e Vehicle Routing Problems[D]．Cheng．
du：School of Economies and Management of Southwest Jiaotong University，2003．(in Chinese)
Analysis of the queuing model of dynamic vehicle routing problem
GUO Yao—huang，ZHONG Xiao-peng
School of Economics and Management，Southwest Jiaotong University，Chengdu 61003 1，China
Abstract：In this thesis，a dynamic model of the vehicle muting problem is developed and analyzed．In this model，
an vehicle with adequate volume travels at a constant velocity in a bounded Euclidean plane to provide services to
demands。whose locations are independent and uniformly distributed over this re,on．The dynamic demands arrive
according to a Poisson process in time and their on—site service times are generally distributed，independent of their
locations．A median strategy for the dy,~-nlc model is proposed to reduce system time of the natural First Come First
Served one，with the improvement of performance verified by simulation results．
Key words：dynamic vehicle muting；traveling salesman problem；queuing theo~；geometrical probability
维普资讯
