多倉庫定位-運(yùn)輸路線安排問題的模型和算法研究

萬鳳嬌

（江漢大學(xué) 商學(xué)院，湖北 武漢 430056）

多倉庫定位-運(yùn)輸路線安排問題的模型和算法研究

萬鳳嬌

（江漢大學(xué) 商學(xué)院，湖北 武漢 430056）

針對現(xiàn)實問題的復(fù)雜性，考慮到單獨研究物流設(shè)施選址和車輛運(yùn)輸路線安排問題的局限性，根據(jù)集成物流管理思想，綜合考慮兩個問題，重點研究了集成物流管理系統(tǒng)中多倉庫定位-運(yùn)輸路線安排問題 （LRP）。首先提出了LRP的數(shù)學(xué)模型，由于LRP屬于NP-hard問題，提出了一種用于求解該類問題的兩階段混合啟發(fā)式算法：禁忌搜索-蟻群混合算法。在選址階段使用禁忌搜索算法求得一個較好的設(shè)施位置后，便轉(zhuǎn)向運(yùn)輸路線安排階段，并采用蟻群算法獲得了一個與已得到的設(shè)施位置相對應(yīng)的優(yōu)化運(yùn)輸路線，這兩階段反復(fù)、連續(xù)運(yùn)算，直到滿足預(yù)先設(shè)置的終止條件。最后，給出算例驗證模型和算法的有效性。

定位—運(yùn)輸路線安排問題；集成物流管理系統(tǒng)；禁忌搜索算法；蟻群混合算法

0 引言

