1、第二章 物流配送車輛路徑問題 2.1 問題的描述及各組成部分特點2.2 車輛路徑問題的分類 2.3 車輛路徑問題的研究現(xiàn)狀和發(fā)展趨勢 12.1 問題的描述及各組成部分特點配送活動中的配送車輛行駛線路優(yōu)化確定問題，是近二十多年來國際運(yùn)籌學(xué)界的研究熱點之一。 運(yùn)籌學(xué)界將此類問題統(tǒng)稱之為車輛路徑問題（Vehicle Routing Problem, VRP），或車輛調(diào)度問題（Vehicle Scheduling Problem, VSP）。一般描述是：對一系列給定的客戶點，確定配送車輛行駛路線，使其從配送中心出發(fā)，有序地對它們進(jìn)行服務(wù)，并在滿足一定的約束條件下（如車輛載重量、客戶需求量、服務(wù)時間限制

2、等），使總運(yùn)輸成本達(dá)到最?。ㄈ缡褂密囕v數(shù)最少、車輛行駛總距離最短等）。一般把最小化車輛使用數(shù)作為第一優(yōu)化目標(biāo)，而最小化車輛行駛距離作為第二優(yōu)化目標(biāo)。 2車輛路徑問題的特點1. 道路網(wǎng)（road network）弧表示路段，點表示道路交叉點、配送中心和客戶?；〉臋?quán)cij表示其距離或行駛時間。32. 客戶（customer） 用圖上的小圓點表示； 需運(yùn)送或收取的貨物量（需求量）di (或di和pi )；要求提供服務(wù)的時間段，即時間窗（time window） 在客戶點所花費的服務(wù)時間si； 能用于服務(wù)該客戶的車輛集合。3. 配送中心（車場）（distribution center，depot） 用

3、圖上的小方點表示；車輛行駛路線開始并終止于配送中心或某一個客戶點；其特征由所配備的車輛種類和數(shù)量、以及所能處理的貨物總量來描述。 44. 車輛（vehicle） 車輛是自備還是外租，完成任務(wù)后是否返回； 車輛的裝載能力;車輛使用費;可用于進(jìn)行貨物裝卸的設(shè)備.5. 駕駛員（driver） 給駕駛員安排取送貨任務(wù)時，必須符合工作時間方面的有關(guān)規(guī)定。 6. 路徑編排中的限制條件 車輛的當(dāng)前負(fù)載不能超過車輛的裝載量； 客戶只要求送貨、取貨、或取送貨兼有；在客戶所要求的時間窗和駕駛員的工作時間內(nèi)提供服務(wù)；訪問客戶的順序要求。 57. 行駛距離和行駛時間必須知道客戶點與客戶點之間，配送中心與客戶點之間的行

4、駛距離和行駛時間。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ā)點時（即車輛的行駛路線是閉合式的），稱之為閉合式車輛路徑問題（Closed VRP），通常簡稱為車輛路徑問題（VRP）。8當(dāng)不要求車輛完成任務(wù)后返回原出發(fā)點，或者是若要求返回原出發(fā)點，則沿原去程

5、路線返回時（即車輛的行駛路線是開放式的），稱之為開放式車輛路徑問題（Open VRP，OVRP）。9根據(jù)所包含的約束條件，問題又可進(jìn)一步分類。以閉合式VRP為例，可歸納如下： DCVRP 路程長度 VRPPD 裝載能力 取送作業(yè) CVRP VRPPDTW 時間窗 VRPTW 回程運(yùn)輸 VRPBTW VRPB102.2.1 帶裝載能力的VRP（Capacitated VRP，CVRP）問題的特點是VRP中的最基本型式。所有客戶都屬于要送貨的或要取貨的，其需求量預(yù)先知道，且不能被分割。 車輛類型相同且都停放在一個配送中心。對車輛只有裝載能力限制。 問題的目標(biāo)是最小化服務(wù)所有客戶的總費用（即所需要的

6、車輛數(shù)及其車輛行駛距離或行駛時間）。 問題的描述（可描述為如下的圖論問題）11設(shè)G = (V, A)為一個完備圖，其中V = 0,n為頂點集，A是弧集。頂點i = 1,n表示客戶，而頂點0表示配送中心。有時配送中心用頂點n +1來表示。 每條弧對應(yīng)著一個非負(fù)的費用cij，表示從點i到點j的行駛費用。 在一些測試算例中，頂點與給定坐標(biāo)的平面上的點相對應(yīng)，且弧的費用cij被定義為對應(yīng)于頂點i和j的兩點間的歐氏距離。 yj j (xj, yj) yi i (xi, yi) xj xi12在配送中心備有相同類型的車輛，每輛的裝載能力為C。每一條線路上的送貨任務(wù)只由一輛車承擔(dān)。 每個客戶 i 有一個已知

