基于ArcGIS的運輸路徑優化研究
——以貴州省湄潭縣某茶業公司物流配送為例

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

（1.南京林業大學 汽車與交通工程學院，江蘇 南京 210037；2.南京林業大學 土木工程學院，江蘇 南京 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 引言

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

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

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

1.2 車輛路徑算法。解決目前車輛路徑問題的算法主要有：精確算法、傳統啟發式和現代啟發式算法[2]。

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

表1 各種算法優劣勢對比

2 ArcGIS圖層設計

2.1 數據采集、錄入

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

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

2.2 數據結構選擇

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

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

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

2.3 屬性數據

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

3 貴州湄潭縣某茶業公司配送路徑優化問題求解

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結論

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

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