基于GIS的農(nóng)資物流配送線路優(yōu)化算法研究

李昱

摘 要：農(nóng)資物流具有較大配送復(fù)雜性，物流成本居高不下，本文引入GIS路線規(guī)劃功能，結(jié)合了經(jīng)典的三類優(yōu)化算法，提出了混合算法，算法獲得最優(yōu)路線效率更高，并且通過算例對(duì)GIS下混合算法的有效性。

關(guān)鍵詞：GIS;農(nóng)資物流;物流配送;混合算法

傳統(tǒng)農(nóng)資物流包括農(nóng)業(yè)生產(chǎn)資料（農(nóng)藥、化肥、農(nóng)具與其他原材料）的運(yùn)輸、存儲(chǔ)等過程，信息化的推進(jìn)催生了現(xiàn)代農(nóng)資物流，融入了信息處理，對(duì)農(nóng)資物流流通過程中進(jìn)行事前、事中與事后的全面控制，從而降低庫存、縮短供貨周期、減少物流配送成本耗費(fèi)，節(jié)約經(jīng)濟(jì)成本。目前，對(duì)于農(nóng)資企業(yè)，從小型作坊到大型企業(yè)有存在自營、連鎖經(jīng)營與第三方物流配送等三種主要物流模式，相對(duì)而言委托第三方更具專業(yè)性，對(duì)于物流配送成本控制更嚴(yán)格，配送規(guī)劃也更科學(xué)，而另外兩種模式缺不乏資源浪費(fèi)、規(guī)劃不科學(xué)等情形。但是，考慮到企業(yè)貿(mào)易壁壘、競爭關(guān)系與商業(yè)機(jī)密等因素，不少農(nóng)資商戶還是選擇了如自營等耗費(fèi)大成本的物流配送方式。

那么，不管何種模式，農(nóng)資物流配送的成本浪費(fèi)最多體現(xiàn)在哪個(gè)節(jié)點(diǎn)呢？不少學(xué)者認(rèn)為物流配送成本增加很大程度上體現(xiàn)在配送線路規(guī)劃不合理，導(dǎo)致繞遠(yuǎn)路，近路堵塞時(shí)間、油耗成本高，空車運(yùn)輸?shù)惹樾?。在路徑?guī)劃中，一個(gè)好的規(guī)劃算法起到?jīng)Q定性作用，研究中主流的算法有遺傳算法、爬山算法與蟻群算法等，該三類算法各有特色，都有不足，并且對(duì)于動(dòng)態(tài)道路信息不適應(yīng)，GIS技術(shù)可以較好地提供道路實(shí)時(shí)信息，提供較好的線路展示功能，由此，本文將結(jié)合三種算法，開發(fā)一個(gè)混合算法，裝載入GIS中，達(dá)到線路規(guī)劃達(dá)到最高效、最優(yōu)化、可視化效果。

一、農(nóng)資物流引入GIS的必要性

現(xiàn)代物流配送中80%以上都會(huì)涉及得到復(fù)雜的空間地理數(shù)據(jù)，而且農(nóng)資物流的配送數(shù)據(jù)更是涉及到時(shí)空數(shù)據(jù)轉(zhuǎn)換，具有多尺度、維度與不確定性、海量特性，對(duì)于物流數(shù)據(jù)的處理變得越來越重點(diǎn)級(jí)。GIS（Geographic Information System）具有強(qiáng)大的地理空間信息的處理與分析能力，運(yùn)用計(jì)算機(jī)與通信技術(shù)建立一個(gè)空間信息數(shù)據(jù)庫，用戶可以進(jìn)行地理信息的查詢、分析與處理，還具有預(yù)測、定位與監(jiān)測功能。具體GIS在物流中的應(yīng)用如下：

1.選址方面

GIS可以很好地整合CAD與數(shù)據(jù)庫系統(tǒng)，使得地理信息數(shù)據(jù)訪問變得非常輕松簡單，在物流配送中心選址方面可以準(zhǔn)確提供詳細(xì)定位參考數(shù)據(jù)與跳過障礙物的拓?fù)湫畔ⅲ瑢?duì)于選址決策有很大的幫助。

2.配送線路規(guī)劃

GIS支持實(shí)時(shí)的地理道路數(shù)據(jù)訪問，對(duì)于信息的處理是實(shí)時(shí)的，對(duì)于動(dòng)態(tài)線路規(guī)劃有很大的幫助。傳統(tǒng)的線路規(guī)劃往往是靜態(tài)的計(jì)算，而借助GIS可以獲取路線實(shí)況來進(jìn)行多次智能導(dǎo)航規(guī)劃，使得成本最小，配送最高效。

