基于中国邮路问题的配送线路规划

王林琳 鲍 进

摘要:烟草配送到户的特点是停留点分布分散,配送车辆需穿行于城市的每一条街道,与邮递员的工作特点非常相似。以运筹学上的中国邮路问题为模型,对某烟草配送公司的配送线路进行规划,用定量的方法提高行驶路线的精确性和标准化程度,争取以更少的车辆、人力和里程数完成更大的服务量。

关键词:烟草配送;线路规划;中国邮路问题模型;欧拉回路

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

Abstract: The characteristic of tobacco distribution is that customers are everywhere, and delivery vehicles are through in every street of the city. It is very similar with the work of postman. Based on chinese postman problem, we have researched into the route programming of a tobacco distribution company in order to improve the accuracy and standardization of the routing with quantitative methods and complete more services with less manpower and mileage.

Key words: tobacco distribution; route planning; Chinese post problem model; euler circuit

0引言

中国邮路问题是我国管梅谷教授于1962年首先研究的,可以总结为:一个邮递员每次送信,从邮局出发,必须至少依次经过他负责投递范围的每一条街道,待完成任务后仍然回到邮局,问他如何选择投递路线,从而使自己所走的路程最短[1-2]?

本案例中的烟草配送公司负责济南市5个区(含郊区)及济南市所辖5县市的卷烟配送工作,包括大型超市、便利店、酒店、零售摊点等各种类型客户。公司的配送原则是配送到户,这些停留点的分布相当分散,遍布于城市的每个角落。配送车辆穿行于城市的每一条街道,将每一条香烟送到客户手中,由此联想到了邮递员的工作。因此,选择运筹学上的中国邮路问题来建立模型,进行路线的规划。另外,这种方法比较简便易懂,也容易为司机所接受。

本案例主要针对该公司配送四部的工作情况进行分析,对其配送路线进行重新规划,从而达到以更少的车辆、人力和里程数,完成更大的服务量的目的。

1配送四部的情况简介

配送四部目前备有5辆金杯车,5名司机和5名配送人员,其所负责的客户主要分布在历下区和历城区的市区部分,北面到大明湖北路,南至市中区的土屋路,西起顺河高架桥,东至姚家庄,如图1所示。

6种颜色代表一周6个工作日每天的工作范围;每个范围里又划分10个小区域,5辆车每天分别负责2个小区的配送工作。

目前,该公司的线路规划已进入第三期工程,在统筹调度上已趋于合理化,但通过调研仍是发现了几点问题,如整体分区的形状不够标准化,不同部门的车辆甚至会出现重复线路的情况;某些小区域上的具体行驶路线没有进行定性定量的规划,仍是司机凭经验拍脑袋决定,这就有可能造成不必要的行驶浪费。

2路径优化的总体思路

为了解决上述问题,结合线路规划过程中的一些制约因素以及公司的实际情况,我们提出了路径优化的总体思路如下:

2.1初步确定每辆车每天的平均配送户数

通过这个约数限制出路径规划的大致范围,即一辆车一天所能配送的最大范围。表1是配送四部5辆车一周6个工作日每天配送的客户数量统计表。

由表1可以看出每辆车的服务户数弹性很大,最小值为45户,最大值亦可以达到78户,因此我们姑且假设优化后每辆车每天的平均配送户数达到最大值78户。后期通过模型验证是否能够达到该数值。

另外,在实际的配送过程中,每个摊点并不一定每星期都订货,也就是说,某天配送的小区内会有个别摊点不在配送范围内,不做停留。

2.2邮路问题模型的建立

运用中国邮路问题的模型,对行驶路径进行全面规划。本案例截取和平路和文化路之间的一段区域,该区域原本是由四部的1号车用一周6个工作日完成配送任务。采用邮路问题建模对行驶路径进行规划,从行驶里程数和工作时间两方面比较规划前后的差别。

