專題2-車輛路徑問題.ppt

2006.12.8 張軍,車輛路徑問題,主要內(nèi)容,什么是VRP VRP背景及應(yīng)用 VRP問題定義 VRP問題的分類 VRP問題數(shù)學(xué)模型 VRP算法類型及簡(jiǎn)要介紹 近年來(lái)關(guān)于VRP的研究,一、什么是VRP,VRP（Vehicle Routing Problem） 車輛路徑問題 當(dāng)不考慮時(shí)間要求，僅根據(jù)空間位置安排線路時(shí)，稱為車輛路徑問題。,二、VRP的背景及應(yīng)用,車輛路徑問題是由G.Dantzig和J.Ramser于1959年首先提出來(lái)的,很快引起運(yùn)籌學(xué)、管理學(xué)、計(jì)算機(jī)應(yīng)用、組合數(shù)學(xué)、圖論等學(xué)科的專家學(xué)者的高度重視。 其研究結(jié)果在運(yùn)輸系統(tǒng)、物流配送系統(tǒng)、快遞收發(fā)系統(tǒng)中都已得到廣泛應(yīng)用。,三、VRP問題定義,對(duì)一系列發(fā)貨點(diǎn)或收貨點(diǎn)，組織適當(dāng)?shù)男熊嚶肪€，使車輛有序地通過它們，在滿足一定的約束條件(如貨物需求量、發(fā)送量、交發(fā)貨時(shí)間、車輛容量限制、行駛里程限制、時(shí)間限制等) 下，達(dá)到一定的目標(biāo)(如路程最短、費(fèi)用最小、時(shí)間盡量少、使用車輛盡量少等)。,四、VRP問題的分類,按任務(wù)特征分類 裝貨問題(Pure Pick Up )、卸貨問題(Pure Delivery)及裝卸混合問題(Combined Pick Up and Delivery) 按任務(wù)性質(zhì)分類 有對(duì)弧服務(wù)問題(如中國(guó)郵遞員問題) 和對(duì)點(diǎn)服務(wù)問題(如旅行商問題) 以及混合服務(wù)問題(如交通車路線安排問題) 按車輛載貨狀況分類 有滿載問題和非滿載問題,按車場(chǎng)數(shù)目分類 有單車場(chǎng)問題和多車場(chǎng)問題 按車輛類型分類 有單車型問題和多車型問題 按車輛對(duì)車場(chǎng)的所屬關(guān)系分類 有車輛開放問題(車輛可不返回車場(chǎng))和車輛封閉問題(車輛必須返回車場(chǎng)) 按已知信息的特征分類 有確定性VRP和不確定性VRP,其中不確定性VRP 可進(jìn)一步分為隨機(jī)VRP(SVRP)和模糊VRP(FVRP),按優(yōu)化目標(biāo)數(shù)來(lái)分類 有單目標(biāo)問題和多目標(biāo)問題 按約束條件分類 有距離約束的VRP問題(Distance Constrained Vehicle Routing Problem) 有能力約束的VRP問題(Vehicle Routing Problem with Capacity Restriction ) 對(duì)稱問題和非對(duì)稱問題 三角不等式問題,按約束條件分類 有等需求問題(Equal Demand)和非等需求問題(Unequal Demand) 有時(shí)間窗的VRP問題(Vehicle Routing Problem with Time Window) 該問題中還包括柔性時(shí)間窗約束和剛性時(shí)間窗約束,五、VRP問題的數(shù)學(xué)模型,(1)問題 從一個(gè)配送中心出發(fā)，向多個(gè)客戶點(diǎn)送貨，然后在同一天內(nèi)返回到該配送中心，要安排一個(gè)滿意的運(yùn)行路線。 (2)已知條件 配送中心擁有的車輛臺(tái)數(shù)m及每輛車的載重量（噸位）為 需求點(diǎn) 數(shù)為n及每個(gè)點(diǎn)的需貨量為 配送中心到各需求點(diǎn)的費(fèi)用及各需求點(diǎn)之間的費(fèi)用為,五、VRP問題的數(shù)學(xué)模型,(3)目標(biāo) 各車輛行走的路徑使總運(yùn)輸費(fèi)用最小。 (4)模型中符號(hào)定義 所有收貨點(diǎn)的貨物量需求為 車輛的容量限制 決策變量,五、VRP問題的數(shù)學(xué)模型,數(shù)學(xué)模型為：,每輛車所運(yùn)送的貨物量不超過其載重量,每個(gè)需求點(diǎn)由且僅由一輛車送貨,若客戶點(diǎn)j由車輛k送貨，則車輛k必由某點(diǎn)i到達(dá)點(diǎn)j,若客戶點(diǎn)i由車輛k送貨，則車輛k送完該點(diǎn)的貨后必到達(dá)另一點(diǎn)j,六、VRP算法類型及簡(jiǎn)要介紹,VRP算法類型 精確解法 啟發(fā)式算法,C-W節(jié)約算法,算法的思想 假定有n個(gè)訪問地，把每個(gè)訪問地看成一個(gè)點(diǎn)，并取其中 的一個(gè)點(diǎn)作為基點(diǎn)。首先將每個(gè)點(diǎn)與基點(diǎn)相聯(lián)接，構(gòu)成 線路1j1(j2，3,n)這樣就得到一個(gè)具有n-1條 線路的圖。旅行者按照此路線訪問的n個(gè)點(diǎn)所走的路程總 為 z=2c1j ,其中c1j 為點(diǎn)1到點(diǎn)j(j2，3,n)的路段 長(zhǎng)度，這里假定c1j cj1（對(duì)所有點(diǎn)j）。若聯(lián)接點(diǎn)i和j, 即使旅行者走弧(i,j),所節(jié)約的路程值(i,j)可計(jì)算如 下：s(i,j)=2 c1i+2 c1j (c1i + c1j + cij )。對(duì)不同的點(diǎn)對(duì) s(i,j)越大，所節(jié)約的路程越多，因此應(yīng)優(yōu)先將這段弧插 入到旅行線路中。,算法的步驟 (1)選取基點(diǎn)，將基點(diǎn)與其他各點(diǎn)聯(lián)接，得到n-1條線路1-j-1(j2，3,n) (2)對(duì)不違背條件的所有可聯(lián)接點(diǎn)對(duì)(i,j)計(jì)算節(jié)約值s(i,j)=c1i + c1j cij (3)將所有的s(i,j)按其值由大到小排列。 (4)按s(i,j)值的上述順序，逐個(gè)考察其端點(diǎn)i和j，若滿足以下條件，就將弧(i,j)插入到線路中。其條件是： 點(diǎn)i和點(diǎn)j不在一條線路上 點(diǎn)i和點(diǎn)j均與基點(diǎn)相鄰。 (5)返回步驟(4),直至考察完所有的弧為止。 通過上面的步驟，使問題的解逐步得到改善，最后 達(dá)到滿意解。,C-W節(jié)約算法,y,例：用C-W節(jié)約算法求解下述TSP問題，已知訪問點(diǎn)的位置如下所示,各點(diǎn)坐標(biāo)： A(10,23) B(0,13) C(1,0) D(21,2) E(13,4) F(11,6) G(10,10),各點(diǎn)對(duì)之間的距離，cij=cji,按各段弧節(jié)約值由大到小的順序進(jìn)行排列,最后得到的線路為A-G-D-E-F-C-B-A，線路總長(zhǎng)度為76.52,插入法,算法思想 在已有的路徑中插入別的需求點(diǎn)，從而不斷擴(kuò)大配送路徑，在插入其他需求點(diǎn)時(shí)，需檢驗(yàn)是否滿足最大運(yùn)距約束、最大載重量約束和作業(yè)時(shí)間約束等條件。 算法步驟 分別對(duì)于每臺(tái)配送車輛適當(dāng)選擇客戶群。 在配送中心與客戶群之間構(gòu)筑路徑，以此作為初始路徑。 對(duì)于客戶群之外的客戶k按照適當(dāng)順序，在具有實(shí)施可能性而且使總的費(fèi)用增加最小。,由此帶來(lái)的費(fèi)用：,其中 為插入客戶k時(shí)，客戶j的等待時(shí)間增量,Sweep算法,算法思想 顧客點(diǎn)的位置以極坐標(biāo)給出。倉(cāng)庫(kù)假設(shè)在原點(diǎn)的位置，客戶點(diǎn)按照角度的逐步增加被排序，如果兩個(gè)點(diǎn)有同樣的角度，那么半徑小的先訪問。然后在滿足可行性條件的前提下,按角度大小歸并到不同的子路徑中,最后再根據(jù)TSP的優(yōu)化算法對(duì)所得到的子路徑進(jìn)行優(yōu)化。 算法步驟 從倉(cāng)庫(kù)出發(fā)。 在目前的車輛路徑中加入目前序號(hào)最小的顧客點(diǎn)，如果車輛超載了，選擇一個(gè)新的車輛，回到步驟1 重復(fù)步驟2直到所有的客戶點(diǎn)都被訪問。 構(gòu)造完初始路徑后，通過交換路徑中的節(jié)點(diǎn)來(lái)改善調(diào)度。,先路徑后分組算法,算法思想 先松弛模型中關(guān)于車輛載重和距離等的約束，構(gòu)造一個(gè)或幾個(gè)很長(zhǎng)的路徑，然后把這些很長(zhǎng)的線路分解成一些短而可行的線路。 算法步驟 尋求對(duì)于每個(gè)節(jié)點(diǎn)通過一次且只通過一次的巡回路徑。 在滿足步驟1上的路徑中節(jié)點(diǎn)的連續(xù)性和給定的條件（最大裝載量或最大距離）下進(jìn)行分組。 確定各組需求點(diǎn)的最優(yōu)訪問順序。,常用的分組方法有集合劃分算法(Set Partitioning Approach)、集合覆蓋算法(Set Covering Approach)、最優(yōu)劃分法(Optimal Partitioning Method)和填充曲線法(Spacefilling Curve Method),先分組后路徑算法,算法思路 這種方法先按節(jié)點(diǎn)和/或弧的要求進(jìn)行分組或劃群,然后對(duì)每一組設(shè)計(jì)一條經(jīng)濟(jì)的路線。 算法步驟 先將客戶按其地理位置和需求量合理地分成若干組，每組客戶的需求總量不超過配送車輛的裝載限量。 對(duì)各組加上倉(cāng)庫(kù)求巡回路徑。,領(lǐng)域分派法,Gillett&Miller的 扇形分派法,Marchetti&Spaccamela的 極線分派法,領(lǐng)域分派法,Karp的 矩形分派法,Haimovitch&Rinnooy Kan的 圓形分派法,近年來(lái)關(guān)于VRP的研究,國(guó)內(nèi)關(guān)于VRP研究的特點(diǎn)是： (1)所研究的問題類型確定性占大多數(shù)。 (2)開始使用蟻群算法、粒子群、免疫算法等新的啟發(fā)式算法解決VRP問題。 (3)研究具有時(shí)間窗約束的VRP。 (4)我國(guó)開始研究關(guān)于開路式VRP，但是文獻(xiàn)非常少，僅1篇。,近年來(lái)關(guān)于VRP的研究,國(guó)外關(guān)于VRP研究的特點(diǎn)是： 國(guó)外對(duì)VRP問題研究比國(guó)內(nèi)早大約30余年，因此國(guó)外關(guān)于VRP問題的文獻(xiàn)相當(dāng)豐富，而且對(duì)該問題的研究還有逐年增加的趨勢(shì)。國(guó)外的VRP研究主要集中在新的約束條件或新的問題實(shí)例下VRP的建模及快速求解方法上，來(lái)更好的適用于不同的實(shí)際情況。,The End,Thank You,depot customer,中國(guó)郵遞員問題,一名郵遞員帶著要分發(fā)的郵件從郵局出發(fā)，經(jīng)過要分發(fā)的每個(gè)街道，送完郵件后又返回郵局如果他必須至少一次走過他管轄范圍內(nèi)的每一條街道，如何選擇投遞路線，使郵遞員走盡可能少的路程,TSP問題,旅行商問題，即TSP問題（Trav