{物流管理}物流系統(tǒng)優(yōu)化中的定位

1、物流管理物流系統(tǒng)優(yōu)化中的定位物流系統(tǒng)優(yōu)化中的定位運輸路線安排問題(LRP )研究評述摘要本文概述了物流優(yōu)化問題中的定位運輸路線安排問題( Location-RoutingProblems,LRP )的開展歷程，且對 LRP 的分類和解 決方法加以 評述，最后就這壹問題的開展方向進行簡單地探討。 關鍵詞 LRP 物流系統(tǒng)優(yōu)化運籌 學1 引言新技術的迅速開展，特別是電子商務的風起云涌，為我國經濟的快速開展提供了契 機。 目前我國電子商務得到政府和民眾的支持， 開展勢頭強勁， 可是，由于它是壹套全 新的技術， 同時仍是壹種全新的管理理念，所以其開展過程中必然存于壹些難題。于電 子商務“三流 (信息流

2、、物流、資金流)中，隨著網絡根底設施建設的成熟、電子商務 網站的蓬勃開展以 及有效利用網絡資源觀念的普及，信息流的開展已經比擬成熟了；而 隨著各大銀行紛紛開展 網上業(yè)務，以及支付網關的建立和加密技術的成熟，網上支付已 經于許多網站上成為現(xiàn)實； 然而，我國傳統(tǒng)的物流體系是于方案經濟環(huán)境下建立、開展 起來的，和目前的電子商務環(huán)境 已經無法相容。現(xiàn)今物流體系的落后現(xiàn)狀已經成為我國 社會經濟快速開展的重要制約因素之 壹。所以對物流系統(tǒng)優(yōu)化的研究將會具有很大的現(xiàn) 實意義。國外許多學者于電子商務出現(xiàn)之前就已經研究物流系統(tǒng)優(yōu)化的問題了，為各類實際 問題 構建了優(yōu)化模型，且形成了許多解決問題的算法。依據實際問

3、題的不同，能夠對物 流系統(tǒng)優(yōu) 化問題進行分類， 比方，運輸車輛路線安排問題 (VRP )、定位配給問題 (LA )、 定 位運輸路線安排問題( LRP )等等，其中 LRP 更貼近目前的物流系統(tǒng)復雜的實際特 征， 所以對它的研究是十分有意義的。本文先從VRP和LA的集成來探討LRP的由來，然后討論LRP的分類，同時探討LRP的研究現(xiàn)狀，且對LRP的解決方法進行概述， 最后就LRP的未來開展方向作簡要的 討論。 2從 VRP、LA至U LRP物流系統(tǒng)的集成 依據實際問題的不同，能夠對物流系統(tǒng)優(yōu)化問題進行分類，比方確定設施(指的是物品流動的出發(fā)點和終到點，如配送中心、倉庫、生產工廠、垃圾回收中心等

4、)位置、運輸路線安排、庫存控制等，國內外許多學者就各類問題的特征進行了分析，且提出了各類問題的數(shù)學模型和解決方法。2.1 運輸車輛路線安排問題(VehicleRoutingProblemsVRP)該問題可定義為：運輸車輛從壹個或多個設施到多個地理上分散的客戶點，優(yōu)化設計壹套貨物流動的運輸路線，同時要滿足壹系列的約束條件。該問題的前提條件是設施位置、客戶點位置和道路情況，由此確定壹套車輛運輸路線，以滿足目標函數(shù)(通常，VRP的目標函數(shù)是總費用最小) 。如圖1所示。表示客戶;實際上，VRP是按如下假設定義的最小費用問題1:(1) 所有車輛路線均起始且終止于設施點。(2) 每個客戶只接受壹個設施的貨

5、物。(3 )滿足其他壹些約束條件，如：容量限制：每個客戶點上均有壹個非負的貨物需求量，但每條車輛路線上的貨物量 總和不超過車輛裝載量。如果此約束不滿足，那么引入懲罰函數(shù)?？倳r間限制：每條路線總的長度或總耗時不超過壹個事先定下的數(shù)值。這項限制旨于滿足客戶對供貨時間的要求，以及對貨物品質的保證。具體時間限制：對某個客戶點，車輛到達時間限制于某壹時間段內。此約束于于滿足客 戶對供給/回收的特殊要求。車輛到達順序要求：如于到達 i點之前要求先到達j點。之上列出的約束只是該問題壹局部，具體操作時要視具體情況而定。其中精確算法包括樹狀尋優(yōu)算對VRP的求解算法可分為精確算法和啟發(fā)式算法倆種。法、動態(tài)規(guī)劃和整

