基于改進(jìn)花朵授粉算法的車輛路徑問(wèn)題研究*

黃佳艷 程 科

（江蘇科技大學(xué)計(jì)算機(jī)學(xué)院 鎮(zhèn)江 212000）

1 引言

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

2012年，花朵授粉算法（Flower Pollination Algorithm，F(xiàn)PA）由Yang［7］提出，它的核心思想是模擬自然界中花朵兩種授粉的模式，是一種新隨機(jī)優(yōu)化算法。FPA因?yàn)樾枨笳{(diào)節(jié)的參數(shù)少，因此具有容易進(jìn)行調(diào)節(jié)、代碼實(shí)現(xiàn)起來(lái)較為簡(jiǎn)單等優(yōu)點(diǎn)，轉(zhuǎn)換概率參數(shù)p能夠有效地調(diào)節(jié)全局和局部之間的平衡，受到了國(guó)內(nèi)外學(xué)者的關(guān)注和研究：肖輝輝等［8～9］融合了差分算法和FPA算法，并且對(duì)移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題進(jìn)行了驗(yàn)證；劉敏［10］在傳統(tǒng)FPA算法中加入遺傳算法的交叉和變異操作，對(duì)中等規(guī)模的物流配送中心選址問(wèn)題交出了答案。基于FPA在求解路徑規(guī)劃上具有的優(yōu)勢(shì)，故考慮將FPA用于VRP的求解。

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

2 改進(jìn)的花朵授粉算法

2.1 花朵授粉算法

自然界中，一個(gè)植株可以開(kāi)好幾朵多花，一朵花可以產(chǎn)生許多花配子，但是FPA中為了簡(jiǎn)便的計(jì)算，假設(shè)一棵植物有一朵花，一朵花有一個(gè)配子，一個(gè)配子是一個(gè)候選解，并且總結(jié)以下四個(gè)理想的規(guī)則。

規(guī)則一：全局搜索行為對(duì)應(yīng)異花傳粉，并且通過(guò)列維飛行的機(jī)制實(shí)現(xiàn)全局授粉；

規(guī)則二：局部搜索行為，或局部授粉對(duì)應(yīng)的為非生物自花授粉；

規(guī)則三：花的穩(wěn)定性（也就是說(shuō)，一個(gè)特定的傳粉者只給一個(gè)特定的植物傳粉）可以被認(rèn)為是花的繁殖概率，與兩種花的相似性成比例；

規(guī)則四：轉(zhuǎn)換概率參數(shù)p∈（0，1），來(lái)平衡全局授粉和局部授粉。p是算法中重要的一個(gè)參數(shù)。

該算法的全局授粉行為由式（1）實(shí)現(xiàn)，局部授粉行為由式（3）實(shí)現(xiàn)：

其中：λ=3/2，Γ（λ）是標(biāo)準(zhǔn)的伽瑪函數(shù)。

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

2.2.1 人工蜂群算法

ABC算法是以蜜蜂采蜜為原型提出的一種智能算法，食物源位置對(duì)應(yīng)求解問(wèn)題的可行性解，其花粉數(shù)量的多少對(duì)應(yīng)解的適應(yīng)度，因?yàn)樗惴▋?yōu)秀的個(gè)體尋優(yōu)能力，受到很多關(guān)注［13～15］。在算法的搜索過(guò)程中，第一需要對(duì)算法進(jìn)行初始化，包括確定當(dāng)前種群數(shù)目、算法的最大循環(huán)次數(shù)、最大搜索次數(shù)以及確定解的搜索空間。初始化后，在三種蜜蜂的作用下進(jìn)行搜尋，不斷的迭代循環(huán)，直到算法達(dá)到最大次數(shù)或者算法最佳解的精確度達(dá)到誤差范圍內(nèi)。

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

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

雇傭蜂在其記錄的對(duì)應(yīng)解xi的鄰域內(nèi)通過(guò)式（5）搜索新的解vi，再利用式（6）計(jì)算其適應(yīng)度值并進(jìn)行越界處理。

