鄭紅劍++劉巧

摘要：針對當(dāng)前農(nóng)產(chǎn)品物流配送車輛路徑問題中無法滿足客戶時(shí)間需求的問題，對混洗蛙跳算法進(jìn)行改進(jìn)，與帶時(shí)間窗的車輛路徑問題相結(jié)合進(jìn)行分析研究，可以有效解決全局收斂和局部收斂問題。結(jié)果表明，G-SFLA算法是求解農(nóng)產(chǎn)品物流配送車輛路徑問題的較優(yōu)方案。

關(guān)鍵詞：混洗蛙跳算法；農(nóng)產(chǎn)品物流；車輛路徑問題

中圖分類號：F274；C934 文獻(xiàn)標(biāo)識碼：A 文章編號：0439-8114（2017）09-1755-04

DOI：10.14088/j.cnki.issn0439-8114.2017.09.039

Research of Agricultural Products Logistics Distribution Vehicle Routing Problem Based on Improved Algorithm of Shuffle Leap-frog

ZHENG Hong-jian，LIU Qiao

（Hubei Academy of Scientific and Technical Information，Wuhan 430074，China）

Abstract： According to current agricultural products logistics distribution vehicle routing problem， unable to meet needs of customers time， algorithm of shuffle leap frog combined with the vehicle routing problem with time Windows analysis was improved， which would solve the problem of global and local convergence， experiments showed that the G-SFLA algorithm for logistics distribution vehicle routing problem was an excellent plan.

Key words： shuffle leap frog algorithm；agricultural products logistics；vehicle routing problem

近年來，農(nóng)產(chǎn)品電子商務(wù)發(fā)展迅速，已經(jīng)在中國得到大力推廣，農(nóng)產(chǎn)品物流配送已經(jīng)成為制約農(nóng)產(chǎn)品電子商務(wù)發(fā)展的一個(gè)重要因素。中國農(nóng)產(chǎn)品電子商務(wù)的發(fā)展競爭主要體現(xiàn)在農(nóng)產(chǎn)品物流的配送方面，農(nóng)產(chǎn)品車輛運(yùn)輸成本是物流企業(yè)首先考慮的問題。優(yōu)化和改善物流配送過程，規(guī)劃農(nóng)產(chǎn)品物流配送的合理路徑是提高物流企業(yè)利潤和提升服務(wù)質(zhì)量的關(guān)鍵。針對當(dāng)前農(nóng)產(chǎn)品物流配送車輛路徑問題中無法滿足客戶時(shí)間需求的問題，本研究對混洗蛙跳算法進(jìn)行改進(jìn)，與帶時(shí)間窗的車輛路徑問題相結(jié)合進(jìn)行分析研究，以期有效解決全局收斂和局部收斂的問題，為農(nóng)產(chǎn)品物流配送發(fā)展提供參考[1]。

1 改進(jìn)的多目標(biāo)優(yōu)化算法

1.1 混洗蛙跳算法原理

混洗蛙跳算法是一種基于啟發(fā)式搜索的算法，2003年Eusuff、Lansay提出混洗蛙跳算法，通過啟發(fā)函數(shù)進(jìn)行搜索，最終找到最優(yōu)解。該算法以模因算法為基礎(chǔ)，結(jié)合粒子群優(yōu)化算法而產(chǎn)生。

1989年Moscato提出模因算法（Memetic Algorithm，MA），Meme如同染色體上攜帶遺傳信息的基因，只有被傳播或重復(fù)的時(shí)候才可以稱為Meme，該算法在處理局部問題時(shí)采用競爭與協(xié)作機(jī)制，解決其他算法無法解決的大型離散優(yōu)化問題。

1995年Eberhart和Mennedy根據(jù)鳥群捕食的行為模擬簡化的社會模型提出粒子群優(yōu)化算法。其原理是在D維搜索空間以特定速度運(yùn)動(dòng)著的粒子群體里，每個(gè)粒子不斷地搜索相關(guān)范圍內(nèi)其他粒子的相優(yōu)值，并在此基礎(chǔ)上進(jìn)行位置變化。粒子的速度和位置公式如下：

V ■■=V ■■+c1ξ（P ■■-x ■■）+c2η（P ■■-x ■■） （1）

V ■■=V ■■+V ■■ （2）

