物流系統(tǒng)優(yōu)化中定位一運輸路線安排問題

(LRP)研究評述*

摘要本文概述了物流優(yōu)化問題中定位一運輸路線

安排問題(Location-RoutingProblems,LRP)發(fā)展

歷程，并對LRP分類和處理方法加以評述，最終就

這一問題發(fā)展方向進行簡單地探討。

關(guān)鍵詞LRP物流系統(tǒng)優(yōu)化運籌學

1引言

新技術(shù)快速發(fā)展，尤其是電子商務(wù)風起云涌，為中國經(jīng)濟

快速發(fā)展提供了契機。現(xiàn)在中國電子商務(wù)得到政府和民眾支

持，發(fā)展勢頭強勁，不過，因為它是一套全新技術(shù)，同時還

是一個全新管理理念，所以其發(fā)展過程中肯定存在部分難

題。在電子商務(wù)“三流”(信息流、物流、資金流)中，伴

隨網(wǎng)絡(luò)基礎(chǔ)設(shè)施建設(shè)成熟、電子商務(wù)網(wǎng)站蓬勃發(fā)展和有效利

?國家自然科學基金關(guān)鍵項目(70031020)

用網(wǎng)絡(luò)資源觀念普及，信息流發(fā)展已經(jīng)比較成熟了；而伴隨

各大銀行紛紛開展網(wǎng)上業(yè)務(wù)，和支付網(wǎng)關(guān)建立和加密技術(shù)成

熟，網(wǎng)上支付已經(jīng)在很多網(wǎng)站上成為現(xiàn)實；然而，中國傳統(tǒng)

物流體系是在計劃經(jīng)濟環(huán)境下建立、發(fā)展起來，和現(xiàn)在電子

商務(wù)環(huán)境已經(jīng)無法相容?，F(xiàn)今物流體系落后現(xiàn)實狀況已經(jīng)成

為中國社會經(jīng)濟快速發(fā)展關(guān)鍵制約原因之一。所以對物流系

統(tǒng)優(yōu)化研究將會含有很大現(xiàn)實意義。

國外很多學者在電子商務(wù)出現(xiàn)之前就已經(jīng)研究物流系統(tǒng)

優(yōu)化問題了，為各類實際問題構(gòu)建了優(yōu)化模型，并形成了很

多處理問題算法C依據(jù)實際問題不一樣，能夠?qū)ξ锪飨到y(tǒng)優(yōu)

化問題進行分類，比如，運輸車輛路線安排問題（VRP）、定

位一配給問題（LA）、定位一運輸路線安排問題（LRP）等等,

其中LRP更貼近現(xiàn)在物流系統(tǒng)復(fù)雜實際特征，所以對它研究

是十分有意義。

本文先從VRP和LA集成來探討LRP由來，然后討論LRP

分類，同時探討LRP研究現(xiàn)實狀況，并對LRP處理方法進行

概述，最終就LRP未來發(fā)展方向作簡明討論。

2從VRPvLA到LRP——物流系統(tǒng)集成

依據(jù)實際問題不一樣，能夠?qū)ξ锪飨到y(tǒng)優(yōu)化問題進行分類,

比如確定設(shè)施（指是物品流動出發(fā)點和終到點，如配送中心、

倉庫、生產(chǎn)工廠、垃圾回收中心等）位置、運輸路線安排、

庫存控制等，中國外很多學者就各類問題特征進行了分析,

并提出了各類問題數(shù)學模型和處理方法。

2.1運輸車輛路線安排問題（VehicleRoutingProblems

VRP）

該問題可定義為：運輸車輛從一個或多個設(shè)施到多個地理上

分散用戶點，優(yōu)化設(shè)計一套貨物流動運輸路線，同時要滿足

一系列約束條件C該問題前提條件是設(shè)施位置、用戶點位置

和道路情況已知，由此確定一套車輛運輸路線，以滿足目標

函數(shù)（通常,VRP目標函數(shù)是總費用最?。D1所表示。

物品質(zhì)確保O

■具體時間限制：對某個用戶點，車輛抵達時間限制

在某一時間段內(nèi)。此約束在于滿足用戶對供給/回收特殊要

求。

■車輛抵達次序要求：如在抵達i點之前要求先

抵達j點。

以上列出約束只是該問題一部分，具體操作時要視具體

情況而定。

對VRP求解算法可分為正確算法和啟發(fā)式算法兩種。其

中正確算法包含樹狀尋優(yōu)算法、動態(tài)計劃和整數(shù)計劃。VRP

啟發(fā)式算法多是起源于對TSP問題求解算法。比如局部優(yōu)先