3.電子地圖顯示

GIS在可視化空間展示方面較強(qiáng)，對(duì)于線路配送給用戶以直觀的、交互性強(qiáng)的線路指示軟件應(yīng)用，對(duì)于物流配送的實(shí)際操作支持較好。

隨著現(xiàn)代物流追求高效運(yùn)作、成本控制與追求安全性等需求高漲，將GIS運(yùn)用于物流行業(yè)的需求也逐漸推高。將GIS引入農(nóng)資物流可以促進(jìn)物流配送線路規(guī)劃、整合資源，提高配送率，有效降低成本與提高客戶滿意度，因此，將GIS引入農(nóng)資物流具有必要性。

二、傳統(tǒng)線路規(guī)劃算法

較為經(jīng)典的優(yōu)化方法有遺傳算法、爬山算法與蟻群算法。三種算法各有優(yōu)劣，對(duì)于物流路徑規(guī)劃各有其長處，均運(yùn)用了優(yōu)化理論對(duì)最優(yōu)解進(jìn)行最優(yōu)線路求解，獲得線路規(guī)劃滿意解。

1.遺傳算法

遺傳算法運(yùn)用了生物學(xué)中的優(yōu)勝劣汰理念，模仿群體進(jìn)化獲得適應(yīng)度最強(qiáng)的解，即滿意解。算法首先將研究的對(duì)象視為多個(gè)個(gè)體，對(duì)個(gè)體進(jìn)行編碼操作，運(yùn)用適應(yīng)度函數(shù)對(duì)各個(gè)體進(jìn)行交叉、變異等遺傳操作，得到最優(yōu)解的集合，進(jìn)一步獲得逼近最優(yōu)解的滿意解。啟發(fā)式算法的有點(diǎn)在于效率高，算法通用性好。

（1）運(yùn)用二進(jìn)制方式進(jìn)行編碼。不同的編碼方式將直接影響交叉操作，進(jìn)而影響最優(yōu)解的產(chǎn)生。不同的編碼方式對(duì)進(jìn)化的效率也是有影響的，編碼方案的選定也具有一定的實(shí)踐性。

（2）初始化種群。種群初始化的好壞對(duì)于種群的進(jìn)化效率是有影響的，因此，需要提前設(shè)定相關(guān)參數(shù)，考慮到種群進(jìn)化中的影響因素，提高初始化種群的合理性，支持快速進(jìn)化。

（3）合理選擇適應(yīng)度函數(shù)。適應(yīng)度函數(shù)的選擇是遺傳算法的關(guān)鍵，偏向于某個(gè)個(gè)體會(huì)導(dǎo)致收斂過度，若忽略個(gè)體特性，又會(huì)導(dǎo)致算法不能夠及時(shí)地收斂，同樣影響效率，因此，適應(yīng)度函數(shù)的選擇至關(guān)重要，需要考慮的因素較多。

（4）選擇與交叉變異操作。以適應(yīng)度值的大小為該個(gè)體的被選擇概率進(jìn)行選擇操作，讓適應(yīng)能力最強(qiáng)的個(gè)體得以保留，將經(jīng)選擇操作留下的個(gè)體進(jìn)行交叉操作，優(yōu)勢互補(bǔ)。為了保持多樣性，進(jìn)行變異操作，隨機(jī)選擇個(gè)體進(jìn)行基因?qū)Q。

2.爬山算法

爬山算法是一種局部擇優(yōu)算法，是對(duì)深度優(yōu)先搜索算法的一種改進(jìn)，充分利用反饋信息輔助生成決策信息。該算法從開始節(jié)點(diǎn)出發(fā)，不斷地與相近的節(jié)點(diǎn)做比較，若遇到更小的值則替換原節(jié)點(diǎn)，直到遍歷完成，達(dá)到最優(yōu)值。

爬山算法通過三步完成搜索，首先是初始序列，第二步根據(jù)代價(jià)值來進(jìn)行領(lǐng)域最優(yōu)解的篩選，最后獲得最優(yōu)解。

3.蟻群算法

蟻群算法模仿了螞蟻群體覓食的行為，通過信息素的相互交流反饋獲得最優(yōu)路徑。蟻群算法是一種模擬進(jìn)化算法，其具有正反饋性與并行性特點(diǎn)，廣泛地應(yīng)用于各種網(wǎng)絡(luò)規(guī)劃與數(shù)據(jù)挖掘中。一般蟻群算法分四個(gè)步驟進(jìn)行優(yōu)化路徑求解：