其中，C1、C2為學(xué)習(xí)因子，具有學(xué)習(xí)和自我總結(jié)的能力，使粒子不斷地向歷史最優(yōu)點(diǎn)逼近；ξ，η∈[0，1]，是區(qū)間內(nèi)的一個(gè)均勻分布隨機(jī)數(shù)，xi=（xi1，xi2，…，xiD）為第i個(gè)粒子位置，pi=（pi1，pi2，…，piD）為粒子經(jīng)歷過的歷史最好點(diǎn)，pg=（pg1，pg2，…，pgD）為粒子經(jīng)過的歷史最好點(diǎn)。

1998年Shi和Eberhart在算法中引入慣性權(quán)重，改善了算法的收斂性能，將速度公式（1）改為：

V ■■=ωV ■■+c1ξ（P ■■-x ■■）+c2η（P ■■-x ■■） （3）

其中ω為慣性權(quán)重，其值的大小可以使粒子具有均衡的探索能力和開發(fā)能力。當(dāng)ω=1時(shí)，就是標(biāo)準(zhǔn)的基本粒子群優(yōu)化算法。

混洗蛙跳算法通過模擬自然界中大量青蛙集體覓食生成的一種群體協(xié)同搜索算法，利用個(gè)體及群體間信息的傳遞，將全局信息交換和局部搜索有效地結(jié)合。將空間中的青蛙劃分為若干個(gè)子群體，各個(gè)子群體都有其自身的特性，子群中的每個(gè)青蛙也有個(gè)自特性并對其他個(gè)體產(chǎn)生影響，隨著蛙群的進(jìn)化也發(fā)生改變，當(dāng)這些子種群進(jìn)化到一定程度時(shí)，將這些子種群進(jìn)行混合，實(shí)現(xiàn)信息的交流，直到滿足終止條件[2]。該算法將局部深度搜索與全局交換搜索相結(jié)合，擺脫了陷入局部最優(yōu)的現(xiàn)象。

1.2 算法流程

步驟1：種群初始化，求解空間中，種群F包含m（m=z×n）只青蛙。其中z表示整個(gè)種群劃為分子種群的數(shù)量，n為每個(gè)子種群中包含的青蛙數(shù)量。維數(shù)為d，每個(gè)青蛙的位置表示一個(gè)候選解，第i只青蛙的位置F（i）的適應(yīng)值用fi表示。

步驟2：種群中的所有青蛙根據(jù)個(gè)體適應(yīng)值的大小按降序排序，生成組數(shù)X={F（i），fi；i=1，2，…，m}，當(dāng)i=1時(shí)，表示該青蛙的位置最好。

步驟3：對整個(gè)種群按m=z×n分為z個(gè)組群Y1，Y2，…，Yz，即：

Yk={F（j），fj|（j）=F[k+z（j-1）]，fj=[k+z（j-1）]，j=1，2，3…，n}，將第1只青蛙分入Y1子群，第2只青蛙分入Y2，以此類推，第z只青蛙分入Yz，第z+1只青蛙分為Y1，直至所有青蛙都分配完為止。

步驟4：在每個(gè)子種群memeplex中，每個(gè)青蛙都受到其他青蛙的影響，不斷地向目標(biāo)接近。采用的進(jìn)化流程如下：

1）初始化迭代次數(shù)dN=0，通過每次進(jìn)化，青蛙個(gè)體之間的信息交流，對最壞位置青蛙的位置進(jìn)行改善。

2）dN=dN+1。

3）對青蛙的位置進(jìn)行移動(dòng)，每次青蛙移動(dòng)的距離不能超過可移動(dòng)的最大距離。

4）對每次青蛙的新位置與原位置相比較，其優(yōu)于原位置，用新位置上的青蛙代替原來的青蛙，否則用歷史最好點(diǎn)的青蛙pg代替子種群中位置最好的青蛙pb，不斷重復(fù)上述動(dòng)作。

5）若上述操作不能產(chǎn)生新解，那么就隨機(jī)產(chǎn)生一個(gè)新的位置代替該子種群中位置最差的青蛙pw。

6）若dN

步驟5：青蛙經(jīng)過memetic進(jìn)化后，將其子種群進(jìn)行混合，重新按適應(yīng)值進(jìn)行排序。

步驟6：滿足結(jié)束條件，直接結(jié)束，否則跳至步驟3。

1.3 改進(jìn)的混洗蛙跳算法

