貪婪算法在構建物流網(wǎng)絡中的應用

任文軒

(1.中國科學技術大學 計算機科學與技術學院，安徽 合肥 230027；2.浙江海洋學院 公共實驗中心，浙江 舟山 316004)

貪婪技術就是在每一步操作中，“貪婪”地選擇最佳操作，并希望通過一系列局部的最優(yōu)選擇進而對全局問題產生一個最優(yōu)解。以收銀員找零問題為例，在中國廣泛使用的人民幣的紙幣面額有：d1=100(100元)、d2=50(50 元)、d3=20(20 元)、d4=10(10 元)、d5=5(5 元)、d6=1(1元)。當用這些面額的紙幣來給出37元的找零時，大多數(shù)人都會選擇給出一張20元、一張10元、一張5元和兩張1元的紙幣。這就是“貪婪”的想法在影響著人們。首先給出一張20元的紙幣就可以將余額降到最低，然后再用同樣的思路進行下面的操作。同樣人們也會想把這種技術應用到其他問題的求解上。

在現(xiàn)代社會中，物流產業(yè)已經(jīng)成為國民經(jīng)濟發(fā)展的動脈，其發(fā)展程度可以說是衡量一國現(xiàn)代化程度和綜合國力的重要標志之一，被喻為促進經(jīng)濟增長的“加速器”[1]。但是當前我國物流成本占GDP比例較高，而下降較為緩慢，反映出我國物流效益整體水平仍然較低。而要改善現(xiàn)狀就要從需求的物流服務水平出發(fā)，以盡可能小的物流費來實現(xiàn)整個物流網(wǎng)絡的合理化。整個物流系統(tǒng)可以用連節(jié)點(物流中心、需求點)和運輸路線構成的物流網(wǎng)絡來表示。而如何在這個物流網(wǎng)絡中找到可以使位于物流中心的多個配送人員可以更快地將貨物送至需求點的路徑，即是本文所要討論的問題。

1 問題描述

從圖論的角度可以把某個物流區(qū)域歸納為一個圖G=(V，E)[2]，其中 Vi其為連節(jié)點(物流中心、需求點)，Eij=［Vi，Vj］為連接節(jié)點 Vi、Vj的邊，并且均有一個非負權值Q(Eij)=Qij用來記錄兩個連節(jié)點之間的路徑的損耗，則最后所求得的配送路線即可以看作是一個最小生成樹，并且是圖 G的一個子圖 G*=(V*，E*)， 且 V=V*，E包含E*。

如圖1所示，假設無向圖G表示一個物流網(wǎng)絡，其中 V0、V1、V2、V3、V4、V5、V6、V7、V8、V9分 別 表 示 10 個 連節(jié)點，E01、E02、E23等為各個節(jié)節(jié)點之間的路徑。 下面需要做的工作就是在這10個連節(jié)點之中，找出一個最適合作為物流中心的節(jié)點，然后再從該節(jié)點出發(fā)繼續(xù)尋找最優(yōu)的物流路徑。而在此之前需要將無向圖G存儲在計算機中，其存儲方式有數(shù)組儲存方式和多重雙向鏈表存儲方式兩種。

圖1 無向圖G

無向圖G的數(shù)組儲存方式如圖2所示。

圖2 鄰接矩陣

為了在實際運算中更方便地解決問題，還需要采用多重雙向鏈表的方式作為邊的存儲結構。其中每一個頂點用一個節(jié)點表示，它包含兩個域：vex域表示該頂點相關的信息，firstEdge域表示第一條與該頂點相關聯(lián)的邊，如圖3所示。

圖3 每個頂點的一個節(jié)點的域

而存儲邊的多重雙向鏈表內應當包含如下域：邊的起始節(jié)點(Pvex)、邊的終點節(jié)點(Nvex)、邊上的權值(Weight)、指向起始節(jié)點和終點節(jié)點的下一條邊的指針域(Pnext)和(Nnext)、指向起始節(jié)點和終點節(jié)點的上一條邊的指針域(Pprior)和(Nprior)，如圖 4所示。該無向圖G的鏈表存儲結構如圖5所示。

圖4 存儲邊的多重雙向鏈表內的域

2 用Dijkstra算法來確定物流中心

Dijkstra算法的思想是：首先求出從起點到最接近起點的頂點之間的最短路徑，然后求出第二近的，以此類推。推而廣之，在第i次迭代開始以前，該算法已經(jīng)確定了i-1條連接起點和離起點最近頂點之間的最短路徑[3]。

該算法的部分偽代碼如下：

由此，在這個圖中就可以根據(jù)計算出來的結果來確定節(jié)點V4與其他節(jié)點最短路徑之和最小，因此在無向圖G中最適合做物流中心的就是V4。