（1）初始化信息。合理地分配各條線路的信息量，根據(jù)對(duì)各條線路的預(yù)估做初始化的線路信息素分配。

（2）選擇路徑。設(shè)定概率轉(zhuǎn)移函數(shù)，對(duì)于單只螞蟻選擇路徑時(shí)使用該函數(shù)進(jìn)行路徑確定，并且對(duì)已經(jīng)經(jīng)過的路徑線節(jié)點(diǎn)進(jìn)行記錄，避免重復(fù)。

（3）對(duì)于分配的信息數(shù)量進(jìn)行更新。模擬蟻群在各條線路上的信息素變化情況，根據(jù)特定策略進(jìn)行多條線路信息素更新，信息素濃的線路表明經(jīng)過的螞蟻多，此條線路更優(yōu)。endprint

（4）根據(jù)信息素的分布選擇最優(yōu)解。按照一定概率進(jìn)行局部最優(yōu)求解，在迭代次數(shù)結(jié)束時(shí)，獲取全局最優(yōu)解。

三、混合算法的提出

三種傳統(tǒng)算法獲得的均可能非最優(yōu)解，均為迭代逼近最優(yōu)解，如果目標(biāo)函數(shù)形式發(fā)生變化則需要根據(jù)實(shí)際情況制定不同的搜索范圍與規(guī)則，我們需要在迭代過程中不斷吸取有利因素，保持基本模型結(jié)構(gòu)，對(duì)搜素規(guī)則進(jìn)行改進(jìn)，開發(fā)出更加符合實(shí)際的算法。我們通過吸取三種傳統(tǒng)算法的優(yōu)點(diǎn)構(gòu)建了如下混合算法，算法主要包括兩個(gè)環(huán)節(jié)：運(yùn)用遺傳算法與爬山算法獲取各路徑的初始信息量;利用蟻群算法進(jìn)行最優(yōu)求解。

1.混合算法流程

（1）環(huán)節(jié)一步驟如下：

①設(shè)定目標(biāo)函數(shù)，成本最小、路線最短等。

②隨機(jī)生成一組編碼，選定適應(yīng)度函數(shù)。適應(yīng)度函數(shù)選擇比較關(guān)鍵，對(duì)于挑選優(yōu)勝個(gè)體起到關(guān)鍵作用。

③進(jìn)行交叉變異操作，令個(gè)體更具適應(yīng)性。

④進(jìn)行優(yōu)勝劣汰操作，融合爬山算法與輪盤賭法。判斷是否全局最優(yōu)，直至迭代結(jié)束。

（2）環(huán)節(jié)二步驟如下：

①根據(jù)步驟一獲得的最優(yōu)解進(jìn)行初始化處理，獲取信息素初始化值。并設(shè)定迭代次數(shù)對(duì)于初始化有效控制。

②將若干螞蟻置于對(duì)應(yīng)的節(jié)點(diǎn)開始遍歷，若已遍歷完所有節(jié)點(diǎn)則進(jìn)入步驟4，否則計(jì)算進(jìn)入下一節(jié)點(diǎn)的概率。

③若約束條件滿足則記錄當(dāng)前解，修改禁忌表，更新所有信息素。

④迭代至獲得最優(yōu)解，否則進(jìn)入步驟2。

2.混合算法的構(gòu)建

（1）目標(biāo)函數(shù)設(shè)定如下：

■ ? （1）

其中■，■，■分別表示車輛權(quán)重、行駛路程與等待時(shí)間權(quán)重，■表示車輛■費(fèi)用，■表示配送總路程，■表示車輛等待時(shí)間。目標(biāo)函數(shù)綜合了三種考慮，即車輛的出車、運(yùn)輸與時(shí)間三大成本，以最小化三類成本獲得綜合成本，當(dāng)綜合成本最小時(shí)我們獲得的最優(yōu)路徑才是實(shí)際物流配送中所需要的真正最理想的配送路徑。

（2）適應(yīng)度函數(shù)的選擇

適應(yīng)度函數(shù)的選擇比較關(guān)鍵，直接影響算法的性能，為了不使得收斂速度波動(dòng)較大，本文采用較為簡單的倒數(shù)方法設(shè)定適應(yīng)度函數(shù)如下：

■，其中■是以上設(shè)定的目標(biāo)函數(shù)，■為既定的權(quán)重。

（3）對(duì)蟻群算法的信息素進(jìn)行初始化

