車輛路徑問題優(yōu)化算法

1、車輛路徑問題優(yōu)化算法美國物流管理學(xué)會(huì)（Council of Logistics Management , CLM）對(duì)物流所作的定 義為： “為符合顧客的需要，對(duì)原料、制造過程中的存貨與制成品以及相關(guān)信息， 從其起運(yùn)點(diǎn)至最終消費(fèi)點(diǎn)之間，做出的追求效率與成本效果的計(jì)劃、執(zhí)行與控制 過程。”而有關(guān)資料顯示，物流配送過程 （包含倉儲(chǔ)、分揀、運(yùn)輸?shù)?）的成本構(gòu)成中，運(yùn)輸 成本占到 52% 之多。因此，如何在滿足客戶適當(dāng)滿意度的前提下，將配送的運(yùn) 輸成本合理地降低，成為一個(gè)緊迫而重要的研究課題，車輛路徑問題正是基于這 一需求而產(chǎn)生的。2.1 車輛路徑問題的定義 車輛路徑問題可以描述為：給定一組有容量限制的

2、車輛的集合、一個(gè)物流中心（或 供貨地）、若干有供貨需求的客戶，組織適當(dāng)?shù)男熊嚶肪€，使車輛有序地通過所 有的客戶，在滿足一定的約束條件（如需求量、服務(wù)時(shí)間限制、車輛容量限制、 行駛里程限制等）下，達(dá)到一定的目標(biāo)（如路程最短、費(fèi)用極小、時(shí)間盡量少、 使用車輛數(shù)盡量少等）。 4 因此研究車輛的路徑問題，就是要研究如何安排運(yùn)輸車輛的行駛路線， 使運(yùn)輸車 輛依照最短的行駛路徑或最短的時(shí)間費(fèi)用， 依次服務(wù)于每個(gè)客戶后返回起點(diǎn)，總 的運(yùn)輸成本實(shí)現(xiàn)最小。車輛路徑問題已被證明是 NP-Hard 問題，因此求解比較困難。然而，由于其在 現(xiàn)實(shí)生活中應(yīng)用非常廣泛，使得它無論在理論上還是在實(shí)踐上都有極大的研究價(jià) 值。P

3、enousal Machado 等人5 指出車輛路徑問題 （vehicle routing problem ，簡稱 VRP）是一個(gè)復(fù)雜的組合優(yōu)化問題，是古老的旅行商問題和背包問題的綜合。實(shí) 際上，車輛路徑問題通?？杀环纸饣蜣D(zhuǎn)化成一個(gè)或幾個(gè)已經(jīng)研究過的基本問題， 再采用相應(yīng)比較成熟的基本理論和方法，以得到最優(yōu)解或滿意解。這些與車輛路徑問題相關(guān)的常用基本問題有； 旅行商問題、運(yùn)輸問題、背包問題、 最短路問題、最小費(fèi)用最大流問題、中國郵路問題、指派問題等。旅行商問題可被描述為：一個(gè)推銷員欲到 n 個(gè)城市推銷商品，每 2 個(gè)城市之間的 距離是已知的。如何選擇一條路徑使推銷員依次又不重復(fù)地走遍每個(gè)城市后

4、， 回 到起點(diǎn)且所走的路徑最短。運(yùn)輸問題關(guān)心的是（確實(shí)的或是比喻的）以最低的總配送成本把供應(yīng)中心（稱為 出發(fā)地，sources）的任何產(chǎn)品運(yùn)送到每一個(gè)接受中心（稱為目的地， destinations ）。運(yùn)輸問題需要的數(shù)據(jù)僅僅是供應(yīng)量、需求量和單位成本。 背包問題是指有一只固定容量的背包和若干體積、 重量不等的物品，背包的容量 不允許裝下這所有的物品，那么如何選擇適當(dāng)?shù)奈锲费b入背包，使得背包的裝載 量（所裝物品的重量之和）最大。最短路徑問題解決的是在一個(gè)網(wǎng)絡(luò)中， 如何尋找兩點(diǎn)之間的最短路徑。這兩點(diǎn)之 間通常沒有直接的通路可達(dá)，但可經(jīng)由若干中間結(jié)點(diǎn)相通。最小費(fèi)用流問題主要解決如何以最小成本在一個(gè)

5、配送網(wǎng)絡(luò)中運(yùn)輸貨物。 最小費(fèi)用 流問題又稱為網(wǎng)絡(luò)配送問題。最大流問題和最小費(fèi)用流問題一樣，也與網(wǎng)絡(luò)中的流有關(guān)。但是它們的目標(biāo)不同， 最大流問題不是使得流的成本最小化， 而是尋找一個(gè)流的方案，使得通過網(wǎng)絡(luò)的 中國郵路問題是由我國管梅谷同志在 1962 年首先提出的，它可描述為：一個(gè)郵 遞員負(fù)責(zé)某一個(gè)地區(qū)的信件投遞。 每天要從郵局出發(fā)， 走遍該地區(qū)所有的街道再 返回郵局，問應(yīng)該怎樣安排送信路線可以使所走的路程最短。指派問題解決將 n 件工作安排給 m 個(gè)人完成的問題。已知不同人完成不同工作 的效率(或成本)不同，指派問題要求以最高的效率(或最小的人工成本)完成 工作的安排。2.2 車輛路徑問題的分

