层状物流系统的车辆配备及各车辆最优路径探讨

朱士东南京河海大学交通工程zhushidon@sina.
com摘要:本文基于当前物流系统化的特点,综合考虑效益,时间等因素,对各层物流中心的选址及各中心内最优车辆配备及各车辆路径的确定,作了简要的论述.
由中国邮递员问题逐步推广,先是单中心多邮递员问题,后推至层次状物流的车辆配备问题及各车辆的路径问题,在每一环节均简略地论述了设计思想,每一环节均在计算机内通过不断的迭代,比较,最后选择理论最佳方案,通过应用,反馈,作出调整.
关键词:资源车辆最优路径中国邮递员问题物流1.
引言在近年来物流服务外包趋势的影响下,物流配送企业与生产和分销实体的联系更加紧密,物流配送服务水平往往直接决定了整条供应链面向客户的回应速度.
物流在现代社会中的地位举足轻重,而覆盖性很广的物流随着经济的发展会成为主流,又由于市场竞争激烈化后在很大程度上体现为时间与利润间的竞争,这就决定了层状物流系统涉及到的内容很广泛,但主要有这样几个方面:(1)子物流中心的选址问题;(2)各物流中心车辆的最优配备;(3)各车辆所走的最优路线问题.
综合考虑经济、时间等因素,忽略次要因素(忽略车辆自身的载重,空间利用等问题)、抓住主要因素而做决策.
因此一个物流系统的设立应以经济效益为目标,用系统学理论和系统工程的方法,综合考虑各种因素.
(1)现在只考虑三层之间的两层的车辆配备问题2.
1物流中心的选址问题物流中心选址是物流系统中具有战略意义的投资决策问题,对整个系统的物流合理化和商品流通的社会效益有着决定性的影响.
但由于商品资源分布、需求状况、运输条件和自然条件等因素的影响,使得在同一区域内的不同地方建立物流中心,整个物流系统和全社会的经济效益是不同的.
因此,物流中心的位置应进行科学的研究与决策.
(2)物流中心的位置是物流网络内货物运往最终消费者过程中的临时经过点.
为了便于说明问题,假定特定区域为一个城市,可见要在各行政区内设立子物流中心.
解决http://www.
paper.
edu.
cn这个问题可利用经典物流中心算法——重心法.
重心法亦称网格法或精确重心法,其利用物理学中对一个二维封闭图形求解重心的原理.
假设条件是:存在这样一系列点分别代表生产地和需求地,各自有一定量的货物需要以一定的运输费率运向位置待定的物流中心或从物流中心运出.
MinC=∑iViMiDiC——总成本Vi——i点的产量或销量Mi——i点运输费率Di——待运物流中心的距离(Xo,Yo)到i(Xi,Yi)的折算距离,综合节点阻抗和路阻函数Di=((Xi-X0)^2+(Yi-Y0)^2)^0.
5将②代入①可使C最小的Xo,Yo.
为了精确计算C,应用迭代法ЭC/ЭX0=∑iViMi(Xi-X0)/Di=0ЭC/ЭY0=∑iViMi(Yi-Y0)/Di=0由上可得物流中心的位置坐标(Xc,Yc):Xc=∑iViMiXi/Di/∑iViMi/DiYc=∑iViMiYi/Di/∑iViMi/Di此法有其局限性即易造成选地不精确,但简便实用.
目前GIS在物流中心的选址中有所应用,但是与传统的重心法相比代价自然高.
(2)2.
2各中心最优车辆配备及各车路径的确定为了便于说明问题,现以报刊发行为例,一个城市中报刊印刷点一般只有一个(看作总部),印刷完成后从总部出发到各子中心(这里有总部车辆配备问题),再由各子中心运到各销售点(各子中心的车辆配备问题).
整个过程以在规定的时间T内(装卸货物的过程时间已经考虑)完成表示经济目的达到(快速).
解决这个问题需要不停的迭代,因此只有用计算机来解决这个问题.
利用Floyd算法可得出各子中心内的各销售点及中心点之间任意两点的距离(或时间,以下为表达方便一律用距离)及路径,亦可得出各子中心与总部构成的系统中任意两点间的最短距离及路径.
Floyd算法的基本思想是递推地产生一个矩阵序列A0,A1,A2,A3,……An,其中A0为给定的代价邻接矩阵,Ak(i,j)(1≤i,j≤n)表示是从点i到j的中间点序号不大于k的最短路径长度.
由于给定的顶点序号不大于n,所以An(i,j)就表示了从i到j的最短路径的长度.
若从i到j的路径没有中间顶点,则对于1≤k≤n有Ak(i,j)=An(i,j)=cost(i,j).
递推地产生A0,A1,A2,A3,……An的过程就是逐步容许越来越多的顶点作为路径的中间顶点,直至找到所有容许作为中间顶点的顶点,算法结束,最短路径也就出来了.
http://www.
paper.
edu.
cn假设已求出Ak-1(i,j)(1≤i,j≤n),这时可分两种情况考虑:1若从顶点i到j的最短路径不经过k,那么由Ak(i,j)的定义可知,从i到j的中间顶点不大于k的最短路径长度就是前一轮形成的数组Ak-1(i,k),即Ak(i,j)=Ak-1(i,j)2若从顶点i到j的最短路径经过k,则路径由i--k,k--j两条组成,由于Ak-1(i,k)和Ak-1(k,j)分别表示i--k和k--j的中间顶点不大于(k-1)的最短路径的长度.
若Ak-1(i,k)+Ak-1(k,j)∈E(G),wij是上的权cost(i,j)=0i=j∞i≠j不在E(G)中在计算机中实现以上的程序框图如(1)图所示:http://www.
paper.
edu.
cn(1)图Floyd算法2.
3通过不断的循环在所要研究的特定大区域内导出整个系统的最优车辆数及各辆车的最优路径.
在利用Floyd的算法得出了最短路距离及最短路径的基础上,利用中国邮递员问题的推广来解决最佳车辆配备问题.
http://www.
paper.
edu.
cn2.
3.
1中国邮递员问题(3)中国邮递员问题的内容是用n来表示特定区域内的n个地方,只有一个邮递员的情况下,如何从一个点出发,在所用时间或路程最短的情况下,经过所以的点并回到出发点.
邮递员从一个点出发必须经过n-1个点,现在令k=1,2,3,4,…n-1,设在第k段邮递员到达点i,并途中经过的点的集合为s,状态Xk为(s,i),决策uk为他前往下一站j,阶段指标为dij,最优值函数fk(s,i)为右1出发经过k个点的集合s到达点i的最短距离,满足fk(s,j)=min[dij+fk-1(s,j)]S∈Ni={2,3,4……,i-1,i,i+1……n},s=ki=2,3,4,……n,k=1,2,3……n-1式中s满足s中点的数量,上面方程是动态规划前向算法的递推方程,始端条件f0(,i)=d1ii=2,3,4,……n利用上二式,计算出fn-1(N,1),n={2,3,4……n},即为全程最短距离,同时可得到最优策略,即最优行走路线.
其程序实现时可以从任意点出发,具有更广泛意义上的应用,利用Floyd算法可画出程序简如(2)图所示.
程序的关键是解决如何邮递员到达一个点时如何来选择下一个目标,解决的方法是不停地寻找最近的点,并最好不是已标号的点,这实际上较符合实际的情况,不可能走很多重复的路程还是最优路径的.
解决这个问题之后,就可以为下面的多个邮递员时问题的解决提供了前提条件.
2.
3.
2多邮递员问题在现实生活中,单个邮递员问题有一定的应用局限性,毕竟只有一个邮递员,未考虑有多个邮递员时的更普遍的情况.
现在暂时把这个问题命名为多邮递员问题.
基本思想是先利用Floyd算法,然后在一出发点有多个邮递员,在每个点都到的前提下所用时间或路程最少,尽量不走重复路.
以上两个问题(Floyd问题和中国邮递员问题)都是些成熟的理论,那么解决现在这个问题则是见仁见智,只要配备后有良好的反馈,就是好的解决方案.
对于这个问题,利用计算机程序不停地迭代,通过比较各个方案的结果来判断其好坏.
其程序设计简图如(3)图所示:http://www.
paper.
edu.
cn(2)图中国邮递员问题简图上关键的地方是如何来判断各车辆的行走路线,本文的思想是在当前各车的位置上,每一车辆逐个来寻最优路线,每一车辆在寻优之前要判断与当前位置各点的标号情况,然后来作出决策.
本程序要完美地实现预想的效果,在具体实现时还得考虑很多因素的影响,也就是说还得到实际运行情况的论证.
2.
3.
3层次物流的车辆配备问题在以上几个问题依次解决之后现在来看看本文开始提出的问题,在一个给定的层状系统中,如何来配备车辆使得整个系统的车辆数最少(可理解为最为经济),所用的时间或所行的路程最少,及它们的各自的最优路径.
设计思路:通过不断的迭代来探询在各不同的车辆配备的情况下其最优函数的值的变化情况(最优情况可表http://www.
paper.
edu.
cn示为F=∑iKiCi(Di)/Di.
,Ki表示矫正系数,Di表示第i辆车所行距离,Ci(Di)表示第i辆车所消耗的费用与距离之间的关系)来选取最佳的车辆配备方案.
系统分层越多,则迭代次数越多.
上面的设计简图只是产生一个F值的算法,若要在多个数据中来比较则还需要多输入几个不同的初始条件来产生不同的方案(4),而条件输入则要从已有的资料中来获得,资料的准确程度对选出的方案运行的准确程度有很大影响,调查这样的资料的活动需要投入很大的资金,各物流公司在决定投入之前得作可行性报告,看是否能收回投资.
其部分设计简如(4)图所示:输入点数输入任意两点间的路程cost(i,j)调用floyd算法输入起点v1及拥有车辆数与当前出发点相连的点无标号的点,第i辆车寻距离最近的未标号的点当前出发点第i辆车寻与其最近的位标号的点标号所经过路径减去重复路径的后加值标号,所经路径加上一较大数值i>ni=i+1判断是否标号i=1输出结束否是是否(3)图多邮递员问题http://www.
paper.
edu.
cn输入数据,分区数N总部车辆数为N1调用多邮递员算法得出到各子中心的时间tiMax{ti}>最大承受时间Tj=1,n(j)=1等区间调用多邮递员算法得出到各子中心的时间tijti+tij>Tj=j+1j>N输出结束n(j)=n(j)+1n(j)>分区车辆上限mn1=n1+1n1=n1+1否否是否是否是是(4)层次物流的车辆配备问题3.
结语:由于物流中心日常配送作业中意外在所难免,而这些事故往往直接影响后续作业的安排,本文中未予考虑.
本文也忽略车辆自身的载重,空间利用等问题,而这些问题也是在配送问http://www.
paper.
edu.
cn题中必须考虑的问题,这些问题可以用遗传算法来解决,限于时间和篇幅,在这里不在熬述.
参考文献(1)孔繁路,王鹏飞,初探遗产算法在配送中心作业优化的应用,现代物流11期,2004(2)李长江,《物流中心设计与运作》【M】北京:中国物资出版社,2002(3)马振华,《运筹与最优化理论卷》,北京,清华大学出版社,1998(4)蔡子经,施伯乐,《数据结构教程》,上海,复旦大学出版社,1994DiscussiononVehicleCollocatingAndEachRouteofLayerLogisticsSystemZhuShidongTransportationDepartment,NanJingHohaiuniversityAbstractThearticlebrieflydiscusseshowtofixaddressesofeverylayeroflogisticscenterandthebestvehiclenumberinitandenchroute,integratingfactorsofbenefit,timeandsoon,basedoncurrentsystematism.
StartingfromtheChinamailcarrierproblem,thearticlediscussesonlyonecarrier,andthenextendstodiscusstheproblemoffixingonthebestvehiclenumberineverylayerandenchroute.
Ineverytacheitshortlytreatsitsdesigningthinking,throughceaselesslyalternatingandcomparing,atlastchoosesthebestscheme.
Rectifyitafterapplyingandfeedingback.
Keywords:resourcevehiclethebestroutetheproblemofChinesemailcarrierlogisticshttp://www.
paper.
edu.
cn