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

2、關目前有關VRPVRP的研究已經可以表示（如圖的研究已經可以表示（如圖1 1）為：給）為：給定一個或多個中心點（中心倉庫，定一個或多個中心點（中心倉庫，central central depotdepot）、一個車輛集合和一個顧客集合，車輛和）、一個車輛集合和一個顧客集合，車輛和顧客各有自己的屬性，每輛車都有容量，所裝載貨顧客各有自己的屬性，每輛車都有容量，所裝載貨物不能超過它的容量。起初車輛都在中心點，顧客物不能超過它的容量。起初車輛都在中心點，顧客在空間任意分布，車把貨物從車庫運送到每一個顧在空間任意分布，車把貨物從車庫運送到每一個顧客（或從每個顧客處把貨物運到車庫），要求滿足客（或從每個

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

4、ing Problem，CVRP)CVRP)。(2) (2) 優先約束：引出優先約束車輛路徑問題優先約束：引出優先約束車輛路徑問題(VehicleRouting Problem with precedence (VehicleRouting Problem with precedence ConstraintsConstraints，VRPPC)VRPPC)。(3) (3) 車型約束：引出多車型車輛路徑問題車型約束：引出多車型車輛路徑問題(Mixed/Heterogeneous Fleet Vehicle Routing (Mixed/Heterogeneous Fleet Vehicle R

5、outing ProblemProblem，MFVRP/ HFVRP)MFVRP/ HFVRP)。(4) (4) 時間窗約束：包括硬時間窗時間窗約束：包括硬時間窗(Hard Time (Hard Time windows)windows)和軟時間窗和軟時間窗(Soft Time windows) (Soft Time windows) 約束。約束。引出帶時間窗引出帶時間窗( (包括硬時間窗和軟時間窗包括硬時間窗和軟時間窗) )的車輛路的車輛路徑問題徑問題(Vehicle Routing Problem withTime (Vehicle Routing Problem withTime win

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

7、ith Stochastic DemandDemand，VRPSD)VRPSD)。(7) (7) 開路：引出開路車輛路徑問題開路：引出開路車輛路徑問題(Open Vehicle (Open Vehicle RoutingProblem)RoutingProblem)。(8) (8) 多運輸中心：引出多運輸中心的車輛路徑問題多運輸中心：引出多運輸中心的車輛路徑問題(Multi-Depot Vehicle Routing Problem)(Multi-Depot Vehicle Routing Problem)。(9) (9) 回程運輸：引出帶回程運輸的車輛路徑問題回程運輸：引出帶回程運輸的車輛路

8、徑問題(VehicleRouting Problem with Backhauls)(VehicleRouting Problem with Backhauls)。(10) (10) 最后時間期限：引出帶最后時間期限的車輛路徑最后時間期限：引出帶最后時間期限的車輛路徑問題問題(Vehicle Routing Problem with Time (Vehicle Routing Problem with Time Deadlines)Deadlines)。(11) (11) 車速隨時間變化：引出車速隨時間變化的車輛路車速隨時間變化：引出車速隨時間變化的車輛路徑問題徑問題(Time-Depende

9、nt Vehicle Routing Problem)(Time-Dependent Vehicle Routing Problem)。3、 CVRP CVRP問題描述及其數學模型問題描述及其數學模型CVRPCVRP的描述：設某中心車場有的描述：設某中心車場有k k輛車，每輛配送車輛車，每輛配送車的最大載重量的最大載重量Q Q，需要對，需要對n n個客戶個客戶( (節點節點) )進行運輸配進行運輸配送，每輛車從中心車場出發給若干個客戶送貨，最送，每輛車從中心車場出發給若干個客戶送貨，最終回到中心車場，客戶點終回到中心車場，客戶點i i的貨物需求量是的貨物需求量是q qi i ( (i i=1,

10、2,=1,2,n n) )，且，且q qi i Q Q。記配送中心編號為。記配送中心編號為0 0，各，各客戶編號為客戶編號為i i( (i i=1,2 ,=1,2 ,n n) )， c cijij表示客戶表示客戶i i到客到客戶戶j j的距離。求滿足車輛數最小，車輛行駛總路程的距離。求滿足車輛數最小，車輛行駛總路程最短的運送方案。最短的運送方案。定義變量如下定義變量如下: :建立此問題的數學模型建立此問題的數學模型：4、車輛路徑問題算法綜述目前，求解車輛路徑問題的方法非常多，基本上可以目前，求解車輛路徑問題的方法非常多，基本上可以分為精確算法和啟發式算法分為精確算法和啟發式算法2 2大類。大類

