城市快遞配送車輛路徑規(guī)劃

項目一人工智能算法在配送環(huán)節(jié)應(yīng)用《物流人工智能技術(shù)》任務(wù)四城市快遞配送車輛路徑規(guī)劃2目錄/CONTENTS01混合遺傳—模擬退火算法設(shè)計02混合遺傳－模擬退火算法性能仿真34【知識目標(biāo)】1.了解混合遺傳－模擬退火算法具體步驟?！厩楦心繕?biāo)】1.具有工匠精神、服務(wù)意識、環(huán)保意識、質(zhì)量意識、安全意識；2.培養(yǎng)獨(dú)立獲取信息和自學(xué)能力；3.堅定擁護(hù)中國共產(chǎn)黨領(lǐng)導(dǎo)和我國社會主義制度。【教學(xué)目標(biāo)】將模擬退火算法內(nèi)嵌入遺傳算法中，緩解遺傳算法的選擇壓力并針對模型特點(diǎn)對混合后算法進(jìn)行修改，算法流程圖為圖５-４，混合遺傳－模擬退火算法具體步驟如下：設(shè)置當(dāng)前解集為空且模擬退火溫度初始值為：Ｔ＿０，進(jìn)化迭代計數(shù)器k=0，迭代次數(shù)最大值為：Ｔ；用實(shí)數(shù)編碼對路徑規(guī)劃問題的可行解進(jìn)行編碼，構(gòu)造初始種群；利用適應(yīng)度函數(shù)對種群中的個體進(jìn)行評價；利用遺傳算法對初始群體進(jìn)行選擇交叉變異操作后得到優(yōu)化后的新種群；對上述染色體組成的種群進(jìn)行退火操作；對上一步驟的種群重新進(jìn)行選擇、交叉、變異等遺傳操作；重復(fù)執(zhí)行Ｓｔｅｐ４到Ｓｔｅｐ６直到符合停止條件遺傳算法的停止條件，一般選為迭代進(jìn)化一定次數(shù)后停止。對用混合算法得到的最優(yōu)解進(jìn)行解碼操作得到問題解。一、混合遺傳—模擬退火算法設(shè)計圖５-４算法流程混合遺傳－模擬退火算法步驟圖NYNY開始初始化種群，評價種群、確定初始溫度執(zhí)行遺傳算法操作（選擇、交叉、變異）對種群中個體進(jìn)行模擬退火搜索由模擬退火產(chǎn)生新狀態(tài)并以概率接受新個體模擬退火操作是否穩(wěn)定對新種群進(jìn)行評價算法收斂條件是否滿足退溫操作輸出最優(yōu)結(jié)果一、混合遺傳—模擬退火算法設(shè)計遺傳算法的編碼方式有很多中，大概可以分為二進(jìn)制編碼、實(shí)數(shù)編碼、矩陣編碼、樹型編碼和量子比特編碼等。本文研究的是車輛路徑規(guī)劃問題，為了避免二進(jìn)制編碼產(chǎn)生無效解而降低遺傳算法的搜索效率，本文采用直觀的自然數(shù)編碼方法，如圖５－５。假設(shè)客戶數(shù)量為L，１為配送中心，配送車輛數(shù)目為k,此時染色體長度可以表示為n＋k＋１，表示為（１，s1，s2，...si,0,sj,...sl,１）其中是自然數(shù)，表示客戶點(diǎn)，１表示配送中心，兩個１之間的數(shù)表示配送車輛在一次配送路徑中，按時間先后順序服務(wù)的客戶點(diǎn)。遺傳算法是在解的群體上進(jìn)行的，因此具有魯棒性、全局性和并行性，因此群體的設(shè)定對遺傳算法的運(yùn)行性能具有很大的影響。群體規(guī)模越大，群體多樣性越高，算法陷入局部解的危險越小，但計算量也隨之顯著增加。染色體1752193841610...11122233321231231234配送車輛服務(wù)順序圖5-5染色體編碼模擬圖1.染色體編碼方案及群體設(shè)定一、混合遺傳—模擬退火算法設(shè)計適應(yīng)度函數(shù)是評價個體優(yōu)劣的重要指標(biāo)，可以區(qū)分群體中個體優(yōu)劣并作出取舍。遺傳算法的適應(yīng)度函數(shù)可由目標(biāo)函數(shù)轉(zhuǎn)換而來。本文研宄的路徑規(guī)劃為多目標(biāo)問題，求解中會出現(xiàn)Pareto解，増加計算時間，因此為了減少計算時間和降低目標(biāo)函數(shù)求解復(fù)雜度簡化目標(biāo)結(jié)構(gòu)，針對本文模型，利用線性加權(quán)將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題Ｚ。轉(zhuǎn)換步驟如下：（１）由于客戶滿意度為［０，１］之間的數(shù)值，配送成本與客戶滿意度量級相差較大，無法直接進(jìn)行衡量，因此需要對客戶滿意度Z1快遞配送成本Z2進(jìn)行標(biāo)準(zhǔn)化操作即將目標(biāo)函數(shù)值與該目標(biāo)最大值進(jìn)行除法運(yùn)算，將兩者量級進(jìn)行統(tǒng)一；（２）將歸一化后的客戶滿意度和配送成本進(jìn)行線性化加權(quán)，分別賦予權(quán)重系數(shù)，權(quán)重系數(shù)可以由企業(yè)對運(yùn)營目的重要性進(jìn)行分配。則歸一化后的目標(biāo)函數(shù)可以表示為在此基礎(chǔ)上構(gòu)造適應(yīng)度函數(shù)，即：公式中的Ａ為染色體Zi對應(yīng)的歸一化后的目標(biāo)函數(shù)值，和為客戶滿意度和配送成本的權(quán)重，可以根據(jù)企業(yè)運(yùn)營目標(biāo)進(jìn)行設(shè)定，也可以設(shè)定為隨機(jī)產(chǎn)生。5-12.適應(yīng)度函數(shù)一、混合遺傳—模擬退火算法設(shè)計（１）選擇結(jié)合模型綜合分析，在輪盤賭選擇算子的基礎(chǔ)上引入最優(yōu)保存策略，防止適應(yīng)度高的個體因為隨機(jī)的原因不被選中，避免適應(yīng)度高的個體被后續(xù)的遺傳操作改變，使群體像最優(yōu)方向進(jìn)化，提高收斂能力。具體選擇操作為：１）將每一代具有最大適應(yīng)度值的個體直接進(jìn)行保存；２）其余個體計算適應(yīng)度f（ｉ＝１，２，…，Ｍ），Ｍ為群體大??；３）計算每個個體被遺傳到下一代群體中的概率；４）計算出每個個體的累計概率；５）在［０，１］之間產(chǎn)生一個均勻分布的隨機(jī)數(shù)ｒ；若ｒ＜ｑ［ｌ］，則選擇個體１進(jìn)入子代種群，若q[k-1]<r?q[k]、選擇個體進(jìn)入子代種群；６）重復(fù)步驟（５），（６），直至子代種群選擇完畢生成新一代種群，并將適應(yīng)度最低的個體用父代適應(yīng)度最高的染色體進(jìn)行置換。3.遺傳操作一、混合遺傳—模擬退火算法設(shè)計（2）交叉在遺傳算法中，交叉過程是模仿自然界基因重組的過程，通過交叉操作可以將優(yōu)良的基因遺傳給下一代，并且通過交換生成新個體，提高多樣性。為了使交叉操作具有更高的效率，在交叉過程中考慮到相似染色體交叉得到的新染色體變化率小的問題，本文在交叉之前加入了相似度提前比對環(huán)節(jié)，其中相似度的定義為：其中、表示兩個待操作個體的第i位，n為染色體長度。設(shè)定相似度閾值Θ,Θ取值一般為染色體長度的１／４-１／２，若ｄ大于Θ則可以進(jìn)行交叉操作，反之則重新選擇個體。在相似度比對后，具體的交叉操作可以描述如下：假設(shè)存在兩個父代個體為“１，２，３，４，５，６，７，８，９”和“５，４，６，９，２，１，７，８，３”，首先確定基因交叉變異的起始位置，對兩個位置中間的數(shù)據(jù)執(zhí)行交叉操作，在客戶數(shù)目范圍內(nèi)隨機(jī)選取整數(shù)，作為變異操作始末節(jié)點(diǎn)。其次是沖突檢測，根據(jù)交換的兩組基因建立一個映射關(guān)系，若在交叉之后在一條染色體中存在相同的基因，則將有沖突的基因根據(jù)映射關(guān)系進(jìn)行消除，直到形成的新一對子代基因無沖突。交叉操作的過程圖如圖５－10。映射關(guān)系123456789546921783Step1:確定交叉段Step2:中間段交叉126921789543456783Step3:沖突檢測69219

