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

1、物流系統(tǒng)優(yōu)化中的定位運輸路線安排問題（）研究評述* 國家自然科學基金重點項目(70031020)林巖胡祥培* 林巖, 碩士研究生, 1972年出生, 主要研究方向: 電子商務, 信息系統(tǒng)工程。 胡祥培, 1962年出生, 教授,博導, 主要研究方向: 電子商務, 智能運籌學, 信息系統(tǒng)集成。 *（大連理工大學系統(tǒng)工程研究所, 116023）摘要 本文概述了物流優(yōu)化問題中的定位運輸路線安排問題（Location-Routing Problems, LRP）的發(fā)展歷程，并對LRP的分類和解決方法加以評述，最后就這一問題的發(fā)展方向進行簡單地探討。關鍵詞 LRP 物流系統(tǒng)優(yōu)化 運籌學1 引言新技術的迅

2、速發(fā)展，特別是電子商務的風起云涌，為我國經濟的快速發(fā)展提供了契機。目前我國電子商務得到政府和民眾的支持，發(fā)展勢頭強勁，但是，由于它是一套全新的技術，同時還是一種全新的管理理念，所以其發(fā)展過程中必然存在一些難題。在電子商務“三流”（信息流、物流、資金流）中，隨著網絡基礎設施建設的成熟、電子商務網站的蓬勃發(fā)展以及有效利用網絡資源觀念的普及，信息流的發(fā)展已經比較成熟了；而隨著各大銀行紛紛開展網上業(yè)務，以及支付網關的建立和加密技術的成熟，網上支付已經在許多網站上成為現(xiàn)實；然而，我國傳統(tǒng)的物流體系是在計劃經濟環(huán)境下建立、發(fā)展起來的，與目前的電子商務環(huán)境已經無法相容?，F(xiàn)今物流體系的落后現(xiàn)狀已經成為我國社會

3、經濟快速發(fā)展的重要制約因素之一。所以對物流系統(tǒng)優(yōu)化的研究將會具有很大的現(xiàn)實意義。國外許多學者在電子商務出現(xiàn)之前就已經研究物流系統(tǒng)優(yōu)化的問題了，為各類實際問題構建了優(yōu)化模型，并形成了許多解決問題的算法。依據實際問題的不同，可以對物流系統(tǒng)優(yōu)化問題進行分類，比如，運輸車輛路線安排問題（VRP）、定位配給問題（LA）、定位運輸路線安排問題（LRP）等等，其中LRP更貼近目前的物流系統(tǒng)復雜的實際特征，所以對它的研究是十分有意義的。本文先從VRP和LA的集成來探討LRP的由來，然后討論LRP的分類，同時探討LRP的研究現(xiàn)狀，并對LRP的解決方法進行概述，最后就LRP的未來發(fā)展方向作簡要的討論。2 從VRP

4、、LA到LRP物流系統(tǒng)的集成依據實際問題的不同，可以對物流系統(tǒng)優(yōu)化問題進行分類，比如確定設施（指的是物品流動的出發(fā)點和終到點，如配送中心、倉庫、生產工廠、垃圾回收中心等）位置、運輸路線安排、庫存控制等，國內外許多學者就各類問題的特征進行了分析，并提出了各類問題的數(shù)學模型和解決方法。2.1運輸車輛路線安排問題（Vehicle Routing Problems VRP）該問題可定義為：運輸車輛從一個或多個設施到多個地理上分散的客戶點，優(yōu)化設計一套貨物流動的運輸路線，同時要滿足一系列的約束條件。該問題的前提條件是設施位置、客戶點位置和道路情況已知，由此確定一套車輛運輸路線，以滿足目標函數(shù)（通常，VR

5、P的目標函數(shù)是總費用最?。?。如圖1所示。圖中，表示設施；表示客戶；表示運輸路線圖1 VRP的圖示實際上，VRP是按如下假設定義的最小費用問題1：（1） 所有車輛路線均起始并終止于設施點。（2）每個客戶只接受一個設施的貨物。（3） 滿足其他一些約束條件，如： 容量限制：每個客戶點上都有一個非負的貨物需求量，但每條車輛路線上的貨物量總和不超過車輛裝載量。如果此約束不滿足，則引入懲罰函數(shù)。 總時間限制：每條路線總的長度或總耗時不超過一個事先定下的數(shù)值。這項限制旨在滿足客戶對供貨時間的要求，以及對貨物品質的保證。 具體時間限制：對某個客戶點，車輛到達時間限制在某一時間段內。此約束在于滿足客戶對供應/回