11、。精確算法是指可求出其最優解的算法，主要運用線性精確算法是指可求出其最優解的算法，主要運用線性規劃、整數規劃、非線性規劃等數學規劃技術來描述規劃、整數規劃、非線性規劃等數學規劃技術來描述物流系統的數量關系，以便求得最優決策。（運籌學物流系統的數量關系，以便求得最優決策。（運籌學領域）領域）精確算法主要有精確算法主要有：分枝定界法分枝定界法(Branch and Bound Approach)(Branch and Bound Approach)割平面法割平面法(Cutting Planes Approach)(Cutting Planes Approach)網絡流算法網絡流算法(Network

12、 Flow Approach)(Network Flow Approach) 動態規劃算法動態規劃算法(Dynamic Programming Approach)(Dynamic Programming Approach)分枝定界法分枝定界法(Branch and Bound Approach)(Branch and Bound Approach)以求相應的線性規劃問題的最優解為出發點，如果得以求相應的線性規劃問題的最優解為出發點，如果得到的解不符合整數條件，就將原規劃問題分成幾支，到的解不符合整數條件，就將原規劃問題分成幾支，每支增加了約束條件，即縮小了可行解區域，可行解每支增加了約束條件，

13、即縮小了可行解區域，可行解范圍也隨之縮小了，因而整數規劃的最優值不會優于范圍也隨之縮小了，因而整數規劃的最優值不會優于相應的線性規劃最優值。相應的線性規劃最優值。“定界定界”是指為目標函數定上下界，以便自動舍去那是指為目標函數定上下界，以便自動舍去那些最優值較差的子問題，提高計算效率。當整數規劃些最優值較差的子問題，提高計算效率。當整數規劃問題的最優目標函數值的上下界相等時，該整數規劃問題的最優目標函數值的上下界相等時，該整數規劃最優解已求出。最優解已求出。首先，不考慮變量的整數約束，求解松弛問題首先，不考慮變量的整數約束，求解松弛問題線性規劃的最優解。如果線性規劃的最優解恰好是線性規劃的最優

14、解。如果線性規劃的最優解恰好是整數解，則這個解就是整數規劃的最優解。整數解，則這個解就是整數規劃的最優解。如果線性規劃的最優解中至少有一個變量不是如果線性規劃的最優解中至少有一個變量不是整數，把線性規劃的可行域切割成兩部分，分別求整數，把線性規劃的可行域切割成兩部分，分別求解兩個線性規劃的最優解。解兩個線性規劃的最優解。如果這兩個線性規劃的最優解還不是整數解，如果這兩個線性規劃的最優解還不是整數解，分別把每一個可行域再進行分割。這個過程，叫做分別把每一個可行域再進行分割。這個過程，叫做“分支分支”。分支過程得到的整數解中，目標函數值最優的分支過程得到的整數解中，目標函數值最優的一個叫做整數規劃

15、目標函數值的一個叫做整數規劃目標函數值的“界界”。分支過程。分支過程中非整數的線性規劃的最優解，如果目標函數值劣中非整數的線性規劃的最優解，如果目標函數值劣于或等于這個于或等于這個“界界”，就停止繼續分支。這個過程，就停止繼續分支。這個過程，叫做叫做“定界定界”。割平面法割平面法(Cutting Planes Approach)(Cutting Planes Approach)用割平面法求解整數規劃的基本思路是：先不考慮整用割平面法求解整數規劃的基本思路是：先不考慮整數約束條件，求松弛問題的最優解，如果獲得整數最數約束條件，求松弛問題的最優解，如果獲得整數最優解，即為所求，運算停止。如果所得到

