基于智能混合算法的車(chē)輛配送路徑優(yōu)化

基于智能混合算法的車(chē)輛配送路徑優(yōu)化

汪嵐

( 黎明職業(yè)大學(xué) 機(jī)電工程與自動(dòng)化學(xué)院，福建 泉州 362000 )

摘要：為提高車(chē)輛配送效率，節(jié)約配送成本，建立了以配送路徑和成本綜合最優(yōu)為目標(biāo)的車(chē)輛配送路徑問(wèn)題數(shù)學(xué)模型.設(shè)計(jì)并實(shí)現(xiàn)了一種智能混合算法，首先利用具有自適應(yīng)交叉率和變異率的改進(jìn)遺傳算法生成全局較優(yōu)解，再將較優(yōu)解轉(zhuǎn)換為初始信息素進(jìn)行蟻群算法，并結(jié)合2-opt算法對(duì)解進(jìn)一步迭代優(yōu)化，最終獲得了車(chē)輛最優(yōu)配送路徑.實(shí)驗(yàn)結(jié)果表明，該算法優(yōu)化后的目標(biāo)值比蟻群算法減少了15.0%，比遺傳算法減少了10.4%，驗(yàn)證了該算法的有效性和優(yōu)越性.

關(guān)鍵詞：車(chē)輛配送路徑問(wèn)題； 智能混合算法； 遺傳算法； 蟻群算法； 2-opt算法

收稿日期：2015-07-23

基金項(xiàng)目：泉州市科技局社會(huì)發(fā)展計(jì)劃項(xiàng)目(2012Z132);黎明職業(yè)大學(xué)?？蒲袌F(tuán)隊(duì)項(xiàng)目(LMTDD2014108)

文章編號(hào)：1004-4353(2015)03-0261-06

中圖分類(lèi)號(hào)：TP391.9

Research on optimizing vehicle routing based on intelligent hybrid algorithm

WANGLan

(DepartmentofMechanicalandElectricalEngineering,LimingVocationalUniversity,Quanzhou362000,China)

Abstract：In order to improve the efficiency and reduce the cost of vehicle delivery,a VRF mathematic model on optimizing vehicle routing and cost was established. An intelligent hybrid algorithm was proposed. Hybrid genetic algorithm which combined with self-adaptive crossover rate and mutation rate was used in the algorithm to conduct the global better solution. Then the better solution was taken as the initial solution of the ant colony algorithm and the stage solution was optimized by 2-opt algorithm to obtain the best vehicle routing. The experimental result showed that the objective value based on hybrid algorithm was 15.0% less than ant colony algorithm and 10.4% less than genetic algorithm，so the efficiency and superiority of the intelligent hybrid algorithm were proved.

Key words： vehicle routing problem; intelligent hybrid algorithm; ant colony algorithm; genetic algorithm; 2-opt algorithm

隨著現(xiàn)代物流業(yè)的飛速發(fā)展，物流配送規(guī)模和數(shù)量急劇猛增，從而導(dǎo)致配送成本在整個(gè)物流成本中占有過(guò)半的比例[1].配送路徑優(yōu)化設(shè)計(jì)，能夠節(jié)約配送成本，提高配送效率，提高企業(yè)競(jìng)爭(zhēng)力，因此，尋求合理、有效的車(chē)輛配送優(yōu)化路徑具有重要的實(shí)際意義.目前，對(duì)于車(chē)輛路徑配送問(wèn)題(vehicle routing problem,VRP)常用的智能算法有遺傳算法[2]、模擬退火算法[3]、禁忌搜索算法[4]和蟻群算法[5]等，但隨著配送過(guò)程中需考慮的約束條件日益復(fù)雜，單一的智能算法已無(wú)法很好地解決VRP問(wèn)題，逐漸被混合優(yōu)化算法[6]所取代.針對(duì)車(chē)輛配送路徑優(yōu)化問(wèn)題，本文構(gòu)造了由改進(jìn)遺傳算法、蟻群算法和2-opt算法相融合的智能混合算法，并與基本遺傳算法、蟻群算法進(jìn)行比較，最后在車(chē)輛配送實(shí)例中驗(yàn)證了混合算法的有效性和優(yōu)越性.

