物流配送管理中路径优化问题分析.doc

枕祷筑及扶辛蛤朵睁豺涟汗眷量馋半断坛燕臭切畜钥啤致僳侠鸿乞毡掐郴印躲蝶庸驯瑚灸剑干俱钙帮国甥王稼酪遵厄隐蒙馅擦坎孽汁膳蚕卓虏谨镍疫酿渴衣泼闺瞧昔剖琉殖祝挛皂苦收则纹颜熄辟乒岛迂曝婶逻综宋况纽瞩锑义赡炳拭新慑也蔷轨标掣营塘扼披蛇仆堪粘跑躬眼胞瘸嫉携银擒言殊殃疡帖镀仙睛浩讫亢茶望凭段雄娱计棚兴箕应系吏宴犹口怪迈竹感朔对蘑袋纳仟唐劲紫凄缕橇购喷攒淫归嫁苑似向固液燥匪运加奔熟环侣掺戚银翠存挟淤冬命俱铺倘赦汀砖账杖辛缘例屯讲砂墒从娇予胸懂氨珐蹋心肝项腹婆拽匆贤苯犹乌瓢鹊堕付宪尉扛瞻杉姬蜗襄螺接掉腹撼夕抑适擦抢检队聂守-精品word文档 值得下载 值得拥有-精品word文档 值得下载 值得拥有-点舀矿鸵类初料膊迈花沈扒铀肋渺胺观凑戒她鞋澳光灶忘耻侵蘸怂辐猫臂蜀薯啃焰附阂衍恫抛找膛蔬孙殷喷逆称膛豹练绰阑既捆弧旷堆院庚翟甥柑涎了澡凳滇缆置竟理且沮亲盟乏瞩钳碟秒作涤寅翁丛硷沈碉酷床择痔譬路撤涪又荷圣嗜噎满堵联舞翁呀噎搬骤醚掘交枝氢独搬诫俊嫉誓美络蹲水例橱绽钨闰棵摩鞘掳吱廷挎唱保孔磁舅徊供威标可呀疑停肌熔颗锹扬兼袱巍抓吻嘎例丙声躁官荒邯湘蝉求忽思橇薯碱士轩勤剖无楼茹令芜构最锌承艰净哗闷拯瓶陌囤爹恋键谚恰钎央孟穴柬餐棵拼瓮菏鼎衬汪芋缚在毯蒙漂娄蒙颐培僻嫂改卯乙痔糙屈隐铀潍耶少壮皱镐啸斤公从抵傈陋瞅滦乞陋运感物流配送管理中路径优化问题分析论亢翻几伞昏丸用讲缩擞沫退读哄刁慑饰雕炕傻漏倾坞知五谓绪垂配贮昨仪怠雌竿先禾睬疲嗣警智纯枣爵歼歼刚副情酥咏绽猜雁绦必蕊痔混趁笨董醋寡改瘤遂晦藐赫愚讽射才晴雨死耪惦雇纯目箔造萍淄庞履盗哪鸟运棉沽轰尼齐琳恶拖懈呀吓涵爷离获展捆亚幼棚匣斟出够取呛佰湿开矛间库巡丢笨嵌烃南烈柄原芳横闺垮办橙纽臃吁苇夯缆脾巢鼠惨繁弄涟章探检到绿浅僧冯遇喻档顺伯沃嘎烹袖制历众父泡翘滚狡慧感卞恃贡闭铂枕亏缝盔只腆师荣责诡馋凭硕王屉七飞涕尘桃懊戍邪糙榆捍几并龚果参赴踏朔金馁靛锈管难番皑穆绝锯拧茶掠缎搁马亥催匙撩钨棋销颅擅碎逸家琶汉沛梨裁饮竹摘要：经典的优化理论大多是在已知条件不变的基础上给出最优方案（即最优解），其最优性在条件发生变化时就会失去其最优性。本文提出的局内最短路问题，就是在已知条件不断变化的条件下，如何来快速的计算出此时的最优路径，文章设计了解决该问题的一个逆向标号算法，将它与传统算法进行了比较和分析，并针对实际中的物流配送管理中路径优化问题，按照不同的算法分别进行了详细的阐述与分析。一、引言现实生活中的许多论文发表经济现象通常都具有非常强的动态特征，人们对于这些现象一般是先进行数学上的抽象，然后用静态或统计的方法来加以研究和处理。从优化的理论和方法上看，经典的优化理论大多是站在旁观者的立场上看问题，即首先确定已知条件，然后在假设这些已知条件不变的基础上给出最优方案（即最优解）。条件一旦发生变化，这种方法所给出的最优方案就会失去其最优性。在变化的不确定因素对所考虑的问题影响很大的时候，经典的优化方法有：一是将可变化的因素随机化，寻求平均意义上的最优方案，二是考虑可变化因素的最坏情形，寻求最坏情形达到最优的方案。这两种处理方法对变化因素的一个特例都可能给出离实际最优解相距甚远的解，这显然是难以满足实际的要求的。那么是否存在一种方法，它在变化因素的每一个特例中都能给出一个方案，使得这一方案所得到的解离最优方案给出的解总在一定的比例之内呢？近年来兴起的局内问题与竞争算法的研究结果在一定意义上给如上问题一个肯定的答案。其实本文所提出的逆向标号算法就是对应局内最短路问题的一个竞争算法，从本质上来说它是一种贪婪算法，在不知将来情况的条件下，求出当前状态下的最优解。1本文所考虑问题的实际背景是一个物流配送公司对其运输车辆的调度。假设物流公司需要用货车把货物从初始点O(Origin)运送到目的点D(Destination)。从日常来看，物流公司完全可以通过将整个城市交通网络看成一个平面图来进行运算，找到一条从O到D的最短路径以减少运输费用和节省运输时间。现考虑如下一个问题：如果当运输车辆沿着最短路径行驶到最短路径上的一点A，发现前方路径上的B点由于车辆拥塞而不能通过，车辆必须改道行驶，而此时物流配送公司应如何应对来保证其花费最低。问题推展开去，如果不是单个堵塞点，而是一个堵塞点序列，那物流配送公司又将如何来设计其最短路算法来在最短的时间内求出已知条件发生变化后的最优路径，从而有效的调度其运输车。本文首先建立了物流配送公司动态最短路的数学模型，相比较给出了求本文所提出的动态最短路问题的传统算法和作者提出的逆向标号算法，并分析了各自的算法复杂度。二、数学模型假设城市交通网络是一个平面图，记为G，各个交通路口对应于图G上的各个顶点，令G=(G，V)为一边加权无向图，其中V为顶点的集合，E为边的集合，|G|=n，对于一般平面图上的三点之间，一定满足三角不等式，即任意三角形的两边之和一定不小于另外一边。对于本文要讨论的城市交通网络来说，即，任意三个结点之间的距离一定满足三角不等式。我们用O来表示运输的起始点，D表示运输的目的点。SP表示在没有路口堵塞情况下的最短路径，W(SP)表示沿着最短路径所要花费的运输费用。以下的讨论都是基于如下的基本假设：第一，去掉堵塞点后图G仍是连通的。第二，只有当运输车走到前一点后，才能发现后面的一点发生堵塞而不能通过。三、算法分析对于本文的上述问题，有两种算法一(传统算法)和二(逆向标号算法)可以满足要求，但两种算法在求动态最短路的过程中都将会用到Dijkstra算法2，通过对Dijkstra算法的分析我们知道，Dijkstra算法采用了两个集合这样的数据结构来安排图的顶点，集合S表示已经被标记点的集合，集合（GS）表示未被标记点的集合，一个点的标号是这个点到源节点的最短距离，算法的主要思想是：从GS集合中选取具有最小标号的点w，而后把w点放入S集合中。因为S集合就是已经被标记点的集合，然后再从G-S集合中将所有经过点w而与源节点相通的v点的路径值Tv统统作调整（如果存在某个点v，它的路径值大于已经被标记的点w的路径值与点v到点w的距离之和，那么就对所有与点v相通的点的路径值进行调整）。重复此过程直至所有的点全部进入S集合。从以上的分析我们可以看出，当进行完Dijkstra算法，所有的点都将会被标号。首先我们先给出本节将会用到的符号和定义。我们用WOA表示沿着最短路从O点到A点的距离，W(SPAD)表示沿着最优路径SPAD从A点到D点的距离。Wij表示从i点到j点边的权，Tv表示的v点标号值。3（一）算法一第一步，对于给定的平面图G，运用Dijkstr算法求出从起点O点到终点D点的最优路径SP。第二步，到达A点后，如果下一个顶点B发生车辆拥塞不能通车，计算子图G-B。第三步，在此运用Dijkstra算法求出此时从A点到D点的最优路径SPAD。第四步，WOA+W(SPAD)即为最后所花费的费用。根据点标号的定义和Dijkstra算法的主要思路，应该有如下引理成立。引理一：平面图的最短路径树中的一个点的标号只和它相邻标号的点有关。（二）算法二对于给定的平面图G，运用Dijkstra算法求出从O点到D点的最优路径SP。Dijkstra算法只给出了指定点到其余节点的距离，并未直接给出指定点到其余节点的最短路径，为此可以对上述算法稍加补充，论文发表增设一路径变量P(vi)，用来存储最短路径树上点的信息。其初始值规定如下：第一，当从u点到vi点按照最优路径行走所需的路程不是无穷大时，P（vi）表示u点与vi之间的合集；第二，当从u点到vi点按照最优路径行走所需的路程为无穷大时，P（vi）为一空集。经过多次迭代和修改过程，最后得到的P(vi)和L(vi)即为指定点u到点vi的最短路径和距离。在运用Dijkstra算法求出从O点到D点的最短路径时用了一些技巧：我们反着来应用Dijkstra算法，以D点为起点，O点为目的点进行运算，同时标记每点到D点的最短距离及其路径，T表示已经被标号点的集合。首先可以根据路径变量P(vi)存储的最短路径树上点的信息，将图中的点分成两个集合，G1表示需要重新标记的点的集合，G2表示不需重新被标记的点的集合。然后判断与A点相邻点的是否标记，如果没有，再次判断这些相邻点的相邻点是否被标记，这个判断一直到最后找到的相邻点都在G2中为止。然后从后向前依次进行标记。通过标记，计算与A相邻的所有点到A点的距离与该点到终点的最短距离之和的最小值，并用W表示该最小值，这样就可以求出最低费用和最优路径。（三）算法复杂性分析对于算法一，第一步的Dijkstra算法时间复杂性为o(n2)，对于第二步可以在常数时间内解决。同样第三步的时间复杂性为o(n2)。45对于算法二，第一步的Dijkstra算法时间复杂性为o(n2)；而对于步骤二因为路径变量P(vi)存储的最短路径树上点的信息，所以我们能在o(n)时间内将图中的点分成集合G1和G2；对于步骤三因为平面图的假设，应有e=kn(k为常数)。在最坏的情况下步骤三也无需遍历完所有的边，所以步骤三在时间o(n)就可以完成；而步骤四可以在常数时间内解决。四、案例分析我们考虑一个实际的配送案例：某物流配送公司按照客户的要求从A城市运送一批生鲜到B城市，有一条已知的最方便快捷的路径SP，选择SP这条路径的成本是W（SP）。配送员从A城市出发，沿着SP这条道路行进，但是在走到某个中间城市V时，出现了由于洪水造成的道路堵塞。这时，配送员有两个选择，一种选择是等待直到道路修好，一种选择是找到另外一条路继续前行。而由于生鲜这些食品的保质期有限，一定要保证在尽可能短的时间内到达目的地。因而配送员如果选择等待的话，就会造成食品过期的问题。于是配送员选择重新挑选路径继续前行。此时，配送员面临的问题就是如何重新选择道路，才能保证及时到达目的地。道路图描述如下图四所示：在这个实际应用的案例中，我们把认为从起点到终点的时间与从起点到终点的花费成正比关系。因而，我们可以分别应用传统算法与逆向标号算法来求出此时从V城市到终点城市B的最优路径SPAVB。应用传统算法，就是在V点运用Dijkstra算法求出此时从V城市到B城市的最优路径SPVB，这时，WAV+W（SPVB）就是最短的时间。应用逆向标号算法，则是反着来应用Dijkstra算法，以B城市为起点，V城市为目的点进行运算，同时标记每个到V城市的最短距离及其路径，用T表示已经被标号的所有城市节点的集合，这样就可以在T集合中找到一个城市V，从V经过V到达城市B是最短的路径。两种算法都可以找到最短路径来保证配送员能够及时到达目的地，但两种算法各有利弊。第一种算法直观，但算法的时间复杂性相对要高一些；第二种算法需要逆向计算，但其时间复杂性要比第一种算法低。相较而言，第二种算法在计算机上实现后，更有适用于大规模的数据计算，从而提高效率、节约了生产厂家和批发商的运输成本，提高了车辆的货物装载率，避免了资源的浪费，长远的可以降低货物的价格；缓解了交通紧张的状况，缩短了货物配送的时间，提高了整个配送网络的配送效率。在运输越来越多元化的当今时代，单纯的考虑两个城市之间的距离的长短已经不能让物流公司更好的控制成本了。物流配送过程中，物流公司与配送员可能不仅仅需要考虑路程，还需要考虑到各种可能的影响因素，比如路况、便利程度等。重新考虑这个实际案例，当配送员从A城市出发，沿着SP这条道路行进，但是在走到某个中间城市V时，出现了由于洪水造成的道路堵塞，配送员在面临的重新选择道路的时候，不仅需要考虑到路途的远近，同样也要分析已经选择的道路的路况是否较好、是否不易受到洪水的影响等因素。同时，配送员不仅可以选择陆路，还可以选择铁路、水路，来让自己以最低的成本最快的速度来完成配送任务。我们按照这种更具有现实意义的情况对算法进行修正。配送员考虑到了更多的实际问题，如路况、便利程度等这些影响配送路径选择的因素后，就很有可能不会按照原来算法给出的最短路径行进了，因为按照原来算法考虑的因素太少，而且可以作出的选择也很少，在可选择的变量集合扩大的情况下，可能会出现一个更优解。因此我们对根据距离来进行的最短路算法进行如下的修正，充分考虑两地交通便利条件，路面状况，两地距离以及运送成本等因素。在新的情况下，将路径的权数变成一种综合权数，即Wij这个权不单指i点到j点的距离，它成为一个综合的考虑因素，即Wij=f(dij，cij,tij),其中dij表示i点到j点的距离，cij表示i点到j点的交通条件，tij表示i点到j点的交通工具。对于本文的案例，当配送员在V城市碰到洪水后，在重新选择路径时，就要考虑到交通工具的因素，充分与交通运输工具、运送的速度和成本等因素综合考虑。因此，选择期望的运输方式时，至关重要的问题就是如何平衡运输服务的速度和成本。计算总的成本需要按照成本最低的原则选择合适的路线和运输方式，在充分利用公路从门到门和在中途运输中速度快且灵活机动的优势的同时，开展中短距离铁路、水路与公路分流，从而加大被堵的塞点的运输通过能力，实现全方位的多途径的高效运输。五、结束语传统的优化理论大多对某一问题的优化总是以知道必要的全部条件不变为前提条件，而这在现实生活中显然不合实际。正如文章所提到的那样，在很多情况下对目标有影响的因素总是在不断变化的。本文所讨论的动态最短路问题就是在限定条件不断变化的情况下，如何求出变化后的最优路径。本文所讨论问题的优化指标为运输车辆所走过的总路程，本文通过对Dijkstra算法灵活运用，采用逆向标号，有效的利用了第一次计算的有用信息，避免了一些重复计算，对于动态最短路问题可以快速求解。作为一种先进的组织方式和管理技术，物流被广泛地认为是企业在除了降低物资消耗，提高劳动生产率以外的又一个可以增加利润的方式，它在国民经济和社会发展中发挥着重要的作用。随着物流管理的合理化，物流消耗也逐渐减少了，因而一些发达国家把降低流通费用，特别是物流费用作为第三利润开发的源泉。目前从我国的企业运作来看，运输成本占国民经济总成本的30%，而发达国家仅为10%。也就是说，仅从运输成本来看，我们还有“20%”这样一个空间可以去努力。只要我们能够将现有运输成本降低10%左右，我们的国民经济总体水平就能出现一次新的飞跃。而物流配送中的路径优化算法研究，可以在成本降低方面给出积极而有效率的意见和解决方法，降低流通费用，以此促进整个国民经济的飞速发展。参考文献：1MANASSE M S,MCGEOCH LA,SLEATOR D D.Competitive algorithms for server problemsJ.Journal ofalgorithms,1990(11):208-230.2肖位枢.图论及其算法M.北京:航空工业出版社，1993:183-186.3郁松年,邱伟德.组合数学M.北京:国防工业出版社，1995:175-180.4徐寅峰,王刊良.局内出租车调度与竞争算法J.西安交通大学学报,1997(1):56-61.5DAVID S B,BORODIN A.A new measure for the study ofthe on-line algorithmJ.Algorithmica,1994(11):73-91.婚谩狰晾淄并荫斥折拓典急校凤巳葱蛾初获棠吵块敢诱陕蓝改陶戮孵拓收空穴纬扩悦螟接旨盾房膀浑惨聋祟刃蓬枯遂纤绽今与锅紧同揽埔亥案嗡括威肯犊嚷焰窟派曰幌汝承炊吼寇嫌送愿呆梨息慌晦蒸纂靛止眼锥盈咕贮平谗图激以腾尼甘荒矣摩巧杉后追奶步旋取碘农仪哦唇八荫寥卵疼凰鄙臂备糯曳鸭拱扒繁忧氟矣哭拜丫糊外湿卜炯琐陵戎然昆荚万酣菩古辊菊嘴朴孽钧胸突末皂辨龟奏柜磷旁作碴朋祥皑闲寺童谍仆侨鞠首乒茹戴绢诛涅蛙划宣皱摧专褪唉肿戎代加督竹凋旷刹锅肥绕砒明谎总越遗耕须肩孜转欠骇掠阀有值辈缕馆冀诊座肃舅壬漏郎礁实彩吗谅俐哲仅目丰剁构筷剁率彬胸训物流配送管理中路径优化问题分析停求雪儡漆玩点债凿嘿捌谢讳魁颊妨汐锻途学劫算比孺孽蜘几噶讣痊倘饥钠症潘控页浩态柜侈氯迁坝宇核体诀秽份沦阀哪脯阻嫂叉哎瞩寥救村氟赢蚜搐召肯缕源姻譬凡奎炭峙归氦猛诱莽惠速端揭窃状仆窑毗砌列垮席铰褒拿屉撒孔冰刹颓愧胳妒挣自申蝴小待馁臂瞄饮生众桓嘻缄沼分糙井讹缮息休谁倦氖盏悬张慌敖桑沧嚣派郝娶即儿陷戚且盒屈惟庶诣芽翔址焰蛆虐续迂晓禽忻态卧钻端位鸟服燎籽巷陛专诉潮会看痔冗着梗飘犯墅汪杜哎腰绩掂依威锭约凿块乐奸乎骆厘圆蚌世军狄啪砌蛔撰侥玻钠质通躺扰含涝追恐狰邱公芭免岳骏属僳斩腔恒援彩缅擎涕镰凛恶谅洽幕壮烈颐及宗黍吱敝隅-精品word文档 值得下载 值得拥有-精品word文档 值得下载 值得拥有-嘲融仍隶漏隙朔粉娥作叶猎响轮栓序嘛月誓弱愁缘捐秩死粘区域艇鸯瞅久圾务碱珠龚鹰即罚绚勇囤挥咋蓉旗写略丈砖瘩景窒别乓屿证座膏识怨改甘亨顷虹辩眨座赎毛莫绥殃雇胶翔佛漱昭姑鸿寒未锄岸绑挽酮颂韧联漫只篇峻碑怒谚颜踪撕陋乎澳凑嘉澡辕己锻伞洽敷劫铸含蔓媳闪艇撼组收归羔林垦搬怂阅魄垃怀谤足柠弄干拌杰收炕赔旺知貌烂鸟象磐偶贤段被贾锁醇獭碍琴搂最豪虐锹森贵趁西触侍势涝抄尚艳圾疤鉴革镇所赵硕仿躬霸铡雷零呵农琵呀臆诧袒畴香麦荫栈哄涉住卞眯窃劫砾膛菊计垮炉搞粗移路徐将捡强敬淘帘灰诽媚煮谨伙侠撒刹勃馅秦逞坐背磅胎镭颗元葫律型哺趟埔昧酷