16、最優解不滿優解，即為所求，運算停止。如果所得到最優解不滿足整數約束條件，則在此非整數解的基礎上增加新的足整數約束條件，則在此非整數解的基礎上增加新的約束條件重新求解。這個新增加的約束條件的作用就約束條件重新求解。這個新增加的約束條件的作用就是去切割相應松弛問題的可行域，即割去松弛問題的是去切割相應松弛問題的可行域，即割去松弛問題的部分非整數解部分非整數解( (包括原已得到的非整數最優解包括原已得到的非整數最優解) )。而把。而把所有的整數解都保留下來，故稱新增加的約束條件為所有的整數解都保留下來，故稱新增加的約束條件為割平面。當經過多次切割后，就會使被切割后保留下割平面。當經過多次切割后，就會

17、使被切割后保留下來的可行域上有一個坐標均為整數的頂點，它恰好就來的可行域上有一個坐標均為整數的頂點，它恰好就是所求問題的整數最優解。即切割后所對應的松弛問是所求問題的整數最優解。即切割后所對應的松弛問題，與原整數規劃問題具有相同的最優解。題，與原整數規劃問題具有相同的最優解。網絡流算法網絡流算法(Network Flow Approach)(Network Flow Approach)圖論圖論中的一種理論與方法，研究網絡上的一類最優化中的一種理論與方法，研究網絡上的一類最優化問題問題 。19551955年年 ，T.E.T.E.哈里斯哈里斯在研究鐵路最大通量時在研究鐵路最大通量時首先提出在一個給

18、定的網絡上尋求兩點間最大運輸量首先提出在一個給定的網絡上尋求兩點間最大運輸量的問題。的問題。19561956年，年，L.R. L.R. 福特和福特和 D.R. D.R. 富爾克森等人給富爾克森等人給出了解決這類問題的算法，從而建立了出了解決這類問題的算法，從而建立了網絡流理論網絡流理論。所謂網絡或容量網絡指的是一個連通的賦權有向圖所謂網絡或容量網絡指的是一個連通的賦權有向圖 D= D= （V V、E E、C C） ， 其中其中V V 是該圖的頂點集，是該圖的頂點集，E E是有向邊是有向邊( (即弧即弧) )集，集，C C是弧上的容量。此外頂點集中包括一個起是弧上的容量。此外頂點集中包括一個起點

19、和一個終點。網絡上的流就是由起點流向終點的可點和一個終點。網絡上的流就是由起點流向終點的可行流，這是定義在網絡上的非負函數，它一方面受到行流，這是定義在網絡上的非負函數，它一方面受到容量的限制，另一方面除去起點和終點以外，在所有容量的限制，另一方面除去起點和終點以外，在所有中途點要求保持流入量和流出量是平衡的。中途點要求保持流入量和流出量是平衡的。動態規劃算法動態規劃算法(Dynamic Programming Approach)(Dynamic Programming Approach)動態規劃是一種求解多階段決策問題的系統技術。動態規劃是一種求解多階段決策問題的系統技術。如果一類活動過程可

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

21、于一個策略可以確定活動的效果，這個效果可以用數量來確定。策略不同，效果也果，這個效果可以用數量來確定。策略不同，效果也不同，多階段決策問題，就是要在可以選擇的那些策不同，多階段決策問題，就是要在可以選擇的那些策略中間，選取一個最優策略，使在預定的標準下達到略中間，選取一個最優策略，使在預定的標準下達到最好的效果。最好的效果。總的說來，精確性算法基于嚴格的數學手段，在可總的說來，精確性算法基于嚴格的數學手段，在可以求解的情況下，其解通常要優于人工智能算法。以求解的情況下，其解通常要優于人工智能算法。但由于引入嚴格的數學方法，計算量一般隨問題規但由于引入嚴格的數學方法，計算量一般隨問題規模的增大呈

