烟草配送线路优化问题的探讨_图文

1、烟草配送线路优化问题的探讨王 芳江苏省泰州市烟草专卖局(公司摘要:配送是物流运输活动的一个重要环节,配送线路规划得成功与否将直接关系到现代物流中心运行的成本和效率。本文对该VRP问题及算法进行了比较深入地研究探讨。对配送区域的形成、区域内优化线路的形成这两个线路优化过程中的关键性问题进行了细致地分析研究,并用一组测试数据验证了算法的可行性。整个方案具有较强的实用性、科学性和实践性。关键词:烟草配送;配送线路VRP问题;线路优化1配送线路优化问题研究的意义烟草行业是国民经济重要而又特殊的行业,实行的是“统一领导、垂直管理、专卖专营”的管理体制。烟草行业在国民经济中占有举足轻重的地位。但随着中国加

2、入WTO, WHO推出了一系列的控烟措施,再加上经济全球化的影响使中国烟草行业面临着前所未有的挑战。中国烟草行业迫切需要提高自己的核心竞争力来应对越来越严峻的形势。现阶段烟草行业的核心竞争力主要由两个方面构成:其一是产品技术,也就是生产国式卷烟所需的各项技术;其二就是物流技术,在生产设备、原辅材料趋于同质的今天,如何做到比竞争对手更及时、更有效地满足市场需要已成为企业竞争的重要内容。二者相比,物流技术更具战略价值。配送是物流一个重要环节,从烟草企业的层面上看,烟草配送是关系到企业经济效益实现,关系到卷烟零售户的满意度提高,进而关系到企业核心竞争能力提升和生存、发展的大问题。配送线路规划的成功与

3、否,将直接影响配送成本高低、工作效率快慢和服务质量优劣,关系到大物流建设的整体优势能否体现。2配送线路优化问题分析物流配送线路优化问题,其实就是以线路最优化为目标的车辆调度问题,即VRP问题,问题的实质是对于一个确定的卷烟零售户集合,在确定的需求下,如何安排车辆、安排行驶路线和安排时间,使得总的行使里程数最小。配送车辆调度问题(VRP,最早是由Dantzig 和Ramser于1959年首次提出的,自此很快引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家与运输计划制定者和管理者的极大重视,成为运筹学与组合优化领域的前沿与研究热点问题。线路优化问题一直是学术界的NP

4、难题,一般来说给定约束条件,具体问题的解空间有限,虽然从理论上是可以找出问题的最优解的,但是此类问题的求解非常复杂,特别是随着配送规模的增加,计算量呈指数增长,求解过程复杂。线路优化问题的常用算法,究其实质,基本上可将求解方法分成精确算法和启发式算法两大类。精确算法的计算量一般随问题规模的增大呈指数增长,因此在实际中其应用范围很有限。由于VRP问题是NP困难问题,高效的精确算法存在的可能性不大(除非P=NP,因此寻找近似算法是必须和现实的,为此,专家们主要把精力花在构造高质量的启发式算法上,目前,绝大部分这方面的研究成果也是对启发式算法的设计或改进。尤以两阶段算法是目前成果最丰富、应用最多的一

5、类方法,作者简介:王芳,女,江苏南通人,经济师,在职研究生,硕士,现为泰州市烟草专卖局(公司经济信息中心主任,邮箱:wfnewyear ,通讯地址:江苏省泰州市迎春西路71号,邮政编码:225300,在两阶段法求解过程中,常常采用交互式优化技术,把人的主观能动作用结合到问题的求解过程中,如先路径后分组算法(Route-First/Cluster-Second Method,先分组后路径算法Cluster -First/ Route -Second Method 3烟草配送线路优化的研究 如何对配送线路进行科学地优化和整合,对配送车辆进行合理的调度、对线路之间的工作量进行科学的均衡,对配送车辆装

6、载率进一步合理的提高,是烟草配送线路优化希望达到的目标。3.1问题提出与描述(1已知条件所有卷烟零售户的集合N 为已知,2,1,0n N =,其中,0为配送中心,其他为卷烟零售户所在地;从配送中心出发的配送车辆,经过卷烟零售户所在地之后再返回配送中心,这时,配送车辆所经过的零售户的顺序称为路线;在配送中心的配送车辆的种类、数量以及每辆车最大装载能力W 为已知;卷烟零售户i P 数为n,地理位置i G 为已知,且每一个客户的卷烟需求量i R 已知(i=1,2,n;每辆车每日最长送货时间为k T ;配送中心到各零售户点的距离及零售户之间的距离为ij d (1,2,1=n i ;n j ,2,1=,

7、j i R2,则把Z 作为第二个凝聚点Z2,否则继续判定下一密度最大者,若下一密度最大者的点与前面若干个凝聚点之间距离均大于R2,则将之作为又一新的凝聚点,如此反复迭代直到达到要求聚类的数目k。5 把得到的k 个聚类中心Z1,Z2,Z3,Zk 作为K-MEANS 算法的初始聚类中心。 以一组测试数据为例,模拟为97零售户的地理座标信息,其分布如下图: 图1 零售户的地理坐标信息模拟Fig. 1 Simulation of retailers geographical coordinates按照上述改进后聚类算法的思路,将97个零售户分成八个类,即八个配送区域。 图2 八个类的分布图(情况二Fi

8、g. 2 Distribution of eight clusters in 2nd situation以车载量为限制条件对聚类结果调整聚类完成后,还应根据车载量这个约束条件对聚类结果进行判断调整。具体实现方法为: Step1:计算每一个类内的零售户的订单量总和;Step2:判断每一类内零售户订单量总和是否超过车载量如果未超过,说明符合限制条件。如果超过车载量,选择该类中距离质心最远的点,将其拟归入距离其他类质心距离最近的类,归入某一类前,还必须判断如归入后该类的卷烟零售户的订单量是否小于车载量。如果小于,即将该数据归入该类,否则,选择欧氏距离再次之的类作为拟归入的类,同样判断该

9、类卷烟零售户订货量是否小于车载量,如果小于则归,否则选择距离再次之的。Step3:当所有的类零售户订单量总和都小于车载量时,暂告一段落。调整完毕以后,每一类的卷烟零售户地理位置相对集中,且订单量总量小于车载重量。 以工作量为限制条件对聚类结果调整提出泛工作量的概念,对配送线路的工作量进行测量,并以工作量为约束条件对聚类以后的结果进行调整。关于配送人员工作量的计算一直是物流配送中心管理工作中一个难点。难点之一在于影响配送人员工作量的因素较多;难点之二在于各影响因素的量纲不统一,无法计算和判断。为了能更好地计算配送人员的工作量,笔者通过与配送中心管理人员、驾驶员、送货员进行广泛接触,

10、了解配送人员的实际工作情况,并通过实地跟车送货,提出了一个衡量配送人员工作量(包括驾驶员和送货员的一个概念“泛工作量”。该指标综合考虑了送货里程、零售户户数、送货卷烟量,以及零售户的结算方式、路况等因素,并且通过一定的权值,将各个影响因素均统一转化成秒、分或小时这些时间单位的数值,从而将工作量的大小以工作时间的长短来表示,能比较直观和准确地衡量不同送货线路负荷大小。具体可以用下式来表示:i L =1a i C +2a i P +3a i R + 4a i H +D (1式(1中:i C 为配送线路的长度、i P 该条配送线路上零售户数、i R 为该条配送线路上卷烟配送量、i H 为配送线路上现

11、金结算的零售户、D 为配送人员每天配送卷烟必须花费的固定时间,主要包括车况检查、停车入库的时间、现金交付银行。1a 、2a 、3a 、4a 分别为i C 、i P 、i R 、i H 的权值,该数值的确定主要根据对历史数据的分析以及根据笔者的实地跟车送货过程对配送人员具体工作量的分析得出。(11a 系数的确定,11bv=,影响1a 系数有两个因素,一是配送车辆速度理论速度v,二是配送道路的路况, 用交通路况系数b 来表示,路况越差,b 越小,配送时间越长。如送货车辆依维柯行驶速度为v =50公里/小时,五菱之光行驶速度为v =30公里/小时,如果将路况分三级(必要时可以分得更细,根据路况的不同

12、,可以得到不同的1a 。具体见下表:表1 1a 系数结果Tab. 1 Results of coefficient 1a一级(政务区二级(住宅区三级(商业区交通路况系数1b 0.8 0.6 0.4 依维柯速度v40公里/小时30公里/小时20公里/小时五菱之光速度为v24公里/小时18公里/小时12公里/小时依维柯1a 0.025 0.033 0.05 五菱之光1a0.0420.056 0.083配送线路的长度,即配送车辆将卷烟送到其配送区域内的所有零售户门上所行驶的线路长度。它的计算是一个比较复杂的计算,将会在下述中国邮递员问题中进行探讨。(22a 系数的确定,2a 系数取决配送人员完成一个

13、零售户配送流程的时间。按照目前的工作规范和要求,配送人员的工作流程大致为:停车靠边搬烟下车步行到零售户店中问候沟通清点卷烟粘贴送货票据收取现金步行回到车上启动开车,其中清点卷烟的时间与该零售户所订卷烟数量有关,将会在讨论3a 系数时加以确定,其他各环节所用时间基本相同,该系数可通过对历史数据或实地调查数据的采集分析得到。如根据实地调查,平均每户零售户完成这个规定环节的工作约需两分半钟。即2a 系数为1.8分钟/户。(33a 系数的确定,3a 系数由配送前装车时间31和+ 卷烟清点时间32构成,每天配送前,配送人员将卷烟人员搬运上车,所消耗的时间为装车时间,配送人员将卷烟送到零售户店中,送货员会

14、当着零售户的面,对卷烟数量、品种和质量以及清点核对,并请零售户在送货单上确认签字,这是卷烟清点时间,这是清点时间。根据实地考察,平均每增加五十条卷烟,装车时间会增加24秒,即31 =0.4分钟/每件,将增加清点时间1.5分钟,即清点系统系数32为1.5分钟/件,3a =0.4+1.5=1.9分钟/件,(44a 系数的确定,4a 为向现金结算户收取现金的时间,约为4a =2分钟/户以一条送货线路为例,该送货线路送货车型为依维柯,其2007年11月送货数量52436条,送货零售户1625户,其中现金结算户487户(目前电子结算户占零售户的比率约70%,送货里程946公里(其中一级路况206公里,二

15、级路况510公里,三级路况230公里,有效工作日22天。该送货线路全月工作量约为:i L =1a i C +2a i P +3a i R + 4a i H +D =2019+3412.5+1992.56+974+440=8838.06分钟=147.30小时 该送货线路平均每天工作量约为:L =L/22=147.3/22=6.7小时,这与实际工作情况基本相符,目前各送货线路上的送货时间一般为6-7小时,进一步印证上述计算工作量的方法的可行性。通过增加上述两个限制条件,聚类结果调整为下图: 图3 调整后的聚类Fig. 3 Adjusted clusters3.3.2第二阶段,利用中国邮递员问题求解

16、配送区域内的优化线路 通过K-MENAS 聚类,再加上车载量和工作量这两个限制条件对聚类结果进行整后,配送区域划分完成。在一个配送区域内如何求得该配送区域的最优行车路线,使得卷烟送货车沿着这条行车路线能将卷烟送到每一个零售户手中,而且所走的路程最短。这是一个求解多点之间的最优化路线问题。中国邮递员问题分析对于多点之间的最优化路线的计算有很多方法,其中中国邮递员问题是解决多点之间的最优化路线比较好的模型之一。中国邮递员问题解决的是边遍行问题,求的是欧拉回路。具体到烟草配送实际,对于某一个配送区域,零售户的经营场所是固定分布在街道上,如果配送车辆能以最优的路线遍行零售户所位处的街道上

17、,即能完成送货任务,这是一个求解欧拉回路的中国邮递员问题。因此,用中国邮递员问题模型来求解某一个配送区域的最优配送线路是比较合适的。用数学的语言来描述就是一个配送区域内的最优线路求解问题:如果把配送区域内街道用一条边(,i jv v,街道的长度用边权w(,i jv v来表示,物流配送中心、街道交叉口用点表示,那么一个卷烟配送区域就构成一个边权连通无向图。配送区域内最优线路的问题用图论的语言来描述,就是在一个边权连通无向图中,怎么寻找一个回路C,使得C至少经过每条边一次且C的长度最短。以上例中聚类四为对象进行分析,该配送区域内有18个零售户,分别位于不同的街道, A点为物流配送中心,V1至V11

18、为街道的交叉口,该配送区域构成如下的边权连通无向图。 图4 聚类四构成的边权连通无向图Fig. 4 Connected graph without direction of cluster 4如果能寻找一个回路C,使得C至少经过每条边一次且C的长度最短。C即是该配送区域的最优送货线路。关于中国邮递员问题的基本解题在上文已作了具体的描述。对于一般的边权连通无向图,求解欧拉回路的关键在于就是求奇次点对最小权完美匹配。最优路线的确定将求G奇次点的最小权完美匹配问题,可转化为指派问题来解。指派问题是运筹学中一个基本问题,是指管理部门可能经常面临这样的问题,有若干项任务需要完成,又有若干对

19、象能够完成其中每项任务,由于每个对象的特点与能力不同,完成各项任务的效益也各不相同。又因任务性质的要求或管理上的需要等缘故,每项任务只能交给一个对象去完成。则应指派哪个对象去完成哪项任务,能够使完成任务的总效益最佳,这类问题就称为指派问题或分配问题。指派问题中,人与任务之间是一对,每一对都有一定的消耗,最终要求解使总消耗为最少的人与任务的配对。同样,奇次点间也是一对对的,每对间的距离即是消耗,最终要求解的就是使总距离为最少的奇点对。效率矩阵就是由奇点对间的距离组成的。此时就将此问题转化成求解指派问题。(1找出奇点及奇点数设一般配送区域线路优化问题均可找到对应的无向图为G=(V,E,V=n,E=

20、m,设图G 有个奇点,分别记为1k v ,2k v kr v ,由图的知识知,r 为偶数。在本实例中,配送区域对应的无向图如下: 图5 配送区域对应的无向图Fig.5 Connected graph without direction for distribution area表2 各点对应的度数值Tab. 2 Degrees of the points点 V1 V2 V3 V4 V5V6V7V8V9V10 V11 V12A 度数3233232334332共有8个奇点,分别为1346891112,v v v v v v v v ,为了计算方便,边的长度不是一个绝对值,按照一定的比例缩小的整数值

21、,实际应用进行一定比例的放大即可。(2求出各个奇点的最短距离利用Floyd 方法,求出各个奇顶点i v 与j v 之间的最短距离,同时将各奇点两两之间的最短距离也一并求出,记ijf 表示奇点mi v 与mj v 之间的最短距离,记F=(ij r r f ,显然,F 为对称矩阵,本例为134689111213468911120678432560188765710798748870896348980125378910362676230355435630v v v v v v v v v v v v v v v v 这个矩阵就是指派问题中的效益矩阵。(3找出各个奇点的两两配对的最优匹配方案 设矩阵(

22、ij r rC c =,其中,ij i j f ij i jc =+=,为最小指派问题的系数矩阵。C=67843256188765717987488789634898125378913626762335543563+解决指派问题的一个重要的方法是匈牙利法,Hungry 法,这种方法是由匈牙利数学家考尼格(Konig,提出的,因此得名匈牙利法,匈牙利算法的理论依据是根据考尼格提出并证明了的两个定理,定理1:设一个指派问题的效益矩阵为(n ij c ,若从(ij c 的第i 行元素中减去一个常数iu (i=1,2,m,从第j 列中减去一个常数jv(j=1,2,n,得到一个新的效益矩阵(ijb ,其

23、中每一元素ij b =ij c -i u -j v ,则(ij b 问题的最优解也是(n ij c 问题的最优解。21定理2:若一方阵中的一部分元素为0,一部分元素为非0,由覆盖方阵内所有0元的最少直线数恰好等于那些位于不同行、不同列的0的最多个数。21用该法可求出*(ij x =0000001000100000010000000000000100000100000010000000100000010000为本例的最优解,即17,2332485665718400,0,0,0,0,0,0为独立的8个0元,即最小指派解对应的系数和为1723324856657184c c c c c c c c +

24、=2+1+1+3+1+1+2+3=14所以56482317,f f f f 为该配送区域邮路问题的奇点最优配对方案。即选择111,v v 配对,43,v v 配对,126,v v 配对,98,v v 配对,配对所得的最小和为56482317f f f f +=7(4为各个配送奇点的最短径加边 图6 加边后的最短路经Fig. 6 The shortest route after pulsing latus在邮路图中对每个配对奇点之间按照最短路径添加重复边,得到*G ,此图中已没有奇点。(5从配送中心出A 发,找出欧拉回路为:A-1v -2v -3v -10v -1v -10v -11v -12v

25、 -4v -3v -4v -5v -6v -12v -6v -7v -8v -9v -10v -11v -8v -9v -A,此回路即为该配送区域内的最短路径,总路径为55。下图为送货车的送货顺序图: 图7 送货顺序Fig.7 Distribute order模拟送货车的实际送货路线,从配送中心出发,给零售户90送货,到达1v 路口;给零售户89送货,到达2v 路口;给零售户87送货,到达3v 路口;给零售户84送货,到达10v 路口;给零售户85送货,到达1v 路口;再到10v 路口;给零售户83送货,到达11v 路口;给零售户82送货,到达12v 路口;给零售户79送货,到达4v 路口;给

26、零售户88送货,到达3v 路口,再到4v 路口;给零售户73送货,到达5v 路口;给零售户72送货,到达6v 路口;给零售户78送货,到达12v 路口,再到6v 路口;给零售户76送货,到达7v 路口;给零售户77送货,到达8v 路口;给零售户81送货,到达9v 路口;给零售户86送货,到达10v 路口,再到11v 路口;给零售户80送货,到达8v 路口,再到9v 路口;给零售户91送货,最后回配送中心。完成了对些配送区域内18位卷烟零售户的送货任务,总送货路程2+5+1+5+1+1+1+3+4+1+1+3+4+3+3+6+3+1+2+1+2+1+1=55 ,用此方法,可以求出所有配送区域内所

27、有送货车辆的最短行驶路线。3.4技术实现配送线路优化的实现借助于计算机技术,会大大提高其效率。上述聚类的实现,配送区域内优化线路的生成等关键性步骤均通过一些C+程序得以实现。涉及到数据库的一些主要表结构如下:4小结 综上所述,本文对烟草配送线路的优化问题提出了一个比较完整的解决方案。该方案具有以下优点:首先在实用性方面:一是实现了车辆的合理调度,减少不必要的出车次数。配送中心每天根据配送当天的订货量以及配送车辆的型号来决定配送车辆出动的数目。在K-MEAN 聚类分析中,按照1+订货量车载量的方法求出K 值,K 既是聚集点的个数,也是送货车辆出动的数量。如果按照30000箱的年销售量,80件的车

28、载量,11条配送线路来计算,平均每天出动的配送车辆为300002501747181220928050+=+辆,全年预计可减少出车次数(11820921275312=车次,减少送货1506人次。二是提高车辆满载率。通过出车次数的减少,必然提高每辆车的满载率,如果以每天平均8辆的出车数来计算,车辆满载率为300002509336%81220928050=,远远高于现在的配送车辆满载率300002506790%111220928050=。三是实现了配送车辆送货线路的最优化生成。通过K-MEANS 聚类算法形成配送区域、再利用指派问题求解CPP 问题得到每一个配送区域内的最优线路,使每一辆配送车辆能按

29、照优化的配送车辆行驶送货,有效缩短了行车里程,避免走重复路、回头路,同时为零售户的送货服务更及时。其次在科学性方面:一是整套解决方案科学合理,结构严谨,层层紧扣,通过四步将VRP 问题层层分解、细化,减小问题规模,得到可行解;二是在配送区域划分采用了K-MEANS 方法,并对初始聚类点的确定方法进行优化改进,使聚类结果更加合理、效率更高;三是在配送区域划分时加上工作量和车载量两个约束条件,使最终结果真正有实用价值;四是在求解配送区域内的多点最优线路问题时,将其转化CPP 问题,通过求解欧拉回路来求解最优线路;五是在求解CPP 问题时将其转化成指派问题来求解。再者在实践性方面:整套方法的每一个关

30、键性步骤均可用C 语言程序加以实现,并在上文论述中均辅以测试数据加以证实,充分论证该解决问题的方法是完全可行的,总的来说,应用上述方法对烟草物流配送线路进行优化,可以科学地规划配送线路,表名 字段1 字段2字段3字段4字段5 字段6零售户信息 客户代码 道路编号 经度纬度 聚类信息表 聚类编号 客户代码 道路信息表 道路编号 道路名称 路口1编号路口2编号道路交通等级单双行线路口信息表路口编号路口名称经度纬度使线路最优;合理地调度车辆,使满载率提高;有效地加强内部管理,使管理成本降低。对于实现“低成本、高效率、优服务”的烟草物流建设目标是一个很好的推动。参考文献1、孙焰.现代物流管理技术建模理

31、论及算法设计.上海:同济大学出版社.2004.2、高志刚,王长琼.基于GIS的多线路配送系统集成研究.武汉理工大学学报.物流科技.2005,(28:14-15.3、戢一鸣.基于GIS的现代物流系统配送算法的研究与应用.武汉:武汉理工大学学报.2004,26(5:154-156.4、李军,曹立明,王小平.基于GIS的物流配送路径计算.计算机应用与软件.2007,24(3:12-15.5、郎茂祥,胡思继.用混合遗传算法求解物流配送路径优化问题的研究.中国管理科学.2002,10(5:51-56.6、陈子侠,蒋长兵.杭烟物流送货线路的划分模式与算法研究.系统工程理论与实践.2003,(3:49-51

32、.7、Tarankilis C D,Kiranondis C T. Using a spatial decision support system for solving the vehicle routing problem J.Information &.Management,2002,39:359-375.8、Luiz S,Dalessandro S,etc.A parallel evolutionary algorithm for the vehicle routing problem with heterogeneous FleetJ.Future Generation Computer Systems,1998,14:285-292.9、乐阳,龚健雅.Dijkstra最短路径算法的一种高效率实现.武汉测绘科技大学学报.2005.10、张可明.物流系统分析.北京:清华大学出版社.2004.11、李军,郭耀煌.物流配送车辆优化调度理论与方