物流配送管理中的路径优化问题研究，本文主要内容关键词为：路径论文,物流配送论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
一、引言
现实生活中的许多经济现象通常都具有非常强的动态特征，人们对于这些现象一般是先进行数学上的抽象，然后用静态或统计的方法来加以研究和处理。从优化的理论和方法上看，经典的优化理论大多是站在旁观者的立场上看问题，即首先确定已知条件，然后在假设这些已知条件不变的基础上给出最优方案（即最优解）。条件一旦发生变化，这种方法所给出的最优方案就会失去其最优性。在变化的不确定因素对所考虑的问题影响很大的时候，经典的优化方法有：一是将可变化的因素随机化，寻求平均意义上的最优方案，二是考虑可变化因素的最坏情形，寻求最坏情形达到最优的方案。这两种处理方法对变化因素的一个特例都可能给出离实际最优解相距甚远的解，这显然是难以满足实际的要求的。那么是否存在一种方法，它在变化因素的每一个特例中都能给出一个方案，使得这一方案所得到的解离最优方案给出的解总在一定的比例之内呢?近年来兴起的局内问题与竞争算法的研究结果在一定意义上给如上问题一个肯定的答案。其实本文所提出的逆向标号算法就是对应局内最短路问题的一个竞争算法，从本质上来说它是一种贪婪算法，在不知将来情况的条件下，求出当前状态下的最优解。[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表示已经被标记点的集合，集合(G-S)表示未被标记点的集合，一个点的标号是这个点到源节点的最短距离，算法的主要思想是：从G-S集合中选取具有最小标号的点w，而后把w点放入S集合中。因为S集合就是已经被标记点的集合，然后再从G-S集合中将所有经过点w而与源节点相通的v点的路径值T[v]统统作调整（如果存在某个点v，它的路径值大于已经被标记的点w的路径值与点v到点w的距离之和，那么就对所有与点v相通的点的路径值进行调整）。重复此过程直至所有的点全部进入S集合。
从以上的分析我们可以看出，当进行完Dijkstra算法，所有的点都将会被标号。首先我们先给出本节将会用到的符号和定义。我们用
表示沿着最短路从O点到A点的距离，W(
)表示沿着最优路径从A点到D点的距离。Wij表示从i点到j点边的权，T[v]表示的v点标号值。[3]
（一）算法一
第一步，对于给定的平面图G，运用Dijkstra算法求出从起点O点到终点D点的最优路径SP。
第二步，到达A点后，如果下一个顶点B发生车辆拥塞不能通车，计算子图G-{B}。
第三步，在此运用Dijkstra算法求出此时从A点到D点的最优路径。
第四步，
即为最后所花费的费用。
根据点标号的定义和Dijkstra算法的主要思路，应该有如下引理成立。
引理一：平面图的最短路径树中的一个点的标号只和它相邻标号的点有关。
图1 最短路径树
（二）算法二
对于给定的平面图G，运用Dijkstra算法求出从O点到D点的最优路径SP。
Dijkstra算法只给出了指定点到其余节点的距离，并未直接给出指定点到其余节点的最短路径，为此可以对上述算法稍加补充，增设一路径变量
，用来存储最短路径树上点的信息。其初始值规定如下：
第一，当从u点到vi点按照最优路径行走所需的路程不是无穷大时，表示u点与
之间的合集；
第二，当从u点到点按照最优路径行走所需的路程为无穷大时，为一空集。
经过多次迭代和修改过程，最后得到的和
即为指定点u到点的最短路径和距离。在运用Dijkstra算法求出从O点到D点的最短路径时用了一些技巧：我们反着来应用Dijkstra算法，以D点为起点，O点为目的点进行运算，同时标记每点到D点的最短距离及其路径，T表示已经被标号点的集合。
对于重新标记与A点相邻的点，我们要针对不同情况进行不同分析，总的来说对于如下两种情况：
如图二所示，如果去掉B点后不会影响与A点相邻点的标号（O点除外），此时我们只需重新标记O点，这在常数时间内就能完成。
如图三所示，如果去掉B点后会影响与A点相邻点的标号，我们就需重新标记与A点相邻的点。对于这种情况，我们可以以如下逆推方法计算：
首先可以根据路径变量存储的最短路径树上点的信息，将图中的点分成两个集合，G1表示需要重新标记的点的集合，G2表示不需重新被标记的点的集合。然后判断与A点相邻点的是否标记，如果没有，再次判断这些相邻点的相邻点是否被标记，这个判断一直到最后找到的相邻点都在G2中为止。然后从后向前依次进行标记。通过标记，计算与A相邻的所有点到A点的距离与该点到终点的最短距离之和的最小值，并用W表示该最小值，这样就可以求出最低费用和最优路径。
（三）算法复杂性分析
对于算法一，第一步的Dijkstra算法时间复杂性为
，对于第二步可以在常数时间内解决。同样第三步的时间复杂性为。[4][5]
对于算法二，第一步的Dijkstra算法时间复杂性为；而对于步骤二因为路径变量存储的最短路径树上点的信息，所以我们能在o(n)时间内将图中的点分成集合G1和G2；对于步骤三因为平面图的假设，应有e=kn（k为常数）。在最坏的情况下步骤三也无需遍历完所有的边，所以步骤三在时间o(n)就可以完成；而步骤四可以在常数时间内解决。
四、案例分析
我们考虑一个实际的配送案例：某物流配送公司按照客户的要求从A城市运送一批生鲜到B城市，有一条已知的最方便快捷的路径SP，选择SP这条路径的成本是W(SP)。配送员从A城市出发，沿着SP这条道路行进，但是在走到某个中间城市V时，出现了由于洪水造成的道路堵塞。这时，配送员有两个选择，一种选择是等待直到道路修好，一种选择是找到另外一条路继续前行。而由于生鲜这些食品的保质期有限，一定要保证在尽可能短的时间内到达目的地。因而配送员如果选择等待的话，就会造成食品过期的问题。于是配送员选择重新挑选路径继续前行。此时，配送员面临的问题就是如何重新选择道路，才能保证及时到达目的地。道路图描述如右图四所示：
在这个实际应用的案例中，我们把认为从起点到终点的时间与从起点到终点的花费成正比关系。因而，我们可以分别应用传统算法与逆向标号算法来求出此时从V城市到终点城市B的最优路径
。
应用传统算法，就是在V点运用Dijkstra算法求出此时从V城市到B城市的最优路径
，这时，
就是最短的时间。
应用逆向标号算法，则是反着来应用Dijkstra算法，以B城市为起点，V城市为目的点进行运算，同时标记每个到V城市的最短距离及其路径，用T表示已经被标号的所有城市节点的集合，这样就可以在T集合中找到一个城市V'，从V经过V'到达城市B是最短的路径。
两种算法都可以找到最短路径来保证配送员能够及时到达目的地，但两种算法各有利弊。第一种算法直观，但算法的时间复杂性相对要高一些；第二种算法需要逆向计算，但其时间复杂性要比第一种算法低。相较而言，第二种算法在计算机上实现后，更有适用于大规模的数据计算，从而提高效率、节约了生产厂家和批发商的运输成本，提高了车辆的货物装载率，避免了资源的浪费，长远的可以降低货物的价格；缓解了交通紧张的状况，缩短了货物配送的时间，提高了整个配送网络的配送效率。
在运输越来越多元化的当今时代，单纯的考虑两个城市之间的距离的长短已经不能让物流公司更好的控制成本了。物流配送过程中，物流公司与配送员可能不仅仅需要考虑路程，还需要考虑到各种可能的影响因素，比如路况、便利程度等。重新考虑这个实际案例，当配送员从A城市出发，沿着SP这条道路行进，但是在走到某个中间城市V时，出现了由于洪水造成的道路堵塞，配送员在面临的重新选择道路的时候，不仅需要考虑到路途的远近，同样也要分析已经选择的道路的路况是否较好、是否不易受到洪水的影响等因素。同时，配送员不仅可以选择陆路，还可以选择铁路、水路，来让自己以最低的成本最快的速度来完成配送任务。
图4 道路图
我们按照这种更具有现实意义的情况对算法进行修正。配送员考虑到了更多的实际问题，如路况、便利程度等这些影响配送路径选择的因素后，就很有可能不会按照原来算法给出的最短路径行进了，因为按照原来算法考虑的因素太少，而且可以作出的选择也很少，在可选择的变量集合扩大的情况下，可能会出现一个更优解。
因此我们对根据距离来进行的最短路算法进行如下的修正，充分考虑两地交通便利条件，路面状况，两地距离以及运送成本等因素。
在新的情况下，将路径的权数变成一种综合权数，即Wij这个权不单指i点到j点的距离，它成为一个综合的考虑因素，即Wij=f(dij,cij,tij)，其中dij表示i点到j点的距离，cij表示i点到j点的交通条件，tij表示i点到j点的交通工具。
对于本文的案例，当配送员在V城市碰到洪水后，在重新选择路径时，就要考虑到交通工具的因素，充分与交通运输工具、运送的速度和成本等因素综合考虑。因此，选择期望的运输方式时，至关重要的问题就是如何平衡运输服务的速度和成本。计算总的成本需要按照成本最低的原则选择合适的路线和运输方式，在充分利用公路从门到门和在中途运输中速度快且灵活机动的优势的同时，开展中短距离铁路、水路与公路分流，从而加大被堵的塞点的运输通过能力，实现全方位的多途径的高效运输。
五、结束语
传统的优化理论大多对某一问题的优化总是以知道必要的全部条件不变为前提条件，而这在现实生活中显然不合实际。正如文章所提到的那样，在很多情况下对目标有影响的因素总是在不断变化的。本文所讨论的动态最短路问题就是在限定条件不断变化的情况下，如何求出变化后的最优路径。本文所讨论问题的优化指标为运输车辆所走过的总路程，本文通过对Dijkstra算法灵活运用，采用逆向标号，有效的利用了第一次计算的有用信息，避免了一些重复计算，对于动态最短路问题可以快速求解。
作为一种先进的组织方式和管理技术，物流被广泛地认为是企业在除了降低物资消耗，提高劳动生产率以外的又一个可以增加利润的方式，它在国民经济和社会发展中发挥着重要的作用。随着物流管理的合理化，物流消耗也逐渐减少了，因而一些发达国家把降低流通费用，特别是物流费用作为第三利润开发的源泉。
目前从我国的企业运作来看，运输成本占国民经济总成本的30%，而发达国家仅为10%。也就是说，仅从运输成本来看，我们还有“20%”这样一个空间可以去努力。只要我们能够将现有运输成本降低10%左右，我们的国民经济总体水平就能出现一次新的飞跃。
而物流配送中的路径优化算法研究，可以在成本降低方面给出积极而有效率的意见和解决方法，降低流通费用，以此促进整个国民经济的飞速发展。
标签：最短路径论文; dijkstra论文; 集合运算论文; 城市配送论文; 城市选择论文;