基于優(yōu)化遺傳算法的多配送中心車輛路徑研究-科技創(chuàng)新論文

1、 基于優(yōu)化遺傳算法的多配送中 心車輛路徑研究-科技創(chuàng)新論文2 作者: 日期:3 基于優(yōu)化遺傳算法的多配送中 L、車輛路徑研究 -科技創(chuàng)新論 文 基丁優(yōu)化遺傳算法的多配送中心車輛路徑研究 黃玉文 荷澤學院計算機與信息工程系，山東 荷澤274015 【摘 要】將遺傳算法與模擬退火算法相結(jié)合，提出了一種基丁優(yōu)化遺傳算法 的多配送中心車輛路徑調(diào)度方法，該調(diào)度方法不僅具有自適應(yīng)遺傳算法的強大全 局搜索能力，也具有模擬退火算法的強大局部搜索能力。通過對雜交率和變異率 進行自適應(yīng)調(diào)整、對接受算子進行退火處理 ，有效地增強了全局尋優(yōu)能力，通過 對適應(yīng)值函數(shù)退火拉伸，加速了尋優(yōu)過程。 關(guān)鍵詞 遺傳算法；模擬退火

2、；多配送中心；車輛路徑 基金工程：山東省高等學校科技方案工程J13LN53 ;荷澤學院科學院科 研基金XY14KJ08 。 作者簡介：黃玉文1978-,男，山東單縣人，碩士，講師，主要研究方向： 網(wǎng)絡(luò)與信息平安、數(shù)據(jù)挖掘、算法分析。 0引言 當前,隨著電子商務(wù)的快速興起，物流業(yè)在市場經(jīng)濟中占有越來越重要的地位， 引起國家的高度重視和越來越多的企業(yè)的關(guān)注。 正確和高效的安排多配送中心車 輛路徑調(diào)度有利丁提高配送速度，有利丁企業(yè)節(jié)約本錢，提高物流配送企業(yè)的經(jīng) 濟效率和顧客效勞水平。近年來，物流配送在國家的經(jīng)濟建設(shè)中扮演越來越重要 的作用，如何提高物流配送效率和降低物流本錢成為一個熱門研究課題 1。

3、多 配送中心配送能夠滿足更廣闊的地理范圍內(nèi)的顧客效勞需求， 配送車輛可以從多4 個配送中心出發(fā)去完成運輸任務(wù)，到達提高車輛利用率、減少總的運輸距離、節(jié) 約運輸本錢，更快滿足顧客需要的目的。車輛路徑問題( Vehicle Routing Problem )在多配送中心物流調(diào)度中占有一個非常重要的環(huán)節(jié)， 這個問題的有效 解決，可以提高物流調(diào)度的科學化水平，降低運輸本錢，提高經(jīng)濟效益 2。同 時物流配送車輛調(diào)度問題作為一個 NP難題，隨著客戶數(shù)量的增加，可選的配送 路徑方案數(shù)量將以指數(shù)速度急劇增長3。因此，用啟發(fā)式算法求解該問題就成 為人們研究的一個重要方向，本文提出了一種基丁 優(yōu)化遺傳算法的多配送

4、中心 車輛路徑方案。 1優(yōu)化遺傳算法思想 遺傳算法不依賴初始解，可以對問題參數(shù)的編碼組進行計算，并且算法具有強 大的搜索能力，故很多研究者把遺傳算法應(yīng)用到解決多配送中心的調(diào)度問題中。 遺傳算法強調(diào)的是兩代之間的進化關(guān)系， 其交義有可能錯過最好解，因而局部搜 索能力較弱，所以即使是在最優(yōu)解附近，而要到達這個最優(yōu)解，卻花費較大的代 價。遺傳算法在最優(yōu)路徑搜索過程中容易陷入局部最優(yōu)， 搜索效率比擬低下，而 模擬退火算法容易脫離局部最優(yōu)4。因此，考慮將模擬退火算法的思想引入遺 傳算法，有效地緩解了遺傳算法的選擇壓力。 退火遺傳算法是集合了遺傳算法和 模擬退火算法各自的優(yōu)點，具有較好的全局搜索和局部搜索

5、能力， 本文把遺傳算 法和模擬退火策略相結(jié)合以解決多配送中心車輛調(diào)度問題 5。 2基丁優(yōu)化遺傳算法的的多配送中心車輛路徑算法 2 . 1 適應(yīng)函數(shù)的退火拉伸 5 在遺傳算法運算前期，由丁染色體的差異較大，輪盤賭選擇容易使遺傳算法進 入局部最優(yōu)；進化后期，染色體的個體差異性較小，輪盤賭選擇容易使遺傳算法 6 進入終止狀態(tài)。故變換適應(yīng)度函數(shù)為： 廣f 史林-時?力 1 / ， 1 式中：f X為適應(yīng)度函數(shù)變換后的值，f max X適應(yīng)度函數(shù)的最大 值，T代表退火溫度，TO代表初始溫度，g代表遺傳代數(shù)，R為略小丁 1的 正數(shù)，本文取0. 99。 2. 2 交義和變異的自適應(yīng)性 1交義操作 遺傳算法通

