羅玉宏，李 莉

(上海對外經(jīng)貿(mào)大學(xué)統(tǒng)計與信息學(xué)院，上海 201620)

1 引言

物流網(wǎng)絡(luò)通常是指物流企業(yè)經(jīng)營活動中所涉及的物流運輸網(wǎng)絡(luò)、物流信息網(wǎng)絡(luò)和物流客戶網(wǎng)絡(luò)[1]。在我國，物流成本占GDP的20%，遠(yuǎn)遠(yuǎn)落后于發(fā)達(dá)國家10%的比重，調(diào)查顯示，運輸配送成本占物流總成本的60%左右，因此優(yōu)化物流運輸網(wǎng)絡(luò)能有效地降低物流成本。對物流運輸網(wǎng)絡(luò)優(yōu)化的核心是確定合適的物流節(jié)點位置、規(guī)模和數(shù)量，選擇合適的連接線路及運輸方式，使物流網(wǎng)絡(luò)在滿足服務(wù)要求的基礎(chǔ)上總的運輸成本最低。對物流運輸網(wǎng)絡(luò)的優(yōu)化一直是國內(nèi)外學(xué)者研究的熱點，在物流業(yè)比較發(fā)達(dá)的歐美國家和日本，研究人員利用數(shù)學(xué)規(guī)劃法、系統(tǒng)仿真法和啟發(fā)式方法等技術(shù)工具對企業(yè)物流的組織管理模式、運營機制、設(shè)施選址、配送路徑選擇、物流成本優(yōu)化等問題提供支持[2]。

1.1 問題描述

1.2 研究現(xiàn)狀

對這類問題的研究，主要集中在物流配送中心選址與路徑的優(yōu)化。配送路徑優(yōu)化問題分為點點間運輸、多點間運輸、單回路運輸及多回路運輸?shù)阮愋?，并且結(jié)合各種現(xiàn)實條件，如最短時限運輸問題、帶時間窗的路徑優(yōu)化問題、帶車容量限制的路徑優(yōu)化問題等進(jìn)行研究[3]。由于運輸路徑優(yōu)化是NP-hard問題，國內(nèi)外對該問題的研究方法主要有：利用博弈論中的夏普里值方法解決物流網(wǎng)絡(luò)中的轉(zhuǎn)載運輸問題；利用基于模型的推理方法和啟發(fā)式搜索方法解決倉庫設(shè)施的定位問題，以及物流網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計中的聚集或分散決策；采用基于多目標(biāo)規(guī)劃設(shè)計物流網(wǎng)絡(luò)的優(yōu)化框架；借助排隊論和非線性理論研究城市物流中心的選址和規(guī)模問題等[4,5]。

本文采用的研究方法是將物流網(wǎng)絡(luò)模型抽象成平面圖，將問題求解轉(zhuǎn)化為構(gòu)造一棵節(jié)點帶權(quán)的Steiner最小樹問題。這類問題的求解同樣是NP-hard問題，采用的方法主要有精確解法、近似解法和參數(shù)解法[6,7]，代表性算法如下：

精確算法主要有支撐樹窮舉法、拓樸枚舉法等[8 - 11]，Melzak[9]提出的歐氏Steiner最小樹ESMT(Euclidean Steiner Minimum Tree)算法(簡稱K-ESMT)是當(dāng)前求解Steiner最小樹程序的核心思想，它將基于原點集的Steiner樹的所有可能的拓?fù)浣Y(jié)構(gòu)進(jìn)行分解，在分解為若干滿Steiner樹后，分別計算其總長，然后設(shè)法求出由這些滿Steiner樹的并集所構(gòu)成的Steiner最小樹，算法的運行時間達(dá)到O(nm) (m表示終端節(jié)點的個數(shù)，n表示網(wǎng)絡(luò)的規(guī)模)。Shore等人[11]提出分支界定的方法，判斷將一條邊是否放入最優(yōu)的Steiner樹進(jìn)行分支，然后再在各分支中分別考慮其最小連通性，時間復(fù)雜度為O(24n)。精確算法的時間復(fù)雜度高，當(dāng)網(wǎng)絡(luò)規(guī)模增大時，影響實際的應(yīng)用。