4

34562

5

1

6

3Step4:最終染色體356921784293456781圖5-10交叉操作示意圖一、混合遺傳—模擬退火算法設(shè)計（３）變異變異操作是將個體染色體中的某些基因座上的基因值以一定的概率用該基因座上其他的等位基因進(jìn)行替換形成新的個體。結(jié)合本文編碼，選擇逆轉(zhuǎn)變異算子，具體操作過程分為兩個步驟，一是種群以變異概率Ｐｍ進(jìn)行變異，產(chǎn)生變異點(diǎn)；二是將變異點(diǎn)之基因進(jìn)行逆轉(zhuǎn)操作，產(chǎn)生新的染色體。例如在種群中的一個父代染色體的基因為“５４６９２１７８３”，變異基因節(jié)點(diǎn)為６和８，變異操作過程需要將兩個節(jié)點(diǎn)位置進(jìn)行交換，變異操作的示意圖為圖５－７。變異節(jié)點(diǎn)為6和8546921783Step1：548921763Step1：圖5-11變異操作示意圖一、混合遺傳—模擬退火算法設(shè)計通過前面的步驟實(shí)現(xiàn)了對群體中個體的選擇、交叉和變異，生成一個全新的群體。遺傳算法是一個逐步去除差值的過程，但是一味的優(yōu)化會導(dǎo)致多樣性的降低，陷入局部最優(yōu)，因此本文按照模擬退火中的Ｍｅｔｒｏｐｏｌｉｓ接受準(zhǔn)則％，對新群體中每個個體進(jìn)行退火操作，即逐步減小控制參數(shù)Ｔ的值，決定進(jìn)入下一代的個體，實(shí)現(xiàn)新舊群體的替換。根據(jù)Ｍｅｔｒｏｐｏｌｉｓ接受準(zhǔn)則入如式（５－２），定義接受性能較差后代個體的概率為：其中ｒ為當(dāng)前溫度，為子代，為父代。（5-2）4.群體優(yōu)化設(shè)計一、混合遺傳—模擬退火算法設(shè)計遺傳算法交叉算子與變異算子的作用效果受到交叉率和變異率的控制，要想得到遺傳算法的最優(yōu)性能必須確定這些參數(shù)的最優(yōu)設(shè)置。自適應(yīng)交叉概率，對選中的兩個染色體進(jìn)行基因交換，取值如式（５－３）由自適應(yīng)變異概率，采用均勻變異法，對染色體的變異點(diǎn)用符合編碼要求的隨機(jī)自然數(shù)以變異概率來替換原有基因位置上的基因，提升局部搜索能力。的取值如式（５－４）其中（t）為兩個相比較染色體中適應(yīng)度較大的值，為變異染色體的適應(yīng)度值。,為小于１的常數(shù)，,符合的大小關(guān)系。由公式（５－３）（５－４）確定的交叉概率取值區(qū)間為（0.31，0.92），變異概率取值區(qū)間為（0.01，0.1）。

