物流配送優(yōu)化第二章

第二章物流配送車輛路徑問題

2.1問題的描述及各組成部分特點2.2車輛路徑問題的分類2.3車輛路徑問題的研究現(xiàn)狀和發(fā)展趨勢12.1問題的描述及各組成部分特點配送活動中的配送車輛行駛線路優(yōu)化確定問題，是近二十多年來國際運(yùn)籌學(xué)界的研究熱點之一。運(yùn)籌學(xué)界將此類問題統(tǒng)稱之為車輛路徑問題（VehicleRoutingProblem,VRP），或車輛調(diào)度問題（VehicleSchedulingProblem,VSP）。一般描述是：對一系列給定的客戶點，確定配送車輛行駛路線，使其從配送中心出發(fā)，有序地對它們進(jìn)行服務(wù)，并在滿足一定的約束條件下（如車輛載重量、客戶需求量、服務(wù)時間限制等），使總運(yùn)輸成本達(dá)到最?。ㄈ缡褂密囕v數(shù)最少、車輛行駛總距離最短等）。一般把最小化車輛使用數(shù)作為第一優(yōu)化目標(biāo)，而最小化車輛行駛距離作為第二優(yōu)化目標(biāo)。

2車輛路徑問題的特點1.道路網(wǎng)（roadnetwork）弧表示路段，點表示道路交叉點、配送中心和客戶?；〉臋?quán)cij表示其距離或行駛時間。32.客戶（customer）用圖上的小圓點表示；需運(yùn)送或收取的貨物量（需求量）di(或di和pi)；要求提供服務(wù)的時間段，即時間窗（timewindow）在客戶點所花費的服務(wù)時間si；

能用于服務(wù)該客戶的車輛集合。3.配送中心（車場）（distributioncenter，depot）

用圖上的小方點表示；車輛行駛路線開始并終止于配送中心或某一個客戶點；其特征由所配備的車輛種類和數(shù)量、以及所能處理的貨物總量來描述。

44.車輛（vehicle）車輛是自備還是外租，完成任務(wù)后是否返回；車輛的裝載能力;車輛使用費;可用于進(jìn)行貨物裝卸的設(shè)備.5.駕駛員（driver）給駕駛員安排取送貨任務(wù)時，必須符合工作時間方面的有關(guān)規(guī)定。6.路徑編排中的限制條件

車輛的當(dāng)前負(fù)載不能超過車輛的裝載量；客戶只要求送貨、取貨、或取送貨兼有；在客戶所要求的時間窗和駕駛員的工作時間內(nèi)提供服務(wù)；訪問客戶的順序要求。57.行駛距離和行駛時間必須知道客戶點與客戶點之間，配送中心與客戶點之間的行駛距離和行駛時間。8.

目標(biāo)（objectives）

最小化總運(yùn)輸成本，其大小取決于所需要的車輛數(shù)（或線路數(shù)）、總行駛距離（時間）；最小化與客戶的不完全服務(wù)等有關(guān)的懲罰值；均衡各線路上的行駛時間和車輛載重量。62.2車輛路徑問題的分類根據(jù)配送車輛完成配送任務(wù)后是否必須返回原出發(fā)點以及返回的形式，可將問題分為閉合式和開放式兩大類。在不需嚴(yán)格區(qū)分的場合，統(tǒng)稱VRP。7當(dāng)車輛完成運(yùn)輸任務(wù)后必須返回原出發(fā)點時（即車輛的行駛路線是閉合式的），稱之為閉合式車輛路徑問題（ClosedVRP），通常簡稱為車輛路徑問題（VRP）。8當(dāng)不要求車輛完成任務(wù)后返回原出發(fā)點，或者是若要求返回原出發(fā)點，則沿原去程路線返回時（即車輛的行駛路線是開放式的），稱之為開放式車輛路徑問題（OpenVRP，OVRP）。9根據(jù)所包含的約束條件，問題又可進(jìn)一步分類。以閉合式VRP為例，可歸納如下：

DCVRP路程長度VRPPD裝載能力取送作業(yè)

CVRP

