有容量限制的倉庫選址及調(diào)運(yùn)問題研究

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

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

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

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

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

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

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

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

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

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

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

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

2 算法步驟

由于選址問題是NP 困難問題，對(duì)原問題的解決，我們分為兩個(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ù)最小元素法求得工廠到倉庫和倉庫到銷售點(diǎn)的初始租賃方案，其中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) 對(duì)每一種租賃方案找可降費(fèi)的閉合回路進(jìn)行調(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ǔ)上，逐個(gè)判斷此時(shí)倉庫Bj(j ＝m ＋1，m ＋2，…m ＋s)的通過量是否小于其余倉庫的剩余容量總和，若是，逐個(gè)去掉倉庫按步驟②-?，求每一種情況下的最優(yōu)解，然后再判斷此時(shí)的解是否小于原來的解，若是，有現(xiàn)在的解覆蓋原來的解，再在剩下的倉庫進(jìn)行判斷，直到不滿足容量限制或不能在降費(fèi)為止，得到的解，就是最后的最優(yōu)解.其中集合D 表示租賃倉庫的位置和個(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ì)算任意給定的多工廠多倉庫實(shí)際調(diào)運(yùn)問題.根據(jù)某物流公司業(yè)務(wù)情況，列表1 所示的十個(gè)基點(diǎn)中，1、2 表示為工廠，3、4、5 表示為倉庫，其余為用戶點(diǎn).

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

假定例中單車滿載的運(yùn)費(fèi)核算，與實(shí)際工廠、倉庫、用戶之間的兩點(diǎn)間距離成正比，其中，sij＝θdij(i，j ＝1，2，…，10)，dij表為兩點(diǎn)間的距離，空車行駛費(fèi)用表示為λsij，給出各點(diǎn)的坐標(biāo)以及對(duì)應(yīng)點(diǎn)車輛或貨物的車數(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é)果，安排具體的車輛方案，總運(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)車輛的方法來給定初始解，取θ ＝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ī)模問題時(shí)，該算法仍然較快地得到了問題最優(yōu)解.鑒于該算法是一種精確算法，適用性和穩(wěn)定性好，而且可以具體計(jì)算出車輛調(diào)運(yùn)的安排方案，這對(duì)當(dāng)前大型物流或者快遞公司的車輛調(diào)運(yùn)安排問題的解決，具有很好的借鑒和參考價(jià)值.

4 結(jié)論與展望

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

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