混洗蛙跳算法在全局搜索能力上比較強(qiáng)，但假如問題比較復(fù)雜時(shí)，則存在收斂速度慢和易陷入局部極值的問題，將遺傳算法引入到混洗蛙跳算法中可以在保持原算法優(yōu)點(diǎn)的基礎(chǔ)上，具有跳出局部最優(yōu)的能力，即遺傳混洗蛙跳算法（Genetic-Shuffle Flog Leaping Algorithm，G-SFLA）。

G-SFLA與SFLA的不同點(diǎn)是對分組進(jìn)化采取遺傳算法的交叉和變異運(yùn)算，這兩個(gè)運(yùn)算應(yīng)用在流程的步驟4中。交叉運(yùn)算指的是隨機(jī)將性能最好的青蛙Pb與性能最差的青蛙Pw的相同位置設(shè)為交叉點(diǎn)，將這兩個(gè)個(gè)體的交叉點(diǎn)右邊交換，生成兩個(gè)新解。若產(chǎn)生的新解位置優(yōu)于Pw，則代替Pw。若產(chǎn)生的新解不優(yōu)于Pw，則隨機(jī)對Pw的若干位進(jìn)行變異運(yùn)算，從而產(chǎn)生新解代替原來的Pw。

G-SFLA中，對于分組也進(jìn)行了一定的改進(jìn)，對于SFLA的分組方法，最后一組的個(gè)體在整個(gè)群體中相對適應(yīng)值比較差的個(gè)體，即使該組成員不斷經(jīng)過信息交流和學(xué)習(xí)，也無法得到一個(gè)較好的進(jìn)化結(jié)果。由于分組的不均勻，使學(xué)習(xí)的局限性放大。新的分組方式是在原來分組的基礎(chǔ)上，隨機(jī)從其他組中抽出若干個(gè)體加入了該組中，此時(shí)組成員的個(gè)數(shù)變?yōu)閚+z-1，小組的多樣性得到了認(rèn)同，發(fā)揮了遺傳運(yùn)算的優(yōu)勢。需要注意的是，當(dāng)小組重新合并為一個(gè)種群時(shí)，種群中個(gè)體的數(shù)量增加了z×（z-1）個(gè)，重新對所有的個(gè)體進(jìn)行排序，刪除重復(fù)的個(gè)體。刪除后的個(gè)體數(shù)量大于z，則取前z個(gè)個(gè)體進(jìn)行下一輪的迭代，假如不足z個(gè)個(gè)體，隨機(jī)產(chǎn)生個(gè)體，補(bǔ)足z個(gè)進(jìn)行下一輪迭代。

2 車輛路徑問題

2.1 車輛路徑問題的描述

近年來，中國的物流行業(yè)發(fā)展迅速，但是農(nóng)產(chǎn)品物流的配送模式相對比較落后，無形之中增加了運(yùn)營的成本。對于物流企業(yè)來說，物流車輛的調(diào)度問題是最關(guān)鍵的，利用信息技術(shù)和數(shù)學(xué)知識對農(nóng)產(chǎn)品車輛路徑問題建立模型，通過模型分析農(nóng)產(chǎn)品車輛的運(yùn)輸能力，可以為物流企業(yè)節(jié)約大量的成本。

農(nóng)產(chǎn)品車輛路徑問題是指對一系列的發(fā)貨點(diǎn)和收貨點(diǎn)規(guī)劃合適的行車路線，在一定的約束條件（需求量、發(fā)貨時(shí)間、發(fā)貨量、車輛容量限制、時(shí)間限制及行駛距離限制等）下，讓車輛有序地通過各個(gè)節(jié)點(diǎn)，達(dá)到使用車輛最少、行駛距離最短和花費(fèi)最少的目標(biāo)。車輛路徑問題簡稱VRP，在1959年由Ramser 和Dantzig提出，隨著社會經(jīng)濟(jì)的不斷發(fā)展，很快受到計(jì)算機(jī)學(xué)科和數(shù)學(xué)相關(guān)學(xué)科的重視[3]。VRP可以描述如圖1所示。

以配送中心為中心，形成若干個(gè)客戶群體，即多個(gè)配送路線，每個(gè)線段代表著運(yùn)輸?shù)馁M(fèi)用，在建立配送線路時(shí)，一般目標(biāo)函數(shù)設(shè)計(jì)為以下兩種：