6、過交義操作能夠產(chǎn)生下一代新個體，由丁遺傳算法在運算過程中容 易陷入局部最優(yōu)，交義操作通過產(chǎn)生的新個體和上一代個體的差異性較大， 使遺 傳算法具有較強的全局搜索能力。本文采用如下的交義操作方式： 二1-。0 洛Xg 礦二探必exJ (2) 4AT VL rhjn ,4 */J*二人 H I I / - W 出 5 nsi二犬 / 久、 在上式中， AB和分別為上一代個體A和B產(chǎn)生的新一代個體，a和6分別 是0, r上的隨機數(shù)，交義系數(shù)r的取值范圍為0 , 1。L和R代表尋優(yōu)參數(shù)的 范圍，如進行交義操作后超過了尋優(yōu)參數(shù)范圍，那么重新進行交義操作。 2變異操作 變異操作采用如下形式 1 (0)=0

7、C-k普I 1 ) = 1 (4) 上式中，C為父個體， C為變異操作產(chǎn)生的新個體，隨機數(shù)的范圍為0,1, 變異系數(shù)k的取值范圍為0,1, 隨機函數(shù)U0,1的值為0或1 2 . 3 接受算子的退火處理 雜交和變異運算后的個體中的最優(yōu)解被保存，這故遺傳算法容易陷入局部最優(yōu) 解，出現(xiàn)早熟現(xiàn)象。本文提出以 Metropolis 準那么保存?zhèn)€體，其保存概率為 式中:fold為雜交(變異)前的父代個體適應(yīng)值，fnew為雜交(變異)后的 子代個體適應(yīng)值，T為退火溫度。 2 . 4 算法的實現(xiàn) 將自適應(yīng)遺傳退火算法應(yīng)用到多配送中心車輛路徑優(yōu)化中， 具體的實現(xiàn)步驟如 ： (1) 設(shè)置初始參數(shù)，包括種群規(guī)模M,

8、最大遺傳代數(shù)Tmax，退火初始溫度T0, 溫度下降系數(shù)精,最小新解接受次數(shù)Nmin,最大內(nèi)循環(huán)次數(shù)Cmax,隨機產(chǎn)生初始 種群 Gi (1,2,，n)。設(shè)定 H、M、qi (i = l,2，M+H)、Q k (k=l, 2，K)、Dk (k=l, 2，K)、dij (i, j=l, 2， u u I( / - A | | M, M+ 1 , M+ 2 ,，M+H)、時間J 懲罰系數(shù)c和d的值。 (2) 計算種群中各個個體的適應(yīng)度值，記錄最優(yōu)個體。對種群中的每一個染色 體Gi ( 1 , 2 ,，n),求得對應(yīng)的目標函數(shù)值f 1 ;假設(shè)染色體對應(yīng)的是不可 行解，那么屆丁其目標函數(shù)一個很大的整數(shù)。

9、并采用如下方法進行適應(yīng)度拉伸 / 公式中f 為拉伸后的適應(yīng)度值。 (3) 選擇操作8 采用輪盤選擇策略進行個體選擇，進行染色體的復制，具體過程如下：對各個染 I F二九 色體u k ,計算適應(yīng)值f k ;計算種群中n個染色體適應(yīng)值的和 ，對各 I & . _ J I 染色體u k,計算選擇概率川婦 2對各個染色體u k，計算 適應(yīng)值 。在區(qū)間0, 1 內(nèi)產(chǎn)生一個隨機數(shù)r,假設(shè)rv q 1 ,那么選擇第一個染色體r V u 1 ;否那么選擇第k個染色體u k (k=l, 2, n),使得q k 1 V r V q k成立。將當前群體中適應(yīng)度最高的個體結(jié)構(gòu)完整的 復制到下一代群體中。 (4

10、) 交義操作。按照式(2)、式(3)進行自適應(yīng)交義操作。 (5) 執(zhí)行Metropolis 準那么，對交義后的算子進行接收退火處理。 (6) 變異操作。對個體的每個參數(shù)進行自適應(yīng)變異操作。 (7) 執(zhí)行Metropolis 準那么，對變異后的算子進行接收退火處理。 (8 )刪除子代種群中的任意一個個體，并替換成步驟 (2)記錄的最優(yōu)個體。 (9)如果當前遺傳代數(shù)T ?芻Tm a x，那么按進行降溫,T=T+1,并返回步驟(2); 否那么結(jié)束整個優(yōu)化過程。 3 結(jié)論 本章對雜交率和變異率的個體進行自適應(yīng)的接受， 有利丁提高遺傳算法的收斂 性。對適應(yīng)值函數(shù)的退火拉伸，能夠使遺傳算法加快收斂速度，能夠更好的尋找 多配送中心車輛路徑。 參考文獻 1 葛顯龍，王旭，鄧蕾.基丁聯(lián)合配送的開放式動態(tài)車輛路徑問題及算法研究 J.管理工程學報，2021,3:44-48. 10 2 丁濱，靳鵬歡,楊忠振.兩階段啟發(fā)式算法求解帶時間窗的多中心車輛路徑 問題J.系統(tǒng)工程理論與實踐,2021,8:32-37. 3 孫國華.帶時間窗的開放式滿載車輛路徑問題