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

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

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

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

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

5、能力， 本文把遺傳算 法和模擬退火策略相結(jié)合以解決多配送中心車輛調(diào)度問題 5。 2基丁優(yōu)化遺傳算法的的多配送中心車輛路徑算法 2 . 1 適應(yīng)函數(shù)的退火拉伸 5 在遺傳算法運(yùn)算前期，由丁染色體的差異較大，輪盤賭選擇容易使遺傳算法進(jìn) 入局部最優(yōu)；進(jìn)化后期，染色體的個(gè)體差異性較小，輪盤賭選擇容易使遺傳算法 6 進(jìn)入終止?fàn)顟B(tài)。故變換適應(yīng)度函數(shù)為： 廣f 史林-時(shí)?力 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)生下一代新個(gè)體，由丁遺傳算法在運(yùn)算過程中容 易陷入局部最優(yōu)，交義操作通過產(chǎn)生的新個(gè)體和上一代個(gè)體的差異性較大， 使遺 傳算法具有較強(qiáng)的全局搜索能力。本文采用如下的交義操作方式： 二1-。0 洛Xg 礦二探必exJ (2) 4AT VL rhjn ,4 */J*二人 H I I / - W 出 5 nsi二犬 / 久、 在上式中， AB和分別為上一代個(gè)體A和B產(chǎn)生的新一代個(gè)體，a和6分別 是0, r上的隨機(jī)數(shù)，交義系數(shù)r的取值范圍為0 , 1。L和R代表尋優(yōu)參數(shù)的 范圍，如進(jìn)行交義操作后超過了尋優(yōu)參數(shù)范圍，那么重新進(jìn)行交義操作。 2變異操作 變異操作采用如下形式 1 (0)=0

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

8、最大遺傳代數(shù)Tmax，退火初始溫度T0, 溫度下降系數(shù)精,最小新解接受次數(shù)Nmin,最大內(nèi)循環(huán)次數(shù)Cmax,隨機(jī)產(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)、時(shí)間J 懲罰系數(shù)c和d的值。 (2) 計(jì)算種群中各個(gè)個(gè)體的適應(yīng)度值，記錄最優(yōu)個(gè)體。對(duì)種群中的每一個(gè)染色 體Gi ( 1 , 2 ,，n),求得對(duì)應(yīng)的目標(biāo)函數(shù)值f 1 ;假設(shè)染色體對(duì)應(yīng)的是不可 行解，那么屆丁其目標(biāo)函數(shù)一個(gè)很大的整數(shù)。

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

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