陳文卓，姜 豐，劉 萍

(華北科技學(xué)院 電子信息工程系，河北 廊坊 065201)

易腐農(nóng)產(chǎn)品（如肉類、瓜果蔬菜、奶制品等），具有保質(zhì)期短、易腐爛、易滋生細(xì)菌的特點(diǎn)，同時(shí)隨著經(jīng)濟(jì)水平的提高，食品安全意識(shí)和環(huán)保意識(shí)逐漸增強(qiáng)，消費(fèi)者在購(gòu)買產(chǎn)品的時(shí)候不僅關(guān)注其價(jià)格，而且更加注重食品的新鮮及安全程度［1-3］。同時(shí)結(jié)合目前新型冠狀肺炎病毒的研究進(jìn)展，發(fā)現(xiàn)集中進(jìn)行動(dòng)物宰殺和農(nóng)產(chǎn)品售賣的華南海鮮市場(chǎng)是疫情初期擴(kuò)散的主要源頭之一。若將此類易腐農(nóng)產(chǎn)品的宰殺和售賣分開(kāi)進(jìn)行，并科學(xué)合理地規(guī)劃配送，不但能夠極大地降低病毒細(xì)菌的危害、最大程度地保障新鮮程度，還能實(shí)現(xiàn)十三五“節(jié)能減排、綠色發(fā)展”的目標(biāo)［4］。

在路徑規(guī)劃方面，羅顯躍［5］提出了1 種在柵格地圖的基礎(chǔ)上利用參數(shù)可調(diào)勢(shì)場(chǎng)法對(duì)巡檢機(jī)器人的避障路徑進(jìn)行智能規(guī)劃的方法，提高了路徑規(guī)劃的效率和準(zhǔn)確性；孫小軍［6］在蟻群算法中加入時(shí)間成本懲戒值，通過(guò)尋求懲戒值的最小解從而得到最優(yōu)路徑；郭詠梅等［7］將人工魚群算法與蟻群算法結(jié)合，在蟻群算法中引入擁擠度因子來(lái)引導(dǎo)蟻群進(jìn)行聚集，從而提高了該算法在求解帶時(shí)間窗路徑規(guī)劃問(wèn)題上的效率；劉云等［8］將基本蟻群算法和單親遺傳算法相結(jié)合，利用單親遺傳算法的特點(diǎn)，構(gòu)建了求解帶時(shí)間窗路徑規(guī)劃問(wèn)題混合蟻群算法，實(shí)驗(yàn)表明算法具有較高的穩(wěn)定性；黃震等［9］將蟻群算法和遺傳算法相結(jié)合，通過(guò)蟻群算法產(chǎn)生初始種群，然后進(jìn)行交叉和變異操作，從而得有效結(jié)果。

在考慮成本的實(shí)際應(yīng)用方面，MA［10］提出1 種基于時(shí)變性的考慮訂單選擇的路徑模型平臺(tái)，加入了時(shí)間窗的限制;邵舉平［11］提出多目標(biāo)生鮮農(nóng)產(chǎn)品配送路徑規(guī)劃的優(yōu)化模型，結(jié)合時(shí)效性的特點(diǎn)，同時(shí)綜合考慮了含配送成本和客戶滿意度在內(nèi)的2 個(gè)目標(biāo)的實(shí)現(xiàn)。

以上文獻(xiàn)分別研究了移動(dòng)空間的解決方案、改進(jìn)算法的效率問(wèn)題以及不同任務(wù)目標(biāo)的模型搭建，雖然能夠解決不同條件影響下的具體問(wèn)題，但是都沒(méi)能簡(jiǎn)單有效地解決綜合成本限制下的含有時(shí)間窗的路徑規(guī)劃。且上述方案中算法收斂不夠迅速，螞蟻容易陷入局部最優(yōu)。因此，筆者改進(jìn)了蟻群算法轉(zhuǎn)移規(guī)則，通過(guò)加入含有時(shí)間啟發(fā)因子的影響函數(shù)，從而提高算法的收斂速度，避免局部最優(yōu)問(wèn)題。同時(shí)考慮以固定成本、運(yùn)輸成本和罰沒(méi)成本為約束進(jìn)行路徑建模，在多目標(biāo)易腐農(nóng)產(chǎn)品配送路徑規(guī)劃的應(yīng)用中，該改進(jìn)算法表現(xiàn)出優(yōu)異的性能，路徑規(guī)劃準(zhǔn)確性極大提高，成本控制合理。