算法、插值法等能夠不用修改地用于部分VRP。

2.2定位一配給問題(Location-AllocationProblems,LA)

定位一配給問題可定義為：依據(jù)用戶點地理分布和貨物

分配關(guān)系，確定出某一地理范圍內(nèi)設(shè)施數(shù)量和位置。圖2所

表示。

圖中，口表示設(shè)施；O表示用戶；K表示運輸路線

圖2LA圖不

LA實質(zhì)上是一個依據(jù)優(yōu)化路徑標準來確定在什么地方設(shè)

置設(shè)施過程［2］。比如，在一個城鎮(zhèn)中設(shè)置一個搶救中心，這

個問題就是一個經(jīng)典LA問題。它目標就是使得全鎮(zhèn)居民到

醫(yī)療中心路徑（時間）總體上最短。

依據(jù)JohnCurrent等學者對此問題綜述研究［3］,把LA問

題進行了分類。Current方法是依據(jù)問題目標函數(shù)來分類，作

為分類依據(jù)目標函數(shù)共分四種：

(1)費用最小化；

(2)用戶需求導(dǎo)向；

(3)利潤最大化；

(4)其它相關(guān)考慮。

2.3定位一運輸路線安排問題(Location-Routing

problems,LRP)

當今物流系統(tǒng)環(huán)境日趨復(fù)雜，而且物流地理分布也不停

擴大。物流系統(tǒng)優(yōu)化問題各個子系統(tǒng)(比如設(shè)施定位問題、

物品配送問題、運輸車輛路線安排問題等)之間相互影響也

越來越大。對很多實際問題，要綜合考慮以上問題，這就形

成了定位一路線安排問題(LRP)。

LRP能夠表述為：給定和實際問題相符一系列用戶點和一系

列潛在設(shè)施點，在這些潛在點中確定出一系列設(shè)施位置，同

時要確定出一套從各個設(shè)施到各個用戶點運輸路線，確定依

據(jù)是滿足問題目標(通常是總費用最小)。用戶點位置和用

戶需求量是已知或可估算，貨物有一個或多個設(shè)施供給，每

個用戶只接收來自一個設(shè)施貨物，潛在設(shè)施點位置已知，問

題目標是把哪些潛在設(shè)施建立起來，以使總費用最小。LRP

可圖不為圖3。

能夠說LRP是LA和VRP集成⑷，但比后二者更復(fù)雜。LA

在定位時考慮是運輸車輛從設(shè)施點到一個用戶點后，隨即返

回設(shè)施點，所以它不考慮路線安排問題［5］。LA在確定出設(shè)

施點后圖形是從設(shè)施點到用戶點射線族。而LRP則在定位時

同時確定運輸路線。LRP和VRP不一樣之處是：VRP前提

條件是設(shè)施點和用戶點在空間上分布是已知；LRP所研究問

題只知道潛在設(shè)施點，在確定運輸路線同時要確定設(shè)施位

置。

△

OO

△

圖中，口表示設(shè)施；△表示未被選中設(shè)施；O表示用戶點；

7表示運輸路線

圖3LRP圖示

在實際物流系統(tǒng)集成特征日益突出之前，就已經(jīng)有些人

研究LRP了。最早研究能夠追溯到20世紀60年代，當初有

些學者已經(jīng)提出部分類似概念了[6-8]。到了70年代,

Cooper[9,10]把定位問題和運輸問題結(jié)合起來，提出了運輸

一定位問題(Transportation-Locationproblem)。在這個階段,

學者們對LRP研究還是相當膚淺，還沒有真正包含運輸路線

安排問題。到了70年代中期，部分學者在研究運輸一定位問

題時，開始加入VRP多點運輸特征，Watson-Gandy和

Dohrn[ll]是最早進行這方面工作學者。直到70年代末，80

年代初，才開始有了真正意義LRP[12-14]o這些研究結(jié)果是

伴伴隨集成物流系統(tǒng)概念出現(xiàn)而出現(xiàn)。

3LRP分類

HokeyMin等學者對LRP進行了具體分類[15],其分類標準

十分詳盡，幾乎包含了LRP各個方面。

表1LRP分類標準

分類標準AB

1物品流向單向雙向

2供/需特征確定隨機

3設(shè)施數(shù)量單個設(shè)施多設(shè)施

4運輸車輛數(shù)單個車輛多車輛

量

5車輛裝載能不確定確定

力

6設(shè)施容量不確定確定

7設(shè)施分級單級多級

8計劃期間單期多期

9時間限制無時間限制有時間限制

10目標數(shù)單目標多目標

11模型數(shù)據(jù)類假設(shè)值實際值

型