1車(chē)輛配送路徑優(yōu)化數(shù)學(xué)模型

車(chē)輛配送路徑優(yōu)化思路為：在配送車(chē)輛的最大承載量、最大行駛距離、客戶(hù)(節(jié)點(diǎn))需求量和位置固定等條件下，配送中心派遣多輛車(chē)對(duì)客戶(hù)進(jìn)行商品配送.基于實(shí)際配送原則，通過(guò)合理的車(chē)輛配送路徑規(guī)劃，在滿(mǎn)足所有約束條件的情況下，使配送成本和配送路徑綜合最優(yōu).

假設(shè)某一物流配送中心，擁有m輛同規(guī)格配送車(chē)，每輛車(chē)的最大承載量為Q，最大行駛距離為D.對(duì)n個(gè)節(jié)點(diǎn)進(jìn)行配送，節(jié)點(diǎn)號(hào)為i(i=1,…,n，其中i=1為配送中心)，每個(gè)客戶(hù)對(duì)應(yīng)的商品需求量為qi，客戶(hù)接受配送服務(wù)的有效時(shí)間區(qū)間為[ai，bi]，車(chē)輛實(shí)際到達(dá)客戶(hù)的時(shí)間為ti.dij為結(jié)點(diǎn)i到結(jié)點(diǎn)j的路徑長(zhǎng)度，cij為結(jié)點(diǎn)i到結(jié)點(diǎn)j的配送成本.結(jié)點(diǎn)i到結(jié)點(diǎn)j的關(guān)系如下：

(1)

(2)

其中：i=1,…,n,j=1,…,n; k=1,…,m.車(chē)輛配送路徑優(yōu)化數(shù)學(xué)模型為：

(3)

(4)

(5)

(6)

(7)

(8)

(9)

式(3)中w1、w2為配送路徑和成本目標(biāo)函數(shù)對(duì)應(yīng)的權(quán)重，式(4)為車(chē)輛承載量約束，式(5)為車(chē)輛行駛距離約束，式(6)限制每個(gè)節(jié)點(diǎn)配送任務(wù)有且只有一輛車(chē)負(fù)責(zé)，式(7)和式(8)則限制到達(dá)和離開(kāi)某一節(jié)點(diǎn)的車(chē)輛有且只有一輛，式(9)為時(shí)間窗約束，l和u為配送早到和晚到的懲罰因子.

2智能混合算法設(shè)計(jì)

遺傳算法具有全局高效尋優(yōu)和魯棒性強(qiáng)的優(yōu)點(diǎn)，但存在著早熟和反饋信息利用率低的缺點(diǎn)；蟻群算法具有反饋信息利用率高且能收斂到最優(yōu)解的優(yōu)點(diǎn)，但因初期信息素匱乏，存在求解速度慢的缺點(diǎn).本文提出的智能混合算法的思路是：將遺傳算法與螞蟻算法相結(jié)合，先對(duì)基本遺傳算法進(jìn)行改進(jìn)，實(shí)現(xiàn)變異率和交叉率的自適應(yīng)調(diào)整，生成若干全局較優(yōu)解，然后將其處理轉(zhuǎn)換為蟻群算法的初始信息素再進(jìn)行求解，并在解生成階段采用2-opt算法[7]進(jìn)一步優(yōu)化，最終獲得最優(yōu)配送路徑方案.

2.1　改進(jìn)遺傳算法

1) 編碼與初始種群生成.采用實(shí)數(shù)編碼，生成長(zhǎng)度為n+m+1的染色體，其中n為包括配送中心和客戶(hù)在內(nèi)的所有節(jié)點(diǎn)數(shù)，m為車(chē)輛數(shù).如某一配送中心有2輛車(chē)為8位客戶(hù)配送商品，應(yīng)生成長(zhǎng)度為11位的染色體.將節(jié)點(diǎn)1默認(rèn)為配送中心，則染色體12345167891表示，車(chē)輛1負(fù)責(zé)為位于節(jié)點(diǎn)2、3、4、5的客戶(hù)配送商品，車(chē)輛2負(fù)責(zé)為位于節(jié)點(diǎn)6、7、8、9的客戶(hù)配送商品，以此類(lèi)推.初始種群采用隨機(jī)方式產(chǎn)生.