因此，人們對Steiner樹問題的研究主要集中在多項式時間可解的近似算法[11 - 17]。近似算法是在最差情況下找到的近似解與最優(yōu)解的比值作為算法的近似度，以此作為衡量算法好壞的重要指標(biāo)[13]。Kou等人[13]最早給出問題的近似算法，利用啟發(fā)式算法獲得一個近似比接近2的極小Steiner樹，時間復(fù)雜度為O(nlogn)。Thomposon[15]利用最小生成樹近似求解Steiner樹 ，通過添加一個Steiner點來連接三個鄰近的點，并通過刪除邊來避免環(huán)的出現(xiàn)，算法的時間復(fù)雜度為O(n4)。Robins[17]提出近似度接近最好的近似算法(簡稱Z-ESMT)，與傳統(tǒng)方法不同，該算法盡可能少地壓縮邊，迭代地修改終端節(jié)點生成樹，近似率接近1.55，時間復(fù)雜度為O(nm)。

參數(shù)理論是近年來發(fā)展起來的解決該難題的一項有效技術(shù)。參數(shù)理論的研究最初來源于觀察到很多計算問題都與一個取值范圍很小的重要參數(shù)相關(guān)，利用參數(shù)的性質(zhì)可以在一定程度上加速計算[18]。Dreyfus和Wagner[19]基于分解技術(shù)提出的動態(tài)規(guī)劃算法是求解Steiner樹的經(jīng)典算法，時間復(fù)雜度為O(3kn+2kn2)，其中k表示要覆蓋的節(jié)點個數(shù)。M?lle等人[20]采用動態(tài)規(guī)劃對問題進(jìn)行求解(算法簡稱M-ESMT)，具有較好的時間復(fù)雜度O((2+ε)k·p(n))，其中0<ε<1，該算法的問題在于，當(dāng)ε趨近于0時，p(n)的指數(shù)上升很快。例如，當(dāng)ε=0.5時，時間復(fù)雜度為O(2.5kn14.2)，當(dāng)ε=0.1時，時間復(fù)雜度為O(2.1kn57.6)，使得算法實際不可行。

借助參數(shù)算法理論，本文提出了一種新的啟發(fā)式算法P-NSMT(Parameterized algorithm for Minimum Node Weighted Steiner Tree)。實驗表明，與其他同類型的算法相比，該算法具有更好的準(zhǔn)確性和時間效率，特別適應(yīng)于網(wǎng)絡(luò)規(guī)模大、終端配送節(jié)點少的物流網(wǎng)絡(luò)。

2 網(wǎng)絡(luò)模型

在物流運輸網(wǎng)絡(luò)中，全部物流活動都在線路和節(jié)點上進(jìn)行。線路指已經(jīng)開辟的可以按規(guī)定進(jìn)行物流運營的路線和航線，包括鐵路線路、公路線路、水運線路、空運線路等。節(jié)點是物流網(wǎng)絡(luò)中連接物流線路的結(jié)節(jié)之處，具有轉(zhuǎn)運、存儲、流通等特點。在線路上進(jìn)行的活動主要是運輸，產(chǎn)生運輸費用，物流功能要素中的其他功能要素，如包裝、裝卸、保管、分貨、配貨、流通加工等都是在節(jié)點上完成的，產(chǎn)生節(jié)點費用[1]。

2.1 網(wǎng)絡(luò)模型構(gòu)建

為了便于構(gòu)建網(wǎng)絡(luò)模型，提出如下假設(shè)：

(1)每個城市看成一個節(jié)點，節(jié)點根據(jù)城市分類的等級，產(chǎn)生的節(jié)點費用各不同。因為建立配送中心的費用很高，為了便于研究，本文將建設(shè)成本平均分?jǐn)偟饺舾赡曦浳镛D(zhuǎn)運的單位成本中。

(2)任意兩個節(jié)點都是連通的，如果兩個節(jié)點有線路直達(dá)，則稱這兩個節(jié)點相鄰，互為鄰居，節(jié)點鄰居的個數(shù)稱為節(jié)點的度。如果兩個節(jié)點不是鄰居，則必須通過其它節(jié)點中轉(zhuǎn)。

(3)設(shè)貨物運輸始發(fā)地為源節(jié)點，貨物運輸目的地為終端節(jié)點。為方便最小運輸費用的研究，這里假定各節(jié)點都有足夠的運輸工具運送貨物，并且都能在約束的時間內(nèi)將貨物運到。這些因素可以在選擇運輸工具或中轉(zhuǎn)城市時作為約束條件引進(jìn)，或設(shè)立配送中心解決。

(4)每個節(jié)點僅知道到相鄰節(jié)點的貨物運輸費用，如果兩個節(jié)點之間存在多種運輸形式，采用價格較低的運輸方式。

