物流網(wǎng)絡(luò)中節(jié)點(diǎn)帶權(quán)的Steiner最小樹(shù)的參數(shù)算法*

羅玉宏，李 莉

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

1 引言

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

1.1 問(wèn)題描述

1.2 研究現(xiàn)狀

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

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

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

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

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

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

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

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

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

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

(1)每個(gè)城市看成一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)根據(jù)城市分類(lèi)的等級(jí)，產(chǎn)生的節(jié)點(diǎn)費(fèi)用各不同。因?yàn)榻⑴渌椭行牡馁M(fèi)用很高，為了便于研究，本文將建設(shè)成本平均分?jǐn)偟饺舾赡曦浳镛D(zhuǎn)運(yùn)的單位成本中。

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

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

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

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

2.2 運(yùn)輸問(wèn)題的轉(zhuǎn)換

定義1基于源節(jié)點(diǎn)s的生成樹(shù)T中節(jié)點(diǎn)i的運(yùn)輸費(fèi)用為:

(1)

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

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

(2)

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

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

3 參數(shù)算法

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

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

連接的頂點(diǎn)覆蓋問(wèn)題[22]：

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

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

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

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

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

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

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

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

4 P-NSMT算法

4.1 算法描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

d.遍歷下一個(gè)節(jié)點(diǎn)。

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

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

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

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

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

(1)如果|T|

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

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

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

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

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

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

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

4.2 算法性能分析

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

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

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

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

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

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

證畢。

□

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

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

5 實(shí)驗(yàn)結(jié)果

5.1 模擬環(huán)境

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

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

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

5.2 模擬結(jié)果

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

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

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

第二種情況，當(dāng)終端節(jié)點(diǎn)數(shù)比例相同、網(wǎng)絡(luò)規(guī)模不同時(shí)，比較算法的準(zhǔn)確性。圖3b顯示了終端節(jié)點(diǎn)比例為10%，網(wǎng)絡(luò)規(guī)模分別為(100，400，700，1 000)的仿真結(jié)果。從圖中可以看出，當(dāng)終端節(jié)點(diǎn)比例固定為10%時(shí)，采用精確解法的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) 算法運(yùn)行效率NormalizedTime的比較。

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

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

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

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

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

6 結(jié)束語(yǔ)

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

下一步的研究工作將運(yùn)用參數(shù)算法解決多源點(diǎn)和多終端節(jié)點(diǎn)的物流網(wǎng)絡(luò)優(yōu)化問(wèn)題。綜合考慮最短時(shí)限運(yùn)輸問(wèn)題、帶時(shí)間窗的路徑優(yōu)化問(wèn)題、帶車(chē)容量限制的路徑優(yōu)化問(wèn)題等，使算法的更趨向于實(shí)際應(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)狀及未來(lái)趨勢(shì)[J].科技經(jīng)濟(jì)市場(chǎng)，2008(1):41-42.

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

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

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

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

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

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