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

2.1問(wèn)題的描述及各組成部分特點(diǎn)2.2車輛路徑問(wèn)題的分類2.3車輛路徑問(wèn)題的研究現(xiàn)狀和發(fā)展趨勢(shì)1第二章物流配送車輛路徑問(wèn)題2.1問(wèn)題的描述及各組成部分2.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)題（VehicleRoutingProblem,VRP），或車輛調(diào)度問(wèn)題（VehicleSchedulingProblem,VSP）。一般描述是：對(duì)一系列給定的客戶點(diǎn)，確定配送車輛行駛路線，使其從配送中心出發(fā)，有序地對(duì)它們進(jìn)行服務(wù)，并在滿足一定的約束條件下（如車輛載重量、客戶需求量、服務(wù)時(shí)間限制等），使總運(yùn)輸成本達(dá)到最?。ㄈ缡褂密囕v數(shù)最少、車輛行駛總距離最短等）。一般把最小化車輛使用數(shù)作為第一優(yōu)化目標(biāo)，而最小化車輛行駛距離作為第二優(yōu)化目標(biāo)。

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

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

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

42.客戶（customer）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)客戶的順序要求。54.車輛（vehicle）57.行駛距離和行駛時(shí)間必須知道客戶點(diǎn)與客戶點(diǎn)之間，配送中心與客戶點(diǎn)之間的行駛距離和行駛時(shí)間。8.

目標(biāo)（objectives）

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

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

CVRP

VRPPDTW時(shí)間窗VRPTW回程運(yùn)輸VRPBTWVRPB10根據(jù)所包含的約束條件，問(wèn)題又可進(jìn)一步分類。以閉合式VRP為例2.2.1帶裝載能力的VRP（CapacitatedVRP，CVRP）問(wèn)題的特點(diǎn)是VRP中的最基本型式。所有客戶都屬于要送貨的或要取貨的，其需求量預(yù)先知道，且不能被分割。

車輛類型相同且都停放在一個(gè)配送中心。對(duì)車輛只有裝載能力限制。

問(wèn)題的目標(biāo)是最小化服務(wù)所有客戶的總費(fèi)用（即所需要的車輛數(shù)及其車輛行駛距離或行駛時(shí)間）。問(wèn)題的描述（可描述為如下的圖論問(wèn)題）112.2.1帶裝載能力的VRP（CapacitatedVR設(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)

xjxi12設(shè)G=(V,A)為一個(gè)完備圖，其中V={0,…,n在配送中心備有相同類型的車輛，每輛的裝載能力為C。每一條線路上的送貨任務(wù)只由一輛車承擔(dān)。

每個(gè)客戶i有一個(gè)已知的需要送往交付的非負(fù)需求量di，假設(shè)di<C。服務(wù)所有客戶至少所需要的車輛數(shù)

13在配送中心備有相同類型的車輛，每輛的裝載能力為C。每一條線路CVRP是求一個(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)。14CVRP是求一個(gè)具有最小總費(fèi)用的由K條簡(jiǎn)單回路組成的集合（每當(dāng)備有的車輛類型不是同一種時(shí)，即有不同的裝載能力Ck，k=1,…,K，則就為經(jīng)?？紤]的另一種變形。CVRP是NP-難的，并且是旅行商問(wèn)題（TSP）的一般化。在TSP中，要求確定一條經(jīng)過(guò)圖G中所有頂點(diǎn)的、費(fèi)用最小的回路（哈密頓回路），當(dāng)CVRP中的C≥∑di和K=1時(shí)就為此情形。15當(dāng)備有的車輛類型不是同一種時(shí)，即有不同的裝載能力Ck，k=2.2.2帶路程長(zhǎng)度的VRP（Distance-ConstrainedandCapacitatedVRP，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)著一個(gè)服務(wù)時(shí)間si，表示車輛必須在該客戶點(diǎn)停留的時(shí)間長(zhǎng)度。

162.2.2帶路程長(zhǎng)度的VRP（Distance-Const2.2.3帶時(shí)間窗的VRP

（VRPwithtimewindows，VRPTW）除了車輛裝載能力約束外，每個(gè)客戶i都有一個(gè)與之相聯(lián)系的要求提供服務(wù)的時(shí)間區(qū)間[ai,bi]。1.帶硬時(shí)間窗的VRP（VRPwithhardtimewindows,VRPHTW）。在不需要嚴(yán)格區(qū)分的場(chǎng)合，一般就稱為帶時(shí)間窗的VRP。特點(diǎn)