6、數(shù)規(guī)劃。VRP的啟發(fā)式算法多是來源于對 TSP問題的求解算法。比 如局部優(yōu)先算法、插值法等能夠不用修改地用于壹些VRP。2.2 定位一配給問題(Location-AllocationProblems,LA定位壹配給問題可定義為：依據客戶點的地理分布和貨物分配關系，確定出某壹地理范圍內設施的數(shù)量和位置。如圖 2所示。圖中，表示設施；表示客戶；/表示運輸路線圖2LA的圖示LA實質上是壹個依據優(yōu)化路徑的原那么來確定于什么地方設置設施的過程2。例如，于壹個城鎮(zhèn)中設立壹個急救中心，這個問題就是壹個典型的LA問題。它的目標就是使 得全鎮(zhèn) 的居民到醫(yī)療中心的路徑 ( 時間)總體上最短。根據 JohnCurr

7、ent 等學者對此問題的綜述研究 3 ，把 LA 問題進行了分類。 Current 的 方法是根據問題的目標函數(shù)來分類的，作為分類依據的目標函數(shù)共分四種：(1) 費用最小化；(2) 客戶需求導向；(3) 利潤最大化；(4) 其他關聯(lián)考慮。2.3 定位壹運輸路線安排問題 ( Location-Routingproblems,LRP )當今物流系統(tǒng)的環(huán)境日趨復雜，而且物流地理分布也不斷擴大。物流系統(tǒng)優(yōu)化問題 的各 個子系統(tǒng) ( 比方設施定位問題、物品配送問題、運輸車輛路線安排問題等)之間的 相互影響也越來越大。對許多實際問題， 要綜合考慮之上問題， 這就形成了定位壹路線 安排問題 ( LRP) 。

8、LRP 能夠表述為：給定和實際問題相符的壹系列客戶點和壹系列潛于的設施點，于 這些 潛于的點中確定出壹系列的設施位置，同時要確定出壹套從各個設施到各個客戶點 的運輸路 線， 確定的依據是滿足問題的目標 ( 通常是總的費用最小 ) ?？蛻酎c的位置和客 戶的需求量 是的或可估算的，貨物有壹個或多個設施供給，每個客戶只接收來自壹 個設施的貨物， 潛于設施點位置， 問題的目標是把哪些潛于的設施建立起來， 以使 的總的費用最小。 LRP 可圖示為圖 3。LA 于定位時考慮的是運能夠說 LRP 是 LA 和 VRP 的集成 4 ，但比后倆者更復雜。LA輸車輛從設施點到壹個客戶點后，隨即返回設施點，所以它不

9、考慮路線安排問題于確定出設施點后的圖形是從設施點到客戶點的射線族。而LRP那么于定位時同時確定運 輸路線。LRP和VRP的不同之處是：VRP的前提條件是設施點和客戶點于空間上的分 布是 的；LRP所研究的問題只知道潛于的設施點，于確定運輸路線的同時要確定設施的位置。圖中，表示設施；表示未被選中的設施；表示客戶點；/表示運輸路線圖3LRP的圖示于實際物流系統(tǒng)的集成的特征日益突出之前，就已經有人研究LRP 了。最早的研究 能夠追溯到20世紀60年代，當時有些學者已經提出壹些類似的概念了6-8。到了 70年 代，Cooper 9,10把定位問題和運輸問題結合起來，提出了運輸壹定位問題(Transpo

10、rtation-Locatioproblem)。于這個階段，學者們對LRP的研究仍是相當膚淺的，仍沒有真正涉及運輸路線安排問題。到了70年代中期，壹些學者于研究運輸壹 定位問題時，開始參加 VRP的多點運輸?shù)奶卣鳎?Watson-Gandy和Dohrn 11是最早進 行這方 面工作的學者。直到70年代末，80年代初，才開始有了真正意義的 LRP 12-14。這些研究 成果是伴隨著集成物流系統(tǒng)概念的出現(xiàn)而出現(xiàn)的。3LRP的分類HokeyMin等學者對LRP進行了詳細的分類15，其分類標準十分詳盡， 幾乎包含了LRP的各個方面表1LRP的分類標準分類標準AB1物品流向單向雙向2供/需特征確定隨機3

11、設施數(shù)量單個設施多設施4運輸車輛數(shù)量單個車輛多車輛5車輛裝載能力不確定確定6設施容量不確定確定7設施分級單級多級8方案期間單期多期9時間限制無時間限制有時間限制10目標數(shù)單目標多目標11模型數(shù)據類型假設值實際值Hokey的分類是依據問題的特征進行的，具體如表1。表1中，各分類標準解釋如下：1 物品流向，單向物品流向問題指的是所有設施只進行輸入供給或只進行輸出回收的操作；而雙向物品流向問題涉及的設施中有壹局部既要輸入又要輸出。2供/需特征，確定型的是指物品供給/需求量是的且于壹定時期內相對穩(wěn)定； 隨機型的是指供給/需求量是不確定的。3 設施數(shù)量，指所研究問題要求設置設施的數(shù)量，分為單壹設施和多設