图2为和平路和文化路之间的燕子山小区的电子地图,蓝点为统计获得的配送停留点的标记。以该小区为例说明如何借助邮路模型来进行规划。

邮路问题的基本原理是每条边上最多重复一次;在图中每个回路上,有重复的边的长度不超过回路总长的一半。分两步来完成:

Step1:确定一个连通图G

图3是抽象出来的该小区的几条街道的示意图。数字表示街道的长度,由济南电子地图上采集,取其约数,单位为公里。红星为选择的车辆出入口。

连通图是指一个图中每一对顶点之间至少存在一条链;链的概念是图中点、边连续交替序列,顶点可重复,边不重复。为了使截取的路径满足上述要求,需进行第二步。

Step2:求出欧拉回路

欧拉回路是指连通图G中,若存在一条回路,经过每边一次且仅一次。很显然,在图中若要遍历所有街道,经过每边仅一次不可能达到要求,因此要构建重复走的路径。方法如下:

(1)找出图中的奇点,并两两相连;奇点是指次为奇数的点。任何图中奇点的个数都为偶数个。其中次是指端点的边的个数称为该点的次;

(2)连接两奇点的虚线长度不超过回路总长的一半。

如图4所示,“×”表示奇点;虚线代表重复走的路径;括号里的数字表示给每一小段街道排上的序号,方便后面走法的表示。它与图3中的里程数是一一对应的。

从红星处进入,遍历所有街道从红星处返回。走法不唯一,只要满足上述方法的要求即可,最终确定的一种走法为:(1)—(2)—(3)—(4)—(4)—(5)—(2)—(6)总里程数为3.87公里。其余地区的配送路线以此类推,分别算出行驶里程数。

2.3模型数据整理

上述计算完成后统计行驶里程数,进而换算出配送时间,找出节约量,从而对每天的配送户数做进一步的调整。

这里要提到两个概念,配送里程数和辅助里程数。配送里程数是指从到达配送区域开始至走出配送区域为止的距离,也就是我们欧拉回路的总长。辅助里程数是指从公司到配送区域和从配送区域返回公司的这两段空程的距离。

和平路和文化路两条主干道之间原本是1辆车6天的工作量,由于每天配送户数的增加,工作时间减少为4天,其行驶里程数如表2所示。

正常行驶的平均速度为30km/h,在配送的过程中行驶的平均速度约为2km/h,由此可以计算出配送与来回空程的时间。

如:第一天配送时间:8.16/2=4.08h辅助时间:20.49/30=0.68h

汇总后4天的行驶时间如表3所示。从中可见,该条线路每天的工作时间除第4天外,都不够8小时。考虑到私事宽放以及每天从仓库发货的时间,仍有很大的挖掘潜力。

若继续增加每天的配送户数,调整各天配送任务的路线,有望将总天数减为3天,节省了一半的工作时间。

进行线路规划时,并不是所有的街道都适合建立邮路模型,有时建立模型反而增加了行车路线的复杂度,应根据实际情况灵活解决。另外,在做到局部优化的时候还要考虑到一些约束条件,如:避免将主干道划入连通图,主干道上保持右转弯;尽量避免跨街送货或者逆向行驶,降低司机和货车的行驶风险等[3]。

3结束语

本文针对烟草配送的特点选择了中国邮路问题作为模型,对其配送线路进行规划。规划后,配送四部的车辆由原来的5辆缩减为3辆,工作时间由原来的6天缩减为5天。采用该方法最重要的一点是简单易行,在项目报告会上引起中层领导的兴趣,在跟司机的沟通中阻力不大,具有一定的实用价值。

参考文献:

[1] 胡运权. 运筹学基础及应用[M]. 哈尔滨:哈尔滨工业出版社,2002.

[2] 赵刚. 物流运筹[M]. 成都:四川人民出版社,2002.

[3] 陈志红. 运输组织技术[M]. 北京:人民交通出版社,2003.