6、類 車輛路徑問題當(dāng)不考慮時(shí)間要求， 僅根據(jù)空間位置安排路線時(shí)稱為車輛路線安排 問題(Vehicle Routing Problem 簡記VRP)；當(dāng)考慮時(shí)間要求安排路線時(shí)稱為車輛 調(diào)度問題(Vehicle Scheduling Problem 簡記VSP);當(dāng)同時(shí)考慮空間位置和時(shí)間要 求時(shí)稱為路線和調(diào)度混合問題 6 。車輛調(diào)度冋題即有時(shí)間要求的車輛路徑冋題(VSP)又被稱為帶時(shí)間窗的車輛路 徑問題(Vehicle Routing Problem with Time Windows ,簡記為 VRPTW)。VRPTW 是在VRP的基礎(chǔ)上增加了客戶要求訪問的時(shí)間窗口，是一般車輛路徑問題的擴(kuò) 展。其

7、簡單的描述如下： 用于服務(wù)的若干車輛從站點(diǎn)出發(fā)， 為處在不同地理位置、 具有不同貨物需求和不同服務(wù)時(shí)間窗要求的所有顧客提供服務(wù)，然后返回站點(diǎn)， 其中為每個(gè)顧客僅提供一次服務(wù)。 其目標(biāo)是在時(shí)間窗內(nèi)為顧客提供服務(wù)時(shí)， 使車 輛的行駛時(shí)間和等待時(shí)間之和最短。根據(jù)時(shí)間約束的嚴(yán)格與否， 帶時(shí)間窗的車輛路徑問題被分為兩類： 軟時(shí)間窗車輛 路徑問題和硬時(shí)間窗車輛路徑問題。 軟時(shí)間窗車輛路徑問題要求配送車輛盡可能 在時(shí)間窗內(nèi)到達(dá)訪問，否則將給予一定的懲罰。該懲罰包括兩部分：(1)車輛在要求的最早到達(dá)時(shí)間之前到達(dá)，必須在任務(wù)點(diǎn)處等待而損失的成本；(2)車輛在要求的最遲到達(dá)時(shí)間之后到達(dá)， 必須付給客戶預(yù)先約定的罰

8、金。 而硬時(shí)間窗車輛 路徑問題則要求必須在時(shí)間窗內(nèi)到達(dá)訪問，否則服務(wù)被拒絕。Koskosidis 等人( 1992) 7 指出，軟時(shí)間窗模式比硬時(shí)間窗更具優(yōu)勢是因?yàn)椋?第一、軟時(shí)窗模式較傳統(tǒng)硬時(shí)窗模式更為一般化， 且軟時(shí)窗的求解演算法較具彈 性(因限制式較少)。而且若要提高準(zhǔn)點(diǎn)服務(wù)頻率，只需適當(dāng)?shù)奶岣邞土P成本即 可；第二、在現(xiàn)實(shí)世界中，時(shí)窗限制大多屬于軟時(shí)窗限制。配送服務(wù)商沒有在約 定的時(shí)間內(nèi)送達(dá)顧客端， 并非一定不可服務(wù)， 而是可以服務(wù)但必須付出雙方約定 的懲罰成本。 有較高準(zhǔn)點(diǎn)送達(dá)要求的顧客的懲罰成本大， 不準(zhǔn)時(shí)但是在可以忍受 的時(shí)間內(nèi)送達(dá)的顧客的懲罰成本相對(duì)小些； 第三、軟時(shí)窗模式可以有

9、效的反應(yīng)配 送商在車隊(duì)營運(yùn)成本、 規(guī)模和服務(wù)水準(zhǔn)兩者之間的關(guān)系； 第四、軟時(shí)窗模式可以 發(fā)現(xiàn)硬時(shí)窗模式無法找到的可行解。 特別是在小規(guī)模車隊(duì)服務(wù)多數(shù)顧客以及嚴(yán)苛 的時(shí)間限制條件狀況下。 在上述的情形得到軟時(shí)窗限制下的可行解后， 可再調(diào)整 時(shí)間窗讓違反時(shí)間窗的情況得到改善。車輛路徑問題還有確定性 (Deterministic) 模式和隨機(jī)性 (Stochastic) 模式之分8 。 確定性模式假設(shè)：其一、客戶的數(shù)目在配送開始前是已知且固定的；其二、客戶 的需求量在配送開始前是已知且固定的； 其三、兩點(diǎn)之間的旅行時(shí)間僅取決于這 兩點(diǎn)之間的距離。 而隨機(jī)性模式不要求以上一個(gè)或多個(gè)假設(shè)。 隨機(jī)性模式又

10、稱為 隨機(jī)需求車輛路徑問題。如果考慮裝卸工人的調(diào)配問題， 則車輛路徑問題就稱為帶裝卸工調(diào)配的車輛路徑 問題。帶裝卸工調(diào)配的車輛路徑問題描述如下 9:設(shè)配送中心有n輛貨車都要 向b個(gè)客戶裝卸貨物。配送中心可以安排 位裝卸工跟著車輛，也可以安排位裝 卸工固定在客戶 處。已知在客戶 處需要的裝卸工人數(shù)是 ，配送中心應(yīng)該考慮 如何調(diào)配裝卸工，使總的裝卸工人數(shù)最少。除了以上分類， 車輛路徑問題還可以按任務(wù)特征分為裝貨問題、 卸貨問題及裝卸 混合問題； 按任務(wù)性質(zhì)分為對(duì)弧服務(wù)問題 （如中國郵遞員問題） 和對(duì)點(diǎn)服務(wù)問題 （如旅行商問題）以及混合服務(wù)問題（如校車路線安排問題）；按車輛載貨狀況 分為滿載問題和非

