薛 亮，黃 新，鄭 琰 XUE Liang,HUANG Xin,ZHENG Yan

（1.南京林業(yè)大學 汽車與交通工程學院，江蘇 南京 210037；2.南京林業(yè)大學 土木工程學院，江蘇 南京 210037）

(1.School of Automobile and Traffic Engineering,Nanjing Forestry University,Nanjing 210037,China;2.School of Civil Engineering,Nanjing Forestry University,Nanjing 210037,China)

0 引言

地理信息系統(tǒng)是一種用來獲取、保存、操作、探究、管理空間或地理數(shù)據(jù)的類數(shù)據(jù)庫系統(tǒng)。具體來說，GIS就是用在廣泛學科領域的一種大地理信息學科，能夠將工程、規(guī)劃、物流、保險、電信、商業(yè)連接起來，并在此基礎上進行數(shù)據(jù)分析和可視化服務。該技術在世界范圍內都十分普及，是實現(xiàn)可視化、智能化、數(shù)字化的物流規(guī)劃的重要部分。結合有效的算法，能夠很好地改善貴州省茶農、茶葉制造廠的配送路徑，提高效率，促進貴州省茶葉物流的發(fā)展。

1 車輛路徑問題及算法介紹

1.1 車輛路徑問題。在國外，車輛線路優(yōu)化問題屬于VRP問題（Vehicle Routing Problem），起源于旅行商問題[1]。車輛路線問題可以描述為如下數(shù)學模型：如有一配送中心點，有S個商鋪，N輛配送車輛。車輛從配送中心出發(fā)，配送所有商鋪，每個商鋪需求被滿足，且容量不能超過車輛上限，最終實現(xiàn)總成本最小的目標。中心倉庫配送、公共交通工具路線制定、紙媒郵件投遞、大型交通工具（飛機、火車）時間表安排、工業(yè)廢品后期處理等，都包括在車輛路線的實際問題中。本文考慮的車輛路徑優(yōu)化問題是針對茶葉企業(yè)實際的單配送中心、單一車型、單向送貨、有回路的實際問題。

1.2 車輛路徑算法。解決目前車輛路徑問題的算法主要有：精確算法、傳統(tǒng)啟發(fā)式和現(xiàn)代啟發(fā)式算法[2]。

通過表1對各種算法的分析比較，傳統(tǒng)啟發(fā)式算法改善程度有限，難以得到滿意解，所以在最短路徑問題中應用較少；遺傳算法和禁忌算法是目前用于解決大規(guī)模車輛路徑優(yōu)化問題的主流方法，對參數(shù)、數(shù)據(jù)要求較高，相對復雜。如果是以整個貴州省為優(yōu)化目標，選用基于K-MEANS的禁忌算法較好，但是解決本案例中的單配送中心、單車型、純送貨、有回路的車輛路徑問題，通常選用精確算法，現(xiàn)將采用幾種算法對比研究。

表1 各種算法優(yōu)劣勢對比

2 ArcGIS圖層設計

2.1 數(shù)據(jù)采集、錄入

（1）數(shù)據(jù)采集與錄入作為建立地理信息系統(tǒng)的第一步，為以后的各項步驟奠定基礎。本文使用的電子地圖來源于網(wǎng)絡，并根據(jù)百度地圖提供的數(shù)據(jù)進行修改增刪。如果想要使得網(wǎng)絡分析功能實現(xiàn)，那么有三個部分不可或缺。首先就是倉庫（或者說配送點）和商超專賣店分布信息，然后是倉庫的容量、商超的容量，最后是貨車從倉庫到商超的所有可能經過的路徑。

（2）最短路徑問題解決的主要問題是倉庫（配送點）和目標商超之間的路徑問題，所以商超的地理分布位置應該作為首要解決的問題。同樣地,商超專賣店應該包含以下內容：準確無誤的經緯度坐標信息，相關次要因素信息。一般來說，我們應該提前建立倉庫（配送點）和商超專賣店的數(shù)據(jù)檔案，建立數(shù)據(jù)服務器或者本地檔案，方便直接調用。與此同時，系統(tǒng)能夠根據(jù)實際需要，隨時增添、修改或刪除對應的相關信息。

2.2 數(shù)據(jù)結構選擇

按照數(shù)據(jù)組織結構的不同分類，主要有兩大類：矢量數(shù)據(jù)結構和柵格數(shù)據(jù)結構。

（1）柵格數(shù)據(jù)結構。按照一定規(guī)則將需要分解的工作區(qū)域平面進行行列劃分，形成網(wǎng)狀結構，每一個網(wǎng)格單元稱為像元。而柵格數(shù)據(jù)結構實質上等于像元按矩陣形式有序組合排列。每一個像元坐標位置由行列號組合形成的二元坐標定位，類似于常見的笛卡爾X-Y坐標軸。