客戶的服務(wù)必須在相應(yīng)的時(shí)間窗內(nèi)開(kāi)始，車輛在客戶點(diǎn)的服務(wù)時(shí)間長(zhǎng)度為si。當(dāng)車輛提前到達(dá)客戶點(diǎn)時(shí)，必須等待到時(shí)刻ai才可開(kāi)始服務(wù)。不允許在bi之后到達(dá)并開(kāi)始服務(wù)。172.2.3帶時(shí)間窗的VRP

（VRPwithtime對(duì)于配送中心，設(shè)服務(wù)時(shí)間s0=0，時(shí)間窗[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)開(kāi)始，車輛的停留時(shí)間長(zhǎng)度為si。當(dāng)ai=0,bi=+∞時(shí)，VRPHTW就為CVRP。18對(duì)于配送中心，設(shè)服務(wù)時(shí)間s0=0，時(shí)間窗[a0,b02.帶軟時(shí)間窗的VRP（VRPwithsofttimewindows,VRPSTW）時(shí)間窗要求是軟的，即允許服務(wù)的開(kāi)始時(shí)間有所偏離時(shí)間窗（早于ai或晚于bi），但要根據(jù)所帶來(lái)的不方便程度支付一定的懲罰?？啥x懲罰函數(shù)來(lái)計(jì)算。若某個(gè)客戶的時(shí)間窗不能被違反（硬的），則有偏離時(shí)應(yīng)支付的懲罰設(shè)為無(wú)窮大?？梢?jiàn)VRPHTW實(shí)際上是VRPSTW的一種特殊情形。

由于允許以支付懲罰偏離時(shí)間窗，與VRPHTW相比，VRPSTW往往會(huì)在所需要的車輛數(shù)、或各線路總距離和總行駛時(shí)間方面獲得較大的節(jié)省。192.帶軟時(shí)間窗的VRP2.2.4帶回程運(yùn)輸?shù)腣RP（VRPwithbackhauls，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)的需求量之和分別不超過(guò)車輛裝載能力C；（4）所有去程客戶必須先于回程客戶得到服務(wù)。202.2.4帶回程運(yùn)輸?shù)腣RP擴(kuò)展帶回程運(yùn)輸和時(shí)間窗的VRP（VRPwithbackhaulsandtimewindows,VRPBTW）21擴(kuò)展212.2.5帶取送貨的VRP（VRPwithpickupanddelivery，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ù)且≤C；222.2.5帶取送貨的VRP（4）當(dāng)Oi不是配送中心時(shí)，它必須與客戶i在同一線路上且先于客戶i得到服務(wù)；（5）當(dāng)Di不是配送中心時(shí)，它必須與客戶i在同一線路上且后于客戶i得到服務(wù)。

擴(kuò)展帶取送貨和時(shí)間窗的VRP（VRPwithpickupanddeliveryandtimewindows,VRPPDTW）。23（4）當(dāng)Oi不是配送中心時(shí)，它必須與客戶i在同一線路上且先于2.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)的較有效的啟發(fā)式算法——Clarke-Wright節(jié)約算法。在這兩篇開(kāi)創(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)域。

242.3車輛路徑問(wèn)題的研究現(xiàn)狀和發(fā)展趨勢(shì)Dantzig和R1983年，Bodin等人在長(zhǎng)達(dá)140多頁(yè)的對(duì)VRP的研究進(jìn)展進(jìn)行綜述的文章中，就列舉了699篇相關(guān)的參考文獻(xiàn)。1995年出版的《HandbooksinOperationsResearchandManagementScience

》中，第八卷就是專門(mén)討論車輛路徑問(wèn)題的。2002年，PaoloToth和DanieleVigo在其出版的著作《TheVehicleRoutingProblem》中，對(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ā)式算法。251983年，Bodin等人在長(zhǎng)達(dá)140多頁(yè)的對(duì)VRP的研究進(jìn)2.3.1車輛路徑問(wèn)題的模型

CVRP的三下標(biāo)車輛流模型。

定義變量262.3.1車輛路徑問(wèn)題的模型CVRP的三下標(biāo)車輛流模型。模型27模型272.3.2VRP的計(jì)算復(fù)雜性和求解算法