近幾年來出現(xiàn)了一種新的物流管理思想，即集成物流管理思想，此思想充分認(rèn)識到設(shè)施定位、供應(yīng)商和客戶的分配以及運(yùn)輸路線安排問題之間的相互依賴關(guān)系，彌補(bǔ)了單獨研究這些問題所帶來的局限性，避免了配送方案的局部最優(yōu)。物流定位-運(yùn)輸路線安排問題 （Location-Routing Oroblem，LRP）一般表述為：給定了與實際問題相符的一系列客戶點和一系列潛在的設(shè)施點，在這些潛在的節(jié)點中選擇出一系列的設(shè)施位置，同時要確定出從各個設(shè)施到各個客戶點的運(yùn)輸路線，確定的依據(jù)是滿足問題的目標(biāo) （通常是總的費(fèi)用最小）?？蛻艄?jié)點的位置和客戶的需求量是已知的或可估算的，貨物有一個或多個設(shè)施供應(yīng)，每個客戶只接收來自一個設(shè)施的貨物，潛在設(shè)施點位置已知，問題的目標(biāo)是把那些潛在的設(shè)施建立起來，以使總的費(fèi)用最小?？梢姡琇RP是物流選址-配給問題 （Location-Allocation Problem，LAP）與車輛路線安排問題（Vehicle Routing Problem，VRP）的集成，但比后兩者更復(fù)雜。目前關(guān)于LRP的研究比較多。Laporte等[1］研究了隨機(jī)LRP模型，在隨機(jī)LRP模型中僅僅當(dāng)車輛到達(dá)客戶處時才知道其需求量。Madsen[2-3］對求解定位-運(yùn)輸路線集成問題的方法進(jìn)行了分析，后來又給出了有現(xiàn)實維度的兩階段定位-運(yùn)輸路線集成問題的方法。Daskin[4］考慮了隨機(jī)時間的緊急服務(wù)的設(shè)施定位、車輛分配以及路線的選擇問題。Chan等[5］建立了一個多倉庫、多車輛、隨機(jī)需求的定位-運(yùn)輸路線問題的數(shù)學(xué)模型，并給出求解的數(shù)學(xué)方法。Wu等[6］研究多倉庫定位-運(yùn)輸路線問題，在所建立的模型中考慮了車輛派遣費(fèi)用和不同車輛具有不同運(yùn)載能力的約束，把LRP問題分解為物流選址-配給問題和車輛路線安排問題。國內(nèi)對定位-運(yùn)輸路線安排問題的研究是在20世紀(jì)90年代后期才慢慢開始興起，比國外滯后了30多年。目前對物流優(yōu)化方面的研究還主要局限于對LAP和VRP的單獨研究。汪壽陽、張潛、林巖等[7-9］是在國內(nèi)較早開始研究LRP問題的學(xué)者，在其論文中對LRP問題的發(fā)展及其優(yōu)化算法進(jìn)行了綜述。另外，張潛等[10］重點研究了集成化物流中一類特殊的定位-運(yùn)輸路線安排問題的兩階段啟發(fā)式算法。

上述研究成果為集成物流管理系統(tǒng)的選址-選線問題的研究奠定了基礎(chǔ)，但是多數(shù)研究成果僅考慮單級物流系統(tǒng)。本文則考慮多倉庫的二級物流系統(tǒng)，對相關(guān)成本進(jìn)行細(xì)化，以使相關(guān)模型得到進(jìn)一步拓展，并給出了求解該問題的啟發(fā)式算法。

1 模型的建立

目前對LRP的研究有很多種，傳統(tǒng)的LRP模型所基于的物流網(wǎng)路是單級。本文研究的物流網(wǎng)絡(luò)為典型的二級結(jié)構(gòu)的網(wǎng)絡(luò)，包括一個工廠、多個倉庫和多個客戶（見圖1），研究的問題為多倉庫LRP問題。

圖1 典型的兩級設(shè)施的LRP

1.1 模型的目標(biāo)分析

1.1.1 總成本最低 要合理安排集成物流系統(tǒng)中的各個環(huán)節(jié)以實現(xiàn)總成本最低。本文研究的LRP問題的總成本包括工廠的固定費(fèi)用、倉庫的建立和庫存成本，以及車輛的指派成本和運(yùn)輸成本。

1.1.2 滿足客戶的要求 在模型中我們考慮客戶的需求是確定的，在供貨期內(nèi)合理地安排路徑，盡可能地滿足客戶的需求。

1.1.3 準(zhǔn)時到達(dá) 近年來，出現(xiàn)了準(zhǔn)時制（JIT）的概念，JIT不僅作為一種生產(chǎn)方式，也作為一種通用管理模式在物流、電子商務(wù)等領(lǐng)域得到推行。它要求貨物要按照客戶的需要準(zhǔn)時到達(dá)，以提高物流服務(wù)質(zhì)量，減少庫存成本。

1.2 基本假設(shè)

在構(gòu)建模型時，本研究對模型做了以下假設(shè)：①假設(shè)工廠的位置是固定的，倉庫的位置是不確定的，需要從給定的潛在倉庫中確定出合適的倉庫；②有多個潛在的倉庫，要求每個倉庫供應(yīng)多個客戶的需求；③ 客戶的需求為單一品種的商品，規(guī)格和價值相同；④每個客戶僅能由一輛車和一個倉庫為其提供服務(wù)；⑤ 運(yùn)輸車輛為同一類型，且每輛車在完成每次運(yùn)輸任務(wù)后返回到出發(fā)點；⑥每條巡回運(yùn)輸路線上的客戶總需求不能超過車輛的載重能力；⑦ 假設(shè)車輛的行駛速度服從已知的連續(xù)分布；⑧ 假設(shè)客戶需求是確定的；⑨ 考慮貨物的相關(guān)成本包括貨物本身的成本、訂購成本和庫存成本；⑩不考慮缺貨成本。

1.3 模型參數(shù)及決策變量

集合：

S—系統(tǒng)中所有潛在倉庫的節(jié)點集合，S=｛1，2，3，…，s｝；

H—系統(tǒng)中所有客戶節(jié)點的集合，H=｛s+ 1，s+2，…，s+h｝；

K—系統(tǒng)中所有運(yùn)輸車輛的集合，K=｛1，2，…，k｝；

G—所有的倉庫和客戶的集合，G=S∪H。參數(shù)：

Fs—表示在s處建立或租用倉庫的固定成本；Fp—表示工廠p的固定成本；

Cpi—表示工廠p到倉庫i的單位運(yùn)輸費(fèi)用，i∈S；

ypi—表示工廠p到倉庫i的運(yùn)量，i∈S；

C1—表示單位距離運(yùn)輸成本；

dij—表示節(jié)點i到節(jié)點j間距離，i，j∈G；

Ck—表示使用運(yùn)輸車輛k的固定成本，k∈K；

Qk—表示運(yùn)輸車輛k的容量，k∈K；

C2—表示貨物的單位成本；

qj—表示客戶j的需求量，j∈H；

Ri—表示倉庫i的需求量，i∈S；

A—表示固定訂購成本；

hi—表示倉庫i的單位存儲成本，i∈S；

Qi—表示倉庫i的訂貨批量，i∈S。

模型中的決策變量：

xijk=1，如果運(yùn)輸車輛k經(jīng)過節(jié)點i到節(jié)點j（i，j∈G，i≠j，k∈K）；否則，xijk=0；

Wpi=1，如果貨物由工廠p運(yùn)至節(jié)點i（i∈S）；否則，Wpi=0；

Zr=1，如果在節(jié)點r處建立或租用一個倉庫（r∈S）；否則，Zr=0；

Yij=1，如果客戶j被分配給倉庫i（i∈S，j∈H）；否則，Yij=0。

1.4 數(shù)學(xué)模型

約束條件為：

（1）式為目標(biāo)函數(shù)，保證整個物流系統(tǒng)的總費(fèi)用最小 （包括設(shè)施固定費(fèi)用、車輛運(yùn)輸費(fèi)用和庫存費(fèi)用）；（2）式保證每一個客戶僅由一輛車輛提供服務(wù)； （3）式為車輛容量約束，保證車輛承擔(dān)的客戶需求不超過車輛的容量；（4）式表示路線連續(xù)約束，即表示在一條路線上對每一個節(jié)點的貨物來說由同一輛車運(yùn)出；（5）式保證每輛車只為一個倉庫服務(wù)；（6）式表示一個客戶只能分配給一個倉庫； （7）式表示只有當(dāng)倉庫開放時，才能給其分配客戶； （8）式保證只有運(yùn)輸路線經(jīng)過了客戶節(jié)點，客戶節(jié)點才可以被指派給倉庫節(jié)點； （9）式保證在任意兩個倉庫之間無連接；（10）式和（11）式保證了每一運(yùn)輸車輛的行駛源于一個倉庫且只能有一個起點； （12）式保證兩個倉庫不會在同一個行車路線上； （13）～（16）式保證決策變量為整數(shù)。

2 算法設(shè)計

在啟發(fā)式算法中，禁忌搜索算法具有全局尋優(yōu)能力，而且比較容易實現(xiàn)，但其局部搜索性能易受分散性的影響。蟻群算法引入正反饋并行機(jī)制，具有較強(qiáng)的魯棒性、優(yōu)良的分布式計算機(jī)制，易于與其他方法結(jié)合的優(yōu)點，但其全局優(yōu)化性能的優(yōu)劣在很大程度上與蒸發(fā)系數(shù)的選擇有關(guān)，如選擇得不合適易使算法陷于局部最優(yōu)。因此，本文將兩種方法組合在一起，可以彌補(bǔ)各自的不足，充分發(fā)揮其長處。根據(jù)所建立的LRP數(shù)學(xué)模型的特點，采用禁忌搜索-蟻群混合算法對問題進(jìn)行求解。

為了有效求解多倉庫LRP，根據(jù)問題的不同決策變量，將其分解為LAP和VRP兩個子問題分別求解。由于僅僅有一些路段會隨著倉庫位置的改變而發(fā)生變化，因此，可以將搜索限制在這些路段內(nèi)。所以，車輛路線安排階段實際上是局部搜索，而不是移動所有線路的全局搜索，這就會消除很多不必要的計算，并允許兩階段算法在合理的計算時間內(nèi)求得較優(yōu)解。

2.1 初始化

由于禁忌搜索算法都是以初始解開始的，所以在進(jìn)行計算之前需要先計算初始解。由于禁忌搜索算法對初始解的依賴性較強(qiáng)，一個較好的初始解可使禁忌搜索在解空間中搜索到更好的解，而一個較差的初始解則會降低搜索的收斂速度和搜索質(zhì)量。為此，我們使用貪婪取走啟發(fā)式算法（Greedy—Drop Heuristic Algorithm）獲得一個較好的初始解，來提高算法的性能。Greedy—Drop的基本思想是從所有候選選址點中，逐個將對目標(biāo)函數(shù)影響最小的選址點去掉直到剩余的選址點只剩下m個。

2.2 定位——分配階段（LAP)

初始解確定了所選的倉庫節(jié)點以及每個倉庫節(jié)點所服務(wù)的客戶，采用禁忌搜索算法改進(jìn)初始解，得到一個當(dāng)前較好解。設(shè)定N為網(wǎng)絡(luò)中所有n個潛在候選倉庫節(jié)點的集合，S為所選點集，N（S）=｛S1，S2，…，Sp（n-p）｝為與之相對應(yīng)的領(lǐng)域，p為給定的選址數(shù)量。最后我們令tabu_tag（i）表示節(jié)點i所處的禁忌狀態(tài)，如tabu_tag（i）=t表示節(jié)點i在接下去的t步內(nèi)將處于禁忌狀態(tài)。

第一階段：采用貪婪取走啟發(fā)式算法（Greedy—Drop Heuristic Algorithm）獲得初始解。

第二階段：采用禁忌搜索改進(jìn)算法。

Step 1：輸入算法的運(yùn)行參數(shù)，包括終止迭代步數(shù)T，每次迭代搜索當(dāng)前解的鄰居的個數(shù)M，禁忌長度l，對不可行方案的懲罰函數(shù)Pw等；初始化迭代步數(shù)、禁忌狀態(tài)和禁忌表，令t= 0，tabu_tag（i）=0，H=φ；確定當(dāng)前最好解S0，令S0=S，利用解的評價方法計算S的評價值E。

Step 2：對當(dāng)前最好解S用兩兩交換法 （2-Swap）實施領(lǐng)域操作，如果兩交換的點不是禁忌表H中的元素，則得到S的一個領(lǐng)域S*，利用解的評價方法計算解S*的評價值E*，然后采用蟻群算法求解路徑安排問題，更新禁忌表。

Step 3：判斷是否滿足終止迭代步數(shù)T。如果滿足，輸出結(jié)果，算法停止。否則，繼續(xù)Step 2。

2.3 車輛路線安排階段（VRP)

基于定位-分配階段求解的設(shè)施定位及客戶分配，在算法的第二階段使用蟻群算法求解VRP，通過迭代循環(huán)實現(xiàn)算法中兩階段搜索的協(xié)調(diào)，直到滿足預(yù)先設(shè)置的終止條件。根據(jù)蟻群算法的基本原理，求解VRP的蟻群算法的基本步驟如下：

Step 1：初始化參數(shù)。設(shè)循環(huán)次數(shù)Nc=0，最大循環(huán)次數(shù)Nmax為一常數(shù)，令路徑（i，j）的初始信息量τij（t）=const（const為常數(shù)），禁忌表tabuk=φ；

Step 2：采用最近鄰域法獲得初始解；

Step 3：將m只螞蟻隨機(jī)放在n個倉庫中，并為其分別建立禁忌表；

Step 4：循環(huán)次數(shù)Nc=Nc+1；

Step 5：令螞蟻禁忌表索引號k=1；

Step 6：k=k+1；

Step 7：對于m只螞蟻，在候選節(jié)點集中，根據(jù)狀態(tài)轉(zhuǎn)移概率公式選擇下一個客戶節(jié)點j，j∈｛allowk-tabuk｝；

Step 8：計算線路上的載重量q，若q＜Q（Q為車輛的額定載重量），則轉(zhuǎn)至下一步，否則將節(jié)點j重新放回到可選客戶點集allowk中；

Step 9：判斷可選客戶集allowk，若allowk=φ，則轉(zhuǎn)至下一步；若沒有訪問完可選客戶集合allowk中的所有點，即k＜m，則從allowk中選擇未被搜索的點，跳轉(zhuǎn)至Step 6，搜索下一個節(jié)點；

Step 10：當(dāng)m只螞蟻選擇到下一個節(jié)點后，對其所走過的路徑，根據(jù)公式τijnew=（1-ρ）τijold+ ρτ0（τ0為路徑上信息量的初始值）進(jìn)行信息素的局部更新和信息素增量τij的更新；

Step 11：計算每只螞蟻搜索的最短路徑的長度，若k=m，則進(jìn)行信息素的全局更新；

Step 12：判斷循環(huán)次數(shù)Nc是否大于最大循環(huán)次數(shù)Nmax；若滿足約束條件，則循環(huán)結(jié)束，輸出計算結(jié)果；否則，清空禁忌表，并跳轉(zhuǎn)至Step 3。

物流定位-運(yùn)輸路線安排問題的算法流程圖如圖2所示。

圖2 物流定位-運(yùn)輸路線安排問題算法流程圖

3 算例分析

設(shè)計一個基本算例。假設(shè)某二級結(jié)構(gòu)物流網(wǎng)絡(luò)中，有1個工廠，6個潛在倉庫，30個客戶需求點，工廠P的坐標(biāo)位置為（42，195），工廠P的固定費(fèi)用為9 500元，工廠P到倉庫Di（i=1，2，…，6）之間的單位運(yùn)輸費(fèi)用如表1所示，潛在倉庫和客戶需求點的位置坐標(biāo)（x，y）在200×200的范圍內(nèi)隨機(jī)分布（見圖3）。潛在倉庫的坐標(biāo)位置及其固定費(fèi)用如表2所示，客戶的需求量如表3所示。潛在倉庫之間以及與客戶需求點之間的距離見表4所示。潛在倉庫到各客戶需求點以及各客戶需求點之間的單位距離運(yùn)輸費(fèi)用為1元，車輛的額定載重量為2.5 t，車輛平均行駛速度為70 km/h，使用車輛的固定成本為600元，貨物的單位成本為0.25元，固定訂購成本為20元，hi為24%。

表1 工廠到倉庫之間的單位運(yùn)輸費(fèi)用 /（元·kg-1）

潛在倉庫和客戶需求節(jié)點之間的距離可以通過下面公式計算：

在此，我們采用兩階段禁忌搜索—蟻群混合算法對該算例進(jìn)行求解，參數(shù)設(shè)置如下：

圖3 潛在倉庫和客戶的位置分布圖

表2 潛在倉庫的坐標(biāo)位置及其固定費(fèi)用

①禁忌搜索的交換操作的最大次數(shù)為9；②禁忌表長度為9；③禁忌搜索的最大迭代次數(shù)為50次；④螞蟻的個數(shù)與客戶的個數(shù)相同；⑤信息素重要程度的參數(shù)α=1.0；⑥啟發(fā)式因子重要程度的參數(shù)β=1.0；⑦信息素蒸發(fā)系數(shù)ρ=0.9；⑧信息素增加強(qiáng)度系數(shù)Q=0.5；⑨蟻群算法的迭代次數(shù)為50次。

表3 客戶需求點的坐標(biāo)位置、需求量

表4 潛在倉庫之間以及與客戶需求點之間的距離/km

仿真計算，使用MATLAB7.0編程實現(xiàn)。經(jīng)過計算后，得到目標(biāo)函數(shù)的最優(yōu)解為43 088.77元。其選址與選線安排如圖4，算法的平均解隨迭代次數(shù)變化的趨勢如圖5，算法的最優(yōu)解隨迭代次數(shù)的變化趨勢如圖6。

圖4 選址選線運(yùn)行路線圖

圖5 平均解隨迭代次數(shù)的變化趨勢

圖6 最優(yōu)解隨迭代次數(shù)的變化趨勢

經(jīng)過計算，選定的倉庫和倉庫所服務(wù)的客戶見表5，最優(yōu)運(yùn)輸路線見表6。

表5 設(shè)施選址階段（LAP)的解

表6 運(yùn)輸路線優(yōu)化階段（VRP)的解

4 結(jié)語

本文給出多倉庫定位-運(yùn)輸路線安排問題的數(shù)學(xué)模型，并提出了采用兩階段禁忌搜索-蟻群混合算法求解該LRP問題。將LRP問題分解成兩個子問題分別求解，即選址定位問題和路線安排問題，在定位階段使用禁忌搜索算法得到一個好的設(shè)施選址結(jié)構(gòu)后，便轉(zhuǎn)向運(yùn)輸路線安排階段，并使用蟻群算法獲得了一個與已得到的選址結(jié)構(gòu)相對應(yīng)的優(yōu)化運(yùn)輸路線，這兩階段反復(fù)、連續(xù)運(yùn)算，直到滿足預(yù)先設(shè)置的終止條件。此禁忌搜索-蟻群混合算法可以在一定程度上克服單一啟發(fā)式算法在局部搜索能力方面的不足，從而能得到比其他啟發(fā)式算法更好地計算結(jié)果。最后，通過算例分析進(jìn)一步驗證了該算法的有效性和可行性。因此，本文提出的兩階段混合啟發(fā)式算法為解決集成物流管理系統(tǒng)中的LRP問題求解提供了新的方法。后續(xù)進(jìn)一步的研究將考慮缺貨成本對于系統(tǒng)總成本的影響。

[1］Laporte G，Louveaux F，Mercure H.Models and exact solutions for a class of stochastic location-routing problems[J］.European Journal of Operational Research，1989，39：71-78.

[2］Madsen O B G.A survey of methods for solving combined location-routing methods[M］//Jaiswal N K.Scientific Management of Transport Systems.North-Holland：Amsterdam，1981：194-201.

[3］Madsen O B G.Methods for solving combined two level location-routing problems of realistic dimensions[J］. European Journal of Operational Research，1983，12：295-301.

[4］Daskin M S.Location，dispatching，and routing models for emergency services with stochastic travel times [M］//Ghosh A，Rushton G.Spatial analysis and location-allocation models.New York：Von Nostrand Reinhold Company，1987：224-265.

[5］Chan Y，Carter W B，Burnes M D.A multiple-depot，multiple-vehicle，location-routing problem with stochastically processed demands[J］.Computers& Operations Research，2001，28：803-826.

[6］Wu T H，Low C Y，Bai J W.Heuristic solutions to multi-depot location-routing problems[J］.Computers &Operations Research，2002，29：1393-1415.

[7］汪壽陽，趙秋紅，夏國平.集成物流管理系統(tǒng)中的定位-運(yùn)輸路線安排問題的研究 [J］.管理科學(xué)學(xué)報，2000，3（2）：69-74.

[8］張潛，高立群，胡祥培.集成化物流中的定位-運(yùn)輸路線安排問題（LRP）優(yōu)化算法評述[J］.東北大學(xué)學(xué)報，2003，24（1）：31-34.

[9］林巖，胡祥培，王旭茵.物流系統(tǒng)優(yōu)化中的定位-運(yùn)輸路線安排問題（LRP）研究綜述[J］.管理工程學(xué)報，2004，18（4）：45-49.

[10］張潛，高立群，劉雪梅，等.定位-運(yùn)輸路線安排問題的兩階段啟發(fā)式算法[J］.控制與決策，2004，19（7）：773-777.

WAN Feng-jiao
（School of Business，Jianghan University，Wuhan 430056，Hubei，China）

Considering the complication of the realistic problem and the limitation of research into locations-routing problem of logistics separately and integrated logistics，the paper studies location-routing problem including multi-depot in integrated logistics.Model of LRP is given on the basis of some hypotheses.Because LRP is NP-hard problem，a two-phase heuristic approach for solving the LRP is proposed.In location-allocation phase，after the candidate facilities and their customers are determined by using taboo-search algorithm，vehicle routing phase is assorted to by adopting ant colony algorithm to search the optimal routes.These two phases operate repeatedly and continuously until meeting the condition of termination.At last，the dissertation gives an example to illustrate the model and algorithm effectiveness.

location-routing problem；integrated logistics；taboo-search algorithm；ant colony algorithm

F252；O224

：A

：1673-0143（2012）03-0026-07

（責(zé)任編輯：強(qiáng)士端）

2012-02-15

江漢大學(xué)高層次人才科研資助項目 （2010003）

萬鳳嬌 （1981—），女，講師，博士生，研究方向：物流系統(tǒng)規(guī)劃與管理。