（2）矢量數(shù)據(jù)結構。矢量是具有一定大小方向的量，代表著有序、有獨有特征的有向線段，它們的集合就構成了圖像。矢量數(shù)據(jù)就是代表地圖特征的各離散數(shù)據(jù)的有序集合，主要用于表示地圖上各種各樣的組成元素，表現(xiàn)了幾何和屬性數(shù)據(jù)的一定關系。

2.3 屬性數(shù)據(jù)

屬性數(shù)據(jù)主要用來表示確定位置的地理對象的特殊屬性，空間位置的變化不一定使屬性改變，例如人行道的具體位置確定，由普通斑馬線變?yōu)槿诵刑鞓虻?。本文涉及到的屬性?shù)據(jù)主要包括城市、道路、超市商店（服務點）的屬性數(shù)據(jù)。城市的屬性數(shù)據(jù)包含以下幾個詞條：ID、name（名稱）、class（等級） 等；道路：ID、name（道路名稱）、kind（道路等級）、shapelength（長度）等；商超：ID、name、kind（種類）等。根據(jù)實際需要增加或減少數(shù)據(jù)類型。

3 貴州湄潭縣某茶業(yè)公司配送路徑優(yōu)化問題求解

貴州湄潭縣某茶業(yè)有限公司，依托100萬畝優(yōu)質茶葉基地，企業(yè)發(fā)展蒸蒸日上，迄今已實現(xiàn)從中國茶葉行業(yè)百強企業(yè)，到貴州省重點龍頭企業(yè)，再到國家級重點龍頭企業(yè)的跨越式發(fā)展。但是物流作為該公司的短板，已經嚴重影響到該公司的發(fā)展，下面將結合各算法，就該問題進行探討。

3.1 蟻群算法求解。蟻群算法是一種用來尋找優(yōu)化路徑的概率型算法。通過閱讀文獻[3-4]，確定在螞蟻數(shù)量為m，信息素重要程度參數(shù)α或者β區(qū)間為［1,5］，信息素蒸發(fā)系數(shù)Rho區(qū)間為［0.3,0.5］，信息素增加強度系數(shù)Q=100時，能夠保證在小規(guī)模計算中，較為快速地求出最優(yōu)路徑。那么根據(jù)本文已有的參數(shù)，可以求得螞蟻數(shù)量為4或者5，而螞蟻數(shù)量越多越能提升搜索量，提高搜索效率，故螞蟻數(shù)量設置為5。經過間隔0.1的組合優(yōu)化，發(fā)現(xiàn)當α=1.5，β=2.0時運算效率較高。在其他參數(shù)確定的情況下，多次試驗發(fā)現(xiàn)Rho=0.4時比較適合本案例。

建立距離矩陣（如表2所示），采用蟻群算法求解最短路徑。通過Matlab編程，多次運行程序（最大迭代次數(shù)為100），可以得到路徑分析結果，最短路徑是11-6-10-7-8-9-3-2-5-4-1，路徑長度為12 039m。

3.2 遺傳算法求解。在設計遺傳算法過程中，某些參數(shù)的選擇影響著算法的可行性和準確性，極大影響算法性能，但是由于參數(shù)選擇至今沒有一個統(tǒng)一的標準，所以目前的解決措施是依靠先驗知識來選擇，與此同時參考國內部分文獻資料[5-6]。

種群規(guī)模直接影響最優(yōu)解的質量，種群規(guī)模的大小與最優(yōu)解質量呈正相關。伴隨著種群數(shù)量的增大，算法運算時間呈指數(shù)級上升，而一般種群數(shù)量約為商超數(shù)量的1～2倍，因此本文選取一個適中的種群數(shù)量20。

表2 10個商超之間的距離矩陣

適應值歸一化淘汰加速指數(shù)，根據(jù)經驗默認取值范圍｛1,2,3,4｝且取值不能偏大，此處由于數(shù)據(jù)較少，試驗得出當該數(shù)值等于2時，比較合適。本文采取固定交叉概率，取值范圍為 ［0.9 , 0.999］，由于商超數(shù)量較小及試驗佐證，選取0.9作為交叉概率數(shù)值可行。同理，選取變異概率Pmutation=0.1，滿足遺傳算法參數(shù)選取經驗。

主要輸入?yún)?shù)包括：商超（包括出發(fā)點）個數(shù)N=11，種群個數(shù)M=20，迭代次數(shù)C=100，適應值歸一化淘汰加速指數(shù)m=2，交叉概率Pc=0.9，變異概率Pmutation=0.1。運行程序,可以得到路徑分析結果，最短路徑是11-1-9-2-3-8-5-4-7-10-6，路徑長度為12 278m。隨著迭代次數(shù)的增多，無限接近于最優(yōu)路徑，但是次數(shù)少往往不能得到最優(yōu)解，只能獲得較為接近最優(yōu)解的最佳解，并且隨著迭代次數(shù)增多，運算時間大大加長，對電腦硬件要求較高，且出現(xiàn)內存不足的情況。

