黃二強(qiáng)，代永強(qiáng)，劉 歡

（甘肅農(nóng)業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院，蘭州 730000）

0 引 言

隨著國(guó)家對(duì)環(huán)境保護(hù)的重視，農(nóng)業(yè)得到了飛速發(fā)展，農(nóng)產(chǎn)品的產(chǎn)量也有了全面提升，需要良好的交通運(yùn)輸路徑來(lái)激活農(nóng)村經(jīng)濟(jì)。 因?yàn)閲?guó)內(nèi)地形地貌復(fù)雜多樣，各地的農(nóng)村之間相距較遠(yuǎn)、且農(nóng)產(chǎn)品種類和產(chǎn)量也不相同，所以就需要規(guī)劃運(yùn)輸路徑的軟件，來(lái)幫助規(guī)劃路徑，車輛運(yùn)輸路線規(guī)劃已經(jīng)變得越來(lái)越重要。 相對(duì)于常規(guī)的路徑規(guī)劃算法，首先，本文中的算法彌補(bǔ)了在運(yùn)輸?shù)恼麄€(gè)環(huán)節(jié)中花費(fèi)在農(nóng)村收購(gòu)點(diǎn)等待農(nóng)產(chǎn)品的時(shí)間，因?yàn)榈乩碓颍召?gòu)商到達(dá)農(nóng)村收購(gòu)點(diǎn)后，因?yàn)椴煌貐^(qū)的果園或農(nóng)田距生活區(qū)較遠(yuǎn)，有的地勢(shì)陡峭、有的地質(zhì)松散、比較危險(xiǎn)，農(nóng)民也會(huì)在不同的時(shí)間去采摘農(nóng)產(chǎn)品，造成收購(gòu)商額外花費(fèi)的時(shí)間不同。 而常規(guī)的路徑規(guī)劃算法中只注重車輛調(diào)度花費(fèi)的時(shí)間。 其次，本文中改進(jìn)的蟻群算法融合退火算法后，提高了蟻群算法跳出局部最優(yōu)的能力和收斂速度。 再次，通過(guò)融合蜜獾算法，在計(jì)算2 個(gè)收購(gòu)點(diǎn)之間的距離時(shí)，本文考慮到農(nóng)村地形影響因素，引入蜜獾算法在挖掘階段的心形模型來(lái)計(jì)算兩點(diǎn)間的距離，此模型更適合計(jì)算農(nóng)村收購(gòu)點(diǎn)之間的距離，其距離與實(shí)際路程更接近。 而常規(guī)算法是計(jì)算連點(diǎn)間直線距離，在計(jì)算山區(qū)中2 個(gè)農(nóng)村之間的距離時(shí)，計(jì)算的直線距離與實(shí)際路程比本文中的要差。 本文選擇甘肅省若干個(gè)村鎮(zhèn)進(jìn)行路徑規(guī)劃，利用改進(jìn)的蟻群算法幫助收購(gòu)商尋找一條最佳的運(yùn)輸路徑。 運(yùn)輸路徑規(guī)劃問(wèn)題可歸于TSP［1］（traveling salesman problem）問(wèn)題，在解決TSP 問(wèn)題上，可用精確算法［2］或啟發(fā)式搜索算法［3］，如分層遞進(jìn)的改進(jìn)聚類蟻群算法［4］或者人工智能算法，如模擬退火算法［5］、蟻群算法［6］、禁忌搜索算法［7］、雞群算法［8］、粒子群算法［9］、蜂群算法［10］、麻雀搜索算法［11］以及遺傳算法［12］等。 在本文中用改進(jìn)的蟻群算法來(lái)規(guī)劃車輛運(yùn)輸路徑。 基于原始蟻群算法中跳出局部最優(yōu)的能力低［13］、收斂速度慢［14］、優(yōu)化效率低［15］的問(wèn)題，改進(jìn)的算法中，首先增加螞蟻體重突變的因素，可以提高蟻群的多樣性，從而提高蟻群算法跳出局部最優(yōu)的能力。 在螞蟻體重突變的過(guò)程中，通過(guò)結(jié)合退火算法的概率計(jì)算方法來(lái)得到當(dāng)前運(yùn)動(dòng)螞蟻的體重；其次，增加目標(biāo)地點(diǎn)的時(shí)間權(quán)重參數(shù)，可通過(guò)設(shè)置目標(biāo)點(diǎn)的時(shí)間權(quán)重值更快、更準(zhǔn)確地找出下一個(gè)地點(diǎn)，提高了蟻群算法的收斂速度。 實(shí)驗(yàn)結(jié)果表明，改進(jìn)的蟻群算法有更好的尋優(yōu)能力。

