混洗蛙跳算法在農(nóng)產(chǎn)品物流配送車輛路徑上的應(yīng)用

鄭紅劍++劉巧

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

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

中圖分類號：F274；C934 文獻標識碼：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ā)展的一個重要因素。中國農(nóng)產(chǎn)品電子商務(wù)的發(fā)展競爭主要體現(xiàn)在農(nóng)產(chǎn)品物流的配送方面，農(nóng)產(chǎn)品車輛運輸成本是物流企業(yè)首先考慮的問題。優(yōu)化和改善物流配送過程，規(guī)劃農(nóng)產(chǎn)品物流配送的合理路徑是提高物流企業(yè)利潤和提升服務(wù)質(zhì)量的關(guān)鍵。針對當前農(nóng)產(chǎn)品物流配送車輛路徑問題中無法滿足客戶時間需求的問題，本研究對混洗蛙跳算法進行改進，與帶時間窗的車輛路徑問題相結(jié)合進行分析研究，以期有效解決全局收斂和局部收斂的問題，為農(nóng)產(chǎn)品物流配送發(fā)展提供參考[1]。

1 改進的多目標優(yōu)化算法

1.1 混洗蛙跳算法原理

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

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

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

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

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

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

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

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

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

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

1.2 算法流程

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

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

步驟3：對整個種群按m=z×n分為z個組群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：在每個子種群memeplex中，每個青蛙都受到其他青蛙的影響，不斷地向目標接近。采用的進化流程如下：

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

2）dN=dN+1。

3）對青蛙的位置進行移動，每次青蛙移動的距離不能超過可移動的最大距離。

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

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

6）若dN

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

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

1.3 改進的混洗蛙跳算法

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

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

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

2 車輛路徑問題

2.1 車輛路徑問題的描述

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

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

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

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

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

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

2.2 帶時間窗的車輛路徑問題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 小結(jié)

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

參考文獻：

[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é)報，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].計算機與現(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] 尚榮華，焦李成，馬文萍，等.用于約束多目標優(yōu)化的免疫記憶克隆算法[J].電子學(xué)報，2009，37（6）：1289-1294.