6、收的特殊要求。 車輛到達順序要求：如在到達i點之前要求先到達j點。以上列出的約束只是該問題一部分，具體操作時要視具體情況而定。對VRP的求解算法可分為精確算法和啟發(fā)式算法兩種。其中精確算法包括樹狀尋優(yōu)算法、動態(tài)規(guī)劃和整數(shù)規(guī)劃。VRP的啟發(fā)式算法多是來源于對TSP問題的求解算法。比如局部優(yōu)先算法、插值法等可以不用修改地用于一些VRP。2.2定位配給問題（Location-Allocation Problems, LA）定位一配給問題可定義為：依據客戶點的地理分布與貨物分配關系，確定出某一地理范圍內設施的數(shù)量和位置。如圖2所示。圖中，表示設施；表示客戶；表示運輸路線圖2 LA的圖示LA實質上是一個

7、依據優(yōu)化路徑的原則來確定在什么地方設置設施的過程2。例如，在一個城鎮(zhèn)中設立一個急救中心，這個問題就是一個典型的LA問題。它的目標就是使得全鎮(zhèn)的居民到醫(yī)療中心的路徑（時間）總體上最短。根據John Current等學者對此問題的綜述研究3，把LA問題進行了分類。Current的方法是根據問題的目標函數(shù)來分類的，作為分類依據的目標函數(shù)共分四種：(1) 費用最小化；(2) 客戶需求導向；(3) 利潤最大化；(4) 其他相關考慮。2.3定位一運輸路線安排問題（Location-Routing problems,LRP）當今物流系統(tǒng)的環(huán)境日趨復雜，而且物流地理分布也不斷擴大。物流系統(tǒng)優(yōu)化問題的各個子系統(tǒng)

8、（比如設施定位問題、物品配送問題、運輸車輛路線安排問題等）之間的相互影響也越來越大。對許多實際問題，要綜合考慮以上問題，這就形成了定位一路線安排問題（LRP）。LRP可以表述為：給定與實際問題相符的一系列客戶點和一系列潛在的設施點，在這些潛在的點中確定出一系列的設施位置，同時要確定出一套從各個設施到各個客戶點的運輸路線，確定的依據是滿足問題的目標（通常是總的費用最?。？蛻酎c的位置和客戶的需求量是已知的或可估算的，貨物有一個或多個設施供應，每個客戶只接收來自一個設施的貨物，潛在設施點位置已知，問題的目標是把哪些潛在的設施建立起來，以使的總的費用最小。LRP可圖示為圖3?？梢哉fLRP是LA與VR

9、P的集成4，但比后兩者更復雜。LA在定位時考慮的是運輸車輛從設施點到一個客戶點后，隨即返回設施點，所以它不考慮路線安排問題5。LA在確定出設施點后的圖形是從設施點到客戶點的射線族。而LRP則在定位時同時確定運輸路線。LRP與VRP的不同之處是：VRP的前提條件是設施點和客戶點在空間上的分布是已知的；LRP所研究的問題只知道潛在的設施點，在確定運輸路線的同時要確定設施的位置。圖中，表示設施；表示未被選中的設施；表示客戶點；表示運輸路線圖3 LRP的圖示在實際物流系統(tǒng)的集成的特征日益突出之前，就已經有人研究LRP了。最早的研究可以追溯到20世紀60年代，當時有些學者已經提出一些類似的概念了6-8。

10、到了70年代，Cooper9, 10把定位問題與運輸問題結合起來，提出了運輸一定位問題（Transportation-Location problem）。在這個階段，學者們對LRP的研究還是相當膚淺的，還沒有真正涉及運輸路線安排問題。到了70年代中期，一些學者在研究運輸一定位問題時，開始加入VRP的多點運輸?shù)奶卣?，Watson-Gandy和Dohrn11是最早進行這方面工作的學者。直到70年代末，80年代初，才開始有了真正意義的LRP12-14。這些研究成果是伴隨著集成物流系統(tǒng)概念的出現(xiàn)而出現(xiàn)的。3LRP的分類Hokey Min等學者對LRP進行了詳細的分類15，其分類標準十分詳盡，幾乎包含了