2) 適應(yīng)度函數(shù).在遺傳算法中，適應(yīng)值函數(shù)與目標(biāo)函數(shù)相映射，即當(dāng)VRP優(yōu)化目標(biāo)數(shù)值Z越小時(shí)，對(duì)應(yīng)的個(gè)體適應(yīng)函數(shù)值應(yīng)越大，其對(duì)應(yīng)解性能就越好.適應(yīng)值函數(shù)設(shè)置為

(10)

4) 自適應(yīng)交叉、變異操作.采用固定值的交叉率和變異率不合理，會(huì)影響新個(gè)體產(chǎn)生的快慢，容易導(dǎo)致算法陷入局部最優(yōu)解，難以保證種群多樣性.因此，本文對(duì)二者進(jìn)行改進(jìn)設(shè)計(jì)，使其能夠根據(jù)每代具體情況進(jìn)行自適應(yīng)調(diào)整[8]，其公式如下：

(11)

2.2　蟻群算法

1) 信息素初始值.蟻群算法的初始信息素計(jì)算公式為

τij(t0)=F(sij)，

(12)

其中F(sij)是遺傳算法獲得的較優(yōu)解對(duì)應(yīng)的適應(yīng)值.這種方法可有效避免初期因信息素匱乏而造成路徑的盲目搜索，可有效提高尋徑的針對(duì)性和效率.

2) 移動(dòng)規(guī)則.t時(shí)刻，螞蟻k將根據(jù)路徑上的信息素強(qiáng)弱從客戶(hù)i移動(dòng)到下一個(gè)客戶(hù)j，其移動(dòng)概率為

(13)

式中τij(t)表示t時(shí)刻客戶(hù)i和客戶(hù)j之間路徑上的初始信息素，ηij=1/dij為客戶(hù)i和客戶(hù)j之間路徑的能見(jiàn)度，allowed為螞蟻k下一步可選擇的節(jié)點(diǎn)，α為信息啟發(fā)式因子，β為期望啟發(fā)式因子.

3) 信息素更新.螞蟻移動(dòng)至新的一個(gè)節(jié)點(diǎn)時(shí)，其對(duì)應(yīng)路徑的信息素將發(fā)生更新，計(jì)算公式為

(14)

式中ρ為信息素?fù)]發(fā)系數(shù)(0<ρ<1)，Δτij=Q/dij為客戶(hù)i和客戶(hù)j之間路徑的信息素增量，Q為常數(shù)，dij為客戶(hù)i和客戶(hù)j之間的路徑長(zhǎng)度.

4) 2-opt優(yōu)化.當(dāng)車(chē)輛配送路徑存在交叉情況時(shí)，配送距離會(huì)增大.因此，在蟻群算法的最后階段引入2-opt算法，即在承載量不變的情況下對(duì)當(dāng)前最優(yōu)路徑進(jìn)行局部?jī)?yōu)化，消除交叉現(xiàn)象，以縮短距離.2-opt算法的優(yōu)化步驟為：

Step1在一條節(jié)點(diǎn)數(shù)為n的路徑中隨機(jī)產(chǎn)生正整數(shù)i和m(m=1,…,n)，m=1.

Step2令i為1~n的任一隨機(jī)整數(shù)，對(duì)當(dāng)前最優(yōu)路徑進(jìn)行交叉判別，當(dāng)di,i+1+di+m,i+m+1>di,i+m+di+1,i+m+1時(shí)，轉(zhuǎn)Step3；否則，轉(zhuǎn)Step4.