2.2.2 改進(jìn)的花朵授粉算法

針對(duì)FPA算法的缺點(diǎn)，本文將ABC算法的采蜜搜索階段和偵查尋優(yōu)階段融合到FPA算法中，將傳統(tǒng)的FPA算法中輸出的最佳解和適應(yīng)度值輸入到第二階段ABC算法，提出一種FPA優(yōu)化算法，即ABCFPA算法，以達(dá)到提高FPA的收斂到最優(yōu)解的速度和找到最優(yōu)解的能力的目的。

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

偵查蜂尋優(yōu)階段：獲取當(dāng)前全部的解并按照解的適應(yīng)度值高低對(duì)應(yīng)的概率，選擇一個(gè)解，公式如式（7）所示：

當(dāng)對(duì)應(yīng)解的適應(yīng)度值越高，那么這個(gè)解的被選擇到的概率就越大，而當(dāng)位置i的解在迭代過(guò)程中未更新的次數(shù)超過(guò)設(shè)定值之后，這個(gè)解將被舍棄，并由偵查蜂重新生成一個(gè)隨機(jī)解來(lái)代替，使算法從局部最優(yōu)中跳出來(lái)。

則ABCFPA算法具體實(shí)現(xiàn)步驟如下。

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

Step2：計(jì)算當(dāng)前種群的適應(yīng)度值并記下當(dāng)前全局的最優(yōu)值及其對(duì)應(yīng)的適應(yīng)度值；

Step3：算法進(jìn)行主體循環(huán)，若p＞rand，則按式（1）對(duì)當(dāng)前解進(jìn)行更新，并進(jìn)行越界處理，否則轉(zhuǎn)step4；

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

Step5：利用ABC算法的式（4）對(duì)step3或者step4中的解進(jìn)行搜索更新，并算出它的適應(yīng)度值；

Step6：利用ABC算法的式（5）在食物源的鄰域內(nèi)循環(huán)進(jìn)行搜索，產(chǎn)生新解，并用式（6）計(jì)算適應(yīng)度值，并進(jìn)行越界處理；

Step7：若step7超過(guò)了limit，那么生成偵查蜂，放棄該解，轉(zhuǎn)step3，否則step9；

Step8：計(jì)算sizepopmax個(gè)種群的最優(yōu)適應(yīng)度值和對(duì)應(yīng)的最優(yōu)解，若其優(yōu)于全局最優(yōu)值，則更新全局最優(yōu)解郁全局最優(yōu)值；

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

3 車輛路徑問(wèn)題的數(shù)學(xué)模型

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

變量Cij為車輛從一個(gè)配送點(diǎn)i駛向另一個(gè)一個(gè)配送點(diǎn)j所需要的成本，數(shù)學(xué)模型如式（8）：

其中式（9）～（10）約束每個(gè)配送點(diǎn)都只有一輛車到達(dá)，式（11）車輛的運(yùn)輸容量約束，式（12）保證每個(gè)配送點(diǎn)都被訪問(wèn)，式（13）消除配送中的局部回路。

4 仿真實(shí)驗(yàn)與分析

4.1 改進(jìn)的花朵授粉算法性能分析

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

表1 FPA和ABCFPA在固定迭代次數(shù)下尋優(yōu)性能比較

由表1可以看出ABCFPA算法在固定維度下各方面的尋優(yōu)效果要好于標(biāo)準(zhǔn)FPA算法，證明了改進(jìn)后的算法在尋優(yōu)能力上的精度更高，函數(shù)1～4均能找到最優(yōu)值（精度得到10-10認(rèn)為尋優(yōu)成功）說(shuō)明了改進(jìn)后的算法能有效地避免陷入局部最優(yōu)。

4.2 小規(guī)模實(shí)例