通過遺傳算法對(duì)路徑上的信息素進(jìn)行初始值設(shè)定

■ ? ? ? ? ? ? （2）

■與■分別表示運(yùn)用遺傳算法獲得的最優(yōu)解求解過程需要的信息素及求解模型中的信息素常量。

（4）轉(zhuǎn)移概率計(jì)算函數(shù)

■ ? ? ? ?（3）

其中■表示第■個(gè)個(gè)體適應(yīng)度函數(shù)，■表示■螞蟻可以前往下一節(jié)點(diǎn)。

（5）更新信息素

■（4）

其中，■表示第■步邊的■信息素，■表示信息素增量

■ ? ?（5）

其中■表示揮發(fā)信息素因子，而■則表示衰退系數(shù)。

■ ? ? ? ? ? ? ? （6）

其中，■代表信息素總量常量，■代表單只螞蟻所經(jīng)路徑長度。

根據(jù)混合算法的流程，即兩個(gè)環(huán)節(jié)8個(gè)步驟的計(jì)算，參考5個(gè)關(guān)鍵步驟，我們可以獲得農(nóng)資物流配送路徑的最優(yōu)結(jié)果，以下我們將通過一個(gè)實(shí)際算例來進(jìn)行模擬計(jì)算，比較混合算法與三類經(jīng)典算法之間的優(yōu)劣，以證明混合算法的有效性。

四、算法模擬驗(yàn)證

假設(shè)有某農(nóng)資物流配送中心，對(duì)30個(gè)不同的農(nóng)資需求點(diǎn)進(jìn)行配送，設(shè)定配送中心單車配送，負(fù)荷與其他參數(shù)都一樣，各參數(shù)設(shè)定為：群體總數(shù)為50，總迭代次數(shù)30，交叉與變異概率分別為0.7與0.07，變異的調(diào)換次數(shù)為20，爬山次數(shù)設(shè)定為30，蟻群算法的啟發(fā)式因子■設(shè)定為3，■期望值為7，■為0.7，■為0.00003，蟻群規(guī)模為50，迭代次數(shù)300次。

選擇客戶點(diǎn)P30為配送起始點(diǎn)，運(yùn)用了matlab軟件，進(jìn)行了模擬混合算法得到配送路徑，模擬結(jié)果如下。

圖中紅圈點(diǎn)為配送起始客戶節(jié)點(diǎn)，連線表示配送線路，從中可以看出配送線路較為密集的地方集中在左下方，左下方客戶節(jié)點(diǎn)分布密集，配送較為集中，花費(fèi)的時(shí)間較少，而其他地方客戶點(diǎn)較為分散，配送路徑也較為疏散。

通過運(yùn)用matlab模擬混合算法與遺傳算法，獲得算例各客戶節(jié)點(diǎn)配送路線總距離圖。按逆序先在城市配送P30-P29-P28-P27-P26五個(gè)客戶節(jié)點(diǎn)，計(jì)算兩種算法獲得總配送距離，再配送P30-P29-P28-P27-P26……P20，計(jì)算總距離，依次類推，獲得圖2。

■

圖2 兩類算法配送距離圖

通過圖2可以看出混合算法起始15個(gè)客戶點(diǎn)配送時(shí)所花費(fèi)的距離較大，到后15個(gè)客戶配送點(diǎn)是距離逐步縮短，而等全部配送完成時(shí)，總距離是各算法中最短的，花費(fèi)的成本最小。

五、結(jié)語

農(nóng)資物流配送具有大批量、復(fù)雜度高、分散分布等特點(diǎn)，對(duì)于農(nóng)資物流的配送是一個(gè)生產(chǎn)實(shí)際有待解決的問題，本文基于三種優(yōu)化算法，構(gòu)建了一種混合算法，該算法具有全局考慮，效率更高等特點(diǎn)，運(yùn)用該算法進(jìn)行最優(yōu)路徑求解，獲得了比三種經(jīng)典優(yōu)化算法更高效、距離更短的全局最優(yōu)路徑，模擬演算驗(yàn)證了混合算法的有效性。但是，本文未對(duì)多個(gè)配送點(diǎn)，動(dòng)態(tài)的配送進(jìn)行研究，而現(xiàn)實(shí)配送中可能存在多個(gè)配送點(diǎn)，多種類型的運(yùn)輸工具，組合式、動(dòng)態(tài)的配送，因此，本文研究存在一定的局限性，對(duì)于該方面的研究有待進(jìn)一步深入探討的開展。

參考文獻(xiàn)：