（5-3）

（5-4）5.關(guān)鍵參數(shù)一、混合遺傳—模擬退火算法設(shè)計為了驗證本文算法的有效性和可行性，選取標(biāo)準(zhǔn)遺傳算法、模擬退火算法與本文算法進(jìn)行對比分析，將迭代終止次數(shù)設(shè)為１０００次，每種算法運(yùn)行５０次，統(tǒng)計各種算法最優(yōu)解結(jié)果及迭代次數(shù)。本文算法、標(biāo)準(zhǔn)遺傳算法、模擬退火算法的收斂性能對比如圖５－８。二、混合遺傳－模擬退火算法性能仿真本文算法與標(biāo)準(zhǔn)遺傳算法和模擬退火算法的求解結(jié)果如表５－２所示。通過圖５－８和表５－２可知，我們可以從收斂速度、尋優(yōu)結(jié)果兩個方面對三種算法進(jìn)行定性定量的對比分析。１）收斂速度從圖５－８可以看出三種算法在收斂速度上具有一定的差異性，具體到迭代次數(shù)來看，本文的算法在６１２己經(jīng)進(jìn)入收斂的穩(wěn)定階段，遺傳算法從４８９代開始收斂穩(wěn)定，模擬退火算法則從６５０代附近開始進(jìn)入收斂穩(wěn)定。這說明本文設(shè)計的方法在收斂速度上優(yōu)于模擬退火算法。２）尋優(yōu)結(jié)果綜合分析圖５－８和表５－２的數(shù)據(jù)，在總成本方面，本文算法計算結(jié)果為2090.5，標(biāo)準(zhǔn)遺傳算法的計算結(jié)果為2218.2，模擬退火算法的計算結(jié)果為2137.6，本文算法可以尋得模型的最優(yōu)解，且本文算法可以跳出遺傳算法的局部最優(yōu)解。通過分析可知，本文的混合算法具有良好的收斂速度和尋優(yōu)能力，可以跳出局部最優(yōu)解，有利于求得路徑規(guī)劃模型的最優(yōu)解。算法名稱迭代穩(wěn)定行駛里程最優(yōu)成本時間(s)遺傳算法4891720.822218.29.2模擬退火6501611.762137.613.6本文算法61214