基于改進(jìn)遺傳算法的物流路徑優(yōu)化方法

（湖南科技大學(xué) 知識(shí)處理與網(wǎng)絡(luò)化制造實(shí)驗(yàn)室，湖南 湘潭 411201）

1 引言

車(chē)輛路徑優(yōu)化是物流配載的中心環(huán)節(jié)，其本質(zhì)是旅行商問(wèn)題（TSP-Travelling salesman problem）[1]：給定一系列城市和每對(duì)城市之間的距離，求解訪問(wèn)每一座城市一次并回到起始城市的最短回路。TSP問(wèn)題，是一種經(jīng)典的從組合問(wèn)題的可行解集中求出最優(yōu)解的問(wèn)題且是一種容易描述卻難以處理的NP難題[2]。隨著城鎮(zhèn)數(shù)目n的增加，其路徑可能存在數(shù)目成指數(shù)型模式增長(zhǎng)，利用現(xiàn)有條件很難求出滿足條件的最優(yōu)解[3]。

目前，針對(duì)物流配送中心環(huán)節(jié)路徑問(wèn)題求解主要采用優(yōu)化方法，構(gòu)造法是率先被提出用來(lái)求解物流配送路徑問(wèn)題的，構(gòu)造法求解速度高效，但是求得的解與最優(yōu)解偏差太遠(yuǎn)[4]，因此構(gòu)造法主要用于求得初始路徑，Clarke、Wright等提出以最小代價(jià)把不在當(dāng)前路徑上的點(diǎn)添加進(jìn)來(lái)[5-7]，形成一條相對(duì)不錯(cuò)的初始路徑，最后再采用改進(jìn)的算法對(duì)初始路徑進(jìn)行處理，盡可能提高解的質(zhì)量。劉荷花等[8]針對(duì)傳統(tǒng)遺傳算法求解TSP問(wèn)題時(shí)解的質(zhì)量不高的問(wèn)題,提出了一種能夠判定遺傳算法截止代數(shù)的改進(jìn)遺傳算法,提高了算法的收斂性，但容易陷入局部最優(yōu)。因此，本文提出一種改進(jìn)的遺傳算法對(duì)物流配送車(chē)輛路徑進(jìn)行優(yōu)化，提高解的質(zhì)量。

2 遺傳算法優(yōu)化物流配送路徑

遺傳算法是一種經(jīng)典的啟發(fā)式算法，也是一種全局搜索算法[9-11]。其主要的思想是根據(jù)自然界的生存法則“優(yōu)勝劣汰”，自然界生物的發(fā)展都是從簡(jiǎn)單到復(fù)雜、從低等到高等、從不適應(yīng)自然界到不斷適應(yīng)自然界的慢慢進(jìn)化的過(guò)程[12]。在這個(gè)過(guò)程中對(duì)環(huán)境適應(yīng)能力強(qiáng)的得以生存，并將其優(yōu)良基因遺傳到下一代，不同個(gè)體之間的交配產(chǎn)生的后代是父代的一個(gè)基因組合，在這個(gè)過(guò)程中可能伴隨著基因的突變和變異，產(chǎn)生出更好的后代。將遺傳算法應(yīng)用于求解物流配送中心環(huán)節(jié)車(chē)輛路徑優(yōu)化問(wèn)題，其詳細(xì)步驟描述如下：

步驟1：計(jì)算距離矩陣D=dij(n×n)；

步驟2：隨機(jī)產(chǎn)生N個(gè)染色體TN={T1，T2，...,Tn}；

步驟3：調(diào)用評(píng)價(jià)函數(shù)計(jì)算染色體集合TN中的各染色體適應(yīng)度的值；

步驟4：對(duì)集合TN首先執(zhí)行選擇運(yùn)算，再執(zhí)行交叉運(yùn)算，最后執(zhí)行變異運(yùn)算；