將改進(jìn)后的ABCFPA算法用于小規(guī)模車輛路徑問(wèn)題的求解，并與文獻(xiàn)［17］～［19］中的算法結(jié)果進(jìn)行效果對(duì)比。假設(shè)，有一個(gè)配送中心，配送車輛為2輛，每輛8噸，配送點(diǎn)為8個(gè)。配送中心與各配送點(diǎn)之間的距離以及各配送點(diǎn)所需要的貨物數(shù)量如表2所示（其中數(shù)字0表示配送中心）。求解目標(biāo)為運(yùn)輸總路徑最短。

表2 配送中心與配送點(diǎn)之間的距離及需求

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

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

表3 小規(guī)模實(shí)例實(shí)驗(yàn)結(jié)果

4.3 大規(guī)模實(shí)例

為了驗(yàn)證改進(jìn)后的花朵授粉算法在大規(guī)模路徑規(guī)劃問(wèn)題上的有效性和求解最小最優(yōu)解的優(yōu)越性，選取國(guó)內(nèi)外通用測(cè)試的車輛路徑問(wèn)題的算例庫(kù)VRPLIB中的四個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如表4所示。

表4 四種測(cè)試集實(shí)驗(yàn)結(jié)果

由表4可以看出對(duì)于配送點(diǎn)小于22個(gè)的配送情況，改進(jìn)后的算法能找到最小路徑，對(duì)于30個(gè)以上點(diǎn)的數(shù)據(jù)沒(méi)有找到最優(yōu)路徑，但尋得的最優(yōu)解已很接近已知最優(yōu)解，驗(yàn)證了本文提出的算法的可靠性。

進(jìn)一步選取E-n33-k4數(shù)據(jù)測(cè)試集合，將本文優(yōu)化算法和標(biāo)準(zhǔn)的ABC算法和FPA算法進(jìn)行對(duì)比。由實(shí)驗(yàn)數(shù)據(jù)可以得出：當(dāng)種群和迭代次數(shù)較小的時(shí)候，三種算法之間的最短路徑的值差異也較大；隨著種群和迭代次數(shù)的增加，同種算法得到的最短路徑差異越小；當(dāng)種群的大小和迭代次數(shù)都達(dá)到峰值后，初始設(shè)置條件影響能力變?nèi)酢１疚奶岢龅母倪M(jìn)算法在大規(guī)模測(cè)試實(shí)例下仍然都保持了較好的尋優(yōu)性能。

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

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

由以上數(shù)據(jù)結(jié)果顯示，改進(jìn)后的花朵授粉優(yōu)化算法趨于穩(wěn)定的最短路徑的速度要明顯較其他兩種優(yōu)化算法更快，最優(yōu)的總路徑值也比其他兩種優(yōu)化算法更短。

當(dāng)種群大小為100，迭代次數(shù)為1000時(shí)，獨(dú)立運(yùn)行10次實(shí)驗(yàn)，最優(yōu)路徑的詳細(xì)路圖如圖2所示。

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

5 結(jié)語(yǔ)

本文首先針對(duì)標(biāo)準(zhǔn)花朵授粉算法存在容易局部最優(yōu)以及演化后期收斂速度過(guò)慢的缺陷，提出將人工蜂群算法的采蜜階段和偵查階段引入FPA來(lái)達(dá)到提高花朵授粉的優(yōu)化能力和尋優(yōu)能力的目的。然后利用改進(jìn)后的花朵授粉算法對(duì)車輛路徑問(wèn)題進(jìn)行求解，得到了較為優(yōu)異的實(shí)驗(yàn)結(jié)果，但對(duì)于更大規(guī)模的車輛路徑問(wèn)題，還不能驗(yàn)證本文提出的優(yōu)化算法的有效性。因此，進(jìn)一步研究本文提出的花朵授粉優(yōu)化算法在大規(guī)模車輛路徑問(wèn)題上的有效性是后續(xù)研究的方向和重點(diǎn)。