1 蟻群算法數(shù)學(xué)模型

目前針對(duì)路徑規(guī)劃研究有蟻群算法、A*算法、禁忌搜索算法、遺傳算法等，其中蟻群算法模仿自然界中螞蟻通過(guò)群體合作尋覓食物來(lái)進(jìn)行最短路徑的啟發(fā)式計(jì)算，具有正反饋、分布式計(jì)算和貪婪的啟發(fā)式搜索等特點(diǎn)，同時(shí)其強(qiáng)大的隨機(jī)搜索能力和較好的耦合性使之易于和其他算法結(jié)合，為更好地解決組合優(yōu)化類問(wèn)題提供了可能［12］。 該算法主要解決的是從某一點(diǎn)出發(fā)，遍歷所有目的地，再回到起點(diǎn)的最短路徑問(wèn)題。

算法原理依據(jù)的是：螞蟻在覓食過(guò)程中，將在經(jīng)過(guò)的路徑上釋放信息素，這種物質(zhì)會(huì)隨著時(shí)間的推移逐漸揮發(fā)，螞蟻將感知到的信息素濃度作為決定自己前往下一地點(diǎn)的主要依據(jù)。較短路徑上的螞蟻往返的次數(shù)更多，所以信息素濃度更大，從而使得更多的螞蟻能夠發(fā)現(xiàn)最佳的路徑［13］。

因此蟻群算法的數(shù)學(xué)模型可以描述為，將m只螞蟻隨機(jī)放在n個(gè)地點(diǎn)上，地點(diǎn)編號(hào)依次為(1,2,…,n)，螞蟻從所處地點(diǎn)的當(dāng)前時(shí)刻T開(kāi)始對(duì)目的地進(jìn)行遍歷。

根據(jù)蟻群算法的原理，螞蟻按照轉(zhuǎn)移規(guī)則P選擇下一個(gè)目的地，轉(zhuǎn)移規(guī)則為：

式中：Pij表示從地點(diǎn)i選擇地點(diǎn)j的轉(zhuǎn)移概率，τij表示從地點(diǎn)i到j(luò)路徑上的信息素濃度，且τij初始值均為1。α為信息素的權(quán)重，表示當(dāng)前路徑上的信息素濃度對(duì)螞蟻選擇的重要程度；β為距離啟發(fā)因子，表示視距函數(shù)在螞蟻選擇中的重要性；Uk表示螞蟻k下一步可選地點(diǎn)的集合，并設(shè)置tabUk為禁忌表，記錄螞蟻已經(jīng)走過(guò)的地點(diǎn)，防止螞蟻?zhàn)呋仡^路，在完成1 次遍歷之前，禁忌表不會(huì)被清空。螞蟻k在選擇下一個(gè)目的地時(shí)，按照輪盤隨機(jī)的方法從Uk中選擇下個(gè)訪問(wèn)的地點(diǎn)j。η表示視距函數(shù)，一般取為地點(diǎn)i到地點(diǎn)j的歐式距離dij的倒數(shù)，即：

2 轉(zhuǎn)移規(guī)則

根據(jù)上述原理，當(dāng)所有的螞蟻遍歷所有地點(diǎn)后，將對(duì)路徑上的信息素進(jìn)行更新，信息素更新公式如下：

其中ρ表示信息素?fù)]發(fā)系數(shù)，信息素會(huì)隨著時(shí)間的增加而逐漸消散，Δτij為信息素的增加量，表示為：

蟻密模型表示為：

蟻周模型可表示為：

3 改進(jìn)蟻群算法

3.1 時(shí)間啟發(fā)因子