[1]洪運(yùn)華.現(xiàn)代農(nóng)資物流管理信息系統(tǒng)構(gòu)建研究[J].物流技術(shù)，2010， （4）.

[2]陳浩，吳潔明.基Web GIS的物流電子商務(wù)與配送網(wǎng)絡(luò)優(yōu)化集成[J].計(jì)算機(jī)與現(xiàn)代化，2005，（3）：89-92.

[3]程賜勝，蒲云虎，吳穎.集成化物流選址-路徑問題優(yōu)化模型的算法研究[J].中南林業(yè)科技大學(xué)學(xué)報(bào)，2008，28（5）：113-118.endprint

（4）根據(jù)信息素的分布選擇最優(yōu)解。按照一定概率進(jìn)行局部最優(yōu)求解，在迭代次數(shù)結(jié)束時(shí)，獲取全局最優(yōu)解。

三、混合算法的提出

三種傳統(tǒng)算法獲得的均可能非最優(yōu)解，均為迭代逼近最優(yōu)解，如果目標(biāo)函數(shù)形式發(fā)生變化則需要根據(jù)實(shí)際情況制定不同的搜索范圍與規(guī)則，我們需要在迭代過程中不斷吸取有利因素，保持基本模型結(jié)構(gòu)，對(duì)搜素規(guī)則進(jìn)行改進(jìn)，開發(fā)出更加符合實(shí)際的算法。我們通過吸取三種傳統(tǒng)算法的優(yōu)點(diǎn)構(gòu)建了如下混合算法，算法主要包括兩個(gè)環(huán)節(jié)：運(yùn)用遺傳算法與爬山算法獲取各路徑的初始信息量;利用蟻群算法進(jìn)行最優(yōu)求解。

1.混合算法流程

（1）環(huán)節(jié)一步驟如下：

①設(shè)定目標(biāo)函數(shù)，成本最小、路線最短等。

②隨機(jī)生成一組編碼，選定適應(yīng)度函數(shù)。適應(yīng)度函數(shù)選擇比較關(guān)鍵，對(duì)于挑選優(yōu)勝個(gè)體起到關(guān)鍵作用。

③進(jìn)行交叉變異操作，令個(gè)體更具適應(yīng)性。

④進(jìn)行優(yōu)勝劣汰操作，融合爬山算法與輪盤賭法。判斷是否全局最優(yōu)，直至迭代結(jié)束。

（2）環(huán)節(jié)二步驟如下：

①根據(jù)步驟一獲得的最優(yōu)解進(jìn)行初始化處理，獲取信息素初始化值。并設(shè)定迭代次數(shù)對(duì)于初始化有效控制。

②將若干螞蟻置于對(duì)應(yīng)的節(jié)點(diǎn)開始遍歷，若已遍歷完所有節(jié)點(diǎn)則進(jìn)入步驟4，否則計(jì)算進(jìn)入下一節(jié)點(diǎn)的概率。

③若約束條件滿足則記錄當(dāng)前解，修改禁忌表，更新所有信息素。

④迭代至獲得最優(yōu)解，否則進(jìn)入步驟2。

2.混合算法的構(gòu)建

（1）目標(biāo)函數(shù)設(shè)定如下：

■ ? （1）

其中■，■，■分別表示車輛權(quán)重、行駛路程與等待時(shí)間權(quán)重，■表示車輛■費(fèi)用，■表示配送總路程，■表示車輛等待時(shí)間。目標(biāo)函數(shù)綜合了三種考慮，即車輛的出車、運(yùn)輸與時(shí)間三大成本，以最小化三類成本獲得綜合成本，當(dāng)綜合成本最小時(shí)我們獲得的最優(yōu)路徑才是實(shí)際物流配送中所需要的真正最理想的配送路徑。

（2）適應(yīng)度函數(shù)的選擇

適應(yīng)度函數(shù)的選擇比較關(guān)鍵，直接影響算法的性能，為了不使得收斂速度波動(dòng)較大，本文采用較為簡單的倒數(shù)方法設(shè)定適應(yīng)度函數(shù)如下：

■，其中■是以上設(shè)定的目標(biāo)函數(shù)，■為既定的權(quán)重。

（3）對(duì)蟻群算法的信息素進(jìn)行初始化

通過遺傳算法對(duì)路徑上的信息素進(jìn)行初始值設(shè)定

■ ? ? ? ? ? ? （2）

■與■分別表示運(yùn)用遺傳算法獲得的最優(yōu)解求解過程需要的信息素及求解模型中的信息素常量。

（4）轉(zhuǎn)移概率計(jì)算函數(shù)