將上述問題轉(zhuǎn)化為網(wǎng)絡(luò)模型：一個無向圖G=(V，E)。V是節(jié)點(頂點)集合，對應(yīng)相應(yīng)的源節(jié)點、中轉(zhuǎn)節(jié)點和終端節(jié)點；E是鏈路(邊)集合，對應(yīng)相鄰城市間的運輸線路。e=[i,j](i,j∈V)是E中的任一條邊，Eij表示從節(jié)點i向節(jié)點j運送單位貨物所需要的費用。Vi表示節(jié)點i的節(jié)點費用。構(gòu)建以始發(fā)地s為源節(jié)點，目的地Di為終端節(jié)點的生成樹T，要求生成樹T對應(yīng)的總運輸費用C(T,s)最小。

2.2 運輸問題的轉(zhuǎn)換

定義1基于源節(jié)點s的生成樹T中節(jié)點i的運輸費用為:

(1)

其中，Vs是源節(jié)點費用，Vi是中轉(zhuǎn)或終端節(jié)點i的節(jié)點費用，Eij是單位貨物從節(jié)點i運輸?shù)狡溧徆?jié)點j所產(chǎn)生的費用。

定義2貨物運輸?shù)目傎M用，即Steiner樹T的總權(quán)值為:

(2)

其中，dj是運往終端節(jié)點的貨物重量，m是終端節(jié)點的數(shù)量。i=s..j是從源節(jié)點s到終端節(jié)點dj在生成樹T中經(jīng)過的路徑節(jié)點編號，Ci(T,s)按照公式(1)計算，表示單位重量貨物在從節(jié)點i到路徑的下一個節(jié)點j所產(chǎn)生的運輸費用。

因此，上述運輸問題轉(zhuǎn)換為求節(jié)點帶權(quán)的Steiner最小樹問題(Node Weighted Steiner Tree Problem)，這類問題屬于NP-hard問題[21]。

3 參數(shù)算法

3.1 參數(shù)問題轉(zhuǎn)換

在參數(shù)算法中，用參數(shù)理論來求解NP-hard問題，本節(jié)首先要將該問題轉(zhuǎn)化為參數(shù)化問題。因此，首先將上述問題轉(zhuǎn)換為參數(shù)算法中連接的頂點覆蓋問題，然后提出啟發(fā)式算法P-NSMT。

連接的頂點覆蓋問題[22]：

輸入: 一個給定的無向連通圖G(V，E)以及一個正整數(shù)k，k≥|m+1|。

問題: 圖G是否存在一個大小為k的頂點覆蓋G′?G，G′是包含m+1個指定節(jié)點的連通樹，并且樹的總權(quán)值最小。

3.2 Steiner樹的相關(guān)性質(zhì)

為了獲得參數(shù)k的值，需要用到文獻(xiàn)[23]中Steiner樹的相關(guān)性質(zhì)。因此，首先需要將模型中節(jié)點帶權(quán)的Steiner樹轉(zhuǎn)換為Steiner樹。轉(zhuǎn)換方式如下：

(1)節(jié)點費用包括兩大部分：中轉(zhuǎn)貨物的費用和到達(dá)目的節(jié)點收貨、存貨等費用。其中到達(dá)目的節(jié)點收貨、存貨等費用與運輸路徑的選擇關(guān)聯(lián)度較小，只與到達(dá)目的節(jié)點的貨物重量有關(guān)，因此這方面的費用本文暫不討論。

(2)中轉(zhuǎn)貨物的費用與運輸網(wǎng)絡(luò)的優(yōu)化有較大關(guān)系。模型中節(jié)點帶權(quán)的Steiner樹，邊的權(quán)值是單位貨物的運輸費用，以節(jié)點間距離的形式呈現(xiàn)，與模型假設(shè)(1)節(jié)點中轉(zhuǎn)單位貨物的費用是統(tǒng)一的。因此，只要將中轉(zhuǎn)單位貨物的節(jié)點費用直接分?jǐn)偟竭叺臋?quán)值中去，就可以將節(jié)點帶權(quán)的Steiner樹轉(zhuǎn)換為Steiner樹，不會改變網(wǎng)絡(luò)的連接結(jié)構(gòu)。然后，直接使用已有的Steiner樹的性質(zhì)[23]：

在無向連通圖G中，有m個終端節(jié)點和1個源節(jié)點，令σ=max(Eij)/min(Eij)，Eij∈E。

推論1在連接的頂點覆蓋問題中，節(jié)點帶權(quán)的Steiner最小樹T的節(jié)點數(shù)k≤m+1+l。