Hokey分類是依據(jù)問題特征進行，具體如表lo

表1中，各分類標準解釋以下：

（1）物品流向，單向物品流向問題指是全部設(shè)施只進行

輸入（供給）或只進行輸出（回收）操作；而雙向物品流向

問題包含設(shè)施中有一部分既要輸入又要輸出。

（2）供/需特征，確定型是指物品供給/需求量是已知并

在一定時期內(nèi)相對穩(wěn)定；隨機型是指供給/需求量是不確定。

（3）設(shè)施數(shù)量，指所研究問題要求設(shè)置設(shè)施數(shù)量,分為

單一設(shè)施和多設(shè)施兩種。

（4）運輸工具數(shù)量，是指有多少車輛為一個設(shè)施服務(wù)標

準，同時也確定了一個從設(shè)施出發(fā)路線數(shù)。分為單一車輛和

多車輛兩種。

（5）車輛裝載能力，是指是否要考慮車輛裝載能力限

制。不確定定型是指對這個問題所包含每條路線上貨物總量

很小，不會超出車輛裝載量，所以不用考慮車輛裝載能力限

制；確定型是指每條路線上貨物總量有可能超出車輛裝載能

力，所以要把車輛裝載限制作為一個參數(shù)引入問題。

（6）設(shè)施容量，是指是否考慮各個設(shè)施容量限制。分為

不確定型和確定型兩種。

（7）設(shè)施分級，能夠把設(shè)施分為兩種：總站型和中間轉(zhuǎn)

運站型。總站型設(shè)施是指那些車輛路線出發(fā)點或終點；中間

轉(zhuǎn)運站型設(shè)施是指物品中間站，貨物運入后還要運出。有了

中間轉(zhuǎn)運站，就產(chǎn)生了設(shè)施分級問題，貨物從總站型設(shè)施運

入中間轉(zhuǎn)運站型設(shè)施，經(jīng)過簡單處理后運到用戶點。單級設(shè)

施問題是指不考慮設(shè)施分級，全部設(shè)施均為同級；而多級中

心設(shè)施問題則要考慮設(shè)施分級。

（8）計劃期間，單期間問題把整個期間作為一個時間段,

是靜態(tài)問題；多期間問題把整個時間段按問題要求分為多個

期間，是動態(tài)問題。

（9）時間限制，關(guān)鍵是指滿足用戶要求或貨物品質(zhì)要求,

而對LRP從設(shè)施點到用戶點時間約束。分為無時間約束和有

時間約束:兩種。

（10）目標數(shù)量,LRP目標通常是總費用（包含建設(shè)設(shè)施費

用和車輛運輸費用等）最小，但有時也需要考慮其它目標,

比如滿足用戶特殊需要、總體利潤量大化等等。假如是多目

標問題，常常會出現(xiàn)各目標之間沖突。

（11）模型數(shù)據(jù)類型，在有些情況下，模型中數(shù)據(jù)（如物品

供/需量等）是起源于實際；而有些情況下，這些數(shù)據(jù)是在實

際中不可得，需要對其進行假設(shè)。依據(jù)模型數(shù)據(jù)類型不一樣,

把LRP分成假設(shè)型和實際型兩類。

4LRP處理方法

國外很多學者對LRP處理方法進行了有益探討，所采取

方法能夠分為兩種：正確算法和啟發(fā)式算法。

4.1處理LRP正確算法

基于運籌學優(yōu)化算法，處理LRP正確算法能夠分為以下

四種：

(1)直接樹狀搜索川；

(2)動態(tài)計劃川“7】；

(3)整數(shù)計劃［網(wǎng)［叫

(4)非線性計劃［2。］.

在以上算法中，最為常見是整數(shù)計劃(包含混合整數(shù)計劃)，

而具體處理時效率最高方法是分支一定界法。它能夠在不很

長計算時間內(nèi)處理多至80個節(jié)點LRP,不過采取分支一定界

法LRP必需在其模型中限制設(shè)施數(shù)量。一旦所包含LRP規(guī)

模擴大，正確算法就不實用了。

4.2處理LRP啟發(fā)式算法

因為LRP結(jié)合了LA問題和VRP,以后二者全部是

NP-Hard（Non-deterministicPolynomialhard）問題，所以,

在大多數(shù)情況下，要用正確算法來處理LRP是十分困難。比

如，在一個物流系統(tǒng)中，有3個潛在中心點,8個分布用戶點,

3條行車路線，假如用整數(shù)計劃來處理，要包含變量會達成

333個［16］。實際上，以上物流系統(tǒng)是十分小，在實踐中碰到