7、的需要送往交付的非負(fù)需求量di，假設(shè)di C。服務(wù)所有客戶至少所需要的車輛數(shù) 13CVRP是求一個具有最小總費用的由K條簡單回路組成的集合（每個回路對應(yīng)于一條配送車輛行駛線路），并滿足 (1)每個回路從配送中心出發(fā)并返回配送中心； (2) 每個客戶點只在一條回路上； (3) 一條回路上各客戶點的需求量之和不超過車輛裝載能力C。總費用一般包括所使用的車輛數(shù)（即回路數(shù)）和車輛行駛費用兩項。通常都認(rèn)為，多用一輛車所帶來的固定費用的增加，總是超過其因總行駛距離縮短所帶來的節(jié)省，因此，一般把最小化車輛使用數(shù)作為第一優(yōu)化目標(biāo)，最小化行駛費用作為第二目標(biāo)。 14當(dāng)備有的車輛類型不是同一種時，即有不同的裝載能

8、力Ck，k =1,K，則就為經(jīng)常考慮的另一種變形。CVRP是NP-難的，并且是旅行商問題（TSP）的一般化。在TSP中，要求確定一條經(jīng)過圖G中所有頂點的、費用最小的回路（哈密頓回路），當(dāng)CVRP中的Cdi和K=1時就為此情形。 152.2.2 帶路程長度的VRP（Distance-Constrained and Capacitated VRP，DCVRP）特點既有車輛裝載能力限制，又有最大路程長度限制。描述每條弧對應(yīng)著一個非負(fù)的長度tij，一般地，費用矩陣與長度矩陣相一致，即cij = tij。 每條線路上各弧的總長度不能超過線路的最大長度L。當(dāng)弧的長度代表的是行駛時間時，每個客戶i就對應(yīng)著一

9、個服務(wù)時間si，表示車輛必須在該客戶點停留的時間長度。 162.2.3 帶時間窗的VRP（VRP with time windows，VRPTW）除了車輛裝載能力約束外，每個客戶i 都有一個與之相聯(lián)系的要求提供服務(wù)的時間區(qū)間 ai, bi。 1.帶硬時間窗的VRP（VRP with hard time windows,VRPHTW）。在不需要嚴(yán)格區(qū)分的場合，一般就稱為帶時間窗的VRP。特點 客戶的服務(wù)必須在相應(yīng)的時間窗內(nèi)開始，車輛在客戶點的服務(wù)時間長度為si。 當(dāng)車輛提前到達(dá)客戶點時，必須等待到時刻ai才可開始服務(wù)。不允許在bi之后到達(dá)并開始服務(wù)。17對于配送中心，設(shè)服務(wù)時間s0 = 0，時間

10、窗 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 （VRP with soft time windows, VRPSTW）時間窗要求是軟的，即允許服務(wù)的開始時間有所偏離時間窗（早于ai或晚于bi ），但要根據(jù)所帶來的不方便程度支付一定的懲罰。可定義懲罰函

11、數(shù)來計算。 若某個客戶的時間窗不能被違反（硬的），則有偏離時應(yīng)支付的懲罰設(shè)為無窮大?？梢奦RPHTW實際上是VRPSTW的一種特殊情形。 由于允許以支付懲罰偏離時間窗，與VRPHTW相比，VRPSTW往往會在所需要的車輛數(shù)、或各線路總距離和總行駛時間方面獲得較大的節(jié)省。 192.2.4 帶回程運(yùn)輸?shù)腣RP （VRP with backhauls，VRPB）特點客戶集：去程客戶，L=1, 2, , n 回程客戶，B=n+1, , n+m先服務(wù)去程客戶，后服務(wù)回程客戶。 描述求一個具有最小總費用的由K條簡單回路組成的集合，并滿足 （1）、（2）同CVRP；（3）一條回路上各去程客戶點和回程客戶點的

12、需求量之和分別不超過車輛裝載能力C； （4）所有去程客戶必須先于回程客戶得到服務(wù)。 20擴(kuò)展帶回程運(yùn)輸和時間窗的VRP（VRP with backhauls and time windows, VRPBTW） 212.2.5 帶取送貨的VRP （VRP with pickup and delivery，VRPPD）特點客戶i對應(yīng)著兩個量：di，送往客戶i的貨物數(shù)量 pi，從客戶i收取的貨物數(shù)量Oi表示需送往客戶i的貨物的始發(fā)點， Di表示待取貨物的終到點。 在每個客戶點，規(guī)定先卸后裝。描述求一個具有最小總費用的由K條簡單回路組成的集合，并滿足 （1）、（2）同CVRP；（3）車輛的當(dāng)前負(fù)載必須