4 P-NSMT算法

4.1 算法描述

P-NSMT算法思想是首先盡可能只利用終端節(jié)點構(gòu)造一棵連通的最小生成樹，然后逐步向樹中添加能減少生成樹總權(quán)值的Steiner節(jié)點，最終生成一棵節(jié)點總數(shù)不超過參數(shù)k的Steiner最小樹。算法包括三個階段：

第一階段，在圖G中建立以源節(jié)點s為根節(jié)點，包含所有終端節(jié)點的初始生成樹T。過程如下：

(1) 將所有節(jié)點設(shè)置成白色節(jié)點，源節(jié)點s設(shè)置為黑色節(jié)點；

(2) 將源節(jié)點s的所有鄰居節(jié)點變成s的孩子節(jié)點(葉子節(jié)點)，并將這些孩子節(jié)點設(shè)置成黑色節(jié)點；

(3) 如果存在終端節(jié)點不包括在生成樹T中，遍歷樹T的葉子節(jié)點，分別將這些節(jié)點的白色鄰居節(jié)點變?yōu)槠浜⒆庸?jié)點(葉子節(jié)點)，并將這些白色鄰居節(jié)點設(shè)置成黑色節(jié)點；

(4) 重復(fù)步聚(3)，直到所有的終端節(jié)點都包括在生成樹T中(可能會存在一些未加入生成樹的非終端節(jié)點)。

這個階段也可以采用文獻(xiàn)[24]提出的分布式算法，直接構(gòu)造一棵包含所有終端節(jié)點的最小生成樹，時間復(fù)雜度可以控制在O(nlogn)。

第二階段，對生成樹T進(jìn)行預(yù)處理，構(gòu)造一棵盡可能只包括終端節(jié)點的連通的最小生成樹。過程如下：

(1)因為在最小覆蓋G′中，葉子節(jié)點必須是終端節(jié)點。所以，先去掉所有不可能出現(xiàn)在最小覆蓋G′中的節(jié)點，刪除規(guī)則為：

① 在生成樹中，葉子節(jié)點j不是終端節(jié)點，如果它沒有別的鄰居節(jié)點，不作為Steiner候選節(jié)點，直接刪除它(如圖1a所示)。

Figure 1 Rules of deleting non candidates for Steiner node圖1 刪除非Steiner候選節(jié)點的規(guī)則

② 在生成樹中，葉子節(jié)點j不是終端節(jié)點，如果它的任一鄰居節(jié)點u是它的兄弟，且父節(jié)點到j(luò)的運費大于到節(jié)點u的費用(Eij>Eiu)，節(jié)點j不是Steiner候選節(jié)點，直接刪除它(如圖1b所示)。

③ 對于不屬于生成樹中的非終端節(jié)點，如果它的度不滿足性質(zhì)1的要求，那么它不是Steiner節(jié)點，直接刪除它。

(2)將生成樹T剩下所有非終端節(jié)點的葉子節(jié)點剪枝后，作為備選的Steiner點存放在集合B中。

(3)利用啟發(fā)式算法對生成樹T進(jìn)行優(yōu)化，建立總費用趨向最小的生成樹：

按輪對生成樹T進(jìn)行優(yōu)化操作，每一輪優(yōu)化過程都是從生成樹根節(jié)點s開始。為方便計算，每個節(jié)點都有一個存儲變量C，用來存放從源節(jié)點s運送貨物到該節(jié)點所需要的費用之和。優(yōu)化算法STO(T,s)：

① 首先按照公式(1)分別計算從根節(jié)點s運輸貨物到它任一孩子節(jié)點所需要的費用Cs(T,s)，并將其分別告知其孩子節(jié)點，孩子節(jié)點將其存放在各自的C中。

② 按照廣度優(yōu)先的次序依次遍歷樹T的每一個節(jié)點(按照當(dāng)前生成樹的順序，不管本輪中樹的結(jié)構(gòu)是否發(fā)生變化)。設(shè)初始值f=1(用f=0表示有交換父節(jié)點操作發(fā)生，f=1表示沒有交換父節(jié)點的操作發(fā)生)。如果一輪遍歷結(jié)束后，f還是為1，則終止優(yōu)化。

③ 當(dāng)遍歷經(jīng)過節(jié)點i時，節(jié)點i的處理過程Handle(i)如下:

a.節(jié)點i的任一鄰居節(jié)點j(j不在節(jié)點i的子樹中)計算其運輸貨物到節(jié)點i的總費用C′=(C+Cj(T,s))(這里C是節(jié)點j的存儲變量)并告知節(jié)點i;

b.節(jié)點i比較自身的C與C′的大小，如果存在C′

c.節(jié)點i分別計算它運輸貨物到它任一孩子節(jié)點所需要的費用Ci(T,s),然后將C+Ci(T,s)的值分別告知它的孩子節(jié)點，孩子節(jié)點將值存放在各自的C中；

d.遍歷下一個節(jié)點。

④ 刪除可能存在的非終端葉子節(jié)點，將其移入Steiner點的備選集B中。

顯然，這時樹T中僅包含源節(jié)點和終端節(jié)點，以及將終端節(jié)點連通必不可少的非終端節(jié)點(如果源節(jié)點和終端節(jié)點不能直接構(gòu)成連通圖)，生成樹T的總費用接近最優(yōu)，并且|T|≤k。

為了更好地理解Handle(i)的處理過程，舉例如下(圖2)：節(jié)點i原來的父節(jié)點為v，從源節(jié)點到v的運輸費是3(C=3)，計算從源節(jié)點到i的運輸費用為C+Vv+Evi=11,令節(jié)點i中C=11。u和v分別是節(jié)點i在樹中的鄰居節(jié)點，如果從節(jié)點u運送貨物到節(jié)點i，它的運輸費用為C+Vu+Eui=15>11，所以u不是節(jié)點i更換父節(jié)點的對象。如果從節(jié)點j運送貨物到節(jié)點i，它的運輸費用為C+Vj+Eji=6<11，所以j可以成為節(jié)點i新的父節(jié)點。更改節(jié)點i的父節(jié)點v到j(luò)，更新節(jié)點i中的C=6。

Figure 2 Node i changes its father node v→j圖2 節(jié)點i改變父節(jié)點v→j

第三階段，向生成樹T中逐步加入符合優(yōu)化條件的Steiner點，減少生成樹T的總費用。

(1)如果|T|

(2)依次從備選集B中取出一個節(jié)點v(v必須是樹T中節(jié)點的鄰居節(jié)點)。

(3)節(jié)點v在它的鄰居節(jié)點中尋找屬于生成樹T中的節(jié)點u，使節(jié)點v連接到節(jié)點u后，節(jié)點v中的C值最小。

(4)對節(jié)點v在生成樹中的任一鄰居節(jié)點j(節(jié)點u除外)進(jìn)行是否更改父節(jié)點判斷，如果j選擇v作為其父節(jié)點,則證明節(jié)點v的加入將減少生成樹的總費用，那么：

① 將v連接到節(jié)點u,將|T|加1;

② 將j連接到節(jié)點v,更新j中的C值，對j子樹Tj進(jìn)行STO(Tj,j)優(yōu)化操作；

③ 刪除T中存在的非終端葉子節(jié)點，每刪除1個，進(jìn)行|T|減1的操作，并且更新生成樹T的信息。

(5)如果備選集B中符合條件的任一節(jié)點加入后，生成樹不再改變，終止算法。

4.2 算法性能分析

定理1P-NSMT算法的時間復(fù)雜度為O(nlogn+kδGδT+k2logk+k2δT)。

證明對P-NSMT算法的復(fù)雜度進(jìn)行分析：

第一階段構(gòu)造初始的生成樹T，最快可以達(dá)到O(nlogn)[24]；

第二階段中第(1)、(2)步對生成樹T進(jìn)行剪枝操作的時間復(fù)雜度為O(nlogn)，第(3)步在優(yōu)化初始的生成樹T的過程中，Handle(i)的時間復(fù)雜度為O(δT)，δT是樹的度。因此，STO(T,s)算法的時間復(fù)雜度為O(klogk+kδT)。

第三階段生成樹優(yōu)化過程中，最多會對kδG個節(jié)點進(jìn)行是否改變連接節(jié)點的判斷，δG是圖G的度，時間復(fù)雜度為O(kδGδT)，最多會對k-m個節(jié)點進(jìn)行子樹優(yōu)化，處理時間為O(k2logk+k2δT)。這個階段算法的時間復(fù)雜度為O(kδGδT+k2logk+k2δT)

因此，P-NSMT算法總的時間復(fù)雜度為O(nlogn+kδGδT+k2logk+k2δT)。

證畢。

□

