車輛路徑問題的概述自己翻譯的

1、車輛路徑問題的概述 保羅托斯 丹尼爾維戈 引引 言言: : 過去幾十年里基于行動(dòng)研究和數(shù)學(xué)編程技術(shù), 優(yōu) 化軟件包已經(jīng)越來越多的被利用來有效管理供貨服務(wù)分 銷系統(tǒng)。有很多現(xiàn)實(shí)生活中的實(shí)例,無論是在北美和歐 洲,有廣泛的調(diào)查數(shù)據(jù)顯示在使用電腦程序分配過程中 會(huì)產(chǎn)生大量的規(guī)劃儲(chǔ)蓄，通常占整個(gè)全球運(yùn)輸成本的 5%到20%。很容易看到這些儲(chǔ)蓄對(duì)全球經(jīng)濟(jì)系統(tǒng)的影 響是十分重要的。事實(shí)上,運(yùn)輸過程中涉及到的所有階 段的生產(chǎn)和分銷系統(tǒng)，代表一個(gè)相關(guān)組件貨物的最終成 本的10%到20%。由于計(jì)算機(jī)技術(shù)的發(fā)展，再加之日 益一體化的信息系統(tǒng)生產(chǎn)和商業(yè)流程，我們可以從硬件 和軟件上具備使用運(yùn)籌學(xué)技術(shù)的條件。 在本書

2、中在本書中,我們只考慮分銷倉(cāng)庫(kù)和最終用戶我們只考慮分銷倉(cāng)庫(kù)和最終用戶( (客戶客戶) )之間之間 存在的問題存在的問題, , 。這些問題通常稱為車輛路徑問題。這些問題通常稱為車輛路徑問題( (vrpsvrps) ) 或車輛調(diào)度問題。這提出了解決車輛調(diào)度問題的模型或車輛調(diào)度問題。這提出了解決車輛調(diào)度問題的模型 和算法，在書中詳細(xì)介紹了可以有效地使用不僅對(duì)解和算法，在書中詳細(xì)介紹了可以有效地使用不僅對(duì)解 決方案的交付等方面的問題或集合貨物決方案的交付等方面的問題或集合貨物,但解決實(shí)際應(yīng)但解決實(shí)際應(yīng) 用中出現(xiàn)的不同交通運(yùn)輸系統(tǒng)。用中出現(xiàn)的不同交通運(yùn)輸系統(tǒng)。 另外一個(gè)同樣重要的成功原因是近些年建模技術(shù)

3、另外一個(gè)同樣重要的成功原因是近些年建模技術(shù) 和算法實(shí)現(xiàn)工具的發(fā)展，事實(shí)上和算法實(shí)現(xiàn)工具的發(fā)展，事實(shí)上, ,該模型考慮到帳戶所該模型考慮到帳戶所 有出現(xiàn)在實(shí)際應(yīng)用程序中的特征分布和在實(shí)際的計(jì)算時(shí)有出現(xiàn)在實(shí)際應(yīng)用程序中的特征分布和在實(shí)際的計(jì)算時(shí) 代中計(jì)算計(jì)算法所能找到的最好的解決方案。代中計(jì)算計(jì)算法所能找到的最好的解決方案。 這種類型的典型應(yīng)用,例如,固體垃圾收集、清掃街道,校車路由、 撥號(hào)叫車服務(wù)系統(tǒng)、運(yùn)輸殘疾人、路由的銷售人員和維修單位。 貨物的分配服務(wù) 是在給定的時(shí)間范圍內(nèi),一組客戶通過一組工具,位于一個(gè) 或多個(gè)倉(cāng)庫(kù),由一個(gè)組人員(司機(jī)) 通過使用一個(gè)適當(dāng)?shù)墓肪W(wǎng) 絡(luò)來執(zhí)行行動(dòng)。特別要指出一

4、個(gè)vrp的解決方案要求確定一 組路線,每個(gè)行動(dòng)通過一個(gè)單一的車輛,開始和結(jié)束都在自己的 倉(cāng)庫(kù),這樣所有的顧客需求都是可以實(shí)現(xiàn),所有的操作約束是符 合要求的,并且可以使得全球運(yùn)輸成本最小化。在本節(jié)中,我們 描述的典型特性路由和調(diào)度問題,考慮他們的主要組件(道路網(wǎng) 絡(luò),客戶、倉(cāng)庫(kù)、車輛和司機(jī)),和不同的操作約束,可以對(duì)行走 在建筑群里的路線,和可能的目標(biāo)來實(shí)現(xiàn)優(yōu)化過程。 typical characteristics of customers aretypical characteristics of customers are： vertex of the road graph in which