11、滿載問題； 按車場數(shù)目分為單車場問題和多車場問題； 按車輛 類型數(shù)分為單車型問題和多車型問題； 按車輛對(duì)車場的所屬關(guān)系分為車輛開放問 題（車輛可不返回車場）和車輛封閉問題（車輛必須返回車場）；按優(yōu)化目標(biāo)可 分為單目標(biāo)問題和多目標(biāo)問題，等等。針對(duì)上述不同的分類方法，車輛路徑問題的模型構(gòu)造及求解算法有很大差別。2.3 車輛路徑問題的構(gòu)成要素 物流配送車輛路徑問題的構(gòu)成因素主要包括貨物、車輛、配送中心、客戶、運(yùn)輸 網(wǎng)絡(luò)、約束條件和目標(biāo)函數(shù)等要素 10 。2.3.1 貨物 貨物是配送的對(duì)象?？蓪⒚總€(gè)客戶需求（或供應(yīng)）的貨物看成一批貨物。每批貨 物包括品名、包裝、重量、體積、要求送到（或取走）的時(shí)間和地

12、點(diǎn)、能否分批 配送等屬性。貨物的品名和包裝， 是選用配送車輛的類型以及決定該批貨物能否 與其他貨物裝在同一車輛內(nèi)的依據(jù)。 例如，一些貨物因性質(zhì)特殊需要使用專用車 輛裝運(yùn)；而一些貨物雖然性質(zhì)特殊， 但由于包裝條件很好， 故也能與其它貨物裝 在同一車輛內(nèi)。 另外， 貨物的重量和體積也是進(jìn)行車輛裝載決策的重要依據(jù)。 當(dāng) 某個(gè)客戶的需求量 （供應(yīng)量） 的貨物的重量或體積超過車輛的最大裝載量或體積 時(shí)，則對(duì)該客戶需要采用多臺(tái)車輛進(jìn)行配送。2.3.2 車輛 車輛是貨物的運(yùn)載工具，其主要包括 : 車輛的類型、裝載量、一次配送的最大行 駛距離、配送前以及完成任務(wù)后車輛的停放位置等。 其一、車輛的類型有通用車輛

13、和專用車輛之分， 通用車輛適于運(yùn)載大多數(shù)普通貨 物，專用車輛適于載運(yùn)一些性質(zhì)特殊的貨物。 其二、車輛的裝載量是指車輛的最大裝載重量和最大裝載容積， 是進(jìn)行車輛裝載 決策的依據(jù)。在某個(gè)配送系統(tǒng)中，車輛的裝載量可以相同也可以不同。 其三、對(duì)每臺(tái)車輛一次配送的行駛距離的要求可以分為以下幾種情況 : 第一、無 距離限制 ; 第二、有距離限制 ; 第三、有距離限制，但可以不遵守。 其四、車輛在配送前可以是停放在某個(gè)停車場、 配送中心或者是客戶所在地。 完 成任務(wù)后，其停放位置一般可以分為以下幾種情形 : 一是必須返回出發(fā)點(diǎn) ; 二是 必須某個(gè)停車場或配送中心 ; 三是可返回任意停車場 ; 四是可停放在任

14、何地點(diǎn)。2.3.3 配送中心 配送中心是從事貨物配備 （集貨、加工、揀選、配貨 ） 和組織對(duì)客戶的送貨，以提 高水平實(shí)現(xiàn)銷售或供應(yīng)的現(xiàn)代流通設(shè)施。 在某個(gè)配送系統(tǒng)中， 配送中心的個(gè)數(shù)可 以是一個(gè)也可以是多個(gè)， 這涉及到配送網(wǎng)絡(luò)問題， 如在某些配送網(wǎng)點(diǎn)多而且配送 范圍廣的情形下， 往往采用多級(jí)配送中心進(jìn)行配送， 通過一級(jí)配送中心配送到下 一級(jí)配送中心再配送， 在多個(gè)二級(jí)配送中心下， 究竟由哪個(gè)配送中心配送， 這涉 及到配送的優(yōu)化問題。其配送示意圖見圖 2-1:圖 2-1 分級(jí)配送示意圖2.3.4 客戶 也稱為用戶，包括各盆景展覽館、陳列中心、公司、家庭用戶等。單個(gè)客戶一次 所需的盆景數(shù)量可能大于