在傳統(tǒng)解決時(shí)間窗的蟻群算法中，通常是加入懲戒值：將到達(dá)每個(gè)配送點(diǎn)的實(shí)際時(shí)間與該點(diǎn)的時(shí)間窗進(jìn)行比較，根據(jù)計(jì)算的差值獲得相應(yīng)的懲戒值；即如果到達(dá)該配送點(diǎn)的時(shí)間超過(guò)時(shí)間窗的最遲開(kāi)放時(shí)間，則懲戒值為達(dá)到時(shí)間與最遲開(kāi)放時(shí)間差值的絕對(duì)值；如果到達(dá)的時(shí)間早于該點(diǎn)的最早開(kāi)放時(shí)間，則懲戒值為最早開(kāi)放時(shí)間與到達(dá)時(shí)間差值的絕對(duì)值。經(jīng)過(guò)多次迭代后，篩選出懲戒值最小的作為最優(yōu)解。但是影響螞蟻選擇下一個(gè)地點(diǎn)的因素是信息素濃度和視距函數(shù)，累計(jì)的懲戒值并沒(méi)有影響螞蟻對(duì)下一地點(diǎn)（前進(jìn)方向）的選擇，所以導(dǎo)致螞蟻在移動(dòng)的時(shí)候并沒(méi)有考慮到時(shí)間窗的限制，因此傳統(tǒng)算法在收斂速度上有所欠缺。針對(duì)該問(wèn)題，文本提出了在轉(zhuǎn)移規(guī)則中加入時(shí)間啟發(fā)函數(shù)進(jìn)行改進(jìn)。

因此如果從地點(diǎn)i出發(fā)，而到達(dá)地點(diǎn)j的時(shí)間不在地點(diǎn)j的開(kāi)放時(shí)間內(nèi)的話，則可以通過(guò)時(shí)間啟發(fā)函數(shù)來(lái)降低不符合時(shí)間限制的路徑被其它螞蟻選擇的概率，因此不需要遍歷所有地點(diǎn)，僅通過(guò)對(duì)改進(jìn)算法進(jìn)行重復(fù)迭代，就可以快速得到路徑的最優(yōu)解。

3.2 改進(jìn)蟻群算法步驟

通過(guò)以上分析，結(jié)合式（1），得到加入時(shí)間啟發(fā)因子后的新的轉(zhuǎn)移規(guī)則為：

其中，Cij為改進(jìn)算法中增加的時(shí)間啟發(fā)函數(shù)，γ為時(shí)間啟發(fā)因子，表示時(shí)間窗限制在螞蟻選擇下一地點(diǎn)時(shí)的重要性，為了凸顯出時(shí)間在螞蟻選擇路徑時(shí)的重要性，設(shè)置γ＞α，γ＞β。

因此改進(jìn)后算法執(zhí)行的步驟如下，如圖1 所示。

（1）初始化算法各參數(shù)值，包括信息素權(quán)重α，距離啟發(fā)因子β等；

（2）清空禁忌列表tabUk并設(shè)定配送任務(wù)的起始時(shí)間T為0；

（3）根據(jù)式（10）每只螞蟻選擇下一個(gè)配送地點(diǎn)，并將該點(diǎn)加入禁忌列表；

（4）所有配送地點(diǎn)都被訪問(wèn)過(guò)后更新信息素，完成1 次迭代；

（5）將當(dāng)前最優(yōu)螞蟻?zhàn)鳛樽顑?yōu)解，同時(shí)更新當(dāng)前最短路徑值D；

（6）重復(fù)步驟2 到步驟5 的操作，直到迭代次數(shù)達(dá)到2 000 次，輸出最終的最優(yōu)解。

圖1 改進(jìn)蟻群算法流程圖Fig.1 Flow chart of improved ant colony algorithm

4 易腐農(nóng)產(chǎn)品配送路徑模型

