車輛路徑問題概念、模型與算法(五星推薦)

1、車輛路徑問題概念、模型及算法 12021/6/7 1、定義 車輛路徑問題車輛路徑問題(VRP)(VRP)一般定義為：對一系列裝貨點一般定義為：對一系列裝貨點 和卸貨點，組織適當(dāng)?shù)男熊嚲€路，使車輛有序地通和卸貨點，組織適當(dāng)?shù)男熊嚲€路，使車輛有序地通 過它們，在滿足一定的約束條件過它們，在滿足一定的約束條件( (如貨物需求量、如貨物需求量、 發(fā)送量、交發(fā)貨時間、車輛容量限制、行駛里程限發(fā)送量、交發(fā)貨時間、車輛容量限制、行駛里程限 制、時間限制等制、時間限制等) )下，達到一定問題的目標下，達到一定問題的目標( (如路程如路程 最短、費用最少、時間盡量少、使用車輛數(shù)盡量少最短、費用最少、時間盡量少、

2、使用車輛數(shù)盡量少 等等) )。 22021/6/7 32021/6/7 目前有關(guān)目前有關(guān)VRPVRP的研究已經(jīng)可以表示（如圖的研究已經(jīng)可以表示（如圖1 1）為：給）為：給 定一個或多個中心點（中心倉庫，定一個或多個中心點（中心倉庫，central depotcentral depot）、）、 一個車輛集合和一個顧客集合，車輛和顧客各有自一個車輛集合和一個顧客集合，車輛和顧客各有自 己的屬性，每輛車都有容量，所裝載貨物不能超過己的屬性，每輛車都有容量，所裝載貨物不能超過 它的容量。起初車輛都在中心點，顧客在空間任意它的容量。起初車輛都在中心點，顧客在空間任意 分布，車把貨物從車庫運送到每一個顧客

3、（或從每分布，車把貨物從車庫運送到每一個顧客（或從每 個顧客處把貨物運到車庫），要求滿足顧客的需求，個顧客處把貨物運到車庫），要求滿足顧客的需求， 車輛最后返回車庫，每個顧客只能被服務(wù)一次，怎車輛最后返回車庫，每個顧客只能被服務(wù)一次，怎 樣才能使運輸費用最小。而顧客的需求或已知、或樣才能使運輸費用最小。而顧客的需求或已知、或 隨機、或以時間規(guī)律變化。隨機、或以時間規(guī)律變化。 42021/6/7 2、VRP問題約束 (1) (1) 容量約束：任意車輛路徑的總重量不能超過該容量約束：任意車輛路徑的總重量不能超過該 車輛的能力負荷。引出帶容量約束的車輛路徑問題車輛的能力負荷。引出帶容量約束的車輛路徑

4、問題 (CapacitatedVehicle Routing Problem(CapacitatedVehicle Routing Problem，CVRP)CVRP)。 (2) (2) 優(yōu)先約束：引出優(yōu)先約束車輛路徑問題優(yōu)先約束：引出優(yōu)先約束車輛路徑問題 (VehicleRouting Problem with precedence (VehicleRouting Problem with precedence ConstraintsConstraints，VRPPC)VRPPC)。 (3) (3) 車型約束：引出多車型車輛路徑問題車型約束：引出多車型車輛路徑問題 (Mixed/Hetero

5、geneous Fleet Vehicle Routing (Mixed/Heterogeneous Fleet Vehicle Routing ProblemProblem，MFVRP/ HFVRP)MFVRP/ HFVRP)。 52021/6/7 (4) (4) 時間窗約束：包括硬時間窗時間窗約束：包括硬時間窗(Hard Time (Hard Time windows)windows)和軟時間窗和軟時間窗(Soft Time windows) (Soft Time windows) 約束。約束。 引出帶時間窗引出帶時間窗( (包括硬時間窗和軟時間窗包括硬時間窗和軟時間窗) )的車輛路的車輛

6、路 徑問題徑問題(Vehicle Routing Problem withTime (Vehicle Routing Problem withTime windowswindows，VRPTW)VRPTW)。 (5) (5) 相容性約束：引出相容性約束車輛路徑問題相容性約束：引出相容性約束車輛路徑問題 (VehicleRouting Problem with Compatibility (VehicleRouting Problem with Compatibility ConstraintsConstraints，VRPCC)VRPCC)。 (6) (6) 隨機需求：引出隨機需求車輛路徑問題