15、盆景配送車某車輛的最大裝載量， 也可能小于該車輛的 最大裝載量。 而該系統(tǒng)全部客戶的貨物需求 （或供應(yīng)）總量可能超過全部車輛的 總裝載量。在以上情形下，當(dāng)貨物一次性需求（或供應(yīng)）總量超過運(yùn)輸能力時(shí)， 需要多次（多輛）分批配送；當(dāng)貨物一次性需求（或供應(yīng)）量小于某車輛的最大 裝載量時(shí)，在可能的情況下，應(yīng)進(jìn)行貨物配載?？蛻舻男枨螅ɑ蚬?yīng)）盆景的時(shí)間，是指要求盆景送達(dá)（或取走）的時(shí)間，對(duì)配 送時(shí)間的要求可分為以下幾種情況 : 第一、無時(shí)間限制；第二、要求在指定的時(shí) 間區(qū)間（也稱為時(shí)間窗）內(nèi)完成運(yùn)輸任務(wù)；第三、有時(shí)間限制，但可以不遵守， 只是不遵守時(shí)要給予一定的懲罰。2.3.5 運(yùn)輸網(wǎng)絡(luò) 運(yùn)輸網(wǎng)絡(luò)是由頂

16、點(diǎn)（指配送中心、客戶、停車場等）、無向邊和有向弧組成 的，邊、弧的屬性包括方向、權(quán)值和交通流量限制等。運(yùn)輸網(wǎng)絡(luò)中邊或弧的權(quán)值 可以表示距離、 時(shí)間或費(fèi)用。邊或弧的權(quán)值變化可分為以下幾種情況 : 一是固定， 即不隨時(shí)間和車輛的不同而變化；二是隨時(shí)間而變化；三是隨車輛不同而變化； 四是既隨時(shí)間不同而變化，又隨車輛不同而變化。對(duì)運(yùn)輸網(wǎng)絡(luò)權(quán)值間的關(guān)系可以要求其滿足三角不等式，即兩邊之和大于第三邊。 也可以不加限制。運(yùn)輸網(wǎng)絡(luò)見示意圖 2-2.圖 2-2 運(yùn)輸網(wǎng)絡(luò)示意圖 對(duì)運(yùn)輸網(wǎng)絡(luò)中頂點(diǎn)、邊或弧的交通流量要求分為以下幾種 : 其一、交通流量隨時(shí) 間不同而變化 ; 其二、邊、弧限制，即每條邊、 弧上同時(shí)行駛

17、的車輛數(shù)有限制 ; 其 三、頂點(diǎn)限制，即每個(gè)頂點(diǎn)上同時(shí)裝、卸的車輛數(shù)有限；其四、邊、弧、頂點(diǎn)都 有限制。2.3.6 約束條件 通常說來， 物流配送車輛路徑問題應(yīng)滿足的約束條件主要包括： 第一，滿足所有 客戶對(duì)貨物品種、規(guī)格、數(shù)量的要求；第二，滿足客戶對(duì)貨物發(fā)到的時(shí)間范圍的 要求；第三，在允許通行時(shí)間進(jìn)行配送（如有時(shí)規(guī)定白天不能通行貨車等）；第 四，車輛在配送過程中的實(shí)際載貨量不得超過車輛的最大允許裝載量； 第五，在 配送中心現(xiàn)有的運(yùn)力范圍內(nèi)。2.3.7 目標(biāo)函數(shù)對(duì)物流配送車輛路徑問題， 可以只選用一個(gè)目標(biāo)， 也可以是多個(gè)目標(biāo)。 經(jīng)常 選用的目標(biāo)函數(shù)主要有 : 第一，配送總里程最短。 配送里程與

18、配送車輛的耗油量、 磨損程度以及司機(jī)疲勞程度等直接相關(guān)， 它直接決定運(yùn)輸?shù)某杀荆?對(duì)配送業(yè)務(wù)的 經(jīng)濟(jì)效益有很大影響。 由于配送里程計(jì)算簡便， 它是確定配送路線時(shí)用得最多的 指標(biāo)。第二， 配送車輛的噸位公里數(shù)最少。 該目標(biāo)將配送距離與車輛的載重量結(jié) 合起來考慮， 即以所有配送車輛的噸位數(shù) （最大載重噸） 與其行駛距離的乘積的 總和最少為目標(biāo)。 第三，綜合費(fèi)用最低。 降低綜合費(fèi)用是實(shí)現(xiàn)配送業(yè)務(wù)經(jīng)濟(jì)效益 的基本要求。在物流配送中，與取送有關(guān)的費(fèi)用包括 : 車輛維護(hù)和行駛費(fèi)用、路 橋費(fèi)用、車隊(duì)管理費(fèi)用、貨物裝卸費(fèi)用、有關(guān)人員工資費(fèi)用等。第四，準(zhǔn)時(shí)性最 高。由于客戶對(duì)交貨時(shí)間有較嚴(yán)格的要求， 為提高配送

19、服務(wù)質(zhì)量， 有時(shí)需要將準(zhǔn) 時(shí)性最高作為確定配送路線目標(biāo)。 第五，運(yùn)力利用最合理。 該目標(biāo)要求使用的較 少的車輛完成配送任務(wù)，并使車輛的滿載率最高，以充分利用車輛的裝卸能力。 第六，勞動(dòng)消耗最低。即以司機(jī)人數(shù)最少、司機(jī)工資時(shí)間最短為目標(biāo)。2.4 車輛路徑問題的求解方法 車輛路徑問題通常被構(gòu)造成整數(shù)規(guī)劃模型、圖論或其它模型，這些模型之間 存在著某種聯(lián)系。 但從建立模型時(shí)的出發(fā)點(diǎn)考慮， 大多數(shù)模型都可看成是下面三 種模型的變形與組合： 第一，以車流為基礎(chǔ)的模型； 第二，以物流為基礎(chǔ)的模型； 第三，集覆蓋模型。求解方法上，常用的基本理論和方法有：分枝定界法、割平面法、線性規(guī)劃法、 動(dòng)態(tài)規(guī)劃法、匹配理論