5、 the customer is located; amount of goods (demand), possibly of different types, which must be delivered or collected at the customer; periods of the day (time windows) during which the customer can be served (for instance, because of specific periods during which the customer is open or the locatio

6、n can be reached, due to traffic limitations); times required to deliver or collect the goods at the customer location (unloading or loading times, respectively), possibly dependent on the vehicle type; and subset of the available vehicles that can be used to serve the customer (for instance, becaus

7、e of possible access limitations or loading and unloading requirements). n有時(shí),它可能不會(huì)完全滿足每個(gè) 客戶的需求。在這些情況下,交 付或收集的數(shù)量會(huì)減少,或一個(gè) 子集的客戶可以被留下無人看 管。處理這些情況,根據(jù)不同的 獎(jiǎng)懲優(yōu)先級(jí)，可以指派給客戶 不同的解決方案。 執(zhí)行路線：執(zhí)行路線： n是指為客戶提供服務(wù)的 始發(fā)點(diǎn)和結(jié)束點(diǎn)在一個(gè) 或多個(gè)倉(cāng)庫(kù)，并且這些 倉(cāng)庫(kù)是位于在頂點(diǎn)的道 路圖。每個(gè)倉(cāng)庫(kù)的特點(diǎn) 是車輛的數(shù)量和類型是 相關(guān)聯(lián)的,并且可以處理 全球的貨物。 n在一些實(shí)際應(yīng)用程序, 在 倉(cāng)庫(kù)客戶是一個(gè)先驗(yàn)的 分區(qū), 車輛必

8、須在每個(gè)路 線的最后回到他們自己 的倉(cāng)庫(kù)里。在這些情況 下，在這些情況下,整個(gè) vrp可以分解成幾個(gè)獨(dú) 立的問題,每一個(gè)關(guān)聯(lián)到 一個(gè)不同的倉(cāng)庫(kù)。 貨物運(yùn)輸是由使用 的車輛組成，大小可以 是固定的或可以被界定 根據(jù)客戶的要求 typical characteristics of the vehicles are: n home depot home depot of the vehicle, and the possibility to end of the vehicle, and the possibility to end service at a depot other than the

9、service at a depot other than the nhome one;home one; n capacity capacity of the vehicle, expressed as the maximum of the vehicle, expressed as the maximum weight, or volume, or number ofweight, or volume, or number of npallets, the vehicle can load;pallets, the vehicle can load; n possible subdivis

10、ion of the vehicle into possible subdivision of the vehicle into compartments, compartments, each characterized by its capacityeach characterized by its capacity nand by the types of goods that can be carried;and by the types of goods that can be carried; n devices available for the loading and unlo

11、ading devices available for the loading and unloading operations;operations; n subset of arcs of the road graph which can be subset of arcs of the road graph which can be traversed by the vehicle; andtraversed by the vehicle; and n costs costs associated with utilization of the vehicle (per associat

12、ed with utilization of the vehicle (per distance unit, per time unit, perdistance unit, per time unit, per nroute, etc.).route, etc.). n司機(jī)操作車輛必須滿足聯(lián)盟合同和公司規(guī)定等幾個(gè)約束司機(jī)操作車輛必須滿足聯(lián)盟合同和公司規(guī)定等幾個(gè)約束(例例 如如,在白天的工作時(shí)間、數(shù)量和持續(xù)工間休息服務(wù)在白天的工作時(shí)間、數(shù)量和持續(xù)工間休息服務(wù),最大持續(xù)最大持續(xù) 開車時(shí)間開車時(shí)間,加班時(shí)間加班時(shí)間)。在下文中。在下文中,限制強(qiáng)加給司機(jī)嵌入這些限制強(qiáng)加給司機(jī)嵌入這些 聯(lián)系在一起的車

13、輛。聯(lián)系在一起的車輛。 n這個(gè)路線必須滿足幾個(gè)操作約束這個(gè)路線必須滿足幾個(gè)操作約束,這依賴于自然貨物的運(yùn)輸這依賴于自然貨物的運(yùn)輸, 高質(zhì)量的服務(wù)水平高質(zhì)量的服務(wù)水平,和具有其自身特點(diǎn)的客戶和車輛。一些和具有其自身特點(diǎn)的客戶和車輛。一些 典型的操作約束是以下幾點(diǎn)典型的操作約束是以下幾點(diǎn): n along each route, the current load of the associated vehicle cannot exceed the vehicle capacity; the ncustomers served in a route can require only the del

14、ivery or the collection of goods, or both npossibilities can exist; and customers can be served only within their time windows and nthe working periods of the drivers associated with the vehicles visiting them. 優(yōu)先約束: n優(yōu)先約束可以對(duì)客戶的順序做一個(gè)路線參觀。 n一種類型的優(yōu)先約束要求一個(gè)給定的客戶服務(wù)，在相同 的一個(gè)給定路線服務(wù)其他客戶子集中,客戶必須去過(或 以后要去)客戶屬于

15、的相關(guān)子集。例如,所謂的皮卡和交 貨問題,其中該航線都可以執(zhí)行收集和交付的貨物和貨 物從傳感器收集客戶必須被帶到相應(yīng)的交付客戶同樣的 車輛。 n另一個(gè)類型的優(yōu)先約束,如果不同類型的客戶服務(wù)同樣 的路線,以何種順序訪問客戶是固定的。這種情況出現(xiàn), 例如,對(duì)于所謂的vrp與backhauls，再次在其中,路線 可以執(zhí)行兩個(gè)集合和交付的貨物,但限制相關(guān)的加載和 卸載操作,難以重新加載的車輛沿路線運(yùn)輸,者意味著所 有貨物必須先進(jìn)行集合。評(píng)估的全球路線成本,和檢查 約束的操作強(qiáng)加于他們,需要知識(shí)的旅行成本和旅行時(shí) 間每對(duì)客戶和客戶之間的倉(cāng)庫(kù)的旅行時(shí)間和。 n為此,原來的道路圖(通常是非常稀少的)通常轉(zhuǎn)換