由定理1可知，當(dāng)k值相對n較小時，可以大大提高算法的性能。當(dāng)k值增大時，算法的性能會慢慢下降，當(dāng)k→n，算法的第二階段對所有的節(jié)點組成的生成樹進(jìn)行優(yōu)化操作，通過剪枝后直接生成Steiner最小樹，不再進(jìn)行第(3)階段的操作。因此，有如下推論：

推論2當(dāng)k→n時，算法的時間復(fù)雜度為O(nlogn+nδG)。

5 實驗結(jié)果

5.1 模擬環(huán)境

比較P-NSMT算法與其它有代表性的構(gòu)造Steiner最小樹算法的性能，這些算法包括：精確解法K-ESMT、近似解法Z-ESMT和參數(shù)解法M-ESMT(ε=0.5)。為了便于比較，實驗中事先將節(jié)點帶權(quán)的Steiner樹轉(zhuǎn)換成Steiner樹，再運算出相應(yīng)的結(jié)果。

分別在不同的網(wǎng)絡(luò)規(guī)模、不同數(shù)目的終端節(jié)點情況下，比較算法P-NSMT、K-ESMT、Z-ESMT和M-ESMT的準(zhǔn)確性和效率，這兩個指標(biāo)的計算方法定義如下：

其中:alg∈A={Z-ESMT,K-ESMT,M-ESMT,P-NSMT},C(Talg,s) 表示用A中的算法生成以s為源節(jié)點的Steiner最小樹的總費用，用公式(2)計算,C(Tbest,s)=min{C(Talg,s),alg∈A};Time(Talg) 表示用A中的算法生成以s為源節(jié)點的Steiner最小樹的計算機運行時間,Time(Tbest)=min{Time(Talg),alg∈A}。

5.2 模擬結(jié)果

實驗在不同的網(wǎng)絡(luò)環(huán)境下分別模擬100次，取95%的置信區(qū)間，結(jié)果如下：

(1) 算法準(zhǔn)確性NormalizedCost的比較。

分兩種情況，第一種情況，當(dāng)節(jié)點規(guī)模固定、終端節(jié)點數(shù)不同時，比較算法的NormalizedCost值。圖3a顯示了網(wǎng)絡(luò)規(guī)模為1 000個節(jié)點，終端節(jié)點數(shù)m分別為(10，40，70,100)的仿真結(jié)果。從圖中可以看出，采用精確解法的K-ESMT算法，求解出來的Steiner最小樹的總運費是最少的。P-NSMT算法的結(jié)果接近于最小的精確算法K-ESMT的結(jié)果，差距不超過2%，不同的終端節(jié)點數(shù)目對算法的準(zhǔn)確性影響不大，并且隨著終端節(jié)點數(shù)的增大，差距更加縮小。其它兩種算法的結(jié)果差距也基本上能控制在10%以內(nèi)。

第二種情況，當(dāng)終端節(jié)點數(shù)比例相同、網(wǎng)絡(luò)規(guī)模不同時，比較算法的準(zhǔn)確性。圖3b顯示了終端節(jié)點比例為10%，網(wǎng)絡(luò)規(guī)模分別為(100，400，700，1 000)的仿真結(jié)果。從圖中可以看出，當(dāng)終端節(jié)點比例固定為10%時，采用精確解法的K-ESMT算法的準(zhǔn)確性最高。其他三種算法隨著網(wǎng)絡(luò)規(guī)模的增加，算法的準(zhǔn)確性都得到了提高。P-NSMT算法優(yōu)于Z-ESMT算法和M-ESMT算法，與K-ESMT算法最大差距為5%,最小差距為1%。

Figure 3 Normalized Cost of the Steiner trees constructed by different algorithms圖3 各算法準(zhǔn)確性Normalized Cost的比較

(2) 算法運行效率NormalizedTime的比較。

比較各算法建立Steiner最小樹的運行時間，實驗平臺的主要配置為Windows 7操作系統(tǒng)，Intel? CoreTMi3 CPU M380@2.53 GHz,內(nèi)存2 GB，使用C++編寫算法并使用GCC4.8.5進(jìn)行編譯。