22、指數增長，因而無法避開指數爆炸問題，模的增大呈指數增長，因而無法避開指數爆炸問題，從而使該類算法只能有效求解中小規模的確定性從而使該類算法只能有效求解中小規模的確定性VRPVRP，并且通常這些算法都是針對某一特定問題設，并且通常這些算法都是針對某一特定問題設計的計的, ,適用能力較差適用能力較差, ,因此在實際中其應用范圍很有因此在實際中其應用范圍很有限。限。啟發式算法啟發式算法由于車輛路徑優化問題是由于車輛路徑優化問題是NPNP難題，高效的精確算法難題，高效的精確算法存在的可能性不大存在的可能性不大( (除非除非P=NP)P=NP)，所以尋找近似算法，所以尋找近似算法是必要和現實的，為此專家

23、主要把精力花在構造高是必要和現實的，為此專家主要把精力花在構造高質量的啟發式算法上。啟發式算法是在狀態空間中質量的啟發式算法上。啟發式算法是在狀態空間中的改進搜索算法，它對每一個搜索的位置進行評價，的改進搜索算法，它對每一個搜索的位置進行評價，得到最好的位置，再從這個位置進行搜索直到目標。得到最好的位置，再從這個位置進行搜索直到目標。在啟發式搜索中，對位置的估價十分重要，采用不在啟發式搜索中，對位置的估價十分重要，采用不同的估價可以有不同的效果。目前已提出的啟發式同的估價可以有不同的效果。目前已提出的啟發式算法較多，分類也相當多，主要的啟發式算法有以算法較多，分類也相當多，主要的啟發式算法有以

24、下幾類：構造算法、兩階段法、智能化算法。下幾類：構造算法、兩階段法、智能化算法。構造算法構造算法(Constructive Algorithm)(Constructive Algorithm)這類方法的基本思想是：根據一些準則，每一次將一這類方法的基本思想是：根據一些準則，每一次將一個不在線路上的點增加進線路，直到所有點都被安排個不在線路上的點增加進線路，直到所有點都被安排進線路為止。該類算法的每一步把當前的線路構形進線路為止。該類算法的每一步把當前的線路構形( (很很可能是不可行的可能是不可行的) )跟另外的構形跟另外的構形( (也可能是不可行的也可能是不可行的) )進進行比較并加以改進，后

25、者或是根據某個判別函數行比較并加以改進，后者或是根據某個判別函數( (例如例如總費用總費用) )會產生最大限度的節約的構形，或是以最小代會產生最大限度的節約的構形，或是以最小代價把一個不在當前構形上的需求對象插入進來的構形，價把一個不在當前構形上的需求對象插入進來的構形，最后得到一個較好的可行構形。這類算法中中最著名最后得到一個較好的可行構形。這類算法中中最著名的是的是ClarkeClarke和和WrightWright在在19641964年提出的節約算法。年提出的節約算法。構造算法最早提出來解決旅行商問題，這些方法一般構造算法最早提出來解決旅行商問題，這些方法一般速度快，也很靈活，但這類方法

26、有時找到的解離最優速度快，也很靈活，但這類方法有時找到的解離最優解差得很遠。解差得很遠。兩階段法兩階段法(Two-phase Algorithm)(Two-phase Algorithm)學者們通過對構造算法的研究，認為由構造算法求學者們通過對構造算法的研究，認為由構造算法求得的解可以被進一步改進，為此提出了兩階段法。得的解可以被進一步改進，為此提出了兩階段法。第一階段得到一可行解，第二階段通過對點的調整，第一階段得到一可行解，第二階段通過對點的調整，在始終保持解可行的情況下，力圖向最優目標靠近，在始終保持解可行的情況下，力圖向最優目標靠近，每一步都產生另一個可行解以代替原來的解，使目每一步都