16、 為完全圖,完全圖的頂點(diǎn)是道路圖頂點(diǎn)所對(duì)應(yīng)于客 戶和倉(cāng)庫(kù)。對(duì)于每一對(duì)頂點(diǎn)i和j的完全圖,一個(gè)弧 (i,j)定義成本cij。旅行時(shí)間的年度財(cái)政,與完全圖 相關(guān)各弧(i,j),計(jì)算旅行時(shí)間的總和的弧屬于最短 路徑的i到j(luò)在路上圖。在下面,而不是原始的道路圖 ,我們考慮相關(guān)的完全圖,可以直接或無向,這取決于 相應(yīng)屬性的成本和旅行時(shí)間矩陣是不是分別對(duì)稱, 這些經(jīng)常形成對(duì)比,目標(biāo)可以被考慮車輛路徑問題 。 典型目標(biāo)是：典型目標(biāo)是： n minimization of the global transportation cost, dependent on the global distance ntra

17、veled (or on the global travel time) and on the fixed costs associated with the used nvehicles (and with the corresponding drivers); n minimization of the number of vehicles (or drivers) required to serve all the customers; n balancing of the routes, for travel time and vehicle load; n minimization

18、of the penalties associated with partial service of the customers; nor any weighted combination of these objectives. 在某些應(yīng)用程序中在某些應(yīng)用程序中,每個(gè)車輛可以運(yùn)行每個(gè)車輛可以運(yùn)行 不止一個(gè)路線不止一個(gè)路線,或者途徑路線時(shí)間可以或者途徑路線時(shí)間可以 持續(xù)超過持續(xù)超過1天。此外天。此外,必要的時(shí)候需要必要的時(shí)候需要 考慮隨機(jī)問題考慮隨機(jī)問題,也就是說也就是說,對(duì)于這個(gè)問題對(duì)于這個(gè)問題 只需要部分有關(guān)客戶或成本只需要部分有關(guān)客戶或成本(和旅行時(shí)和旅行時(shí) 間間)相關(guān)的弧道路網(wǎng)絡(luò)知識(shí)

19、的要求。相關(guān)的弧道路網(wǎng)絡(luò)知識(shí)的要求。 n超過40年以來已經(jīng)過去,ramser dantzig vrp11 在他們的論文中描述了一個(gè)真實(shí)的應(yīng)用程序(關(guān)于交付 汽油加油站),并提出和制定了的第一個(gè)數(shù)學(xué)規(guī)劃和算 法解決問題。幾年后,克拉克和賴特9提出了一個(gè)有 效啟發(fā)式,改進(jìn)了這個(gè)dantzig-ramser方法。以下兩 個(gè)具有開創(chuàng)性的論文,許多模型，精確算法和啟發(fā)式算 法建立了優(yōu)化和近似解的vrp的不同版本。本章描述 了幾種不同的，也是最重要和最有效的模型和算法是 在。 ndesrochers,lenstra,savelsbergh13給出了一個(gè) 分類方案。 laporte和nobert32提出了一

20、個(gè)廣泛的 調(diào)查,完全致力于用確切方法解決vrp,并在1980年代 末給他們一個(gè)完整而詳細(xì)，具有藝術(shù)氣息的分析狀態(tài) 。 n其他調(diào)查,覆蓋精確算法,但通常主要致力于啟發(fā)式方法,提出了 n通過christofides,mingozzi,托斯馬尼安蒂7,36,博丹et al 。4,christofides5, nlaporte30,費(fèi)舍爾19,托斯和比戈第四十一條、第四十二條 ,和黃金et al。26。 n提出了一個(gè)帶注釋的書目laporte31,和廣泛的參考書目 n提出了laporte和奧斯曼33。一本關(guān)于這個(gè)題目的書是編輯金 n和阿薩德25。模型和算法解決所謂的電弧路由問題,即 n問題產(chǎn)生的變體當(dāng)

21、客戶所在不是在頂點(diǎn)但 n沿弧線的道路網(wǎng)絡(luò),在最近的書描述編輯dror14。 n這一特定的情況時(shí)產(chǎn)生的vrp只有一個(gè)車輛可以在倉(cāng)庫(kù)和 n沒有額外的操作應(yīng)用的約束,即眾所周知的旅行推銷員 n問題,是廣泛的經(jīng)典書籍中描述編輯lawler et al。34。 問題定義和基本的符號(hào)問題定義和基本的符號(hào): : n在這一節(jié)中,我們給一個(gè)正式的定義,如圖理論模型,基本的問題 車輛的路由類。這些問題,它已收到最大的關(guān)注科學(xué)文獻(xiàn),詳細(xì) 討論了這本書的前兩部分。我們首先描述vrp生產(chǎn),這是最簡(jiǎn)單 、最具有研究意義的家庭成員,然后我們介紹了距離約束 vrp,vrp帶時(shí)間窗的,vrp與backhauls,vrp與選送。

