范昌勝，徐錦華，陳新莊，李 斌

(1.陜西工商職業(yè)學(xué)院工程與建筑學(xué)院，陜西 西安 710119；2.西北工業(yè)大學(xué)理學(xué)院應(yīng)用數(shù)學(xué)系，陜西 西安 710072)

當(dāng)前的物流行業(yè)通過(guò)倉(cāng)儲(chǔ)、運(yùn)輸、配送等形式進(jìn)行全面綜合管理，使得在物流過(guò)程中縮短了時(shí)間，降低了成本.眾多大型物流配送企業(yè)都會(huì)共同遇到類(lèi)似的倉(cāng)庫(kù)選址及調(diào)運(yùn)問(wèn)題.通常采用將物流網(wǎng)絡(luò)中的倉(cāng)庫(kù)合理分散設(shè)置的方案，制定恰當(dāng)?shù)膫}(cāng)庫(kù)選址及車(chē)輛出行線路，最大程度地為分散的用戶(hù)提供一定的服務(wù)，又能降低整個(gè)系統(tǒng)運(yùn)行的總費(fèi)用[1-2].

對(duì)倉(cāng)庫(kù)選址問(wèn)題的研究，國(guó)內(nèi)外的學(xué)者都寄予很高的重視，對(duì)此問(wèn)題的解決，有精確算法和近似算法兩種.主要包括分支定界法，拉格朗日松弛法，禁忌搜索法，模擬退火法、遺傳算法[2-3]及一些混合算法.在國(guó)外，對(duì)無(wú)容量約束的倉(cāng)庫(kù)選址問(wèn)題，文獻(xiàn)[4]給出了禁忌搜索算法；對(duì)有容量約束的倉(cāng)庫(kù)選址問(wèn)題，文獻(xiàn)[5]對(duì)此問(wèn)題的解決方法從精確算法和近似算法進(jìn)行了總結(jié)，文獻(xiàn)[6]給出了增加或減少倉(cāng)庫(kù)的啟發(fā)式算法.在國(guó)內(nèi)，文獻(xiàn)[7]用單親進(jìn)化遺傳算法解決有倉(cāng)庫(kù)容量限制的選址問(wèn)題，這要求一個(gè)需求點(diǎn)僅由一個(gè)配送中心(倉(cāng)庫(kù))供應(yīng)，上述文獻(xiàn)所研究的都是只考慮倉(cāng)庫(kù)和需求點(diǎn)之間的供應(yīng)關(guān)系. 還有許多文獻(xiàn)對(duì)上述選址問(wèn)題進(jìn)行了擴(kuò)展，考慮工廠，倉(cāng)庫(kù)，需求點(diǎn)三層之間的供應(yīng)關(guān)系.文獻(xiàn)[8]研究了只有一個(gè)工廠的情形，并用混合遺傳算法求得其近似最優(yōu)解.文獻(xiàn)[9]考慮了多工廠的情形，用啟發(fā)式算法進(jìn)行求解，不過(guò)倉(cāng)庫(kù)的固定費(fèi)用沒(méi)有反映在解值上.文獻(xiàn)[10-12]通過(guò)把三層關(guān)系轉(zhuǎn)化成兩層關(guān)系來(lái)求解，即在優(yōu)化兩層關(guān)系的前提下，按隨機(jī)要求從工廠向倉(cāng)庫(kù)供應(yīng)貨物.并用拉格朗日松弛法和遺傳算法求得其最優(yōu)解.

在上述問(wèn)題研究的基礎(chǔ)上，對(duì)有倉(cāng)庫(kù)容量限制，多工廠的三層供應(yīng)關(guān)系的倉(cāng)庫(kù)選址問(wèn)題進(jìn)行了研究，給出了一種精確算法.這種算法在求出工廠到倉(cāng)庫(kù)、倉(cāng)庫(kù)到銷(xiāo)售點(diǎn)最短路徑的前提下，在滿(mǎn)足倉(cāng)庫(kù)容量限制的基礎(chǔ)上，找出可降費(fèi)的閉合回路進(jìn)行調(diào)整，最后再通過(guò)減少倉(cāng)庫(kù)個(gè)數(shù)確定最優(yōu)倉(cāng)庫(kù)個(gè)數(shù)和運(yùn)輸路線.這種算法用計(jì)算機(jī)語(yǔ)言很容易編程實(shí)現(xiàn)，具有計(jì)算速度高，存儲(chǔ)空間少等優(yōu)點(diǎn).

1 問(wèn)題描述及其數(shù)學(xué)模型