對(duì)VRP求解算法的研究一直是重點(diǎn)和難點(diǎn)?，F(xiàn)已證明，幾乎所有類型的VRP均為NP-難問(wèn)題。VRP之所以引起學(xué)術(shù)界的極大重視，除了它具有廣泛的應(yīng)用背景外，是因?yàn)橄喈?dāng)難解，從而富有挑戰(zhàn)性。目前已提出了許多求解VRP的算法，究其實(shí)質(zhì)，可分為精確算法和啟發(fā)式算法兩大類。282.3.2VRP的計(jì)算復(fù)雜性和求解算法對(duì)VRP求解算法精確算法

指可求出其最優(yōu)解的算法，且一般要求問(wèn)題能用相應(yīng)的數(shù)學(xué)模型表示。

目前用于求解VRP的精確算法主要有

分支定界法（Branch-and-BoundAlgorithm）分支切面法（Branch-and-CutAlgorithm）

割平面法（CuttingPlaneMethod）

因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精確算法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)、遺傳算法(GA)等，研究運(yùn)用這些算法來(lái)構(gòu)造求解VRP的算法已成為主流和當(dāng)前的研究熱點(diǎn)，并已取得了許多令人鼓舞的成果。求出的解高出最優(yōu)解（或已知最好解）：基于經(jīng)典啟發(fā)式方法：2-10%；基于通用啟發(fā)式方法：<0.5%30啟發(fā)式算法30發(fā)展趨勢(shì)為了使現(xiàn)代啟發(fā)式算法能在商業(yè)軟件中得到應(yīng)用，開(kāi)發(fā)更快、更簡(jiǎn)單、更健壯的算法已成為一種趨勢(shì)，盡管這將在解的質(zhì)量方面帶來(lái)一些小損失。在算法測(cè)試與比較方面，研究人員目前已取得一個(gè)共識(shí)：必須使用公開(kāi)的標(biāo)準(zhǔn)測(cè)試算例（benchmarkinstances)對(duì)所提出的算法進(jìn)行測(cè)試。這樣，其測(cè)試結(jié)果才具有可比性和說(shuō)服力。31發(fā)展趨勢(shì)319、有時(shí)候讀書(shū)是一種巧妙地避開(kāi)思考的方法。12月-2212月-22Saturday,December3,202210、閱讀一切好書(shū)如同和過(guò)去最杰出的人談話。10:01:5710:01:5710:0112/3/202210:01:57AM11、越是沒(méi)有本領(lǐng)的就越加自命不凡。12月-2210:01:5710:01Dec-2203-Dec-2212、越是無(wú)能的人，越喜歡挑剔別人的錯(cuò)兒。10:01:5710:01:5710:01Saturday,December3,202213、知人者智，自知者明。勝人者有力，自勝者強(qiáng)。12月-2212月-2210:01:5710:01:57December3,202214、意志堅(jiān)強(qiáng)的人能把世界放在手中像泥塊一樣任意揉捏。03十二月202210:01:57上午10:01:5712月-2215、最具挑戰(zhàn)性的挑戰(zhàn)莫過(guò)于提升自我。。十二月2210:01上午12月-2210:01December3,202216、業(yè)余生活要有意義，不要越軌。2022/12/310:01:5710:01:5703December202217、一個(gè)人即使已登上頂峰，也仍要自強(qiáng)不息。10:01:57上午10:01上午10:01:5712月-22ThankYou...

Youmademyday!---敢為天下先，勇?tīng)?zhēng)第一9、有時(shí)候讀書(shū)是一種巧妙地避開(kāi)思考的方法。12月-2212月32第二章物流配送車輛路徑問(wèn)題

2.1問(wèn)題的描述及各組成部分特點(diǎn)2.2車輛路徑問(wèn)題的分類2.3車輛路徑問(wèn)題的研究現(xiàn)狀和發(fā)展趨勢(shì)33第二章物流配送車輛路徑問(wèn)題2.1問(wèn)題的描述及各組成部分2.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)題（VehicleRoutingProblem,VRP），或車輛調(diào)度問(wèn)題（VehicleSchedulingProblem,VSP）。一般描述是：對(duì)一系列給定的客戶點(diǎn)，確定配送車輛行駛路線，使其從配送中心出發(fā)，有序地對(duì)它們進(jìn)行服務(wù)，并在滿足一定的約束條件下（如車輛載重量、客戶需求量、服務(wù)時(shí)間限制等），使總運(yùn)輸成本達(dá)到最小（如使用車輛數(shù)最少、車輛行駛總距離最短等）。一般把最小化車輛使用數(shù)作為第一優(yōu)化目標(biāo)，而最小化車輛行駛距離作為第二優(yōu)化目標(biāo)。