20、、對(duì)偶理論、組臺(tái)理論、線搜索技術(shù)、列生成技術(shù)、拉格 朗日松弛技術(shù)、狀態(tài)空間松弛技術(shù)、 Benders 分解技術(shù)、扶梯度 （sub gradient） 優(yōu)化技術(shù)、概率分析、統(tǒng)計(jì)分析、最差情況分析、經(jīng)驗(yàn)分折等常用算法基本上可分為優(yōu)化算法和啟發(fā)式算法兩大類。 優(yōu)化算法求解時(shí)間長， 算 法效率低且不適合求解規(guī)模較大的問題， 因此在實(shí)際應(yīng)用中受到限制； 啟發(fā)式算 法效率較高且能逼近最優(yōu)解， 為此專家們主要把精力花在構(gòu)造高質(zhì)量的啟發(fā)式算 法上。目前已提出的啟發(fā)式算法相當(dāng)多，大體上可分為傳統(tǒng)啟發(fā)式算法 （ Heuristic ）和巨集啟發(fā)式算法（ Meta-Heuristic ）兩大類 11 。 傳統(tǒng)啟發(fā)式

21、算法具有求解速度快、 求得的解較為固定的特點(diǎn)。 已被證明會(huì)陷入局 部優(yōu)化解中 11 。巨集啟發(fā)式算法則嘗試以不同的方式跳出局部解，在可接受的 時(shí)間內(nèi)，求得近似最優(yōu)解，甚至是全局最優(yōu)解。所以在近年來的研究中，多用巨 集啟發(fā)式算法來求解車輛路徑問題， 或者混合使用傳統(tǒng)啟發(fā)式算法和巨集啟發(fā)式 算法。2.4.1 傳統(tǒng)啟發(fā)式算法根據(jù) Bodin 等人12 的研究，用于求解車輛路徑問題的傳統(tǒng)啟發(fā)式算法可 分為： 第一，先分組后安排路線的方法（ Cluster-First Route-Second ）：這種方法先把 節(jié)點(diǎn)（或弧）的需求進(jìn)行分組或劃群，然后對(duì)每一組設(shè)計(jì)一條經(jīng)濟(jì)的路線。如 Gillett 和 M

22、iller 于 1974 年提出的掃描（ sweep ）算法13,14,15 。方法是先以極 坐標(biāo)的方式表示各個(gè)客戶點(diǎn)的區(qū)域位置， 再任取一個(gè)客戶點(diǎn)作為起點(diǎn)以順時(shí)針方 向，以車輛容量為限制條件（或再加入其它限制條件）對(duì)區(qū)域進(jìn)行分割，使不超 過車輛容量 （或滿足其它限制條件） 的需求點(diǎn)組成一個(gè)區(qū)域， 一個(gè)區(qū)域就是一個(gè) 組。當(dāng)形成一系列這樣的組后， 再對(duì)每一組中的各點(diǎn)安排線路。 這種算法一般僅 適用于裝貨（或卸貨）問題，且車輛是封閉的。 第二，先安排路線后分組的方法（ Route-First Cluster-Second ）：在不考慮約束 條件的前提下進(jìn)行路線的構(gòu)建， 然后再根據(jù)約束條件對(duì)路線進(jìn)行

23、切割。 這種方法 首先構(gòu)造一條或幾條很長的路線 （通常不可行 ），它包括了所有需求對(duì)象，然后再 把這些很長的路線劃分成一些短而可行的路線。 具體進(jìn)行時(shí)， 一般是先解一個(gè)經(jīng) 過所有點(diǎn)的旅行商問題，形成一條路線，然后根據(jù)一定的約束 （ 如車輛容量等 ）對(duì) 它進(jìn)行分劃。典型的有由 Rosenkrantz 等人16于 1977 年提出的最臨近點(diǎn)法。 思路是以車場為起點(diǎn)， 尋找離車場距離成本最小且沒有加入路線的節(jié)點(diǎn)為起始路 線，重復(fù)以上步驟直至找不到可以滿足車輛限制條件的節(jié)點(diǎn)時(shí)， 回到車場重新出 發(fā)，另外構(gòu)建一條新的路徑。第三，節(jié)約插入算法（ Saving or Insertion ）：根據(jù)節(jié)約值的大小

24、來構(gòu)建路線， 直至無法改善或達(dá)到停止條件為止。 該算法的每一步， 把當(dāng)前的線路構(gòu)形 （很可 能是不可行的）跟另外的構(gòu)形（也可能是不可行的）進(jìn)行比較，后者或是根據(jù)某 個(gè)判別函數(shù)（例如總費(fèi)用） 會(huì)產(chǎn)生最大程度的節(jié)約的構(gòu)形， 或是以最小代價(jià)把一 個(gè)不在當(dāng)前構(gòu)形上的需求對(duì)象插人進(jìn)來的掏形，最后得到一個(gè)較好的可行構(gòu)形。 節(jié)約算法最早是由 Clark 和 Wright 于 1964 年提出的 11 。根據(jù)三角形兩邊之和 大于第三邊的性質(zhì)， 以一部車服務(wù)一個(gè)客戶作為初始解， 一部車服務(wù)一個(gè)客戶然 后就返回車場為其起始狀況， 計(jì)算路徑間的合并節(jié)約值。 將算出的節(jié)約值按照降 冪排序并依次合并路徑。 若找不到滿足