■ ? ? ? ?（3）

其中■表示第■個(gè)個(gè)體適應(yīng)度函數(shù)，■表示■螞蟻可以前往下一節(jié)點(diǎn)。

（5）更新信息素

■（4）

其中，■表示第■步邊的■信息素，■表示信息素增量

■ ? ?（5）

其中■表示揮發(fā)信息素因子，而■則表示衰退系數(shù)。

■ ? ? ? ? ? ? ? （6）

其中，■代表信息素總量常量，■代表單只螞蟻所經(jīng)路徑長度。

根據(jù)混合算法的流程，即兩個(gè)環(huán)節(jié)8個(gè)步驟的計(jì)算，參考5個(gè)關(guān)鍵步驟，我們可以獲得農(nóng)資物流配送路徑的最優(yōu)結(jié)果，以下我們將通過一個(gè)實(shí)際算例來進(jìn)行模擬計(jì)算，比較混合算法與三類經(jīng)典算法之間的優(yōu)劣，以證明混合算法的有效性。

四、算法模擬驗(yàn)證

假設(shè)有某農(nóng)資物流配送中心，對(duì)30個(gè)不同的農(nóng)資需求點(diǎn)進(jìn)行配送，設(shè)定配送中心單車配送，負(fù)荷與其他參數(shù)都一樣，各參數(shù)設(shè)定為：群體總數(shù)為50，總迭代次數(shù)30，交叉與變異概率分別為0.7與0.07，變異的調(diào)換次數(shù)為20，爬山次數(shù)設(shè)定為30，蟻群算法的啟發(fā)式因子■設(shè)定為3，■期望值為7，■為0.7，■為0.00003，蟻群規(guī)模為50，迭代次數(shù)300次。

選擇客戶點(diǎn)P30為配送起始點(diǎn)，運(yùn)用了matlab軟件，進(jìn)行了模擬混合算法得到配送路徑，模擬結(jié)果如下。

圖中紅圈點(diǎn)為配送起始客戶節(jié)點(diǎn)，連線表示配送線路，從中可以看出配送線路較為密集的地方集中在左下方，左下方客戶節(jié)點(diǎn)分布密集，配送較為集中，花費(fèi)的時(shí)間較少，而其他地方客戶點(diǎn)較為分散，配送路徑也較為疏散。

通過運(yùn)用matlab模擬混合算法與遺傳算法，獲得算例各客戶節(jié)點(diǎn)配送路線總距離圖。按逆序先在城市配送P30-P29-P28-P27-P26五個(gè)客戶節(jié)點(diǎn)，計(jì)算兩種算法獲得總配送距離，再配送P30-P29-P28-P27-P26……P20，計(jì)算總距離，依次類推，獲得圖2。

■

圖2 兩類算法配送距離圖

通過圖2可以看出混合算法起始15個(gè)客戶點(diǎn)配送時(shí)所花費(fèi)的距離較大，到后15個(gè)客戶配送點(diǎn)是距離逐步縮短，而等全部配送完成時(shí)，總距離是各算法中最短的，花費(fèi)的成本最小。

五、結(jié)語

農(nóng)資物流配送具有大批量、復(fù)雜度高、分散分布等特點(diǎn)，對(duì)于農(nóng)資物流的配送是一個(gè)生產(chǎn)實(shí)際有待解決的問題，本文基于三種優(yōu)化算法，構(gòu)建了一種混合算法，該算法具有全局考慮，效率更高等特點(diǎn)，運(yùn)用該算法進(jìn)行最優(yōu)路徑求解，獲得了比三種經(jīng)典優(yōu)化算法更高效、距離更短的全局最優(yōu)路徑，模擬演算驗(yàn)證了混合算法的有效性。但是，本文未對(duì)多個(gè)配送點(diǎn)，動(dòng)態(tài)的配送進(jìn)行研究，而現(xiàn)實(shí)配送中可能存在多個(gè)配送點(diǎn)，多種類型的運(yùn)輸工具，組合式、動(dòng)態(tài)的配送，因此，本文研究存在一定的局限性，對(duì)于該方面的研究有待進(jìn)一步深入探討的開展。

參考文獻(xiàn)：

[1]洪運(yùn)華.現(xiàn)代農(nóng)資物流管理信息系統(tǒng)構(gòu)建研究[J].物流技術(shù)，2010， （4）.

[2]陳浩，吳潔明.基Web GIS的物流電子商務(wù)與配送網(wǎng)絡(luò)優(yōu)化集成[J].計(jì)算機(jī)與現(xiàn)代化，2005，（3）：89-92.

