基于改進花朵授粉算法的車輛路徑問題研究*

黃佳艷 程 科

（江蘇科技大學計算機學院 鎮江 212000）

1 引言

計算機和萬物互聯的迅速傳播，網絡購物需求被激發，推動了現代物流配送行業發展，對于現代物流配送的車輛路徑規劃問題（Vehicle Routing Problem，VRP）的研究在實際流配送行有著重要的應用價值［1］。解決車輛路徑問題的目的就在于尋找最優路徑，從而提高物流的配送效率、降低配送成本、提高車輛的利用率。最近幾年使用元啟發式算法（MetaHeuristic Algorigthm，MA）來解決車輛路徑問題是學者研究的熱點［2］：Berak等［3］改進了群智能算法，用來求解不確定車輛數的帶時間窗的VRP問題；鄔開俊［4］將改進的差分算法與貪心算法相融合；Brito等［5］進一步加入模糊約束和時間窗，而且混合蟻群算法，給出了近距離開放式車輛路徑規劃問題的答案；王超等［6］創新了模擬退火路徑重連優化算法，解答了兩級選址一路徑的問題，并且大大地提高了對大規模路徑問題的尋找最優解的能力。

2012年，花朵授粉算法（Flower Pollination Algorithm，FPA）由Yang［7］提出，它的核心思想是模擬自然界中花朵兩種授粉的模式，是一種新隨機優化算法。FPA因為需求調節的參數少，因此具有容易進行調節、代碼實現起來較為簡單等優點，轉換概率參數p能夠有效地調節全局和局部之間的平衡，受到了國內外學者的關注和研究：肖輝輝等［8～9］融合了差分算法和FPA算法，并且對移動機器人路徑規劃問題進行了驗證；劉敏［10］在傳統FPA算法中加入遺傳算法的交叉和變異操作，對中等規模的物流配送中心選址問題交出了答案。基于FPA在求解路徑規劃上具有的優勢，故考慮將FPA用于VRP的求解。

但與傳統的MA類似，FPA算法具有易陷入小范圍的局部尋優，且算法后期收斂到最佳解的速度慢使得算法的能力受限制等缺陷。因此，本文提出基于人工蜂群算法（Artificial Bee Colony Algorithm，ABC）［11］的花朵授粉優化算法（ABCFPA），用來提高初始算法的尋找最佳解的能力，并將改進后的FPA優化算法用來求解現代車輛物流配送中VRP的求解。

2 改進的花朵授粉算法

2.1 花朵授粉算法

自然界中，一個植株可以開好幾朵多花，一朵花可以產生許多花配子，但是FPA中為了簡便的計算，假設一棵植物有一朵花，一朵花有一個配子，一個配子是一個候選解，并且總結以下四個理想的規則。

規則一：全局搜索行為對應異花傳粉，并且通過列維飛行的機制實現全局授粉；

規則二：局部搜索行為，或局部授粉對應的為非生物自花授粉；

規則三：花的穩定性（也就是說，一個特定的傳粉者只給一個特定的植物傳粉）可以被認為是花的繁殖概率，與兩種花的相似性成比例；

規則四：轉換概率參數p∈（0，1），來平衡全局授粉和局部授粉。p是算法中重要的一個參數。

該算法的全局授粉行為由式（1）實現，局部授粉行為由式（3）實現：

其中：λ=3/2，Γ（λ）是標準的伽瑪函數。

2.2 基于人工蜂群模型的花朵授粉算法

2.2.1 人工蜂群算法

ABC算法是以蜜蜂采蜜為原型提出的一種智能算法，食物源位置對應求解問題的可行性解，其花粉數量的多少對應解的適應度，因為算法優秀的個體尋優能力，受到很多關注［13～15］。在算法的搜索過程中，第一需要對算法進行初始化，包括確定當前種群數目、算法的最大循環次數、最大搜索次數以及確定解的搜索空間。初始化后，在三種蜜蜂的作用下進行搜尋，不斷的迭代循環，直到算法達到最大次數或者算法最佳解的精確度達到誤差范圍內。

