贪婪算法在构建物流网络中的应用

任文轩

(1.中国科学技术大学 计算机科学与技术学院，安徽 合肥 230027；2.浙江海洋学院 公共实验中心，浙江 舟山 316004)

贪婪技术就是在每一步操作中，“贪婪”地选择最佳操作，并希望通过一系列局部的最优选择进而对全局问题产生一个最优解。以收银员找零问题为例，在中国广泛使用的人民币的纸币面额有：d1=100(100元)、d2=50(50 元)、d3=20(20 元)、d4=10(10 元)、d5=5(5 元)、d6=1(1元)。当用这些面额的纸币来给出37元的找零时，大多数人都会选择给出一张20元、一张10元、一张5元和两张1元的纸币。这就是“贪婪”的想法在影响着人们。首先给出一张20元的纸币就可以将余额降到最低，然后再用同样的思路进行下面的操作。同样人们也会想把这种技术应用到其他问题的求解上。

在现代社会中，物流产业已经成为国民经济发展的动脉，其发展程度可以说是衡量一国现代化程度和综合国力的重要标志之一，被喻为促进经济增长的“加速器”[1]。但是当前我国物流成本占GDP比例较高，而下降较为缓慢，反映出我国物流效益整体水平仍然较低。而要改善现状就要从需求的物流服务水平出发，以尽可能小的物流费来实现整个物流网络的合理化。整个物流系统可以用连节点(物流中心、需求点)和运输路线构成的物流网络来表示。而如何在这个物流网络中找到可以使位于物流中心的多个配送人员可以更快地将货物送至需求点的路径，即是本文所要讨论的问题。

1 问题描述

从图论的角度可以把某个物流区域归纳为一个图G=(V，E)[2]，其中 Vi其为连节点(物流中心、需求点)，Eij=［Vi，Vj］为连接节点 Vi、Vj的边，并且均有一个非负权值Q(Eij)=Qij用来记录两个连节点之间的路径的损耗，则最后所求得的配送路线即可以看作是一个最小生成树，并且是图 G的一个子图 G*=(V*，E*)， 且 V=V*，E包含E*。

如图1所示，假设无向图G表示一个物流网络，其中 V0、V1、V2、V3、V4、V5、V6、V7、V8、V9分 别 表 示 10 个 连节点，E01、E02、E23等为各个节节点之间的路径。 下面需要做的工作就是在这10个连节点之中，找出一个最适合作为物流中心的节点，然后再从该节点出发继续寻找最优的物流路径。而在此之前需要将无向图G存储在计算机中，其存储方式有数组储存方式和多重双向链表存储方式两种。

图1 无向图G

无向图G的数组储存方式如图2所示。

图2 邻接矩阵

为了在实际运算中更方便地解决问题，还需要采用多重双向链表的方式作为边的存储结构。其中每一个顶点用一个节点表示，它包含两个域：vex域表示该顶点相关的信息，firstEdge域表示第一条与该顶点相关联的边，如图3所示。

图3 每个顶点的一个节点的域

而存储边的多重双向链表内应当包含如下域：边的起始节点(Pvex)、边的终点节点(Nvex)、边上的权值(Weight)、指向起始节点和终点节点的下一条边的指针域(Pnext)和(Nnext)、指向起始节点和终点节点的上一条边的指针域(Pprior)和(Nprior)，如图 4所示。该无向图G的链表存储结构如图5所示。

图4 存储边的多重双向链表内的域

2 用Dijkstra算法来确定物流中心

Dijkstra算法的思想是：首先求出从起点到最接近起点的顶点之间的最短路径，然后求出第二近的，以此类推。推而广之，在第i次迭代开始以前，该算法已经确定了i-1条连接起点和离起点最近顶点之间的最短路径[3]。

该算法的部分伪代码如下：

由此，在这个图中就可以根据计算出来的结果来确定节点V4与其他节点最短路径之和最小，因此在无向图G中最适合做物流中心的就是V4。

3 用改进的Prim算法来计算最佳路径

3.1 Prim算法

在实际的物流过程中，并不是每次送货都需要遍历图中所有的节点，如何在这几个点中找到一条最佳路径从而在最大程度上节省物流成本是各物流公司所要面对的一个问题。Prim算法是解决上述问题的一个非常有效的方法。假设需要经过n个需求点，就需要在无向图中找出n－1条边，使包含该n个节点的生成树在保持连通的同时还要使权值最小。其步骤如下：