在現(xiàn)實(shí)生活中，產(chǎn)品的流通與否直接影響著企業(yè)的經(jīng)濟(jì)效益，為了方便產(chǎn)品的流通，工廠經(jīng)常需要建立或租賃倉(cāng)庫(kù)來(lái)存儲(chǔ)貨物，以達(dá)到使整個(gè)物流環(huán)節(jié)的費(fèi)用支出最小，對(duì)于這種活動(dòng)，可以描述為以下數(shù)學(xué)問(wèn)題.

問(wèn)題描述:在有N 個(gè)節(jié)點(diǎn)的無(wú)向連通網(wǎng)絡(luò)中，節(jié)點(diǎn)Ai表示工廠(i ＝1，2，...m)，Bj表示倉(cāng)庫(kù)(j ＝m ＋1，m ＋2，…m ＋s)，Ck表示銷(xiāo)售點(diǎn)(k ＝m ＋s ＋1，m ＋s ＋2，…m ＋s ＋n)，并且滿(mǎn)足m ＋s ＋n ≤N；已知第Ai個(gè)工廠可提供貨物量為Pi，第Bj個(gè)倉(cāng)庫(kù)的容量為Rj、租賃費(fèi)為Fj， 第Ck個(gè)銷(xiāo)售點(diǎn)需求貨物量為Qk，并且滿(mǎn)足又已知網(wǎng)絡(luò)中任意相鄰節(jié)點(diǎn)i 和j 間的單位運(yùn)費(fèi)為Sij＝Sji(1 ≤i，j ≤N)[13].

研究:如何選擇工廠到倉(cāng)庫(kù)的運(yùn)輸線路，倉(cāng)庫(kù)到銷(xiāo)售點(diǎn)的運(yùn)輸線路，才可使所有貨物從工廠運(yùn)送到倉(cāng)庫(kù)再到銷(xiāo)售點(diǎn)的總成本最低(總成本包括倉(cāng)庫(kù)租賃費(fèi)和貨物運(yùn)輸費(fèi)用)?

問(wèn)題分析:這個(gè)問(wèn)題具有很廣泛的現(xiàn)實(shí)意義，根據(jù)問(wèn)題描述，我們解決的思路是把N 個(gè)節(jié)點(diǎn)分成三類(lèi)點(diǎn)，工廠、倉(cāng)庫(kù)和銷(xiāo)售點(diǎn)，在已知任意相鄰兩點(diǎn)i 和j 間的單位運(yùn)費(fèi)Sij(1 ≤i，j ≤N)的前提下，用Floyd 算法求得從工廠到倉(cāng)庫(kù)最短路徑cij，從倉(cāng)庫(kù)到銷(xiāo)售點(diǎn)的最短路徑cjk.在此轉(zhuǎn)化的基礎(chǔ)上，可得到以下數(shù)學(xué)模型:

其中:xij＞0 表示第i 個(gè)工廠向第j 個(gè)倉(cāng)庫(kù)運(yùn)輸貨物，且運(yùn)量為xij，xij＝0 表示第i 個(gè)工廠向第j 個(gè)倉(cāng)庫(kù)無(wú)運(yùn)量；同理，xjk＞0 表示第j 個(gè)倉(cāng)庫(kù)向第k 個(gè)銷(xiāo)售點(diǎn)運(yùn)輸貨物，且運(yùn)量為xjk，xjk＝0 表示第j 個(gè)倉(cāng)庫(kù)向第k 個(gè)銷(xiāo)售點(diǎn)無(wú)運(yùn)量.

目標(biāo)函數(shù)是最小化所有費(fèi)用，其中前兩項(xiàng)為運(yùn)輸費(fèi)用，最后一項(xiàng)為倉(cāng)庫(kù)租賃費(fèi)用.(1)表示從工廠發(fā)出的貨物總和應(yīng)等于它所提供的貨物；(2)表示銷(xiāo)售點(diǎn)的需求量應(yīng)得到滿(mǎn)足；(3)表示由工廠發(fā)往每個(gè)倉(cāng)庫(kù)的貨物量等于該倉(cāng)庫(kù)滿(mǎn)足其銷(xiāo)售點(diǎn)的貨物量；(4)表示如果第j 個(gè)倉(cāng)庫(kù)被選中，則它接收的貨物總量不得超過(guò)它的容量；(5)表示工廠和銷(xiāo)售點(diǎn)的貨物總和相等，并且不超過(guò)所有被選中倉(cāng)庫(kù)的總貨物量；(6)和(7)是變量約束[14].

2 算法步驟

由于選址問(wèn)題是NP 困難問(wèn)題，對(duì)原問(wèn)題的解決，我們分為兩個(gè)階段[15].

2.1 第一階段

根據(jù)Floyd 算法把題中Sij(1 ≤i，j ≤N) 轉(zhuǎn)化成cij，cjk(i ＝1，2，..m； j ＝m ＋1，m ＋2，…m ＋s； k ＝m ＋s ＋1，…m ＋s ＋n)，具體算法步驟如下:

①輸入 Sij(i，j ＝1，2，...N)；dij?Sij， pij?j. ( i，j ＝1，2，...N) k?1.

(注:當(dāng)節(jié)點(diǎn)i 與節(jié)點(diǎn)j 不相鄰時(shí)， Sij＝∞； 當(dāng) i ＝j(luò) 時(shí)， Sij＝0)

②若dik＋dkj＝μ ＜dij， 則 dij?μ， pij?pik；

否則(μ≥dij) dij與pij都不變( i，j ＝1，2，...N).

③若k ＜N， 則k?k ＋1 ，轉(zhuǎn)到②； 否則 (k ＝N) 轉(zhuǎn)到④.

④cij?dij， cjk?djk，

( i ＝1， 2，...，m； j ＝m ＋1，..m ＋s； k ＝m ＋s ＋1，...，m ＋s ＋n).

2.2 第二階段

1)先根據(jù)最小元素法求得工廠到倉(cāng)庫(kù)和倉(cāng)庫(kù)到銷(xiāo)售點(diǎn)的初始租賃方案，其中R'j為倉(cāng)庫(kù)的待分配量，bj為倉(cāng)庫(kù)的剩余容量，具體算法步驟如下:

①輸入Pi， Rj，Qk， S?充分大的數(shù)， bj?Rj， P'i?Pi， bk?Qk，

②求min{cij｜i ＝1， 2，...m； j ＝m ＋1，m ＋2，...m ＋s}Δ＝ μ，

否則(bt＝0)，x?0，(i ＝1，2，...m；i≠v).

⑤求min{cjk｜j ＝m ＋1，m ＋2，...m ＋s； k ＝m ＋s ＋1，...m ＋s ＋n} Δ μ

⑥若(R'v＝0)， 則 xvk?0， (k ＝m ＋s ＋1，m ＋s ＋2，...m ＋s ＋n；k≠t)；

否則 (Qt＝0)， 則 xjt?0， (j ＝m ＋1，m ＋2，...m ＋s；j≠v).

2) 對(duì)每一種租賃方案找可降費(fèi)的閉合回路進(jìn)行調(diào)整，在1)的基礎(chǔ)上，直到不能再調(diào)整為止，得最優(yōu)解，具體步驟見(jiàn)⑧-?.

⑧ i ＝1， k ＝m ＋s ＋1.

⑩若 k ＜m ＋s ＋n， k?k ＋1， 轉(zhuǎn)⑨； 否則 ( k ＝m ＋s ＋n)，轉(zhuǎn)?.

?若 i ＜m， i?i ＋1， 轉(zhuǎn)⑨； 否則 (i ＝m)， 轉(zhuǎn)?.

?若j ＜m ＋s， j?j ＋1， 轉(zhuǎn)⑧； 否則 (j ＝m ＋s)， 轉(zhuǎn)?.

?求min {xij，xjk，bt｜xij＞0， xjk＞0， bt＞0，

若S0＜S，則S?S0，轉(zhuǎn)?；否則，轉(zhuǎn)?.

3) 在2)得到解的基礎(chǔ)上，逐個(gè)判斷此時(shí)倉(cāng)庫(kù)Bj(j ＝m ＋1，m ＋2，…m ＋s)的通過(guò)量是否小于其余倉(cāng)庫(kù)的剩余容量總和，若是，逐個(gè)去掉倉(cāng)庫(kù)按步驟②-?，求每一種情況下的最優(yōu)解，然后再判斷此時(shí)的解是否小于原來(lái)的解，若是，有現(xiàn)在的解覆蓋原來(lái)的解，再在剩下的倉(cāng)庫(kù)進(jìn)行判斷，直到不滿(mǎn)足容量限制或不能在降費(fèi)為止，得到的解，就是最后的最優(yōu)解.其中集合D 表示租賃倉(cāng)庫(kù)的位置和個(gè)數(shù)，具體步驟如下:

? j1?m ＋1， D ＝{ j｜ yj＝1， j ＝m ＋1，m ＋2，...m ＋s}.

? 若 j1∈D， 轉(zhuǎn)?， 否則(j1?D)， 轉(zhuǎn)?.

轉(zhuǎn)②； 否則，轉(zhuǎn)?.

? 若 j1＜m ＋s， j1?j1＋1， 轉(zhuǎn)?， 否則 s?s-1， 轉(zhuǎn)?.

? 輸出S0， yj， xij， xjk， (i ＝1，2，...m； j ＝m ＋1，m ＋2，...m ＋s； k ＝m ＋s ＋1，m ＋s ＋2，...m＋s ＋n).

3 算例演示