在算法的初始階段，所有的可行性解都是通過式（4）生成：

公式中r為（0，1）上的隨機數，是第i（i=1，…，SN）個解的第m（m=1，…，D）維，SN為種群大小，D為向量維度。

雇傭蜂在其記錄的對應解xi的鄰域內通過式（5）搜索新的解vi，再利用式（6）計算其適應度值并進行越界處理。

2.2.2 改進的花朵授粉算法

針對FPA算法的缺點，本文將ABC算法的采蜜搜索階段和偵查尋優階段融合到FPA算法中，將傳統的FPA算法中輸出的最佳解和適應度值輸入到第二階段ABC算法，提出一種FPA優化算法，即ABCFPA算法，以達到提高FPA的收斂到最優解的速度和找到最優解的能力的目的。

采蜜搜索階段：通過式（4）完成。

偵查蜂尋優階段：獲取當前全部的解并按照解的適應度值高低對應的概率，選擇一個解，公式如式（7）所示：

當對應解的適應度值越高，那么這個解的被選擇到的概率就越大，而當位置i的解在迭代過程中未更新的次數超過設定值之后，這個解將被舍棄，并由偵查蜂重新生成一個隨機解來代替，使算法從局部最優中跳出來。

則ABCFPA算法具體實現步驟如下。

Step1：初始化所需參數：花朵種群最大的規模為sizepopmax，最大迭代次數tmax，蜂群的搜索次數上限為limit，解的維度D；

Step2：計算當前種群的適應度值并記下當前全局的最優值及其對應的適應度值；

Step3：算法進行主體循環，若p＞rand，則按式（1）對當前解進行更新，并進行越界處理，否則轉step4；

Step4：若p＜rand，則按式（2）對解進行更新，并進行越界處理。

Step5：利用ABC算法的式（4）對step3或者step4中的解進行搜索更新，并算出它的適應度值；

Step6：利用ABC算法的式（5）在食物源的鄰域內循環進行搜索，產生新解，并用式（6）計算適應度值，并進行越界處理；

Step7：若step7超過了limit，那么生成偵查蜂，放棄該解，轉step3，否則step9；

Step8：計算sizepopmax個種群的最優適應度值和對應的最優解，若其優于全局最優值，則更新全局最優解郁全局最優值；

Step9：結束條件判斷，若滿足，退出程序并輸出結果，否則step3。

3 車輛路徑問題的數學模型

車輛路徑規劃問題的模型是指由配送中心向周邊配送點配送貨物并且最終重新回到配送中心的模型。假設該配送中心有k（k=0，…，k）輛貨車，并且每一輛貨車容量為q，配送點i（i=1，…，m），i=O表示配中心，配送點需求為g并要求：每一個配送點都要被滿足并且只被訪問一次，配送路徑最短，使用車輛最少，且配送車輛需回到配送點。定義如下變量：

變量Cij為車輛從一個配送點i駛向另一個一個配送點j所需要的成本，數學模型如式（8）：

其中式（9）～（10）約束每個配送點都只有一輛車到達，式（11）車輛的運輸容量約束，式（12）保證每個配送點都被訪問，式（13）消除配送中的局部回路。

4 仿真實驗與分析

4.1 改進的花朵授粉算法性能分析

所涉及的實驗在CPU為3.0GHz、4GB內存、Windows 7的計算機上采用Matlab 2016a進行仿真驗證。首先對改進后算法的有效性和精確性進行驗證：設置種群最大規模20，最大迭代次數3000，最大限制次數limit=20，轉化概率P=0.8，λ=1.5。將FPA和ABCFPA獨立運行50次后最優值、平均值、最差值和尋優成功率進行對比，結果如表1所示。

表1 FPA和ABCFPA在固定迭代次數下尋優性能比較

由表1可以看出ABCFPA算法在固定維度下各方面的尋優效果要好于標準FPA算法，證明了改進后的算法在尋優能力上的精度更高，函數1～4均能找到最優值（精度得到10-10認為尋優成功）說明了改進后的算法能有效地避免陷入局部最優。