實驗同樣分兩種情況。第一種情況，當(dāng)節(jié)點規(guī)模固定、終端節(jié)點數(shù)不同時，比較算法的運行時間。圖4a 顯示了網(wǎng)絡(luò)規(guī)模為1 000個節(jié)點，終端節(jié)點數(shù)m分別為(10，40，70，100)，算法的NormalizedTime的值。結(jié)果顯示，P-NSMT算法的時間性能是最好的，特別是在終端節(jié)點數(shù)為10的時候，K-ESMT算法和M-ESMT算法運行時間分別達(dá)到了P-NSMT算法的9 351倍和8 025倍，近似算法Z-ESMT運行時間是P-NSMT算法的3 068倍。當(dāng)終端節(jié)點數(shù)增多時，四者的差距迅速縮小。當(dāng)終端節(jié)點數(shù)達(dá)到100時，時間的差距縮小到300以內(nèi)?？梢?，P-NSMT算法在終端節(jié)點數(shù)很小時，更能體現(xiàn)出算法的時間性能優(yōu)勢。

第二種情況，當(dāng)終端節(jié)點比例相同、網(wǎng)絡(luò)規(guī)模不同時，比較算法的運行時間。圖4b顯示了當(dāng)終端節(jié)點比例占10%，網(wǎng)絡(luò)規(guī)模分別為(100，400，700，1 000)，各算法的NormalizedTime的值?？梢钥闯?，時間性能的差距不大，當(dāng)網(wǎng)絡(luò)規(guī)模為100時，四個算法的差距不超過40倍；隨著網(wǎng)絡(luò)規(guī)模的增大，運行時間的差距慢慢增大，當(dāng)網(wǎng)絡(luò)規(guī)模達(dá)到1 000時，差距擴大到300倍左右。

從兩種情況都可以看出，P-NSMT算法的時間性能是最好的，其次是Z-ESMT算法，時間性能最差的是K-ESMT算法和M-ESMT算法。雖然M-ESMT算法理論上的時間復(fù)雜度比Z-ESMT算法和K-ESMT要好，但實際操作中，并沒有反映出來。P-NSMT算法無論是在理論時間復(fù)雜度還是實際的運行時間上，都體現(xiàn)了性能上的優(yōu)勢，特別是當(dāng)終端節(jié)點數(shù)目遠(yuǎn)小于網(wǎng)絡(luò)規(guī)模時，更加能體現(xiàn)出算法的時間性能優(yōu)勢。

Figure 4 Normalized Time of the Steiner trees constructed by different algorithms圖4 各算法運行效率Normalized Time的比較

6 結(jié)束語

本文將集中配送的物流運輸網(wǎng)絡(luò)優(yōu)化問題轉(zhuǎn)換成求解節(jié)點帶權(quán)的Steiner最小樹問題，運用參數(shù)理論，提出了一種新的啟發(fā)式解決算法P-NSMT。該算法首先盡可能只利用終端節(jié)點構(gòu)造一棵連通的最小生成樹，然后逐步向樹中添加能減少生成樹總權(quán)值的Steiner節(jié)點，最終生成一棵節(jié)點總數(shù)不超過參數(shù)k的Steiner最小樹。實驗表明，其他經(jīng)典啟發(fā)式算法相比，P-NSMT算法具有更好的準(zhǔn)確性和時間效率，特別適應(yīng)于網(wǎng)絡(luò)規(guī)模大、終端配送節(jié)點數(shù)目較少的物流網(wǎng)絡(luò)。

下一步的研究工作將運用參數(shù)算法解決多源點和多終端節(jié)點的物流網(wǎng)絡(luò)優(yōu)化問題。綜合考慮最短時限運輸問題、帶時間窗的路徑優(yōu)化問題、帶車容量限制的路徑優(yōu)化問題等，使算法的更趨向于實際應(yīng)用。

[1] Alan H, Remko V H. Logistics management and strategy:Competing through the supply chain[M].4th Edition.Upper Saddle River:Prentice Hall,2011.

[2] Xiang Tao.Research status and future trends of logistics network[J].Science & Technology Economy Market,2008(1):41-42.(in Chinese)

[3] Li Zhen-ping,Zhou Wen-feng.Modeling and solving of logistics distribution center location and path optimization problem [M].Beijing:China Machine Press,2014.(in Chinese)

[4] Ju Song-dong,Xu Jie,Bian Wen-liang,et.al.Putting forward and research on MF network theory[J].Journal of Beijing Jiaotong University(Social Sciences Edition),2009,8(2):16-20.(in Chinese)

[5] Gong Gu, Hu Xiao-ting,Wei Kai-xia,et al.Optimized performance research of the vehicle routing problem in industry logistics[J].Computer Engineering & Science,2011,33(5):106-111.(in Chinese)

[6] Zheng Ying,Wang Jian-xin,Chen Jian-er.Survey of Steiner tree problem[J].Computer Science,2011,38(10):16-22.(in Chinese)