22、對(duì)于這 些問題,提出了幾個(gè)較小的變異和檢查在文學(xué)和經(jīng)常不同的問題 給出了相同的名稱。雖然在許多例解決方案的方法,特別是啟發(fā) 式的公司,可能會(huì)適應(yīng)合并額外的特性,這種不確定性的問題定 義通常會(huì)導(dǎo)致更多的混亂。因此,對(duì)于每個(gè)問題我們首先描述基 本的版本,例如,一個(gè)在這本書是用相應(yīng)的縮略詞,然后我們將討 論不同的變體。在另外,我們讓一個(gè)明確的區(qū)分對(duì)稱和非對(duì)稱的 版本問題只是如果模型和解決方案的方法在文獻(xiàn)提出的利用這 種區(qū)別。 n也在這一節(jié)中,我們將介紹所有相關(guān) 的符號(hào)和術(shù)語在這本書。額外的標(biāo) 記和定義需要描述特定的變異和實(shí) 用的vrp問題給出相應(yīng)的章節(jié)。圖 1.1總結(jié)了這一節(jié)中描述的主要問題 ,說明

23、了它們的連接。在本圖中,一 個(gè)箭頭將從a到b的問題問題意味著b 是一個(gè)擴(kuò)展。 生產(chǎn)和距離約束生產(chǎn)和距離約束vrpvrp n在cvrp,所有的客戶對(duì)應(yīng)于的交付問題和 他的要求是確定性的,是要提前知道,不得 分裂。車輛被強(qiáng)加的條件是要數(shù)量相等且 在一個(gè)中央倉(cāng)庫(kù),只有容量受限制。目標(biāo) 是為所有的客戶實(shí)現(xiàn)最小化總成本(即,一 個(gè)加權(quán)函數(shù)路線的數(shù)量及其長(zhǎng)度或旅行時(shí) 間)。 圖 基本的問題和它們之間的聯(lián)系vrp ncvrp的可以被描述為下面的圖理論 問題。讓g =(v,a)是一個(gè)完整的圖形 ,設(shè)置v = 0,n是頂點(diǎn)組和一個(gè) 是電弧。 n頂點(diǎn)i= 1n,對(duì)應(yīng)于客戶,而頂點(diǎn)0 對(duì)應(yīng),倉(cāng)庫(kù)有時(shí)候是與頂點(diǎn)n +

24、 1對(duì)應(yīng) n一個(gè)非負(fù)成本,cij,伴隨著每個(gè)弧(i,j) a和代表了旅行 成本花去從頂點(diǎn)i到頂點(diǎn)j。通常i,不允許使用循環(huán)弧 ,(i,i),而是通過定義為 n如果g是一個(gè)有向圖,成本矩陣c是不對(duì)稱的,和相應(yīng)的問 題是cvrp n稱為非對(duì)稱的(acvrp)。 否則,我們這個(gè)問題 n就是所謂的對(duì)稱 ncvrp(scvrp) n電弧通常被設(shè)置為一組無向邊,e。 n給定一個(gè)邊緣ee,讓 表示其端點(diǎn)的頂點(diǎn)。 在下面我們 n表示邊緣設(shè)置的無向圖g的邊緣時(shí)表示通過 n他們的端點(diǎn)(i,j),i,j v,當(dāng)邊表示通過單個(gè)索引e。 n圖形圖形g g必須是完整的，給定一個(gè)前向頂點(diǎn)必須是完整的，給定一個(gè)前向頂點(diǎn)i i

25、，讓，讓+(i)+(i)表示表示i i，定，定 義為組頂點(diǎn)義為組頂點(diǎn)j,j,?。ɑ。╥ i，j j） a a，也就是說，頂點(diǎn)直接從，也就是說，頂點(diǎn)直接從i i訪問。訪問。 類似的，讓類似的，讓- -表示逆向頂點(diǎn)表示逆向頂點(diǎn)i,i,定義為組頂點(diǎn)（定義為組頂點(diǎn)（i,ji,j） a,a,頂點(diǎn)頂點(diǎn) 直接從直接從i i訪問。給定一個(gè)頂點(diǎn)組訪問。給定一個(gè)頂點(diǎn)組s s vv，讓，讓(s(s) ) 和和e(s)e(s)表示邊緣表示邊緣 e e e e，有一個(gè)或兩個(gè)相同的端點(diǎn)，有一個(gè)或兩個(gè)相同的端點(diǎn)s s。 n在一些實(shí)際情況下在一些實(shí)際情況下, ,成本矩陣滿足三角不等式成本矩陣滿足三角不等式, ,即即: : n

