贪婪算法制定船舶物流航线

一、总论

所谓贪婪技术就是在每一步操作中，“贪婪”地选择最佳操作，并希望通过一系列局部的最优选择进而对全局问题产生一个最优解。贪婪算法的思想经常在日常生活中左右着我们处理问题时所采取的行为。最简单的例子就是我们在买菜的时候总是想花最少的钱去买最好的菜，在进行选择时如果两家菜的质量一样，我们显然会去选择其中价格最低的那一家来进行购买，这其实就是最为朴素的贪婪算法。在现代社会中物流产业已经成为国民经济发展的动脉，其发展程度可以说是衡量一国现代化程度和综合国力的重要标志之一，被喻为促进经济增长的“加速器”。然而目前我们国内整体物流成本占GDP的比例比较较高，下降速度也是非常缓慢，这就反映出我国的物流效益整体水平仍然较低。而通过物流网络的合理化，可以在很大程度上降低物流成本，提高物流效益。本文就单独以船舶物流航线来进行讨论。我们的整个航运系统可以用联节点（港务中心、需求点）和航运路线构成的航运网络来表示。我们首先需要制定出一个航运网络，然后再确定出它的港务中心，最后以该港务中心为出发点制定航线。

二、问题分析

从计算机图论的角度出发我们可以将某个物流区域归纳为一个图L=（V，E），其中的Vi为航运网络图结点（港务中心、需求点），Eij=［Vi，Vj］为连接节点Vi，Vj的边并且有一个非负权值Q（Eij）=Qij用来记录两个联节点之间的路径的损耗，那么我们最后所求得的配送路线即可以看作是一个小生成树，并且是图L的一个子图L*=（V*，E*），且V包含V*，E包含E*。如上图1所示，假设无向图L表示一个航运网络，而其中的V0，V1，V2，V3，V4，V5，V6，V7，V8，V9，V10，V11，V12，V13分别表示十四个联节点，E01，E02，E23等分别为各个联结点之间的路径。而在路径上的数字则表示两个结点之间路径的权值。

三、通过Dijkstra算法确定港务中心

Dijkstra算法的思想是：首先，求出从起点到最接近起点的顶点之间的最短路径，然后求出第二近的，以此类推。推而广之，在第i次迭代开始以前，该算法已经确定了i-1条连接起点和离起点最近顶点之间的最短路径。运用这种Dijkstra算法的效率取决于图本身的数据结构，以及表示集合V-Vm（Vm是指已经加入到子树中的结点的集合）的优先队列的数据结构。如果我们采用数组存储的方式来进行运算的话，我们的时间复杂度将会属于O（|V|2）。假设我们所参考的图的权值足够准确，我们就可以将与其他结点最短路径之和最小的那个结点用来作为我们整个航运网络的港务中心。运算结果如下：1300iid=807，1310iid=629，通过上述计算结果我们可以知道结点V3到其他结点的最短路径之和最小，所以在无向图L之中最适合做其港务中心的结点就是V3。而结点V13到其他结点的最短路径之和最大，因此是最不适合选作港务中心的结点。

四、用改良后的Prim算法来计算最佳航路

1．Prim算法介绍Prime算法是图论中求最小生成树的一种经典算法。它是解决下述问题的一种有效方法：假设我们在一个无向图中需要经过n个需求点，我们就需要在该无向图中找出n－1条边使包含该n个结点的生成树在保持连通的同时还要使权的总和最小。通过上面的描述我们可以看到，Prim算法也可以用来解决在一个航运网络中求最短航运线路的问题。其具体步骤如下：令无向图L=（V，E），其生成树的顶点集合为Vm。

（1）首先我们将把港务中心结点V3加入到Vm中。

（2）在所有的Vm与V－Vm结点之间寻找在其中权值最小的边e∈E并将这一条边加入到该生成树之中。

（3）把步骤二中所找到的边e所对应的属于V－Vm之中的结点V*加入Vt集合。这时进行检测如果发现Vm集合之中已经包含有所需要的n个元素，则算法结束；否则继续执行步骤二。

2．并行Prim算法当然在实际情况中，在同一个航运网络之中往往同时运行有两条或两条以上的航运线路。而用传统的Prim算法就无法解决这种问题，而需要对其进行改进。首先我们需要确定港务中心所需要派出的船舶组数，如果是需要两组运输船舶那么我们最后所得出的结果应为两个子树L1（V*1，E*1），L2（V*2，E*2）其分别对应两组航运线路。下面是以无向图L为例子的算法分析。第一步：首先在我们之前计算出来各个结点到其他结点的所有最短路径之和中找出数值最大的那个结点，在无向图L中为V13.第二步：然后再找出V13的所有邻边之中权值最小的一条边E11-13并将此边加入到结果子树L1的边集E*1中，并将V13，V11加入到子树L1的点集V*1中。接着再用Prim算法找出结点V11，V13到港务中心V3的最短路径V3-V5-V10-V11-V13并将该路径上的所有结点和边均加入子树L1中。第三步：根据图三选择除港务中心结点外到其他结点所有最短路径之和最小的结点，判断该结点是否在V*1中，若在，则接着去找次小值的结点继续判断。直到发现满足条件的结点并将此结点的邻边中权值最小的一条边加入到结果子树L2边集E*2中。然后用Prim算法找出该结点到物流中心的最短路径，并将该路径上的所有结点和边均加入子树L2中。无向图L中除了港务中心结点外到其他结点所有最短路径之和最小的结点是V5，但是V5已经存在于V*1中了，因此我们需要找次小值V4继续判断，发现V4不在V*1中，因此，我们就将V4的最小临边E47加入到L2的边集E*2中，将V4，V7加入到L2的点集V*2中。然后找出V4，V7到港务中心V3的最短路径V3–V4–V7并将其加入到子树L2中。第四步：对于剩余的孤立结点，我们可以先计算出他们分别连接到两个子树所产生的路径长度，取其中较小者将其加入。假如该结点到两条子树的路径增加值均相同，则我们需要考虑子树总路径的长度，选择子树总路径长度最小的那一条将其并入。在本例中还有V0，V1，V2，V6，V8，V9，V12，七个结点，分别判断其加入到L1或L2后路径长度的增加值。V6离子树L2近加入子树L2后其长度增加值为5，V8离子树L2近加入子树L2后其长度增加值为11，V9离子树L2近加入子树L2后其长度增加值为15，V12离子树L1近加入子树L1后其长度增加值为10，V2离子树L2近加入子树L2后其长度增加值为20，V1离子树L1近加入子树L1后其长度增加值为25，V0离子树L2近加入子树L2后其长度增加值为23。因此这里选择先将V1，V12加入到子树L1中，而将V0，V2，V6，V8，V9这五个结点加入到子树L2中。通过上述运算，我们在无向图L中求出了两个子树L1、L2也就是得到了两条航运线路。他们最终生成子图如下。

五、总结

本文首先运用贪婪算法在一个航运网络的各个结点之中，找出适合作为港务中心的结点。然后本文又利用一种改进的Prim算法，在整个航运网络中找出两条航运线路来提高整个物流网络的工作效率，并尽可能的降低物流损耗。然而要真正制定出符合实际的物流线路，其关键还是在于无向图中的“权”值的制定，这也是本人今后工作的研究方向之一。