1 蟻群算法

蟻群算法是Dorigo 等學(xué)者［16］在二十世紀(jì)九十年代提出的一種新型的模擬進(jìn)化算法［17］。 通過(guò)研究發(fā)現(xiàn)螞蟻之間傳遞信息是通過(guò)一種稱為信息素的物質(zhì)，當(dāng)螞蟻在尋找食物時(shí)通過(guò)這種物質(zhì)進(jìn)行信息交互的。 螞蟻在覓食的過(guò)程中會(huì)在經(jīng)過(guò)的路徑上留下信息素，并且螞蟻也能夠感受到信息素，螞蟻會(huì)通過(guò)判斷信息素來(lái)指導(dǎo)自己運(yùn)動(dòng)的方向：若無(wú)信息素則按照隨機(jī)性前進(jìn)，若有信息素、則根據(jù)信息素的強(qiáng)度來(lái)確定自己的運(yùn)動(dòng)方向。 螞蟻會(huì)選擇信息素、濃度高的方向運(yùn)動(dòng)。 由于大量螞蟻組成的蟻群集體行為表現(xiàn)出一種信息正反饋現(xiàn)象，在某一路徑上走過(guò)的螞蟻越多，則后來(lái)者選擇該路徑的概率就越大。蟻群算法相對(duì)于其他的一些算法很有優(yōu)勢(shì)，文獻(xiàn)［18］中利用Matlab 對(duì)蟻群算法和遺傳算法對(duì)TSP的求解進(jìn)行了研究對(duì)比，研究發(fā)現(xiàn)，在若干個(gè)城市里，無(wú)論兩地之間距離多遠(yuǎn)，蟻群算法比遺傳算法更優(yōu)。 在文獻(xiàn)［19］ 中設(shè)計(jì)了一種包含改進(jìn)PRM（probabilistic road map）算法和蟻群算法的一種融合算法，可以一次規(guī)劃出多個(gè)目標(biāo)點(diǎn)的路徑，但是所規(guī)劃出來(lái)的路徑具有隨機(jī)性。 文獻(xiàn)［20］中將蟻群算法和粒子群算法對(duì)比，蟻群算法的可靠性和精確度高、適應(yīng)性強(qiáng)。在該算法中，將m只螞蟻隨機(jī)性地放在了n個(gè)城市里，全部的路徑（i，j） 上信息素的初始值△τij（0）＝常數(shù)（C），之后螞蟻k（1，…，m）在t時(shí)刻就按照其轉(zhuǎn)移概率來(lái)選擇出下一個(gè)節(jié)點(diǎn)。

2 模擬退火算法

模擬退火算法（Simulated Annealing，SA）最早的思想是由N. Metropolis 等學(xué)者［21］于1953年提出［21］。 1983年，Kirkpatrick［22］成功地將退火思想引入到組合優(yōu)化［23］領(lǐng)域。 這是基于Monte－Carlo［24］迭代求解策略的一種隨機(jī)尋優(yōu)算法［25］。 王光等學(xué)者［26］提出的算法進(jìn)行可靠性模型參數(shù)求解，具有解的全局性好、收斂速度快等優(yōu)點(diǎn)。 其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過(guò)程與一般組合優(yōu)化問(wèn)題之間的相似性。 本質(zhì)思想為以概率接受新?tīng)顟B(tài)：在溫度為T時(shí)，設(shè)當(dāng)前狀態(tài)為i，新?tīng)顟B(tài)為j，若Ej ＜Ei，則接受j為當(dāng)前狀態(tài)；否則，若概率大于［0，1） 區(qū)間的隨機(jī)數(shù)，則仍接受狀態(tài)j為當(dāng)前狀態(tài)；若不成立，則保留狀態(tài)i為當(dāng)前狀態(tài)。p ＝：在高溫下，可接受與當(dāng)前狀態(tài)能量差較大的新?tīng)顟B(tài)；在低溫下，只接受與當(dāng)前狀態(tài)能量差較小的新?tīng)顟B(tài)。 該式中的K為玻爾茲曼常量，是熱力學(xué)的一個(gè)基本常量，數(shù)值為1.380 649×10－23J／K。