步驟5：判斷循環(huán)次數(shù)是否滿足指定代數(shù)，若滿足，繼續(xù)第6步，輸出最優(yōu)解；否則，跳轉(zhuǎn)到第3步；

步驟6：對(duì)遺傳算法迭代生成的最后解調(diào)用解碼函數(shù)進(jìn)行解碼操作，即可得到每輛車(chē)的派車(chē)路線和訪問(wèn)順序。

遺傳算法優(yōu)化物流配載路徑算法流程如圖1所示。

3 改進(jìn)遺傳算法優(yōu)化物流配送路徑

遺傳算法是傳統(tǒng)經(jīng)典算法，具有全局搜索能力、很好的收斂性和魯棒性，但其搜索全局解的能力比較弱，容易陷入局部最優(yōu)，為了避免陷入局部最優(yōu)，所以針對(duì)遺傳算法做出一些改變。

圖1 遺傳算法優(yōu)化物流配載路徑算法流程圖

3.1 在求解過(guò)程中用較高質(zhì)量的解代替較低質(zhì)量的解

（1）采用動(dòng)態(tài)交叉策略來(lái)解決遺傳算法中較早收斂的問(wèn)題，在求解路徑的過(guò)程中，交換兩個(gè)待送貨客戶(hù)的順序，將距離最小的組合順序保存下來(lái)，其交叉變異公式如下：

式（1）中pc2表示種群中配送路徑最小的個(gè)體的交叉率，f為要交叉的每組中配送路徑最小的個(gè)體，fmax為種群中配送路徑最大的值，favg為種群配送路徑平均值。

（2）采用動(dòng)態(tài)變異策略可以解決算法中較早收斂的問(wèn)題，變異策略同交叉策略相同，在求解路徑的過(guò)程中，交換兩個(gè)待派送客戶(hù)之間的途徑順序，將路徑最小的組合順序保存下來(lái)，其變異公式如下：

式（2）中pn2表示種群中配送路徑最小的個(gè)體的變異率，f為要交叉的每組中配送路徑最小的個(gè)體，fmax為種群配送路徑最大的值，favg為種群配送路徑平均值。

3.2 利用爬山算法對(duì)得到的解進(jìn)行優(yōu)化改進(jìn)

爬山算法是一種局部擇優(yōu)的查找算法，該算法每次從當(dāng)前的解開(kāi)始，然后與其鄰域內(nèi)的解進(jìn)行比較，選擇最優(yōu)的解作為當(dāng)前解。動(dòng)態(tài)交叉策略和動(dòng)態(tài)變異策略主要是在求解的過(guò)程中選擇較優(yōu)解，爬山算法主要是對(duì)生成的路線作進(jìn)一步的優(yōu)化改進(jìn)，交換線路中兩個(gè)待派車(chē)客戶(hù)的訪問(wèn)順序，如果交換兩個(gè)待派車(chē)客戶(hù)順序后路徑變短，就交換這兩個(gè)待派車(chē)客戶(hù)的派送順序，反之，則按照原來(lái)線路的客戶(hù)訪問(wèn)順序不變。其流程示意圖如圖2所示。

圖2 爬山算法改進(jìn)線路的流程

3.3 改進(jìn)后的遺傳算法步驟

步驟1：隨機(jī)產(chǎn)生初始種群，用自然數(shù)串進(jìn)行編碼，染色體中每個(gè)基因位代表待派送區(qū)域內(nèi)的每個(gè)待派車(chē)的客戶(hù)，每個(gè)個(gè)體對(duì)應(yīng)待派送區(qū)域內(nèi)全部待派車(chē)客戶(hù)的一個(gè)全排列，用所配送車(chē)輛行駛的總距離作為適應(yīng)度值；

步驟2：對(duì)種群中的個(gè)體進(jìn)行譯碼，按照染色體上基因順序計(jì)算每條染色體上車(chē)輛行駛的總路徑；

步驟3：進(jìn)行選擇操作，用輪盤(pán)賭注方法選擇父代最優(yōu)個(gè)體遺傳至子代；

