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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21、算法具有求解速度快、 求得的解較為固定的特點。 已被證明會陷入局 部優(yōu)化解中 11 。巨集啟發(fā)式算法則嘗試以不同的方式跳出局部解，在可接受的 時間內(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é)點（或?。┑男枨筮M(jìn)行分組或劃群，然后對每一組設(shè)計一條經(jīng)濟(jì)的路線。如 Gillett 和 M

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

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

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

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

26、進(jìn)或達(dá)到停止條件為止。 該算法在始終保持解可行的情況下， 力圖向最優(yōu)目標(biāo) 靠近，每一步都產(chǎn)生另一個可行解以代替原來的解， 使目標(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 ) 三個基本運算元重復(fù)運作， 以

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

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

29、局最優(yōu)解。禁忌搜索法( Tabu Search, TS )，是由 Glover20 于 1977 年提出的， Willard 21 于 1989 年將其用于車輛路徑問題上。其求解的過程是先求得一初始解，然后在 鄰域中搜索較佳解或是移動到較差的區(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 年提出，其靈感 來自螞蟻覓食時可以在食物和巢穴間找到最短路徑的能力。 螞蟻覓食時會在走過 的路線上留下一種稱為費洛蒙 ( pheromone )的化學(xué)物質(zhì)， 費洛蒙的濃度與遺留 時間成反比，與走過該路線的螞蟻的數(shù)量成正比。 當(dāng)一只螞蟻面臨路線的選擇時， 它會優(yōu)先選取費洛蒙濃度高的路線。 就是說， 費洛蒙殘留的濃度越高， 則吸引螞 蟻前來的能力越強(qiáng)，越多的螞蟻經(jīng)過某條路線時，該路線的費洛蒙濃度就越高， 從而吸引更多的螞蟻前來。 通過這種方式， 螞蟻就可找出食物與巢穴間的最短路 徑。2.4.3 混合啟發(fā)式算法 一是、基于數(shù)學(xué)

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

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

33、給它的各需 求點離它的總距離最小。 交替求解分派問題和定點問題， 直到目標(biāo)沒有進(jìn)一步的 改進(jìn)。第二階段：用列生成技術(shù)生成新解，直到不能進(jìn)一步改進(jìn)為止。 這幾種啟發(fā)式算法常不是絕對劃分的，有的方法同屬于好幾類。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)空間； 問題的求解 過程就是找一個組合狀態(tài)， 使目標(biāo)函數(shù)值最小。 大量的研究證明， 模擬退火算法 可在多項式時間內(nèi)求解全局優(yōu)化問題的目標(biāo)。模擬退火算法來源于固體退火原理

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

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

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

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

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