7、隨機需求：引出隨機需求車輛路徑問題 (VehicleRouting Problem with Stochastic (VehicleRouting Problem with Stochastic DemandDemand，VRPSD)VRPSD)。 62021/6/7 (7) (7) 開路：引出開路車輛路徑問題開路：引出開路車輛路徑問題(Open Vehicle (Open Vehicle RoutingProblem)RoutingProblem)。 (8) (8) 多運輸中心：引出多運輸中心的車輛路徑問題多運輸中心：引出多運輸中心的車輛路徑問題 (Multi-Depot Vehicle R

8、outing Problem)(Multi-Depot Vehicle Routing Problem)。 (9) (9) 回程運輸：引出帶回程運輸?shù)能囕v路徑問題回程運輸：引出帶回程運輸?shù)能囕v路徑問題 (VehicleRouting Problem with Backhauls)(VehicleRouting Problem with Backhauls)。 (10) (10) 最后時間期限：引出帶最后時間期限的車輛路最后時間期限：引出帶最后時間期限的車輛路 徑問題徑問題(Vehicle Routing Problem with Time (Vehicle Routing Problem wi

9、th Time Deadlines)Deadlines)。 (11) (11) 車速隨時間變化：引出車速隨時間變化的車輛車速隨時間變化：引出車速隨時間變化的車輛 路徑問題路徑問題(Time-Dependent Vehicle Routing (Time-Dependent Vehicle Routing Problem)Problem)。 72021/6/7 3、 CVRP CVRP問題描述及其數(shù)學(xué)模型問題描述及其數(shù)學(xué)模型 CVRPCVRP的描述：設(shè)某中心車場有的描述：設(shè)某中心車場有k k輛車，每輛配送車輛車，每輛配送車 的最大載重量的最大載重量Q Q，需要對，需要對n n個客戶個客戶( (節(jié)

10、點節(jié)點) )進行運輸配進行運輸配 送，每輛車從中心車場出發(fā)給若干個客戶送貨，最送，每輛車從中心車場出發(fā)給若干個客戶送貨，最 終回到中心車場，客戶點終回到中心車場，客戶點i i的貨物需求量是的貨物需求量是q qi i ( (i i=1,2,=1,2,n n) )，且，且q qi i Q Q。記配送中心編號為。記配送中心編號為0 0，各，各 客戶編號為客戶編號為i i( (i i=1,2 ,=1,2 ,n n) )， c cij ij表示客戶 表示客戶i i到客到客 戶戶j j的距離。求滿足車輛數(shù)最小，車輛行駛總路程的距離。求滿足車輛數(shù)最小，車輛行駛總路程 最短的運送方案。最短的運送方案。 820

11、21/6/7 定義變量如下定義變量如下: : 92021/6/7 建立此問題的數(shù)學(xué)模型建立此問題的數(shù)學(xué)模型： 102021/6/7 4、車輛路徑問題算法綜述 目前，求解車輛路徑問題的方法非常多，基本上可目前，求解車輛路徑問題的方法非常多，基本上可 以分為精確算法和啟發(fā)式算法以分為精確算法和啟發(fā)式算法2 2大類。大類。 精確算法是指可求出其最優(yōu)解的算法，主要運用線精確算法是指可求出其最優(yōu)解的算法，主要運用線 性規(guī)劃、整數(shù)規(guī)劃、非線性規(guī)劃等數(shù)學(xué)規(guī)劃技術(shù)來性規(guī)劃、整數(shù)規(guī)劃、非線性規(guī)劃等數(shù)學(xué)規(guī)劃技術(shù)來 描述物流系統(tǒng)的數(shù)量關(guān)系，以便求得最優(yōu)決策。描述物流系統(tǒng)的數(shù)量關(guān)系，以便求得最優(yōu)決策。 （運籌學(xué)領(lǐng)域）

12、（運籌學(xué)領(lǐng)域） 精確算法主要有精確算法主要有： 分枝定界法分枝定界法(Branch and Bound Approach)(Branch and Bound Approach) 割平面法割平面法(Cutting Planes Approach)(Cutting Planes Approach) 網(wǎng)絡(luò)流算法網(wǎng)絡(luò)流算法(Network Flow Approach)(Network Flow Approach) 動態(tài)規(guī)劃算法動態(tài)規(guī)劃算法(Dynamic Programming Approach)(Dynamic Programming Approach) 112021/6/7 分枝定界法分枝定界法(

13、Branch and Bound Approach)(Branch and Bound Approach) 以求相應(yīng)的線性規(guī)劃問題的最優(yōu)解為出發(fā)點，如果得以求相應(yīng)的線性規(guī)劃問題的最優(yōu)解為出發(fā)點，如果得 到的解不符合整數(shù)條件，就將原規(guī)劃問題分成幾支，到的解不符合整數(shù)條件，就將原規(guī)劃問題分成幾支， 每支增加了約束條件，即縮小了可行解區(qū)域，可行解每支增加了約束條件，即縮小了可行解區(qū)域，可行解 范圍也隨之縮小了，因而整數(shù)規(guī)劃的最優(yōu)值不會優(yōu)于范圍也隨之縮小了，因而整數(shù)規(guī)劃的最優(yōu)值不會優(yōu)于 相應(yīng)的線性規(guī)劃最優(yōu)值。相應(yīng)的線性規(guī)劃最優(yōu)值。 “定界定界”是指為目標函數(shù)定上下界，以便自動舍去那是指為目標函數(shù)定上下