12、施倆種 4 運輸工具數(shù)量，是指有多少車輛為壹個設施效勞的標準，同時也確定了壹個從設施出發(fā)的路線數(shù)。分為單壹車輛和多車輛倆種。 5 車輛裝載能力，是指是否要考慮車輛裝載能力的限制。 不確定定型是指對這個 問題所涉及的每條路線上的貨物總量很小，不會超出車輛的裝載量，所以不用考慮車輛 的裝 載能力的限制；確定型是指每條路線上的貨物總量有可能超出車輛的裝載能力，所 以要把車 輛的裝載限制作為壹個參數(shù)引入問題。6設施容量，是指是否考慮各個設施容量的限制。分為不確定型和確定型倆種。7設施分級，能夠把設施分為倆種：總站型和中間轉運站型。總站型設施是指那 些車輛路線的出發(fā)點或終點；中間轉運站型設施是指物品的中

13、間站，貨物運入后仍要運 出。 有了中間轉運站，就產生了設施分級的問題，貨物從總站型設施運入中間轉運站型 設施，經 過簡單處理后運到客戶點。單級設施問題是指不考慮設施的分級，所有設施均 為同級；而多 級中心設施問題那么要考慮設施的分級。8方案期間，單期間問題把整個期間作為壹個時間段，是靜態(tài)問題；多期間問題 把 整個時間段按問題要求分為多個期間，是動態(tài)問題。 9 時間限制，主要是指滿足客戶要求或貨物品質要求，而對LRP 的從設施點到客戶點的時間約束。分為無時間約束和有時間約束倆種。 10 目標數(shù)量， LRP 的目標通常是總的費用 包括建設設施費用和車輛運輸費用 等 最小，但有時也需要考慮其他目標，

14、比方滿足顧客的特殊需要、總體利潤量大化等 等。如果 是多目標問題，經常會出現(xiàn)各目標之間的沖突。11 模型數(shù)據類型，于有些情況下，模型中的數(shù)據如物品供/需量等是來源于實際的；而有些情況下，這些數(shù)據是于實際中不可得的，需要對其進行假設。根據模型 數(shù)據 類型的不同，把 LRP 分成假設型和實際型倆類4LRP 的解決方法國外許多學者對 LRP 的解決方法進行了有益的探討，所采用的方法能夠分為倆種： 精 確算法和啟發(fā)式算法。4.1 解決 LRP 的精確算法基于運籌學的優(yōu)化算法，解決 LRP 的精確算法能夠分為以下四種：(1) 直接樹狀搜索 1；(2) 動態(tài)規(guī)劃 117 ；(3) 整數(shù)規(guī)劃 1819 ；(

15、4) 非線性規(guī)劃 20 。于之上算法中，最為常用的是整數(shù)規(guī)劃 ( 包括混合整數(shù)規(guī)劃 ) ,而具體解決時效率最 高的方法是分支定界法。它能夠于不很長的計算時間內解決多至 80 個節(jié)點的 LRP ， 可是 采用分支定界法的 LRP 必須于其模型中限制設施的數(shù)量。 壹旦所涉及的 LRP 的規(guī) 模擴 大，精確算法就不實用了。4.2 解決 LRP 的啟發(fā)式算法由 于 LRP 結 合 了 LA 問 題 和 VRP ， 而 后 倆 者 均 是 NP-Hard(Non-deterministicPolynomialhard)問題，所以，于大多數(shù)情況下，要用精確算法來解決LRP是十分困難的。例如，于壹個物流系統(tǒng)

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

17、研究 LRP 時比擬各種啟 發(fā) 式算法的優(yōu)劣。而于解決實際規(guī)模問題時壹般要采用啟發(fā)式算法。5LRP 的未來研究方向實際物流系統(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)化問題十分有效的工具?？墒侨绻麑?/p>

18、際問題發(fā)生變化， 就會 引起數(shù)學模型改變和模型求解程序的改變。對于動態(tài)問題，這種連鎖反響是時時刻 刻均于發(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 技術開展迅速， Agent 具有的自主性、主動性、反響性和智能性為 改將 Agent 技 術和進基于運籌學知識表示理論的動態(tài)問題的實時優(yōu)化控制系統(tǒng)創(chuàng)造了條件。運籌學理論有機結合和交叉滲透，必將對最終解決實際規(guī)模 LRP 有決定性的意義。5.3 隨機性于實踐中，物品的供給 / 需求量、客戶點位置、車輛行駛時間等等于很多情況下是不 能 事先確定的，這些參數(shù)就帶有隨機性。把隨機性引入 LRP ，更有利于解決實際問題。已經有許多學者對隨機性 LRP 進行了研究，如 Laporte 等人29