令图 G=(V，E)，其生成树的顶点集合为Vt。

(1)把物流中心节点 V4加入到Vt中。

(2)在所有Vt与 V－Vt节点之间寻找一条权值最小的边e∈E并将其加入生成树。

(3)把(2)中找到的边 e对应的属于 V－Vt的节点v加入Vt集合，如果 Vt集合中已有 n个元素，则算法结束；否则继续执行(2)。

3.2 并行Prim算法

在实际工作中，如果货物量比较大或者为了减少整个物流运输的时间等原因，则需要从物流中心同时派出两组以上的运输车辆来完成送货任务。这就需要在原来的Prim算法的基础上加以改进。首先要确定物流中心所需要运输车辆的组数，如果是需要两组运输车辆则得出的结果应为 G1(V*1，E*1)和 G2(V*2，E*2)两个子树，其分别对应两组运输车辆的送货路径。其算法分析如下：

(1)在各个节点到其他节点所有最短路径之和中找出数值最大的那个节点(在图G中为V2)。

表1 各节点到其他节点所有最短路径之和

(2)找出 V2所有邻边中权值最小的一条边 E12，并将此边加入到结果子树G1的边集 E*1中，同时将V1、V2加入到子树G1的点集V*1中；然后用Prim算法找出V1、V2到物流中心V4的最短路径V2--V1--V0--V4，并将该路径上的所有节点和边均加入子树G1中。

(3)根据表1选择除物流中心节点外到其他节点所有最短路径之和最小的节点，判断该节点以及其临界节点是否在V*1中，若在，则接着去寻找次小值的节点继续判断。如果不在则将此节点的邻边中权值最小的一条边加入到结果子树G2的边集E*2中；然后用Prim算法找出节点到物流中心的最短路径，并将该路径上的所有节点和边均加入子树G2中。

在图G中，除物流中心节点外到其他节点所有最短路径之和最小的节点是V0，但是V0已经存在于V*1中了，因此需要找次小值V5继续判断，发现V5以及其邻节点均不在V*1中，因此可将V5的最小临边E59加入到G2的边集 E*2中，将 V5、V9加入到 G2的点集 V*1中；然后找出 V5、V9~V4的最短路径V9--V5--V4，并将其加入到子树G2中。

这里如果需要增加第三组运输车辆时，就按照步骤(3)所描述的在剩下的节点中继续寻找合适的点去构建子树G3。

(4)针对剩余的孤立点连接到两个子树的距离，判断其加入到各自最近子树后子树的总路径长度的增加值，取较小者将其加入子树。

在本例中还有 V3、V6、V7、V84 个节点，分别判断其加入G1或G2后路径长度的增加值。V3离G1近，则加入后路径长度增加30，V6离G2近，则加入后路径长度增加 15，V7离G1、G2的距离一样都是 30，V8离G2近加入后路径长度增加60。因此这里选择先将V6加入G2。

(5)重复步骤(4)直到图G中无任何孤立点存在。

经过上述算法，得到了G1、G2两个子树即两条送货路线。

本文介绍了如何利用贪婪技术在一个物流网络的各个节点之中，找出适合作为物流中心的节点，并提出了一种经过改进的并行Prim算法，使其在整个物流网络中可以找出两条以上的物流送货线路来提高整个物流运输的工作效率，使其在一定程度上减少物流损耗。但本文所提出的算法改进还存在很多不足之处，今后的工作是要改进算法，进一步考虑运输路线的回路等问题的解决。

[1]章海峰.进口物资中转运输选址-分配问题[D].武汉：华中科技大学，2006.

[2]黄冬梅，张岭，韩彦岭.并行搜救算法在确定灾后搜救路线中的应用[J].计算机应用研究，2011，28(2)：472-480.

[3]LEVITIN A.Introduction to the design and analysis of algorithms[M].潘彦译.北京：清华大学出版社，2010.

[4]江波，张黎.基于Prim算法的最小生成树优化研究[J].计算机工程与设计，2009，30(13)：3244-3247.

[5]OMRAN M G， ENGELBRECHTA P， SALMAN A.Particle swarm optimization method for image clustering[J].International Journal on Pattern Recognition and Artificial，2005，19(3)：297-322.

[6]SALEH B，SADOUN B.Design and implementation of a GIS system for planning[J].International Journal on Digital Libraries， 2006，6(2)：210-218.