14、界，以便自動舍去那 些最優(yōu)值較差的子問題，提高計算效率。當(dāng)整數(shù)規(guī)劃些最優(yōu)值較差的子問題，提高計算效率。當(dāng)整數(shù)規(guī)劃 問題的最優(yōu)目標函數(shù)值的上下界相等時，該整數(shù)規(guī)劃問題的最優(yōu)目標函數(shù)值的上下界相等時，該整數(shù)規(guī)劃 最優(yōu)解已求出。最優(yōu)解已求出。 122021/6/7 首先，不考慮變量的整數(shù)約束，求解松弛問題首先，不考慮變量的整數(shù)約束，求解松弛問題 線性規(guī)劃的最優(yōu)解。如果線性規(guī)劃的最優(yōu)解恰好是線性規(guī)劃的最優(yōu)解。如果線性規(guī)劃的最優(yōu)解恰好是 整數(shù)解，則這個解就是整數(shù)規(guī)劃的最優(yōu)解。整數(shù)解，則這個解就是整數(shù)規(guī)劃的最優(yōu)解。 如果線性規(guī)劃的最優(yōu)解中至少有一個變量不是如果線性規(guī)劃的最優(yōu)解中至少有一個變量不是 整數(shù)，把

15、線性規(guī)劃的可行域切割成兩部分，分別求整數(shù)，把線性規(guī)劃的可行域切割成兩部分，分別求 解兩個線性規(guī)劃的最優(yōu)解。解兩個線性規(guī)劃的最優(yōu)解。 132021/6/7 如果這兩個線性規(guī)劃的最優(yōu)解還不是整數(shù)解，如果這兩個線性規(guī)劃的最優(yōu)解還不是整數(shù)解， 分別把每一個可行域再進行分割。這個過程，叫做分別把每一個可行域再進行分割。這個過程，叫做 “分支分支”。 分支過程得到的整數(shù)解中，目標函數(shù)值最優(yōu)的分支過程得到的整數(shù)解中，目標函數(shù)值最優(yōu)的 一個叫做整數(shù)規(guī)劃目標函數(shù)值的一個叫做整數(shù)規(guī)劃目標函數(shù)值的“界界”。分支過程。分支過程 中非整數(shù)的線性規(guī)劃的最優(yōu)解，如果目標函數(shù)值劣中非整數(shù)的線性規(guī)劃的最優(yōu)解，如果目標函數(shù)值劣

16、于或等于這個于或等于這個“界界”，就停止繼續(xù)分支。這個過程，就停止繼續(xù)分支。這個過程， 叫做叫做“定界定界”。 142021/6/7 割平面法割平面法(Cutting Planes Approach)(Cutting Planes Approach) 用割平面法求解整數(shù)規(guī)劃的基本思路是：先不考慮整用割平面法求解整數(shù)規(guī)劃的基本思路是：先不考慮整 數(shù)約束條件，求松弛問題的最優(yōu)解，如果獲得整數(shù)最數(shù)約束條件，求松弛問題的最優(yōu)解，如果獲得整數(shù)最 優(yōu)解，即為所求，運算停止。如果所得到最優(yōu)解不滿優(yōu)解，即為所求，運算停止。如果所得到最優(yōu)解不滿 足整數(shù)約束條件，則在此非整數(shù)解的基礎(chǔ)上增加新的足整數(shù)約束條件，則在

17、此非整數(shù)解的基礎(chǔ)上增加新的 約束條件重新求解。這個新增加的約束條件的作用就約束條件重新求解。這個新增加的約束條件的作用就 是去切割相應(yīng)松弛問題的可行域，即割去松弛問題的是去切割相應(yīng)松弛問題的可行域，即割去松弛問題的 部分非整數(shù)解部分非整數(shù)解( (包括原已得到的非整數(shù)最優(yōu)解包括原已得到的非整數(shù)最優(yōu)解) )。而把。而把 所有的整數(shù)解都保留下來，故稱新增加的約束條件為所有的整數(shù)解都保留下來，故稱新增加的約束條件為 割平面。當(dāng)經(jīng)過多次切割后，就會使被切割后保留下割平面。當(dāng)經(jīng)過多次切割后，就會使被切割后保留下 來的可行域上有一個坐標均為整數(shù)的頂點，它恰好就來的可行域上有一個坐標均為整數(shù)的頂點，它恰好就

