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

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

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

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

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

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

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

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

8、變形。CVRP是NP-難的，并且是旅行商問題(TSP的一般化。在 TSP中，要求確定一條經(jīng)過圖G中所有頂點(diǎn)的、費(fèi)用最小的回路(哈密頓回路)，當(dāng)CVRP中的 OE di和K=1時(shí)就為此情形。*帶路程長(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)度不能超過線路的最大長(zhǎng)度 L。當(dāng)弧的長(zhǎng)度代表的是行駛時(shí)間時(shí)，每個(gè)客戶i就對(duì)應(yīng)著一個(gè)服務(wù)時(shí)間 si,表示車輛必須在該客戶點(diǎn)停留的

9、時(shí)間長(zhǎng)度。*帶時(shí)間窗的 VRP( VRP with time windows , VRPTW)除了車輛裝載能力約束外, 每個(gè)客戶 i 都有一個(gè)與之相聯(lián)系的要求提供服務(wù)的時(shí)間區(qū)間 ai, bi。1帶硬時(shí)間窗的 VRP(VRP with hard time win dows,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ù)。*對(duì)于配送中心，設(shè)服務(wù)時(shí)間s0 = 0，時(shí)間窗 a0, b0 。應(yīng)注意的是， 時(shí)間

10、窗的要求導(dǎo)致每條線路具有隱含的方向性， 以及線路長(zhǎng)度的限制， 最大線 路長(zhǎng)度為 L =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 = +s時(shí)，VRPHTW就為 CVRP*2.帶軟時(shí)間窗的 VRP（ VRP with soft timewindows, VRPSTW）時(shí)間窗要求是軟的,即允許服務(wù)的開始時(shí)間有所偏離時(shí)間窗（早于ai 或晚于 bi ）,但要根據(jù)所帶來的不方便程度支付一定的懲罰?？啥x懲罰函數(shù)來計(jì)算。若某個(gè)客戶的

11、時(shí)間窗不能被違反（硬的）,則有偏離時(shí)應(yīng)支付的懲罰設(shè)為無窮大?？梢奦RPHTW實(shí)際上是VRPSTW的一種特殊情形。由于允許以支付懲罰偏離時(shí)間窗，與VRPHTW相比，VRPSTW往往會(huì)在所需要的車輛數(shù)、或各線路總距離和總行駛時(shí)間方面獲得較大的節(jié)省。*帶回程運(yùn)輸?shù)?VRP（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)的需求量之和分別不超過車輛裝載能力C；（4）所有去程客戶

12、必須先于回程客戶得到服務(wù)。*擴(kuò)展 帶回程運(yùn)輸和時(shí)間窗的 VRP（VRP with backhauls and time windows, VRPBTW）*帶取送貨的 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ù)載必須保持非負(fù)且wC;*( 4)當(dāng) Oi 不是配送中心時(shí)，它必須

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

14、larke-Wright 節(jié)約算法。在這兩篇開創(chuàng)性的論文發(fā)表后， VRP很快引起學(xué)術(shù)界和實(shí)際工作者的極大重視，成為近二十多年來運(yùn)籌學(xué)領(lǐng)域的研究熱點(diǎn)之一。 特別是物流配送活動(dòng)中的配送車輛行駛路徑問題， 是近 年來VRP的重點(diǎn)研究對(duì)象和應(yīng)用領(lǐng)域。*1983年，Bodin等人在長(zhǎng)達(dá)140多頁的對(duì)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 中， 對(duì)VRP的最新研究進(jìn)展和發(fā)展趨勢(shì)進(jìn)行了比較全面的分析。與國(guó)際上相比，國(guó)內(nèi)對(duì) VRP的研究相對(duì)較少，最近幾年才陸續(xù)有一些相關(guān)的研究成果發(fā)表。通過各國(guó)研究人員的共同努力，現(xiàn)已提出了許多用于求解不同類型的VRP 的最優(yōu)解和近優(yōu)解的模型及其精確算法和啟發(fā)式算法。*2.3.1 車輛路徑問題的模型CVRP的三下標(biāo)車輛流模型。定義變量*模型*232 VRP的計(jì)算復(fù)雜性和求解算法對(duì)VRP求解算法的研究一直是重點(diǎn)和難點(diǎn)?，F(xiàn)已證明，幾乎所有類型的VRP均為NP-難問題。VRP之所以引起學(xué)術(shù)界的極大重視，除了它具有廣泛的應(yīng)用背景外，是因?yàn)橄?/p>

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