4.2 小規模實例

將改進后的ABCFPA算法用于小規模車輛路徑問題的求解，并與文獻［17］～［19］中的算法結果進行效果對比。假設，有一個配送中心，配送車輛為2輛，每輛8噸，配送點為8個。配送中心與各配送點之間的距離以及各配送點所需要的貨物數量如表2所示（其中數字0表示配送中心）。求解目標為運輸總路徑最短。

表2 配送中心與配送點之間的距離及需求

仿真實驗中的參數設置如下：設置最大規模為60，最大迭代次數為50。將算法獨立運行20次，實驗得到的運行20次下的平均最短行駛路徑為67.65，找到最短路徑18次，尋優成功率為90%。此外，在相同的種群大小和迭代次數下，以下算法進行獨立模擬實驗20次，標準遺傳算法（GA）和雙種群遺傳算法（DPGA）獨立實驗20次的結果如下：標準遺傳算法的20次平均結果是73.25，未找到已知的最短路徑，雙種群遺傳算法的20次平均結果是69.575，有20%的成功率可以找到已知的最優路徑；混合遺傳算法（HGA）進行獨立實驗20次得到的平均結果是67.875，找到最短路徑的次數15次，尋優成功率為75%；改進微粒群算法（MPSO）進行20次獨立實驗的結果為平均結果68.375，找到最短路徑9次，尋優成功率只有45%。

由表3中的數據對比可以看出，在相同的設置條件下，改進后的花朵授粉優化在求解車輛路徑規劃問題上找到最短路徑的成功率更高且找到的平均最短路徑較其他算法更短。

表3 小規模實例實驗結果

4.3 大規模實例

為了驗證改進后的花朵授粉算法在大規模路徑規劃問題上的有效性和求解最小最優解的優越性，選取國內外通用測試的車輛路徑問題的算例庫VRPLIB中的四個數據集進行實驗。實驗結果如表4所示。

表4 四種測試集實驗結果

由表4可以看出對于配送點小于22個的配送情況，改進后的算法能找到最小路徑，對于30個以上點的數據沒有找到最優路徑，但尋得的最優解已很接近已知最優解，驗證了本文提出的算法的可靠性。

進一步選取E-n33-k4數據測試集合，將本文優化算法和標準的ABC算法和FPA算法進行對比。由實驗數據可以得出：當種群和迭代次數較小的時候，三種算法之間的最短路徑的值差異也較大；隨著種群和迭代次數的增加，同種算法得到的最短路徑差異越小；當種群的大小和迭代次數都達到峰值后，初始設置條件影響能力變弱。本文提出的改進算法在大規模測試實例下仍然都保持了較好的尋優性能。

圖1給出了本文提出的改進算法和FPA以及ABC在種群大小為100和迭代次數為1000的情況下對實例E-n33-k4進行實驗的收斂曲線圖。

圖1 E-n33-k4的收斂曲線圖

由以上數據結果顯示，改進后的花朵授粉優化算法趨于穩定的最短路徑的速度要明顯較其他兩種優化算法更快，最優的總路徑值也比其他兩種優化算法更短。

當種群大小為100，迭代次數為1000時，獨立運行10次實驗，最優路徑的詳細路圖如圖2所示。

圖2 E-n33-k4的車輛路線

5 結語

本文首先針對標準花朵授粉算法存在容易局部最優以及演化后期收斂速度過慢的缺陷，提出將人工蜂群算法的采蜜階段和偵查階段引入FPA來達到提高花朵授粉的優化能力和尋優能力的目的。然后利用改進后的花朵授粉算法對車輛路徑問題進行求解，得到了較為優異的實驗結果，但對于更大規模的車輛路徑問題，還不能驗證本文提出的優化算法的有效性。因此，進一步研究本文提出的花朵授粉優化算法在大規模車輛路徑問題上的有效性是后續研究的方向和重點。