研究以1 個(gè)配送加工中心為例，使用m輛相同種類的車輛，為n個(gè)配送點(diǎn)進(jìn)行易腐農(nóng)產(chǎn)品的配送路徑問(wèn)題。在此路徑規(guī)劃中，不但要保證在規(guī)定時(shí)間范圍內(nèi)到達(dá)并按計(jì)劃服務(wù)時(shí)間完成配送，而且需要在最低開(kāi)銷和最短路徑之間進(jìn)行平衡。因此需要建立考慮時(shí)間窗，且以客戶實(shí)際需求、車輛運(yùn)行成本為約束條件，綜合成本最小為目標(biāo)的配送路徑模型。

問(wèn)題假設(shè)

（1）每個(gè)配送點(diǎn)都能夠到達(dá)，且僅由1 輛車完成配送任務(wù)；

（2）配送車在運(yùn)送過(guò)程中勻速運(yùn)行，完成任務(wù)后返回出發(fā)點(diǎn)即配送加工中心；

（3）每個(gè)配送點(diǎn)地理位置、開(kāi)放配送的時(shí)間和服務(wù)限制時(shí)間已知，同時(shí)不考慮裝載時(shí)間。

在國(guó)家“十三五”提倡綠色、低碳、環(huán)保的經(jīng)濟(jì)背景下，為全面反映實(shí)際配送中的情況，在此考慮的易腐農(nóng)產(chǎn)品配送的綜合成本包括固定成本、運(yùn)輸成本、罰沒(méi)成本。

固定成本C1指配送車輛保險(xiǎn)、維修保養(yǎng)、日常損耗、司機(jī)工資，該項(xiàng)成本與其他變量無(wú)關(guān)，如式（11）所示：

其中v表示配送車輛數(shù)，f表示平均每輛車的固定成本，sv=1 表示第v輛配送車被使用，sv=0 則表示未被使用。

運(yùn)輸成本C2指的是運(yùn)送過(guò)程中產(chǎn)生的燃油損耗，在考慮勻速運(yùn)行問(wèn)題假設(shè)情況下，該成本將僅與距離有關(guān)，如式（12）所示：

罰沒(méi)成本C3指超出時(shí)間窗和服務(wù)時(shí)間限制所產(chǎn)生的的費(fèi)用，如式（13）所示：

其中ω為超時(shí)單位時(shí)間罰款額，tiv表示第v輛車到達(dá)配送目的地i的時(shí)刻，bi為時(shí)間窗［ai，bi］中的到達(dá)截止時(shí)間。

綜上所述，易腐農(nóng)產(chǎn)品配送路徑模型為：

以式（14）為目標(biāo)函數(shù)，同時(shí)滿足以下式子的約束。其中式（15）表示配送車完成配送后返回加工配送中心，式（16）表示加工配送中心有m輛同種類型車，且每個(gè)配送點(diǎn)最多由1 輛車完成配送，式（17）表示共計(jì)有n個(gè)配送目的地需要提供服務(wù)，式（18）表示配送車進(jìn)行服務(wù)卸貨操作的時(shí)間滿足配送目的地的時(shí)間限制。

5 仿真實(shí)驗(yàn)

以河北省廊坊市某加工配送公司為例，設(shè)其作為中心，編號(hào)為 9，進(jìn)行等比例縮放后坐標(biāo)為（46.1，42.1），m輛配送車每天早晨6 點(diǎn)從配送中心出發(fā)，開(kāi)始進(jìn)行配送，地點(diǎn)編號(hào)、坐標(biāo)、開(kāi)放配送時(shí)間、服務(wù)限制時(shí)間如表1 所示。配送車需在指定時(shí)間范圍，從配送中心出發(fā)，完成對(duì)其他18 個(gè)目標(biāo)配送點(diǎn)易腐農(nóng)產(chǎn)品的運(yùn)輸及配送服務(wù)。

表1 配送地點(diǎn)坐標(biāo)及信息Table 1 Coordinate and information of distribution sites