系統(tǒng)規(guī)模往往會遠超出它。很多情況下要引入啟發(fā)式算法。

LRP往往是十分復(fù)雜，需要采取多級分解方法對其簡化。

現(xiàn)在處理LRP啟發(fā)式算法多采取以下四種方法或是它們組

合：

（1）先處理定位一配給問題，然后處理運輸路線安排問

題［15,21］；

（2）先處理運輸路線安排問題，然后處理定位一配給問

題［22］；

（3）費用降低/插入算法囚，24］；

（4）路線擴展交換算法。

很多情況下正確優(yōu)化算法僅僅是作為一個參考基準，在研究

LRP時比較多種啟發(fā)式算法優(yōu)劣。而在處理實際規(guī)模問題時

通常要采取啟發(fā)式算法。

5LRP未來研究方向

實際物流系統(tǒng)集成程度越來越高，物流決議者面臨問題也就

越來越復(fù)雜。用現(xiàn)在LRP研究結(jié)果來處理尤其復(fù)雜物流系統(tǒng)

優(yōu)化問題還存在很多局限。未來對LRP研究將會集中于以下

難點：

5.1動態(tài)性

很多LRP參數(shù)是隨時間改變，如庫存費用會隨職員人數(shù)、

職員工資水平等原因改變而改變；運輸費用也會因車輛裝載

情況、油料費用等改變而改變。所以LRP含有動態(tài)性，對動

態(tài)LRP研究是有現(xiàn)實意義。

運籌學理論被認為是處理優(yōu)化問題十分有效工具。不過假如

實際問題發(fā)生改變，就會引發(fā)數(shù)學模型改變和模型求解程序

改變。對于動態(tài)問題，這種連鎖反應(yīng)是時時刻刻全部在發(fā)生。

所以用傳統(tǒng)運籌學理論處理動態(tài)優(yōu)化問題會力不從心。其原

因是傳統(tǒng)運籌學理論缺乏基于知識推理機制和處理動態(tài)問

題自適應(yīng)能力。為了克服這一缺點，八十年代以來中國外學

者將人工智能和知識工程理論引入運籌學，開辟了智能運籌

學［25,26］這一新研究方向。使運籌學由過去僅能處理靜態(tài)問

題變?yōu)槟軌蛱幚韯討B(tài)問題，它必將有利于動態(tài)LRP求解

5.2實時調(diào)控

在實際情況下，尤其是在現(xiàn)在被廣泛重視電子商務(wù)物流實施

過程中，商品供貨點、運輸工具、運輸路徑和送貨時間等需

要實時作出決擇。這就包含到實時調(diào)控問題。

多年來，Agent技術(shù)發(fā)展快速，Agent含有自主性、主動性、

反應(yīng)性和智能性為改善基于運籌學知識表示理論動態(tài)問題

實時優(yōu)化控制系統(tǒng)發(fā)明了條件。將Agent技術(shù)和運籌學理論

有機結(jié)合和交叉滲透，必將對最終處理實際規(guī)模LRP有決定

性意義。

5.3隨機性

在實踐中，物品供給/需求量、用戶點位置、車輛行駛時間

等等在很多情況下是不能事先確定，這些參數(shù)就帶有隨機

性。把隨機性引入LRP,更有利于處理實際問題。

已經(jīng)有很多學者對隨機性LRP進行了研究，如Laporte等人

[29]對供給/需求量不確定LRP作了探討。她們提出了一個兩

階段算法：第一階段，在供給/需求量未知情況下，確定中心

位置、運輸路線、車隊數(shù)量；第二階段，因為一條路線上供

給/需求量有可能超出車輛裝載能力，車輛在某點裝滿時要

返回中心點裝貨/卸貨，然后回到返回點恢復(fù)運輸，以上車輛

操作產(chǎn)生了處罰項。為了處理這類問題，引入兩種方法：（1）

在確保出現(xiàn)車輛返回概率大于某一預(yù)定值情況下，確定第一

階段值。（2）在確保因為車輛返回而產(chǎn)生費用不超出某一預(yù)

定費用情況下，確定第一階段值。這類問題就能夠采取整數(shù)

計劃來處理了。

5.4時間限制

實際物流系統(tǒng)中，很多情況下，用戶對車輛抵達時間是有限

制。這種時間限制又能夠分為硬限制和軟限制兩利I硬限制

要求時間一點，軟限制指定一段時間。不過，到現(xiàn)在為止，對

LRP研究極少考慮對時間限制。這方面研究將會是有益。

5.5多目標性

物流系統(tǒng)中各個目標之間會產(chǎn)生沖突，如根據(jù)總費用最小目

標確定方案，在滿足用戶對時間要求目標時，可能會不合要