1）客戶滿意度（客戶對配送時(shí)間的要求）。

2）企業(yè)運(yùn)營成本最?。ㄜ囕v使用成本、運(yùn)輸成本、企業(yè)配送時(shí)間成本等）。

對于VRP的約束條件主要有車輛運(yùn)行時(shí)間、配送中心的開放時(shí)間、車載容量、最大車輛數(shù)等。

2.2 帶時(shí)間窗的車輛路徑問題

隨著物流行業(yè)的不斷發(fā)展，客戶對送貨時(shí)間的滿意度成為物流行業(yè)之間競爭的主要因素，將客戶的時(shí)間窗這一限制與車輛路線優(yōu)化相結(jié)合形成帶時(shí)間窗的車輛路徑問題（VRPTW）。VRPTW除了考慮企業(yè)的運(yùn)營成本之外，還考慮到客戶在等待物流車輛時(shí)所占用的時(shí)間。將帶時(shí)間窗的車輛路徑問題描述如下：一個(gè)配送中心、M輛一定載重的農(nóng)產(chǎn)品運(yùn)輸車輛和N個(gè)客戶節(jié)點(diǎn)[4]。其中已知條件為配送中心及客戶節(jié)點(diǎn)的位置，運(yùn)輸車輛的載重量、每個(gè)客戶的需求量及第i個(gè)客戶允許等待服務(wù)的時(shí)間[Ei，Ui]，車輛路徑問題的目標(biāo)是設(shè)計(jì)出合理的行駛路線，使得客戶等待的時(shí)間最短，達(dá)到最高的滿意度。

對于時(shí)間窗的設(shè)置主要有三種，一種是硬時(shí)間窗，即要求配送車輛必須嚴(yán)格按照要求時(shí)間送達(dá)，早到則等待客戶，遲到則客戶拒收；第二種是軟時(shí)間窗，在規(guī)定的時(shí)間窗內(nèi)沒有配送到達(dá)，無論是早到或遲到，都要受到處罰，該處罰不同于硬時(shí)間窗的等待與拒收，早到或遲到的時(shí)間越久，所受到的處罰越嚴(yán)重。描述兩種時(shí)間窗如圖2所示。

3 G-SFLA在農(nóng)產(chǎn)品物流配送VRP中的應(yīng)用

3.1 帶時(shí)間窗的VRP數(shù)學(xué)模型

帶時(shí)間窗的VRP的相關(guān)描述如下：一個(gè)配送中心用0表示，配送中心可以有M輛車與N個(gè)客戶，一輛配送車輛的最大行駛距離為D，一輛車的載重為Q，設(shè)置配送中心的坐標(biāo)位置為（X0，y0），第i個(gè)客戶的坐標(biāo)為（xi，yi），第i個(gè)客戶接收配送物品的時(shí)間窗為[e，u]，需求量為qi，每個(gè)車輛到達(dá)第i個(gè)客戶位置后的時(shí)間為ti，給客戶服務(wù)的時(shí)間為si，從第i個(gè)客戶到第j個(gè)客戶所需的時(shí)間為tij，兩個(gè)客戶之間的距離為dij，當(dāng)?shù)趍輛車為第i個(gè)客戶服務(wù)后行駛至第j個(gè)客戶為其服務(wù)為決策變量Xijm，Xijm只能為1或0。配送車輛只為每個(gè)客戶服務(wù)一次，規(guī)劃出合理的農(nóng)產(chǎn)品配送車輛行駛路線，使得企業(yè)的運(yùn)營成本最低，客戶的滿意度最高[5，6]。建立的數(shù)學(xué)模型如下：

MinA1=∑■■∑■■∑■■Xijm （4）

該公式為目標(biāo)函數(shù)1，表示配送車輛行駛的距離最小。

MinA2=∑■■∑■■{max（ei-tim）+max（tim-ui）} （5）

該公式為目標(biāo)函數(shù)2，表示配送車輛行駛的等待時(shí)間及遲到時(shí)間花費(fèi)的最少，即車輛準(zhǔn)時(shí)到達(dá)的次數(shù)最多。除了目標(biāo)函數(shù)外，還有約束函數(shù)，主要是每個(gè)客戶都必須得到服務(wù)且只能由一輛配送車輛提供，配送中心發(fā)出的車輛不能超過總車輛M。

3.2 G-SFLA求解模型的算法設(shè)計(jì)