25、限制條件的節(jié)點(diǎn)， 便回到車場， 重新構(gòu)建 新的路徑，直到?jīng)]有大于零的節(jié)約值為止。節(jié)約算法是利用節(jié)約值的大小和是否滿足限制條件來決定兩節(jié)點(diǎn)是否相連的。 節(jié) 約值的計(jì)算如下：設(shè)0表示示車場，i和j為兩個(gè)任務(wù)點(diǎn)，定義點(diǎn)對(duì)i和j的節(jié)約 值為 其含義為點(diǎn)i和點(diǎn)j在同一條線路上的距離成本與點(diǎn)i和點(diǎn)j各在不同線路上的距 離成本相比得到的距離成本的節(jié)約值。這種算法與 Sweep 算法的適用范圍差不 多。2.4.2 巨集啟發(fā)式算法 巨集啟發(fā)式算法主要基于改進(jìn)或交換( Improvement or Exchange )的思路，即 先構(gòu)建一個(gè)初始解，再用貪婪算法( Greedy)17 ，進(jìn)行路線的優(yōu)化，直至無法 改

26、進(jìn)或達(dá)到停止條件為止。 該算法在始終保持解可行的情況下， 力圖向最優(yōu)目標(biāo) 靠近，每一步都產(chǎn)生另一個(gè)可行解以代替原來的解， 使目標(biāo)函數(shù)值得以改進(jìn)， 一 直繼續(xù)到不能再改進(jìn)目標(biāo)函數(shù)值為止。 經(jīng)典的遺傳算法、模擬退火算法、禁忌搜索算法、蟻群算法都屬于這一類方法。 遺傳算法( Genetic Algorithm, GA) 最早由 Holland 18 于 1975 年提出，是根據(jù) 達(dá)爾文進(jìn)化論中 “物競天擇，適者生存 ”的自然進(jìn)化法則發(fā)展而來。其基本精神是 進(jìn)化與選擇，利用復(fù)制( reproduction )、交配( crossover )、突變( mutat ion ) 三個(gè)基本運(yùn)算元重復(fù)運(yùn)作， 以

27、達(dá)到淘汰較差解的目的。 其做法是： 先由數(shù)個(gè)可行 解個(gè)體產(chǎn)生一母體集合，其中的元素即為基因(gene )。再通過計(jì)算第一代母 體中個(gè)體目標(biāo)值的方式，選出較優(yōu)秀的個(gè)體，以交配、突變等方式產(chǎn)生下一代。 最后依據(jù)停止條件結(jié)束演算。 遺傳算法具有多點(diǎn)平行搜尋可行解的特性， 已逐漸 被運(yùn)用于高度空間搜尋的組合最佳化問題上。模擬退火算法(Simulated Ann eali ng ，SA)，其最初的思想由 Metropolis在 1953 年提出， Kirkpatrick 等人19 在 1983 年成功地將其應(yīng)用在組合最優(yōu)化問題 中。模擬退火算法來源于固體退火原理： 將固體加溫至充分高， 再讓其徐徐冷卻，

28、 加溫時(shí)， 固體內(nèi)部粒子隨溫升變?yōu)闊o序狀， 內(nèi)能增大， 而徐徐冷卻時(shí)粒子漸趨有 序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。用固體 退火模擬組合優(yōu)化問題，將內(nèi)能 E模擬為目標(biāo)函數(shù)值f，溫度T演化成控制參數(shù) t，由初始解i和控制參數(shù)t的初值開始，對(duì)當(dāng)前解重復(fù) 產(chǎn)生新解計(jì)算目標(biāo)函 數(shù)差一接受或舍棄”的迭代，逐步衰減t值，并設(shè)定終止條件，即得到解組合優(yōu) 化問題的模擬退火算法。 算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解， 這是基于蒙 特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過程。模擬退火算法具有能往目標(biāo)值較差處移動(dòng)的機(jī)會(huì)， 這種隨機(jī)過程產(chǎn)生的機(jī)會(huì)使得 該算法有能力避免陷入局部優(yōu)化，而得到全

29、局最優(yōu)解。禁忌搜索法( Tabu Search, TS )，是由 Glover20 于 1977 年提出的， Willard 21 于 1989 年將其用于車輛路徑問題上。其求解的過程是先求得一初始解，然后在 鄰域中搜索較佳解或是移動(dòng)到較差的區(qū)域搜索該區(qū)域最佳解， 并且記錄曾經(jīng)搜尋 的路徑，作為下次搜索的依據(jù)， 以避免陷入局部最優(yōu)解中。 禁忌搜索算法主要包 含移步(Move)、候選列表(Can didate List)、禁忌列表(Tabu List)、渴望 準(zhǔn)則( Aspiration Level )及搜尋停止準(zhǔn)則( Stopping Criterion )等五種要素。 蟻群算法( Ant S

30、ystem, AS )最早由 Macro Dorigo22 于 1992 年提出，其靈感 來自螞蟻覓食時(shí)可以在食物和巢穴間找到最短路徑的能力。 螞蟻覓食時(shí)會(huì)在走過 的路線上留下一種稱為費(fèi)洛蒙 ( pheromone )的化學(xué)物質(zhì)， 費(fèi)洛蒙的濃度與遺留 時(shí)間成反比，與走過該路線的螞蟻的數(shù)量成正比。 當(dāng)一只螞蟻面臨路線的選擇時(shí)， 它會(huì)優(yōu)先選取費(fèi)洛蒙濃度高的路線。 就是說， 費(fèi)洛蒙殘留的濃度越高， 則吸引螞 蟻前來的能力越強(qiáng)，越多的螞蟻經(jīng)過某條路線時(shí)，該路線的費(fèi)洛蒙濃度就越高， 從而吸引更多的螞蟻前來。 通過這種方式， 螞蟻就可找出食物與巢穴間的最短路 徑。2.4.3 混合啟發(fā)式算法 一是、基于數(shù)學(xué)