VRPPDTW時間窗VRPTW回程運(yùn)輸VRPBTWVRPB102.2.1帶帶裝載載能力力的VRP（CapacitatedVRP，CVRP））問題的的特點點是VRP中的最最基本本型式式。所有客客戶都都屬于于要送送貨的的或要要取貨貨的，，其需需求量量預(yù)先先知道道，且且不能能被分分割。。車輛類類型相相同且且都停停放在在一個個配送送中心心。對車輛輛只有有裝載載能力力限制制。問題的的目標(biāo)標(biāo)是最最小化化服務(wù)務(wù)所有有客戶戶的總總費用用（即即所需需要的的車輛輛數(shù)及及其車車輛行行駛距距離或或行駛駛時間間）。。問題的的描述述（可可描述述為如如下的的圖論論問題題）11設(shè)G=(V,A)為一個個完備備圖，，其中中V={0,…,n}為頂點點集，，A是弧集集。頂頂點i=1,……,n表示客客戶，，而頂頂點0表示示配送送中心心。有有時配配送中中心用用頂點點n+1來表示示。每條弧弧對應(yīng)應(yīng)著一一個非非負(fù)的的費用用cij，表示從從點i到點j的行駛駛費用用。在一些些測試試算例例中，，頂點點與給給定坐坐標(biāo)的的平面面上的的點相相對應(yīng)應(yīng)，且且弧的的費用用cij被定義義為對對應(yīng)于于頂點點i和j的兩點點間的的歐氏氏距離離。yjj(xj,yj)yii(xi,yi)xjxi12在配配送送中中心心備備有有相相同同類類型型的的車車輛輛，，每每輛輛的的裝裝載載能能力力為為C。每每一一條條線線路路上上的的送送貨貨任任務(wù)務(wù)只只由由一一輛輛車車承承擔(dān)擔(dān)。。每個客戶戶i有一個已已知的需需要送往往交付的的非負(fù)需需求量di，假設(shè)di<C。服務(wù)所有有客戶至至少所需需要的車車輛數(shù)13CVRP是求一個個具有最最小總費費用的由由K條簡單回回路組成成的集合合（每個個回路對對應(yīng)于一一條配送送車輛行行駛線路路），并并滿足(1)每個回路路從配送送中心出出發(fā)并返返回配送送中心；；(2)每個客戶戶點只在在一條回回路上；；(3)一條回路路上各客客戶點的的需求量量之和不不超過車車輛裝載載能力C?？傎M用一一般包括括所使用用的車輛輛數(shù)（即即回路數(shù)數(shù)）和車車輛行駛駛費用兩兩項。通通常都認(rèn)認(rèn)為，多多用一輛輛車所帶帶來的固固定費用用的增加加，總是是超過其其因總行行駛距離離縮短所所帶來的的節(jié)省，，因此，，一般把把最小化化車輛使使用數(shù)作作為第一一優(yōu)化目目標(biāo)，最最小化行行駛費用用作為第第二目標(biāo)標(biāo)。14當(dāng)備有的的車輛類類型不是是同一種種時，即即有不同同的裝載載能力Ck，k=1,……,K，則就為經(jīng)經(jīng)常考慮慮的另一一種變形形。CVRP是NP-難的，并并且是旅旅行商問問題（TSP）的一般化化。在TSP中，要求求確定一一條經(jīng)過過圖G中所有頂頂點的、、費用最最小的回回路（哈哈密頓回回路），，當(dāng)CVRP中的C≥∑di和K=1時就為此此情形。。152.2.2帶帶路程長長度的VRP（（Distance-ConstrainedandCapacitatedVRP，DCVRP）特點既有車輛裝載載能力限制，，又有最大路路程長度限制制。描述每條弧對應(yīng)著著一個非負(fù)的的長度tij，一般地，費用用矩陣與長度度矩陣相一致致，即cij=tij。每條線路上各各弧的總長度度不能超過線線路的最大長長度L。當(dāng)弧的長度代代表的是行駛駛時間時，每每個客戶i就對應(yīng)著一個個服務(wù)時間si，表示車輛必須須在該客戶點點停留的時間間長度。162.2.3帶帶時間窗的的VRP