Step3判斷存在路徑交叉現(xiàn)象，刪除邊(i,i+1)和邊(i+m,i+m+1)，增加邊(i,i+m)和邊(i+1,i+m+1).令m=m+1，轉(zhuǎn)Step5.

Step4判斷不存在路徑交叉現(xiàn)象.令m=m+1，轉(zhuǎn)Step5.

Step5判斷m=n，若等式不成立，轉(zhuǎn)Step2；等式成立，算法結(jié)束.

2-opt算法優(yōu)化路徑的效果如圖1所示.

(a)路徑交叉　　　　　　　　(b)路徑無(wú)交叉 圖1　2-opt算法優(yōu)化路徑效果圖

2.3　智能混合算法的具體步驟

1)改進(jìn)遺傳算法基本參數(shù)初始化，如種群規(guī)模，交叉率Pc1、Pc2，變異率Pm1、Pm2，最大進(jìn)化代數(shù)Genmax，配送早到和晚到的懲罰因子l、u等.

2)實(shí)數(shù)編碼，隨機(jī)生成初始種群P0，根據(jù)式(10)計(jì)算每個(gè)個(gè)體的適應(yīng)值.

3)進(jìn)行選擇操作，按照式(11)計(jì)算自適應(yīng)交叉率Pc和自適應(yīng)變異率Pm后，進(jìn)行交叉變異操作，生成新一代種群Pi(t).

4)計(jì)算新種群每個(gè)個(gè)體的適應(yīng)值.

5)判斷Genmax是否達(dá)到，若未達(dá)到，則迭代次數(shù)加1，跳轉(zhuǎn)到3)；若達(dá)到,則輸出對(duì)應(yīng)的若干個(gè)較優(yōu)解，轉(zhuǎn)到6)繼續(xù)執(zhí)行；

6)蟻群算法基本參數(shù)初始化，如α，β，ρ，Q和最大循環(huán)次數(shù)NCmax等.

7)將混合遺傳算法獲得的較優(yōu)解，按照式(12)轉(zhuǎn)換處理成蟻群算法各路徑上的信息素初始值τij(t0)，令車(chē)輛數(shù)等于螞蟻數(shù)，將螞蟻放置配送中心.

9)判斷螞蟻k是否周游過(guò)所有節(jié)點(diǎn)，若未完成，則跳轉(zhuǎn)到8)；若完成，令k←k+1，轉(zhuǎn)到10)繼續(xù)執(zhí)行.

10)判斷是否所有螞蟻都完成了周游遍所有節(jié)點(diǎn)，若未完成，則跳轉(zhuǎn)到8)；否則，轉(zhuǎn)到11)繼續(xù)執(zhí)行.

11)路徑構(gòu)建完成，對(duì)當(dāng)前路徑進(jìn)行2-opt優(yōu)化，并根據(jù)式(14)進(jìn)行當(dāng)前最佳路徑信息素全局更新.

12)判斷是否達(dá)到最大循環(huán)次數(shù)，若未達(dá)到，循環(huán)次數(shù)加1，跳轉(zhuǎn)到8)；否則，算法結(jié)束，獲得全局最優(yōu)配送路徑R.

3實(shí)驗(yàn)結(jié)果及分析

以某物流配送點(diǎn)為例：擁有配送中心1個(gè)，坐標(biāo)為(0,0)對(duì)應(yīng)節(jié)點(diǎn)號(hào)為1；同規(guī)格配送車(chē)輛9輛，車(chē)輛最大載重量8t，客戶(hù)17個(gè).遺傳算法的參數(shù)設(shè)置為：種群規(guī)模為80，交叉率Pc1=0.3,Pc2=0.7，變異率Pm1=0.001,Pm2=0.01，最大進(jìn)化代數(shù)Genmax=150，配送早到和晚到的懲罰因子l=1，u=2；蟻群算法的參數(shù)設(shè)置為：α=1，β=1，ρ=0.15，Q=15，最大循環(huán)次數(shù)NCmax=150.分別采用蟻群、遺傳和混合3種算法進(jìn)行配送路徑優(yōu)化仿真，各自進(jìn)行10次測(cè)試取平均值，3種算法的優(yōu)化目標(biāo)與迭代次數(shù)的關(guān)系曲線(xiàn)以及收斂過(guò)程如圖2和圖3所示.