根據(jù)G-SFLA算法的流程，算法的設(shè)計(jì)主要有編碼、種群初始化、適應(yīng)值排序、分配組群、進(jìn)化（交叉和變異運(yùn)算）等五個(gè)方面[7]。

1）編碼。根據(jù)數(shù)學(xué)模型，將配送中心設(shè)置為0，N個(gè)客戶從1至N進(jìn)行表示，則最多有N條路線，N條路線與N個(gè)客戶結(jié)點(diǎn)相結(jié)合，形成2N個(gè)自然數(shù)序列。每個(gè)客戶和線路都只能執(zhí)行一次，是算法的一個(gè)基本約束條件。

2）種群初始化。在求解空間中，種群F包含n個(gè)客戶和n條線路。假設(shè)一輛配送車輛可以包含一個(gè)組群，則m輛車表示整個(gè)種群劃分子種群的數(shù)量，每個(gè)客戶的位置表示一個(gè)候選解，第i個(gè)客戶的位置F（i）的適應(yīng)值用fi表示。

3）適應(yīng)值排序。對每個(gè)客戶的適應(yīng)值按大小進(jìn)行排序，排序由目標(biāo)函數(shù)和約束函數(shù)的評估結(jié)果來決定，先利用約束條件對其進(jìn)行初步的篩選。

4）分配組群。與適應(yīng)值相近的客戶分配為一個(gè)組群，由一輛配送車輛來完成配送。初步分配的組群中客戶的數(shù)量是相同的，即n/m。

5）進(jìn)化。進(jìn)化操作利用交叉和變異兩種運(yùn)算，使算法實(shí)現(xiàn)全局收斂和局部收斂。其中交叉運(yùn)算指的是隨機(jī)將計(jì)算出性能最好的客戶適應(yīng)值Pb與性能最差的客戶Pw的相同位置設(shè)為交叉點(diǎn)，將這兩個(gè)客戶的交叉點(diǎn)進(jìn)行右邊交換，生成兩個(gè)新解。若產(chǎn)生的新解位置優(yōu)于Pw，則代替Pw。若產(chǎn)生的新解不優(yōu)于Pw，則隨機(jī)對Pw的若干位進(jìn)行變異運(yùn)算，從而產(chǎn)生新解代替原來的Pw。在不斷的迭代過程中，不斷地劃分每輛配送車輛的行駛范圍，即不斷規(guī)劃出新的行駛路線，最終達(dá)到最優(yōu)。

4 小結(jié)

針對時(shí)間窗的車輛路徑問題的算法分析，有效地解決了農(nóng)產(chǎn)品運(yùn)輸車輛路徑優(yōu)化問題，可以為物流配送企業(yè)的決策者提供配送方案的最優(yōu)解。但是，本研究的算法是建立在一種相對理想的狀態(tài)，如給每個(gè)客戶的服務(wù)時(shí)間是相同的，這在現(xiàn)實(shí)中是不可能的，另外隨著客戶量的不斷增加，算法能否適應(yīng)未來發(fā)展的需要，也是需要進(jìn)一步研究。

參考文獻(xiàn)：

[1] ZITZLER E，THIELE L.Multiobjective evolutionary algorithms：A comparative case study and the strength pareto approach[J].IEEE Transactions on Evolulionary Compution，1999，3（4）：257-271.

[2] DNATZIG G，RAMSER J. The truck dispatching porblem[J]. Management Science，1959（6）：80-91.

[3] 劉云忠，宣慧玉.車輛路徑問題的模型及算法研究綜述[J].管理工程學(xué)報(bào)，2005，9（1）：124-131.

[4] EUSUFF M，LANSEY K E. Optimization of water distribution network design using the shuffled frog leaping algorithm[J]. Water Resources Planning and Management，2003，129（3）：210-225.

[5] 染垚深，盛建倫.基于粒子群算法的混洗蛙跳算法[J].計(jì)算機(jī)與現(xiàn)代化，2009（11）：39-41.

[6] ZHEN Z Y，WANG D B，LIU Y Y. Improved shuffled frog leaping algorithm for continuous optimization problem[C].USA：IEEE Congress on Evolutionary Computation，2009.

[7] 尚榮華，焦李成，馬文萍，等.用于約束多目標(biāo)優(yōu)化的免疫記憶克隆算法[J].電子學(xué)報(bào)，2009，37（6）：1289-1294.