3 蜜獾算法

蜜獾算法（Honey Bavdger Algorithm，HBA）是2022年提出的一種元啟發(fā)式優(yōu)化算法。 該算法的靈感來(lái)源于蜜獾的覓食行為，蜜獾會(huì)通過(guò)挖掘階段和采蜜階段尋找食物，還會(huì)根據(jù)氣味強(qiáng)弱接近獵物捕食。 該算法具有開發(fā)能力強(qiáng)、收斂速度快等特點(diǎn)，但探索能力有所不足。 研究發(fā)現(xiàn)，蜜獾算法的挖掘階段的心形模型類似于農(nóng)村收購(gòu)點(diǎn)之間的路線形狀，故而將蜜獾算法融合到農(nóng)村收購(gòu)點(diǎn)路徑優(yōu)化算法中。

4 改進(jìn)的蟻群算法

針對(duì)蟻群算法收斂速度慢的問(wèn)題，先提出對(duì)原始蟻群算法［27］的信息素優(yōu)化方法，其次討論了改進(jìn)的蟻群算法的原理。

4.1 信息素的優(yōu)化

首先，在改進(jìn)的蟻群算法中對(duì)參數(shù)信息素重要程度α和信息素啟發(fā)式因子β進(jìn)行多次實(shí)驗(yàn)得到的最優(yōu)值并將其參數(shù)值都設(shè)置為最優(yōu)值2。 其次，根據(jù)蟻群生物學(xué)［28］了解到蟻群中由工蟻、兵蟻、雄蟻、蟻后等組成，其中在工蟻或兵蟻或雄蟻中的螞蟻的個(gè)體大小和體重并不一樣，而其中更重的螞蟻對(duì)信息素時(shí)的釋放量比更輕的螞蟻釋放得更多，由此引入螞蟻的體重突變因素不僅增加了蟻群的多樣性，而且間接地影響了螞蟻釋放信息素的量；在原始蟻群算法中，信息素的釋放量是一個(gè)常量，而在改進(jìn)的蟻群算法中將其信息素改為可變的量。當(dāng)一只螞蟻從i點(diǎn)到j(luò)點(diǎn)，若從i點(diǎn)到j(luò)點(diǎn)的路徑不是最優(yōu)路徑時(shí)，由于越來(lái)越多的螞蟻的移動(dòng)將由信息素來(lái)進(jìn)行導(dǎo)向，那么從（i，j） 路徑上走過(guò)的螞蟻就越來(lái)越多，導(dǎo)致蟻群算法跳出局部最優(yōu)的能力越差。 根據(jù)下文函數(shù)（8）可以看出，可以通過(guò)蒙特卡洛準(zhǔn)則中的概率公式得到螞蟻體重突變概率F，進(jìn)而可以得到該螞蟻的體重，因?yàn)橄乱粋€(gè)農(nóng)村點(diǎn)的時(shí)間權(quán)重值越大，則該地點(diǎn)需要等待的時(shí)間越長(zhǎng)，而兩地時(shí)間權(quán)重值的差值越大，則函數(shù)（8）得到的概率值F就越小，再通過(guò)下文函數(shù)（5）可以看出，F(xiàn)越小、則螞蟻體重突變的概率越小，進(jìn)而該螞蟻釋放的信息素就越少，反之則釋放的信息素越多，最終提高了蟻群算法跳出局部最優(yōu)的能力，加快了算法的收斂速度。

4.2 算法介紹