（VRPwithtimewindows，VRPTW）除了車輛裝載載能力約束外外，每個客戶戶i都有一個與之之相聯(lián)系的要要求提供服務(wù)務(wù)的時間區(qū)間間[ai,bi]。1.帶硬時間窗的VRP（VRPwithhardtimewindows,VRPHTW）。在不需要嚴(yán)格格區(qū)分的場合合，一般就稱稱為帶時間窗窗的VRP。特點客戶的服務(wù)必必須在相應(yīng)的的時間窗內(nèi)開開始，車輛在在客戶點的服服務(wù)時間長度度為si。當(dāng)車輛提前到到達(dá)客戶點時時，必須等待待到時刻ai才可開始服務(wù)務(wù)。不允許在在bi之后到達(dá)并開開始服務(wù)。17對于配送中心心，設(shè)服務(wù)時時間s0=0，時間窗[a0,b0]。應(yīng)注意的是，，時間窗的要要求導(dǎo)致每條條線路具有隱含的方方向性，以及線路長度的限限制，最大線路長長度為L=b0。描述VRPHTW是求一個具有有最小總費用用的由K條簡單回路組組成的集合，，并滿足（1）、（2）、（3））同CVRP；（4）對每個客戶i，服務(wù)在時間窗窗[ai,bi]內(nèi)開始，車輛輛的停留時間間長度為si。當(dāng)ai=0,bi=+∞時，VRPHTW就為CVRP。182.帶軟時間窗的VRP（（VRPwithsofttimewindows,VRPSTW）時間窗要求求是軟的，，即允許服服務(wù)的開始始時間有所所偏離時間間窗（早于于ai或晚于bi），但要根據(jù)所所帶來的不不方便程度度支付一定定的懲罰。?？啥x懲懲罰函數(shù)來來計算。若某個客戶戶的時間窗窗不能被違違反（硬的的），則有有偏離時應(yīng)應(yīng)支付的懲懲罰設(shè)為無無窮大?？煽梢奦RPHTW實際上是VRPSTW的一種特殊殊情形。由于允許以以支付懲罰罰偏離時間間窗，與VRPHTW相比，VRPSTW往往會在所所需要的車車輛數(shù)、或或各線路總總距離和總總行駛時間間方面獲得得較大的節(jié)節(jié)省。192.2.4帶回程程運(yùn)輸?shù)腣RP（（VRPwithbackhauls，VRPB）特點客戶集：去去程客戶，，L={1,2,……,n}回程客戶，，B={n+1,……,n+m}先服務(wù)去程程客戶，后后服務(wù)回程程客戶。描述求一個具有有最小總費費用的由K條簡單回路路組成的集集合，并滿滿足（1）、（（2）同CVRP；；（3）一條回路上上各去程客客戶點和回回程客戶點點的需求量量之和分別別不超過車車輛裝載能能力C；（4）所有去程客客戶必須先先于回程客客戶得到服服務(wù)。20擴(kuò)展帶回程運(yùn)輸輸和時間窗窗的VRP（VRPwithbackhaulsandtimewindows,VRPBTW）212.2.5帶取送送貨的VRP（（VRPwithpickupanddelivery，VRPPD）特點客戶i對應(yīng)著兩個個量：di，送往客戶i的貨物數(shù)量量pi，從客戶i收取的貨物物數(shù)量Oi表示需送往往客戶i的貨物的始始發(fā)點，Di表示待取貨貨物的終到到點。在每個客戶戶點，規(guī)定定先卸后裝裝。描述求一個具有有最小總費費用的由K條簡單回路路組成的集集合，并滿滿足（1）、（（2）同CVRP；；（3）車輛的當(dāng)前前負(fù)載必須須保持非負(fù)負(fù)且≤C；22（4）當(dāng)Oi不是配送中中心時，它它必須與客客戶i在同一線路路上且先于于客戶i得到服務(wù)；；（5）當(dāng)Di不是配送中中心時，它它必須與客客戶i在同一線路路上且后于于客戶i得到服務(wù)。。擴(kuò)展帶取送貨和和時間窗的的VRP（VRPwithpickupanddeliveryandtimewindows,VRPPDTW）。232.3車輛路徑問問題的研究究現(xiàn)狀和發(fā)發(fā)展趨勢Dantzig和Ramser于1959年年首首先先對對VRP進(jìn)行行了了研研究究。。他他們們描描述述了了一一個個將將汽汽油油送送往往各各加加油油站站的的實實際際問問題題，，并并提提出出了了相相應(yīng)應(yīng)的的數(shù)數(shù)學(xué)學(xué)規(guī)規(guī)劃劃模模型型及及其其求求解解算算法法。。1964年年，，Clarke和Wright提出出一一種種對對Dantzig-Ramser方法法進(jìn)進(jìn)行行改改進(jìn)進(jìn)的的較較有有效效的的啟啟發(fā)發(fā)式式算算法法———Clarke-Wright節(jié)約約算算法法。。在這這兩兩篇篇開開創(chuàng)創(chuàng)性性的的論論文文發(fā)發(fā)表表后后，，VRP很快快引引起起學(xué)學(xué)術(shù)術(shù)界界和和實實際際工工作作者者的的極極大大重重視視，，成成為為近近二二十十多多年年來來運(yùn)運(yùn)籌籌學(xué)學(xué)領(lǐng)領(lǐng)域域的的研研究究熱熱點點之之一一。。特別別是是物物流流配配送送活活動動中中的的配配送送車車輛輛行行駛駛路路徑徑問問題題，，是是近近年年來來VRP的的重重點點研研究究對對象象和和應(yīng)應(yīng)用用領(lǐng)領(lǐng)域域。。241983年年，，Bodin等人人在在長長達(dá)達(dá)140多多頁頁的的對對VRP的研研究究進(jìn)進(jìn)展展進(jìn)進(jìn)行行綜綜述述的的文文章章中中，，就就列列舉舉了了699篇篇相相關(guān)關(guān)的的參參考考文文獻(xiàn)獻(xiàn)。。1995年年出出版版的的《《HandbooksinOperationsResearchandManagementScience》中中，，第第八八卷卷就就是是專專門門討討論論車車輛輛路路徑徑問問題題的的。。2002年年，，PaoloToth和DanieleVigo在其其出出版版的的著著作作《TheVehicleRoutingProblem》》中，，對對VRP的最最新新研研究究進(jìn)進(jìn)展展和和發(fā)發(fā)展展趨趨勢勢進(jìn)進(jìn)行行了了比比較較全全面面的的分分析析。。與國國際際上上相相比比，，國國內(nèi)內(nèi)對對VRP的研研究究相相對對較較少少，，最最近近幾幾年年才才陸陸續(xù)續(xù)有有一一些些相相關(guān)關(guān)的的研研究究成成果果發(fā)發(fā)表表。。通過過各各國國研研究究人人員員的的共共同同努努力力，，現(xiàn)現(xiàn)已已提提出出了了許許多多用用于于求求解解不不同同類類型型的的VRP的最最優(yōu)優(yōu)解解和和近近優(yōu)優(yōu)解解的的模模型型及及其其精精確確算算法法和和啟啟發(fā)發(fā)式式算算法法。。252.3.1車車輛輛路路徑徑問問題題的的模模型型CVRP的三三下下標(biāo)標(biāo)車車輛輛流流模模型型。。定義義變變量量26模型型272.3.2VRP的計計算算復(fù)復(fù)雜雜性性和和求求解解算算法法對VRP求解解算算法法的的研研究究一一直直是是重重點點和和難難點點?！，F(xiàn)已證證明，，幾乎乎所有有類型型的VRP均為NP-難問題題。VRP之所以以引起起學(xué)術(shù)術(shù)界的的極大大重視視，除除了它它具有有廣泛泛的應(yīng)應(yīng)用背背景外外，是是因為為相當(dāng)當(dāng)難解解，從從而富富有挑挑戰(zhàn)性性。目前已提出出了許許多求求解VRP的算法法，究其實實質(zhì)，，可分為精確算算法和啟發(fā)式式算法法兩大類類。28精確算算法指可求求出其其最優(yōu)優(yōu)解的的算法法，且且一般般要求求問題題能用用相應(yīng)應(yīng)的數(shù)數(shù)學(xué)模模型表表示。。目前用用于求求解VRP的精確確算法法主要要有分支定定界法法（Branch-and-BoundAlgorithm）分支切切面法法（Branch-and-CutAlgorithm）割平面面法（CuttingPlaneMethod）因VRP是NP-難問問題，，其精精確算算法的的計算算量隨隨問題題規(guī)模模的增增大呈呈指數(shù)數(shù)增長長，在在實際際中的的應(yīng)用用范圍圍有限限。但但在對對相應(yīng)應(yīng)的啟啟發(fā)式式算法法的質(zhì)質(zhì)量評評估等等理論論研究究工作作中卻卻很有有意義義。從實際際應(yīng)用用的角角度來來