模型中參數(shù)設(shè)定分別為：配送車的固定成本為300，假設(shè)每條路上時(shí)間花費(fèi)相同。同時(shí)，設(shè)置開(kāi)始時(shí)間T=6，螞蟻數(shù)m=30，蟻群算法中各參數(shù)初始值為Q=100，α=1，β=2，ρ=0.5；路徑模型中參數(shù)分別為：f=300，OCij=5.5，w=50。同時(shí)為了突出時(shí)間啟發(fā)函數(shù)的權(quán)重，設(shè)置γ=10， 在Python 中分別用遺傳算法、傳統(tǒng)蟻群算法和改進(jìn)蟻群算法對(duì)上述地點(diǎn)編程，并進(jìn)行對(duì)照實(shí)驗(yàn)仿真，結(jié)果如表2 和 圖2 ～5 所示。

表2 各種算法求解結(jié)果Table 2 Results of the different algorithms

通過(guò)表2 可以看出，雖然遺傳算法求解得到的路徑長(zhǎng)度最終解和平均值分別為34.73 和36.22，與此對(duì)應(yīng)的基本蟻群算法2 類解分別為48.67，改進(jìn)蟻群算法為48.44，在此維度上遺傳算法最優(yōu)。但是通過(guò)表2 還可以看出，改進(jìn)蟻群算法的平均迭代次數(shù)和標(biāo)準(zhǔn)差均為最小，分別比遺傳算法減少2 次迭代、標(biāo)準(zhǔn)差減小5.1，比基本蟻群算法減少了53 次迭代、標(biāo)準(zhǔn)差減小27.5。因此綜上分析，證明了改進(jìn)蟻群算法在收斂速度和穩(wěn)定性上均優(yōu)于其他兩者。同時(shí)圖2 ～4 給出了這3 種算法的路徑規(guī)劃圖。

圖2 遺傳算法路徑圖Fig.2 Genetic algorithm path planning

圖3 基本蟻群算法路徑圖Fig.3 Ant colony algorithm path planning

圖4 改進(jìn)蟻群算法路徑圖Fig.4 Improved ant colony algorithm path planning

根據(jù)圖2 ～4 所示路徑，結(jié)合易腐農(nóng)產(chǎn)品配送路徑模型對(duì)算法的效率和性能進(jìn)行驗(yàn)證，針對(duì)表1中的數(shù)據(jù)對(duì)3 種算法分別進(jìn)行100 次迭代實(shí)驗(yàn)，通過(guò)對(duì)比算法達(dá)到綜合成本最優(yōu)解時(shí)迭代次數(shù)，得到其效率上的差異，實(shí)驗(yàn)結(jié)果對(duì)比如圖5 所示。使用遺傳算法進(jìn)行路徑規(guī)劃得到的綜合成本最高，迭代次數(shù)居中；雖然基本蟻群算法和改進(jìn)蟻群算法最終綜合成本相同，但前者需要更長(zhǎng)的時(shí)間才能得到此最優(yōu)解。

圖5 迭代次數(shù)及收斂速度對(duì)比Fig.5 Comparison of total cost and iteration times

綜上所述，盡管改進(jìn)蟻群算法在路徑規(guī)劃中未能取得短路徑，但能快速收斂，迭代次數(shù)最小，標(biāo)準(zhǔn)差最小，且其獲得的綜合總成本求解值最小。因此在考慮綜合成本最小的路徑規(guī)劃模型中，改進(jìn)蟻群算法效果最優(yōu)。

6 結(jié)論

筆者通過(guò)在基本蟻群算法轉(zhuǎn)移規(guī)則中加入時(shí)間啟發(fā)因子，從而改進(jìn)了算法核心結(jié)構(gòu)。并考慮以固定成本、油耗和罰沒(méi)成本為約束，且綜合配送成本最小為目標(biāo)，通過(guò)對(duì)算例中加工配送公司進(jìn)行仿真實(shí)驗(yàn)，對(duì)比驗(yàn)證了改進(jìn)蟻群算法能夠有效進(jìn)行易腐農(nóng)產(chǎn)品配送徑規(guī)劃，且與其他考慮時(shí)間窗的路徑規(guī)劃解決方案相比，其設(shè)計(jì)的復(fù)雜度更低，收斂更快、效率高、穩(wěn)定性強(qiáng)、且效果最優(yōu)。后續(xù)研究可以增加考慮實(shí)際道路交通狀況及突發(fā)情況下對(duì)易腐食品配送路徑的影響。