27、產生另一個可行解以代替原來的解，使目標函數值得以改進，一直繼續到不能再改進目標函標函數值得以改進，一直繼續到不能再改進目標函數值為止。數值為止。一般第一階段常用構造算法，在第二階段常用的改一般第一階段常用構造算法，在第二階段常用的改進技術有進技術有2-opt(Lin,1965)2-opt(Lin,1965)，3-opt(Lin 3-opt(Lin Kernighan,1973)Kernighan,1973)和和Or-opt (Or,1976)Or-opt (Or,1976)交換法，這交換法，這是一種在解的鄰域中搜索，對初始解進行某種程度是一種在解的鄰域中搜索，對初始解進行某種程度優化的算法，以

28、改進初始解。優化的算法，以改進初始解。在兩階段法求解過程中，常常采用交互式優化技術，在兩階段法求解過程中，常常采用交互式優化技術，把人的主觀能動作用結合到問題的求解過程中，其把人的主觀能動作用結合到問題的求解過程中，其主要思想是：有經驗的決策者具有對結果和參數的主要思想是：有經驗的決策者具有對結果和參數的某種判斷能力，并且根據知識直感，把主觀的估計某種判斷能力，并且根據知識直感，把主觀的估計加到優化模型中去。這樣做通常會增加模型最終實加到優化模型中去。這樣做通常會增加模型最終實現并被采用的可能性。現并被采用的可能性。智能化算法智能化算法(Intelligent Algorithm)(Intel

29、ligent Algorithm)這類算法以啟發式準則來代替精確算法中的決策準這類算法以啟發式準則來代替精確算法中的決策準則，以縮小解搜索的空間。則，以縮小解搜索的空間。總體來看，盡管啟發式算法能夠在有限的時間內求總體來看，盡管啟發式算法能夠在有限的時間內求出質量較高的解，但由于其搜索解空間的能力有所出質量較高的解，但由于其搜索解空間的能力有所限制，因此經常無法達到預期的要求。限制，因此經常無法達到預期的要求。2020世紀世紀9090年年代以來，由于人工智能方法在解決組合優化問題中代以來，由于人工智能方法在解決組合優化問題中的強大功能，不少學者開始將人工智能引入車輛路的強大功能，不少學者開始將