將m只螞蟻隨機(jī)性地放在了n個(gè)城市里，路徑（i，j） 上信息素的初始值τij（0）＝0，螞蟻k（1…48）在t時(shí)刻按照其轉(zhuǎn)移概率來(lái)選擇出下一個(gè)節(jié)點(diǎn)。 通過(guò)多次實(shí)驗(yàn)測(cè)試得出，信息素重要性α的值和啟發(fā)式因子β的值分別設(shè)置為2和2，將螞蟻的體重突變作為影響啟發(fā)式因子的因素，螞蟻的體重越大，且當(dāng)前路徑的距離越短，啟發(fā)信息越大，則選擇此路徑的可能性越大；實(shí)驗(yàn)測(cè)試得出，改進(jìn)蟻群算法的收斂速度更快、得到的解更優(yōu)。 由此推得的公式為：

其中，Lij表示通過(guò)蜜獾算法的挖掘模式計(jì)算得到農(nóng)村山區(qū)路段（i，g，j）的距離，s表示螞蟻通過(guò)體重突變后的體重。 函數(shù)（2） 中考慮到山區(qū)地形因素，引入了車輛體重因素對(duì)道路順暢度的影響：車體越重的、主要考慮路線長(zhǎng)短的因素，次要考慮時(shí)間長(zhǎng)短的因素。

各個(gè)路徑所含的信息素更新公式為：

其中，1－ ρ表示信息素殘留因子，ρ∈（0，1）。

其中，△τij表示在本次所有螞蟻運(yùn)動(dòng)到目的地時(shí)，路徑（i，j） 上螞蟻的信息素總量； 在初始時(shí)刻△τij（0）＝0，指的是第k只螞蟻在此次循環(huán)時(shí)留在路徑（i，j） 上的信息素總量。 此處需用到如下公式：

首先，從函數(shù)（5）中可以看出在信息素釋放量的影響因素中添加了車輛重量因素，其車重超出標(biāo)準(zhǔn)越多、且路程越長(zhǎng)時(shí)，路段（i，j） 上釋放的信息素就越少，選中該路段的概率就越小，反之則概率越大。 其次，是通過(guò)蜜獾算法中挖掘階段的心形模型計(jì)算兩點(diǎn)之間的路程，通過(guò)該模型得到的路程更符合實(shí)際情況：

在實(shí)際情況中考察得知，農(nóng)村收購(gòu)點(diǎn)之間需要翻過(guò)山丘或者大山，其路程是弧形的、與蜜獾算法的挖掘階段的心形模型類似，在螞蟻搜尋的初始階段按照蜜獾算法中的挖掘階段的模型找到一個(gè)隨機(jī)產(chǎn)生的坐標(biāo)（xg，yg，），可以通過(guò)該模型計(jì)算2 個(gè)農(nóng)村收購(gòu)點(diǎn)（i，j） 之間的實(shí)際距離為（i，g，j），算法如下：

其中，xg為模型在經(jīng)度上的弧度；yg為模型在緯度上的弧度；α、r0、r1、r2為（0，1）的隨機(jī)數(shù)。

在此基礎(chǔ)上，又推得數(shù)學(xué)模型公式具體如下：

5 模型構(gòu)建及求解

5.1 選取48 個(gè)農(nóng)村點(diǎn)

在甘肅省內(nèi)選擇48 個(gè)農(nóng)村種植區(qū)的經(jīng)緯度作為坐標(biāo)，通過(guò)改進(jìn)的蟻群算法進(jìn)行路徑規(guī)劃。 選取的農(nóng)村種植區(qū)的坐標(biāo)見(jiàn)表1。

表1 農(nóng)村坐標(biāo)表Tab. 1 Rural coordinates

5.2 問(wèn)題分析