3 用改進的Prim算法來計算最佳路徑

3.1 Prim算法

在實際的物流過程中，并不是每次送貨都需要遍歷圖中所有的節(jié)點，如何在這幾個點中找到一條最佳路徑從而在最大程度上節(jié)省物流成本是各物流公司所要面對的一個問題。Prim算法是解決上述問題的一個非常有效的方法。假設需要經(jīng)過n個需求點，就需要在無向圖中找出n－1條邊，使包含該n個節(jié)點的生成樹在保持連通的同時還要使權值最小。其步驟如下：

令圖 G=(V，E)，其生成樹的頂點集合為Vt。

(1)把物流中心節(jié)點 V4加入到Vt中。

(2)在所有Vt與 V－Vt節(jié)點之間尋找一條權值最小的邊e∈E并將其加入生成樹。

(3)把(2)中找到的邊 e對應的屬于 V－Vt的節(jié)點v加入Vt集合，如果 Vt集合中已有 n個元素，則算法結束；否則繼續(xù)執(zhí)行(2)。

3.2 并行Prim算法

在實際工作中，如果貨物量比較大或者為了減少整個物流運輸?shù)臅r間等原因，則需要從物流中心同時派出兩組以上的運輸車輛來完成送貨任務。這就需要在原來的Prim算法的基礎上加以改進。首先要確定物流中心所需要運輸車輛的組數(shù)，如果是需要兩組運輸車輛則得出的結果應為 G1(V*1，E*1)和 G2(V*2，E*2)兩個子樹，其分別對應兩組運輸車輛的送貨路徑。其算法分析如下：

(1)在各個節(jié)點到其他節(jié)點所有最短路徑之和中找出數(shù)值最大的那個節(jié)點(在圖G中為V2)。

表1 各節(jié)點到其他節(jié)點所有最短路徑之和

(2)找出 V2所有鄰邊中權值最小的一條邊 E12，并將此邊加入到結果子樹G1的邊集 E*1中，同時將V1、V2加入到子樹G1的點集V*1中；然后用Prim算法找出V1、V2到物流中心V4的最短路徑V2--V1--V0--V4，并將該路徑上的所有節(jié)點和邊均加入子樹G1中。

(3)根據(jù)表1選擇除物流中心節(jié)點外到其他節(jié)點所有最短路徑之和最小的節(jié)點，判斷該節(jié)點以及其臨界節(jié)點是否在V*1中，若在，則接著去尋找次小值的節(jié)點繼續(xù)判斷。如果不在則將此節(jié)點的鄰邊中權值最小的一條邊加入到結果子樹G2的邊集E*2中；然后用Prim算法找出節(jié)點到物流中心的最短路徑，并將該路徑上的所有節(jié)點和邊均加入子樹G2中。

在圖G中，除物流中心節(jié)點外到其他節(jié)點所有最短路徑之和最小的節(jié)點是V0，但是V0已經(jīng)存在于V*1中了，因此需要找次小值V5繼續(xù)判斷，發(fā)現(xiàn)V5以及其鄰節(jié)點均不在V*1中，因此可將V5的最小臨邊E59加入到G2的邊集 E*2中，將 V5、V9加入到 G2的點集 V*1中；然后找出 V5、V9~V4的最短路徑V9--V5--V4，并將其加入到子樹G2中。

這里如果需要增加第三組運輸車輛時，就按照步驟(3)所描述的在剩下的節(jié)點中繼續(xù)尋找合適的點去構建子樹G3。

(4)針對剩余的孤立點連接到兩個子樹的距離，判斷其加入到各自最近子樹后子樹的總路徑長度的增加值，取較小者將其加入子樹。

在本例中還有 V3、V6、V7、V84 個節(jié)點，分別判斷其加入G1或G2后路徑長度的增加值。V3離G1近，則加入后路徑長度增加30，V6離G2近，則加入后路徑長度增加 15，V7離G1、G2的距離一樣都是 30，V8離G2近加入后路徑長度增加60。因此這里選擇先將V6加入G2。

(5)重復步驟(4)直到圖G中無任何孤立點存在。

經(jīng)過上述算法，得到了G1、G2兩個子樹即兩條送貨路線。

本文介紹了如何利用貪婪技術在一個物流網(wǎng)絡的各個節(jié)點之中，找出適合作為物流中心的節(jié)點，并提出了一種經(jīng)過改進的并行Prim算法，使其在整個物流網(wǎng)絡中可以找出兩條以上的物流送貨線路來提高整個物流運輸?shù)墓ぷ餍?，使其在一定程度上減少物流損耗。但本文所提出的算法改進還存在很多不足之處，今后的工作是要改進算法，進一步考慮運輸路線的回路等問題的解決。

[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算法的最小生成樹優(yōu)化研究[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.