31、規(guī)劃的算法( Mathematical-Programming Based ) 6 是把問題 直接描述成一個(gè)數(shù)學(xué)規(guī)劃問題， 根據(jù)其模型的特殊構(gòu)形， 應(yīng)用一定的技術(shù) (如分 解)進(jìn)行分劃，進(jìn)而求解已被廣泛研究過的子問題。典型的有 Fisher 和 Jaikumar 提出的算法。該算法把車輛路線問題構(gòu)造為一個(gè)廣 義分派問題， 并提出下述啟發(fā)式算法： 首先把問題描述為一個(gè)數(shù)學(xué)規(guī)劃問題， 再 將問題分解成一個(gè)旅行商問題和一個(gè)分派問題。 對(duì)每一輛車將顧客進(jìn)行分派， 這 通過解一般分派問題來得到。 每輛車為它的顧客服務(wù)， 以一個(gè)近似等于旅行商線 路的費(fèi)用為目標(biāo)， 分派一旦做出， 通過應(yīng)用一些旅行商問題的啟

32、發(fā)式算法或優(yōu)化 算法來得到每輛車的行車路線。二是、交互式優(yōu)化法 6 。即把人的因素結(jié)合到問題的求解過程中，其思想是； 有經(jīng)驗(yàn)的決策者應(yīng)具有確定和修改參數(shù)的能力， 并且根據(jù)知識(shí)經(jīng)驗(yàn)， 把主觀的估 計(jì)加到優(yōu)化模型中去。這通常會(huì)增加模型最終實(shí)現(xiàn)并被采用的可能性。 如 Cuilew， Jarvis 和 Ratfiff 提出的兩段法： 第一階段： 由有經(jīng)驗(yàn)的調(diào)度員或是根據(jù)自動(dòng)生成 規(guī)則選定一些 “組”點(diǎn)，目標(biāo)函數(shù)定義為線性近似 ( )，其中 定義為需求點(diǎn) i 和“組 點(diǎn)”之間的歐氏距離，根據(jù)確定的 組”點(diǎn)坐標(biāo)求解得出的分派問題，由求出的結(jié) 果再求解得出的定點(diǎn)問題，即重新確定每個(gè) “組”點(diǎn)的位置，以使分派

33、給它的各需 求點(diǎn)離它的總距離最小。 交替求解分派問題和定點(diǎn)問題， 直到目標(biāo)沒有進(jìn)一步的 改進(jìn)。第二階段：用列生成技術(shù)生成新解，直到不能進(jìn)一步改進(jìn)為止。 這幾種啟發(fā)式算法常不是絕對(duì)劃分的，有的方法同屬于好幾類。4.1.1 算法描述 模擬退火算法是一種用于求解大規(guī)模優(yōu)化問題的隨機(jī)搜索算法， 它以優(yōu)化問題求 解過程與物理系統(tǒng)退火過程之間的相似性為基礎(chǔ)； 優(yōu)化的目標(biāo)函數(shù)相當(dāng)于金屬的 內(nèi)能；優(yōu)化問題的自變量組合狀態(tài)空間相當(dāng)于金屬的內(nèi)能狀態(tài)空間； 問題的求解 過程就是找一個(gè)組合狀態(tài)， 使目標(biāo)函數(shù)值最小。 大量的研究證明， 模擬退火算法 可在多項(xiàng)式時(shí)間內(nèi)求解全局優(yōu)化問題的目標(biāo)。模擬退火算法來源于固體退火原理

34、， 將固體加溫至充分高， 再讓其徐徐冷卻， 加 溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀， 內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序， 在每個(gè)溫度都達(dá)到平衡態(tài)， 最后在常溫時(shí)達(dá)到基態(tài)， 內(nèi)能減為最小。 用固體退火 模擬組合優(yōu)化問題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f，溫度T演化成控制參數(shù)t， 即得到解組合優(yōu)化問題的模擬退火算法：由初始解 i和控制參數(shù)初值t開始，對(duì) 當(dāng)前解重復(fù) 產(chǎn)生新解一計(jì)算目標(biāo)函數(shù)差一接受或舍棄”的迭代，并逐步衰減t值, 算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解， 這是基于蒙特卡羅迭代求解法的一種 啟發(fā)式隨機(jī)搜索過程。模擬退火算法需要一個(gè)構(gòu)建好的初始解作為算法的輸入?yún)?shù)， 在進(jìn)入迭代后， 每 一次迭