商貿(mào)企業(yè)在經(jīng)營(yíng)過(guò)程中以效益為首，需要開源節(jié)流，而運(yùn)輸過(guò)程中消耗的時(shí)間和資源是商貿(mào)企業(yè)支出的重要的一部分，通過(guò)對(duì)商貿(mào)企業(yè)運(yùn)輸車輛的路徑規(guī)劃可以讓商貿(mào)企業(yè)減少開支。 商貿(mào)企業(yè)在采購(gòu)農(nóng)產(chǎn)品時(shí)，首先，為了減少不必要的車程開銷，假設(shè)運(yùn)輸車輛從一個(gè)農(nóng)村點(diǎn)出發(fā)、從所有農(nóng)村點(diǎn)只經(jīng)過(guò)一次。 直至到達(dá)最后一個(gè)農(nóng)村點(diǎn)的前提下，規(guī)劃出路程最短的最優(yōu)路徑，類似旅行商問(wèn)題。 本文利用改進(jìn)的蟻群算法求解運(yùn)輸路線的最優(yōu)路徑。 其次，以收購(gòu)農(nóng)產(chǎn)品為例，計(jì)算所需天數(shù)。 不妨假設(shè)從平?jīng)?焦莊村出發(fā)，經(jīng)過(guò)所有農(nóng)村點(diǎn)、直到最后一個(gè)農(nóng)村點(diǎn)，花費(fèi)的時(shí)間包括運(yùn)輸車輛在路上的時(shí)間和在農(nóng)村點(diǎn)等待收購(gòu)所花費(fèi)的時(shí)間；根據(jù)前面求解出的最佳運(yùn)輸路徑，計(jì)算出所需的天數(shù)，并且對(duì)運(yùn)輸過(guò)程做具體的安排。

5.3 求解實(shí)例與仿真

改進(jìn)的蟻群算法給參數(shù)設(shè)定的值可以應(yīng)用到農(nóng)產(chǎn)品運(yùn)輸路徑規(guī)劃中，首先在時(shí)間權(quán)重T ＝1 時(shí)對(duì)運(yùn)輸路線進(jìn)行規(guī)劃，其次時(shí)間權(quán)重T的值分別按3種方案對(duì)運(yùn)輸路線進(jìn)行規(guī)劃。 通過(guò)實(shí)驗(yàn)得到各地點(diǎn)在3 種時(shí)間權(quán)重情況下的運(yùn)輸路徑規(guī)劃結(jié)果。

5.3.1 算法對(duì)比

首先，繪制出48 個(gè)農(nóng)村點(diǎn)的坐標(biāo)，如圖1 所示。其次，當(dāng)時(shí)間權(quán)重值T ＝1 時(shí)，求出原始蟻群算法和改進(jìn)的蟻群算法在200 次測(cè)試中每一次得到的最優(yōu)路徑長(zhǎng)度，如圖2 所示。 最后，通過(guò)對(duì)表2 中的2 種算法在最優(yōu)解、平均解和耗時(shí)三方面做對(duì)比，可以看出改進(jìn)的蟻群算法收斂速度更快、跳出局部最優(yōu)的能力更強(qiáng)、得到的解更優(yōu)，并繪制出改進(jìn)的蟻群算法求解得到的最優(yōu)路徑圖，并進(jìn)行2 種不同的展示，如圖3、圖4 所示。

圖1 48 個(gè)地點(diǎn)分布圖Fig. 1 Distribution of 48 sites

圖2 各地時(shí)間權(quán)值T ＝1 時(shí)的路徑曲線圖Fig. 2 Path curve when time weight T ＝1

圖3 無(wú)經(jīng)緯度的最優(yōu)路徑Fig. 3 Optimal path without longitude and latitude

圖4 有經(jīng)緯度的最優(yōu)路徑Fig. 4 Optimal path with longitude and latitude

表2 算法比較Tab. 2 Comparison of algorithms

5.3.2 設(shè)置時(shí)間權(quán)重表

從往年的收購(gòu)花費(fèi)時(shí)間的記錄中可以預(yù)估兩地之間從出發(fā)到完成農(nóng)產(chǎn)品收購(gòu)需要花費(fèi)的天數(shù)、即時(shí)間權(quán)重，在3 種不同的天氣給48 個(gè)農(nóng)村點(diǎn)設(shè)置時(shí)間權(quán)重值T；T ＝1 指的是運(yùn)輸車輛到達(dá)農(nóng)村時(shí)、可以立即開始收購(gòu)農(nóng)產(chǎn)品，值為1.5、表示需要等待0.5天才可以收購(gòu)農(nóng)產(chǎn)品，其余值依此類推。

5.3.3 求最優(yōu)路徑

