車輛優(yōu)化調度問題的算法之啟發(fā)式算法

物流人工智能技術技能培訓項目三人工智能算法在配送環(huán)節(jié)應用任務十二車輛優(yōu)化調度問題的算法之啟發(fā)式算法目錄CONTENTS構造啟發(fā)式算法PART1改進啟發(fā)式算法PART2【教學目標】過程與方法：知識與技能：1.掌握構造啟發(fā)式算法；2.掌握改進啟發(fā)式算法。在學習動畫視頻的過程中，理解其基本工作原理，了解其實際應用價值。情感、態(tài)度與價值觀：1.提升對人工智能的認識，發(fā)展辯證思維，客觀認識人工智能技術對社會的影響，培養(yǎng)正確的科學技術應用觀。2.堅定擁護中國共產黨領導和我國社會主義制度。通常精確算法的計算量隨著車輛優(yōu)化調度問題規(guī)模的增大呈指數增長，所以它不適合求解車輛優(yōu)化調度問題，并且車輛路徑規(guī)劃是具有NP難的組合優(yōu)化問題，很難找到精確解，因此尋找近似解是必要的。一、構造啟發(fā)式算法用啟發(fā)式算法解決問題常?？梢缘玫綕M意解，通過迭代過程進行實現(xiàn)時，需要一套解的搜索規(guī)則和評價標準。啟發(fā)式方法能同時滿足詳細描繪問題和求解的需要，比精確優(yōu)化方法更為實用，缺點是難以確定什么時候好的啟發(fā)式解已被求得。一、構造啟發(fā)式算法首先確定目標函數，也就是建立運輸總成本函數，目的是使總成本取得最小值；然后求解，先求初始解，從以后的求解過程中，依次得到接近最小成本的解?；舅悸芬弧嬙靻l(fā)式算法該算法的每一步，把當前的線路構形跟另外的構形，進行比較并加以改進，或者根據某個判別函數產生最大限度的節(jié)約構形，或以最小代價把一個不在當前構形上的需求對象插入進來，最后得到一個較好的構形。一、構造啟發(fā)式算法某配送中心P向10個客戶A~J配送貨物，其道路網如圖1所示。圖中連線上的數字表示兩節(jié)點間的距離（km），各客戶點旁括號內的數字表示該客戶的需求量（t）。配送中心有載重量為2t和4t的兩種車輛可供使用，但車輛一次巡回的行駛距離不能超過30km。試制定最優(yōu)的配送線路。一、構造啟發(fā)式算法1.節(jié)約里程法第一步：根據給出的相鄰節(jié)點間的距離，求出配送中心至各客戶點、各客戶點間的最短距離。如表所示。第二步：根據最短距離表，計算節(jié)約值Sij，計算結果有正有負，當節(jié)約值Sij為負數時，無實際意義，故取值為零。一、構造啟發(fā)式算法第三步：將所有的節(jié)約值Sij按從大到小的順序排列，如表所示。第四步：按照節(jié)約值Sij的大小順序，以及車輛載重量和行駛距離的限制，逐步構造配送線路。一、構造啟發(fā)式算法對每一個客戶分別單獨派車送貨，如圖所示。形成了10條初始配送線路。（1）初始線路一、構造啟發(fā)式算法按照節(jié)約值Sij的大小順序，連接A~B、A~J。如圖所示（2）線路合并一、構造啟發(fā)式算法如圖4所示，此時該線路的總需求量為3.6t，線路長度為27km。按照Sij的大小順序，現(xiàn)在應考慮是否將C~D連接到配送線路I。但若將C~D連接到該線路，線長度將超過30km，不可行。（3）連接B~C，形成配送線路I一、構造啟發(fā)式算法（4）然后，連接D~E，開始構造配送線路Ⅱ。重復該步驟，直到沒有可合并的線路為止。（5）得到的最終解，如下圖5所示。共構造出3條配送線路?？偟男旭偫锍虨?0km。一、構造啟發(fā)式算法掃描算法是用于求解車輛數目不限制的車輛路徑規(guī)劃的一種啟發(fā)式算法。掃描算法本質上是將距離近的客戶歸并到一個子路徑中。一、構造啟發(fā)式算法2.掃描算法以起始點（配送中心）作為極坐標的原點，并以圖中的任意一客戶點和極點（配送中心）的連線定義為角度零，建立極坐標系，然后對所有的客戶所在的位置進行極坐標系的變換，把所有客戶點全部都轉換為極坐標系下的點。建立極坐標系1.一、構造啟發(fā)式算法從最小角度的兩個客戶開始，建立一個組，按逆時針或者順時針方向，將客戶逐個加入到組中，直到客戶需求總量超過了車輛負載限制時，結束該條線路。分組2.一、構造啟發(fā)式算法建立一個新的組，繼續(xù)按照逆時針或者順時針方向，將客戶繼續(xù)逐個加入到組中，生成新的線路，直到所有的客戶點都被分到某個組為止。重復（2）的過程3.一、構造啟發(fā)式算法對各個分組內的客戶群就是一個個單獨的TSP問題（其中，各組的起點都是極點）求解TSP，得到優(yōu)化線路。線路優(yōu)化4.一、構造啟發(fā)式算法例如某配送中心P向客戶點配送貨物。圖中各客戶點旁括號內的數字表示該客戶的需求量（t）。配送中心有載重量為2t的車輛可供使用。試制定其最優(yōu)的配送線路。一、構造啟發(fā)式算法顯然，根據掃描算法，可以把客戶點分為不同的兩組，分別為：（A,B,C,D），（F,G,H，I）。分組完成后，即可對組內的客戶點進行路徑優(yōu)化。如圖7所示。一、構造啟發(fā)式算法這種方法首先構造一條或幾條很長的線路（通常不可行），它包括了所有需求對象，然后再把這些很長的線路劃分成一些短而可行的線路。具體進行時，一般是先解一個經過所有點的旅行商問題，形成一條線路，然后再根據一定的約束對它進行劃分。先排程后分組一、構造啟發(fā)式算法3.兩階段算法這種方法先把節(jié)點和（或）弧的需求進行分組或劃群，然后對每一組設計一條經濟的線路。先分組后排程掃描算法，其目的在于形成需求點的徑向區(qū)域，從車場發(fā)出的射線“掃過”這個區(qū)域，使不超過車輛容量的需求點組成一個區(qū)域，一個區(qū)域就是一個組，當形成一系列這樣的組后，再對每一組中的各點安排線路。一、構造啟發(fā)式算法都屬于改進啟發(fā)式算法，都是從初始解開始，通過對當前的解進行反復的局部擾亂，以達到較好的解。啟發(fā)式搜索算法智能算法啟發(fā)式的并行算法二、改進啟發(fā)式算法啟發(fā)式搜索算法包括：爬山法禁忌搜索算法模擬退火算法1.2.3.二、改進啟發(fā)式算法（1）爬山算法也稱局部搜索算法，是一種基于鄰域搜索技術的、沿著有可能改進解的質量的方向進行單方向搜索的搜索算法。該方法的局部搜索能力很強，是一種常用的尋找局部最優(yōu)解的方法。二、改進啟發(fā)式算法以目標函數最小為例，使用爬山算法求解組合優(yōu)化問題的步驟如下。第一步：選定一個初始解