步驟4：根據(jù)動(dòng)態(tài)交叉策略和動(dòng)態(tài)變異策略對(duì)個(gè)體分別執(zhí)行交叉操作和變異操作，在求解路徑的過(guò)程中求出較優(yōu)解；

步驟5：用局部爬山法對(duì)種群中的單個(gè)個(gè)體配送路徑進(jìn)行改進(jìn)；

步驟6：通過(guò)環(huán)境選擇生成下一代新種群；

步驟7：如果達(dá)到預(yù)先設(shè)定的進(jìn)化代數(shù)或停止條件，算法結(jié)束并輸出路徑；否則，跳轉(zhuǎn)到第2步。

具體操作流程如圖3所示。

圖3 改進(jìn)遺傳算法優(yōu)化物流配載路徑算法流程

4 實(shí)驗(yàn)分析

本算法是根據(jù)步步高云通物流配送公司的實(shí)際需求提出，為了驗(yàn)證改進(jìn)遺傳算法的正確性和有效性，隨機(jī)從步步高云通物流2017年11月份訂單數(shù)據(jù)中選擇3 000條訂單進(jìn)行測(cè)試，每一個(gè)訂單是一個(gè)待派車(chē)門(mén)店。實(shí)驗(yàn)采用JAVA編程語(yǔ)言，對(duì)傳統(tǒng)遺傳算法和改進(jìn)后的遺傳算法進(jìn)行編碼實(shí)現(xiàn)，分別求解物流配送路徑。通過(guò)對(duì)兩種算法求得最優(yōu)物流配送路徑的行駛里程和耗費(fèi)時(shí)間進(jìn)行對(duì)比分析。

利用遺傳算法進(jìn)行物流配送路徑優(yōu)化求解，需要預(yù)先設(shè)定種群規(guī)模N的大小，種群規(guī)模N影響算法的執(zhí)行效率；交叉概率Pc的大小影響著求解較優(yōu)路徑時(shí)交換途徑帶派車(chē)客戶(hù)的操作的頻率，同樣變異概率Pm影響著交換途徑待派車(chē)客戶(hù)順序操作的頻率。根據(jù)步步高訂單數(shù)據(jù)得知，一個(gè)區(qū)域一天的待派客戶(hù)量在500左右，同時(shí)考慮到種群多樣性和收斂時(shí)間，種群規(guī)模N設(shè)定為10 000，兼顧考慮算法執(zhí)行的效率和保持種群的多樣性，變異概率Pm設(shè)置為0.05，交叉概率Pc設(shè)置為0.6，終止條件最優(yōu)個(gè)體持續(xù)的代數(shù)M=150。設(shè)定比較指標(biāo)里程節(jié)約百分比、標(biāo)準(zhǔn)差、路徑較優(yōu)百分比。程，L2：改進(jìn)遺傳算法平均里程）。標(biāo)準(zhǔn)差里程的平均值，N：總實(shí)驗(yàn)次數(shù)，i:第i次實(shí)驗(yàn)）。路徑較優(yōu)百分比=N1/(N1+N2)（N1：傳統(tǒng)遺傳算法出現(xiàn)的路徑較優(yōu)次數(shù)，N2：改進(jìn)遺傳算法出現(xiàn)的路徑較優(yōu)次數(shù)）。

表1 實(shí)驗(yàn)結(jié)果對(duì)比分析

從表1可知，在N次實(shí)驗(yàn)中，通過(guò)路徑較優(yōu)百分比可以看出，改進(jìn)遺傳算法明顯優(yōu)于傳統(tǒng)遺傳算法，特別是在里程穩(wěn)定性方面，改進(jìn)遺傳算法求得的路徑里程幾乎沒(méi)有任何的波動(dòng)；里程節(jié)約方面，傳統(tǒng)遺傳算法比改進(jìn)的遺傳算法平均節(jié)約10.15%，也就是說(shuō)每100km大約節(jié)約10.15km。

