王　佳　池　洁　王　勇

摘要:配送线路的正确选择,有利于提高企业的服务质量,降低成本。通过实际调研,绘制城市道路的距离网络图,并通过交通工程中的浮动车法计算网络图的时间权值,绘制配送时间网络图。运用运筹学中的动态规划算法分别计算配送路线及配送时间的最优线路,并比较说明相应的实际问题。

关键词:浮动车法;网络图;动态规划;最优线路

中图分类号:U116.2文献标识码:A

Abstract: The rightness of choosing distribution routes will be beneficial to enhance the service quality, and reduce the cost. Through practical research, mapping the urban road network graph, and through the floating vehicle method in traffic engineering to calculate the time right in the network, and mapping the distribution time network. Calculated optimal delivery time routes and deliver paths optimal routes by dynamic programming algorithm in operational research, and compared the corresponding practical problems.

Key words: floating vehicle method; network graph; dynamic programming; optimal routes

0引言

物流配送是物流系统中一个重要的环节,是物流节点送达收货人的过程。满足货运要求的前提下,如何选择配送线路是非常重要的,线路优化的目的在于保证运输安全的前提下,使配送线路和运输时间最优。

货物配送的重点就是如何将车辆进行有效利用,使得在配送时间和距离都相对最优的情况下配送到客户手中。由于规定了装卸点位置,力求多装快跑,节约时间和费用,提高效率,最经济就是两点间最佳运行路线。采用运筹学方法统筹考虑配送路线和配送时间,寻求最经济运行线路是非常必要的。本文应用相应算法并通过对济南市区配送线路的调查,计算相应的最佳配送线路,并进行对比说明一定问题。

1线路优化方法概述

假设某配送中心负责b个接货点V=v,v,…,v,v为配送站,G=V,E,W由城市道路构成的网络图,V=V∪Yv,E,W分别表示城市道路构成得边集,以及道路长度(或时间)构成的权集。

这类问题可用动态规划方法求解:第一步,将问题划分为m个阶段(阶段数划分根据接货点数而定);第二步,状态变量v,S,v∈V,v表示送货车从v走到v,S表示到v之前所经过的接货点集合,SV;第三步,此处决策表示由一个接货点v走到另一个接货点v;第四步,最优指标函数fv,S=fvSv+pk=1,2,…,m,其中,Sv表示除i之外的接货点,p表示v和v两点间最短距离;边界条件为fv,φ

=p, j=1,2,…,m。进而求得来回且经过要求的点,使得路程最短。

2实际中配送路线的线路优化

现有批娱乐设备,打算由运输车从济南长途汽车总站配送到大明湖、趵突泉和千佛山三个旅游景点,并回到长途汽车总站,试计算一条最短配送路线使得来回所走的路程最短。我们经过实际测算得到图1。

对图1进一步说明如下,v:长途汽车总站,v:三孔桥,v:天桥,v:人民商场,v:大明湖,v:趵突泉,v:省中医,v:青龙桥,v:千佛山。针对上述路线图,求配送车从v(长途汽车总站)出发途经V

=v,v,v返回v,求最短环游路线及路径。

解依据动态规划方法原理,由边界条件可知:

fv,φ=p=3.95; fv,φ=p=4.22

fv,φ=p=7.30

当K=1时:

fv,v=fv,φ+p=4.22+3.16=7.38

fv,v=fv,φ+p=7.30+6.24=13.54

fv,v=fv,φ+p=3.95+3.16=7.11

fv,v=fv,φ+p=7.30+3.08=10.38

fv,v=fv,φ+p=3.95+6.24=10.19; fv,v=fv,φ+p=4.22+3.08=7.30

当K=2时:

fv,v,v=minfv,v+p, fv,v+p=min10.38+3.16, 7.30+6.24=13.54

fv,v,v=minfv,v+p, fv,v+p=min13.54+3.16, 10.19+3.08=13.27

fv,v,v=minfv,v+p, fv,v+p=min7.38+6.24, 7.11+3.08=10.19

当K=3时:

fv,v,v,v=minfv,v,v+p, fv,v,v+p, fv,v,v+p

=min13.54+3.95, 13.27+4.22, 10.19+7.30=17.49

由此,通过动态规划的追溯方法得到由v出发配送货物到v,v,v这三个配送点,并最终回到v出发点,这条路线的路程最短的最优路径,即距离17.49km,这条路线为:

v→v→v→v→v→v→v→v→v→v或v→v→v→v→v→v→v→v→v→v

上述路线说明,配送车按照上述路线行走,使得配送线路的路程最短。

3实际中配送时间的线路优化

3.1配送时间调查表的绘制及计算。对于上述线路图1,通过浮动车法并应用相应公式计算各段路程时间。首先对长途车站到天桥间距离l为1.42km的线路进行调查,并绘制调查记录表,表1中各列含义为:T:出发时间,t:行程时间,X:迎面驶来的车辆数,Y:超越测试车的车辆数,Y:测试车超越的车辆数,Y:超越测试车车辆数与测试车超越车辆数之差,且表中序号1～6表示测试车向南行驶,序号1′～6′表示测试车向北行驶。调查表如表1。

浮动车法调查计算表如表2。

(1)先计算向南行情况

q===19.78辆/min=1 187辆/h;=t-=4.56-=4.56-0.08=4.48min

=×60=×60=19.02km/h

(2)再计算向北行情况

q===20.33辆/min=1 220辆/h;=t-=4.62-=4.62min

=×60=×60=18.44km/h

计算由长途车站到天桥时间为4.48min,而返回的时间为4.62min,取平均值当作行程时间为4.55min。

3.2配送时间网络图的建立及计算。图2中各节点与图1中相同,同样应用浮动车法求得了其他路段的行程时间,如图2所示。

由v配送到v,v,v三个配送点,并回到v,这条路线的时间最短为33.41min,最佳配送路径为:

v→v→v→v→v→v→v→v或v→v→v→v→v→v→v→v

上述路线说明,配送车按照上述路线行走,使得配送线路的配送时间最短。

4配送路线与配送时间类比

经计算得知若按最短距离行走,路线长度为17.49km,但花费的时间是64.65min。而按最短时间为33.41min行走的路线长度为23.41km,显而易见,如果按最短距离行走,虽然距离比按最短时间行走少了5.92km,但时间却多花费了31.24min,时间也是效益,节省时间也相当于节约成本,完全可以利用多花费的时间去再配送一趟物品,这样虽然多跑了路线,但却大大提高了车辆的利用率,节约了配送成本。

对于网络优化问题,由路程和时间求得最佳路径是不尽相同的。因此,在生活实践中应综合考虑时间及路程的最优问题,有利于提高车辆的利用率,降低运输成本,使运输效率达到最高。

5结束语

配送线路优化能有效提高企业的服务质量、降低成本,充分考虑时间和路程,效果更加明显。因此,配送线路的优化研究对于发展城市的现代物流业和提高企业的核心竞争力具有重要的指导意义。

参考文献:

[1] 池洁,李莉. 物流中配送区域与配送路线网络优化法[J]. 运筹与管理,2003,12(2):123-126.

[2] 王炜,过秀成. 交通工程学[M]. 江苏:东南大学出版社,2000:23-43.

[3] 陈子侠. 城市卷烟配送线路的网格划分算法[J]. 上海交通大学学报,2003(7):1013-1017.

[4] 曹二保,赖明勇,聂凯,等. 大规模物流配送车辆调度问题研究[J]. 湖南大学学报,2007,34(12):89-92.