35、代都需要構(gòu)建新解。 本文用最臨近點(diǎn)法來構(gòu)建初始解， 用區(qū)域搜索法來求 得每一次迭代的新解 28 。分別論述如下：1）最臨近點(diǎn)法構(gòu)建初始解：從盆景養(yǎng)護(hù)基地出發(fā)，尋找距離它最近的客戶，生 成一條線路；再從該客戶出發(fā)，尋找他的最臨近客戶，加入該線路。重復(fù)該過程 直到滿足車輛的最大裝載容量限制 （同時(shí)考慮時(shí)間窗限制和車輛的最大行駛距離 限制），即完成一條線路的構(gòu)建。返回盆景養(yǎng)護(hù)基地，重復(fù)以上步驟繼續(xù)構(gòu)建線 路，直到所有的客戶都被加入線路中，則初始解的構(gòu)建就完成了。2）區(qū)域搜索法產(chǎn)生新解：區(qū)域搜索法是通過不斷改善路經(jīng)來求得更佳的解，并 以貪婪法則決定是否接受新的改善解。 改善的方法是在同一條線路中隨機(jī)交

36、換節(jié) 點(diǎn)，或在相鄰線路中隨機(jī)交換節(jié)點(diǎn)。有2-opt交換法、3-opt交換法以及Cross-opt 交換法，本文采用 2-opt 交換法。4.1.2 算法步驟 模擬退火算法的主要步驟如下 29 ：1）初始化：初始溫度 （充分大 ），初始解狀態(tài) （是算法迭代的起點(diǎn) ）， 每個(gè) 值的 迭代次數(shù) ；2）對(duì) 重復(fù)以下第 （3）至第（6）步；3）產(chǎn)生新解 ；4）計(jì)算增量 ，其中 為評(píng)價(jià)函數(shù)；5）若 則接受 作為新的當(dāng)前解，否則以概率 接受 作為新的當(dāng)前解；6）如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。終止條件通常取為 連續(xù)若干個(gè)新解都沒有被接受時(shí)終止算法。否則執(zhí)行下面第 （7） 步；7）逐漸衰減（

37、趨于零），然后轉(zhuǎn)第 （2） 步。4.1.3 重點(diǎn)抽樣與 Metroplis 準(zhǔn)則模擬退火的主要思想是： 在搜索區(qū)間（二維平面中） 隨機(jī)游走（即隨機(jī)選擇點(diǎn)） ， 再以 Metropolis 準(zhǔn)則抽樣，使隨機(jī)游走逐漸收斂于局部最優(yōu)解。Metropolis 抽樣準(zhǔn)則是一種有效的重點(diǎn)抽樣法。其思想為：系統(tǒng)從一種狀態(tài)變到 另一種狀態(tài)時(shí)，相應(yīng)的能量從 變化到 ，如果 ，系統(tǒng)接收此狀態(tài)，否則，以 的 概率接收或丟棄此狀態(tài)。經(jīng)過一定次數(shù)的迭代，系統(tǒng)會(huì)逐漸趨于穩(wěn)定狀態(tài)。 重點(diǎn)抽樣時(shí)，新狀態(tài)如果向下則接受（局部最優(yōu)），若向上（全局搜索），以一 定概率接受。 模擬退火方法從某個(gè)初始解出發(fā)， 經(jīng)過大量解的變換后， 可

38、以求得 給定控制參數(shù)值時(shí)組合優(yōu)化問題的相對(duì)最優(yōu)解。然后減小控制參數(shù) 的值，重復(fù) 執(zhí)行 Metropolis 算法，就可以在控制參數(shù) T 趨于零時(shí)，最終求得組合優(yōu)化問題 的整體最優(yōu)解?？刂茀?shù)的值必須緩慢衰減。溫度是 Metropolis 算法的重要控制參數(shù)。開始時(shí)溫度高 （ 值大 ），算法可能接受 較差的惡化解；隨著 值的減小，只能接受較好的惡化解；最后當(dāng) 趨于 0 時(shí)，就 不再接受任何惡化解了。當(dāng) 值足夠大時(shí)（即無限高溫），系統(tǒng)立即均勻分布，接受所有提出的變換。 衰 減得越小， 到達(dá)終點(diǎn)的時(shí)間就越長， 但可使馬可夫鏈縮短， 使到達(dá)準(zhǔn)平衡分布的 時(shí)間縮短。4.1.4 算法重點(diǎn)和難點(diǎn) 模擬退火算法的重點(diǎn)是新解的產(chǎn)生和接受。主要有以下四個(gè)步驟： 其一、由一個(gè)產(chǎn)生函數(shù)從當(dāng)前解產(chǎn)生下一個(gè)位于解空間的新解。 為便于后續(xù)的計(jì) 算和接受， 減少算法耗時(shí)， 通常選擇由當(dāng)前新解經(jīng)過簡單地變換即可產(chǎn)生新解的 方法，如對(duì)構(gòu)成新解的全部或部分元素進(jìn)行置換、 互換等。 產(chǎn)生新解的變換方法 決定了當(dāng)前解的鄰域結(jié)構(gòu)，因而對(duì)冷卻進(jìn)度表的選取有一定的影響。其二、計(jì)算與新解所對(duì)應(yīng)的目標(biāo)函數(shù)差。 因?yàn)槟繕?biāo)函數(shù)差僅由變