342.1問(wèn)題的描述及各組成部分特點(diǎn)配送活動(dòng)中的配送車輛行駛線車輛路徑問(wèn)題的特點(diǎn)1.道路網(wǎng)（roadnetwork）弧表示路段，點(diǎn)表示道路交叉點(diǎn)、配送中心和客戶。弧的權(quán)cij表示其距離或行駛時(shí)間。35車輛路徑問(wèn)題的特點(diǎn)32.客戶（customer）用圖上的小圓點(diǎn)表示；需運(yùn)送或收取的貨物量（需求量）di(或di和pi)；要求提供服務(wù)的時(shí)間段，即時(shí)間窗（timewindow）在客戶點(diǎn)所花費(fèi)的服務(wù)時(shí)間si；

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

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

362.客戶（customer）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)客戶的順序要求。374.車輛（vehicle）57.行駛距離和行駛時(shí)間必須知道客戶點(diǎn)與客戶點(diǎn)之間，配送中心與客戶點(diǎn)之間的行駛距離和行駛時(shí)間。8.

目標(biāo)（objectives）

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

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

CVRP

VRPPDTW時(shí)間窗VRPTW回程運(yùn)輸VRPBTWVRPB42根據(jù)所包含的約束條件，問(wèn)題又可進(jìn)一步分類。以閉合式VRP為例2.2.1帶裝載能力的VRP（CapacitatedVRP，CVRP）問(wèn)題的特點(diǎn)是VRP中的最基本型式。所有客戶都屬于要送貨的或要取貨的，其需求量預(yù)先知道，且不能被分割。

車輛類型相同且都停放在一個(gè)配送中心。對(duì)車輛只有裝載能力限制。

問(wèn)題的目標(biāo)是最小化服務(wù)所有客戶的總費(fèi)用（即所需要的車輛數(shù)及其車輛行駛距離或行駛時(shí)間）。問(wèn)題的描述（可描述為如下的圖論問(wèn)題）432.2.1帶裝載能力的VRP（CapacitatedVR設(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)

xjxi44設(shè)G=(V,A)為一個(gè)完備圖，其中V={0,…,n在配送中心備有相同類型的車輛，每輛的裝載能力為C。每一條線路上的送貨任務(wù)只由一輛車承擔(dān)。

每個(gè)客戶i有一個(gè)已知的需要送往交付的非負(fù)需求量di，假設(shè)di<C。服務(wù)所有客戶至少所需要的車輛數(shù)

45在配送中心備有相同類型的車輛，每輛的裝載能力為C。每一條線路CVRP是求一個(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)。46CVRP是求一個(gè)具有最小總費(fèi)用的由K條簡(jiǎn)單回路組成的集合（每當(dāng)備有的車輛類型不是同一種時(shí)，即有不同的裝載能力Ck，k=1,…,K，則就為經(jīng)?？紤]的另一種變形。CVRP是NP-難的，并且是旅行商問(wèn)題（TSP）的一般化。在TSP中，要求確定一條經(jīng)過(guò)圖G中所有頂點(diǎn)的、費(fèi)用最小的回路（哈密頓回路），當(dāng)CVRP中的C≥∑di和K=1時(shí)就為此情形。47當(dāng)備有的車輛類型不是同一種時(shí)，即有不同的裝載能力Ck，k=2.2.2帶路程長(zhǎng)度的VRP（Distance-ConstrainedandCapacitatedVRP，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)著一個(gè)服務(wù)時(shí)間si，表示車輛必須在該客戶點(diǎn)停留的時(shí)間長(zhǎng)度。

482.2.2帶路程長(zhǎng)度的VRP（Distance-Const2.2.3帶時(shí)間窗的VRP

（VRPwithtimewindows，VRPTW）除了車輛裝載能力約束外，每個(gè)客戶i都有一個(gè)與之相聯(lián)系的要求提供服務(wù)的時(shí)間區(qū)間[ai,bi]。1.帶硬時(shí)間窗的VRP（VRPwithhardtimewindows,VRPHTW）。在不需要嚴(yán)格區(qū)分的場(chǎng)合，一般就稱為帶時(shí)間窗的VRP。特點(diǎn)