[7] Tobias P,Siavash V D.The Steiner tree challenge:An updated study[EB/OL].[2014-08-24].http://dimacs11.cs.princeton.edu/downloads.html.

[8] Markus L, Zvana L, Martin L, et al. New real-world instances for the Steiner tree problem in graphs[R].Vienna:Department of Statistics and Operations Research, University of Vienna,2014.

[9] Melazk Z A.On the problem of Steiner[J].Canadian Mathematical Bulletin,1961,4(1):143-148.

[10] Huang T, Young E F Y. Obsteiner:An exact algorithm for the construction of rectilinear Steiner minimum trees in the presence of complex rectilinear obstacles[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2013,32(6):882-893.

[11] Shore M L,Foulds L R,Gibbons P B.An algorithm for the Steiner problem in graphs[J].Networks,1982,12(3):323-333.

[12] Uchoa E, Werneck R F.Fast local search for the Steiner problem in graphs[J].ACM Journal of Experimental Algorithms,2012,17(2):2.2:1-2.2:22.

[13] Kou L,Markowsky G,Berman L.A fast algorithm for Steiner trees[J].Acta Information,1981,15(2):141-145.

[14] Hougardy S,Silvanus J,Vygen J.Dijkstra meets steiner:A fast exact goal-oriented Steiner tree algorithm[EB/OL].[2015-09-08].https://arxiv.org/abs/1406.0492.

[15] Thomposon E A. The method of minimum evolution[J].Annals of Human Genetics,1973,36(3):333-340.

[16] Pajor T,Uchoa E,Werneck R F.A robust and scalable algorithm for the Steiner problem in graphs[EB/OL].[2014-12-10].http://arxiv.org/pdf/1412.2787v2.pdf.

[17] Robins G,Zelikovsky A.Improved Steiner tree approximation in graphs[C]∥Proc of Symposium on Discrete Algorithms,2000:770-779.

[18] Chen J.Parameterized computation and complexity:A new approach dealing with NP-hardness[J].Journal of Computer Science and Technology,2005,20(1):18-37.

[19] Dreyfus S E,Wagner R.The Steiner problem in graphs[J].Networks,1971,1(3):195-207.

[20] Mǒlle D,Richter S,Rossmanith P A.Faster algorithm for the Steiner tree problem[C]∥Proc of the 23rd Symposium on Theoretical Aspects of Computer Science,2006:561-570.

[21] Li Zhen-jian, Zhu Hong.An approximation algorithm of minimum spanning tree with edges and vertices weight[J].Computer Applications and Software,2008,25(1):12-13.(in Chinese)

[22] Chen Jian-e, Kanj I, Jia Wei-jia.Vertex cover:Further observations and further improvements[C]∥Proc of the 25th International Worshop on Graph-Theoretic Concepts in Computer Science, 1999:313-324.

[23] Liang Zhao-jian.The distributing of terminals and the prop-

erty of Steiner vertices on the Steiner tree problem[D].Changsha:National University of Defense Technology,2004.(in Chinese)

[24] Gallager R, Humblet P A, Spira P M.A distributed algorithm for minimum weight spanning trees[J].ACM Transactions on Programming Languages and Systems,1983,5(1):66-77.

附中文參考文獻(xiàn):

[2] 向濤.物流網(wǎng)絡(luò)研究現(xiàn)狀及未來趨勢[J].科技經(jīng)濟市場，2008(1):41-42.

[3] 李珍萍,周文峰.物流配送中心選址與路徑優(yōu)化問題—建模與求解[M].北京:機械工業(yè)出版社,2014.

[4] 鞠頌東,徐杰,卞文良,等.物流網(wǎng)絡(luò)理論的提出與探究[J].北京交通大學(xué)學(xué)報(社會科學(xué)版),2009,8(2):16-20.

[5] 鞏固,胡曉婷,衛(wèi)開夏,等.物流配送車輛路徑問題的優(yōu)化研究[J].計算機工程與科學(xué)，2011,33(5):106-111.

[6] 鄭瑩,王建新,陳建二.Steiner Tree 問題的研究進(jìn)展[J].計算機科學(xué),2011,38(10):16-22.

[21] 李鎮(zhèn)堅,朱洪.一種點邊帶權(quán)最小生成樹的近似算法[J],計算機應(yīng)用與軟件,2008,25(1):12-13.

[23] 梁兆健.Steiner樹問題中正則點分布Steiner點性質(zhì)[D].長沙：國防科學(xué)技術(shù)大學(xué),2004.