26、 cik+ckjcik+ckj cijcij ( (i,j,ki,j,k v) v) n n給定坐標(biāo)給定坐標(biāo): :v(i,jv(i,j),),每個(gè)每個(gè)( (i,ji,j) a, ) a, 定義為歐氏距離定義為歐氏距離, ,這兩個(gè)點(diǎn)這兩個(gè)點(diǎn) 之間的頂點(diǎn)對(duì)應(yīng)之間的頂點(diǎn)對(duì)應(yīng)i i和和j j。在這種情況下的成本矩陣對(duì)稱且滿足三角。在這種情況下的成本矩陣對(duì)稱且滿足三角 不等式，并由此產(chǎn)生的問題叫做歐幾里德的不等式，并由此產(chǎn)生的問題叫做歐幾里德的scvrpscvrp。 n每個(gè)顧客每個(gè)顧客i i（i=1i=1， ，n n），關(guān)聯(lián)到一個(gè)已知的非負(fù)需求），關(guān)聯(lián)到一個(gè)已知的非負(fù)需求didi， 倉(cāng)庫(kù)的虛擬需求倉(cāng)庫(kù)的

27、虛擬需求d0=0d0=0，給定一個(gè)頂點(diǎn)組，給定一個(gè)頂點(diǎn)組s s vv，令，令d(s)= i d(s)= i sdisdi來表示總需求的設(shè)置。來表示總需求的設(shè)置。 n相同的車輛相同的車輛k,k,相同的容量相同的容量c c，假設(shè)，假設(shè)di cdi c（i=1i=1， ，n n），令），令k k kminkmin，kminkmin的值可能的值可能通過求解與通過求解與cvrpcvrp相關(guān)的裝箱問題相關(guān)的裝箱問題 (bpp) (bpp) 來決定。來決定。 set set s s v 0, v 0, 表示表示r(sr(s) )需要的最小數(shù)量需要的最小數(shù)量 的車輛的車輛. . r(vr(v 0) = 0)

28、= kmin,r(skmin,r(s) )為為bpp bpp 的下界。的下界。 即：即： n d(s)/cd(s)/c 然而就這些相應(yīng)的原始成本而言，激烈的失真度量誘然而就這些相應(yīng)的原始成本而言，激烈的失真度量誘 導(dǎo)此操作會(huì)產(chǎn)生很壞的上下界。請(qǐng)注意，當(dāng)成本每個(gè)導(dǎo)此操作會(huì)產(chǎn)生很壞的上下界。請(qǐng)注意，當(dāng)成本每個(gè) 弧的圖是平等的對(duì)成本的最短路徑的終點(diǎn)，相應(yīng)成本弧的圖是平等的對(duì)成本的最短路徑的終點(diǎn)，相應(yīng)成本 矩陣滿足三角不等式。在某些情況下頂點(diǎn)的相關(guān)點(diǎn)給矩陣滿足三角不等式。在某些情況下頂點(diǎn)的相關(guān)點(diǎn)給 定了坐標(biāo)和成本定了坐標(biāo)和成本/ /年，為每個(gè)?。?，為每個(gè)弧（i i，j j）屬于）屬于a a，定義，定

29、義 為歐氏距離兩點(diǎn)之間的對(duì)應(yīng)頂點(diǎn)為歐氏距離兩點(diǎn)之間的對(duì)應(yīng)頂點(diǎn)i i和和j .j .在這種情況下在這種情況下 的成本矩陣對(duì)稱且滿足三角不等式，并由此產(chǎn)生的問的成本矩陣對(duì)稱且滿足三角不等式，并由此產(chǎn)生的問 題叫做歐幾里得題叫做歐幾里得scvrpscvrp。觀察到經(jīng)常進(jìn)行舍入到最近的。觀察到經(jīng)常進(jìn)行舍入到最近的 整數(shù)的實(shí)際價(jià)值，歐幾里得弧成本可能導(dǎo)致違反三角整數(shù)的實(shí)際價(jià)值，歐幾里得弧成本可能導(dǎo)致違反三角 不等式，如果成本圍捕，這就不會(huì)發(fā)生。不等式，如果成本圍捕，這就不會(huì)發(fā)生。 每個(gè)客戶每個(gè)客戶i（i= 1.n），是與一個(gè)已知的非負(fù)需求，），是與一個(gè)已知的非負(fù)需求，di 是被交付和倉(cāng)庫(kù)虛擬需求是被交付

30、和倉(cāng)庫(kù)虛擬需求d0= 0。給定一個(gè)頂點(diǎn)集。給定一個(gè)頂點(diǎn)集s包含包含 于于v，讓，讓 表示總需求的一套。表示總需求的一套。 一套的車輛一套的車輛k，每個(gè)容量，每個(gè)容量c，可在倉(cāng)庫(kù)。保證我們認(rèn)為可行，可在倉(cāng)庫(kù)。保證我們認(rèn)為可行 性，性，di c為每個(gè)為每個(gè)i=1,n。每輛車可能在最一條路線，。每輛車可能在最一條路線， 我們假設(shè)是不小于公里的地方，是最低公里所需車輛的數(shù)我們假設(shè)是不小于公里的地方，是最低公里所需車輛的數(shù) 量為所有客戶。對(duì)知識(shí)價(jià)值的可能確定通過求解裝箱問題量為所有客戶。對(duì)知識(shí)價(jià)值的可能確定通過求解裝箱問題 （應(yīng)用）與（應(yīng)用）與cvrp，要求日確定最低數(shù)量的垃圾箱，每個(gè)，要求日確定最低數(shù)