圖2　優(yōu)化目標(biāo)與迭代次數(shù)的關(guān)系曲線(xiàn)

圖3　不同算法下的配送路徑仿真圖

由圖2可看出，智能混合算法的收斂速度和目標(biāo)值的優(yōu)化效果比其他兩種優(yōu)化算法具有明顯的優(yōu)勢(shì)，由此證明了該算法的有效性和優(yōu)越性.由圖3可看出,最佳配送路線(xiàn)為：1→11→1→4→16→15→1→6→14→1→2→1→3→1→13→7→5→1→12→17→1→10→18→1→9→8→1，配送最短行駛里程為124.6517km.表1為3種算法優(yōu)化后的性能指標(biāo).由表1中3種不同算法對(duì)配送路徑優(yōu)化后的性能指標(biāo)可知:對(duì)于綜合目標(biāo)值，混合算法比蟻群算法減少了15.0%，比遺傳算法減少了10.4%；對(duì)于運(yùn)算耗時(shí)，混合算法耗時(shí)比蟻群算法縮短了2.20%，比遺傳算法縮短了2.18%.由此可知，采用混合算法獲得的配送路徑比蟻群算法和遺傳算法能夠節(jié)省配送成本，縮短配送路徑，可有效地提高配送效率.

表1　不同算法優(yōu)化對(duì)應(yīng)的性能指標(biāo)

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

本文構(gòu)建了以配送路徑和配送成本為優(yōu)化目標(biāo)且?guī)в袝r(shí)間窗約束的車(chē)輛配送路徑優(yōu)化數(shù)學(xué)模型,針對(duì)模型特點(diǎn)，提出一種智能混合算法，將遺傳算法、蟻群算法和2-opt算法融合起來(lái)，發(fā)揮各自算法的優(yōu)點(diǎn)，提高了算法全局尋優(yōu)能力和局部搜索的科學(xué)性.仿真實(shí)驗(yàn)結(jié)果表明，采用智能混合算法求解，比遺傳算法和蟻群算法獲得的結(jié)果更優(yōu)，具有較好的實(shí)際意義.本文所建的模型有一定的局限性，且對(duì)時(shí)間窗的研究還較為不足，今后將對(duì)此做進(jìn)一步地研究，使之更加貼近實(shí)際情況.

參考文獻(xiàn)：

[1]張曉龍.電子商務(wù)下現(xiàn)代物流企業(yè)配送系統(tǒng)優(yōu)化研究[J].物流技術(shù),2011,30(6):135-138.

[2]柳林,朱建榮.基于遺傳算法的物流配送路徑優(yōu)化問(wèn)題的研究[J].計(jì)算機(jī)工程與應(yīng)用,2005(27):227-229.

[3]胡大偉,朱志強(qiáng),胡勇.車(chē)輛路徑問(wèn)題的模擬退火算法[J].中國(guó)公路學(xué)報(bào),2006,19(4):123-126.

[4]王雪蓮,汪波,鐘石泉.一類(lèi)半開(kāi)放式車(chē)輛路徑問(wèn)題及其晉江算法研究[J].機(jī)系統(tǒng)仿真學(xué)報(bào),2008,20(8):1969-1972.

[5]楊從平.基于蟻群算法的快遞物流配送路徑優(yōu)化[J].物流工程與管理,2014,36(4):27,65-67.

[6]蔣國(guó)清,潘勇,胡飛躍.兩階段式的物流配送路徑優(yōu)化方法[J].計(jì)算機(jī)工程與應(yīng)用,2015,51(2)：255-258.

[7]任璐.基于遺傳算法的建立與求職崗位匹配研究[D].廣州：暨南大學(xué)，2009:22.

[8]宋娟,崔艷.基于改進(jìn)遺傳算法的同城快遞配送模型[J].電子技術(shù)應(yīng)用,2014,40(12):136-139.