11、LRP的各個方面。表1 LRP的分類標準分類標準AB1物品流向單向雙向2供/需特征確定隨機3設施數(shù)量單個設施多設施4運輸車輛數(shù)量單個車輛多車輛5車輛裝載能力不確定確定6設施容量不確定確定7設施分級單級多級8計劃期間單期多期9時間限制無時間限制有時間限制10目標數(shù)單目標多目標11模型數(shù)據類型假設值實際值Hokey的分類是依據問題的特征進行的，具體如表1。表1中，各分類標準解釋如下：（1） 物品流向，單向物品流向問題指的是所有設施只進行輸入（供應）或只進行輸出（回收）的操作；而雙向物品流向問題涉及的設施中有一部分既要輸入又要輸出。（2） 供/需特征，確定型的是指物品供應/需求量是已知的并在一定時期

12、內相對穩(wěn)定；隨機型的是指供應/需求量是不確定的。（3） 設施數(shù)量，指所研究問題要求設置設施的數(shù)量，分為單一設施和多設施兩種。（4） 運輸工具數(shù)量，是指有多少車輛為一個設施服務的標準，同時也確定了一個從設施出發(fā)的路線數(shù)。分為單一車輛和多車輛兩種。（5） 車輛裝載能力，是指是否要考慮車輛裝載能力的限制。不確定定型是指對這個問題所涉及的每條路線上的貨物總量很小，不會超出車輛的裝載量，所以不用考慮車輛的裝載能力的限制；確定型是指每條路線上的貨物總量有可能超出車輛的裝載能力，所以要把車輛的裝載限制作為一個參數(shù)引入問題。（6） 設施容量，是指是否考慮各個設施容量的限制。分為不確定型和確定型兩種。（7） 設

13、施分級，可以把設施分為兩種：總站型和中間轉運站型?？傉拘驮O施是指那些車輛路線的出發(fā)點或終點；中間轉運站型設施是指物品的中間站，貨物運入后還要運出。有了中間轉運站，就產生了設施分級的問題，貨物從總站型設施運入中間轉運站型設施，經過簡單處理后運到客戶點。單級設施問題是指不考慮設施的分級，所有設施均為同級；而多級中心設施問題則要考慮設施的分級。（8） 計劃期間，單期間問題把整個期間作為一個時間段，是靜態(tài)問題；多期間問題把整個時間段按問題要求分為多個期間，是動態(tài)問題。（9） 時間限制，主要是指滿足客戶要求或貨物品質要求，而對LRP的從設施點到客戶點的時間約束。分為無時間約束和有時間約束兩種。（10）

14、目標數(shù)量，LRP的目標通常是總的費用（包括建設設施費用和車輛運輸費用等）最小，但有時也需要考慮其他目標，比如滿足顧客的特殊需要、總體利潤量大化等等。如果是多目標問題，經常會出現(xiàn)各目標之間的沖突。（11） 模型數(shù)據類型，在有些情況下，模型中的數(shù)據（如物品供/需量等）是來源于實際的；而有些情況下，這些數(shù)據是在實際中不可得的，需要對其進行假設。根據模型數(shù)據類型的不同，把LRP分成假設型和實際型兩類。4 LRP的解決方法國外許多學者對LRP的解決方法進行了有益的探討，所采用的方法可以分為兩種：精確算法和啟發(fā)式算法。4.1 解決LRP的精確算法 基于運籌學的優(yōu)化算法，解決LRP的精確算法可以分為以下四種

15、：(1) 直接樹狀搜索1；(2) 動態(tài)規(guī)劃117；(3) 整數(shù)規(guī)劃1819；(4) 非線性規(guī)劃20。在以上算法中，最為常用的是整數(shù)規(guī)劃（包括混合整數(shù)規(guī)劃）,而具體解決時效率最高的方法是分支定界法。它可以在不很長的計算時間內解決多至80個節(jié)點的LRP，但是采用分支定界法的LRP必須在其模型中限制設施的數(shù)量。一旦所涉及的LRP的規(guī)模擴大，精確算法就不實用了。4.2解決LRP的啟發(fā)式算法由于LRP結合了LA問題和VRP，而后兩者都是NP-Hard (Non deterministic Polynomial hard)問題，所以，在大多數(shù)情況下，要用精確算法來解決LRP是十分困難的。例如，在一個物流系

