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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

17、研究 LRP 時(shí)比擬各種啟 發(fā) 式算法的優(yōu)劣。而于解決實(shí)際規(guī)模問題時(shí)壹般要采用啟發(fā)式算法。5LRP 的未來研究方向?qū)嶋H物流系統(tǒng)集成的程度越來越高，物流決策者面臨的問題也就越來越復(fù)雜。用目 前 LRP 的研究成果來解決特別復(fù)雜的物流系統(tǒng)優(yōu)化問題仍存于許多局限。 未來對 LRP 的 研究 將會(huì)集中于以下難點(diǎn)：5.1 動(dòng)態(tài)性許多 LRP 的參數(shù)是隨時(shí)間變化的，如庫存費(fèi)用會(huì)隨員工的人數(shù)、員工的工資水平等 因 素的變化而變化； 運(yùn)輸費(fèi)用也會(huì)因車輛裝載情況、 油料費(fèi)用等的改變而改變。 所以 LRP 具 有動(dòng)態(tài)性，對動(dòng)態(tài) LRP 的研究是有現(xiàn)實(shí)意義的。運(yùn)籌學(xué)理論被認(rèn)為是解決優(yōu)化問題十分有效的工具?？墒侨绻麑?shí)

18、際問題發(fā)生變化， 就會(huì) 引起數(shù)學(xué)模型改變和模型求解程序的改變。對于動(dòng)態(tài)問題，這種連鎖反響是時(shí)時(shí)刻 刻均于發(fā) 生的。因而用傳統(tǒng)的運(yùn)籌學(xué)理論解決動(dòng)態(tài)的優(yōu)化問題會(huì)力不從心。其原因是傳 統(tǒng)的運(yùn)籌學(xué)理 論缺乏基于知識(shí)的推理機(jī)制和處理動(dòng)態(tài)問題的自適應(yīng)能力。為了克服這壹缺陷，八十年代以來國內(nèi)外學(xué)者將人工智能和知識(shí)工程理論引入運(yùn)籌學(xué),開辟了智能運(yùn)籌學(xué) 25,26 這壹新的研究方向。 使運(yùn)籌學(xué)由過去的僅能解決靜態(tài)問題變?yōu)槟軌蚪鉀Q動(dòng)態(tài)問題，它必將有助于動(dòng)態(tài) LRP 的求解5.2 實(shí)時(shí)調(diào)控于實(shí)際情況下，特別是于如今被廣泛重視的電子商務(wù)物流的實(shí)施過程中，商品供貨 點(diǎn)、 運(yùn)輸工具、 運(yùn)輸路徑和送貨時(shí)間等需要實(shí)時(shí)作出決擇。這就涉及到實(shí)時(shí)調(diào)控的問題。近年來， Agent 技術(shù)開展迅速， Agent 具有的自主性、主動(dòng)性、反響性和智能性為 改將 Agent 技 術(shù)和進(jìn)基于運(yùn)籌學(xué)知識(shí)表示理論的動(dòng)態(tài)問題的實(shí)時(shí)優(yōu)化控制系統(tǒng)創(chuàng)造了條件。運(yùn)籌學(xué)理論有機(jī)結(jié)合和交叉滲透，必將對最終解決實(shí)際規(guī)模 LRP 有決定性的意義。5.3 隨機(jī)性于實(shí)踐中，物品的供給 / 需求量、客戶點(diǎn)位置、車輛行駛時(shí)間等等于很多情況下是不 能 事先確定的，這些參數(shù)就帶有隨機(jī)性。把隨機(jī)性引入 LRP ，更有利于解決實(shí)際問題。已經(jīng)有許多學(xué)者對隨機(jī)性 LRP 進(jìn)行了研究，如 Laporte 等人29