3.3 免疫算法求解過程。由于免疫算法與遺傳算法擁有極大相似性，所以主要參數(shù)設置基本與遺傳算法相同，此處不再贅述。定義：商超個數(shù)N=11，種群個數(shù)M=N-1，字符變異概率pStrChange=0.4，字符交叉概率pCharReCompose=0.4，最大迭代次數(shù)MaxIterateNum=100。

運行程序,可以得到路徑分析結果，最短路徑是11-9-7-8-4-10-6-5-2-3-1，路徑長度為12 039m。多次迭代可以找出最短路徑，但是會出現(xiàn)路徑不是最優(yōu)的情況。免疫算法適合數(shù)量較大的問題，對于數(shù)量級較小的問題，難以迅速求出最優(yōu)路徑，但是對比遺傳算法則快了許多。

3.4 ArcGIS自帶Dijkstra算法求解。ArcGIS本身具有網(wǎng)絡分析功能，其中最基礎的功能即是最佳路徑分析功能。在網(wǎng)絡分析中，有最短和最優(yōu)兩種路徑分析的工具模塊，前者在解決最短路徑問題方面比較適用，后者在路徑分析方面主要用于城市基礎設施網(wǎng)絡如各種城市設施建設、地下排污管道、通信光纜等的線路路徑分析。另外，在進行網(wǎng)絡分析之前，這兩種工具都需要在構建道路網(wǎng)絡的拓撲關系的基礎上，建立網(wǎng)絡數(shù)據(jù)集。路網(wǎng)拓撲關系構建比較復雜，且往往不能得到所需的最優(yōu)解。采用ArcGIS計算上例中的最短路徑，結果顯示：具體路徑是11-9-2-4-6-7-8-10-5-1-3-11，長度為14 336m。

3.5 算法比較。過上述四種方法分別求得物流配送的最短路徑，下面從幾個方面進行分析，如表3所示。

表3 各算法理論最短路徑比較

對比各項數(shù)據(jù)，就本例而言，采用蟻群算法比較合適。它可以在硬件條件受限時迅速得出最短路徑，且編程比較容易獲取，其他算法都存在一定的限制。遺傳算法的參數(shù)設置要求比較高，如果設置不合適，會出現(xiàn)過早收斂，找不到最優(yōu)解而是次優(yōu)解。但迭代次數(shù)比較大時（大于1 500），會出現(xiàn)內存不足的情況，可見當?shù)螖?shù)增加時，對硬件條件的要求也相應地提高了；免疫算法類似于遺傳算法，但是又與之不同。最典型的就是免疫算法可以結合其他算法，吸收其他算法特點。因此，免疫算法在很大程度上將依賴其他算法。

3.6 蟻群算法與GIS集成效果。本例采用的是自行繪制的貴州省湄潭縣的道路網(wǎng)絡，空間數(shù)據(jù)主要有點、線、面三種矢量格式。根據(jù)實際需要，分為網(wǎng)絡交通路網(wǎng)、優(yōu)化路徑圖層，以及需要停靠的商超店面等圖層。在處理編輯過的空間數(shù)據(jù)與組織形式后，得到準確有效的GIS地圖，利用GIS中的網(wǎng)絡分析功能解決最短路徑問題，實現(xiàn)GIS配送路徑與蟻群算法的結合，如圖1所示。

最短的配送路徑應該是茶城大道向東行駛4 600m，至農貿街東側盡頭720m，環(huán)西路1 600m，茶鄉(xiāng)北路300m，小北街200m，浙江路100m，湄江南路400m，塔坪路1 000m，中山西路 300m，茶海路600m，天文大道1 400m，雙擁路600m，茶城大道1 000m，總計13 720m。

某公司原本運用Dijkstra算法作為主要算法，根據(jù)上文的數(shù)據(jù)對比，可以發(fā)現(xiàn)，采用與蟻群算法的結合，可以減少600m左右的運輸路徑。按照該公司一天一次，兩車一起運輸?shù)某Ｒ?guī)配送，至少可以節(jié)約1 200m運輸路徑，按照92號汽油6.8元/L、小噸位冷藏車百公里20L油耗來算，該公司僅在湄潭縣內運輸一年至少可以節(jié)約1 200元。如果將該法推廣至整個貴州省88個縣級行政區(qū)劃單位，加上配送車輛及配送網(wǎng)絡的增加，至少可以節(jié)約十幾萬至幾十萬元不等，能產生較好的經濟效益和社會效益。

4 結論

ArcGIS軟件與蟻群算法的結合有利于降低茶葉物流配送成本，并且能夠實現(xiàn)可視化配送，大大降低配送難度，提升配送效率。本文采用四種算法各自計算最短路徑，并對計算結果、時間進行比較，最終確定蟻群算法與ArcGIS軟件的結合，對于茶葉配送效率提升最大，每一趟能夠縮短600m左右的路程，對整個貴州省茶葉配送具有一定的參考意義。但是，該算法是否具有普適性，ArcGIS的適用與否，都應因地制宜。因此，企業(yè)應該根據(jù)自身實際情況，做好前期的可行性調研。

圖1 蟻群算法與ArcGIS集成效果圖