16、統(tǒng)中，有3個潛在的中心點，8個分布的客戶點，3條行車路線，如果用整數(shù)規(guī)劃來解決，要涉及的變量會達到333個16。實際上，以上的物流系統(tǒng)是十分小的，在實踐中遇到的系統(tǒng)規(guī)模往往會遠超過它。很多情況下要引入啟發(fā)式算法。LRP往往是十分復雜的，需要采用多級分解方法對其簡化。目前解決LRP的啟發(fā)式算法多采用以下四種方法或是它們的組合：（1） 先解決定位一配給問題，然后解決運輸路線安排問題15, 21；（2） 先解決運輸路線安排問題，然后解決定位一配給問題22；（3） 費用降低/插入算法23, 24；（4） 路線擴展交換算法。很多情況下精確的優(yōu)化算法僅僅是作為一種參照的基準，在研究LRP時比較各種啟發(fā)式算

17、法的優(yōu)劣。而在解決實際規(guī)模問題時一般要采用啟發(fā)式算法。5 LRP的未來研究方向實際物流系統(tǒng)集成的程度越來越高，物流決策者面臨的問題也就越來越復雜。用目前LRP的研究成果來解決特別復雜的物流系統(tǒng)優(yōu)化問題還存在許多局限。未來對LRP的研究將會集中于以下難點：5.1 動態(tài)性許多LRP的參數(shù)是隨時間變化的，如庫存費用會隨員工的人數(shù)、員工的工資水平等因素的變化而變化；運輸費用也會因車輛裝載情況、油料費用等的改變而改變。所以LRP具有動態(tài)性，對動態(tài)LRP的研究是有現(xiàn)實意義的。運籌學理論被認為是解決優(yōu)化問題十分有效的工具。但是如果實際問題發(fā)生變化，就會引起數(shù)學模型改變和模型求解程序的改變。對于動態(tài)問題，這種

18、連鎖反應是時時刻刻都在發(fā)生的。因而用傳統(tǒng)的運籌學理論解決動態(tài)的優(yōu)化問題會力不從心。其原因是傳統(tǒng)的運籌學理論缺乏基于知識的推理機制和處理動態(tài)問題的自適應能力。為了克服這一缺陷，八十年代以來國內外學者將人工智能和知識工程理論引入運籌學,開辟了智能運籌學25, 26這一新的研究方向。使運籌學由過去的僅能解決靜態(tài)問題變?yōu)榭梢越鉀Q動態(tài)問題，它必將有助于動態(tài)LRP的求解5.2 實時調控在實際情況下，特別是在如今被廣泛重視的電子商務物流的實施過程中，商品供貨點、運輸工具、運輸路徑和送貨時間等需要實時作出決擇。這就涉及到實時調控的問題。近年來，Agent技術發(fā)展迅速，Agent具有的自主性、主動性、反應性和智

19、能性為改進基于運籌學知識表示理論的動態(tài)問題的實時優(yōu)化控制系統(tǒng)創(chuàng)造了條件。將Agent技術與運籌學理論有機結合和交叉滲透，必將對最終解決實際規(guī)模LRP有決定性的意義。5.3 隨機性在實踐中，物品的供應/需求量、客戶點位置、車輛行駛時間等等在很多情況下是不能事先確定的，這些參數(shù)就帶有隨機性。把隨機性引入LRP，更有利于解決實際問題。已經有許多學者對隨機性LRP進行了研究，如Laporte等人29對供應/需求量不確定的LRP作了探討。他們提出了一種兩階段算法：第一階段，在供應/需求量未知的情況下，確定中心位置、運輸路線、車隊數(shù)量；第二階段，由于一條路線上的供應/需求量有可能超出車輛的裝載能力，車輛在

20、某點裝滿時要返回中心點裝貨/卸貨，然后回到返回點恢復運輸，以上的車輛操作產生了懲罰項。為了解決這類問題，引入兩種方法：（1）在保證出現(xiàn)車輛返回的概率不小于某一預定值的情況下，確定第一階段值。（2）在保證由于車輛返回而產生的費用不超過某一預定費用的情況下，確定第一階段值。這類問題就可以采用整數(shù)規(guī)劃來解決了。5.4 時間限制實際的物流系統(tǒng)中，許多情況下，客戶對車輛的到達時間是有限制的。這種時間的限制又可以分為硬限制和軟限制兩種，硬限制要求時間的一點，軟限制指定一段時間。但是，到目前為止，對LRP的研究很少考慮對時間的限制。這方面的研究將會是有益的。5.5 多目標性物流系統(tǒng)中的各個目標之間會產生沖突

