萬(wàn)鳳嬌

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

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

萬(wàn)鳳嬌

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

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

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

0 引言

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

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

1 模型的建立

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

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

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

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

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

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

1.2 基本假設(shè)

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

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

集合：

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

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

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

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

Fs—表示在s處建立或租用倉(cāng)庫(kù)的固定成本；Fp—表示工廠p的固定成本；

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

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

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

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

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

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

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

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

Ri—表示倉(cāng)庫(kù)i的需求量，i∈S；

A—表示固定訂購(gòu)成本；

hi—表示倉(cāng)庫(kù)i的單位存儲(chǔ)成本，i∈S；

Qi—表示倉(cāng)庫(kù)i的訂貨批量，i∈S。

模型中的決策變量：

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

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

Zr=1，如果在節(jié)點(diǎn)r處建立或租用一個(gè)倉(cāng)庫(kù)（r∈S）；否則，Zr=0；

Yij=1，如果客戶j被分配給倉(cāng)庫(kù)i（i∈S，j∈H）；否則，Yij=0。

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

約束條件為：

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

2 算法設(shè)計(jì)

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

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

2.1 初始化

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

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

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

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

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

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

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

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

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

基于定位-分配階段求解的設(shè)施定位及客戶分配，在算法的第二階段使用蟻群算法求解VRP，通過迭代循環(huán)實(shí)現(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個(gè)倉(cāng)庫(kù)中，并為其分別建立禁忌表；

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

Step 5：令螞蟻禁忌表索引號(hào)k=1；

Step 6：k=k+1；

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

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

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

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

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

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

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

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

3 算例分析

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

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

潛在倉(cāng)庫(kù)和客戶需求節(jié)點(diǎn)之間的距離可以通過下面公式計(jì)算：

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

圖3 潛在倉(cāng)庫(kù)和客戶的位置分布圖

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

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

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

表4 潛在倉(cāng)庫(kù)之間以及與客戶需求點(diǎn)之間的距離/km

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

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

[9］林巖，胡祥培，王旭茵.物流系統(tǒng)優(yōu)化中的定位-運(yùn)輸路線安排問題（LRP）研究綜述[J］.管理工程學(xué)報(bào)，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é)高層次人才科研資助項(xiàng)目 （2010003）

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