18、是所求問題的整數(shù)最優(yōu)解。即切割后所對應(yīng)的松弛問是所求問題的整數(shù)最優(yōu)解。即切割后所對應(yīng)的松弛問 題，與原整數(shù)規(guī)劃問題具有相同的最優(yōu)解。題，與原整數(shù)規(guī)劃問題具有相同的最優(yōu)解。 152021/6/7 網(wǎng)絡(luò)流算法網(wǎng)絡(luò)流算法(Network Flow Approach)(Network Flow Approach) 圖論圖論中的一種理論與方法，研究網(wǎng)絡(luò)上的一類最優(yōu)化中的一種理論與方法，研究網(wǎng)絡(luò)上的一類最優(yōu)化 問題問題 。19551955年年 ，T.E.T.E.哈里斯哈里斯在研究鐵路最大通量時在研究鐵路最大通量時 首先提出在一個給定的網(wǎng)絡(luò)上尋求兩點間最大運輸量首先提出在一個給定的網(wǎng)絡(luò)上尋求兩點間最大運輸量

19、 的問題。的問題。19561956年，年，L.R. L.R. 福特和福特和 D.R. D.R. 富爾克森等人給富爾克森等人給 出了解決這類問題的算法，從而建立了出了解決這類問題的算法，從而建立了網(wǎng)絡(luò)流理論網(wǎng)絡(luò)流理論。 所謂網(wǎng)絡(luò)或容量網(wǎng)絡(luò)指的是一個連通的賦權(quán)有向圖所謂網(wǎng)絡(luò)或容量網(wǎng)絡(luò)指的是一個連通的賦權(quán)有向圖 D= D= （V V、E E、C C） ， 其中其中V V 是該圖的頂點集，是該圖的頂點集，E E是有向邊是有向邊 ( (即弧即弧) )集，集，C C是弧上的容量。此外頂點集中包括一個起是弧上的容量。此外頂點集中包括一個起 點和一個終點。網(wǎng)絡(luò)上的流就是由起點流向終點的可點和一個終點。網(wǎng)絡(luò)上的

20、流就是由起點流向終點的可 行流，這是定義在網(wǎng)絡(luò)上的非負函數(shù)，它一方面受到行流，這是定義在網(wǎng)絡(luò)上的非負函數(shù)，它一方面受到 容量的限制，另一方面除去起點和終點以外，在所有容量的限制，另一方面除去起點和終點以外，在所有 中途點要求保持流入量和流出量是平衡的。中途點要求保持流入量和流出量是平衡的。 162021/6/7 動態(tài)規(guī)劃算法動態(tài)規(guī)劃算法(Dynamic Programming Approach)(Dynamic Programming Approach) 動態(tài)規(guī)劃是一種求解多階段決策問題的系統(tǒng)技術(shù)。動態(tài)規(guī)劃是一種求解多階段決策問題的系統(tǒng)技術(shù)。 如果一類活動過程可以分為若干個互相聯(lián)系的階段，如果

21、一類活動過程可以分為若干個互相聯(lián)系的階段， 在每一個階段都需作出決策，一個階段的決策確定以在每一個階段都需作出決策，一個階段的決策確定以 后，常常影響到下一個階段的決策，從而就完全確定后，常常影響到下一個階段的決策，從而就完全確定 了一個過程的活動路線，則稱它為多階段決策問題。了一個過程的活動路線，則稱它為多階段決策問題。 各個階段的決策構(gòu)成一個決策序列，稱為一個策略。各個階段的決策構(gòu)成一個決策序列，稱為一個策略。 每一個階段都有若干個決策可供選擇，因而就有許多每一個階段都有若干個決策可供選擇，因而就有許多 策略供我們選取，對應(yīng)于一個策略可以確定活動的效策略供我們選取，對應(yīng)于一個策略可以確定活

22、動的效 果，這個效果可以用數(shù)量來確定。策略不同，效果也果，這個效果可以用數(shù)量來確定。策略不同，效果也 不同，多階段決策問題，就是要在可以選擇的那些策不同，多階段決策問題，就是要在可以選擇的那些策 略中間，選取一個最優(yōu)策略，使在預(yù)定的標準下達到略中間，選取一個最優(yōu)策略，使在預(yù)定的標準下達到 最好的效果。最好的效果。 172021/6/7 總的說來，精確性算法基于嚴格的數(shù)學(xué)手段，在可總的說來，精確性算法基于嚴格的數(shù)學(xué)手段，在可 以求解的情況下，其解通常要優(yōu)于人工智能算法。以求解的情況下，其解通常要優(yōu)于人工智能算法。 但由于引入嚴格的數(shù)學(xué)方法，計算量一般隨問題規(guī)但由于引入嚴格的數(shù)學(xué)方法，計算量一般隨

23、問題規(guī) 模的增大呈指數(shù)增長，因而無法避開指數(shù)爆炸問題，模的增大呈指數(shù)增長，因而無法避開指數(shù)爆炸問題， 從而使該類算法只能有效求解中小規(guī)模的確定性從而使該類算法只能有效求解中小規(guī)模的確定性 VRPVRP，并且通常這些算法都是針對某一特定問題設(shè)，并且通常這些算法都是針對某一特定問題設(shè) 計的計的, ,適用能力較差適用能力較差, ,因此在實際中其應(yīng)用范圍很有因此在實際中其應(yīng)用范圍很有 限。限。 182021/6/7 啟發(fā)式算法啟發(fā)式算法 由于車輛路徑優(yōu)化問題是由于車輛路徑優(yōu)化問題是NPNP難題，高效的精確算法難題，高效的精確算法 存在的可能性不大存在的可能性不大( (除非除非P=NP)P=NP)，所以