[3]程賜勝，蒲云虎，吳穎.集成化物流選址-路徑問題優(yōu)化模型的算法研究[J].中南林業(yè)科技大學(xué)學(xué)報(bào)，2008，28（5）：113-118.endprint

（4）根據(jù)信息素的分布選擇最優(yōu)解。按照一定概率進(jìn)行局部最優(yōu)求解，在迭代次數(shù)結(jié)束時(shí)，獲取全局最優(yōu)解。

三、混合算法的提出

三種傳統(tǒng)算法獲得的均可能非最優(yōu)解，均為迭代逼近最優(yōu)解，如果目標(biāo)函數(shù)形式發(fā)生變化則需要根據(jù)實(shí)際情況制定不同的搜索范圍與規(guī)則，我們需要在迭代過程中不斷吸取有利因素，保持基本模型結(jié)構(gòu)，對(duì)搜素規(guī)則進(jìn)行改進(jìn)，開發(fā)出更加符合實(shí)際的算法。我們通過吸取三種傳統(tǒng)算法的優(yōu)點(diǎn)構(gòu)建了如下混合算法，算法主要包括兩個(gè)環(huán)節(jié)：運(yùn)用遺傳算法與爬山算法獲取各路徑的初始信息量;利用蟻群算法進(jìn)行最優(yōu)求解。

1.混合算法流程

（1）環(huán)節(jié)一步驟如下：

①設(shè)定目標(biāo)函數(shù)，成本最小、路線最短等。

②隨機(jī)生成一組編碼，選定適應(yīng)度函數(shù)。適應(yīng)度函數(shù)選擇比較關(guān)鍵，對(duì)于挑選優(yōu)勝個(gè)體起到關(guān)鍵作用。

③進(jìn)行交叉變異操作，令個(gè)體更具適應(yīng)性。

④進(jìn)行優(yōu)勝劣汰操作，融合爬山算法與輪盤賭法。判斷是否全局最優(yōu)，直至迭代結(jié)束。

（2）環(huán)節(jié)二步驟如下：

①根據(jù)步驟一獲得的最優(yōu)解進(jìn)行初始化處理，獲取信息素初始化值。并設(shè)定迭代次數(shù)對(duì)于初始化有效控制。

②將若干螞蟻置于對(duì)應(yīng)的節(jié)點(diǎn)開始遍歷，若已遍歷完所有節(jié)點(diǎn)則進(jìn)入步驟4，否則計(jì)算進(jìn)入下一節(jié)點(diǎn)的概率。

③若約束條件滿足則記錄當(dāng)前解，修改禁忌表，更新所有信息素。

④迭代至獲得最優(yōu)解，否則進(jìn)入步驟2。

2.混合算法的構(gòu)建

（1）目標(biāo)函數(shù)設(shè)定如下：

■ ? （1）

其中■，■，■分別表示車輛權(quán)重、行駛路程與等待時(shí)間權(quán)重，■表示車輛■費(fèi)用，■表示配送總路程，■表示車輛等待時(shí)間。目標(biāo)函數(shù)綜合了三種考慮，即車輛的出車、運(yùn)輸與時(shí)間三大成本，以最小化三類成本獲得綜合成本，當(dāng)綜合成本最小時(shí)我們獲得的最優(yōu)路徑才是實(shí)際物流配送中所需要的真正最理想的配送路徑。

（2）適應(yīng)度函數(shù)的選擇

適應(yīng)度函數(shù)的選擇比較關(guān)鍵，直接影響算法的性能，為了不使得收斂速度波動(dòng)較大，本文采用較為簡單的倒數(shù)方法設(shè)定適應(yīng)度函數(shù)如下：

■，其中■是以上設(shè)定的目標(biāo)函數(shù)，■為既定的權(quán)重。

（3）對(duì)蟻群算法的信息素進(jìn)行初始化

通過遺傳算法對(duì)路徑上的信息素進(jìn)行初始值設(shè)定

■ ? ? ? ? ? ? （2）

■與■分別表示運(yùn)用遺傳算法獲得的最優(yōu)解求解過程需要的信息素及求解模型中的信息素常量。

（4）轉(zhuǎn)移概率計(jì)算函數(shù)

■ ? ? ? ?（3）

其中■表示第■個(gè)個(gè)體適應(yīng)度函數(shù)，■表示■螞蟻可以前往下一節(jié)點(diǎn)。

（5）更新信息素

■（4）

其中，■表示第■步邊的■信息素，■表示信息素增量