31、量的垃圾箱，每個(gè) 容量，需加載所有這個(gè)項(xiàng)目，每一個(gè)非負(fù)權(quán)重的容量，需加載所有這個(gè)項(xiàng)目，每一個(gè)非負(fù)權(quán)重的di, i=1,n。雖然是。雖然是np-hard的應(yīng)用強(qiáng)烈的情況下，數(shù)以百的應(yīng)用強(qiáng)烈的情況下，數(shù)以百 計(jì)的項(xiàng)目可以很有效地優(yōu)化求解。計(jì)的項(xiàng)目可以很有效地優(yōu)化求解。 給定一組，我們指的是給定一組，我們指的是r（s）的最低所需的車輛）的最低所需的車輛 數(shù)目服務(wù)所有的客戶在數(shù)目服務(wù)所有的客戶在s,i.e.，即最優(yōu)解的價(jià)值與，即最優(yōu)解的價(jià)值與 項(xiàng)目相關(guān)的培訓(xùn)集合。注意項(xiàng)目相關(guān)的培訓(xùn)集合。注意r（v 0 ）= k(min)。通常。通常r（5）取而代之的是平凡和下界。）取而代之的是平凡和下界。 d(s)/

32、c 該該cvrp構(gòu)成找到收集畝（每個(gè)相應(yīng)的簡(jiǎn)單電路構(gòu)成找到收集畝（每個(gè)相應(yīng)的簡(jiǎn)單電路 車輛路線）與最低成本，界定為總和的費(fèi)用的弧車輛路線）與最低成本，界定為總和的費(fèi)用的弧 所屬的電路等。所屬的電路等。 v （一）每個(gè)電路訪問的頂點(diǎn)；（一）每個(gè)電路訪問的頂點(diǎn)； v （二）客戶每一個(gè)頂點(diǎn)是訪問了整整一個(gè)電路；（二）客戶每一個(gè)頂點(diǎn)是訪問了整整一個(gè)電路； v （三）總和的要求的頂點(diǎn)訪問的電路不超過車輛能力。（三）總和的要求的頂點(diǎn)訪問的電路不超過車輛能力。 在文獻(xiàn)上被認(rèn)為幾種版本的在文獻(xiàn)上被認(rèn)為幾種版本的cvrp。首先當(dāng)數(shù)可用的車輛。首先當(dāng)數(shù)可用的車輛 是一個(gè)是一個(gè)kmjn，它可能會(huì)留下一些車輛使用，從

33、而在最電，它可能會(huì)留下一些車輛使用，從而在最電 路必須確定。在這種情況下，固定成本是經(jīng)常使用的車輛，路必須確定。在這種情況下，固定成本是經(jīng)常使用的車輛， 以及額外的目的需要數(shù)量減少電路（即使用的車輛）被添以及額外的目的需要數(shù)量減少電路（即使用的車輛）被添 加到這需要最小總成本。另一個(gè)經(jīng)常被認(rèn)為是變種出現(xiàn)時(shí)加到這需要最小總成本。另一個(gè)經(jīng)常被認(rèn)為是變種出現(xiàn)時(shí) 現(xiàn)有的車輛是不同的，即有不同的能力現(xiàn)有的車輛是不同的，即有不同的能力ck，k= 1，k 。 最后路線，只含有一個(gè)客戶可能不被允許。在下一節(jié)，我最后路線，只含有一個(gè)客戶可能不被允許。在下一節(jié)，我 們討論如何模型的基本們討論如何模型的基本crvp