24、尋找近似算法，所以尋找近似算法 是必要和現(xiàn)實的，為此專家主要把精力花在構(gòu)造高是必要和現(xiàn)實的，為此專家主要把精力花在構(gòu)造高 質(zhì)量的啟發(fā)式算法上。啟發(fā)式算法是在狀態(tài)空間中質(zhì)量的啟發(fā)式算法上。啟發(fā)式算法是在狀態(tài)空間中 的改進搜索算法，它對每一個搜索的位置進行評價，的改進搜索算法，它對每一個搜索的位置進行評價， 得到最好的位置，再從這個位置進行搜索直到目標。得到最好的位置，再從這個位置進行搜索直到目標。 在啟發(fā)式搜索中，對位置的估價十分重要，采用不在啟發(fā)式搜索中，對位置的估價十分重要，采用不 同的估價可以有不同的效果。目前已提出的啟發(fā)式同的估價可以有不同的效果。目前已提出的啟發(fā)式 算法較多，分類也相當(dāng)

25、多，主要的啟發(fā)式算法有以算法較多，分類也相當(dāng)多，主要的啟發(fā)式算法有以 下幾類：構(gòu)造算法、兩階段法、智能化算法。下幾類：構(gòu)造算法、兩階段法、智能化算法。 192021/6/7 構(gòu)造算法構(gòu)造算法(Constructive Algorithm)(Constructive Algorithm) 這類方法的基本思想是：根據(jù)一些準則，每一次將一這類方法的基本思想是：根據(jù)一些準則，每一次將一 個不在線路上的點增加進線路，直到所有點都被安排個不在線路上的點增加進線路，直到所有點都被安排 進線路為止。該類算法的每一步把當(dāng)前的線路構(gòu)形進線路為止。該類算法的每一步把當(dāng)前的線路構(gòu)形( (很很 可能是不可行的可能是不可

26、行的) )跟另外的構(gòu)形跟另外的構(gòu)形( (也可能是不可行的也可能是不可行的) )進進 行比較并加以改進，后者或是根據(jù)某個判別函數(shù)行比較并加以改進，后者或是根據(jù)某個判別函數(shù)( (例如例如 總費用總費用) )會產(chǎn)生最大限度的節(jié)約的構(gòu)形，或是以最小代會產(chǎn)生最大限度的節(jié)約的構(gòu)形，或是以最小代 價把一個不在當(dāng)前構(gòu)形上的需求對象插入進來的構(gòu)形，價把一個不在當(dāng)前構(gòu)形上的需求對象插入進來的構(gòu)形， 最后得到一個較好的可行構(gòu)形。這類算法中中最著名最后得到一個較好的可行構(gòu)形。這類算法中中最著名 的是的是ClarkeClarke和和WrightWright在在19641964年提出的節(jié)約算法。年提出的節(jié)約算法。 構(gòu)造算

27、法最早提出來解決旅行商問題，這些方法一般構(gòu)造算法最早提出來解決旅行商問題，這些方法一般 速度快，也很靈活，但這類方法有時找到的解離最優(yōu)速度快，也很靈活，但這類方法有時找到的解離最優(yōu) 解差得很遠。解差得很遠。 202021/6/7 兩階段法兩階段法(Two-phase Algorithm)(Two-phase Algorithm) 學(xué)者們通過對構(gòu)造算法的研究，認為由構(gòu)造算法求學(xué)者們通過對構(gòu)造算法的研究，認為由構(gòu)造算法求 得的解可以被進一步改進，為此提出了兩階段法。得的解可以被進一步改進，為此提出了兩階段法。 第一階段得到一可行解，第二階段通過對點的調(diào)整，第一階段得到一可行解，第二階段通過對點的調(diào)

28、整， 在始終保持解可行的情況下，力圖向最優(yōu)目標靠近，在始終保持解可行的情況下，力圖向最優(yōu)目標靠近， 每一步都產(chǎn)生另一個可行解以代替原來的解，使目每一步都產(chǎn)生另一個可行解以代替原來的解，使目 標函數(shù)值得以改進，一直繼續(xù)到不能再改進目標函標函數(shù)值得以改進，一直繼續(xù)到不能再改進目標函 數(shù)值為止。數(shù)值為止。 212021/6/7 一般第一階段常用構(gòu)造算法，在第二階段常用的改一般第一階段常用構(gòu)造算法，在第二階段常用的改 進技術(shù)有進技術(shù)有2-opt(Lin,1965)2-opt(Lin,1965)，3-opt(Lin 3-opt(Lin Kernighan,1973)Kernighan,1973)和和Or