；記錄當前最優(yōu)解

，令

（表示

的鄰域）。第二步：當P≠0時，或滿足其他停止運算準則時，轉至第四步；否則，從

中按某規(guī)則選一個解

，轉第三步。二、改進啟發(fā)式算法第四步：輸出計算結果，停止。第三步：若

的目標值

小于

的目標值

，則令

，

，轉第二步。否則

，轉第二步。二、改進啟發(fā)式算法在爬山算法中，第一步的初始解可以采用隨機方法產生，也可用一些經驗方法得到，還可采用其他方法得到初始解。在第二步中，其他停止運算準則是指除P≠0以外的其他準則，這些準則一般取決于人們對算法的計算時間、計算結果的要求。第二步中在

中

選取

的規(guī)則可以采用隨機選取的規(guī)則?？梢娕郎剿惴◤慕饪臻g中的一個點出發(fā)，通過不斷迭代，最終可達到一個局部最優(yōu)點。算法停止時得到解的質量依賴于算法初始解的選取、鄰域選點的規(guī)則和算法終止條件等。二、改進啟發(fā)式算法（2）禁忌搜索算法禁忌搜索算法是解決組合優(yōu)化問題的另一種優(yōu)化方法。其算法是采用禁忌技術，即用一個禁忌表中的信息不再或有選擇地搜索這些點，以此來跳出局部最優(yōu)點。該算法可以克服爬山算法全局搜索能力不強的弱點。二、改進啟發(fā)式算法在禁忌搜索算法中，首先按照隨機方法產生一個初始解作為當前解，然后在當前解的鄰域中搜索若干個解，取其中的最好解作為新的當前解。為了避免陷入局部最優(yōu)解，這種優(yōu)化方法允許一定的下山操作，下山操作是指使解的質量變差。另外，為避免對已搜索過的局部最優(yōu)解的重復，禁忌搜索算法使用禁忌表記錄已搜索的局部最優(yōu)解的信息，這可在一定程度上避開局部極值點，從而開辟新的搜索區(qū)域。二、改進啟發(fā)式算法實現(xiàn)步驟：第一步：選定一個初始解

，令禁忌表H≠0。第二步：若滿足終止規(guī)則，轉第四步；否則，在

的鄰域

中選出滿足禁忌要求的候選集

，轉第三步。二、改進啟發(fā)式算法實現(xiàn)步驟：第四步：輸出計算結果，停止。第三步：在

中選一個評價值最好的解

，令

，更新禁忌表H，轉第二步。二、改進啟發(fā)式算法禁忌搜索算法的第二步中，的鄰域中滿足禁忌要求的解包括兩類，一些是那些沒有被禁忌的解，一些是可以被解除禁忌的解。二、改進啟發(fā)式算法（3）模擬退火算法也是局部搜索算法的擴展，它與局部搜索算法的不同之處在于它以一定的概率選擇鄰域中目標函數值差的狀態(tài)。二、改進啟發(fā)式算法退火是一種物理過程，一種金屬物體在加熱到一定溫度后，它的所有分子在其狀態(tài)空間中自由運動。在溫度最低時，分子重新以一定的結構排列。當溫度相當高時，每個狀態(tài)的概率基本相同，都接近平均值。當溫度趨于0時，分子停留在最低能量狀態(tài)的概率趨于1。二、改進啟發(fā)式算法模擬退火算法是一種基于上述退火原理建立的隨機搜索算法。組合優(yōu)化問題與金屬物體的退火過程可進行如下類比：組合優(yōu)化問題的解類似于金屬物體的狀態(tài)組合優(yōu)化問題的最優(yōu)解類似于金屬物體能量最低的狀態(tài)組合優(yōu)化問題的費用函數類似于金屬物體的能量。二、改進啟發(fā)式算法實現(xiàn)步驟：第一步：初始化初始溫度T（T需要充分大），初始解狀態(tài)S（S是算法迭代的起點），每個T值的迭代次數L；第二步：對k=1，……，L做第三步；二、改進啟發(fā)式算法實現(xiàn)步驟：第三步：產生新解S'；計算增量，其