混洗蛙跳算法在農產品物流配送車輛路徑上的應用

鄭紅劍++劉巧

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

關鍵詞：混洗蛙跳算法；農產品物流；車輛路徑問題

中圖分類號：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

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

1 改進的多目標優化算法

1.1 混洗蛙跳算法原理

混洗蛙跳算法是一種基于啟發式搜索的算法，2003年Eusuff、Lansay提出混洗蛙跳算法，通過啟發函數進行搜索，最終找到最優解。該算法以模因算法為基礎，結合粒子群優化算法而產生。

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

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

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

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

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

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

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

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

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

1.2 算法流程

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

步驟2：種群中的所有青蛙根據個體適應值的大小按降序排序，生成組數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）初始化迭代次數dN=0，通過每次進化，青蛙個體之間的信息交流，對最壞位置青蛙的位置進行改善。

2）dN=dN+1。

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

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

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

6）若dN

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

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

1.3 改進的混洗蛙跳算法

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

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

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

2 車輛路徑問題

2.1 車輛路徑問題的描述

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

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

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

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

2）企業運營成本最小（車輛使用成本、運輸成本、企業配送時間成本等）。

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

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

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

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

3 G-SFLA在農產品物流配送VRP中的應用

3.1 帶時間窗的VRP數學模型

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

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

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

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

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

3.2 G-SFLA求解模型的算法設計

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

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

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

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

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

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

4 小結

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

參考文獻：

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