13、保持非負(fù)且C； 22（4）當(dāng)Oi不是配送中心時，它必須與客戶i在同一線路上且先于客戶i得到服務(wù)；（5）當(dāng)Di不是配送中心時，它必須與客戶i在同一線路上且后于客戶i得到服務(wù)。 擴(kuò)展帶取送貨和時間窗的VRP（VRP with pickup and delivery and time windows, VRPPDTW）。 232.3 車輛路徑問題的研究現(xiàn)狀和發(fā)展趨勢 Dantzig和Ramser于1959年首先對VRP進(jìn)行了研究。他們描述了一個將汽油送往各加油站的實際問題，并提出了相應(yīng)的數(shù)學(xué)規(guī)劃模型及其求解算法。1964年，Clarke和Wright提出一種對Dantzig-Ramser方法進(jìn)行改進(jìn)

14、的較有效的啟發(fā)式算法Clarke-Wright節(jié)約算法。在這兩篇開創(chuàng)性的論文發(fā)表后，VRP很快引起學(xué)術(shù)界和實際工作者的極大重視，成為近二十多年來運(yùn)籌學(xué)領(lǐng)域的研究熱點之一。特別是物流配送活動中的配送車輛行駛路徑問題，是近年來VRP的重點研究對象和應(yīng)用領(lǐng)域。 241983年，Bodin等人在長達(dá)140多頁的對VRP的研究進(jìn)展進(jìn)行綜述的文章中，就列舉了699篇相關(guān)的參考文獻(xiàn)。1995年出版的Handbooks in Operations Research and Management Science 中，第八卷就是專門討論車輛路徑問題的。 2002年， Paolo Toth和Daniele Vigo

15、在其出版的著作The Vehicle Routing Problem 中，對VRP的最新研究進(jìn)展和發(fā)展趨勢進(jìn)行了比較全面的分析。與國際上相比，國內(nèi)對VRP的研究相對較少，最近幾年才陸續(xù)有一些相關(guān)的研究成果發(fā)表。通過各國研究人員的共同努力，現(xiàn)已提出了許多用于求解不同類型的VRP的最優(yōu)解和近優(yōu)解的模型及其精確算法和啟發(fā)式算法。 252.3.1 車輛路徑問題的模型 CVRP的三下標(biāo)車輛流模型。 定義變量26模型272.3.2 VRP的計算復(fù)雜性和求解算法 對VRP求解算法的研究一直是重點和難點。現(xiàn)已證明，幾乎所有類型的VRP均為NP-難問題。VRP之所以引起學(xué)術(shù)界的極大重視，除了它具有廣泛的應(yīng)用背景

16、外，是因為相當(dāng)難解，從而富有挑戰(zhàn)性。目前已提出了許多求解VRP的算法，究其實質(zhì)，可分為精確算法和啟發(fā)式算法兩大類。28精確算法 指可求出其最優(yōu)解的算法，且一般要求問題能用相應(yīng)的數(shù)學(xué)模型表示。 目前用于求解VRP的精確算法主要有 分支定界法（Branch-and-Bound Algorithm） 分支切面法（Branch-and-Cut Algorithm） 割平面法（Cutting Plane Method） 因VRP是NP-難問題，其精確算法的計算量隨問題規(guī)模的增大呈指數(shù)增長，在實際中的應(yīng)用范圍有限。但在對相應(yīng)的啟發(fā)式算法的質(zhì)量評估等理論研究工作中卻很有意義。從實際應(yīng)用的角度來說，公認(rèn)的明智做法是設(shè)計相應(yīng)的啟發(fā)式算法來求出問題的近優(yōu)解。 29啟發(fā)式算法 是基于直觀或經(jīng)驗構(gòu)造的算法，一般不要求非得將問題表述為某種標(biāo)準(zhǔn)的數(shù)學(xué)模型；在可接受的計算量內(nèi)求出問題的滿意解，但不能保證最優(yōu)。1960-1990年間，所提出的求解VRP的啟發(fā)式算法都是基于經(jīng)典的啟發(fā)式方法的思想。 1990年以來，隨著通用啟發(fā)式算法（meta-heuristics）的出現(xiàn)，如模擬退火(SA)、禁忌搜索(TS)、遺傳算法(