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

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

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

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

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

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

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

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

研究:如何選擇工廠到倉庫的運輸線路，倉庫到銷售點的運輸線路，才可使所有貨物從工廠運送到倉庫再到銷售點的總成本最低(總成本包括倉庫租賃費和貨物運輸費用)?

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

其中:xij＞0 表示第i 個工廠向第j 個倉庫運輸貨物，且運量為xij，xij＝0 表示第i 個工廠向第j 個倉庫無運量；同理，xjk＞0 表示第j 個倉庫向第k 個銷售點運輸貨物，且運量為xjk，xjk＝0 表示第j 個倉庫向第k 個銷售點無運量.

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

2 算法步驟

由于選址問題是NP 困難問題，對原問題的解決，我們分為兩個階段[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.

(注:當節(jié)點i 與節(jié)點j 不相鄰時， Sij＝∞； 當 i ＝j(luò) 時， 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ù)最小元素法求得工廠到倉庫和倉庫到銷售點的初始租賃方案，其中R'j為倉庫的待分配量，bj為倉庫的剩余容量，具體算法步驟如下:

①輸入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) 對每一種租賃方案找可降費的閉合回路進行調(diào)整，在1)的基礎(chǔ)上，直到不能再調(diào)整為止，得最優(yōu)解，具體步驟見⑧-?.

⑧ 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ǔ)上，逐個判斷此時倉庫Bj(j ＝m ＋1，m ＋2，…m ＋s)的通過量是否小于其余倉庫的剩余容量總和，若是，逐個去掉倉庫按步驟②-?，求每一種情況下的最優(yōu)解，然后再判斷此時的解是否小于原來的解，若是，有現(xiàn)在的解覆蓋原來的解，再在剩下的倉庫進行判斷，直到不滿足容量限制或不能在降費為止，得到的解，就是最后的最優(yōu)解.其中集合D 表示租賃倉庫的位置和個數(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è)計，編制程序，可計算任意給定的多工廠多倉庫實際調(diào)運問題.根據(jù)某物流公司業(yè)務(wù)情況，列表1 所示的十個基點中，1、2 表示為工廠，3、4、5 表示為倉庫，其余為用戶點.

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

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

表2 實例10 個節(jié)點的試驗結(jié)果Table 2 Example test results for 10 nodes

根據(jù)上表2 中的試驗結(jié)果，安排具體的車輛方案，總運費計算結(jié)果為301.029.

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

表3 實例p01 至p05 試驗結(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

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

表4 250 個節(jié)點的實例試驗結(jié)果Table 4 Example test results for 250 nodes

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

4 結(jié)論與展望

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

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