客戶的服務(wù)必須在相應(yīng)的時(shí)間窗內(nèi)開(kāi)始，車輛在客戶點(diǎn)的服務(wù)時(shí)間長(zhǎng)度為si。當(dāng)車輛提前到達(dá)客戶點(diǎn)時(shí)，必須等待到時(shí)刻ai才可開(kāi)始服務(wù)。不允許在bi之后到達(dá)并開(kāi)始服務(wù)。492.2.3帶時(shí)間窗的VRP

（VRPwithtime對(duì)于配送中心，設(shè)服務(wù)時(shí)間s0=0，時(shí)間窗[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)開(kāi)始，車輛的停留時(shí)間長(zhǎng)度為si。當(dāng)ai=0,bi=+∞時(shí)，VRPHTW就為CVRP。50對(duì)于配送中心，設(shè)服務(wù)時(shí)間s0=0，時(shí)間窗[a0,b02.帶軟時(shí)間窗的VRP（VRPwithsofttimewindows,VRPSTW）時(shí)間窗要求是軟的，即允許服務(wù)的開(kāi)始時(shí)間有所偏離時(shí)間窗（早于ai或晚于bi），但要根據(jù)所帶來(lái)的不方便程度支付一定的懲罰?？啥x懲罰函數(shù)來(lái)計(jì)算。若某個(gè)客戶的時(shí)間窗不能被違反（硬的），則有偏離時(shí)應(yīng)支付的懲罰設(shè)為無(wú)窮大?？梢?jiàn)VRPHTW實(shí)際上是VRPSTW的一種特殊情形。

由于允許以支付懲罰偏離時(shí)間窗，與VRPHTW相比，VRPSTW往往會(huì)在所需要的車輛數(shù)、或各線路總距離和總行駛時(shí)間方面獲得較大的節(jié)省。512.帶軟時(shí)間窗的VRP2.2.4帶回程運(yùn)輸?shù)腣RP（VRPwithbackhauls，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)的需求量之和分別不超過(guò)車輛裝載能力C；（4）所有去程客戶必須先于回程客戶得到服務(wù)。522.2.4帶回程運(yùn)輸?shù)腣RP擴(kuò)展帶回程運(yùn)輸和時(shí)間窗的VRP（VRPwithbackhaulsandtimewindows,VRPBTW）53擴(kuò)展212.2.5帶取送貨的VRP（VRPwithpickupanddelivery，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ù)且≤C；542.2.5帶取送貨的VRP（4）當(dāng)Oi不是配送中心時(shí)，它必須與客戶i在同一線路上且先于客戶i得到服務(wù)；（5）當(dāng)Di不是配送中心時(shí)，它必須與客戶i在同一線路上且后于客戶i得到服務(wù)。

擴(kuò)展帶取送貨和時(shí)間窗的VRP（VRPwithpickupanddeliveryandtimewindows,VRPPDTW）。55（4）當(dāng)Oi不是配送中心時(shí)，它必須與客戶i在同一線路上且先于2.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)的較有效的啟發(fā)式算法——Clarke-Wright節(jié)約算法。在這兩篇開(kāi)創(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)域。

562.3車輛路徑問(wèn)題的研究現(xiàn)狀和發(fā)展趨勢(shì)Dantzig和R1983年，Bodin等人在長(zhǎng)達(dá)140多頁(yè)的對(duì)VRP的研究進(jìn)展進(jìn)行綜述的文章中，就列舉了699篇相關(guān)的參考文獻(xiàn)。1995年出版的《HandbooksinOperationsResearchandManagementScience

》中，第八卷就是專門(mén)討論車輛路徑問(wèn)題的。2002年，PaoloToth和DanieleVigo在其出版的著作《TheVehicleRoutingProblem》中，對(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ā)式算法。571983年，Bodin等人在長(zhǎng)達(dá)140多頁(yè)的對(duì)VRP的研究進(jìn)2.3.1車輛路徑問(wèn)題的模型

CVRP的三下標(biāo)車輛流模型。

定義變量582.3.1車輛路徑問(wèn)題的模型CVRP的三下標(biāo)車輛流模型。模型59模型272.3.2VRP的計(jì)算復(fù)雜性和求解算法

對(duì)VRP求解算法的研究一直是重點(diǎn)和難點(diǎn)?，F(xiàn)已證明