29、-opt (Or,1976)Or-opt (Or,1976)交換法，這交換法，這 是一種在解的鄰域中搜索，對初始解進行某種程度是一種在解的鄰域中搜索，對初始解進行某種程度 優(yōu)化的算法，以改進初始解。優(yōu)化的算法，以改進初始解。 在兩階段法求解過程中，常常采用交互式優(yōu)化技術(shù)，在兩階段法求解過程中，常常采用交互式優(yōu)化技術(shù)， 把人的主觀能動作用結(jié)合到問題的求解過程中，其把人的主觀能動作用結(jié)合到問題的求解過程中，其 主要思想是：有經(jīng)驗的決策者具有對結(jié)果和參數(shù)的主要思想是：有經(jīng)驗的決策者具有對結(jié)果和參數(shù)的 某種判斷能力，并且根據(jù)知識直感，把主觀的估計某種判斷能力，并且根據(jù)知識直感，把主觀的估計 加到優(yōu)化模

30、型中去。這樣做通常會增加模型最終實加到優(yōu)化模型中去。這樣做通常會增加模型最終實 現(xiàn)并被采用的可能性?，F(xiàn)并被采用的可能性。 222021/6/7 智能化算法智能化算法(Intelligent Algorithm)(Intelligent Algorithm) 這類算法以啟發(fā)式準則來代替精確算法中的決策準這類算法以啟發(fā)式準則來代替精確算法中的決策準 則，以縮小解搜索的空間。則，以縮小解搜索的空間。 總體來看，盡管啟發(fā)式算法能夠在有限的時間內(nèi)求總體來看，盡管啟發(fā)式算法能夠在有限的時間內(nèi)求 出質(zhì)量較高的解，但由于其搜索解空間的能力有所出質(zhì)量較高的解，但由于其搜索解空間的能力有所 限制，因此經(jīng)常無法達到

31、預(yù)期的要求。限制，因此經(jīng)常無法達到預(yù)期的要求。2020世紀世紀9090年年 代以來，由于人工智能方法在解決組合優(yōu)化問題中代以來，由于人工智能方法在解決組合優(yōu)化問題中 的強大功能，不少學(xué)者開始將人工智能引入車輛路的強大功能，不少學(xué)者開始將人工智能引入車輛路 線問題的求解中，并構(gòu)造了大量的基于人工智能的線問題的求解中，并構(gòu)造了大量的基于人工智能的 啟發(fā)式算法啟發(fā)式算法( (智能化啟發(fā)式算法智能化啟發(fā)式算法) )。 232021/6/7 智能化啟發(fā)式算法從本質(zhì)上講仍然屬于啟發(fā)式算法，智能化啟發(fā)式算法從本質(zhì)上講仍然屬于啟發(fā)式算法， 其基本思想是從一初始解開始，通過對當(dāng)前的解進其基本思想是從一初始解開始

32、，通過對當(dāng)前的解進 行反復(fù)地局部擾亂行反復(fù)地局部擾亂(Perturbations)(Perturbations)以達到較好的以達到較好的 解。目前，最常見的智能化啟發(fā)式算法包括模擬退解。目前，最常見的智能化啟發(fā)式算法包括模擬退 火算法火算法(Simulated Annealing)(Simulated Annealing)、禁忌搜索算法、禁忌搜索算法 (Tabu Search)(Tabu Search)、遺傳算法、遺傳算法(Genetic Algorithm)(Genetic Algorithm)、 蟻群算法蟻群算法(Ant Colony)(Ant Colony)和神經(jīng)網(wǎng)絡(luò)和神經(jīng)網(wǎng)絡(luò)(Neut

33、ral (Neutral Networks)Networks)、粒子群算法（、粒子群算法（Particle Swarm Particle Swarm Optimization,PSOOptimization,PSO）方法等。）方法等。 242021/6/7 模擬退火算法模擬退火算法(Simulated Annealing)(Simulated Annealing) 模擬退火算法來源于固體退火原理，將固體加溫至充分高，再模擬退火算法來源于固體退火原理，將固體加溫至充分高，再 讓其徐徐冷卻，加溫時，固體內(nèi)部粒子隨讓其徐徐冷卻，加溫時，固體內(nèi)部粒子隨溫升溫升變?yōu)闊o序狀，內(nèi)變?yōu)闊o序狀，內(nèi) 能增大，而徐

