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

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