物流配送車輛路徑問(wèn)題

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

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

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

4、駛距離和行駛時(shí)間。8. 目標(biāo)（objectives） 最小化總運(yùn)輸成本，其大小取決于所需要的車輛數(shù)（或線路數(shù)）、總行駛距離（時(shí)間）；最小化與客戶的不完全服務(wù)等有關(guān)的懲罰值； 均衡各線路上的行駛時(shí)間和車輛載重量。 62.2 車輛路徑問(wèn)題的分類根據(jù)配送車輛完成配送任務(wù)后是否必須返回原出發(fā)點(diǎn)以及返回的形式，可將問(wèn)題分為閉合式和開放式兩大類。在不需嚴(yán)格區(qū)分的場(chǎng)合，統(tǒng)稱VRP。7當(dāng)車輛完成運(yùn)輸任務(wù)后必須返回原出發(fā)點(diǎn)時(shí)（即車輛的行駛路線是閉合式的），稱之為閉合式車輛路徑問(wèn)題（Closed VRP），通常簡(jiǎn)稱為車輛路徑問(wèn)題（VRP）。8當(dāng)不要求車輛完成任務(wù)后返回原出發(fā)點(diǎn)，或者是若要求返回原出發(fā)點(diǎn)，則沿原去程

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

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

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

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

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

10、窗 a0, b0。應(yīng)注意的是，時(shí)間窗的要求導(dǎo)致每條線路具有隱含的方向性，以及線路長(zhǎng)度的限制，最大線路長(zhǎng)度為L(zhǎng) =b0。 描述VRPHTW是求一個(gè)具有最小總費(fèi)用的由K條簡(jiǎn)單回路組成的集合，并滿足（1）、（2）、（3）同CVRP；（4）對(duì)每個(gè)客戶i，服務(wù)在時(shí)間窗ai, bi內(nèi)開始，車輛的停留時(shí)間長(zhǎng)度為si。 當(dāng)ai = 0, bi = +時(shí)，VRPHTW就為CVRP。 182.帶軟時(shí)間窗的VRP （VRP with soft time windows, VRPSTW）時(shí)間窗要求是軟的，即允許服務(wù)的開始時(shí)間有所偏離時(shí)間窗（早于ai或晚于bi ），但要根據(jù)所帶來(lái)的不方便程度支付一定的懲罰?？啥x懲罰函

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

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

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

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

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

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