0107112物流系統(tǒng)優(yōu)化中的定位-運(yùn)輸路線安排問(wèn)題(doc)
物流系統(tǒng)優(yōu)化中的定位—運(yùn)輸路線安排問(wèn)題 （ＬＲＰ）研究評(píng)述( 摘要 本文概述了物流優(yōu)化問(wèn)題中的定位—運(yùn)輸路線安排問(wèn)題（Location-Routing Problems, LRP）的發(fā)展歷程，并對(duì)LRP的分類和解決方法加以評(píng)述，最后就這一問(wèn)題的發(fā)展方 向進(jìn)行簡(jiǎn)單地探討。 關(guān)鍵詞 LRP 物流 系統(tǒng)優(yōu)化 運(yùn)籌學(xué) 1 引言 新技術(shù)的迅速發(fā)展，特別是電子商務(wù)的風(fēng)起云涌，為我國(guó)經(jīng)濟(jì)的快速發(fā)展提供了契機(jī) 。目前我國(guó)電子商務(wù)得到政府和民眾的支持，發(fā)展勢(shì)頭強(qiáng)勁，但是，由于它是一套全新 的技術(shù)，同時(shí)還是一種全新的管理理念，所以其發(fā)展過(guò)程中必然存在一些難題。在電子 商務(wù)“三流”（信息流、物流、資金流）中，隨著網(wǎng)絡(luò)基礎(chǔ)設(shè)施建設(shè)的成熟、電子商務(wù)網(wǎng) 站的蓬勃發(fā)展以及有效利用網(wǎng)絡(luò)資源觀念的普及，信息流的發(fā)展已經(jīng)比較成熟了；而隨 著各大銀行紛紛開展網(wǎng)上業(yè)務(wù)，以及支付網(wǎng)關(guān)的建立和加密技術(shù)的成熟，網(wǎng)上支付已經(jīng) 在許多網(wǎng)站上成為現(xiàn)實(shí)；然而，我國(guó)傳統(tǒng)的物流體系是在計(jì)劃經(jīng)濟(jì)環(huán)境下建立、發(fā)展起 來(lái)的，與目前的電子商務(wù)環(huán)境已經(jīng)無(wú)法相容?，F(xiàn)今物流體系的落后現(xiàn)狀已經(jīng)成為我國(guó)社 會(huì)經(jīng)濟(jì)快速發(fā)展的重要制約因素之一。所以對(duì)物流系統(tǒng)優(yōu)化的研究將會(huì)具有很大的現(xiàn)實(shí) 意義。 國(guó)外許多學(xué)者在電子商務(wù)出現(xiàn)之前就已經(jīng)研究物流系統(tǒng)優(yōu)化的問(wèn)題了，為各類實(shí)際問(wèn) 題構(gòu)建了優(yōu)化模型，并形成了許多解決問(wèn)題的算法。依據(jù)實(shí)際問(wèn)題的不同，可以對(duì)物流 系統(tǒng)優(yōu)化問(wèn)題進(jìn)行分類，比如，運(yùn)輸車輛路線安排問(wèn)題（VRP）、定位—配給問(wèn)題（LA） 、定位—運(yùn)輸路線安排問(wèn)題（LRP）等等，其中LRP更貼近目前的物流系統(tǒng)復(fù)雜的實(shí)際特征 ，所以對(duì)它的研究是十分有意義的。 本文先從VRP和LA的集成來(lái)探討LRP的由來(lái)，然后討論LRP的分類，同時(shí)探討LRP的研究 現(xiàn)狀，并對(duì)LRP的解決方法進(jìn)行概述，最后就LRP的未來(lái)發(fā)展方向作簡(jiǎn)要的討論。 2 從VRP、LA到LRP——物流系統(tǒng)的集成 依據(jù)實(shí)際問(wèn)題的不同，可以對(duì)物流系統(tǒng)優(yōu)化問(wèn)題進(jìn)行分類，比如確定設(shè)施（指的是物 品流動(dòng)的出發(fā)點(diǎn)和終到點(diǎn)，如配送中心、倉(cāng)庫(kù)、生產(chǎn)工廠、垃圾回收中心等）位置、運(yùn) 輸路線安排、庫(kù)存控制等，國(guó)內(nèi)外許多學(xué)者就各類問(wèn)題的特征進(jìn)行了分析，并提出了各 類問(wèn)題的數(shù)學(xué)模型和解決方法。 2.1 運(yùn)輸車輛路線安排問(wèn)題（Vehicle Routing Problems VRP） 該問(wèn)題可定義為：運(yùn)輸車輛從一個(gè)或多個(gè)設(shè)施到多個(gè)地理上分散的客戶點(diǎn)，優(yōu)化設(shè)計(jì) 一套貨物流動(dòng)的運(yùn)輸路線，同時(shí)要滿足一系列的約束條件。該問(wèn)題的前提條件是設(shè)施位 置、客戶點(diǎn)位置和道路情況已知，由此確定一套車輛運(yùn)輸路線，以滿足目標(biāo)函數(shù)（通常 ，VRP的目標(biāo)函數(shù)是總費(fèi)用最?。?。如圖1所示。 圖中，□表示設(shè)施；?表示客戶；↗表示運(yùn)輸路線 圖1 VRP的圖示 實(shí)際上，VRP是按如下假設(shè)定義的最小費(fèi)用問(wèn)題[1]： （1） 所有車輛路線均起始并終止于設(shè)施點(diǎn)。 （2） 每個(gè)客戶只接受一個(gè)設(shè)施的貨物。 （3） 滿足其他一些約束條件，如： ■ 容量限制：每個(gè)客戶點(diǎn)上都有一個(gè)非負(fù)的貨物需求量，但每條車輛路線上的貨物量 總和不超過(guò)車輛裝載量。如果此約束不滿足，則引入懲罰函數(shù)。 ■ 總時(shí)間限制：每條路線總的長(zhǎng)度或總耗時(shí)不超過(guò)一個(gè)事先定下的數(shù)值。這項(xiàng)限制旨 在滿足客戶對(duì)供貨時(shí)間的要求，以及對(duì)貨物品質(zhì)的保證。 ■ 具體時(shí)間限制：對(duì)某個(gè)客戶點(diǎn)，車輛到達(dá)時(shí)間限制在某一時(shí)間段內(nèi)。此約束在于滿足 客戶對(duì)供應(yīng)/回收的特殊要求。 ■ 車輛到達(dá)順序要求：如在到達(dá)i點(diǎn)之前要求先到達(dá)j點(diǎn)。 以上列出的約束只是該問(wèn)題一部分，具體操作時(shí)要視具體情況而定。 對(duì)VRP的求解算法可分為精確算法和啟發(fā)式算法兩種。其中精確算法包括樹狀尋優(yōu)算 法、動(dòng)態(tài)規(guī)劃和整數(shù)規(guī)劃。VRP的啟發(fā)式算法多是來(lái)源于對(duì)TSP問(wèn)題的求解算法。比如局 部?jī)?yōu)先算法、插值法等可以不用修改地用于一些VRP。 2.2 定位—配給問(wèn)題（Location-Allocation Problems, LA） 定位一配給問(wèn)題可定義為：依據(jù)客戶點(diǎn)的地理分布與貨物分配關(guān)系，確定出某一地理 范圍內(nèi)設(shè)施的數(shù)量和位置。如圖2所示。 圖中，□表示設(shè)施；?表示客戶；↗表示運(yùn)輸路線 圖2 LA的圖示 LA實(shí)質(zhì)上是一個(gè)依據(jù)優(yōu)化路徑的原則來(lái)確定在什么地方設(shè)置設(shè)施的過(guò)程[2]。例如， 在一個(gè)城鎮(zhèn)中設(shè)立一個(gè)急救中心，這個(gè)問(wèn)題就是一個(gè)典型的LA問(wèn)題。它的目標(biāo)就是使得 全鎮(zhèn)的居民到醫(yī)療中心的路徑（時(shí)間）總體上最短。 根據(jù)John Current等學(xué)者對(duì)此問(wèn)題的綜述研究[3]，把LA問(wèn)題進(jìn)行了分類。Current的方法是根據(jù)問(wèn) 題的目標(biāo)函數(shù)來(lái)分類的，作為分類依據(jù)的目標(biāo)函數(shù)共分四種： (1) 費(fèi)用最小化； (2) 客戶需求導(dǎo)向； (3) 利潤(rùn)最大化； (4) 其他相關(guān)考慮。 2.3 定位一運(yùn)輸路線安排問(wèn)題（Location-Routing problems,LRP） 當(dāng)今物流系統(tǒng)的環(huán)境日趨復(fù)雜，而且物流地理分布也不斷擴(kuò)大。物流系統(tǒng)優(yōu)化問(wèn)題的 各個(gè)子系統(tǒng)（比如設(shè)施定位問(wèn)題、物品配送問(wèn)題、運(yùn)輸車輛路線安排問(wèn)題等）之間的相 互影響也越來(lái)越大。對(duì)許多實(shí)際問(wèn)題，要綜合考慮以上問(wèn)題，這就形成了定位一路線安 排問(wèn)題（LRP）。 LRP可以表述為：給定與實(shí)際問(wèn)題相符的一系列客戶點(diǎn)和一系列潛在的設(shè)施點(diǎn)，在這 些潛在的點(diǎn)中確定出一系列的設(shè)施位置，同時(shí)要確定出一套從各個(gè)設(shè)施到各個(gè)客戶點(diǎn)的 運(yùn)輸路線，確定的依據(jù)是滿足問(wèn)題的目標(biāo)（通常是總的費(fèi)用最小）。客戶點(diǎn)的位置和客 戶的需求量是已知的或可估算的，貨物有一個(gè)或多個(gè)設(shè)施供應(yīng)，每個(gè)客戶只接收來(lái)自一 個(gè)設(shè)施的貨物，潛在設(shè)施點(diǎn)位置已知，問(wèn)題的目標(biāo)是把哪些潛在的設(shè)施建立起來(lái)，以使 的總的費(fèi)用最小。LRP可圖示為圖3。 可以說(shuō)LRP是LA與VRP的集成[4]，但比后兩者更復(fù)雜。LA在定位時(shí)考慮的是運(yùn)輸車輛 從設(shè)施點(diǎn)到一個(gè)客戶點(diǎn)后，隨即返回設(shè)施點(diǎn)，所以它不考慮路線安排問(wèn)題[5]。LA在確定 出設(shè)施點(diǎn)后的圖形是從設(shè)施點(diǎn)到客戶點(diǎn)的射線族。而LRP則在定位時(shí)同時(shí)確定運(yùn)輸路線。 LRP與VRP的不同之處是：VRP的前提條件是設(shè)施點(diǎn)和客戶點(diǎn)在空間上的分布是已知的；L RP所研究的問(wèn)題只知道潛在的設(shè)施點(diǎn)，在確定運(yùn)輸路線的同時(shí)要確定設(shè)施的位置。 圖中，□表示設(shè)施；△表示未被選中的設(shè)施；?表示客戶點(diǎn)；↗表示運(yùn)輸路線 圖3 LRP的圖示 在實(shí)際物流系統(tǒng)的集成的特征日益突出之前，就已經(jīng)有人研究LRP了。最早的研究可 以追溯到20世紀(jì)60年代，當(dāng)時(shí)有些學(xué)者已經(jīng)提出一些類似的概念了[6- 8]。到了70年代，Cooper[9, 10]把定位問(wèn)題與運(yùn)輸問(wèn)題結(jié)合起來(lái)，提出了運(yùn)輸一定位問(wèn)題（Transportation- Location problem）。在這個(gè)階段，學(xué)者們對(duì)LRP的研究還是相當(dāng)膚淺的，還沒(méi)有真正涉及運(yùn)輸路 線安排問(wèn)題。到了70年代中期，一些學(xué)者在研究運(yùn)輸一定位問(wè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)的。 3 LRP的分類 Hokey Min等學(xué)者對(duì)LRP進(jìn)行了詳細(xì)的分類[15]，其分類標(biāo)準(zhǔn)十分詳盡，幾乎包含了LRP的各個(gè)方 面。 表1 LRP的分類標(biāo)準(zhǔn) | |分類標(biāo)準(zhǔn) |A |B | |1 |物品流向 |單向 |雙向 | |2 |供/需特征 |確定 |隨機(jī) | |3 |設(shè)施數(shù)量 |單個(gè)設(shè)施 |多設(shè)施 | |4 |運(yùn)輸車輛數(shù)量 |單個(gè)車輛 |多車輛 | |5 |車輛裝載能力 |不確定 |確定 | |6 |設(shè)施容量 |不確定 |確定 | |7 |設(shè)施分級(jí) |單級(jí) |多級(jí) | |8 |計(jì)劃期間 |單期 |多期 | |9 |時(shí)間限制 |無(wú)時(shí)間限制 |有時(shí)間限制 | |10 |目標(biāo)數(shù) |單目標(biāo) |多目標(biāo) | |11 |模型數(shù)據(jù)類型 |假設(shè)值 |實(shí)際值 | Hokey的分類是依據(jù)問(wèn)題的特征進(jìn)行的，具體如表1。 表1中，各分類標(biāo)準(zhǔn)解釋如下： （1） 物品流向，單向物品流向問(wèn)題指的是所有設(shè)施只進(jìn)行輸入（供應(yīng)）或只進(jìn)行輸出（回收 ）的操作；而雙向物品流向問(wèn)題涉及的設(shè)施中有一部分既要輸入又要輸出。 （2） 供/需特征，確定型的是指物品供應(yīng)/需求量是已知的并在一定時(shí)期內(nèi)相對(duì)穩(wěn)定；隨機(jī)型 的是指供應(yīng)/需求量是不確定的。 （3） 設(shè)施數(shù)量，指所研究問(wèn)題要求設(shè)置設(shè)施的數(shù)量，分為單一設(shè)施和多設(shè)施兩種。 （4） 運(yùn)輸工具數(shù)量，是指有多少車輛為一個(gè)設(shè)施服務(wù)的標(biāo)準(zhǔn)，同時(shí)也確定了一個(gè)從設(shè)施出發(fā) 的路線數(shù)。分為單一車輛和多車輛兩種。 （5） 車輛裝載能力，是指是否要考慮車輛裝載能力的限制。不確定定型是指對(duì)這個(gè)問(wèn)題所涉 及的每條路線上的貨物總量很小，不會(huì)超出車輛的裝載量，所以不用考慮車輛的裝載能 力的限制；確定型是指每條路線上的貨物總量有可能超出車輛的裝載能力，所以要把車 輛的裝載限制作為一個(gè)參數(shù)引入問(wèn)題。 （6） 設(shè)施容量，是指是否考慮各個(gè)設(shè)施容量的限制。分為不確定型和確定型兩種。 （7） 設(shè)施分級(jí)，可以把設(shè)施分為兩種：總站型和中間轉(zhuǎn)運(yùn)站型?？傉拘驮O(shè)施是指那些車輛路 線的出發(fā)點(diǎn)或終點(diǎn)；中間轉(zhuǎn)運(yùn)站型設(shè)施是指物品的中間站，貨物運(yùn)入后還要運(yùn)出。有了 中間轉(zhuǎn)運(yùn)站，就產(chǎn)生了設(shè)施分級(jí)的問(wèn)題，貨物從總站型設(shè)施運(yùn)入中間轉(zhuǎn)運(yùn)站型設(shè)施，經(jīng) 過(guò)簡(jiǎn)單處理后運(yùn)到客戶點(diǎn)。單級(jí)設(shè)施問(wèn)題是指不考慮設(shè)施的分級(jí)，所有設(shè)施均為同級(jí)； 而多級(jí)中心設(shè)施問(wèn)題則要考慮設(shè)施的分級(jí)。 （8） 計(jì)劃期間，單期間問(wèn)題把整個(gè)期間作為一個(gè)時(shí)間段，是靜態(tài)問(wèn)題；多期間問(wèn)題把整個(gè)時(shí) 間段按問(wèn)題要求分為多個(gè)期間，是動(dòng)態(tài)問(wèn)題。 （9） 時(shí)間限制，主要是指滿足客戶要求或貨物品質(zhì)要求，而對(duì)LRP的從設(shè)施點(diǎn)到客戶點(diǎn)的時(shí)間 約束。分為無(wú)時(shí)間約束和有時(shí)間約束兩種。 （10） 目標(biāo)數(shù)量，LRP的目標(biāo)通常是總的費(fèi)用（包括建設(shè)設(shè)施費(fèi)用和車輛運(yùn)輸費(fèi)用等）最小，但 有時(shí)也需要考慮其他目標(biāo)，比如滿足顧客的特殊需要、總體利潤(rùn)量大化等等。如果是多 目標(biāo)問(wèn)題，經(jīng)常會(huì)出現(xiàn)各目標(biāo)之間的沖突。 （11） 模型數(shù)據(jù)類型，在有些情況下，模型中的數(shù)據(jù)（如物品供/需量等）是來(lái)源于實(shí)際的；而 有些情況下，這些數(shù)據(jù)是在實(shí)際中不可得的，需要對(duì)其進(jìn)行假設(shè)。根據(jù)模型數(shù)據(jù)類型的 不同，把LR...
0107112物流系統(tǒng)優(yōu)化中的定位-運(yùn)輸路線安排問(wèn)題(doc)