30、人工智能引入車輛路線問題的求解中，并構造了大量的基于人工智能的線問題的求解中，并構造了大量的基于人工智能的啟發式算法啟發式算法( (智能化啟發式算法智能化啟發式算法) )。智能化啟發式算法從本質上講仍然屬于啟發式算法，智能化啟發式算法從本質上講仍然屬于啟發式算法，其基本思想是從一初始解開始，通過對當前的解進其基本思想是從一初始解開始，通過對當前的解進行反復地局部擾亂行反復地局部擾亂(Perturbations)(Perturbations)以達到較好的以達到較好的解。目前，最常見的智能化啟發式算法包括模擬退解。目前，最常見的智能化啟發式算法包括模擬退火算法火算法(Simulated Annea

31、ling)(Simulated Annealing)、禁忌搜索算法、禁忌搜索算法(Tabu Search)(Tabu Search)、遺傳算法、遺傳算法(Genetic Algorithm)(Genetic Algorithm)、蟻群算法蟻群算法(Ant Colony)(Ant Colony)和神經網絡和神經網絡(Neutral (Neutral Networks)Networks)、粒子群算法（、粒子群算法（Particle Swarm Particle Swarm Optimization,PSOOptimization,PSO）方法等。）方法等。模擬退火算法模擬退火算法(Simulate

32、d Annealing)(Simulated Annealing)模擬退火算法來源于固體退火原理，將固體加溫至充分高，模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升溫升變為無序狀，變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態，最后在常溫時達到基態，內能減為最小。根據平衡態，最后在常溫時達到基態，內能減為最小。根據MetropolisMetropolis準則，準則，粒子粒子在溫度在溫度T T時趨于平衡的時趨于平衡的概率概率為為e(-e

33、(-EE/(kT)/(kT)，其中，其中E E為溫度為溫度T T時的內能，時的內能，EE為其改變量，為其改變量，k k為為BoltzmannBoltzmann常數。用常數。用固體固體退火模擬組合優化問題，將內能退火模擬組合優化問題，將內能E E模模擬為擬為目標函數目標函數值值f f，溫度，溫度T T演化成控制參數演化成控制參數t t，即得到解組合，即得到解組合優化問題的模擬退火算法：由初始解優化問題的模擬退火算法：由初始解i i和控制參數初值和控制參數初值t t開始，開始，對當前解重復對當前解重復“產生新解產生新解計算目標函數差計算目標函數差接受或舍棄接受或舍棄”的迭代，并逐步衰減的迭代，并逐

34、步衰減t t值，算法終止時的當前解即為所得近值，算法終止時的當前解即為所得近似似最優解最優解，這是基于，這是基于蒙特卡羅蒙特卡羅迭代求解法的一種啟發式迭代求解法的一種啟發式隨機隨機搜索搜索過程。退火過程由冷卻進度表過程。退火過程由冷卻進度表(Cooling Schedule)(Cooling Schedule)控制，控制，包括控制參數的初值包括控制參數的初值t t及其衰減因子及其衰減因子tt、每個、每個t t值時的迭代值時的迭代次數次數L L和停止條件和停止條件S S。禁忌搜索算法禁忌搜索算法(Tabu Search)(Tabu Search)禁忌算法是一種隨機搜索算法，它從一個初始可行解出發

35、，選擇一系列禁忌算法是一種隨機搜索算法，它從一個初始可行解出發，選擇一系列的特定搜索方向（移動）作為試探，選擇實現讓特定的目標函數值變化的特定搜索方向（移動）作為試探，選擇實現讓特定的目標函數值變化最多的移動。為了避免陷入局部最優解，最多的移動。為了避免陷入局部最優解，TSTS搜索中采用了一種靈活的搜索中采用了一種靈活的“記憶記憶”技術，對已經進行的優化過程進行記錄和選擇，指導下一步的技術，對已經進行的優化過程進行記錄和選擇，指導下一步的搜索方向，這就是搜索方向，這就是TabuTabu表的建立。表的建立。1 1、在搜索中，構造一個短期循環記憶表、在搜索中，構造一個短期循環記憶表- -禁忌表，禁

36、忌表中存放剛剛進禁忌表，禁忌表中存放剛剛進行過的行過的 |T|T|（T T稱為禁忌表）個鄰居的移動，這種移動即解的簡單變化。稱為禁忌表）個鄰居的移動，這種移動即解的簡單變化。2 2、禁忌表中的移動稱為禁忌移動。對于進入禁忌表中的移動，、禁忌表中的移動稱為禁忌移動。對于進入禁忌表中的移動， 在以后在以后的的 |T| |T| 次循環內是禁止的，以避免回到原來的解，從而避免陷入循環。次循環內是禁止的，以避免回到原來的解，從而避免陷入循環。|T| |T| 次循環后禁忌解除。次循環后禁忌解除。3 3、禁忌表是一個循環表，在搜索過程中被循環的修改，使禁忌表始終保、禁忌表是一個循環表，在搜索過程中被循環的修

37、改，使禁忌表始終保持持 |T| |T| 個移動。個移動。4 4、即使引入了禁忌表，禁忌搜索仍可能出現循環。因此，必須給定停止、即使引入了禁忌表，禁忌搜索仍可能出現循環。因此，必須給定停止準則以避免出現循環。當迭代內所發現的最好解無法改進或無法離開它準則以避免出現循環。當迭代內所發現的最好解無法改進或無法離開它時，算法停止。時，算法停止。遺傳算法遺傳算法(Genetic Algorithm)(Genetic Algorithm)遺傳算法是模擬遺傳算法是模擬達爾文達爾文生物進化生物進化論的自然選擇和論的自然選擇和遺傳學遺傳學機理的生物進化過機理的生物進化過程的計算程的計算模型模型，是一種通過模擬自

38、然進化過程搜索，是一種通過模擬自然進化過程搜索最優解最優解的方法。遺傳算法的方法。遺傳算法是從代表問題可能潛在的解集的一個是從代表問題可能潛在的解集的一個種群種群（populationpopulation）開始的，而一個種）開始的，而一個種群則由經過群則由經過基因基因（genegene）編碼的一定數目的個體）編碼的一定數目的個體(individual)(individual)組成。每個個組成。每個個體實際上是體實際上是染色體染色體(chromosome)(chromosome)帶有特征的實體。染色體作為帶有特征的實體。染色體作為遺傳物質遺傳物質的主的主要載體，即多個基因的要載體，即多個基因的集

39、合集合，其內部表現（即，其內部表現（即基因型基因型）是某種基因組合，它）是某種基因組合，它決定了個體的形狀的外部表現，如黑頭發的特征是由染色體中控制這一特征決定了個體的形狀的外部表現，如黑頭發的特征是由染色體中控制這一特征的某種基因組合決定的。因此，在一開始需要實現從的某種基因組合決定的。因此，在一開始需要實現從表現型表現型到基因型的到基因型的映射映射即即編碼編碼工作。由于仿照基因編碼的工作很復雜，我們往往進行簡化，如工作。由于仿照基因編碼的工作很復雜，我們往往進行簡化，如二進二進制制編碼，初代種群產生之后，按照適者生存和優勝劣汰的原理，逐代編碼，初代種群產生之后，按照適者生存和優勝劣汰的原理

40、，逐代（generationgeneration）演化產生出越來越好的近似解，在每一代，根據問題域中個）演化產生出越來越好的近似解，在每一代，根據問題域中個體的體的適應度適應度（fitnessfitness）大小選擇（）大小選擇（selectionselection）個體，并借助于自然遺傳學）個體，并借助于自然遺傳學的遺傳的遺傳算子算子（genetic operatorsgenetic operators）進行組合交叉（）進行組合交叉（crossovercrossover）和變異）和變異（mutationmutation），產生出代表新的解集的種群。這個過程將導致種群像自然進），產生出代表新的

41、解集的種群。這個過程將導致種群像自然進化一樣的后生代種群比前代更加適應于環境，末代種群中的最優個體經過化一樣的后生代種群比前代更加適應于環境，末代種群中的最優個體經過解解碼碼（decodingdecoding），可以作為問題近似最優解。），可以作為問題近似最優解。蟻群算法蟻群算法(Ant Colony)(Ant Colony)各個各個螞蟻螞蟻在沒有事先告訴他們食物在什么地方的前在沒有事先告訴他們食物在什么地方的前提下開始尋找食物。當一只找到食物以后，它會向提下開始尋找食物。當一只找到食物以后，它會向環境釋放環境釋放一種揮發性分泌物一種揮發性分泌物pheromone (pheromone (稱為稱為信息信息素素, ,該該物質物質隨著時間的推移會逐漸揮發消失，隨著時間的推移會逐漸揮發消失，信息信息素素濃度的大小表征路徑的遠近濃度的大小表征路徑的遠近) )來實現的，吸引其來實現的，吸引其他的螞蟻過來，這樣越來越多的螞蟻會找到食物。他的螞蟻過來，這樣越來越多的螞蟻會找到食物。有些螞蟻并沒有像其它螞蟻一樣總重復同樣的路，有些螞蟻并沒有像其它螞蟻一樣總重復同樣的路，他們會另辟蹊徑，如果另開辟的道路比原來的其他他們會另辟蹊徑，如果另開辟的道路比原來的其他道路更短，那么，漸漸地，更多的螞蟻被吸引到這道路更短，那么，漸漸地，更多的螞蟻被吸引到這條較短的路上來。最后，經過一段時間運行，可能條較