5 結(jié)束語(yǔ)

物流配送的中心環(huán)節(jié)-路徑優(yōu)化問(wèn)題是現(xiàn)階段國(guó)內(nèi)外專(zhuān)家、學(xué)者正在研究的熱點(diǎn)問(wèn)題，各種優(yōu)化算法層出不窮。本文先對(duì)傳統(tǒng)遺傳算法求解物流配送中心環(huán)節(jié)路徑優(yōu)化問(wèn)題進(jìn)行了介紹，由于傳統(tǒng)遺傳算法在求解物流配送路徑優(yōu)化方面存在過(guò)早收斂和解不穩(wěn)定的特征，針對(duì)性的采用動(dòng)態(tài)交叉策略和動(dòng)態(tài)變異策略避免了在求解路徑時(shí)出現(xiàn)過(guò)早收斂的問(wèn)題，然后采用爬山算法對(duì)交叉和變異操作之后得到的較優(yōu)解進(jìn)一步的優(yōu)化改進(jìn)，提高了解的質(zhì)量。最后，運(yùn)用步步高云通物流公司的真實(shí)訂單數(shù)據(jù)進(jìn)行模擬仿真實(shí)驗(yàn)，進(jìn)一步證實(shí)了本文提出的改進(jìn)遺傳算法在求解物流配送路徑方面的可行性和優(yōu)越性。

[1]李娟,張婷,李元香.基于改進(jìn)演化算法的最短路徑問(wèn)題研究[J].計(jì)算機(jī)應(yīng)用與軟件,2015,32(9):244-245.

[2]劉晗兵.基于GIS決策功能的物流配送TSP優(yōu)化模型研究[J].電子設(shè)計(jì)工程,2017,25(18):46-49.

[3]Qing-rong Wang,Chang-feng Zhu,Ying Li,Zheng-kun Zhang.Research on robust optimization of emergency logistics network considering the time dependencecharacteristic[J].IOP Conference Series:Earth and Environmental Science,2017,69(1).

[4]申艷光,張玲玉,劉永紅.基于混合遺傳算法的物流路徑優(yōu)化方法研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2018,(3).

[5]Thi Thoa Mac,Cosmin Copot,Duc Trung Tran,Robin De Keyser.A hierarchical global path planning approach for mobile robots based on multi-objective particle swarm optimization[J].Applied Soft Computing,2017,59.

[6]Y Volkan Pehlivanoglu.A new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of autonomous UAV[J].Aerospace Science and Technology,2011,16(1).

[7]Xiao-Bing Hu,Ming-Kong Zhang,Qi Zhang,Jian-Qin Liao.Co-Evolutionary path optimization by Ripple-Spreading algorithm[J].Transportation Research(Part B),2017,(2).

[8]劉荷花,崔超,陳晶.一種改進(jìn)的遺傳算法求解旅行商問(wèn)題[J].北京理工大學(xué)學(xué)報(bào),2013,33(4):390-393.

[9]唐沖.基于模擬退火算法的應(yīng)急物流車(chē)輛調(diào)度[J].物流技術(shù),2017,36(1):114-116.

[10]蔣然.改進(jìn)遺傳算法在TSP問(wèn)題中的應(yīng)用[J].軟件導(dǎo)刊,2016,15(12):127-129.

[11]金巳婷,呂閃,吳陽(yáng)明,等.基于改進(jìn)遺傳算法的物流配送路徑優(yōu)化方法研究[J].計(jì)算機(jī)與數(shù)字工程,2017,45:629-631.

[12]AdemTuncer,Mehmet Yildirim.Dynamic path planning of mobile robots with improved genetic algorithm[J].Computers and Electrical Engineering,2012,38(6).

[13]劉兆仁,徐冠宇,尹航.基于遺傳算法的公共自行車(chē)調(diào)度優(yōu)化[J].物流技術(shù),2017,36(2):78-81.