時間：2022-06-18 13:11:38
開篇：寫作不僅是一種記錄，更是一種創造，它讓我們能夠捕捉那些稍縱即逝的靈感，將它們永久地定格在紙上。下面是小編精心整理的12篇路徑規劃，希望這些內容能成為您創作過程中的良師益友，陪伴您不斷探索和進步。
Key words:distribution regional division; distribution vehicle routing optimization; algorithm
0 引 言
流通領域中,許多物流配送企業借助外部經濟的發展,實現了規模擴張與快速發展,但對如何控制成本,提高運營效率的迫切性并不強。現在隨著經營環境的變化,物流需求量更大,客戶、網絡更復雜,對服務的要求更多樣化。但面臨的競爭更加激烈,不管是從事跨區域配送還是城市配送,首先需要考慮顧客服務水平,贏得客戶的認可,然后考慮配送運營的成本問題,因而如何創新物流服務,提高運營效率和控制日常運營成本成為每個配送企業需要時刻思考的問題。
傳統的基于經驗的方法,在企業規模有限,客戶數量不是非常多,配送網絡相對簡單的情況下,只要員工和管理者技能過關,執行力好,都應該能夠較好地完成配送任務,獲得企業的發展。但是隨著銷售區域擴大,客戶數量的不斷增加,客戶需求持續增長,配送業務量大增,配送周期縮短,配送線路更復雜,并且需求的隨機性、變動性加大,光憑經驗和手工安排,已無法做到配送計劃的優化,必須借助于統計分析、利用數學模型和智能算法,才能獲得較好的配送計劃,節省時間,提高效率。本文就是針對這些問題,從企業應用的角度,提出先合理劃分配送區域,再優化配送路線的方法,從而達到降低成本,提高競爭力的目標。
1 論文總體思路綜述
排單和車輛調度是整個配送計劃和作業實施的核心,是配送任務和客戶服務按時完成的有力保證。
傳統的訂單排單和車輛調度、路線安排都是由公司里業務能手來完成,送貨區域大了,客戶多了,這項工作的效率和完成工作的成本控制都會不理想,現在常用的智能優化方法,把它作為一個典型的VSP問題,建立數學模型,利用智能化的算法,求解可行的配送路徑規劃,作為理論研究,這樣的做法是有意義的。但是有兩個問題:(1)這個模型數據的收集整理工作量特別大,計算過程也較長,因而成本不會低。(2)模型本身一定要適合實際的作業過程,這就需要有一個不斷測試和優化的過程,并且還要適應每天的動態變化,否則反而會影響到日常的作業過程。許多研究理論完備、精深,但是在適應產業化運營時,工程上的可實現性還有待提高和完善。因而影響了這些很有價值的研究在企業實際中的運用。
本文的研究并不針對配送路徑規劃做理論上的深究,而是立足實際應用,在可接受的范圍內,利用較簡易實用的智能優化方法,在較短的時間內,以較低的成本獲得相對優化的配送路徑規劃方案。不求最佳,但求有效。為今后電子排單和送貨線路優化軟件的開發和應用作必要的鋪墊。
具體設想:第一步,利用聚類分析法對配送區域進行合理分區,先把復雜問題簡單化。第二步,每個分區內就是個典型的TSP問題,有很成熟的解決辦法。在平衡好各分區工作時間安排后,就能很快獲得較理想的配送方案。
重點是第一步,分區時一定要考慮到客戶位置、需求量、車輛載重、作業時間均衡限制等因素,需要花費好多功夫。
2 配送區域動態優化及其方法
2.1 配送區域的初始劃分方法。配送區域優化方法對最終優化的結果有很大的影響,因而合理的劃分方法的選擇十分重要,目前常用的劃分方法有掃描法和聚類算法,在配送客戶有限、區域較小時運用掃描法就可以了,但是當客戶數量很多,區域較大,又要考慮約束條件時,聚類算法就是我們必然的選擇了,聚類算法中K- means比較成熟,操作簡單,原理是:把大量d維(二維)數據對象n個聚集成k個聚類k 在運用聚類分析法時有幾個問題要注意:第一,k的選擇,以一天送貨總量/單車載重量,也可以放寬一些,到:一天送貨總量/單車載重量+1。第二,k個聚類內的密度,分區密度大,效率高,成本低。第三,每個分區內工作時間大體相當,這樣便于運行的穩定,進行成本控制和人員、車輛的考核。第四,每個聚類間不重合。做到這樣分區效果會比較好。
傳統的K-means聚類法,k個聚類區內,初始點是隨機產生的,運行時間長,收斂效果差。基于均衡化考慮,在配送對象分布不均勻時,用密度法效果較好,初始中心點以密度來定義,運用兩點間歐氏距離方法,求解所有對象間的相互距離,并求平均數,用meanD表示,確定領域半徑R,n是對象數目,coefR是半徑調節系數,0 coefR=0.13時,效果最好。如果使用平均歐
氏距離還不理想,可增加距離長度,甚至用最大距離選擇法,收斂速度比較快。 在配送對象分布較均勻時,可考慮用網格法,效果較好,整個配送區域劃分用k=Q/q,k為初始點個數,假設k=mn,將地圖劃分成m行n列,以每格中心點為初始點,通過網格內的反復聚類運算,達到收斂,獲得網格穩定的聚類中心。
2.2 分區內配送工作量的均衡。這樣就完成了配送區域的初步劃分,但是沒有考慮各個分區內工作量的均衡問題,如果工作量不均衡,對于客戶服務水平的保證,成本的控制,作業的安排,人員、車輛的考核都存在問題。
在實際的物流企業配送作業過程中,一般一輛車一天也就送貨10多家或20來家,多余的時間要用于收款,與公司財務部門交賬,核算出車相關費用,所以不考慮同一車同一天出車多次的情況,多次出車待以后深入探討。那么就意味著每個分區就是一輛車一條線路,把問題大大簡化了,需要說明的是:這種方法對于配送規模不是特別大的單個城市配送是適用的,也具有廣泛性。
各分區內的每日配送工作量是以配送作業耗用時間來衡量的,耗用時間有兩部分構成:(1)車輛行駛時間;(2)客戶服務時間。由于配送分區有限,每個分區內的客戶數量不是很多,可以采用實地測時的方式,把每條線路的配送時間統計出來,這是一種手工辦法,但比較符合實際來調整超過差值的分區內的客戶,從而使得各區作業時間基本均衡。
如果客戶數量眾多,分區也較復雜,就需要借助統計學方法,通過對樣本線路車輛行駛時間以及服務時間,擬合出分區作業時間函數,然后,計算出所有線路作業時間,即使分區重新調整,線路重新組合,仍可以很快計算出線路作業時間。本文不在這個方面進行深入探討。
2.3 重新組合客戶,確定最終區域劃分。觀察各線路作業時間超過允許差值的部分,由大到小來調整,將離聚類中心最遠的數據點彈出,使本區T值下降,直至在差值以內,將彈出點加入到臨近的不足均衡作業時間的分區內,如果臨近分區作業時間超過允許差值,這個點就不能彈出,只能彈出另外的次遠數據點,以此類推,任何一個數據點只能彈出一次,直到所有數據點和分區調整完畢。
這樣最終確定的分區,既能做到區域劃分緊密,效率、成本更低,又能做到各區作業時間均衡,便于工作指派,車輛、人員核算。
以上是本文的第一部分工作,也是最有意義的工作,確定好合理的區域劃分,不僅是配送作業合理化的重要步驟,也是業務人員訪銷工作和客戶服務的重要依據。
3 基于改進蟻群算法的分區線路優化方法
分區內線路安排,就是一輛送貨車由DC出發,依次經過分區內每一個客戶點,完成送貨后返回DC,求出近似最優的行車順序,這是個典型的旅行商問題(Traveling Salesman Problem,TSP),TSP是NP完全問題,解法很多,有精確算法,也有啟發式算法,目前許多智能算法就屬于啟發式算法,可以解決較復雜的線路優化問題,對于一般線路優化也能做得更準確,這里介紹蟻群算法解決實際問題。原因是蟻群算法與其他啟發式算法相比,在求解性能上,具有較強的魯棒性和搜索較好解的能力,是一種分布式的并行算法,一種正反饋算法,易于與其它方法結合。克服基本算法缺點,改善算法性能。
3.1 蟻群算法簡介。蟻群算法(Ant Colony Algorithm, ACA)是由意大利學者M.Dorigo等人于20世紀90年代初提出的一種新的模擬進化算法,其真實地模擬了自然界螞蟻群體的覓食行為。 M.Dorigo等人將其用于解決旅行商問題TSP,并取得了較好的實驗結果。
蟻群算法用于解決優化問題的基本思路是:用螞蟻的行走路徑表示待優化問題的可行解,整個螞蟻群體的所有路徑構成待優化問題的解空間。路徑較短的螞蟻釋放的信息素數量較多,隨時間推移,較短路徑上積累的信息素濃度逐步增高,選擇該路線的螞蟻數量也越來越多,最終整個螞蟻會在正反饋的作用下集中到最佳線路上,這個路線就是最有解。
蟻群算法解決TSP問題具體步驟:(1)基本參數設置:包括螞蟻數m,信息素重要程度因子0≤α≤5,啟發函數重要因子1≤β≤5,信息素消逝參數0.1≤ρ≤0.99,信息素釋放總量10≤Q≤10 000,最大迭代次數iter_max,迭代次數初值iter=1。用試驗方法確定α、β、ρ、Q值,以獲得較優的組合,有助于改進基本蟻群算法,提高整體優化效果,并縮短運算時間。(2)初始解的求解:利用最近鄰算法,以縮短算法運算時間,并以此算法產生初始解的路徑長度作為產生初始信息素的基礎。 (3)構建解空間:將各個螞蟻隨機地置于不同出發點,對每個螞蟻,按公式(1)計算其下一個待訪問的網點,直到所有螞蟻訪問完區域內所有網點。(4)更新信息素:計算各個螞蟻經過的路徑長度Lk=1,2,…,m,記錄當前迭代次數中的最優解。同時,根據(2)式和(3)式對各個網點連接路徑上的信息素濃度進行更新。(5)判斷是否終止:若iter 蟻群算法如結合其他啟發式算法,建立混合算法,能夠解決許多現實問題,達到較好運算效果,結合具體問題,可以深入研究。
4 本文的局限與進一步研究的方向
關鍵詞:移動多智能體;全局規劃;局部規劃
中圖分類號:TP393文獻標識碼:A文章編號:1009-3044(2010)16-4487-03
Research on Path Planning for Mobile Multi-Agent
CHEN Cui-li, GAO Zhen-wei
(Henan Normal University, Xinxiang 453007,China)
Abstract: A path planning method based on both the benefits of global and local path planners is proposed for mobile Multi-Agent path planning in dynamic and unstructured environments. The global path planner uses A*algorithm to generate a series of sub-goal nodes to the target node, and the local path planner adopts an improved potential field method to smooth and optimize the path between the adjacent sub goal nodes. Taking into full consideration the kinematical constraints of the mobile robot, this method cannot only effectively generate a global optimal path using the known information, but also handle the stochastic obstacle information in time. and is simulated on simulation platform developed by using Visual Studio 2005 software, simulation result presents the validity and utility of the algorithm.
Key words: mobile Multi-Agent; global path; local path
在移動智能體相關技術研究中,路徑規劃技術是一個重要研究領域。移動智能體路徑規劃問題是指在有障礙的環境中,尋找一條智能體從起始點到目標點的運動路徑,使智能體在運動過程中安全、無碰撞地繞過所有的障礙物。這不同于用動態規劃等方法求得最短路徑,而是指移動智能體能對靜態及動態環境下做出綜合性判斷,進行智能決策。在以往的研究中,移動智能體路徑規劃方法大體上可以分為三種類型:其一是基于環境模型的路徑規劃,它能處理完全已知的環境下的路路徑規劃。而當環境變化時(出現移動障礙物)時,此方法效果較差,具體方法有:A*方法、可視圖法、柵格化和拓撲圖法等;其二是基于傳感器信息的局部路徑規劃方法,其具體的方法有:人工勢場法、模糊邏輯法和遺傳算法等;其三是基于行為的導航行為單元,如跟蹤和避碰等,這些單元彼此協調工作,完成總體導航任務。隨著計算機、傳感器及控制技術的發展,特別是各種新算法不斷涌現,移動機器人路徑規劃技術已經取得了豐碩研究成果。
一個好的路徑規劃方法需要滿足如下性能[1]:合理性、完備性、最優性、適時、環境變化適應性和滿足約束。有些方法沒有高深的理論,但計算簡單,實時性、安全性好,就有存在的空間。如何使性能指標更好是各種算法研究的一個重要方向。
在未知的(或部分已知的),動態的非結構的環境下,多智能體利用傳統的路徑規劃方法很難滿足前面的性能要求,本文提出了一種將全局路徑規劃方法和局部規劃方法相結合,將基于反應的行為規劃和基于慎思的行為規劃相結合的路徑規劃方法,其思路如下:多智能體分別采用A*算法進行全局路徑規劃,各自生成到達目標點的子目錄節點序列,同時采用改進的人工勢能對子目錄節點序列中相鄰節點進行路徑的平滑和優化處理,該方法不但能夠充分利用已知環境信息生成全局最優路徑,而且還能及時處理所遇到的隨機障礙(其它智能體)信息,從而提高了多智能體整體的路徑規劃的性能。
1 路徑規劃方法
1.1 相關研究
1) A*算法
在最佳優先搜索的研究中,最廣范圍應有的方法為A*搜索,其基本思想[2]是:它把到達節點的代價g(n)和從該節點到目標節點的代價h(n)結合起來對節點進行評價:f(n) = g(n) + h(n)(1)。A*算法用于移動多智能體的路徑規劃時,多智能體分別按照已知的地圖規劃出一條路徑,然后沿著這條生成路徑運動,但智能體傳感探測到的環境信息和原來的環境信息不一致時,智能體重新規劃從當前位置到目標點的路徑。如此循環直至智能體到達目標點或者發現目標點不可達[3]。重新規劃算法依舊是從當前位置到目標點的全局搜索的過程,運算量較大。而且由于采用A*方法規劃出的最優路徑并沒有考慮到機器人的運動學約束,即使機器人可以采用A*方法規劃出一條最優路徑,機器人也未必可以沿著這條路徑運動。
2) 人工勢能法
人工勢能法由 Khatib 提出的一種虛擬力法[4]。人工勢場方法結構簡單,便于低層的實時控制,在實時避障和平滑的軌跡控制方面得到了廣泛的應用,但根據人工勢場方法原理可知,引力勢場的范圍比較大,而斥力的作用范圍只能局部的,當智能體和障礙物超過障礙物影響范圍的時候,智能體就不受來自障礙物引起的排斥勢場的影響。所以,勢場法只能解決局部空間的避障問題,他缺乏所在的全局信息,,這樣就造成產生局部最優解不能進行整體規劃,智能于局部最小點的時候,智能體容易產生振蕩和停滯不前。
1.2 路徑規劃方法描述
鑒于A*算法全局路徑搜索的全局性與改進人工勢場算法局部路徑搜索的靈活性,通過一定的方法把兩者結合起來,其思路如下:多智能體分別采用A*算法進行全局路徑規劃,各自生成到達目標點的子目錄節點序列,同時采用改進的人工勢能對子目錄節點序列中相鄰節點進行路徑的平滑和優化處理,該方法不但能夠充分利用已知環境信息生成全局最優路徑,而且還能及時處理所遇到的隨機障礙(其它智能體)信息,從而提高了多智能體整體的路徑規劃的性能。由于A*方法采用柵格表示地圖,柵格粒度越小,障礙物的表示也就越精確,但是同時算法搜索的范圍會按指數增加。采用改進人工勢場的局部路徑規劃方法對A*方法進行優化,可以有效增大A*方法的柵格粒度,達到降低A*方法運算量的目的。
2 環境構造
目前主要有三種比較典型的環境建模方法:構型空間法、自由空間法和柵格法,本文仿真實驗采用的環境建模方法是柵格法,柵格法將機器人路徑規劃的環境劃分成二維網格,每格為一個單元,并假設障礙的位置和大小已知,且在機器人運動過程中不會發生變化。柵格法中的網格單元共有三種類型,即障礙網格、自由網格和機器人所在網格。目前常用的柵格表示方法有兩種,即直角坐標法和序號法。這兩種表示方法本質上是一樣的,每個單元格都與(x, y)一一對應。本文采用序號法表示柵格,設柵格的中心點坐標為柵格的直角坐標,則每個柵格編號都與其直角坐標一一對應,地圖中任意一點(x,y)與柵格編號N的映射關系為:N=INT(xGs)+xmaxGs×INT(yGs),(1)式中,xmax表示x軸的取值范圍,Gs表示柵格尺寸的大小,INT函數表示取整,而柵格中心點的坐標為(xG,yG),它與柵格編號N之間的關系為:xG=(N%M)×Gs+Gs/2,yG=INT(N/M)×Gs+Gs/2,(2)式中,M=xmax/Gs,符號%表示取余操作。本文中根據機器人的尺寸來確定柵格的粒度,假設一個柵格能容納一個智能體,這里選擇柵格的大小為40cm×40cm[5]。本文的仿真環境為800cm×800cm,柵格號N=0~399,機器人的初始位置的柵格號為N=42,目標位置的柵格號為N=314。在Visual Studio 2005中進行仿真,仿真結果如圖1所示,長方形和橢圓圖形代表障礙物柵格,小圓圈所代表的柵格為機器人的起始柵格和目標柵格,剩下的是自由柵格。在路徑規劃中機器人可以選擇自由柵格作為它的路徑點。
建立柵格后,對柵格進行初始化。設置變量G_Obstacle為0表示自由柵格,G_Obstacle為1表示障礙網格包括機器人柵格。若障礙物或智能體占當前位置柵格面積大于1/3則設置變量G_Obstacle為1.
3 數據的采集
對于簡單地形,我們將實際地形就行考察并進行測量、量化,轉化為平面坐標數據最后轉換相應的柵格編號。對于復雜地形在沒有航攝資料的情況下,本實驗以地圖為數據源的DTM數據獲取方法在,可利用已有的地形圖采集地形數據,用手扶跟蹤式數字化儀將平面圖形轉化為平面坐標數據,最后轉換相應的柵格編號。
4 實現過程
第1步:對環境信息進行數據采集并轉化成相應的平面坐標數據。
第2步:確定各個智能體的初始位置和目標位置。
第3步:建立柵格,對柵格進行初始化。
第4步:智能體S(i)首先根據已知信息規劃出各自的一條目標序列S(i)n。
第5步:智能體S(i)利用測試傳感器探測到臨界危險區L范圍內的信息與原有信息是否一致,當智能體利用傳感器探測到臨界危險區L范圍內的信息與原有信息一致時,利用改進后的人工勢能算法搜索相鄰目標點之間的軌跡,否則智能體搜索從當前序列點S(i)n到S(i)n+4路徑。定義臨界危險區L、目標序列點S(i)n(n>=1)。
第6步:智能體一旦移動到達目標柵格,則程序終止;否則返回第5步。系統的工作流程如圖2所示。
5 仿真結果及結論
在Visual Studio 2005平臺上進行了仿真,,首先根據已知環境信息,進行數據采集量化并進行柵格化處理,設置障礙和智能體的大小及位置(為了簡單化,本實驗所有障礙都設置為圓形),再進行初始化操作,采用0、1二元信息數組存儲柵格化的地形。
智能體運用A*算法進行全局路徑規劃,圖3顯示兩個智能體的運動過程,顯然兩個智能體的路徑相交可能會發生碰撞,智能體為了避免碰撞應重新規劃算法依舊是從當前位置到目標點的全局搜索的過程,運算量較大。而且顯然只用A*算法規劃出二維路徑點序列,相鄰兩點之間的夾角一定是π/4的整倍數,機器人很難按照所生成的序列點運動。智能體采用改進后的人工勢場進行目標序列點之間的局部路徑規劃,圖4顯示智能體的運動過程。顯然智能體的整條運動軌跡顯得比較平滑同時又實現實時避障的目的。
6 總結
本文對多智能體在動態環境下路徑規劃技術進行了研究探索,提出了一種能夠將全局路徑規劃方法和局部路徑規劃方法相結合,通過仿真取得了很好的結果,證明A*和人工勢場算法的結合可行。
參考文獻:
[1] 劉華軍,楊靜宇,陸建峰,等.移動機器人運動規劃研究綜述[J].中國工程科學,2006,8(1):85-94.
[2] Nilsson N J. Princip les of Artificial Intelligence[M].Berlin, Ger2 many: Sp ringer,1980.
移動機器人遺傳算法完全遍歷路徑規劃
1引言
完全遍歷路徑規劃（ Complete Coverage Path Planning， CCPP）是一種特殊的路徑規劃，它要求移動機器人在滿足一定的指標下完遍歷目標環境中的可達區域。在機器人的許多應用領域，大都需要用到遍歷路徑規劃算法，例如軍事用的地雷探測、家居及辦公環境的地面清潔、不同應用領域地圖的創建等。在這些應用中要求機器人覆蓋環境中所有未被障礙物占據的區域。按照對環境知識的了解，在已知環境覆蓋算法中讓清潔機器人規劃出一條能走過環境中的所有地方并目.是代價最小路徑，這個時候的問題就相當于旅行家問題，未知環境的覆蓋要求清潔機器人必須借助身體上攜帶的不同類型的傳感器來感知周圍的環境并進行規劃。
為克服上述路徑規劃中存在的問題，本文比較了基于遺傳算法的完全遍歷路徑規劃方法的優缺點，提出了基于遺傳算法與單元分解法、啟發式搜索和障礙物逼近算法結合的完全遍歷路徑規劃新方法，將該方法應用于清潔機器人的完全遍歷路徑規劃，與基于其他算法的路徑規劃方法進行比較，在多個性能指標上都得到了改善與提高。
2完全遍歷規劃性能指標
移動機器人的完全遍歷路徑規劃常用的性能評價指標有遍歷面積百分率，遍歷重疊率。
（1）遍歷覆蓋率，是指機器人沿可行軌跡線遍歷完成后，己遍歷面積與可達區域面積的百分比。
（2）遍歷重疊率，指所有遍歷重疊面積之和與可達區域面積的之比的百分數。
為了保證相鄰區域之間不留有遍歷盲區，相鄰遍歷區域必須有一定程度的重疊，顯然，
重疊區域越小越好，但因受機器人本身的系統誤差，定位誤差，控制精度以及環境狀態的影響，重疊區不可能太小，如果一個機器人性能越高，則遍歷重疊率能控制在很小的范圍內。
從遍歷重疊率，還可以推出未遍歷面積百分率，它指機器人沿著可行軌跡線遍歷完成后，未遍歷面積與可達面積的百分比。
如果一個機器人性能越高，則遍歷覆蓋率越高，遍歷重疊率越低，遍歷效果越好，本文中主要結合遍歷重疊率和未遍歷面積來綜合評價完全遍歷路徑規劃。
3基于遺傳算法的完全遍歷路徑規劃
本文的環境地圖采用幾何表示法表示，即用點、線及其組合來表示環境中的特征，并用參數來表明各個特征在環境中的具置。將地圖進行Boustrophedon單元分解后，地圖將由若干障礙區和若干遍歷區組成。電子地圖則表示為各個區域信息的集合，而其中單個區域的信息包括區域的屬性（障礙區屬性或遍歷區屬性）及區域頂點的坐標。通過 Boustrophedon單元分解，環境可以分解為如圖 1所示的若干遍歷區和障礙區。
如圖1所示，區域 2和區域 5之間的連通距離是不方便求解的，本文通過定義一個距離來表示兩者之間的實際距離。雖然這個距離與實際距離之間有一定的差距，但距離值的大小趨勢是一致的，而且距離的定義主要考慮了兩個區域之間的直線距離、區域之間的連通關系、區域之間的障礙物情況。對于非毗鄰關系的區域之間的距離，我們用D%= bDJN%來表示。其中， b是一個可調系數，可以通過仿真來調整該值以得到一個較好的數值；D為環境中兩個區域之間的直線距離矩陣，對于該表達式中的各個參數， D、N可以根據劃分后的區域的邊界信息來確定，而J需要通過下面的算法實現。
由圖2我們可以得到矩陣A
aij = 1表示遍歷子區域i和j毗鄰，aij = 0表示不毗鄰。矩陣A為對稱矩陣，其對角線的元素值為0，即不存在通過一次連通的路徑連通區域1與它自身。aij = 1表示存在一條從區域i到區域j的一次連通路徑，如a12 = 1，從圖 2看出，區域1、 2存在一次連通路徑。那么如何得到非一次連通的區域之間的連通關系呢？我們可以通過求矩陣 A的n次冪來得到兩個區域之間的n次連通關系。對于i、j、k三個區域，如果區域i和區域j連通，區域j和區域k連通，則區域i和區域k連通，即當元素aij為非零值，ajk也為非零值，則通過計算
得到區域i和k的有幾條連通路徑。圖2中各區域之間的連通關系矩陣如下：
在電子地圖中兩個遍歷子區域的最近頂點分別為 A（ x i ， y i ）、 B （ x j ， y j ） ，判斷兩者之間的障礙物個數就是判斷AB連線通過的障礙物個數。障礙物頂點在向量AB的順時針方向還是在逆時針方向可以通過向量的叉乘來判斷，即
電子地圖中遍歷子區域之間的障礙物數矩陣 N如下：
為了只保留對角線元素為 0，將矩陣 N的非對角線元素加1，得到規格化后的障礙物矩陣N。
距離矩陣 D表示遍歷子區域之間的實際距離，其元素dij為子區域i和j的最近頂點之間的距離，對于毗鄰區域的距離值定為a，非毗鄰區域的距離值由電子地圖根據區域坐標定出。圖 1區域之間距離矩陣 D實測如下：
通過對障礙物矩陣、距離矩陣、連通矩陣的相同位置的元素相乘，再對非一次連通的區域距離乘以系數b，得到一個重新定義的綜合距離矩陣D'，其中
圖1區域綜合距離矩陣D'如下：
4仿真研究
基于本章提出的完全遍歷路徑規劃算法，進行了大量的仿真實驗。下面是對圖3的仿真地圖完全遍歷結果。
經過大量地圖的仿真表明，該遍歷算法的覆蓋率達到90%以上，有的甚至達到95%以上，而且重復率在10%以下。對于不同的地圖覆蓋率和重復率是不同的，不過對大多數地圖而言，該算法是高效的、實用的，具有很強的適應性。該完全遍歷算法特點是系統要處理的信息量很少，機器人實時性控制更強。特別是提出了基點這一重要概念，使得在未知環境中實現完全遍歷更有效、更方便。
5結論
本文根據遍歷環境內區域關系和區域連通圖，將已有的連通圖補充為完全連通圖，并根據區域信息和連通信息定義一個區域之間的距離矩陣，賦予區域之間的連接權值。根據距離矩陣，采用遺傳算法對區域的遍歷順序進行優化。仿真研究表明，該方法用于不確定環境下的移動機器人遍歷路徑規劃，不但能保證遍歷所有可達工作空間，并且規劃的路徑較短、路徑重復率小，具有較高的規劃效率。
參考文獻：
[1]丁學恭.機器人控制研究[M].浙江大學出版社，2006.
[2]楊高波，元波.精通MATLAB7.混合編程[M].電子工業出版社，2006.
關鍵詞：精英策略；蟻群算法；配送中心；信息素；路徑
中圖分類號：F252.14 文獻標識碼：A
關于物流配送路徑規劃一直是物流領域研究的熱點和難點問題，從國外研究情況來看，1993年Ronald 等人提出物流系統設計的四個核心戰略規劃區域模型（Four major strategic planning areas in logistics system design），他認為四個核心區域為客戶服務水平、選址決策、庫存決策和運輸決策（Customer service levels，Location decisions，Inventory decisions，Transport decisions），對于配送中心選址方法可簡單分為定性和定量兩大類，定性方法主要是層次分析法和模糊綜合評價相結合對各個方案進行指標評價，找出最優地址。定量方法包括重心法、運輸規劃法、Cluste法、CFLP法、Baumol-Wolfe模型、混合0—1整數規劃法、雙層規劃法、遺傳算法等。蟻群算法是一種新型的優化方法，該算法不依賴于具體問題的數學描述，具有全局優化能力。
本文提出了一種基于改進蟻群算法的物流配送路徑規劃方法，將物流配送中心看成一個聚類過程，再利用蟻群系統中螞蟻通過信息素留存尋找最優路徑的機制，結合螞蟻使物體聚堆的行為模式，合理設計轉移概率、禁忌列表及信息素更新方式，使系統配送中心的配送路徑最短，從而確定配送中心的配送路徑。
1 蟻群算法
仿生學家經過大量細致觀察研究發現，螞蟻個體之間通過一種稱為外激素的物質進行信息傳遞，螞蟻在運動過程中，能夠在它所經過的路徑上留下信息素，而且螞蟻在運動過程中能夠感知這種物質，并且以此指導自己的運動方向。受此啟發，它由意大利學者Marco Dorigo于1991年在他的博士論文中引入，提出了一種基于螞蟻種群的新型優化算法——蟻群算法。
蟻群算法（ant colony optimization， ACO），又稱螞蟻算法，是一種用來在圖中尋找優化路徑的機率型技術。其靈感來源于螞蟻在尋找食物過程中發現路徑的行為，螞蟻總能找到巢穴與食物源之間得最短路徑。經研究發現，螞蟻的這種群體協作功能是通過一種遺留在其來往路徑上叫做信息素（Pheromone）的揮發性化學物質來進行通信和協調的。化學通信是螞蟻采取得基本信息交流方式之一，在螞蟻的生活習性中起著重要的作用。通過對螞蟻覓食行為的研究發現，整個蟻群就是通過這種信息素進行相互協作，形成正反饋，從而使多個路徑上的螞蟻都逐漸聚集到最短的那條路徑上。
1.1 研究目的
本研究擬通過學習螞蟻覓食回巢的生物本能，對物流配送進行仿真模擬，找出優化的配送路徑，提高物流配送的效率和效益。
1.2 研究的對象
先對6個同配送點的配送方案進行研究，然后延伸到100個配送點，并找出最佳路徑。以上步驟均通過計算機編程進行演化分析。把研究的成果進行實際應用的演算和驗證。
1.3 研究方法
本文使用蟻群算法，進行人工模擬配送路線，并用計算機編程進行模擬，就如同一只人工螞蟻，背著背包，到若干個結點，搬運食物回蟻巢。
規則1 環境：人工螞蟻所在的環境是一個虛擬的世界，有確定的路線橋，且兩點間路線橋不相交；有信息素，信息素都同質（不區分，找到食物時分泌的信息素和回巢時分泌的信息素），環境以一定的速率讓信息素消失。
規則2 移動：人工螞蟻只會沿著路線橋覓食，當走到結點（覓食點），人工螞蟻會判斷是否有信息素及其濃度，優先選擇信息素濃度大的路線橋為路徑；同時會有一定的概率，隨機選擇別的路線橋；如路線橋上均無信息素則隨機選擇路線橋。
規則3 覓食：人工螞蟻沿路線橋到各個結點覓食，當到達該覓食點后，為防止人工螞蟻原地轉圈，它會記住最近剛走過哪些點（禁忌表），如發現下一個結點是已覓食過的結點，則會避開該點。
規則4 信息素：每只人工螞蟻在遍歷完各點后，系統會利用蟻周算法更新信息素，對總路徑最短的路線進行精英激勵，會大量增加該路線信息素；如果總路徑較長則少量增加信息素；信息素在人工螞蟻遍歷完后，將會按一定速率自動揮發所有路線橋上的信息素。
2 研究步驟
2.1 初始化結點
各個結點進行坐標化，數據存入zuobiao（序號：X，Y）表中，見表1，然后構造成路線橋距離矩陣存入jiedian（序列：1，2，3，…，n）表中，見表2，此次研究擬選用zuobiao表中的結點和數據：
2.2 信息素表示
所有的路線橋上的信息素全部為0，并把信息素數據存入xinxisu（序號：1，2，3，...，n）表中，見表3，用0表示無信息素。
2.3 初始化禁忌表
人工螞蟻比較聰明，當到達該覓食點后，它會記住已找到的結點，并把結點信息存入jinji（序號，禁忌，先后順序）表中，其中0表示未用，1表示已用，詳見jinji表，見表4。
第1只人工螞蟻運行狀態：人工螞蟻從巢穴出發，判斷與該結點連接的各個路線橋上的信息素的濃度，因信息素均為0，則用隨機函數進行選擇路線在jinji表中把起點設置為1（已用），先后順序為1，離開起點沿著該路線橋到達下一覓食結點，信息素為0，則用隨機函數進行選擇路線同樣在jinji表中把第1個覓食結點設置為1（已用），先后順序為2，離開第1個結點沿著該路線橋到達下一覓食結點，判斷信息素，隨機函數選擇路線橋……當6個覓食結點全部走完后，人工螞蟻自動沿著路線橋回到巢穴結點，從而形成完整的閉合回路計算總路線橋長度，用L1表示，同時更新xinxisu表，在路線橋閉合回路全部灑上強度為3的信息素。
第2只人工螞蟻運行狀態：人工螞蟻從巢穴出發，判斷與該結點連接的各個路線橋上的信息素的濃度，原則上沿著信息素濃度大的路線橋通往下一覓食結點，但也會有“叛逆”的情況，用隨機函數產生這種小概率事件，如人工螞蟻遇到小概率事件，則沿著小概率事件選擇的路線橋爬行到下一覓食結點在jinji表中把起點設置為1（已用），先后順序為1，離開起點沿著該路線橋到達下一覓食結點，判斷連接該覓食結點各個方向上的信息素濃度，正常是沿著信息素濃度大的方向移動，同時考慮小概率事件是否發生，如發生則沿著小概率選擇的優先路線前進。同樣在jinji表中把第1個覓食結點設置為1（已用），先后順序為2，離開第1個結點沿著該路線橋到達下一覓食結點，判斷信息素濃度，并優先考慮小概率事件……當6個覓食結點全部走完后，人工螞蟻自動沿著路線橋回到巢穴結點，從而形成完整的閉合回路計算總路線橋長度，用L2表示，更新xinxisu表，判斷該輪路線橋總長度是否是最短，如最短則在第2只螞蟻走過的路線橋上全部灑上激勵的信息素，其值為3，同時，在全部路線橋上按1個信息素/每輪的速率，揮發信息素。
2.4 總路線長度最優的判定
判斷路線橋該輪路線橋總長度是否是最短，可分為如下三種情況。
L1
L1=L2 增加L2閉合回路上的信息素+3 把L2設為最短路徑，用Lmin表示，后續人工螞蟻的Ln均與Lmin比較
L1>L2 增加L2閉合回路上的信息素+3 把L2設為最短路徑，用Lmin表示，后續人工螞蟻的Ln均與Lmin比較
后續n只人工螞蟻和第2只螞蟻一樣覓食（n=80），最終沿著信息素最濃的路線橋爬行各個覓食點，其路徑橋為最短路線。
2.5 參數選取
（1）隨機小概率為0.05，結點6個，信息素對精英螞蟻獎勵+3，對一般螞蟻+1，信息素揮發速率為1/輪。
（2）人工螞蟻選取80只（迭代80輪）。
（3）覓食結點的狀態。其中第1只人工螞蟻比較特殊，路線橋選擇不是按信息素的濃度進行選擇，而是人工賦予隨機選擇函數。在離開原點時選擇概率為1/6，到第一個結點后選擇概率為1/5，到第二個結點后選擇概率為1/4，……，1/1回到巢穴。
2.6 進行演算
覓食結點的狀態選取3種狀態：離散型、聚合型、平均型；隨機小概率事件按分形理論選取20個不同的參數，如下值：0.5、1.5、2.5、3.5、4.5、5.5、6.5、7.5、8.5、9.5、5、15、25、35、45、55、65、75、85、95；每輪螞蟻選擇80只；為了剔除異常收斂，每輪均進行10次演算求出平均值，作為該輪穩定的最短路徑。綜合考慮狀態的聚合度、覓食結點個數、隨機小概率事件，通過編程和建立數據庫，模擬最優路線結果如下：
1354261 其中Lmin=45.2
3 實例分析
為了驗證本算法的正確性，在Matlab平臺上對其進行了仿真實驗。建立如下數學模型，選取福州市某配送中心10個點進行配送，并且要求路徑最短，如表5所示，10個點經過坐標化后是接均型分布，小概率事件選取0.5，人工螞蟻選取80只，每輪進行10次迭代并取平均值。結合迭代運算，得出最優路徑如下：
23456810912
蟻群算法可以比較完美地解決配送路徑問題，但也存在不足之處，特別是在信息不完全的情況下，比如兩點之間有捷徑，模擬最優線路與實際線路會有偏差，同時算法可能會陷入局部最優，可以通過控制收斂速度和加快趨向最優路徑對蟻群算法進行優化。
參考文獻：
[1] 李云清. 物流系統規劃[M]. 上海：同濟大學出版社，2004.
[2] 秦固. 基于蟻群優化的多物流配送中心選址算法[J]. 系統工程理論與實踐，2006（4）：120-124.
[3] 魏娜. 關于物流配送中心選址優化問題研究[D]. 大連：東北財經大學（碩士學位論文），2006.
[4] 高雷阜，等. 基于最大最小螞蟻系統的物流配送中心選址算法的研究[J]. 運籌與管理，2007（12）：42-46.
[5] 許慧，王正友，楊歡慶. 蟻群算法及其聚類應用[J]. 礦山機械，2007（1）：115-117.
［關鍵詞］ 績效預算 目標路徑
一、問題的提出
2003年，黨的十六屆三中全會上提出“建立績效預算評價體系”，七年來，我國已經在績效預算評價研究上取得了一定的成果，學界對績效預算的關注程度也逐漸提高，各級地方政府紛紛開展了績效預算的理論探索和試點實施工作。但是關于績效預算的一些基礎問題卻沒有得到明確的解決，比如績效預算的內容包括哪些？各部分內容的邏輯關系是什么？推行績效預算的根本目標是什么？具體目標是什么？為了實現各階段的目標，哪些部門應當完成哪些工作？如果這些問題沒有搞清楚，那么實施績效預算就像開了一艘沒有羅盤的輪船，不知道前進的方向在哪里。正是由于這些問題沒有得到回答，目前我國在實施績效預算過程中遇到了許多障礙，例如績效預算實施受到一些部門的抵觸、績效預算評價體系不規范、績效評價沒有貫穿預算全過程、績效評估工作流于形式等。本文的研究目的就是試圖對上述一系列基本問題給出一個清晰的回答，對如何正確、有效、規范地實施績效預算給出一個明確的可行的路徑規劃。
二、績效預算包含內容的邏輯關系界定
1.績效預算所包含的內容
績效預算的內涵是：績效預算是以結果為導向的，注重預算的效率和效果的科學化、民主化的預算。它的根本目的是試圖學習私人部門的績效管理和運行方式，以更有效率的方法為公眾提供公共產品。但僅僅了解績效預算的內涵是不夠的，我們同時應該弄清楚績效預算的具體內容，及其各方面內容之間的邏輯關系，以理解各種情況下所指“績效預算”的真實意思。筆者認為績效預算的內容應該包括以下幾個層次：
(1)將績效理論應用于財政資金支出結果的事后評
(2)將績效理論應用于財政資金的分配、使用、結果
(3)將績效理論應用于預算部門自身的工作評價
(4)將績效評價的結果應用于績效溝通和績效管理
(5)將績效理論擴展應用于政府行政管理的全過程
2.績效預算所包含內容的邏輯關系界定
績效預算是一個系統工程，短短四個字卻包含了十分豐富的內容。績效預算應包括5個層次的內容，他們之間是循序漸進，由淺入深的關系。第一個層次只是對財政資金支出結果的評價，是實施績效預算試水階段。第二個層次是對預算的全程評價，主要目標是將績效方法引入到預算資金的分配和使用階段，實現預算全過程的績效管理。第三個層次是對預算工作自身的評價，即預算工作的的績效評價，它和第一和第二個層次的績效評價對象不同，預算績效評價的對象是預算工作或者預算部門自身，而第一、二層次的績效評價對象則是預算資金。第四個層次則是在獲得全面的績效預算評價結果的基礎上，有效地應用結果，切實發揮績效預算結果的價值，促進部門之間的預算工作的溝通，并為下一年度的預算制定作出指導。績效預算的第五個層次則是將績效管理的思想應用到政府的各個部門和各項行政工作中，這既可以說包括在績效預算之中，因為它構成了績效預算實施的環境，也可以說已經超越了預算本身，成為政府的績效管理。
三、我國實施績效預算的目標規劃
在了解了績效預算的內涵與內容之后，我們進而探索績效預算是否可以在我國實施以及用它達到什么樣的目標。至于可行性和必要性研究，許多學者已經從理論和實踐方面給予了充分的論證，此處不再贅述。此處筆者試圖探索績效預算的根本目標，及其短期和長期的目標，以為績效預算的實施提供明確的行動方向和優先次序。
1.根本目標
政府實施績效預算的根本目標就是對預算過程實施科學化管理，追求財政資金的使用效率，并最終更加有效地向公眾提供公共產品。
2.短期目標
在績效預算實施的過程中普遍面臨的問題是績效評價指標的選擇，尤其是定性指標。相比較而言，項目預算比一般預算的結果和產出更容易定量化，更容易測量和評估。所以在短期，我們主要的主要目標是實現項目預算的全程績效管理，具體分為以下幾個目標：
(1)實現各地區、各部門項目預算的財政資金支出結果的績效評價，建立和完善績效預算評價指標體系，將績效預算的理論和方法在政府部門普及開來。
(2)將績效理論應用于預算資金的分配環節。即要求部門在申請項目預算時提交績效預算計劃報告，其中應包括該項目預算的績效目標，具體的績效評價指標，評價方法，以及該項目的工作程序、方法、所需資源等。由財政部門和相關主管部門共同對該項目的績效預算計劃報告進行績效預測和評估，決定是否撥款和撥款數量的多少，實現事前的績效評估。
(3)將績效預算應用于預算的執行環節，用事前的績效計劃報告對項目的實施進行全程監督。不僅要看花錢的進度，更追蹤促實際項目的實現的數量、質量；資監督源分配合理性、資金使用情況等，促進項目的按時、保質、保量的完成。
(4)在項目執行完成以后，由對該項目執行結果進行績效評價。績效評價的指標和方法主要依據初期項目預算申請部門提交的績效預算計劃報告中的各項指標；績效評價的執行主體是財政部門、主管部門、專家學者和公眾代表，公眾對項目實施結果的評價應當是績效評價的主要參考意見，注重公民取向。最終整理、分析出該項目的績效評價總體結果，并將評價結果向公眾公開說明。
3.中期目標
(1)實現對一般預算的績效管理
在實現對項目預算績效管理的基礎之上，我們可以開始對一般預算進行績效管理。這一預算的主要產出就是各單位的行政效率，行政人員工作技能，各單位提供特定公共產品的效率等。對一般預算進行績效管理，其實是為政府部門實現全面的績效管理奠定了基礎。
(2)建立績效評價結果與預算編制相結合的約束激勵機制
在實現對預算過程實施全面的績效管理的基礎上，績效評估的結果就應當開始發揮它的價值。通過對績效評價結果進行分析，財政部門可以辨別各個部門預算執行的質量，因而可以為后期的預算決策提供科學指導。對于預算執行質量高的部門，給予激勵，而對于預算執行質量差的部門給予指導，并且在后期的預算中調整預算計劃。這樣一來，就可以形成了預算決策、預算執行、預算評估的三位一體的激勵約束機制。
4.長期目標
通過一般預算的績效管理推進政府部門的全面績效管理，完成績效預算實施的制度環境改革。這一目標已經不僅僅局限于預算本身，而是擴展到整個政府行政管理體制的績效改革。也就是說績效預算的長期目標是以績效預算為突破口，最終實現政府績效管理，實現為公眾更好地提供公共產品的目的。
四、我國實施績效預算的路徑規劃
由于實現項目預算的全面績效管理是績效預算工作的當務之急，筆者僅就如何實現這個短期目標進行探討。筆者認為我國實現績效預算的路徑，就是一條掃除前進障礙，提供有利條件的路徑，其實也就是為績效預算的實現提供各種支持的這樣一條路徑。要成功地實現績效預算的短期目標，主要需要以下幾點現實支持：
1.思想支持
首先要突破傳統的行政觀念約束，轉變政府行政人員的思想，遏制官僚作風，樹立公共產品提供者和負責人的意識；其次要突破傳統的預算觀念，加強對績效預算的宣傳和推廣力度，樹立一種全新的要產出、要效果的預算意識；第三，要增加公眾參與預算的機會與能力，真正體現公眾作為公共產品需求者的角色，提高公眾對預算決策、預算執行、預算評估的參與度，因為一項預算執行好壞的最終評判標準是公眾的滿意度。最后，績效預算還需要領導者的高度支持，因為績效預算的改革必然會影響到部分既得利益者，必然會跟新興的模式作頑固抵抗，這就需要領導者有足夠的決心和魄力，推進績效預算的順利進行。
2.法律支持
完善預算法案，將績效預算思想融入法案，以法律的形式固定下來。在績效預算的法案中應當明確指出負責績效預算工作推進的具體機構，明確績效預算的主體、目標、績效評價體系構建原則、績效評估工作的要求、績效評估結果的應用等等。這樣一來，績效預算就不會僅僅是一句口號，一種意向，一種提倡，而是成為一項方針，一項具體的有明確負責人和明確執行計劃的改革任務。這樣，各個部門才能明白明確什么是績效預算，目的是什么，各個行政人員必須按照何種標準完成何種事項，以及相應的獎懲措施是什么。法律支持能夠讓績效預算的實施有法可依，增強績效預算實施的規范性和強制性。
3.技術支持
績效預算的核心就是構建規范、科學的財政資金支出的績效評價體系。首先要構建的便是項目預算的績效評價體系。在評價體系構建過程中應當注意以下幾點：
首先，當一些指標難以確定，或者指標評價之間存在沖突時，堅持以公眾的滿意度為最根本的評價標準。
其次，改變目前各地區、各部門各設一套體系，導致績效評價水準參差不齊，績效評價結果可信度差，可比性較差的局面。中央部門應該在百花齊放的同時，博采眾長，集中力量研究出一套質量較高的，并且可以在全國普遍使用的績效評價體系，使得績效評價更加規范化，統一化。另外，當制定一套固定的針對各個部門和各項支出的評價體系存在困難或者不合理性時，我們應當確立一些指定評價指標的原則、規范和指導思想，這樣就可以在遵循一定根本原則的基礎上，又能夠隨機應變，適應各種特殊情況。
第三，不同部門應設置不同的評價標準、模式，有的側重于定量分析，有的側重于定性分析。由此設置相應的共性指標，與個性指標。主要從預算執行情況、財務管理狀況、資產管理情況以及衡量績效目標完成程度的社會效益和經濟效益等方面評價。對適用于不同部門的個性指標，要針對項目實際，結合部門職能和項目管理目標，根據評價的目的，按照一定的程序來制定評價指標和確定評價標準。
4.人員支持
實現項目預算的全面績效管理需要大量的人員支持。一方面要培養績效預算、績效管理的專門人才，建立績效預算學者庫，專門對績效預算的相關理論進行研究。另一方面要對行政人員進行績效預算知識的培訓，使之具備績效預算操作的技能。除此之外，我們也更應當重視對公眾的培養，提高公眾對績效預算的參與積極性和參與能力，因為科學的績效預算的評價離不開公眾的廣泛和深度的參與。
5.制度支持
成功地實現績效預算同樣需要相關的制度支持。在實現短期目標的過程中，我們應當完成對以下制度的改革：進一步完善目前的部門預算制度；完善國庫集中收付制度；改革政府采購制度；完成會計制度由收付實現制向權責發生制度的過度；完善預算的監督制度，并且對預算過程實行問責機制，向單位問責，向個人問責；最后，要增加預算的公開透明度，對于預算信息哪些應該公開，公開到什么程度，政府應該做出明確的要求。
當然上述的每項制度的變革都是非常艱辛和復雜的過程，必然會對績效預算的實施形成阻力，但是它并不能夠阻止績效預算的腳步。即使制度環境不是那么優越，條件不是那么成熟，績效預算的推進也勢在必行。等待，只會延長上述一些不合理制度存在的時間。筆者認為，績效預算既是一種目標，也是一種手段，可以成為改革不合理制度的壓力和動力，最終在實現績效預算的過程中也完成了制度的改革。
參考文獻：
[1]馬國賢: 政府績效評價[M] . 上海:復旦大學出版社,2005.
[2]彭鍛煉 左武:推行政府績效預算管理改革的難點與目標[J]. 中南財經政法大學學報,2009,(6)
[3]白景明:全面認識績效預算[J].中國財政.2009.(24).
[4]孔志峰:績效預算論. [M].北京:經濟科學出版社.
1、蔣巷村——農業起家、工業發家、旅游旺家
蔣巷村以農業起步，在先天農業條件較差的情況下，上世紀60年代通過大力治水改土工程改良土地，實現農業的快速發展；80年代，蔣巷村瞄準市場先機，通過自籌資金發展建材加工業，迅速躍升為該省的龍頭產業，提高了村莊經濟實力；進入新世紀，蔣巷村在大力鞏固拓展工業的同時，以工業發展帶來的經濟效益反哺農業，打造農民新居、農業規模化生產以及生態種植園，并建立起一系列景點設施，發展鄉村生態旅游業。蔣巷村的成就與當地政府扶持和推廣分不開。早期農業經營分散，規模效益不高，當地政府及時提供涉農優惠政策，引導蔣巷村依托成立農民專業合作社組織，帶動了廣大農戶增收。工業方面，當村級龍頭企業遭遇金融危機以及其他企業的激烈競爭時，政府部門主動對接企業，實行增值稅轉型政策助推企業轉型升級，將其推入一個新的發展階段。旅游業方面，該村旅游資源并不突出、旅游吸引力較低，政府一方面大力推廣宣傳，一方面積極開展旅游業稅收優惠措施，支持和鼓勵企業開拓市場，大力扶持其鄉村旅游品牌。蔣巷村在資源條件相對貧瘠的情況下，走出了一條“改天換地、農業起家、工業發家、三產協同”的創新發展之路，以農業為基礎、以工業為重點大力發展經濟建設，并通過工業經濟反哺農業、旅游業的發展，實現了一、二、三產業的互動發展，帶來經濟效益的良性循環。
2、大山村——本底良好、政府拉動、旅游慢村
早期大山村由于處地偏僻交通不便，經濟發展緩慢，但生態環境保持良好，2005年高淳確定“生態立縣”的發展方向，重點打造“國家生態示范區”，在此機遇下大山村走上了一條快速發展的生態旅游轉型之路。在政府主持和出資下，大山村積極開展基礎設施建設、對建筑風貌進行改造，打造田園風光特色，扶持農家樂專業戶，一躍成為本省內的鄉村旅游示范點。2011年，隨著椏溪鎮被評為“國際慢城”，大山村作為“國際慢城”的核心組成部分，具備非常突出的發展條件和優勢。通過實施新農村建設工程、調整農業產業結構、發展休閑農業，打造高標準的鄉村旅游業。為保障旅游配套服務業的高水平化，椏溪鎮政府出臺了統一的農家樂資格認證標準，并出資對環境整治進行改善和提升。目前村內已建成16家特色農家樂，可同時接納上千名游客，每戶年均收入達30-40萬元。該村還通過招商及合資的方式開發休閑精品旅游項目，打造特色旅游產品，擴大“國際慢城大山生態之旅”的影響力和知名度。大山村在本底條件和區域環境基礎上，通過政府扶持，以“整體打造、標準管控和庭院經濟”的重點，實現了旅游產業的跨越式發展。政府主導的整體打造有效地保證了旅游產業的整體質量，強調政府對旅游硬件設施的標準性把控有效避免了接待設施的參差不齊，推廣庭院經濟充分利用村民房前屋后的院落以及零星的土地、水塘，形成果蔬種植、家禽養殖、居住、餐飲接待等復合功能，打造出家家門前有綠樹、戶戶門前有花香的生態經濟循環發展模式。
3、張陽村——農業起步、發展苗木、拓展旅游
同大多數村莊一樣，張陽村早期發展仍以基礎農業起步，該村用地較為平坦，水資源豐富，氣候溫暖濕潤，農田規模集中，糧食產量也較高。良好的農業條件為張陽村的發展打下了堅實的基礎。70年代初期以前，張陽村依托10多個礦山宕口大搞礦業開采，以采石、采礦為主導產業，當時大量山體破壞嚴重、植被遭到砍伐，路面坑洼，造成了嚴重的污染。80年代，隨著張公洞風景區的打造，部分村民意識到市場先機，上山挖來木樁制成盆景，受到游客青睞。越來越多的村民投入到苗木盆景的制作中，張陽村開始了規模化的苗木盆景栽培，在政府的幫助下，建立起專業的花卉苗木基地，取得了良好的經濟效益和示范作用。隨著花卉苗木品牌的擴大，以及張公洞、玉女潭等旅游景點的知名度上升，張陽村開始轉型為鄉村休閑旅游與自然觀光旅游。2003年該村成立了花卉苗木專業合作社，開辟了1000畝的花卉盆景基地，打造以苗木、吊瓜、茶葉、楊梅、青梅、板栗等六大特色的種植基地5000多畝。培養出龍潭苑樹樁苗木基地、偉達開心農場、瑞龍潭生態園等集觀光旅游與農事體驗為一體的旅游景點。張公洞、玉女潭的開發更是吸引了大量省外游客，張陽村前后投入4000多萬實施美麗鄉村建設，整治環境景觀和旅游配套服務設施，形成了以景點觀光、農業體驗、養生度假為主的休閑旅游業。張陽村的發展路徑經歷了由農業起步，高污染的礦業開發治理到特色化農業生產再到休閑旅游業四個階段，其特色在于依托良好的自然環境和獨特的旅游資源，打造苗木盆景特色產業，借助景區效益推廣鄉村旅游品牌，并在此基礎上以苗木產業為依托積極融入區域旅游的大圈子，形成了農業、苗木、鄉村旅游三業并舉的發展格局。
作者：劉方 單位：重慶市規劃設計研究院
針對標準遺傳算法解決機器人處于障礙環境下尋找最優路徑局部尋優精度較差、規劃效率低的問題，提出一種改進遺傳算法的機器人路徑規劃方法。該算法采用一維編碼表示路徑， 構造了路徑最優化的目標函數和適應度函數，利用多個種群拓寬搜索空間，提高了規劃效率，采用保優選擇策略，避免陷入局部最優。仿真結果表明，改進遺傳算法比標準遺傳算法路徑規劃質量高，能夠獲得平滑的低代價路徑，穩定性好，是機器人路徑規劃的一種較好的方法，且具有一定的推廣意義。
機器人路徑規劃問題一直是機器人學的一個重要研究課題. 也是目前研究的熱點領域。機器人路徑規劃問題是指在有障礙物的工作環境中， 如何尋找一條從給定起點到終止點的較優的運動路徑， 使機器人在運動過程中能安全、無碰撞地繞過所有的障礙物， 且所走路徑最短.本質是多約束多目標的最優化問題[1]。
采用智能優化算法求解航跡規劃問題是目前使用的主流方法。文獻[2]中，蟻群算法的機器人路徑規劃需要存儲的信息多，在搜索過程中易出現停滯現象或陷入死循環;文獻[3]中的人工勢場法雖便于底層的實時控制，但缺乏全局信息，存在局部最優值的問題;文獻[4]中，模糊推理法最大的優點是實時性非常好， 但是模糊隸屬函數的設計、模糊控制規則的制定主要靠人的經驗。遺傳算法[6]已證明是一種全局搜索能力強的算法，具有強的魯棒性，并行性，但大量實驗結果表明，應用標準遺傳算法對該問題求解時局部尋優精度較差，穩定性不好[6]。
對此，本文提出一種改進遺傳算法的機器人路徑規劃方法，并進行了仿真實驗，結果證明了該方法是有效可行的。
結束語
針對標準遺傳算法解決機器人處于障礙環境下尋找最優路徑局部尋優精度較差、規劃效率低的問題，提出一種改進遺傳算法的機器人路徑規劃方法，并進行仿真，實驗表明該算法具有高的穩定性，并減少了陷入局部最優的可能，且規劃出的路徑精度更高。同時，提出的模型可引申應用于類似情況下的路線規劃問題，具有一定的推廣意義。
有些學者從微觀經濟理論的角度探索消費和投資的最優比率。例如,Phelps構建了不確定收入下的最優消費率[2]。基于這一模型,Merton以布朗運動模擬不確定收益,利用動態規劃建模的方式,求出在連續時間假設下獲得最大消費效用的消費和資產投資組合[3]。然而Merton的模型采用了Pratt的絕對風險厭惡度(absolute risk aversion)[4],即假設投資者的風險偏好是和年齡、財富無關的常數,從而把家庭總財富比率設計成常數。為了改進過于嚴格的常系數風險厭惡假設,Farhi和Pan-ageas假設投資者可以通過控制退休時間來調整勞動供給,從而實現最優消費和投資[5]。另外有些學者拓展了Merton等人的模型,如Hakansson和Richard研究了存在保險時的生命周期最優消費[6][7];Karatzas使用鞅方法研究了個人如何選擇消費率來實現消費和財富效用最大化[8];Bodie等人探討了退休期間的最優消費投資問題[9]。有些學者則從宏觀經濟學的角度闡述消費和投資對消費效用最大化的影響。李嘉圖的古典消費理論強調了消費對經濟的刺激。凱恩斯絕對收入假說認為消費主要取決于當期絕對收入,平均消費傾向(APC)隨收入增加而減少。按此假說,一戰后,美國人民收入增加,儲蓄應隨之增加。但是,Kuznets實證研究發現戰后儲蓄并未增加,長期APC穩定[10]。為解析上述矛盾現象,Duesenberry提出相對收入假說,家庭會比較其他家庭的收入,即相對水平,來決定自己的消費水平[11](P3)。相對收入假說的缺陷在于家庭的消費是短視行為,沒有考慮未來收入。為克服相對收入假說存在的問題,Friedman提出了家庭將根據終生收入來決定消費的持久收入假說[12](P26-135)。內生增長理論被廣泛用于分析投資和消費的最優分配。該理論假設在生產過程中的規模收益不變,即凸性生產技術,經濟增長的決定因素是生產要素,生產率是由模型內生所決定的,而不是由資源、人口等外部因素決定。典型的內生增長模型有AK模型、Rebelo模型等[13]。
曾經有人質疑AK模型是否可以用來評估經濟增長。Jones建立了技術為常數的AK模型,對函數關于物質資本和人力資本求最大值,并基于1950~1988年加拿大、法國、德國等15個OECD國家的時間序列數據,研究發現戰后投資額同經濟增長無關,并由此推斷AK模型對投資和經濟增長關系的預測是短期的或不正確的[14]。為了反駁AK模型不適用于研究經濟增長的結論,McGrattan建立了技術為常數的AK模型,對函數關于消費和資本求最大值。McGrattan用1870~1989年11個國家的數據驗證了投資率和經濟增長之間的正相關關系,證明政府投資誘導政策會永久性影響經濟增長[15]。McGrat-tan發現Jones之所以用AK模型測不出投資和經濟增長的相關性,一是數據期限短,二是模型設計存在缺陷。McGrattan的模型假設如下:(1)代表性家庭選擇投資和消費,從而實現生命周期效用最大化;(2)家庭有兩種資本,分別是結構資本和設備資本,家庭收入來源于把結構資本和設備資本租給公司的租金;(3)家庭收入要向政府繳納稅收,因此政府政策可以影響投資產出比和勞動閑暇選擇。這樣一來,McGrattan就解釋了Jones觀察到的投資增加而產出穩定的短期離差,并從理論和實證角度驗證了AK模型的有效性。本文在持久收入假設和內生增長理論框架下,研究經濟增長的最優消費投資比率,從理論上指導國民收入的合理分配。之所以選擇資本產出彈性為單位彈性的AK模型,是因為資本對發展中國家很重要。發展中國家可以通過購買技術先進的國家的設備得到知識,這種由投資帶來的技術溢出可以加速整個國家的現代化。另外,由于行業間存在溢出效應,當資本提高某個行業的生產率時,與之相關行業的生產率也隨之提高[16],所以不僅要考慮資本對單個行業的作用,還需要考慮資本的社會回報。Ljungqvist和Sargent建立的AK模型與本文有類似的目標函數yt=Akαt,也猜測了相同的值函數形式,并得到了類似的策略函數[17],但本文與之不同的是:第一,他們假設資本產出彈性大于零而小于1(0<α<1),從而使資本邊際效用遞減,通過數學推導發現資本收斂,而本文假設資本產出彈性等于1(α=1),從而使資本沒有邊際效用遞減,通過數學推導發現資本不收斂,而值函數收斂;第二,本文考慮了資本折舊;第三,本文通過真實數據,再現改革開放以來消費和投資對提高社會效用的貢獻。本文余下部分的結構安排如下:第二部分建立包含資本折舊率和貼現因子的最優消費模型,通過猜解求出策略函數,討論了消費、資本積累序列的意義,并通過求導分析了各變量對值函數的影響;第三部分比較了不同貼現因子下的值函數,并用三維效果圖展示了1978~2010年中國消費、資本和值函數的演變關系;最后是本文的結論。
模型
本文考慮生產單一商品的經濟,此商品既可消費又可投資,投資以資本的形式體現,消費品和資本品可以相互轉換。消費數量和消費投資比決定代表性行為人的效用,社會計劃者的目標是通過政策引導消費路徑,使代表性行為人在任意時期都能獲得最大效用。經濟增長由資本驅動,因此設生產函數為yt=Akt,其中A反映技術水平,yt、kt和ct分別表示在時期t的生產量、資本存量和消費。對于任意t期,有ct≥0,kt≥0;且初始資本k0已知。由此,可得模型:max∑!t=0βtln c(t)s.t.kt+1=yt+1-(δ)kt-ct, yt=Ak烅烄烆t(1)其中δ為資本折舊率,0≤δ≤1;β為貼現因子,0<β<1;βtln c(t)是消費效用。式(1)是終生消費效用,資本積累規則為下期資本的數量取決于本期的有效商品總供給和本期的消費。令f k(t)=Akt+1-(δ)kt=(A+1-δ)kt表示包含資本折舊的有效商品總供給,則式(1)可轉化為:max∑!t=0βtln c(t)s.t.kt+1=f (kt)-ct,f (kt)=(A+1-δ)k烅烄烆t(2)式(2)目標函數的含義是代表性行為人追求一生消費的貼現效用最大化,其中消費ct是控制變量,資本kt為狀態變量。由約束條件kt+1=f (kt)-ct,可得ct=f (kt)-kt+1,即控制變量可表示為狀態變量的函數。求式(2)的最優解,就是在給定約束條件下,找到一個恰當的序列ct,k{t+1}!t=0,使目標函數∑!t=0βtln (ct)取得最大值。(一)猜解求值函數和策略函數為方便求極值,將式(2)由離散形式轉化為連續形式,并定義值函數()V k為投資者在給定財富下所能達到的期望終生總效用。在競爭性均衡中投資者的效用得到了最大化,則根據漢密爾頓-雅可比-貝爾曼方程(Hamilton-Jacobi-Bellman equation,HJBE)可得:()V k=maxk'()ln [f k-k]'+β{V (k)}'()=ln [f k-g(k)]+βV [g(k)](3)式(3)中,k是當前時期的資本存量(相當于kt),k'是下一時期的資本存量(相當于kt+1)。g(k)是利用HJBE進行遞歸迭代的策略函數,且g(k)=k',表示計劃者面臨的決策為:究竟是應該用政策引導代表性行為人當期多消費一些,還是當期少消費,留作下一期的資本,從而使下一期能消費更多。()V k和g(k)都是連續可微的。根據動態規劃理論,可猜測值函數的形式為:()()V k=E+Fln k(4)其中,E、F是待定常數。對式(3)和(4)計算一階最優的必要條件,并根據式(2)可得:g(k)=k'=βF A+1-(δ)k1+βF(5)()c=f k-k'=A+1-(δ)k1+βF(6)式(5)是策略函數g(k)關于k的顯式解,F是待定系數。(二)最優消費、資本累積序列令n=1,式(3)變成式(7)。由式(2)可知當t=1時,以下兩式成立:V1()k=maxk'()ln f k-k[]'(7)V1()k=maxk'()ln f k-k[]'+βV0k()'(8)式(7)是目標函數(2)的最大值,即社會計劃者最優問題中的值函數;式(8)表示代表性行為人一生的效用貼現值等于當期效用、未來效用的貼現值之和。當期消費和期末資本的選擇c,k{}'產生了當期效用ln(c),下期的資本k'將按照策略函數g(k)來選擇。此處可獲得的最大期望效用是V k()',而k'的貼現值為βV0k()'。類似的,利用式(5)、式(3)逐期遞歸迭代可得到值函數Vn()k序列。對任意t期,有:Vn()k=∑n-1i=1(β)i-1 lnA+1-δ1+β()F+βn-1ln (A+1-δ)+ ∑n-1j=1j(β)j lnβF A+1-(δ)1+β[]F+∑ns=1(β)s-1()ln k由于0<β<1,根據級數理論容易證明:當n!時,Vn()k是收斂的,且其極限值()V k=limn!Vn()k就是無窮序列的唯一解。也就是說,得到的函數方程與式(4)的猜測完全符合。可以解出E=11-βln (1-)βA+1-[(δ)]+β1-(β)2lnβA+1-[(δ)],F=11-β。將E和F代入式(4)可得到函數方程(3)的具體表達式和相應的策略函數:()V k=11-βln (1-)βA+1-[(δ)]+β1-(β)2lnβA+1-[(δ)]+11-β()ln k(9)g(k)=βA+1-(δ)k(10)式(9)也就是式(1)的解。對于任意給定的k0>0,值函數()V k采用策略k'=g(k)=βA+1-(δ)k恒可取得最優值。回到式(1)的離散形式,對任意時期t(t≥0),當資本存量按策略kt+1=βA+1-(δ)kt逐步演變時,式(1)必定取得最優解。相應地,ct=1-(β)A+1-(δ)kt。綜上所述,可得式(1)的最優消費、資本累積序列ct,k{t+1}!t=0為:ct=1-(β)A+1-(δ)ktkt+1=βA+1-(δ)k烅烄烆t(11)從式(11)可以看出:資本折舊率δ和當期消費ct以及下期資本kt+1負相關。資本折舊率反映了資本的使用成本,折舊率越大,資本越少,收入越少,可供消費也越少。對資本的良好維護,可以降低資本折舊率。宏觀政策能改變折舊率,比如政府推出投資刺激政策,會使維護既有資本的成本高于重新投資,從而提高資本折舊率;再如,高利率增加貸款成本,導致生產者更傾向于用廉價原材料,產品耐用度降低,資本折舊率提高。貼現因子β和當期消費ct負相關,和下期資本kt+1正相關。貼現因子反映了資產預期總收入超出當期總收入的部分折現到當期末的值。貼現因子越小,代表性行為人越傾向于當期消費ct;貼現因子越大,代表性行為人越希望把消費推遲到將來。貼現因子是隨機的、主觀的,受真實的經濟發展變化的影響,可以通過宏觀經濟政策引導貼現因子變化。比如福利保障制度可以提高當期消費者的信心,而提高利率會導致人們推遲當期消費。α=1時,AK模型y=Akαt的資本增長率kt+1kt=βA+1-(δ)更大,而且資本不收斂。0<α<1時[1 7],AK模型y=Akαt的資本增長率kt+1kt=αβAkα-1t更小,而且資本收斂。另外,根據方程(1)最優解的一階必要條件可以斷定,當且僅當ct+kt+1=Dkγt(D為常數,γ是大于零的任意實數)的形式時,即ct+kt+1必須與kγt成正比關系,AK模型才可能求出顯式的最優解。
關鍵詞：GPS手機導航；移動GIS；ArcGIS for Android；Dijkstra算法；最短路徑
中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2014）06-1294-05
Research and Application of Campus Navigation System Path Planning Based on Android
WU Qi1，LIN Jing1，YANG Jiang-tao2，3
（1.School of Computer Science and Control Engineering， North University of China，Taiyuan 030051，China； 2.Science and Technology on Electronic Test and Measurement Laboratory， North University of China，Taiyuan 030051，China；3.Key Laboratory of Instrumentation Science&Dynamic Measurement of Ministry of Education， North University of China，Taiyuan 030051，China）
Abstract： Regarding colleges and universities as the research objects and combining the digital campus with GPS mobile navigation system， a smartphone campus navigation system is designed by using the mobile GIS， Android platform and ESRI's ArcGIS Android API plug.Taking the campus of The North University of China as an example， the paper realizes the design of system architecture， describes data organization and the function of system. After comparing three kinds of classical shortest path algorithms， the authors select Dijkstra algorithm to achieve the shortest path selection in the smartphone campus navigation system.The implementation of the system provides a convenient， fast and intelligent navigation services for freshmen and visitors.
Key words： GPS mobile navigation； mobile GIS； ArcGIS for Android； Dijkstra algorithm； shortest path
隨著高校校園的逐漸擴建以及對外交流的日益增多，來高校參觀、訪問的人也越來越多，但高校面積一般都很大，機構和重要建筑分布錯綜復雜，來訪者要經過一番周折才能到達目的地。而且高校一般很少提供紙質的地圖向來訪者提供導航服務，因此，建立具有校園信息查詢、智能導航服務等功能的系統，對高校提高人性化服務水平很有必要。
目前，國內高校對于基于PC的校園智能導航研究得比較多，如清華大學虛擬校園、華中科技大學校園導航系統。相比之下，大部分高校對Android系統上的校園導航都缺少研究，而今Android開發技術日新月異，將傳統PC機的導航系統用Android技術實現已成為可能。隨著移動通信的發展，手機已經不僅僅是解決通話的問題了，它漸漸成了集通信手持電腦于一體的移動計算工具，人們對手機所賦予的功能也已經擴展到分布式計算、移動位置服務等更高端的領域。導航軟件在智能手機中的應用現已成為研究熱點之一，越來越多的互聯網應用被移植到智能手機中來，不但充分發揮數據業務運營商的潛力，而且極大的提高了用戶對手機多功能需求的滿意度，給人們的生活帶來了方便。本課題基于這種考慮，設計了一種基于Android的校園智能手機導航系統。采用Dijkstra算法并利用GIS系統的空間數據特性，根據實際情況對任意兩點間最短路徑進行規劃，在智能手機平臺上實現了優化路徑選擇，為新生和校外來訪人員提供了非常便捷的服務。本系統實用性強，易于開發、管理和升級，很好地解決了初次來學校的新生和校外來訪人員所遇到的問題，既方便了新生和校外來訪人員，又提高了學校的美譽度，具有很好的應用價值[1]。
1 系統開發理論基礎
1.1 系統背景介紹
校園是大學生日常活動的主要空間。大學校園通常具有面積大、開放性強、建筑布局分散、各類設施雜亂等特點，校園地理信息相對來說比較復雜。這給校園內的每一個人尤其是對大一新生和校外來訪人員帶來諸多不便。因此，開發出一個為新生和校外來訪人員提供校園信息服務的智能手機導航系統十分必要[2，3]。
1.2 移動GIS技術
地理信息系統（簡稱GIS）[4]是一種特定的十分重要的空間信息系統，是在計算機軟、硬件系統支持下，對整個或部分地球表層（包括大氣層）的有關地理分布數據進行采集、存儲、管理、運算、分析、顯示和描述的技術系統。移動GIS[5]是GIS（地理信息系統）從靜態走向動態環境的重大發展，通過綜合運用GPS的精確定位技術、便攜移動設備（如掌上電腦、智能手機）、移動通信技術和GIS的空間信息處理能力，使野外工作者能夠利用該系統實時地獲取、存儲、更新、處理、分析和顯示地理信息。
1.3 ArcGIS for Android介紹
ArcGIS for Android將GIS的適用范圍從辦公室擴展到移動Web。時，ArcGIS for Android 將包括一個應用程序，您將能夠從Android Market應用商店下載這款稱為ArcGIS的應用程序。這個應用程序類似于已經的ArcGIS for iOS和Windows Phone應用程序。使用該ArcGIS應用程序，您能夠瀏覽或ArcGIS Server提供的地圖，并且利用程序中提供的工具進行搜索，識別位置和要素，測量線和面，以及編輯[6]。
2 系統設計
2.1 系統結構設計
本系統的結構分為服務器端的搭建和客戶端軟件的開發。使用ArcGIS Server在服務器計算機上搭建一套完整的地圖服務，能夠自己的地圖和隨時對地圖信息進行編輯。客戶端軟件所要開發的功能有地圖顯示、地圖定位、位置搜索、選擇圖層、路徑導航等。系統功能結構圖如圖1所示。
圖1 系統功能結構圖
2.2 數據庫設計
1）在圖層中創建一個線要素Road，用于表示地圖中的道路，再給該要素添加屬性，為了方便與最短路徑的計算，添加了道路的長度、限速值、行駛時間、端點信息等屬性，OBJECTID是自動生成的用于唯一標識一個要素，SHAPE是指要素的類型，這里是幾何類型，由于Road是線要素，所以系統也會自動生成SHAPE_LENGTH屬性，默認表示該線段的幾何長度，SpeedLimit和DriveTime都是自己另外添加的屬性，為計算最短路徑功能所用。如表1所示。
2）為了實現智能導航系統的選擇圖層功能，再向圖層中添加一些生活常用的信息點，如醫院、停車場、電影院、美食、銀行、加油站、超市等，所以又添加了11個點要素：Food、Hospital、Shop、Park、KTV、Movie、Bank、Gas、Medicine、KFC、Mcdonald。每個要素各對應有自己的屬性表，由于他們都類似，下面只列出其中的一個表，如表2所示。
表1 道路信息表
表2 醫院信息表
3 核心問題和難點問題
路徑導航功能是該系統最核心且最有難度的功能，路徑導航就是用戶設定一個起點（或以當前定位點為起點）和一個終點，系統采用一種最短路徑算法來通過計算求出所設起點到終點的最優路徑。在空間決策模型中，實現行駛最優路徑的規劃算法是空間決策的核心內容。只有構建出最優路徑模型，系統終端獲取的地理位置信息才能夠最迅速快捷地用到校園導航路線的選擇和優化中。
3.1 三種最短路徑算法的比較與選擇
本系統最核心的算法就是導航功能中的最短路徑選擇算法，為了選擇最適合于本系統的最短路徑算法，對常見的三種最短路徑算法進行分析和比較，歸納出這三種最短路徑算法的對比如表3所示。
表3 三種最短路徑算法對比表
根據對比可以看出，Dijkstra算法在時間和空間上都是優于Floyd算法和Bellman-Ford算法的。不足之處就是Dijkstra算法不能處理含負權邊的圖。但根據本系統的實際情況，地圖中的道路長度一定為正數，最短行駛時間也一定為正數，所以對于本系統來說，Dijkstra算法的這個缺陷可以忽略不計。因此，本系統選用Dijkstra算法來計算導航功能中的最短路徑問題。
3.2 經典Dijkstra算法過程分析
Dijkstra算法也是求單源最短路徑的算法，思想就是以源點s為中心，向外層層擴展，直到擴展到終點為止。算法思路如下[7]：
1）初始化：設源點s的dis[s]=0，除源點外的其他點dis[i]=無窮大，同時把所有的結點的狀態都設為未擴展狀態；
2）循環V次：在未擴展的點中取一個dis值最小的點i，把結點i標記為已擴展的，并對和點i相鄰的每一個點j進行松弛操作，即更新dis[j]的值；
3）算法結束后，對于任意的點i，dis[i]就是源點s到結點i的最短距離。
算法的偽代碼如下：
For each v ∈ V（G）
do dis[v] = INF；
dis[s] = 0；
把結點都插入優先隊列Q
while Q非空 do
i = Q.top（）；
把i標記為已擴展
For each edge（i，j） do
If j未標記 and dis[j] > dis[i] + w[i，j] then
dis[j] > dis[i] + w[i，j]
如果用普通的鄰接矩陣來存儲圖的結構，只能在每次循環里面再用一個循環來找出dis值最小的結點，那么時間復雜度將是O（V2）。所以為了優化時間，可以使用優先隊列來保存所有結點的dis值，優先隊列的內部實現一般都是使用二叉堆，所以建立和維護這個優先隊列的時間復雜度是O（log|V|），所以Dijkstra算法的總時間復雜度是O（E+V*log|V|），空間復雜度是O（V+E）。
4 系統功能及其實現
4.1 系統主要功能
我們要實現的是校園智能手機導航系統，服務的對象是入學不久的新生和初到校園的校外來訪人員，所以此系統的設計應遵從“界面直觀，功能鮮明，使用簡便”的原則，從而為新生和校外來訪人員了解校園環境提供便捷和幫助。系統具有的功能大致如下：
1）數據的更改和刪除。由于高校校園逐漸擴建，校園地理環境不斷變化，對于已經建成的校園導航系統，進行及時準確的更新十分必要。系統可以在數據庫中對現有的數據進行刪除、修改，從而實現對校園地圖和屬性的及時更新。2）數據的查詢和顯示。用戶可以通過輸入關鍵詞后在地圖上搜索地點。對于顯示在地圖窗口的地圖可以進行放大、縮小、漫游等操作，用戶還可以根據自己的需要及興趣點控制各個圖層的顯示，使查詢的信息更加明顯。3）空間分析查詢。打開客戶端軟件時，手機進行實時GPS定位，獲取當前位置后在地圖上顯示位置坐標，并顯示附近的地圖信息。基于“Dijkstra算法”的最短路徑導航功能還可以對任意兩點可以進行最短路徑的查詢和導航，這是系統最核心的功能，用戶通過輸入起點（或以當前定位點為起點）和終點可以迅速查詢出兩點間最短路徑，為新生和校外來訪人員提供了非常便捷及人性化的服務。
4.2 性能測試分析
1）GPS定位功能實現。在移動端采用坐標定位的方法，如果手機的GPS定位功能已開啟，地圖會自動定位，獲取到當前的坐標時，地圖控件會自動平移到當前的位置。界面如圖2所示。
2）搜索地點功能實現。在搜索框中輸入關鍵詞地名，例如“金虎超市”，點擊搜索按鈕，就會向服務器發送請求，若能找到，則返回它的坐標，然后客戶端就在地圖中顯示一個藍色的點，表示搜索的位置。界面如圖3所示。
3）選擇圖層功能實現。基于用戶興趣點選擇圖層，其中包含的圖層有：美食、醫院、超市、停車場、KTV、電影院、銀行、加油站、藥店等。用戶選擇感興趣的圖層后，可以在地圖上顯示對應的圖標。界面如圖4所示。
4）路徑導航功能實現。采用Dijkstra算法實現最短路徑的選擇，當用戶設置起點（或以當前定位點為起點）和終點后地圖會在該兩點顯示標記，點擊導航按鈕后，地圖上就會顯示出從起點到終點的一條最優路徑。界面如圖5和圖6所示。
圖2 GPS實時定位界面 圖3 關鍵詞搜索地點界面 圖4 興趣點選擇圖層界面
圖5 最短路徑導航界面（用戶設置起點） 圖6 最短路徑導航界面（以當前定位點為起點）
5 結束語
校園智能手機導航系統的建立是校園數字化的一種體現，為學校日后建立綜合校園管理體系奠定了基礎。利用Dijkstra算法實現了最短路徑的選擇，獲得的最短路徑的屬性數據得以顯示，提供了及時且更直觀的校園導航系統的信息。通過測試，本系統起到了為新生報到和校外來訪人員提供指南導航的作用，提供了方便、快捷的智能導航服務信息，從而提高了學校管理水平和工作效率。系統服務于高校的規劃和建設，可以為高校的發展做出一定的貢獻。基于Android平臺可以快速有效地進行系統開發，極大地減少了程序開發工作量，縮短了開發周期。可以實現高效、無縫的系統集成，這是未來GIS程序開發的發展趨勢。隨著GIS的發展的日新月異，相信其應用領域也將有更大拓展。希望該系統的設計方案和核心模塊的功能實現方法能為此類系統的設計提供一定的參考。
參考文獻：
[1] 王福平，喬丹，王俊彩，胡長中.基于嵌入式的校園智能導航系統設計[J].計算機應用，2011，31（z1）：146-148.
[2] 劉永軒，原凱敏，劉芬等.基于GIS的山西師范大學新生報到導航系統[J].科技情報開發與經濟，2010， 20（32）：107-109.
[3] 虞昌彬，謝瀟.基于.Net平臺的校園新生導航系統[J].福建電腦，2008，10：121-122.
[4] 唐偉奇.校園地理信息系統的開發與實現[J].科學技術與工程，2006，6（8）：1102-1118.
[5] 袁滿，于海洋.基于ArcGIS Mobile的油田移動GIS系統架構與實現[J].科學技術與工程，2011，11（20）： 4800-4803.
關鍵詞：農民工；職業生涯規劃；路徑
中圖分類號：F241文獻標志碼：A文章編號：1673-291X（2011）12-0111-02
浙江是一個勞務輸入大省，溫州也是一個勞務輸入比較集中的城市。2005年起溫州市政府把到溫州務工的農民工稱為“新溫州人”，充分體現了政府號召人們對進城務工人員的認可和尊重，從思想觀念上消除對農民工的歧視和偏見，切實讓農民工享有平等待遇。據溫州市公安局統計，2008年12月，溫州市公安局對外公布全市登記在冊的外地暫住人口為3 396 053，主要以湖南、湖北、貴州、江西、安徽、四川等省，暫住人口中務工的為3 135 307人，從事服務業的58 805人，務農的24 250人，溫州已經成為創業的第二故鄉。溫州對農民工有著巨大的吸引力，溫州的發展也同樣離不開農民工。
一、職業生涯規劃內容
隨著越來越多的農民工朋友進入到城市里展開個人的城市生涯，每個人都要借助于謀求職業而實現自我的發展。職業生涯規劃，簡稱職業規劃，就是對個人的職業歷程乃至整個一生進行持續的、系統的、規劃性的設計的過程。從個人角度和企業角度，職業生涯規劃又劃分為兩個方面的內容：
1.個人職業生涯規劃：企業中的大多數員工，其中包括受過良好教育的員工，都有從自己現在和未來的工作中得到成長、發展和獲得滿足的強烈愿望和要求。為了實現這種愿望和要求，他們不斷地追求實現職業的理想，能主動根據個人的特點、企業發展的現實和社會發展的需要，制定自己的職業規劃。
2.企業員工職業生涯管理：在廣大員工希望得到成長、發展的強烈要求推動下，企業人力資源管理部門（或人事部）為了更好地開展工作，在了解員工個人的特點，成長和發展的方向及興趣的基礎上，通過一些宣傳、教育和咨詢等活動，幫助員工制訂有關個人成長、發展的計劃以及與組織需求和發展相結合的計劃，不斷地增強他們的滿意感，并使他們與企業組織的發展統一協調起來。可見，職業生涯規劃既要體現員工發展的需要，又要體現企業發展的需要，是員工個人發展與企業發展的一種協調與相融。
二、農民工做好職業生涯規劃的意義
職業生涯規劃對所有工作年齡的人來說都很重要，在人一生的歷程中，需要靠職業來生存和發展。每個人都需要規劃好自己的職業生涯，主動去把握它、迎合它、順應它才是生存之道。有些農民工朋友會說，職業生涯規劃，那是大學生的事，我們居無定所，四處漂泊，生活如無根的浮萍，天天生活在變化中，甚至工作有沒有著落也不清楚，還需要做職業生涯規劃嗎？實際上這樣的看法并不在少數，正是由于存在這樣的觀點，很多農民工朋友的城市生活才沒有更多的長進。離開家鄉進城工作，可不能像當年游擊隊一樣，打一槍換一個地方，如果沒有合理的、長遠的、多方面的規劃，就無法進一步實現個人的職業理想和生活理想。那么怎樣看待農民工做職業生涯規劃這個問題呢？
1.從社會的角度看。每年一度的春節，大量的農民工返鄉，春節過后又有大批農民工進城，在上億的勞動力大軍流動過程中，許多人完成了一年的職業勞作，來年又重歸游離的狀態，不能也無法重新回歸從前的單位，也不能從事原先的職業。于是乎，大量的人力資源耗費在等待、煎熬、徘徊和痛苦之中。這中間有很多原因是由于農民工朋友在自己進入城市之后，沒有對自己能做什么，個人想要什么，有什么基礎，個人發展的方向是什么等問題，做深入、系統的分析和探討而造成的。農民工朋友做好自己的職業生涯規劃，有利于建立科學的擇業觀，提高就業的成功率，還可以減少失業、被辭職的情況，從社會角度來看對降低就業壓力是有較大幫助的。因此，農民工朋友做職業生涯規劃是社會現實的需要。
2.從企業發展的角度看。長期以來，由于中國擁有巨大的勞動力資源優勢，整個勞動力市場呈嚴重的供過于求的狀態。大量進城務工人員一方面為企業提供了大量的廉價勞動力，另一方面上到國家、下到企業都逐漸產生了員工流動和使用的依賴，中外企業招聘員工一般不用發愁。但是，目前大多數企業對待農民工勞動力，都是重在使用而輕視培養，重視招聘新員工而輕視已有勞動力的再提高，更不用說對員工進行職業發展規劃和技能提升。實際上，企業員工缺乏職業安全感和職業發展需求的滿足感，員工的安心工作就會出現波動，企業發展就會有隱患。如果農民工勞動力資源沒能及時有效地得到規劃、開發與儲蓄，大部分農民工很可能將永久性地退出勞動力市場。為了農民工的“再出發”與產業的“再發展”，就必須做好勞動力供給的“蓄水池”，進行科學的職業發展規劃與開發。
3.從個人發展的角度看。從個人的角度來講，農民工朋友絕大多數原來是在土地上從業的農民，由于尋求個人的發展等動力促進，離開了自己熟悉的家鄉，來到全新的城市環境里，謀求有所發展，但是如果個人在進入城市職場之前，對自己的未來發展沒有規劃和目標，那么會對個人的發展造成障礙的。特別對剛剛成長起來的步入城市的年輕打工者（新生代農民工），該用怎樣的眼光來看待自己未來的發展道路，將對其一生的成就產生重大影響。農民工做好個人的職業生涯規劃，對個人發展的意義主要體現為以下幾個方面：（1）做好職業生涯規劃，可以分析自我，個人可以準確評價自身的職業能力、性格特點、價值追求、優勢與劣勢等，在職業競爭中發揮個人優勢。以既有的成就為基礎，確立人生的方向，提供奮斗的策略。（2）通過職業生涯規劃，可以重新安排自己的職業生涯，突破原有生活的局限，塑造全新、充實的自我。即使自己已經進城打工多年，還可以評估個人目標和現狀的差距，提供前進的動力。（3）通過職業生涯規劃重新認識自身的價值并使其增值。通過自我評估，知道自己的優缺點，然后通過反思和學習，不斷完善自己，使個人價值增值。還有助于全面了解自己，增強職業競爭力，發現新的職業機遇。（4）職業生涯規劃通常建立在個體的人生規劃上，因此，做好職業生涯規劃將個人生活、事業與家庭聯系起來，讓生活充實而有條理。
三、農民工做好職業生涯規劃的路徑
根據職業生涯規劃理論，農民工朋友規劃自己的職業生涯可以從以下幾個方面入手。
1.評價自我。即審視自己、認識自己、了解自己，做自我評估。自我評估就是對自己做全面分析，通過自我評估才能對自己的職業作出正確的選擇，才能選定適合自己發展的生涯路線，才能對自己的生涯目標作出最佳抉擇。因此，自我評估是職業規劃的重要步驟之一。自我評估包括自己的興趣、特長、性格、學識、技能、智商、情商、思維方式、思維方法、道德水準以及社會中的自我等內容。也許農民工朋友會說，我沒有什么特長，其實不是這樣的，每個人都有自己的特長，只是平時沒有去挖掘發現而己，仔細分析自己，就會發現原來我還有這樣或那樣的特長。
2.評估職業機會。主要分析內外因素對自己職業選擇的影響，每一個人都處在一定的環境之中，離開了這個環境，便無法生存與成長。所以，在制定個人的職業規劃時，要分析環境條件的特點，環境的發展變化情況，自己與環境的關系，自己在這個環境中的地位，環境對自己提出的要求，以及環境對自己的有利條件與不利條件等等。只有對這些環境因素充分了解，才能做到在復雜的環境中避害趨利，使職業規劃具有實際意義。農民工要把自己作為一個職業人來了解周圍的環境、你所在的地區、你將要就業的行業等，只有清晰掌握周圍的環境，才能權衡利弊。
3.選擇職業。通過自我評估、生涯機會的評估，認識自己、分析環境，在此基礎上對自己的職業作出選擇。也就是在職業選擇時，要充分考慮到自身的特點，即自己的能力、性格和興趣，特別是個人的工作能力，工作能力往往是限制一個人在勞動力市場選擇合適崗位的因素。分析自我、了解自己、分析環境、了解職業世界，使自己的性格、興趣、特長與職業相吻合。通過對自己以往的經歷及經驗的分析，找出自己的特長與興趣點。選擇職業重要的是能正確地分析自己，找到自己最適合做的專業，然后努力成為本行業的佼佼者。職業的選擇決定以后的成長道路，所以每一位農民工朋友千萬不要簡單的認為找一份工份就是自己以后的職業，隨意從這個工作跳到那個工作，這里不行就到那里。對待自己的工作選擇要慎重。
4.制訂職業計劃。在做個人職業發展計劃的時候，要考慮你所選擇的工作，能否幫助你實現人生的最終目標？你是否有辦法可以讓你現有的職業與你的人生基本目標一致起來？簡單的說，就是你希望在多少年之內達到什么目標，根據這個目標我又該怎么做？通常在制訂職業計劃時，先制定一個長期目標，然后把長期目標分解成一個個短期和中期目標，這樣對于每一個短期目標就會變得貼近生活、容易達到。
5.實施行動。開始行動，這是所有生涯設計中最艱難的一個步驟，因為行動就意味著你要停止夢想而切實地開始行動。如果想法不轉換成行動，就是一紙空文，目標也只能停留在夢想階段。如果你想成為一個電工或家政人員，當你制定職業規劃后就立即行動起來，你可以參加政府提供的免費技能培訓，針對大量需要培訓的農民工，政府每年都會提供大量的資源為農民工進行多種形式的免費培訓的，那農民兄弟們可以充分利用這些機會，提升自己的能力。立即行動，無論你是處于剛剛踏上職業路途的年輕人，還是40歲左右并且正陷在一份你不喜歡的工作之中的中年人，現在都是你進行職業規劃的好時機。只要你還沒有到安享晚年的地步，任何時候開始你的職業規劃都不為晚。
參考文獻：
[1]鄒樹新.中國城市農民工問題[M].北京：群言出版社，2007.
[2]陸漢洲.聚焦中國民工[M].北京：中國經濟出版社，2005.
[3]沈立人.中國農民工[M].北京：民主與建設出版社，2005.
關鍵詞：水利；發展；經濟
一、水利經濟發展概述
水利經濟是指水資源、水環境、水利工程為要素所從事的生產經營活動的統稱，水利行業的一個重要組成部分就是水利經濟的發展。我國建國以后在水利建設方面取得了很大的成就，水利經濟也伴隨著國家經濟的發展而不斷的發展。水利行業逐漸的形成了以水利建設的勘測、施工、運行管理為主的產業結構，我國水利企業無論在人員、規模及技術方面都在朝好的方向發展，企業的未來也充滿了希望，但如何使水利經濟的發展能夠更迅速，水利企業能夠真正實現可持續發展，依然是我們要研究的課題。
二、水利經濟發展的客觀必然性
1.水利經濟存在與發展的客觀必然性
水是一種自然資源，以一種生態要素的形式出現，發揮著不可替代的生態效益與環境效益。但當水以一種經濟資源存在時，其在經營活動中就是一種生產要素，能夠增值且有經濟效益。以水為原料的生產包括：水產養殖、水路運輸、水能資源開發、水利工程對水資源的優化配置等。我們長期以來一直強調水的自然屬性和公益性作用，而忽視了水的經濟屬性，這使得水利經濟的發展失去了很多機會，影響了行業的現代化建設進程。可以說水利經濟發展是社會經濟發展的客觀需要。
2.水利經濟與實行水務管理體制的客觀必然性
水資源是人類社會極為重要的基礎性資源，我們既要保持水資源的可持續利用，又要充分發揮其經濟功能效益，這就要求我們必須對水資源科學管理、統一規劃。只有協調好水資源保護與水資源開發利用之間的關系，使二者可以有機的結合起來，才能真正意義上的實現對水資源的統一管理，對水資源進行保護及科學利用。
3.水利經濟與水利現代化建設的客觀必然性
與交通、通訊、電力等行業相比，水利同樣作為社會經濟發展中的基礎性行業，而在發展中卻明顯落后。在我國經濟飛速發展的今天，水利經濟發展要與社會經濟發展同步，甚至要超越社會經濟發展的速度，水利行業要根據水資源的雙重屬性創新水利的投入機制，充分利用市場機制和政府財政的力量，加大水利投入的規模，加強安全水利、環境水利、民生水利的建設，為我國社會經濟發展提供牢固的基礎支撐及保障。
三、關于發展水利經濟的主要措施
1.多渠道籌集水利建設資金
對于水利建設資金的湊集要采取多渠道、多方式的辦法，要挖掘民間資本，推薦民營水利建設。對投資大、收入高的項目可成立股份公司，在行業內部或是面向社會湊集資金，水利企業的內部員工可以參與投資入股，共同開發水利市場。值得注意的是，水利建設是關系到民生的大事，設計到人民群眾的生命安全，所以水利建設部門必須對相關審批嚴格控制，對水利公共事業的安全性負責。
積極開展招商引資活動來滿足城市水務建設的需要，將有實力的大企業集團引入來做大做好水利項目。目前我國很多的公司已經和水利部門合作參與到水利市場中來，共同來發展水利經濟，并在水務市場中占據了一定的位置。這樣水利部門達成了預定的目標，參與企業也實現了經濟效益，達到一種雙贏的結果。
2.法制經濟、依法收費
水利建設必須形成一種法制經濟，目前中央及地方也出臺了很多保障水利經濟發展的政策，但水利建設實現法制經濟還是存在著法規不完善、法規政策落實不到位等問題。水利行業要堅持實行依法收費，將政府制定的法律法規真正的落實到實際工作中去，同時要杜絕企業內部資源浪費的現象，做好水土資源保持工作。
3.實行體制改革
我國現行的區域分割治理方式容易造成地區利益爭奪，也不利于水資源的合理分配及發揮其最大的經濟效力，會出現一個地方水資源充沛浪費嚴重，而另一個地方水資源又極度緊張的情況。所以要注意城市供水由水利管理部門統一分配、農村用水要由水利行政部門管理、發動地方群眾參與當地的水利建設興休等問題。
4.重視人才
一個行業的發展離不開人才，人才是技術及經驗的載體，是企業發展的寶貴財富。我國水利行業的發展中培養了很多懂水利建設的人員，但精通管理、善于經營的人才卻較少。所以水利行業在尋求發展的同時也要關注對人才的培養、培育，企業內部要重視人才，建立起人才培育的體系。另外，企業也要敢于在市場中引入高端人才，使企業可以更好的發展。
5.提高科技含量
相對于歐美等一些西方發達國家，我國水利科技的發展程度、水利科技的含量都較低，水利行業內部員工的素質、科學文化水平也都不高，這些因素的存在阻礙了我國水利經濟向世界一流水平前進。我國水利行業應該改變原來那種僅僅依靠經驗來進行生產經營活動的思維方式，變成依靠高科技、勞動技術、經驗等相結合的方式來實現水利建設科技化發展。加快水利企業技術改造，鼓勵水利企業技術創新，努力形成低投入、高產出的企業經營狀態。
參考文獻：
關鍵詞：移動機器人；路徑規劃；A*算法；柵格法
中圖分類號：TP391.4 文獻標志碼：A
Mobile Robot Path Planning Based on an Improved A* Algorithm SUN Wei1， LV Yunfeng1， TANG Hongwei1，2， XUE Min1
（1. College of Electrical and Information Engineering， Hunan University， Changsha 410082， China；
2. Department of Electrical Engineering， Shaoyang University， Shaoyang 422000， China）
Abstract：An improved A* algorithm was presented for global path planning of mobile robot. Firstly， the environment model was described using the grid method， and the preliminary path was obtained by traditional A* algorithm. Secondly， the path planned by A* method was flaw with much redundant points， large path length， and turning angle. The original path was partitioned by tiny step to obtain a series of path point. The finish point from the start point was connected by using straight line in sequence. To decrease the path length and turning angle， the path node can be removed if there are no obstacles on the line. The analysis and comparison between the proposed algorithm， traditional A* algorithm and another improved A* method were then given in the simulation experiment and physical experiments. Additionally， the merits of the proposed algorithm and other algorithms were compared when the obstacle rate， amount of task point， and step length were different. The experiment results show that the proposed algorithm effectively reduces the path length and turning angle.
Key words：mobile robot； path planning； A* algorithm； grid method
路徑規劃問題一直是智能機器人領域的一個研究岬.移動機器人路徑規劃是指機器人基于機載傳感器獲得的環境信息規劃出一條從起點到終點的無碰、安全的可行路徑，并在此基礎上盡可能地優化路徑[1].移動機器人路徑規劃主要解決以下三個問題：第一是規劃出的路徑能使機器人從起點運動到終點；第二是采用相應的算法使得機器人能夠避開環境中的障礙物；第三是在滿足前面兩點要求的基礎上，盡可能地優化機器人的運動軌跡，通常是以規劃出的路徑最短作為優化目標[2].根據機器人對環境信息的感知程度，路徑規劃問題分為全局路徑規劃和局部路徑規劃.前者是指機器人在擁有全部環境信息的基礎上進行的路徑規劃，又稱為離線路徑規劃；后者是指機器人在只有部分環境信息的基礎上進行的路徑規劃，又稱為在線路徑規劃[3].本文主要討論全局路徑規劃.
移動機器人路徑規劃的研究起始于20世紀70年代，到目前為止，已有大量的研究成果.針對全局路徑規劃，主要方法有可視圖法、拓撲學法、人工智能算法和柵格法[4].文獻[5]針對自由空間法當環境發生變化時，需要重新建立網絡連接模型，因而導致路徑規劃算法的環境適應性差和實時性不高的缺陷，提出了一種基于可視圖的全局路徑規劃算法，該方法是直接在環境地圖上進行路徑規劃，從而提高了算法的環境適應能力和實時性.神經網絡作為人工智能中一種重要的算法也被應用到了移動機器人路徑規劃領域，如文獻[6]，首先建立了一個障礙物罰函數的神經網絡模型，并得到了整條路徑的能量函數；然后求得該函數的極小值點，且應用了模擬退火算法避免陷入局部最優；最終對得到的路徑進行了優化，使得路徑更加平滑和安全.除此之外，學者們還采用其它的智能算法來解決移動機器人路徑規劃問題，如模糊邏輯[7-9]，蟻群算法[10]，粒子群優化[11]，遺傳算法[12-13]等.
柵格法是將機器人運動環境建立成一系列具有二值信息的網格模型，再用搜索算法獲取最優路徑.文獻[14]提出了一種改進的A*算法，解決了傳統A*算法得到的路徑包含過多冗余點問題，并得到機器人在拐點處的最小轉折角度.但該算法并沒有減小機器人的路徑長度和轉折角度.文獻[15]針對傳統A*算法得到的路徑折線多、累計轉折角度大的問題，提出了一種平滑A*算法，減少了不必要的路徑點并減小了路徑長度和轉折角度.但只是在原有的路徑點上進行處理，路徑長度和轉折角度的減少量有限.本文提出了另一種改進的A*算法，將進一步地減少移動機器人的總路徑長度和總轉折角度.
1 環境模型描述
眾所周知，移動機器人工作環境地圖建立是路徑規劃中十分重要的一步.地圖建立是指將各種傳感器獲得的環境信息進行融合并抽象成地圖模型[16].采用柵格單位描述二維環境信息非常簡單有效，應用廣泛.所以，本文也使用柵格法來建立移動機器人工作環境模型.如圖1所示，柵格法將機器人工作環境分割成一系列具有相同尺寸的柵格，并將這些柵格分成兩類：可通過柵格和不可通過柵格.圖1中，空白柵格表示可通過柵格，即移動機器人能自由通過的地方，黑色柵格表示不可通過柵格，即該柵格有靜態的障礙物.
為了方便研究又不失一般性，本出以下3點合理的假設：1）障礙物邊界是在實際邊界的基礎上加一個移動機器人安全距離得到的，這樣就可以將移動機器人看作是環境中的一個質點；2）在這有限的二維空間中，機器人的移動方向可以是任意的，并且不考慮高度的影響；3）在整個路徑規劃過程中，環境信息是不變的.圖1是一個10*10的移動機器人工作環境，S是機器人起點，D是終點.本文的工作就是找到一條從起點到終點的無碰的最優路徑.
2 A*全局路徑規劃算法
A*算法是一種典型的啟發式搜索方法.通過估價函數來引導和決定它的搜索方向.從起點開始搜索周圍的節點，由估價函數得到每個節點的價值，選擇價值最低的作為下一個擴展節點，循環重復這一過程直到搜索到終點，則停止搜索，獲得最終路徑.由于每一次都是以估價值最低的節點作為擴展節點，所以最終的路徑代價是最低的.估價函數由式（1）給出：
式中：g（n）是狀態空間中從起始節點到節點n的實際代價，h（n）是從節點n到終點的啟發式估計代價函數，本文采用曼哈頓距離作為啟發式函數[14].
xd是目標點的橫坐標，yd是目標點的縱坐標，xn是節點n的橫坐標，yn是節點n的縱坐標.
在A*算法搜索路徑的過程中，需要不斷地更新兩個列表，一個是開啟列表，另一個是關閉列表.開啟列表存儲的是所有的周圍節點.A*算法從開啟列表中選擇具有最小估價值的節點作為下一個擴展節點.關閉列表存儲的是所有經過的節點和環境中的障礙節點.應用A*算法進行路徑搜索的具體流程如下所述：
Step1 把起始節點放入開啟列表.
Step2 檢查開啟列表是否為空，如果為空，則表示搜索失敗；不為空，則執行Step3.
Step3 選取開啟列表中具有最低f（?）的節點作為當前擴展節點，對擴展節點的每個周圍節點作如下處理：①當該節點的周圍節點是障礙點或者是關閉列表中的節點，則沒有任何動作；②當該節點的周圍點不在開啟列表中，則把該節點的周圍節點添加進開啟列表中，并將當前擴展節點作為該節點的周圍節點的父節點，計算該節點的周圍節點的f（?）和g（?）；③當該節點的周圍節點在開啟列表中，如果以當前擴展節點作為父節點，該節點的周圍節點的g（?）比原來更低，則把當前擴展節點作為父節點，并重新計算該節點的周圍節點的f（?）和g（?）.否則，不作任何改變.
Step4 將當前擴展節點放入關閉列表中，并檢查終點是否在開啟列表中.如果不在開啟列表中，則跳回Step2繼續搜索；否則，最優路徑已經找到，結束搜索.
Step5 從終點開始，沿著每一個父節點移動，回到起始點，這就是最終的路徑.
3 改進的A*算法
采用A*算法進行移動機器人路徑規劃雖然能獲得一條安全無碰的路徑，但路徑點較多，折線多，導致路徑的總長度和總轉折角度較大.這在移動機器人實際應用中將消耗更多的能量和花費更多的r間.本文提出了一種改進的A*算法，能有效地減少路徑長度和轉折角度.
圖2的實線是在一個任意環境中A*算法規劃出的路徑，本文方法是在原路徑的基礎上，從起點開始以較小的步長分割原路徑，得到更多路徑點，如圖2的路徑點a1到a20.按照一定的規則剔除冗余路徑點，將剩余的路徑點按順序連接，最終獲得更加優化的路徑.
圖3是本文算法的流程圖，圖中符號的定義如下：
k為分割路徑的步長；c，m，i分別是當前路徑點下標、待連接路徑點下標和新路徑點下標；A為以步長k分割原始路徑得到的路徑點集合A={a1，a2，…，aN}，其中a1是起始點，aN是終點；ac為當前路徑點；am為當前待連接點；
lcm為連接ac與am的直線；lc，c+1為連接ac與ac+1的直線；B為新的路徑點集合，B={b1，b2，…，bs }.
注意，以步長k分割路徑是在原路徑的直線段進行的.例如，對圖4中A*算法得到的路徑進行分割，先進行直線段L1的分割，從起點開始依次得到路徑點a1，a2，…，a7，此時a8與原路徑點的距離小于步長k，則將原路徑點作為a8，并從路徑點a8開始重復上述過程，分割直線段L2和L3直到將終點作為路徑點a20時，分割過程結束.
圖4中的實線是在任意環境中A*算法規劃出的路徑1，由直線段L1 ，L2 和L3組成，本文方
法規劃出的路徑3由直線段La1a6，La6a9，La9a10和La10a20組成，其中Laiaj是指起點為ai，終點為aj的直線段.由圖4可以直觀地看出：路徑1的路徑長度明顯大于路徑3的路徑長度.另外，路徑1的總轉折角度：
路徑3的總轉折角度：
其中α2=∠ba6a9 ， β2=∠da9a10，γ1=∠ca10a20.而α1=α2+β2，β1=γ1+γ2，γ2=∠a15a20a10，則θ1=α1+β1=α2+β2+γ1+γ2=θ3+γ2.所以，θ1>θ3.相對于A*算法，本文方法縮短了總路徑長度，減小了總轉折角度.
文獻[15]提出的平滑A*算法直接地剔除A*算法規劃出的路徑點，使得路徑更加平滑.而本文方法是先進行分割，再剔除冗余的路徑點.圖4中直線段La1a8，La8a11和La11a20是文獻[15]中平滑A*算法得到的路徑2.顯然，路徑2的長度大于路徑3的長度.另外，路徑2的轉折角度：
其中α1=∠ba8a9，β3=∠a15a20a10，而α1=α2+β2，β3=γ1+γ3，γ3=∠a11a20a10，則θ2=α1+β3=α2+β2+γ1+γ3=θ3+γ3，所以θ2>θ3.相對于文獻[15]提出的平滑A*算法，本文方法得到的路徑也更加優化.
4 實 驗
為了驗證本文算法的可行性和有效性，進行了計算機仿真實驗和實物實驗.考察了不同情形下算法的性能，以下將從4個方面進行仿真實驗： 1）探究同樣的條件下本文算法與A*算法以及文獻[15]的平滑A*算法的性能；2）環境障礙率p對各算法的影響；3）不同目標點數n下算法的優劣；4）本文算法在不同的分割步長k下的效果.以下的4種情形都是在邊長為200個單位的正方形環境下進行實驗，將實驗環境分割成20*20個柵格元素，每個元素是邊長為10個單位的正方形柵格.將實驗環境分割成20*20個柵格元素，每個元素是邊長為10個單位的正方形柵格.
情形1 環境障礙率（障礙柵格數量占總柵格數量的比例）p=30%，取本文算法的分割步長k=0.1，目標數n=1即只有一個終點，起點是（4，4），終點是（198，198），機器人在起點的角度為90°.進行了50次實驗，圖5和圖6是不同算法規劃出的路徑長度和轉折角度，表1是3種算法50次實驗的各項平均值比較.從實驗結果中可以看出，本文提出的改進A*算法相對于A* 算法和文獻[15]的平滑A* 算法，有效地減少了路徑長度和轉折角度.注意，雖然環境障礙率都是30%，但障礙柵格是隨機分布的，這就導致了不同的環境復雜度，所以同樣的算法和實驗條件在不同的實驗次數下卻有不同的實驗結果.
情形2 考察在不同的環境障礙率下，各個算法的性能.令分割步長k=0.1，目標數n為1，起點（4，4）、終點（198，198），機器人在起點的角度為90°.分別在環境障礙率為10%，20%，30%，40%，50%時，進行了50次實驗，并求得不同障礙率下路徑長度的均值和轉折角度的均值，實驗結果如圖7、圖8所示.可以看出，一方面當環境障礙率增大時，各個算法得到的路徑長度和轉折角度也在不斷增大.這是因為環境障礙率一定程度上代表了環境的復雜度，當環境越復雜時，那么規劃的路徑長度和轉折角度也就越大；另一方面，在圖7和圖8中，方框內的數據是本文算法相對于A*算法路徑長度和轉折角度的減少量.當環境障礙率越大時，路徑長度和轉折角度的減少量也不斷增大，這說明相對于A*算法，本文方法更加適合在障礙物較多的環境中使用.
情形3 在移動機器人的工作空間中可能存在多個任務點，這就意味著環境中會有多個不同的終點.這里將研究當機器人有多個任務點時，各個路徑規劃算法的優劣性.這里做以下兩點規定：1）對環境中的任務點進行了編號，任務點1，（198，198）；任務點2，（4，198）；任務點3，（95，95）；任務點4，（198，4）.2）當機器人有n個任務需要執行時，它的執行順序是由任務點1遞增至任務點n.取障礙率p=30%，分割步長k=0.1，分別在n等于1，2，3，4時，進行了50次實驗，并求得路徑長度和轉折角度的均值，實驗結果如圖9和圖10所示，圖中方框內的數據是本文算法相對于A*算法路徑長度和轉折角度的減少量.顯而易見，當機器人的任務點越多，本文算法相對于A*算法規劃的路徑長度和轉折角度的減少量越大.
情形4 本文算法中存在一個分割步長k，這里將考察參數k對算法效果的影響.令環境障礙率p=30%，僅有一個任務點（198，198），起點是（4，4），機器人在起點的角度為90°.在不同的分割步長下進行了50實驗，并求出相應的均值，驗結果如圖11和圖12所示.可以得出這樣的結論：當分割步長越小時，本文算法得到的路徑長度和轉折角度也越小.顯然，這是因為分割步長越小，路徑分割得越精細，路徑長度和轉折角度也就相應減小.
在實物實驗中，本文采用的移動機器人是Turtlebot2，移動底座的最大移動速度：0.7 m/s，最大角速度：180°/s.采用ThinkPad E450C筆記本電腦作為移動機器人的控制器.移動機器人的實際運動空間如圖13所示，是3.6 m×6.6 m的矩形環境.起點（0.9 m，0.9 m），終點（2.7 m，6.3 m），機器人在起點的角度為90°.為了使用本文改進的A*算法進行路徑規劃，需要先建立環境的柵格模型，設置柵格元素為0.6 m×0.6 m的正方形，對實際障礙物進行膨化處理，映射成圖14的黑色柵格.分別采用A*算法、文獻[15]的平滑A*算法和本文算法進行移動機器人的路徑規劃.圖14的直線段La1a5，La5a11，La11a21，La21a27，La27a32，La32a44 和
La44a53是A*算法規劃出的路徑；文獻[15]中平滑A*算法得到的路徑是直線段La1a5，La5a11，La11a21，La21a27，La27a32和La32a53；直線段La1a8，La8a24，La24a25，La25a35和La35a53是本文算法得到的結果.由于移動機器人的運動總是存在外界干擾和運動精度等因素，其運動的實際路徑長度與轉折角度總是比規劃的路徑長度和轉折角度要稍稍大一些，如表2所示.但無論是規劃的路徑長度和轉折角度，還是移動機器人實際運動的路徑長度和轉折角度，本文算法得到的實驗結果都比A*算法和文獻[15]平滑A*算法更加優化.
5 結 論
采用A*算法進行移動機器人路徑規劃，可以得到一條從起點連接終點的無碰安全路徑，但路徑的冗余點較多，路徑長度和轉折角度較大.針對這些問題，本文提出了一種改進A*算法，能有效地減少路徑冗余點和減小路徑長度及轉折角度.并且，分析比較了不同的環境障礙率、任務點數量、分割步長對算法性能的影響.一方面，相對于A*算法，本文方法更加適合多任務點，高障礙率環境下的移踴器人路徑規劃；另一方面，采用較小的分割步長可使得規劃出的路徑更加優化.
參考文獻
[1] 席裕庚，張純剛.一類動態不確定環境下機器人的滾動路徑規劃[J].自動化學報，2002，28（2）： 161-175.
XI Yugeng， ZHANG Chungang.Rolling path planning of mobile robot in a kind of dynamic uncertain environment[J]. Acta Automatica Sinica， 2002，28（2）：161-175.（In Chinese）
[2] 張捍東，鄭睿，岑豫皖.移動機器人路徑規劃技術的現狀與展望[J].系統仿真學報，2005， 17（2）： 439-443.
ZHANG Handong， ZHENG Rui， CEN Yuwan. Present situation and future development of mobile robot path planning technology[J]. Journal of System Simulation， 2005，17（2）：439-443.（In Chinese）
[3] 朱大奇，顏明重.移動機器人路徑規劃技術綜述[J].控制與決策，2010， 25（7）： 961-967.
ZHU Daqi， YAN Mingzhong. Survey on technology of mobile robot path planning[J]. Control and Decision， 2010，25（7）：961-967.（In Chinese）
[4] 吳乙萬，黃智.基于動態虛擬障礙物的智能車輛局部路徑規劃方法[J].湖南大學學報：自然科學版，2013，40（1）： 33-37.
WU Yiwan， HUANG Zhi. Dynamic virtual obstacle based local path planning for intelligent vehicle[J]. Journal of Hunan University：Natural Sciences， 2013，40（1）：33-37.（In Chinese）
[5] 楊淮清，肖興貴，姚棟.一種基于可視圖法的機器人全局路徑規劃算法[J].沈陽工業大學學報，2009，31（2）： 225-229.
YANG Huaiqing， XIAO Xinggui， YAO Dong. A V-graph based global path planning algorithm for mobile robot[J]. Journal of Shenyang University of Technology， 2009，31（2）：225-229.（In Chinese）
[6] 梁瑾，宋科璞.神經網絡在移動機器人路徑規劃中的應用[J].系統仿真學報，2010，22（增刊1）： 269-272.
LIANG Jin， SONG Kepu. The application of neural network in mobile robot path planning[J]. Journal of System Simulation， 2010，22（s1）：269-272.（In Chinese）
[7] 郝冬，劉斌.基于模糊邏輯行為融合路徑規劃方法[J].計算機工程與設計，2009，30（3）： 660-663.
HAO Dong， LIU Bin. Behavior fusion path planning method for mobile robot based on fuzzy logic[J]. Computer Engineering and Design， 2010，30（3）：660-663.（In Chinese）
[8] ARPINO C P， MELENDEZ W M， GUZMAN J， et al. Fuzzylogic based speed planning for autonomous navigationunder velocity field control[C]//2009 IEEE Int Conf on Mechatronics. Malaga， 2009： 201-212.
[9] ZOUMPONOS G T， ASPRAGATHOS N A. Fuzzy logic pathplanning for the robotic placement of fabrics on a worktable[J]. Robotics and Computer Integrated Manufacturing， 2008， 24 （2）： 174-186.
[10]鄧高峰，張雪萍，劉彥萍.一種障礙環境下機器人路徑規劃的蟻群粒子群算法[J].控制理論與應用，2009，26（8）： 879-883.
DENG Gaofeng， ZHANG Xueping， LIU Yanping. Ant colony optimization and particle swarm optimization for robot-path planning in obstacle environment[J]. Control Theory & Applications， 2009，26（8）：879-883.（In Chinese）
[11]吳憲祥，郭寶龍，王娟.基于粒子群三次樣條優化的移動機器人路徑規劃算法[J].機器人，2009，31（6）： 556-560.
WU Xianxiang， GUO Baolong， WANG Juan. Mobile robot path planning algorithm based on particle swarm optimization of cubic splines[J]. ROBOT， 2009，31（6）：556-560.（In Chinese）
[12]王雪松，高，程玉虎，等.知識引導遺傳算法實現機器人路徑規劃[J].控制與決策，2009，24（7）： 1043-1049.
WANG Xuesong， GAO Yang， CHENG Yuhu， et al. Knowledge-guided genetic algorithm for path planning of robot[J]. Control and Decision， 2009，24（7）：1043-1049.（In Chinese）
[13]THEODORE M， KAVEH A， ROGER L W. Genetic algorithms for autonomous robot navigation[J]. IEEE In Strumentation and Measurement Magazine， 2007，12（1）： 26-31.
[14]王殿君.基于改進A*算法的室內移動機器人路徑規劃[J].清華大學學報：自然科學版，2012， 52（8）： 1085-1089.
WANG Dianjun. Indoor mobile-robot path planning based on an improved A* algorithm[J]. Journal of Tsinghua University：Science and Technology，2012，52（8）：1085-1089.（In Chinese）
[15]王紅衛，馬勇，謝勇，等.基于平滑A*算法的移動機器人路徑規劃[J].同濟大學學報：自然科學版，2010，38（11）： 1647-1651.
WANG Hongwei， MA Yong， XIE Yong， et al. Mobile robot optimal path planning based on smoothing A* algorithm[J]. Journal of Tongji University：Natural Science， 2010，38（11）：1647-1651.（In Chinese）