在改進(jìn)的蟻群算法中，根據(jù)表3～表5 三個(gè)方案的時(shí)間權(quán)重值分別求出對(duì)應(yīng)的最優(yōu)路線。 經(jīng)過(guò)200 次測(cè)試，得到運(yùn)輸車輛的3 種最優(yōu)路徑，如圖5～圖7 所示。3 種策略得到的曲線如圖8 所示。 根據(jù)圖8，可以看出3 條路線的收斂速度、及最優(yōu)路徑的路徑總長(zhǎng)。 車輛央最優(yōu)路徑上花費(fèi)的時(shí)間的結(jié)果曲線如圖9 所示。 根據(jù)圖9，可以看出每輛車經(jīng)過(guò)全程所花費(fèi)的時(shí)間。

圖5 根據(jù)表2 得到的最優(yōu)路徑Fig. 5 The optimal path obtained according to Table2

圖6 根據(jù)表3 得到的最優(yōu)路徑Fig. 6 The optimal path obtained according to Table3

圖7 根據(jù)表4 得到的最優(yōu)路徑Fig. 7 The optimal path obtained according to Table4

圖8 3 種策略得到的曲線Fig. 8 Curves obtained by three strategies

圖9 車輛在最優(yōu)路徑上花費(fèi)時(shí)間的曲線Fig. 9 Curve of time spent by vehicles on the optimal path

表3 方案一的各地的時(shí)間權(quán)重值Tab. 3 Time weight value of each region in scheme I

表4 方案二的各地的時(shí)間權(quán)重值Tab. 4 Time weight values of different regions in scheme II

表5 方案三的各地的時(shí)間權(quán)重值Tab. 5 Time weight values of different regions in scheme III

5.3.4 規(guī)劃路徑的建議

從圖5～圖8 看出，可以通過(guò)設(shè)置時(shí)間權(quán)重來(lái)規(guī)劃出路徑方案，該方案可以在花費(fèi)最少的時(shí)間、農(nóng)產(chǎn)品價(jià)格最低、成熟度最好時(shí)，到達(dá)各農(nóng)村收購(gòu)和運(yùn)輸農(nóng)產(chǎn)品，通過(guò)這種方法可以消耗最少的資源來(lái)得到最大的收益。 從圖8 中可以看出紅色曲線的運(yùn)輸規(guī)劃路徑在地理順序和路程總長(zhǎng)兩方面是最優(yōu)的運(yùn)輸路徑。 經(jīng)過(guò)這48 個(gè)農(nóng)村的最佳運(yùn)輸路路徑為：2—1—3—4—5—6—7—10—8—9—11—15—13—14—12—16—18—17—21—20—19—22—23—26—25—27—28—30—29—33—36—30—31—32—34—35—39—37—47—42—44—38—45—48—46—43—41—40。 花費(fèi)總時(shí)間：3.888 9 天，實(shí)際上就是需4 天。

行程安排：要完成這些村鎮(zhèn)的農(nóng)產(chǎn)品的收購(gòu)工作，總共需要4 天。 如果企業(yè)安排收購(gòu)任務(wù)的時(shí)間比較寬裕，可以在符合時(shí)間范圍內(nèi)的規(guī)劃路徑中將天氣等因素考慮其中，如此就可以更完美地規(guī)劃運(yùn)輸路徑了。

6 結(jié)束語(yǔ)

本文提出了一種改進(jìn)的蟻群算法，并將其應(yīng)用到農(nóng)村運(yùn)輸路徑的優(yōu)化求解。 首先，在基本蟻群算法中引入了模擬退火算法的隨機(jī)概率作為螞蟻體重突變的策略的參數(shù)和時(shí)間權(quán)重參數(shù)，使算法更快地跳出局部最優(yōu)；采用螞蟻體重突變策略增強(qiáng)了種群的多樣性，提高了全局搜索能力和算法的收斂速度。 其次，根據(jù)農(nóng)村運(yùn)輸?shù)沫h(huán)境建立模型，并建立目標(biāo)函數(shù)。 最后，通過(guò)Matlab 進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明優(yōu)化蟻群算法能夠更快速地找出最優(yōu)路徑以及在運(yùn)輸過(guò)程中花費(fèi)的時(shí)間，有效提高了運(yùn)輸路徑規(guī)劃的效率。 運(yùn)輸路徑規(guī)劃受環(huán)境的影響較大，本文開展的研究未考慮天氣、高山等環(huán)境因素的影響，在以后的研究工作中將增加其他影響運(yùn)輸路徑規(guī)劃因素進(jìn)行系統(tǒng)研究。