34、徐冷卻時粒子漸趨有序，在每個溫度都達到平衡能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡 態(tài)，最后在常溫時達到基態(tài)，內(nèi)能減為最小。根據(jù)態(tài)，最后在常溫時達到基態(tài)，內(nèi)能減為最小。根據(jù)MetropolisMetropolis 準則，準則，粒子粒子在溫度在溫度T T時趨于平衡的時趨于平衡的概率概率為為e(-e(-EE/(kT)/(kT)，其中，其中E E 為溫度為溫度T T時的內(nèi)能，時的內(nèi)能，EE為其改變量，為其改變量，k k為為BoltzmannBoltzmann常數(shù)。用常數(shù)。用固固 體體退火模擬組合優(yōu)化問題，將內(nèi)能退火模擬組合優(yōu)化問題，將內(nèi)能E E模擬為模擬為目標函數(shù)目標函數(shù)值值f f，溫

35、度，溫度 T T演化成控制參數(shù)演化成控制參數(shù)t t，即得到解組合優(yōu)化問題的模擬退火算法：，即得到解組合優(yōu)化問題的模擬退火算法： 由初始解由初始解i i和控制參數(shù)初值和控制參數(shù)初值t t開始，對當(dāng)前解重復(fù)開始，對當(dāng)前解重復(fù)“產(chǎn)生新解產(chǎn)生新解 計算目標函數(shù)差計算目標函數(shù)差接受或舍棄接受或舍棄”的迭代，并逐步衰減的迭代，并逐步衰減t t值，算值，算 法終止時的當(dāng)前解即為所得近似法終止時的當(dāng)前解即為所得近似最優(yōu)解最優(yōu)解，這是基于，這是基于蒙特卡羅蒙特卡羅迭迭 代求解法的一種啟發(fā)式代求解法的一種啟發(fā)式隨機搜索隨機搜索過程。退火過程由冷卻進度表過程。退火過程由冷卻進度表 (Cooling Schedule

36、)(Cooling Schedule)控制，包括控制參數(shù)的初值控制，包括控制參數(shù)的初值t t及其衰減因及其衰減因 子子tt、每個、每個t t值時的迭代次數(shù)值時的迭代次數(shù)L L和停止條件和停止條件S S。 252021/6/7 禁忌搜索算法禁忌搜索算法(Tabu Search)(Tabu Search) 禁忌算法是一種隨機搜索算法，它從一個初始可行解出發(fā)，選擇一系列禁忌算法是一種隨機搜索算法，它從一個初始可行解出發(fā)，選擇一系列 的特定搜索方向（移動）作為試探，選擇實現(xiàn)讓特定的目標函數(shù)值變化的特定搜索方向（移動）作為試探，選擇實現(xiàn)讓特定的目標函數(shù)值變化 最多的移動。為了避免陷入局部最優(yōu)解，最多的移

37、動。為了避免陷入局部最優(yōu)解，TSTS搜索中采用了一種靈活的搜索中采用了一種靈活的 “記憶記憶”技術(shù)，對已經(jīng)進行的優(yōu)化過程進行記錄和選擇，指導(dǎo)下一步的技術(shù)，對已經(jīng)進行的優(yōu)化過程進行記錄和選擇，指導(dǎo)下一步的 搜索方向，這就是搜索方向，這就是TabuTabu表的建立。表的建立。 1 1、在搜索中，構(gòu)造一個短期循環(huán)記憶表、在搜索中，構(gòu)造一個短期循環(huán)記憶表- -禁忌表，禁忌表中存放剛剛進禁忌表，禁忌表中存放剛剛進 行過的行過的 |T|T|（T T稱為禁忌表）個鄰居的移動，這種移動即解的簡單變化。稱為禁忌表）個鄰居的移動，這種移動即解的簡單變化。 2 2、禁忌表中的移動稱為禁忌移動。對于進入禁忌表中的移動

38、，、禁忌表中的移動稱為禁忌移動。對于進入禁忌表中的移動， 在以后在以后 的的 |T| |T| 次循環(huán)內(nèi)是禁止的，以避免回到原來的解，從而避免陷入循環(huán)。次循環(huán)內(nèi)是禁止的，以避免回到原來的解，從而避免陷入循環(huán)。 |T| |T| 次循環(huán)后禁忌解除。次循環(huán)后禁忌解除。 3 3、禁忌表是一個循環(huán)表，在搜索過程中被循環(huán)的修改，使禁忌表始終保、禁忌表是一個循環(huán)表，在搜索過程中被循環(huán)的修改，使禁忌表始終保 持持 |T| |T| 個移動。個移動。 4 4、即使引入了禁忌表，禁忌搜索仍可能出現(xiàn)循環(huán)。因此，必須給定停止、即使引入了禁忌表，禁忌搜索仍可能出現(xiàn)循環(huán)。因此，必須給定停止 準則以避免出現(xiàn)循環(huán)。當(dāng)?shù)鷥?nèi)所發(fā)現(xiàn)