依據(jù)上述第三部分算法設(shè)計(jì)，編制程序，可計(jì)算任意給定的多工廠多倉(cāng)庫(kù)實(shí)際調(diào)運(yùn)問(wèn)題.根據(jù)某物流公司業(yè)務(wù)情況，列表1 所示的十個(gè)基點(diǎn)中，1、2 表示為工廠，3、4、5 表示為倉(cāng)庫(kù)，其余為用戶(hù)點(diǎn).

表1 算例中給定的數(shù)據(jù)信息Table 1 Data information given in theproblem

假定例中單車(chē)滿(mǎn)載的運(yùn)費(fèi)核算，與實(shí)際工廠、倉(cāng)庫(kù)、用戶(hù)之間的兩點(diǎn)間距離成正比，其中，sij＝θdij(i，j ＝1，2，…，10)，dij表為兩點(diǎn)間的距離，空車(chē)行駛費(fèi)用表示為λsij，給出各點(diǎn)的坐標(biāo)以及對(duì)應(yīng)點(diǎn)車(chē)輛或貨物的車(chē)數(shù).按照第三部分的算法編制程序，取θ ＝0.5、λ ＝0.4 時(shí)，如下表2 為得到的算值:

表2 實(shí)例10 個(gè)節(jié)點(diǎn)的試驗(yàn)結(jié)果Table 2 Example test results for 10 nodes

根據(jù)上表2 中的試驗(yàn)結(jié)果，安排具體的車(chē)輛方案，總運(yùn)費(fèi)計(jì)算結(jié)果為301.029.

采用VRP Web 上實(shí)例p01 至p05 數(shù)據(jù)，擴(kuò)大數(shù)據(jù)規(guī)模，進(jìn)一步地檢驗(yàn)算法適用性，編程實(shí)驗(yàn)，按照依次用完一個(gè)節(jié)點(diǎn)車(chē)輛的方法來(lái)給定初始解，取θ ＝0.5、λ ＝0.4，結(jié)果如表3 所示.

表3 實(shí)例p01 至p05 試驗(yàn)結(jié)果Table 3 Example p01 to p05 test results

P04 (30，30，40) 8 61 1407 1.453 739.8(100) (30，40，30) 7 272 1389 1.609 739.8 P05 (40，40，20) 12 239 968 1.234 576.0(100) (20，40，40) 8 350 858 1.187 477.0

取實(shí)例中有250 個(gè)節(jié)點(diǎn)的p08 至p11 數(shù)據(jù)，為檢驗(yàn)算法在較大規(guī)模時(shí)的性能，結(jié)果如表4 所示.

表4 250 個(gè)節(jié)點(diǎn)的實(shí)例試驗(yàn)結(jié)果Table 4 Example test results for 250 nodes

表4 的結(jié)果表明:在遇到較大規(guī)模問(wèn)題時(shí)，該算法仍然較快地得到了問(wèn)題最優(yōu)解.鑒于該算法是一種精確算法，適用性和穩(wěn)定性好，而且可以具體計(jì)算出車(chē)輛調(diào)運(yùn)的安排方案，這對(duì)當(dāng)前大型物流或者快遞公司的車(chē)輛調(diào)運(yùn)安排問(wèn)題的解決，具有很好的借鑒和參考價(jià)值.

4 結(jié)論與展望

作為一般車(chē)輛路徑問(wèn)題的擴(kuò)展，本文針對(duì)對(duì)有倉(cāng)庫(kù)容量限制，多工廠的三層供應(yīng)關(guān)系的倉(cāng)庫(kù)選址問(wèn)題進(jìn)行了研究，依據(jù)其運(yùn)送特點(diǎn)建立了循環(huán)迭代的精確算法，這種算法在求出工廠到倉(cāng)庫(kù)、倉(cāng)庫(kù)到銷(xiāo)售點(diǎn)最短路徑的前提下，在滿(mǎn)足倉(cāng)庫(kù)容量限制的基礎(chǔ)上，找出可降費(fèi)的閉合回路進(jìn)行調(diào)整，最后再通過(guò)減少倉(cāng)庫(kù)個(gè)數(shù)確定最優(yōu)倉(cāng)庫(kù)個(gè)數(shù)和運(yùn)輸路線，這種算法用計(jì)算機(jī)語(yǔ)言很容易編程實(shí)現(xiàn)，具有計(jì)算速度高，存儲(chǔ)空間少等優(yōu)點(diǎn)，并且在現(xiàn)實(shí)中的問(wèn)題數(shù)據(jù)規(guī)模較大時(shí)，也具備較好的應(yīng)用價(jià)值.

本文研究的三層調(diào)運(yùn)問(wèn)題，在此算法基礎(chǔ)上只需保證相鄰三層節(jié)點(diǎn)間調(diào)整，即可以擴(kuò)展推廣到N(N≥3)層運(yùn)送關(guān)系的網(wǎng)絡(luò)問(wèn)題上.