■ ? ?（5）

其中■表示揮發(fā)信息素因子，而■則表示衰退系數(shù)。

■ ? ? ? ? ? ? ? （6）

其中，■代表信息素總量常量，■代表單只螞蟻所經(jīng)路徑長度。

根據(jù)混合算法的流程，即兩個(gè)環(huán)節(jié)8個(gè)步驟的計(jì)算，參考5個(gè)關(guān)鍵步驟，我們可以獲得農(nóng)資物流配送路徑的最優(yōu)結(jié)果，以下我們將通過一個(gè)實(shí)際算例來進(jìn)行模擬計(jì)算，比較混合算法與三類經(jīng)典算法之間的優(yōu)劣，以證明混合算法的有效性。

四、算法模擬驗(yàn)證

假設(shè)有某農(nóng)資物流配送中心，對(duì)30個(gè)不同的農(nóng)資需求點(diǎn)進(jìn)行配送，設(shè)定配送中心單車配送，負(fù)荷與其他參數(shù)都一樣，各參數(shù)設(shè)定為：群體總數(shù)為50，總迭代次數(shù)30，交叉與變異概率分別為0.7與0.07，變異的調(diào)換次數(shù)為20，爬山次數(shù)設(shè)定為30，蟻群算法的啟發(fā)式因子■設(shè)定為3，■期望值為7，■為0.7，■為0.00003，蟻群規(guī)模為50，迭代次數(shù)300次。

選擇客戶點(diǎn)P30為配送起始點(diǎn)，運(yùn)用了matlab軟件，進(jìn)行了模擬混合算法得到配送路徑，模擬結(jié)果如下。

圖中紅圈點(diǎn)為配送起始客戶節(jié)點(diǎn)，連線表示配送線路，從中可以看出配送線路較為密集的地方集中在左下方，左下方客戶節(jié)點(diǎn)分布密集，配送較為集中，花費(fèi)的時(shí)間較少，而其他地方客戶點(diǎn)較為分散，配送路徑也較為疏散。

通過運(yùn)用matlab模擬混合算法與遺傳算法，獲得算例各客戶節(jié)點(diǎn)配送路線總距離圖。按逆序先在城市配送P30-P29-P28-P27-P26五個(gè)客戶節(jié)點(diǎn)，計(jì)算兩種算法獲得總配送距離，再配送P30-P29-P28-P27-P26……P20，計(jì)算總距離，依次類推，獲得圖2。

■

圖2 兩類算法配送距離圖

通過圖2可以看出混合算法起始15個(gè)客戶點(diǎn)配送時(shí)所花費(fèi)的距離較大，到后15個(gè)客戶配送點(diǎn)是距離逐步縮短，而等全部配送完成時(shí)，總距離是各算法中最短的，花費(fèi)的成本最小。

五、結(jié)語

農(nóng)資物流配送具有大批量、復(fù)雜度高、分散分布等特點(diǎn)，對(duì)于農(nóng)資物流的配送是一個(gè)生產(chǎn)實(shí)際有待解決的問題，本文基于三種優(yōu)化算法，構(gòu)建了一種混合算法，該算法具有全局考慮，效率更高等特點(diǎn)，運(yùn)用該算法進(jìn)行最優(yōu)路徑求解，獲得了比三種經(jīng)典優(yōu)化算法更高效、距離更短的全局最優(yōu)路徑，模擬演算驗(yàn)證了混合算法的有效性。但是，本文未對(duì)多個(gè)配送點(diǎn)，動(dòng)態(tài)的配送進(jìn)行研究，而現(xiàn)實(shí)配送中可能存在多個(gè)配送點(diǎn)，多種類型的運(yùn)輸工具，組合式、動(dòng)態(tài)的配送，因此，本文研究存在一定的局限性，對(duì)于該方面的研究有待進(jìn)一步深入探討的開展。

參考文獻(xiàn)：

[1]洪運(yùn)華.現(xiàn)代農(nóng)資物流管理信息系統(tǒng)構(gòu)建研究[J].物流技術(shù)，2010， （4）.

[2]陳浩，吳潔明.基Web GIS的物流電子商務(wù)與配送網(wǎng)絡(luò)優(yōu)化集成[J].計(jì)算機(jī)與現(xiàn)代化，2005，（3）：89-92.

[3]程賜勝，蒲云虎，吳穎.集成化物流選址-路徑問題優(yōu)化模型的算法研究[J].中南林業(yè)科技大學(xué)學(xué)報(bào)，2008，28（5）：113-118.endprint