39、的最好解無法改進或無法離開它準則以避免出現(xiàn)循環(huán)。當(dāng)?shù)鷥?nèi)所發(fā)現(xiàn)的最好解無法改進或無法離開它 時，算法停止。時，算法停止。 262021/6/7 遺傳算法遺傳算法(Genetic Algorithm)(Genetic Algorithm) 遺傳算法是模擬遺傳算法是模擬達爾文達爾文生物進化生物進化論的自然選擇和論的自然選擇和遺傳學(xué)遺傳學(xué)機理的生物進化過程的機理的生物進化過程的 計算計算模型模型，是一種通過模擬自然進化過程搜索，是一種通過模擬自然進化過程搜索最優(yōu)解最優(yōu)解的方法。遺傳算法是從代表的方法。遺傳算法是從代表 問題可能潛在的解集的一個問題可能潛在的解集的一個種群種群（populationpo

40、pulation）開始的，而一個種群則由經(jīng)過）開始的，而一個種群則由經(jīng)過基基 因因（genegene）編碼的一定數(shù)目的個體）編碼的一定數(shù)目的個體(individual)(individual)組成。每個個體實際上是組成。每個個體實際上是染色體染色體 (chromosome)(chromosome)帶有特征的實體。染色體作為帶有特征的實體。染色體作為遺傳物質(zhì)遺傳物質(zhì)的主要載體，即多個基因的的主要載體，即多個基因的 集合集合，其內(nèi)部表現(xiàn)（即，其內(nèi)部表現(xiàn)（即基因型基因型）是某種基因組合，它決定了個體的形狀的外部表）是某種基因組合，它決定了個體的形狀的外部表 現(xiàn)，如黑頭發(fā)的特征是由染色體中控制這一特征

41、的某種基因組合決定的。因此，現(xiàn)，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。因此， 在一開始需要實現(xiàn)從在一開始需要實現(xiàn)從表現(xiàn)型表現(xiàn)型到基因型的到基因型的映射映射即即編碼編碼工作。由于仿照基因編碼的工工作。由于仿照基因編碼的工 作很復(fù)雜，我們往往進行簡化，如作很復(fù)雜，我們往往進行簡化，如二進制二進制編碼，初代種群產(chǎn)生之后，按照適者生編碼，初代種群產(chǎn)生之后，按照適者生 存和優(yōu)勝劣汰的原理，逐代（存和優(yōu)勝劣汰的原理，逐代（generationgeneration）演化產(chǎn)生出越來越好的近似解，在每）演化產(chǎn)生出越來越好的近似解，在每 一代，根據(jù)問題域中個體的一代，根據(jù)問題域中個體的適應(yīng)度

42、適應(yīng)度（fitnessfitness）大小選擇（）大小選擇（selectionselection）個體，并）個體，并 借助于自然遺傳學(xué)的遺傳借助于自然遺傳學(xué)的遺傳算子算子（genetic operatorsgenetic operators）進行組合交叉（）進行組合交叉（crossovercrossover） 和變異（和變異（mutationmutation），產(chǎn)生出代表新的解集的種群。這個過程將導(dǎo)致種群像自然），產(chǎn)生出代表新的解集的種群。這個過程將導(dǎo)致種群像自然 進化一樣的后生代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個體經(jīng)過進化一樣的后生代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個體經(jīng)

43、過解碼解碼 （decodingdecoding），可以作為問題近似最優(yōu)解。），可以作為問題近似最優(yōu)解。 272021/6/7 蟻群算法蟻群算法(Ant Colony)(Ant Colony) 各個各個螞蟻螞蟻在沒有事先告訴他們食物在什么地方的前在沒有事先告訴他們食物在什么地方的前 提下開始尋找食物。當(dāng)一只找到食物以后，它會向提下開始尋找食物。當(dāng)一只找到食物以后，它會向 環(huán)境釋放環(huán)境釋放一種揮發(fā)性分泌物一種揮發(fā)性分泌物pheromone (pheromone (稱為稱為信息素信息素, , 該該物質(zhì)物質(zhì)隨著時間的推移會逐漸揮發(fā)消失，隨著時間的推移會逐漸揮發(fā)消失，信息素信息素濃濃 度的大小表征路徑的遠近度的大小表征路徑的遠近) )來實現(xiàn)的，吸引其他的螞來實現(xiàn)的，吸引其他的螞 蟻過來，這樣越來越多的螞蟻會找到食物。有些螞蟻過來，這樣越來越多的螞蟻會找到食物。有些螞 蟻并沒有像其它螞蟻一樣總重復(fù)同樣的路，他們會蟻并沒有像其它螞蟻一樣總重復(fù)同樣的路，他們會 另辟蹊徑，如果另開辟的道路比原來的其他道路更另辟蹊徑，如果另開辟的道路比原來的其他道路更 短，那么，漸漸地，更多的螞蟻被吸引到這條較短短，那么，漸漸地，更多的螞蟻被吸引到這條較短 的路上來。最后，經(jīng)過一段時間運行，可能會出現(xiàn)的路上來。最后，經(jīng)過一段時間運行，可能會出現(xiàn) 一