21、，如按照總費用最小目標確定的方案，在滿足客戶對時間要求的目標時，可能會不合要求。然而，實際物流系統(tǒng)均有多目標的特征。所以以后對LRP的研究中會注重多目標之間優(yōu)化。6結論本文對物流系統(tǒng)中的LRP的由來、分類、解決方法作了簡要的評述，并對LRP的未來研究方向作了分析。對LRP的研究還存在許多沒有很好解決的方面。對LRP的研究將會越來越向符合實際情況的方向發(fā)展。參考文獻1 Gilbert Laporte.The vehicle routing problem:An overview of exact and approximate algorthms.European Journal of Oper

22、ational Research,1992,59 : 345-3582 Alant Murray, Ross A. Gerrard. Capacitated service and regional constraints in location-allocation modeling. Location Science, 1997, 5(2):103-1183 John Current, H. Min, D.A. Schilling. Multiobjective analysis of facility location decisions. European Journal of Ope

23、rational Research, 1990, 49: 295-3074 汪壽陽, 趙秋紅, 夏國平. 集成物流管理系統(tǒng)中的定位運輸線路安排問題的研究. 管理科學學報, 2000, 3(2) : 69-755 S. Salhi, G.K. Rand. The effect of ignoring routes when locating deports. European Journal of Operational Research, 1989, 39 : 150-1566 Maranzana F.E. On the location of supply points to minimiz

24、e transport cost. Operational Research Quarterly,1965,(15):261-2707 M.H.J. Webb. Cost functions in the location of deports for multiple-delivery journeys. Operational Research Quarterly, 1968, (19):311-3208 N.Christofides, S.Eilton. An algorithm for the vehicle dispatching problem. Operational Resea

25、rch Quarterly, 1969, (20):309-3189 Leon Cooper. The Transportation-Location Problem. Operations Research, 1972, 20 : 94-10810 Leon Cooper. An efficient heuristic algorithm for the transportation location problem. Journal of Regional Science, 1976, 16(3) : 309-31511 C.Watson-Gandy, P.Dohrn. Depot loc

26、ation with van salesman A practical approach. Omega, 1973, 1(3) : 321-32912 I.Or, W.P.Pierskalla. A transportation, location allocation model for regional blood banking. AIIE Transactions, 1979, 11(2) : 86-9513 Jacobson.S.k., Madsen. O.B.G.A comparative study of heuristics for a tow-level routing lo

27、cation problem. European Journal of Operational Research,1980,5:378-38714 Laporte G.,Nobert Y. A exact algorithm for minimizing routing and operating costs in depot location . European Journal of Operational Research,1981,6:224-22615 Hokey Min, Vaidyanathan Jayaraman, Rajesh Srivastava. Combined loc

28、ation - routing problems : A synthesis and future research direction.European Journal of Operational Research,1998,108:1-1516 Rajesh Srivastava,W.C.Benton. The location-routing problem:considerations in physical distribution system design.Computers & Operations Research,1990,17:427-43517 I.Averb

29、akh, O.Berman. Routing and location routing p-delivery man problems on a path. Transportation Science, 1994, 28(2) : 162-16618 C.ReVelle, J.Cohon, D.Shobrys. Simultaneous siting and routing in the disposal of hazardous wastes. Transportation Science, 1991, 25(2) : 138-14519 G.Laporte, Y. Nobert, D.A

30、rpin. An exact algorithm for solving a capacitated location routing problem. Annals of Operations Research, 1986, 6, : 293-31020 C.L.Stowers, U.S.Paleker. Location models with routing considerations for a single obnoxious facility. Transportation Science, 1993, 27(4) : 350-36221 J.H.Bookbinder, K.E.

31、Reece. Vehicle routing considerations in distribution system design. European Journal of Operational Research, 1988, 37: 204-21322 J.Perl, M.S.Daskin. A warehouse location routing problem. Transportation Research, 1985, 19B(5) : 381-39623 T.W.Chien. Heurristic procedures for practical sized uncapaci

32、tated location capacitated routing problems. Decision Sciences, 1993, 24(5) : 995-102124 P.H.Hansen,B.Hegedah1,S.Hjortk, B.Obel.A heuristic solution to the warehouse location-routing problem.European Journal of Operational Research,1994,76:111-12725 R.I.phelps. Artificial Intelligence - An overview of Similarities with O.R. Journal of Operational Research Society, 1986, 37(1) : 13-2026 胡祥培, 楊德禮. 智能運籌學與動態(tài)系統(tǒng)實時優(yōu)化控制. 經濟管理與社會科學前沿研究2000年中國博士后學術大會經濟