第29卷　第5期2005年10月武汉理工大学学报(交通科学与工程版)Jou rnal of W uhan U n iversity of T echno logy(T ran spo rtati on Science &Engineering )V o l .29　N o.5O ct .2005物流配送路径优化策略研究 收稿日期:20050514 周　程:女,27岁,硕士生,主要研究领域为物流管理周　程(湖北经济学院工商管理学院　武汉　430205)摘要:配送是物流中的核心环节,最短路径的选择决定着配送效率.从图论的角度出发,分析了经典的D ijk star 算法和F loyd 算法,并指出了它们的一些不足:D ijk star 算法随着配送点数目的增多,效率将下降;F loyd 算法主要解决有向图等.给出了一些改进的建议:针对D ijk star 算法,将交通路线图分成子图,以提高效率;对于F loyd 算法,将邻接矩阵上三角和下三角复制,能解决采用F loyd 算法解决无向图的最短路径问题.针对某物流配送公司,给出了基于改动后的F loyd 算法的程序实现,开发了一个配送路径优化决策系统.关键词:物流;配送;最优路径;D ijk star 算法;F loyd 算法中图法分类号:U 4922220　引 言随着现代社会的发展,物流、商流和资金流广泛深入影响着人们的日常生活.电子商务主要是基于互联网络的虚拟经济,而物流促使电子商务由虚转化为实.物流系统是现代社会经济系统的支柱.关键的物流活动包括:仓储、物料搬运、包装、运输等,其中配送运输是最大的物流成本之一,因此配送运输活动组织得好坏,直接影响着物流活动的成败.配送运输是指将被订购的货物用汽车或者其他运输工具从供应点送至顾客手中的活动,其间可能是从工厂等生产地仓库直接送至客户,也可能通过批发商、经销商或由配送中心、物流中心送至客户手中.配送运输[1]通常是一种短距离、小批量、高频率的运输形式.配送的目标之一就是以最小的代价,将产品从原产地(或物流配送中心)转移到规定地点.因此,对制定车辆调配计划和配送路线计划就显得非常重要了.通常,最小的代价所对应的配送路径就是最优路径.文中首先介绍在物流行业中配送问题的分类和常用路径选优算法,重点分析对比了D ijk stra 算法和F loyd 算法,结合F loyd 算法给出一种简单易行的配送优化策略,最后给出程序运行结果.1　配送问题的描述物流行业中配送优化策略研究的主要内容就是配送车辆优化调度.在物流配送过程中,影响配送运输效果的因素主要分成两种:一是动态因素,如车流量的变化、道路施工、配送客户的变动、可供调动的车辆变动等;二是静态因素,如配送客户的分布区域、道路交通网络、车辆运行限制等.各种因素相互影响,很容易造成送货不及时、配送路线选择不当.配送问题面临的一个核心难题就是求解最短路径.最短路径问题一般可分成三类:一是距离上的最优;二是经济上的最优;三是时间上的最优.配送问题抽象如下:设有一物流企业需要向n 个配送节点配送不等的货物Q i ,已知每个节点路径各自对应的权值,求最优的配送车辆搭配和各自路线最优规划,即使在相应约束条件下(如时间范围内或一次到货等),配送系统的总权值最小.本文对这个问题采用图的结构进行描述:图的顶点表示配送中心和配送点,边表示它们之间的线路联系,边赋予相应的权值(表示时间、距离、线路运况等),这样配送问题就转化为在网络图求解路线的权值最优,权值可代表距离、时间、费用或它们之间的综合因子,配送优化问题就要求在从始点到终点的所有路径中找出一条总权数为最小的路径[2,3].2　D ijk stra 算法及分析首先讨论求解单源点的最短路径问题:给定带权值有向图G 和源点V ,求V 到图中其余顶点的最短路径.如图1所示的带权有向图G 5中从V 0到其余各个顶点之间的最短路径如表1所列.图1　带权有向图G 5表1　有向图G 5中从V 0到其他顶点的最短路径始点终点最短路径路径长度V0V 1(V 0,V 1)15V 0V 2(V 0,V 1,V 2)30V 0V 3(V 0,V 3)25VV4(V 0,V 4)20 从图1中可看出从起始点V 0到顶点V 2有两条路径(V 0,V 3,V 2)和(V 0,V 1,V 2),路径(V 0,V 3,V 2)长度为35,路径(V 0,V 1,V 2)长度为30,显然路径(V 0,V 1,V 2)是V 0到V 2的最短路径.D ijk star 提出了一个按路径长度递增的次序产生最短路径的算法.首先引入一个中间辅助变量D [i ]表示当前源点V 到每个终点V i 的最短路径的长度.D [i ]的初始值为:如果源点V 到终点V i 之间有直接相连的路径,则D [i ]为这条路径的权值,否则,设定D [i ]=M A X .设D [j ]=m in{D [i ] V i ∈V } 显然D [j ]为从源点V 出发的一条最短路径,下一条最短路径的长度一定是D [j ]=m in{D [i ] V i ∈V -S }其中:S 为已经求得最短路径的终点集合.经典D ijk star 算法描述[4～6]如下.Step 1　系统初始化.假设采用带权的邻接矩阵a rcs 表示带权有向图,a rcs [i ][j ]表示弧<V i ,V j >上的权值.若顶点V i 和顶点V j 不直接相连,则a rcs [i ][j ]给定M A X (极大值).S 为已经找到从V 出发的最短路径的终点的集合,它的初始状态为空集.那么,从V 出发到图上其余各顶点(终点)V i 可能达到的最短路径长度的初值为D [i ]=a rcs [L oca te V ex (G ,V )[i ] v i ∈V ].Step 2　选择V j ,使得D [j ]=m in {D [i ] V i ∈V -S }.V j 就是当前求得的一条从V 出发的最短路径的终点.令S =S ∪{j }.Step 3　修改从V 出发到集合V -S 上任意一顶点V k 可达到的最短路径长度.如果D [j ]+a rcs [j ][k ]<D [k ],则修改D [k ]为D [k ]=D [j ]+a rcs [j ][k ].Step 4　重复Step 2和Step 3就可求得V 到图上其余各个顶点的最短路径. D ijk star 算法思路清晰,程序实现简单.但是D ijk star 算法存在三重循环,第一重循环时间复杂度为O (n ),第二和第三重循环为嵌套循环,时间复杂度为O (n 2).因此求解一顶点到另一顶点的最短路径时,采用D ijk star 算法的时间复杂度为O (n 2).当顶点n 较大时,算法的时间复杂度急剧增加,即使用带权的邻接表作为有向图的存储结构,则修改D 的时间可以减少,但由于在D 向量中选择最小分量的时间不变,所以总的时间复杂度仍然为O (n 2).这里介绍一种改进策略,主要思想是将整个带权值有向图分区划分成各个子图,这也和现代物流配送企业分区配送一致,这样人们只需要对各子图进行划分计算各自顶点的最短路径,最后将其综合决策进行处理.划分的基本原则如下:两点之间直线距离为最短几何距离,因此一般最短路径在配送起点和终点连接的直线周围.因此应该沿着连接起点和终点的直线进行划分.同时,系统还应该开辟存储结构,将已经计算好的顶点之间最短路径存储在数据库中,避免进行重复性工作.3　F loyd 算法及实现针对求解交通网络中的任意顶点之间的最短路径时,D ijk star 算法主要是求解单源点的最短路径问题.这里以每个顶点作为源点,重复运行D ijk star 算法求解,就可获得每对顶点之间的最短路径,总的时间复杂度为O (n 3).下面引入F loyd 算法求解每对顶点之间的最短路径,并给出一种简单实现的基于F loyd 算法的求解最短路径的系统.F loyd 算法仍然从带有权有向图的邻接矩阵出发求解最短路径的,经典F loyd 算法描述[4,7]如下.假设求解从顶点V i 到顶点V j 的最短路径.如果从V i 到V j 有弧,则从V i 到V j 存在一条长度为・897・武汉理工大学学报(交通科学与工程版)2005年　第29卷a rcs[i][j]的路径,该路径不一定是最短路径,尚需要进行n次试探.首先考虑路径(V i,V0,V j)是否存在(即判断弧(V i,V0)和(V0,V j)是否存在).如果存在,则比较(V i,V j)和(V i,V0,V j)的路径长度取短者为从V i到V j的中间顶点的序号不大于0的最短路径.假如在路径上再增加一个顶点V1,也就是说,如果(V i,…,V1)和(V1,…,V j)分别是当前找到的中间顶点的序号不大于1的最短路径.将它和已经能够获得的从V i到V j中间顶点序号不大于0的最短路径相比较,从中选择中间顶点的序号不大于1的最短路径之后,再次增加一个顶点V2,继续试探.依次类推.在一般情况下,若(V i,…,V k)和(V k,…,V j)分别是从顶点V i到顶点V k和从顶点V k到顶点V j的中间顶点的序号不大于k-1的最短路径,则将(V i,…,V k,…,V j)和已经得到的从V i到V j且中间顶点序号不大于k-1的最短路径相比较,其长度最短者便是从V i 到V j的中间顶点序号不大于k的最短路径.这样,在经历n次比较后,最后求得V i到V j的最短路径,按照相同的方法可获取所有顶点相互间的最短路径.显然经典的F loyd算法主要针对带权有向图而言,对于无向图,它并没有考虑,其实只需要稍微改进就可以实用于无向图,采取的策略为将邻接矩阵上三角和下三角复制,从而每条边就成为双通的路径,采用原F loyd算法就可求解任意顶点间的最短路径.F loyd算法的程序如下.P rivate Functi on F loyd(begin A s Integer)　Fo r i=0To begin　Fo r j=0To beginIf i<>j T hena(i,j)=graph(i,j)E lsea(i,j)=0End IfIf i<>j A nd a(i,j)<m ax T henpat(i,j)=iE lsepat(i,j)=0End IfN ext j　N ext iFo r k=0To beginFo r i=0To beginFo r j=0To beginIf a(i,k)+a(k,j)<a(i,j)T hen　a(i,j)=a(i,k)+a(k,j)　pat(i,j)=pat(k,j)End IfN ext jN ext iN ext kEnd Functi on针对华中地区某物流公司配送方面存在着下列问题:车辆运输线路优化不合理,主要实行单车配送,车辆经常不能够满载,运力浪费严重,没有实行协同送货等问题.结合将邻接矩阵上三角和下三角权值复制改进的F loyd开发一个中小物流企业配送系统.配送系统整体框架如图2所示.图2　配送系统功能模块从企业运行成本的角度设想,站点录入机制采用模拟的电子地图而没有采用地理信息系统,将与企业有业务往来的配送点通过录入界面录入并存储于数据库中.站点录入界面主要是生成各个配送点在模拟电子地图上的具体坐标,即标定各个配送点的位置,而站站录入界面主要是生成每个配送点及配送中心之间的路径关联,也给定相应的权值.采用F loyd算法可获得任意顶点之间的最短路径线路.显然系统将录入的电子地图上任意顶点之间的最短路径都存储在数据库中,这样就避免了重复性的工作,提高了系统效率.给出一个配送任务:从配送中心0送1单位的货物到配送点6,送2单位货物到5,送1单位货物到4,送0.5单位货物到3,选择载重量为4.5单位的车辆,配送系统运行主界面如图3所示.车辆调度策略是需要一辆载重为4.5t的车完成配送任务,最优行车路线为(0,12,6,5,4,3,0).图3　配送系统运行界面・997・　第5期周　程:物流配送路径优化策略研究参考文献1　苏一丹,李　桂.电子商务物流管理信息系统中最优(佳)径算法的研究.计算机工程与应用,2002(18):182～1832　李腊元,李春林.计算机网络技术.第2版.北京:国防工业出版社,2004.185～1903　李春林.Q oS 多播路由技术进展.武汉理工大学学报(交通科学与工程版),2001,25(4):386～3894　朱永升,韩伯棠,夏　平.交通限制条件下城市物流配送路线优化选择.武汉理工大学学报(交通科学与工程版),2004,28(3):391～3945　孙毅彪,王程铭.基于有向图规划的最佳物流路径策略分析及应用.运筹与管理,2003,12(2):110～1136　黄伟东,万义玲.公路网最佳路径算法的研究.南昌大学学报(工科版),2001,23(1):48～527　周炳生.F loyd 算法的一个通用程序及在图论中的应用.杭州应用工程技术学院学报,1999,11(3):1～9R esearch on Op ti m ize M ethod of L ogistics D elivery Rou teZhou Cheng(S chool of B usiness A dm in istra tion ,H ubei U n iversity of E cono m ics ,W hhan 430205)AbstractSince the delivery is the key po in t of logistics ,sho rtest p ath decisi on is essen tial fo r the efficiencyof delivery .C lassical D ijk star algo rithm and F loyd algo rithm are analyzed from the po in t of view of Graph T heo ry .It po in ts ou t these tw o algo rithm s deficiencies such as :D ijk star algo rithm efficiency w ill drop fast w ith the num ber of delivery po in t increasing ,F loyd algo rithm m ain ly so lves the directi on grap h p rob lem and no t fit fo r non 2directi on grap h p rob lem .T hen som e i m p rovem en t m ethods are b rough t fo r w ard such as :fo r D ijk star algo rithm ,the w ho le graph is divided in to som e ch ild grap h and then it w ill increase the efficiency ,fo r F loyd algo rithm ,the abu t m atrix is m odified to an equal m atrix and then it so lves non 2directi on grap h p rob lem based on F loyd algo rithm .F inally ,an exam p le of logistics delivery rou te op ti m izati on based on F loyd algo rithm is given .Key words :logistics ;delivery ;op ti m izati on m ethod ;dijk star algo rithm ;floyd algo rithm(上接第787页)R esearch on Concrete A ppearance D efect Ex tracti on and R ecogn iti on Based on M atrix P rinci pal Com ponen ts A nalysisChen X i aoj i a Zhou X i angjun L iY icheng (S chool of T ransp orta tion ,W U T ,W uhan 430063)AbstractT h is p ap er discu sses a new m ethod ,w h ich can realize to in sp ect defects and recogn ize vari ou s defect typ es on concrete su rface by techn ique of digital i m age p rocessing and pattern recogn iti on .T he p ap er em phasizes on research of featu re ex tracti on and neu ral netw o rk s classifier design ,w h ich m u st have credib ility and availab ility to m eet the need .T he m atrix p rinci pal com ponen ts analysis (M A T PCA )m ethod ,w h ich is an effective m ethod of analyzing data in statistics ,is w idely u sed in the data featu re ex tracti on and data com p ressi on fo r h igher di m en si onal data space can be tran sfo r m ed in to low er di m en si onal featu re space by M A T PCA m ethod .In th is pap er ,the i m age p ixel featu re ex tracted by M A T PCA m ethod ,w h ich is realized by the too l of M A TLAB ,can m eet the need the recogn iti onlayer w ell.In the recogn iti on layer ,the B P neu ral net w o rk m ethod is discu ssed .T he recogn iti on resu lts show that it is effective .Key words :m atrix p rinci pal com ponen ts analysis ;featu re ex tracti on ;concrete ;ex ternal appearance ;neu ral netw o rk・008・武汉理工大学学报(交通科学与工程版)2005年　第29卷。