求。然而，實際物流系統(tǒng)全部有多目標特征。所以以后對LRP

研究中會重視多目標之間優(yōu)化。

6結(jié)論

本文對物流系統(tǒng)中LRP由來、分類、處理方法作了簡明

評述，并對LRP未來研究方向作了分析。對LRP研究還存在

很多沒有很好處理方面。對LRP研究將會越來越向符合實際

情況方向發(fā)展。

參考文件

1Gilber.Laporte.Tble..A.overvie.o.exac.an.a

pproximat.algorthms.Europea.Journa.o.Operationa.Research,

1992,5.345-358

2Alan.Murray.Ros.A.Gen'ard.Capacitate.servic.an.regiona.con

straint.i.location-allocatio.modeling.Locatio.Science.1997.5(2

..103-118

3Joh.Current.H.Min.D.A.Schilling.Multiobjectiv.analysi.o.faci

lit.locatio.decisions.Europea.Journa.o.Operationa.Research.l

990.4..295-307

4汪壽陽,趙秋紅.夏國平.集成物流管理系統(tǒng)中定位一一運輸

線路安排問題講究.管理科學學報?.3(2..69-75

5S.Salhi.G.K.Rand.Th.effec.o.ignorin.route.whe.locatin.deport

s.Europea.Journa.o.Operationa.Research.l989.3..150-156

6Maranzan.F.E.O.th.locatio.o.suppl.point.t.minimiz.transpor.co

st.Operationa.Researc.Quarterly,!965,(15..261-270

7M.H.J.Webb.Cos.function.1.th.locatio.o.deport.fo.multiple-del

iver.journeys.Operationa.Researc.Quarterly.l968.(19..311-32

0

8N.Christofides.S.Eilton.A.

blem.Operationa.Researc.Quarterly.1969.(20..309-318

9Leo.Cooper.Th.Transportation-Locatio.Problem.Operation.Re

search.1972.2..94-108

10Leo.Cooper.A.efficien.heuristi.algorith.fo.th.transportatio..loc

blem.Journa.o.Regiona.Science.1976.16(3..309-315

11C.Watson-Gandy.P.Dohrn.Depo.locatio.wit.va.salesma...pract

ica.approach.Omega.1973.1(3..321-329

12I.Or.W.P.Pierskalla..transportation.locatio..allocatio.mode.fo.r

egiona.bloo.banking.AII.Transactions.l979.11(2..86-95

13Jacobson.S.k..Madsen.O.B.G..comparativ.stud.o.heuristic.fo..t

blem.Europea.Journa.o.Operationa

.Research.1980...378-387

14Laport.G.,Nober.Y..exac.algorith.fo.minimizin.routin.an.opera

tin.cost.i.depo.locatio..Europea.Journa.o.Operationa.Research

,1981,6:224-226

15Hoke.Min.Vaidyanatha.Jayaraman.Rajes.Srivastava.Combine

.blem...synthesi.an.futur.researc.direction.E

uropea.Journa.o.Operationa.Research.l998.108:1-15

16Rajes.Srivastava.W.C.Benton.Tble..consi

deration.i.physica.distributio.syste.design.Computer..Operatio

n.Research.1990.1..427-435

17LAverbakh.O.Berman.Routin.an.locatio..routin.p-deliver.ma.

problem.o..path.Transportatio.Science.l994.28(2..!62-166

18C.ReVelle.J.Cohon.D.Shobrys.Simultaneou.sitin.an.routin.i.th

.disposa.o.hazardou.wastes.Transportatio.Science.l991.25(2..

138-145

19G.Laporte.Y.Nobert.D.Arpin.A.exac.algorith.fo.solvin..capaci

blem.Annal.o.Operation.Research.1986

.6..293-310

20C.L.Stowers.U.S.Paleker.Locatio.model.wit.routin.considerati

on.fo..singl.obnoxiou.facility.Transportatio.Science.1993.27(

4..350-362

21J.H.Bookbinder.K.E.Reece.Vehicl.routin.consideration.i.distri

butio.syste.design.Europea.Journa.o.Operationa.Research.l98

8.3..204-213

22J.Perl.M.S.Dblem.Transpo

rtatio.Research.1985.19B(5..381-396

23T.W.Chien.Hcedure.fo.practica..size.uncapacitate.l

blems.Decisio.Sciences.1993.24(

5..995-1021

24P.H.Hansen.B.Hegedahl.S.Hjortk.B.ObeL.heuristi.solutio.t.th

.blem.Europea.Journa.o.Operatio

na.Research.l994.7..111-127

25R.I.phelps.Artificia.Intelligenc..A.ove