34、能夠適應(yīng)這些額外的功能考能夠適應(yīng)這些額外的功能考 慮。慮。 該該crvp是已知的是已知的np-hard(在強(qiáng)意義）和推廣了著名的旅行商在強(qiáng)意義）和推廣了著名的旅行商 問題（問題（tsp），要求確定一個(gè)最小電路簡(jiǎn)單訪問所有頂點(diǎn)），要求確定一個(gè)最小電路簡(jiǎn)單訪問所有頂點(diǎn)g（哈（哈 密頓回路）和時(shí)所產(chǎn)生的密頓回路）和時(shí)所產(chǎn)生的c的（的（v）和）和k= 1。因此所有的松弛，。因此所有的松弛， 提出了問題的有效期為提出了問題的有效期為crvp。 第一個(gè)版本第一個(gè)版本crvp我們考慮的是所謂的距離限制的車輛路徑問題我們考慮的是所謂的距離限制的車輛路徑問題 （dvrp），在每個(gè)路徑的容量約束，取而代之的是一個(gè)

35、最大長(zhǎng)），在每個(gè)路徑的容量約束，取而代之的是一個(gè)最大長(zhǎng) 度（或時(shí)間）約束。特別是一個(gè)非負(fù)的長(zhǎng)度，側(cè)向度（或時(shí)間）約束。特別是一個(gè)非負(fù)的長(zhǎng)度，側(cè)向tij（或（或te） 是與每個(gè)是與每個(gè)arc（i，j）a一個(gè)（或邊界一個(gè)（或邊界ee），和總長(zhǎng)度的圓），和總長(zhǎng)度的圓 弧各路線不能超過最大路徑長(zhǎng)度弧各路線不能超過最大路徑長(zhǎng)度t。如果車輛的不同，然后最大。如果車輛的不同，然后最大 路徑長(zhǎng)度路徑長(zhǎng)度tk,k = 1，k。此外當(dāng)弧的長(zhǎng)度代表的旅行時(shí)間，。此外當(dāng)弧的長(zhǎng)度代表的旅行時(shí)間， 服務(wù)時(shí)間，服務(wù)時(shí)間，si，可能與每個(gè)客戶的我，表示時(shí)間段的車輛必須停，可能與每個(gè)客戶的我，表示時(shí)間段的車輛必須停 止在它的位

36、置。另外該服務(wù)可以被添加到旅行時(shí)間弧，即通過定止在它的位置。另外該服務(wù)可以被添加到旅行時(shí)間弧，即通過定 義，為每個(gè)義，為每個(gè)arc（i，j），），tij=ij + si/2+ sj/2在那里原來在那里原來 是旅行時(shí)的是旅行時(shí)的arc（i，j）。）。 一般來說，成本和長(zhǎng)度矩陣一致，即一般來說，成本和長(zhǎng)度矩陣一致，即i.e .cij= tij對(duì)所有（對(duì)所有（i，j） a（或（或ce=te對(duì)所有的對(duì)所有的ee）。因此，客觀的問題是盡量減）。因此，客觀的問題是盡量減 少總長(zhǎng)度本路線或他們的時(shí)間，當(dāng)服務(wù)時(shí)間包括在旅行時(shí)間的弧。少總長(zhǎng)度本路線或他們的時(shí)間，當(dāng)服務(wù)時(shí)間包括在旅行時(shí)間的弧。 在這種情況下的容量

37、和最大距離的限制目前被稱為距離限制的在這種情況下的容量和最大距離的限制目前被稱為距離限制的 crvp（dcrvp）。準(zhǔn)確和啟發(fā)式算法）。準(zhǔn)確和啟發(fā)式算法crvp和和dcrvp的章的章 節(jié)描述節(jié)描述 vrpvrp與時(shí)間窗與時(shí)間窗: : 有時(shí)間窗的車輛路徑問題（有時(shí)間窗的車輛路徑問題（vrptw）是延伸的）是延伸的crvp的能力施加的的能力施加的 限制和每個(gè)客戶我是與一個(gè)時(shí)間區(qū)間限制和每個(gè)客戶我是與一個(gè)時(shí)間區(qū)間ai,bi，稱為時(shí)間窗口。時(shí)間即，稱為時(shí)間窗口。時(shí)間即 時(shí)在該車輛離開倉(cāng)庫(kù)，旅行時(shí)間，風(fēng)云，為每個(gè)時(shí)在該車輛離開倉(cāng)庫(kù)，旅行時(shí)間，風(fēng)云，為每個(gè)arc（i，j）a（或（或 te對(duì)每個(gè)對(duì)每個(gè)ee）

38、和一個(gè)額外的服務(wù)時(shí)間為每一個(gè)客戶）和一個(gè)額外的服務(wù)時(shí)間為每一個(gè)客戶si。服務(wù)每個(gè)客。服務(wù)每個(gè)客 戶必須在相關(guān)的時(shí)間窗口，和車輛必須停在客戶定位為第一時(shí)間的瞬戶必須在相關(guān)的時(shí)間窗口，和車輛必須停在客戶定位為第一時(shí)間的瞬 間。此外在案件早期到達(dá)的位置間。此外在案件早期到達(dá)的位置i，車輛一般是可以等到時(shí)間瞬間，車輛一般是可以等到時(shí)間瞬間ai， i.e.,直到服務(wù)可以開始。直到服務(wù)可以開始。 通常成本和走時(shí)矩陣一致，和時(shí)間窗口定義假設(shè)所有車輛離開倉(cāng)庫(kù)時(shí)即通常成本和走時(shí)矩陣一致，和時(shí)間窗口定義假設(shè)所有車輛離開倉(cāng)庫(kù)時(shí)即 時(shí)時(shí)0。此外，觀察時(shí)間窗要求誘導(dǎo)隱方向各路線的就算了原來的矩陣都。此外，觀察時(shí)間窗要求

39、誘導(dǎo)隱方向各路線的就算了原來的矩陣都 是對(duì)稱的。因此是對(duì)稱的。因此vrptw通常是模仿作為一種非對(duì)稱問題。通常是模仿作為一種非對(duì)稱問題。 vrptw是為了找到一個(gè)集合是為了找到一個(gè)集合k由恰電路簡(jiǎn)單最低成本，比如：由恰電路簡(jiǎn)單最低成本，比如： （一）每個(gè)電路訪問的頂點(diǎn)；（一）每個(gè)電路訪問的頂點(diǎn)； （二）客戶每一個(gè)頂點(diǎn)是訪問了整整一個(gè)電路（二）客戶每一個(gè)頂點(diǎn)是訪問了整整一個(gè)電路； （三）頂點(diǎn)的電路訪問的需求的總和不超過車輛容量三）頂點(diǎn)的電路訪問的需求的總和不超過車輛容量,c; （四）為每一個(gè)客戶（四）為每一個(gè)客戶i,在服務(wù)開始的時(shí)間窗口在服務(wù)開始的時(shí)間窗口ai,bi內(nèi)，并且車輛停內(nèi)，并且車輛停

40、止時(shí)刻止時(shí)刻si。 vrp vrp中的回程載運(yùn)中的回程載運(yùn): : v 帶回送的帶回送的vrp （ vrpb ）是擴(kuò)展）是擴(kuò)展cvrp時(shí)，客戶的時(shí)，客戶的v 0被劃分為兩個(gè)被劃分為兩個(gè) 子集。第一子集，子集。第一子集，l ，包含，包含n linehaul customers，每一種都需要給定數(shù)量，每一種都需要給定數(shù)量 的產(chǎn)品以交付。第二子集，的產(chǎn)品以交付。第二子集，b，包含，包含m的回程的客戶，即一定量的入境產(chǎn)品必須的回程的客戶，即一定量的入境產(chǎn)品必須 獲得獲得?？蛻?。客戶被被編號(hào)，使得編號(hào)，使得l = 1, . . . , n 和和 fi = n+ ! , . . . , + m. v 在在v

41、rpb中中 ，優(yōu)先約束回程，優(yōu)先約束回程linehaul和客戶之間存在：和客戶之間存在： 每當(dāng)路由每當(dāng)路由為為兩種類型的客戶提供服務(wù)，所有的兩種類型的客戶提供服務(wù)，所有的linehaul的客戶必須的客戶必須在在回程客戶回程客戶 可能被服務(wù)之前被服務(wù)可能被服務(wù)之前被服務(wù)。一個(gè)。一個(gè)被被交付或視其類型而收集的非負(fù)需求交付或視其類型而收集的非負(fù)需求dt，與每一，與每一 個(gè)客戶個(gè)客戶聯(lián)系在一起聯(lián)系在一起，車廠車廠與一個(gè)虛構(gòu)需求與一個(gè)虛構(gòu)需求jq 0 聯(lián)系在一起聯(lián)系在一起。 當(dāng)成本矩陣是當(dāng)成本矩陣是 不對(duì)稱的，相關(guān)的問題被稱為非對(duì)稱帶回送的不對(duì)稱的，相關(guān)的問題被稱為非對(duì)稱帶回送的vrp （ avrpb

42、）。）。vrpb （和（和avrpb也一樣）找到恰好也一樣）找到恰好k的以最小的成本的以最小的成本集合的集合的簡(jiǎn)單簡(jiǎn)單回路回路，以及，如，以及，如 （一一）各電路訪問的車廠頂點(diǎn)）各電路訪問的車廠頂點(diǎn); （二）每個(gè)客戶的頂點(diǎn)是被訪問的一個(gè)（二）每個(gè)客戶的頂點(diǎn)是被訪問的一個(gè)回路回路; （ 三三）參觀了一個(gè)電路的）參觀了一個(gè)電路的linehaul客戶和回程客戶的總需求沒有被滿足，尤其客戶和回程客戶的總需求沒有被滿足，尤其 是車輛的通行能力是車輛的通行能力c; （四四）如果有的話，在每個(gè)電路所有的）如果有的話，在每個(gè)電路所有的linehaul的客戶回程客戶之前。的客戶回程客戶之前。 v 電路只包含回程

43、的客戶一般都是不允許的。此外，觀察其優(yōu)先約束引入了一電路只包含回程的客戶一般都是不允許的。此外，觀察其優(yōu)先約束引入了一 個(gè)隱含的方向的個(gè)隱含的方向的“混合混合”車輛路線，車輛路線， v 如，訪問如，訪問干線運(yùn)輸干線運(yùn)輸和回程頂點(diǎn)。和回程頂點(diǎn)。 讓讓kl和和kb表示服務(wù)所有表示服務(wù)所有干線和回程的干線和回程的最小車輛數(shù)量。這最小車輛數(shù)量。這 些值可以用些值可以用bpp與相應(yīng)的客戶的子集相關(guān)聯(lián)的實(shí)例解決。與相應(yīng)的客戶的子集相關(guān)聯(lián)的實(shí)例解決。 為了確?？尚行?，我們假定為了確?？尚行?，我們假定k是不小于需要為所有客戶是不小于需要為所有客戶服服 務(wù)的務(wù)的車輛的最小數(shù)目，即車輛的最小數(shù)目，即k maxa, kb 。 vrpb和和avrpb是是np-hard的強(qiáng)烈的責(zé)任感，因?yàn)樗麄兊膹?qiáng)烈的責(zé)任感，因?yàn)樗麄?概括基本的概括基本的scvrp和和ac vrp的版本，當(dāng)?shù)陌姹?，?dāng)b = 0時(shí)所產(chǎn)時(shí)所產(chǎn) 生。此外，所謂的生。此外，所謂的 ， tsp帶回送（帶回送（ tspb ）是是vrpb在在 c maxd(l), d(b v and k = 1時(shí)時(shí)的特殊情況。的特殊情況。vrpb在現(xiàn)代時(shí)間窗的案例已在現(xiàn)代時(shí)間窗的案例已 經(jīng)在文學(xué)中作為研究，經(jīng)在文學(xué)中作為研究， 文學(xué)文學(xué)被稱為被稱為vrp帶回送和時(shí)間窗（帶回送和時(shí)間窗（ vrpb