車輛優(yōu)化調(diào)度問(wèn)題的算法之啟發(fā)式算法

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

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

，令

（表示

的鄰域）。第二步：當(dāng)P≠0時(shí)，或滿足其他停止運(yùn)算準(zhǔn)則時(shí)，轉(zhuǎn)至第四步；否則，從

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

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

的目標(biāo)值

小于

的目標(biāo)值

，則令

，

，轉(zhuǎn)第二步。否則

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

中

選取

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

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

的鄰域

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

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

中選一個(gè)評(píng)價(jià)值最好的解

，令

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