時間：2023-03-01 16:32:11
序論：速發表網結合其深厚的文秘經驗，特別為您篩選了11篇路徑規劃范文。如果您需要更多原創資料，歡迎隨時與我們的客服老師聯系，希望您能從中汲取靈感和知識！
一、哪些內容是課題研究過程設計時需要考慮的？
所謂課題研究過程，是指為完成課題研究工作而經歷的程序、階段。課題研究的過程設計，也就是指研究者根據一定的研究內容和研究目標，對課題研究活動作出安排的預設程序。它是課題研究方案的重要組成部分，既是對研究內容、研究階段、研究方法、研究成員等諸多要素進行分析與思考的結果，更是一個根據研究假設調動各類資源進行實踐的過程。
研究內容往往是課題研究過程設計的基本依據。不同的內容，其研究程序也是有所區別的。如課題“小學生家庭作業習慣調查及對策研究”，其研究程序一般先要有相應的現狀調查，然后根據調查了解到的問題設計針對性的策略，再通過實踐嘗試，檢驗預設的策略是否有效解決了相應的問題，最后分析提煉相應的對策。又如“小學語文‘特色作業’設計研究”這個課題，在過程設計時則首先要對“特色作業”作一定的思考，分析其具備的特征，然后再進行相關設計、應用實踐、分析提煉等。
研究階段則是課題研究過程設計的重要內容，它首先涉及一個課題通過幾個階段的研究完成研究任務的問題，其次則需要考慮對具體的研究工作有大致時間上的確定。如上面提到的“小學生家庭作業習慣調查及對策研究”這一課題，一般分為現狀調查、問題分析、對策思考、實踐嘗試、效果分析等階段，且每前一階段研究活動都是后一階段研究活動的基礎，后一階段研究活動則是前一階段研究活動的延續。
這里的研究方法不僅指嚴格意義上的研究方法，如調查法、觀察法等，還包括在研究活動中采用的一些具體的操作策略，如問題設計、教學實踐等。研究方法設計同樣是研究過程設計中的一個重要組成部分。
研究過程設計除了受到以上三個方面的基本要素影響之外，其實有時也會受制于某個課題研究成員的影響。如有的課題涉及的部門較多，牽涉的人員也就比較多，此時，在研究過程設計中，需要對相關成員的任務作出相應的分配，目的是保證在研究活動具體展開時能夠作出及時有效的協調。
二、怎樣的過程設計才能保證課題研究工作的順利進行？
從一個課題來看，其研究過程的設計一般可以從行動路徑和研究策略兩個方面來體現。其中行動路徑是大方向，是對課題研究工作的整體把握;研究策略則是具體研究活動中的操作方法的總和。
（一）規劃課題研究行動路徑，細化各項研究任務
課題研究的行動路徑是課題研究整體推進的重要基礎，它是一個課題順利開展研究工作的保障。行動路徑一般包括三方面的內容：研究階段及其說明、內容選擇及其說明以及環節設計及其說明?？捎脠D表的方式加以呈現，并配以一定的文字作解釋。如《區域實施“綠色評價”的實踐與研究》，將課題研究的行動路徑作了如下表述：
在以上圖例表述研究的行動路徑基礎上，又作了簡要的說明：“理論學習，內涵理解”階段，主要是通過學習國家、省、市的相關文件精神，切實把握中小學教育質量綜合評價改革的核心思想，深入理解評價理念及內容的變化，明確教育評價改革的方向，為本區實施“綠色評價”奠定基礎;“多部門聯動，整體推進”階段，結合各部門本身的職能，在基于綜合素養評價理念背景下，實踐教育質量綜合評價過程，推進課題研究的深入;“梳理成果，總結推廣”階段，主要在策略性成果和對象性成果方面作較為完善的分析與提煉。
在以上的“行動路徑”中，我們很明顯地看出本課題研究分為三個階段進行，且每個階段的研究主體與研究任務都比較明確。因為有了清晰明確的“行動路徑”設計，不但對整體課題的研究工作作出了整體規劃，同時還有相應研究內容的分工與階段性推進的計劃，顯然有利于課題研究人員在不同的研究階段，落實好研究工作，而且還能對研究工作作出即時的反思與調整。
（二）想明白各個環節的研究方式，具化研究活動中的操作策略
課題研究過程的設計中，還有一塊相當重要的內容，便是針對具體的研究內容與研究活動作出的策略設計、方法選擇以及環節預設。這是課題研究過程中最為具體的工作，一般需要基于相應的研究內容進行思考與設計。
如我區有一位教師在研究“運用幾何直觀培養小學生解決問題能力的實踐研究”這一課題時，針對“培養小學生運用幾何直觀解決問題能力”這樣一個研究內容，提出了“數形結合，以數化形”“強調直觀，以形析文”和“重視圖例，突出關系” 這三種策略。并在每一種策略的具體闡述中，又通過一張流程圖來表達策略的操作過程。
第一步是化境為數，經歷從實際情境中抽象出數的過程，體驗抽象。第二步是以數化形，經歷將數轉化成多種形的過程，體驗演繹。第三步將形歸數，經歷多形中發現共同點的過程，體驗歸納。三步流程使學生經歷數（式）與形轉化的過程，積累數形結合的基本活動經驗，奠定運用幾何直觀解決問題的能力基礎。以上研究策略設計，內容明確，路徑清晰，有很強的可操作性，顯然為后續研究活動的順利開展奠定了扎實的基礎。
又如一位幼兒教師在研究課題“幼兒園‘五樂游戲’活動的設計研究”時，提出了“樂運動、樂表達、樂交往、樂探究、樂表現”等五樂游戲后，于每一種游戲活動的研究中，設計了相當具體的操作策略――支架。如在“講述類”游戲研究時，設計了如下的一個支架：
有了相應的支架，研究者也就有了具體的實踐操作依據，后續研究實踐活動也就有了“落地”的保證。
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完全問題,解法很多,有精確算法,也有啟發式算法,目前許多智能算法就屬于啟發式算法,可以解決較復雜的線路優化問題,對于一般線路優化也能做得更準確,這里介紹蟻群算法解決實際問題。原因是蟻群算法與其他啟發式算法相比,在求解性能上,具有較強的魯棒性和搜索較好解的能力,是一種分布式的并行算法,一種正反饋算法,易于與其它方法結合?？朔舅惴ㄈ秉c,改善算法性能。
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 蟻群算法如結合其他啟發式算法,建立混合算法,能夠解決許多現實問題,達到較好運算效果,結合具體問題,可以深入研究。
所謂電子地圖是一項結合計算機制圖以及數據庫處理和信息系統等學科為一體的圖形表現形式。在現代社會中，電子地圖在各個行業中應用廣泛如在車載導航系統中，它已成為路徑規劃中一項較為重要的技術。但有關電子地圖的詳細應用主要在快速生成衛星影像和航空相片以及行數據的記錄和新數據的派生方面。存在的問題是其技術的應用還不夠廣泛和深入。所以，本文結合實例對電子地圖中的數據特點以及路徑算法和算法的改進進行分析，同時對路徑規劃中電子地圖的應用進行探討。
1.實例應用
在計算機的相關軟件的運行環境下，用VisualC++開發某市實驗用地圖上提取的300個道路所用點，同時添加附加信息，實施路徑規劃。在地圖上制定路徑的起始點和終止點之后，電子地圖可在很短的時間內確定最優化的路徑，同時該路徑的各種輔助設備能夠滿足實際車載和各種應急需求。
2.電子地圖的數據特征與路徑算法
2.1數據特征
電子地圖的數據特征是按照一定圖層進行疊加的，在電子地圖中的各種點、線、面等的集合就是圖層。在電子地圖中的數據分為兩種：（1）空間數據。它主要是對空間對象的幾何特征、位置關系以及拓撲關系進行存放。（2）屬性數據。主要是對空間對象的類別、名稱以及特征等進行確定。在本文所引用的Shape File中，屬性數據主要以dbf的形式儲存于數據庫中，相對的空間數據則主要以Shape File所固有的格式進行數據的儲存。這兩種數據通過一定的形式聯系在一起。電子地圖中，將城市的道路網建設成一個圖層，將其命名為道路網，同時在地圖上實施路徑規劃，要對道路進行操作，那么就不涉及其它圖層。
2.2電子地圖的路徑算法
在電子地圖的路徑規劃中，路徑算法是重要的工作過程之一?，F在電子地圖中最長用的算法是啟發式搜索算法，其主要的模型為f（x） =g（x）+h（x）.（1）式中：g（x）表示從起點到搜索點的實際花費；h（x）表示從起點到終點的預估花費，稱為啟發函數；f（x）表是總花費。在采用啟發模型之后，可以對驅動模型進行改進：（1）在每次新生成的節點展開之前，要對顯示的同一位置兩個節點的花費進行比較，在新生成節點大于已生成節點的前提下，可放棄已生成節點，反之用原節點。（2）將最小距離作為搜索信息，其花費的現實隨節點的開展而增加。（3）在節點的數量增加后，綜合代價增加，在每次新生成的節點的花費大于原來節點的情形下，可將新生成的節點淘汰用原來的路徑。
3.路徑規劃中電子地圖的應用
在路徑規劃過程中，電子地圖重新定義了地圖在人們心中的形象。在電子地圖的幫助下，可以將現成的路徑規劃中出現的各種要素進行不同形式的組合最后連接成新的地圖；同時交通部門可以根據電子地圖在路徑規劃中的應用，對各種交通情況諸如交通事故、天氣變化、不同路段的情況進行不同程度的監管；此外，路徑規劃中電子地圖的使用為各種市民和公民進出入不同的城市提供便捷的服務，可以在現有的地址、地址范圍和地理位置以及道路的交叉口等進行準確的定位，幫助人們在不熟悉路徑以及路況的情況下正確的選擇道路。
3.1起終點問題
在實際的生活過程中，電子地圖上的起終點并不能代表實際路線中的出發點和結束點。在我們的日常生活中較為常見的是起點和終點都位于某一個路段的中間部分，在此時，必須將路段的出發點作為起點，目的地作為終點，在電子地圖中輸入該城市的行政規劃圖，通過電子地圖對該路徑數據的處理和分析，得出最佳路徑區劃圖。
3.2最優路徑模型的確立
電子地圖在路徑規劃中的應用中所要解決的最優路徑問題并不僅僅指最短的路途。它還包括利用電子地圖在最短時間和最小花費內尋找到最合適的通向目的地的路徑或者在電子地圖的幫助下，將這幾個問題全部綜合在一起，最后使問題得到解決。同時在電子地圖對路徑的道路級別、人流量的大小以及轉彎限制等做出詳細的判斷之后，確定最佳的路徑模式。此時可將啟發式模型中的g（x）進行一定程度的修改：g（x）=∑aijLij+∑bmnTmn。在該式中，Lij表示的是i和j之間的路徑長度；其中aij表示的是相應的權值，這個參數與道路的級別和流量有關；Tmn表示的是從路段m到路段n之間所需要的花費（如時間等）；與之相應的bmn代表的是穿越的權值。若在該路段處禁止轉彎則可將其設置為常數，g（x）則表示從起點到所要到達的地點之間的花費。在電子地圖啟用最佳模型的情況下，進行路徑的選擇。
3.3確立加權模型
中圖分類號: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.
隨著科技的不斷進步，我國自動化技術發展越來越好，這對提高人們的生活質量有著較大幫助。應用自動化技術，可以生產出具有更多功能的機器與設備，比如，自動導航小車就是一種新型的機器，其具有自動定位與行駛的特點，可以利用計算機技術，對小車的行駛路徑進行規劃與控制。自動導航小車的設計與制作涉及多個領域，在科技不斷發展的背景下，我國自動化控制水平越來越高，這也促進了自動導航小車的發展。下面筆者對自動導航小車的路徑規劃以及控制方法進行簡單分析。
1.自動導航小車路徑規劃的定義與方法
1.1自動導航小車路徑規劃的定義
有學者對自動導航小車這類機器的路徑規劃有著如下定義：在自動導航小車中，設有自動導航系統，該系統是由較多的剛體部件構成的，而且有著不同的自由度。如果該系統可在二維或者三維空間中運行，則說明小車可以在不破壞自身運動約束的條件下，進行自由運動。另外，在工作空間中，也存在較多的幾何參數障礙。路徑規劃指的是自動導航小車在系統設定的連續動作下，由給定的初始位形運動到目標位形的設計。位形指的是自動導向小車位置與形態，相關設計人員通過改變位形，可以控制小車的行車路線。
1.2路徑規劃的方法
自動導航小車路徑規劃的方法主要有兩類，其一是傳統方法，其二是智能方法。第一類傳統路徑規劃方法中，常用的有自由空間法、圖搜索法、人工勢場法等；第二類智能路徑規劃方法中，常用的是基于遺傳算法的路徑規劃、基于人工勢場的路徑規劃等等。在現代自動導航小車設計中，應用智能方法比較多，其可以提高路徑規劃的準確性，下面筆者對自動導航小車的路徑規劃常用的幾種智能方法進行簡單的介紹。
1.2.1基于遺傳算法的路徑規劃
基于遺傳算法的路徑規劃在自動導航小車路徑研究中應用比較廣泛，其是由國外的學者提出的，是在模擬達爾文生物進化論的基礎上創建的，應用這種方法可以解決傳統路徑規劃中存在的漏洞。遺傳算法具有隨機性，而且具有針對性，利用遺傳算法可以對自動導航小車的移動路徑進行準確的規劃，其具有高效的特點。
1.2.2基于人工勢場的路徑規劃
人工勢場是一種虛擬的方法，其將自動導航小車的運動路徑看做是人工受力場下運動，應用虛擬的方法，主要是利用障礙物對自動導航小車所產生出的斥力，以及目標點對小車產生的引力而完成運動路徑的。在斥力與引力的共同作用下，自動導航小車可以從初始位形移動到目標位形，由于斥力與引力對小車的速度有著較大影響，所以，利用加速力相關人員還可以計算出小車所處的位置，從而控制小車的運動方向以及路徑規劃。
2.不同環境下自動導航小車的路徑規劃策略
自動導航小車是一種新型的機器，其在未知的環境下，收集信息的情況也有一定差異，通過分析發現，其收集信息主要有兩種類型，一種是在已知的信息環境下，全局路徑的規劃；另一種是在未知的環境信息下，局部路徑的規劃。下面筆者主要對靜態已知環境下局部路徑規劃方法以及靜態未知環境下局部路徑規劃方法進行分析。
2.1靜態已知環境下局部路徑規劃方法
靜態已知的信息環境下，對小車局部路徑進行規劃是一種比較容易實現的方法，這種規劃方法有著廣泛的應用空間，這種方式最早應用的是可視圖算法，隨著科技的不斷發展，相關人員又提出了隨機路圖法，這兩種方法有著各自的適用范圍。可視圖算法提出的時間比較早，其廣泛應用是在1987年，研究人員利用可視圖算法，解決了小車路徑規劃問題?？梢晥D是由節點與可視邊組成，在已知的環境下，技術人員通過設置障礙點以及目標點，可以幫助小車快速到達指定位置。為了提高小車運動的效率，設計人員需要了解可視圖算法的最短路徑定理，該定理指出，從初始點到目標點含有窮路徑集合，為了得到最短路徑的算法，需要全面考慮可視圖構造，這種方法在二維空間中發揮較高的效用，但是在高維空間中并不適用。
2.2靜態未知環境下局部路徑規劃方法
靜態未知環境下，自動導航小車需要利用自身傳感器對環境進行感知，在獲得局部信息后，對局部路徑進行規劃，這種規劃方式主要采用了勢場法，但是在應用的過程中也存在一定局限性，設計人員需要重點考慮梯度以及積分問題，而且需要通過分析多個局部信息，掌握全局信息。這種路徑規劃法效用的發揮與傳感器性能有較大關系，為了更好的掌握全局信息，設計人員多采用的是實時傳感器。這種規劃方法的基本思路是：自動導航小車向目標點運動的過程中有多種路徑，相關人員需要將所有可能性進行量化，在通過分析障礙物信息，從而得出最佳的規劃路徑。在對通路進行檢測時，要避免小車進入死路，通過測量障礙物間的距離，判斷小車是否可以通行，如果通路被堵塞，則需要重新優化路徑。
3.自動導航小車的路徑控制
控制軟件與各模塊驅動程序是保障系統正常運行不可或缺的部分。控制軟件在主機上實現，各模塊驅動程序在各自模塊中運行，控制軟件與各模塊驅動程序之間可通過主從式結構進行必要的通信聯系。子機可向主機發出異常情況處理信號，利用通信技術，還可以控制各子模塊的運行狀況。
3.1運動控制的位置環調節
參數調節運動控制驅動器的位置控制回路時，運用基于觀測器的狀態變量控制技術。采用此技術，運動控制驅動器的優點是：⑴系統將具有很高的動態剛度；⑵即使負載和電機的慣量有較大差別，仍可有效減少跟蹤誤差。在運動之前，必須進行軌跡參數設置及完成參數設置。初始調節時，一般設定運動速度、加速度、加加速度為較大值，而運動位置為一較小值。
3.2軸的運動
軸運動有兩種，一種是單軸運動，另一種是多軸協調運動。單軸運動是指某一種運動模式設定后，該軸將保持這種運動模式，直到設置新的運動模式為止。多軸協調運動是指運動控制器可以實現兩種軌跡的多軸協調運動。對于各模式之間的切換，除電子齒輪模式之外，其他模式必須是在當前軸運動完全停止的情況下進行?？刂破髦胁煌妮S可以工作在不同的運動模式下，在某些情況下，為了安全起見，需要在某些位置或某個時刻使運動停止。
4.結語
通過上文的分析可以看出，自動導航小車具有較高的性能以及較多的功能，其性能體現了我國科技的進步性。在計算機技術的影響下，相關設計人員利用傳感器，使自動導航小車獲取周圍環境的信息，其獲取的方式有兩種，一種是在已知的信息環境下，獲取全局信息，另一種是在未知的環境下，獲取局部的信息。為了更好的控制小車路徑，相關人員需要掌握傳感器信息融合算法，還要避免外界環境對信息準確性的影響，這樣才能提高路徑規劃與控制測量的可行性。
【參考文獻】
Abstract：this article simulated biological immune process，and established the mathematical model of immune algorithm.It is studied the application of mobile robot path planning in static and dynamic environment.
Key words：Immune algorithm;Intelligent vehicle path planning;Simulation experiment
1.概述
隨著機器人相關技術的發展，對于智能車輛控制的準確性要求越來越高，控制系統的數學模型的好壞直接影響著控制的有效性和準確性。智能算法用于建模困難或本質為非線性或復雜對象的控制系統，效果優于常規控制方法，若系統的轉動慣量，結構參數等存在誤差是仍能實現精確跟蹤，魯棒性良好。
為解決路徑規劃及壁障問題，我們在局部環境中，出現智能車輛必須放棄期望軌跡避開障礙物的情況下，研究基于免疫算法的智能車輛避障控制方法：首先在局部環境下，生成占有柵格地圖;再生成障礙物的極坐標柱狀圖;設計了基于免疫算法的車輛避障方法。
2.免疫算法
人工免疫系統（Artificial Immune Sys-tem，簡稱AIS）是在免疫學及其理論的基礎上發展而來的，因此需對生物免疫系統進行研究。生物免疫系統是復雜程度很高的系統，在檢測和消除干擾問題上表現出了精確的調節能力。免疫系統展示了許多可以將其融入人工智能系統的性質：如多樣性、動態性、適應性、魯棒性、自適應、自治性、自我監測、錯誤耐受等等。
在免疫算法用于路徑規劃中，我們有如下，如表1所示。
表1 對應關系
免疫系統 路徑規劃
障礙物 抗體
可行柵格 抗原
親和力 路徑選擇可行度
抗體變異 動態障礙物
算法步驟：
考察車輛的路徑規劃問題，智能車從初始點gs出發，尋找一條通往目標點的最優路徑。如果智能車某時刻ti位于柵格點的gi，那么它下一步必然選擇gi周圍的可行柵格。
步驟1：確定載入的抗原（障礙物），隨機產生初始抗體即隨機產生候選解，創建一個總量為N的初始種群抗體集合P（可行柵格）。
步驟2：計算抗體親和力：對于每個vP，評估g（v）和創建克隆種群C，親和力g設為對應的函數。
步驟3：從種群C中選擇n個親和力最高的抗體形成臨時抗體集v’。
步驟4：克隆親和力高的抗體：克隆上一步n個親和力最高的抗體，其中每個抗體被單獨克隆，抗體親和度越高，被克隆的抗體規模越大。通過評估g（v'），如果g（v'）>g（v）那么通過克隆v'取代v。即，選擇路徑最優。
其中：
（1）
g（v）是抗體克隆總數量，是一個克隆因子，N是抗體集合P的總數量，i是以遞減排序的最有抗體序號，ceil是向上取整算子。通過上述的條件判斷和克隆取代操作，可使最優抗體的規模逐步擴大。
步驟5：對新的種群中的部分抗體進行變異操作（加入動態障礙物）。
步驟6：重新計算變異后的親和力并令n加1，重復第四步操作。
步驟7：判斷gi是否滿足終止條件，即是否到達目的地gd;若不是返回步驟2，將gi設為gi+1，否則算法結束，輸出最優路徑。
3.免疫算法路徑規劃仿真
3.1 環境模型
假定：①移動機器人在二維有限空間中運動;②機器人的工作空間中分布著有限個障礙物;③把障礙物邊界向外擴展機器人體在長、寬方向上最大尺寸的l/2，機器人中心位置可用點來表示，即所謂“點機器人”。
記A為移動機器人R在二維平面上的凸多邊形有限運動區域，以A的左下角為坐標原點，水平向右為X軸正方向，垂直向上為Y軸正方向，建立直角坐標系XOY，則有A在X、Y軸上的最大值分別為Xmax和Ymax。以占為步長將X，Y分別進行劃分，由此形成環境的柵格圖表示。每行的柵格數Nx=Xmax/，每列的柵格數NY=Ymax/，考慮到A為任意形狀，可在其邊界補以障礙柵格，使其成為正方形或者是長方形。每個障礙物至少占有一個柵格，當不滿一個柵格時，算一個柵格。任意一個柵格g，都有確定的坐標g（x，y）及相應的序號S，其中x為g所在的行號，y為g所在的列號。定義g（l，l）的序號為1，g（l，2）的序號為2，…，則坐標g（x，y）與序號S之間的關系可表示為：
式中，mod為求余運算，int為舍余取整運算，i=l，2，…，M，M為地圖中柵格的總數。由此，我們可構建一個8x8的柵格地圖如圖1所示。
3.2 靜態路徑規劃
為了驗證算法的有效性，我們建立了在各種復雜環境下，只要有通路存在，本算法都可以迅速的規劃出最優路徑。如圖2所示。
圖1 柵格地圖
圖2 最優路徑
3.3 動態路徑規劃
本實驗的目的是讓移動機器人避開所有的障礙物，并且追捕到運動目標。即，通過變異操作實現動態障礙物的克隆取代。其仿真結果如圖3（a）、（b）、（c）在動態障礙物，在不同位置時的路徑規劃。只要存在到達目標點的通路，本算法必能快速的規劃出最優路徑。
圖3 動態路徑規劃
4.結論
本文研究了靜態和動態環境下移動機器人的路徑規劃問題。首先，描述了仿真環境建立，然后，較為詳細地介紹了免疫算法，并研究了它在靜態和動態環境下移動機器人的路徑規劃中的應用。并驗證其應用的有效性。
參考文獻
DOIDOI：10.11907/rjdk.161914
中圖分類號：TP301文獻標識碼：A文章編號文章編號：16727800（2017）001017703
引言
自20世紀80年代末以來，多機器人系統開始引起廣大學者關注，并且得到了迅速發展。相較于傳統的多個單機器人系統而言，多機器人系統具有更大的優勢。比如，多機器人系統在時間和空間分布性上更加具有優越性。具有分布性的多機器人系統中單個機器人的傳感器信息可以有效互補，因此整個機器人系統具備較高的數據冗余度和更強的自適應性、魯棒性；在多機器人系統中，由于單個機器人可以不必具有極強的功能和極高的性能，因此多機器人系統本質上具備低成本、強魯棒性的優勢；尤其是在完成復雜任務時，多機器人的優勢更加突出，通常多機器人系統能夠借助先進的協作架構和協同策略，完成多個單臺機器人難以實現的復雜任務等。
多機器人系統的主要特點有：由于高科技快速發展，機器人的研究和開發更加容易、自適應性更好。隨著多機器人協作策略的不斷進步，其完成復雜任務的成本更低、效率更高、可擴展性更好。近年來，由于材料科學等邊緣科學及交叉科學的發展，機器人的研發成本逐年降低，同時多機器人的應用范圍和領域更加廣泛。因此，越來越多的學者們重視多機器人系統及其應用研究，多機器人系統已經成為機器人學研究中一個飛速發展、具有良好應用前景的研究方向。
近年來，隨著科技不斷進步，多機器人系統相關研究得到快速發展，多機器人系統中的實現技術也取得較大突破[12]。目前，多機器人系統的關鍵技術主要包括任務規劃、運動規劃、協調控制等[35]。
1多機器人系統國內外研究現狀
目前，多機器人系統的研究無論在理論中還是在實踐上都取得了很大進展，建立了許多仿真系統和硬件實驗平臺，為進一步研究機器人系統夯實了基礎。日本屬于較早開展多機器人系統研究與實踐的國家之一，1989年設計出了著名的ACTRESS系統和CEBOT系統。圖1為日本名古屋大學Fukuda等研制的CEBOT（Cellular Robotics System） 系統，該系統采用分布式體系結構設計，將多機器人系統中功能簡單的自主機器人視為“細胞元”（Cells），研究“細胞元”機器人自組織地構成功能強大的多機器人系統。特別是通過傳感器感知環境的動態變化，“細胞元”間相互耦合并自組織重構得以實現更加優化的體系結構。
1996年第一屆機器人足球世界杯在韓國隆重舉行，來自7個國家的23支參賽隊參與了競賽，如圖2所示。1997年過多方共同努力，成立了國際機器人足球聯合會，聯合會總部設在韓國，其任務包括：每年組織一次機器人足球世界杯大賽；同時還要舉辦相關學術會議，給參賽者提供充分交流的學習平臺，探討機器人足球研究方面的經驗和技術，從而有效地促進該學科方向的不斷發展。
圖3為美國南加州大學Mataric等人研制的The Nerd Herd 系統。該系統由20個機器人組成，每個機器人上裝有碰撞傳感器、定位系統和通訊系統，可以實現游弋（Safe Wandering）、跟隨（Following）、聚集（Aggregation）、分散（Dispersion）和回家（Homing）等行為。研究人員主要將該系統應用于多機器人學習、群體行為、協調與協作等方面的試驗研究與探討，圖4為利用該系統進行的推箱子實驗裝置。
圖2機器人世界杯圖3The Nerd Herd系統 C.R.Kube等人研制的Collective Robotics 系統如圖5所示。該系統從自然界里昆蟲的社會行為得到啟發，利用多個功能簡單的機器人組成功能強大的合作機器人群體。該系統在無顯式通信的條件下，能夠充分利用分布式控制策略實現移動機器人之間的協作。因此，單個簡單智能的機器人通過交互作用實現了多機器人系統復雜的群體智能行為。
圖6為美國MIT的計算科學和人工智能實驗室（CSAIL）研制開發的多機器人系統。該實驗室在多機器人系統上開展了協調多個機器人行為的算法設計、多機器人協調算法性能預測等問題的研究。這些關鍵問題及其研究成果形成多機器人控制算法的重要基礎。
我國在多機器系統的研究方面也開展了卓有成效的工作，雖然起步相對較晚，但到目前為止也取得了豐碩的研究成果。沈陽自動化研究所以制造環境中多機器人的裝配為研究背景，建立了多機器人協作裝配系統MRCAS（Multi-Robots Cooperative Assembly System）。通過采用集中和分散相結合的分層體系結構，該系統可以完成自主編隊行進、隊形變換、自主避障等功能，進一步通過多機器人間協調與合作，完成裝配工件任務。南京理工大學在早期開展的地面微小型機器人研究基礎上，進行了移動機器人協作編隊、自主定位、智能導航等關鍵技術研究，并取得一定成果。目前，由清華大學、國防科技大學、浙江大學和南京理工大學等著名高校聯合研制的第四代無人駕駛車輛實現了多車無人干預下的編隊行駛、超車行駛等核心技術。此外，上海交通大學、哈爾濱工業大學、中南大學等知名高校紛紛開展多機器人系統關鍵技術研究，也取得了一系列突破性研究成果，為我國機器人系統研究與發展奠定了重要基礎。
2多機器人路徑規劃問題研究
多機器人路徑規劃問題是多機器人系統的關鍵技術，該技術也是多機器人協作完成任務的根本保障。多機器人路徑規劃問題定義為：利用已知的靜態環境信息或者依靠傳感器獲得的動態環境信息，多機器人系統各個機器人自主規劃一條從已知起點到目標終點的無碰撞最優路徑，該最優路徑不僅要求單個機器人與所有障礙物之間避障，而且還需滿足多個機器人之間也無碰撞要求。
由單個機器人路徑規劃問題發展而來的多機器人路徑規劃問題，首先需要解決單個機器人路徑規劃問題，其次還要求解決多機器人之間的協調運動和多個機器人之間的協作問題，重點就是避免機器人之間的碰撞和避免出現機器人之間的路徑死鎖等問題。其中，環境建模方法、路徑規劃算法、協調避碰算法等都是關鍵技術問題[6]。
2.1環境建模
最有效的環境建模方法是建立環境地圖，柵格地圖、拓撲地圖、特征地圖等是目前常用的環境地圖。
為了方便機器人的定位，柵格法將整個環境劃分為許多大小相同的正方形單元格，并給予每個單元格唯一的整數標示。柵格地圖模型最大的優點是簡單，其缺點是柵格地圖的粒度不好控制，若粒度較小，計算復雜度增加，若粒度較大，真實環境無法準確表示。
拓撲地圖是利用節點間相關聯的邊所構成的拓撲結構來標示環境，拓撲地圖模型將環境中的重要位置視為節點（如障礙物的棱角），將節點間存在的直接連接的路徑視為地圖中的邊。拓撲地圖雖然適用于環境比較簡單的情況，也不需要機器人準確的位置信息。但拓撲地圖通常難以直接獲取，且對于相似環境的識別也比較困難。
特征地圖模型不同于以上兩種方法，本文利用抽象的幾何特征（如點、直線、曲線等）表示機器人感知的外部環境。此模型便于位置估計和目標識別，但抽象的幾何特征需要對感知的環境信息作進一步處理才能獲取，一般適用于特定的環境。
2.2規劃方法
按照多機器人系統運動規劃的控制方式，多機器人的運動規劃方法可以分為以下4種類型：①完全集中的規劃：需要一個集中控制器來規劃所有機器人的運動；②不完全集中的規劃：每個機器人規劃好自己的路徑，但是有一個集中控制器來管理多機器人系統中單個機器人如何走自己的路徑以保證機器人間不發生沖突；③不完全分散的規劃：多機器人系統中單個機器人規劃各自的路徑以及如何走好自己規劃的路徑，在不安全情況下才由集中控制器進行統一規劃；④完全分散的規劃：單個機器人的運動完全自主規劃，不存在集中控制器。
2.3協調避碰策略
協調避障是多機器人系統路徑規劃問題的重要技術之一，也是多機器人系統路徑規劃和多個單機器人路徑規劃的本質區別體現。多機器人系統協調避障問題除了要解決單個機器人自身路徑規劃問題，還必須解決多個機器人之間的碰撞、堵塞及死鎖問題。目前，學者們提出的協調策略主要有速率調整法、交通規則法、優先級法、幾何修正法以及基于行為的避碰方法等。隨著“智能制造2025”的深入推進，服務機器人應用領域還在不斷擴展，多機器人系統協調避碰策略亟需進一步探討。
3多機器人系統展望
多機器人系統是一個多學科高度交叉的前沿學科，多機器人系統的進一步發展也必定會受到相關學科發展的限制。研究多C器人系統需要借鑒這些學科或學科中解決某些問題的理論和方法，才能產生突破性進展，這是未來研究多機器人系統的發展方向和重要趨勢，具體而言，這些學科有：分布式系統、生物學、傳感器技術、機械工程等?？蓮囊韵聨讉€方面探討多機器人路徑規劃問題：
（1）先進的傳感技術。移動機器人中傳感器設備被視為人類的五官，實現移動機器人的視覺、聽覺、嗅覺等功能。在環境建模中依靠先進的傳感技術，機器人能完成高效實時采集環境信息的任務。
（2）多傳感器的信息融合技術。移動機器人導航方式正在向多傳感器發展，使用多個傳感器可以同時采集和處理信息，從而提高機器人系統的速度和性能。通過合理支配并充分利用傳感器及其采集信息，并采用信息融合技術以獲得環境的一致性解釋及描述形式，可以提高機器人路徑規劃的精準度和魯棒性。
（3）智能優化算法的發展。隨著復雜問題規模呈現指數級增長，智能優化方法迅速成為多機器人系統路徑規劃研究新的發展方向。但由于算法實時性、自適應性、魯棒性還不夠好，智能優化算法在實際應用中必然存在一定的局限性。因此，多機器人系統路徑規劃問題研究中，智能優化算法還有很大的發展空間。
4結語
多機器人系統的研究與應用已經對人類社會產生深刻影響，隨著科學技術的不斷進步，其還將會對人類生活和社會進步帶來巨大變革。不久的將來，人們的生活質量和工業、農業和國防現代化水平都將得到極大提高。但目前對于多機器人系統的研究還處于初級階段，多機器人系統關鍵技術研究還亟需深入探討，特別是多機器人系統路徑規劃算法還有待進一步改進，多機器人系統無論在理論研究上還是技術實現上都需要更多學者進行不懈努力和積極探索。
參考文獻：
[1]吳軍，徐昕，連傳強，等.協作多機器人系統研究進展綜述[J].智能系統學報，2011，6（1）：1326.
[2]原魁，李園，房立新.多移動機器人系統研究發展近況[J].自動化學報 2007，33（8）：785795.
[3]蔡自興，崔益安.多機器人覆蓋技術研究進展[J].控制與決策，2007，2（3）：17.
[4]張崳，劉淑華.多機器人任務分配的研究與進展[J].智能系統學報，2008，3（2）：115120.
中圖分類號：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）的揮發性化學物質來進行通信和協調的?；瘜W通信是螞蟻采取得基本信息交流方式之一，在螞蟻的生活習性中起著重要的作用。通過對螞蟻覓食行為的研究發現，整個蟻群就是通過這種信息素進行相互協作，形成正反饋，從而使多個路徑上的螞蟻都逐漸聚集到最短的那條路徑上。
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.
中圖分類號:TP301文獻標識碼:A文章編號:1009-3044(2010)11-2717-02
醫藥物流是指醫藥器械從醫藥配送中心分發、配送到各個醫院和醫療中心的過程,甚至包括通過醫院到達消費者(患者)手中的過程,其中所產生的物流成本是醫藥器械成本的重要組成部分。降低醫藥運輸成本是減少患者醫療負擔的重要途徑之一。而藥物配送實際上就是旅行商問題[1]。遺傳算法作為一種求解問題的高效并行全局搜索方法,成為目前解決NP完全問題的較為有效的方法之一。
1 旅行商問題與遺傳算法
1.1 旅行商問題原理
旅行商問題(Traveling Saleman Problem,TSP)是VRP[2]的特例,已證明TSP問題是NP難題。旅行商問題(TSP)又譯為旅行推銷員問題、貨郎擔問題,簡稱為TSP問題。TSP問題可描述為:給定一組n個城市和它們兩兩之間的直達距離,尋找一條閉合的旅程,使得每個城市剛好經過一次而且總的旅行路徑最短。TSP問題的描述很簡單,簡言之就是尋找一條最短的遍歷n個城市的路徑,或者說搜索整數子集X={1,2,…,n}(X中的元素表示對n個城市的編號)的一個排列π(X)={v1,v2,…,vn},使取最小值。式中的d(vi,vi+1)表示城市vi到城市vi+1的距離。
1.2 遺傳算法基本原理與描述
1.2.1 算法原理
遺傳算法是一種借鑒生物界自然選擇和自然遺傳機制的隨機搜索算法,由美國J.Holland教授提出,其主要內容是種群搜索策略和種群中個體之間的信息交換,搜索不依賴于梯度信息。該算法是一種全局搜索算法,尤其適用于傳統搜索算法難于解決的復雜和非線性問題。
1.2.2 算法描述
該算法包括以下6個基本要素:
1) 編碼:遺傳算法不能直接處理解空間的數據,必須通過編碼將它們表示成基因型串數據。常對參數采用二進制編碼,編碼當作一條染色體,編碼前應先量化[3]。
2) 生成初始種群:初始種群的個體通過隨機方法產生,且對應研究問題的一個解。
3) 評估適應度:遺傳算法在搜索過程中用適應度來評估個體的優劣,并把它作為遺傳操作的依據。適應度函數常取非負數,且適應度增大的方向與目標函數的優化方向一致。
4) 選擇:根據適者生存的選擇原理,從當前種群中選擇生命力強的個體(即適應度高的個體),產生新的種群。適應度越高的個體,被選擇的機會就越大,但并不意味著適應度高的個體一定會被選擇[4]。
5) 交叉:將選擇出的個體存入配對庫,用隨機的方法進行配對,以產生新一代的個體。
6) 變異:在交叉過程中可能丟失一些重要的遺傳信息(特定位置的0或1)1必須引入適度的變異,即按一定的概率改變染色體基因位。
2 優化路徑遺傳算法的構造
針對優化物流配送路徑的特點,本文構造了求解該問題的遺傳算法。
2.1 初始種群的生成與編碼方法的選定
隨機生成規模為N的初始種群。采用巡回旅行路線所經過的各個城市的順序排,列來表示各個個體的編碼串,這是TSP問題最自然的一種個體編碼方式。例如對于一個10個城市的TSP:2-5-3-4-7-1-6-8-9(可簡單表示為[253471698]),表示從城市2出發依次經過城市5,3,4,7,1,6,8,9,然后返回城市2的一條路徑。這種編碼方式滿足TSP問題的約束條件,保證了每個城市經過且只經過一次,在任何一個城市子集中不形成回路[5]。
2.2 適應度評估
對于某條染色體,設其對應的配送路徑方案的不可行路徑數為Ni(Ni=0表示該個體對應一個可行解),其目標函數7值為Td,則該個體的適應度可用下式表示:,式中α為對每條不可行路徑的懲罰權重,可根據目標函數的取值范圍取一個相對較大的正數(α值太小則會影響適應度的比較)。
2.3 遺傳操作
2.4.1 選擇操作
選擇將使適應度較大個體有較大的存在機會,而適應度較小的個體繼續存在的機會也較小。簡單遺傳算法采用賭輪選擇機制,令Σfi表示群體的適應度值之總和,fi表示種群中第i個染色體的適應度值,它產生后代的能力正好為其適應度值所占份額fi/Σfi。作為其被選中的概率Psi。這方法既可保證最優個體生存至下一代,又能保證適應度較大的個體以較大的機會進入下一代。
2.4.2 雜交操作
采用順序編碼法后,若用簡單的一點雜交或多點雜交,必然會導致未能完全遍歷所有城市的非法路徑。如城市9的TSP問題的兩個父路徑為:1 2 3 4 |5 6 7 8 9; 9 8 7 6 |5 4 3 2 1,若采取一點雜交,雜交點隨機選為4,則雜交產生的兩個后代為:9 8 7 6 |5 6 7 8 9;1 2 3 4 |5 4 3 2 1,顯然,這兩個子路徑均未能遍歷所有9個城市都違反了TSP問題的約束條件,為解決這一問題,既要進行雜交操作,又要滿足約束條件,就必須對雜交操作進行修正[6]。關于路徑表示的常用的幾種修正的雜交操作方法為:
1) 部分映射雜交(PMX, partially-mapped cross-over)。
在PMX操作中,先隨機地在父體中選取兩雜交點,并交換相應段。再根據段內的城市確定部分映射。在每父體中先填入無沖突的城市,而對有沖突的城市分別執行這些部分映射直到填入無沖突,則獲得雜交后的兩后代。例如,兩父體A1、A2為('|'標記截斷點) A1=(2 6 4 |7 3 5 8 |9 1), A2=(4 5 2 |1 8 7 6 |9 3)。則由交換段確定的部分映射為:7-1,3-8,5-7,8-6,先交換相應的段得B1=(### |1 8 7 6|##),B2=(### |7 3 5 8 |##)。此處'#'表示城市待定。再從各自的父體中填入無沖突的城市得B1=(2#4 |1 8 7 6 |9#),B2=(4#2 |7 3 5 8 |9#)。個體B1第一個'# '處原處為6,映射到8后仍有沖突,再將8映到3填入。第二個'#'處原處為1,映射到7后仍有沖突,再將7映到5填入。類似地求得B2。于是兩后代為B1=(2 3 4 |1 8 7 6 |9 5), B2=(4 1 2 |7 3 5 8 |9 6)。這樣,子代仍是遍歷的,但每個子代的次序部分地由其父代確定。
2) 次序雜交(OX, order crossover)。
次序雜交的操作與部分映射雜交的操作非常類似。也是首先隨機地在父體中選擇兩雜交點,再交換雜交段,其它位置根據保持父體中城市的相對次序來確定。例如,設兩父體及雜交點仍為前述的A1和A2, A1=(2 6 4 |7 3 5 8 |9 1), A2=(4 5 2 |1 8 7 6 |9 3)。交換雜交段于是仍有B1=(### |1 8 7 6 |##),B2=(### |7 3 5 8 |##)。從B1的第二個雜交點開始,將路徑依原次序排列,即: 9-1-2-6-4-7-3-5-8去除雜交段中的城市,得子路徑9-2-4-3-5。依次順序從第二個雜點開始填入得B1=(4 3 5 |1 8 7 6 |9 2),類似地有B2=(2 1 6 |7 3 5 8 |9 4),雖然, PMX法與OX法非常類似,但它們處理相似特性的手段卻不同。PMX法趨向于所期望的絕對城市位置。本算法采用此方法交雜交。
3) 循環雜交(CX, cycle crossover)
循環雜交將另一父體作為參照以對當前父體中的城市進行重組。先與另一父體實現一個循環鏈,并將對應的城市填入相應的位置。循環組成后,再將另一父體的城市填入相同的位置。例如,仍考慮前兩個父體路徑A1=(2 6 4 7 3 5 8 9 1), A2=(4 5 2 1 8 7 6 9 3)。先從A1中取第1個城市作為B1的起始點,于是B1=(2########),由于后代中第一個城市都必須從父體相同位置的城市中選取,于是根據循環原則,2對應于A2中的城市4,而在A1中位于第3位,所以應有B1=(2#4######),又A1中城市4對應于A2中的2,于是組成了一個環。再將A2中剩余的城市填入對應的相同位置得到B1=(2 5 4 1 8 7 6 9 3),類似地可得到B2=(4 6 2 7 3 5 8 9 1),由此可見,循環雜交保持其父體串中城市所處的絕對位置。
3 算法實現和結果
下面對某市一醫藥公司的銷售點的物流配送路徑規劃用遺傳算法進行優化。該公司有56處銷售點,通過路徑規劃希望找出最優路徑以節省運輸成本。
3.1 運行參數設計
本實驗采用n城市的遍歷順序編碼法,適應度函數取總長度Td的倒數(無懲罰函數)。選擇機制是保留M個較優個體,在每一代運算中,個體被選中的概率與其在群體中的相對適應度成正比。雜交操作采用OX(次序雜交)法。為使算法盡快地收斂,在經過雜交變異操作后,增加了局部優化過程,提高個體對環境的適應。群體規模取56,交叉概率和變異概率分別取0.9和0.01, 最大迭代數2000。
3.2 實驗結果
運行環境:操作系統Microsoft Windows XP;仿真軟件:MierosoftVisualC++6.0。
在實驗計算中采用以上設定參數對該公司配送路徑問題求解,所得到的優配送化路徑最優長度為862,用時126秒,迭代次數1528。得到的路徑線路如圖1所示。
4 結論
在此也可以看到,運用遺傳算法解決實際問題,算法是使用參數的編碼集,而不是參數本身,參數的選擇十分方便;遺傳算法與其他計算機算法不同,相比之下,它比較具有隨機性而不是穩定性,遺傳算法是在點群中,而不是在一個單點尋優。因此利用遺傳算法解決實際問題需要選取大量數據,通過多次實驗的數據分析不斷改進算法和設置參數來求得更優的結果。用遺傳算法求解組合優化問題具有巨大的優越性[7]。非常有助于物流企業根據自己的實際情況科學、有效地制定物流決策,降低風險,降低成本,提高經濟效益和自身的競爭力。
參考文獻:
[1] 田貴超,黎明.旅行商問題(TSP)的幾種求解方法[J].計算機仿真,2006,23(8):153-157.
[2] Holland J H.Adaptation in natural and artificial systems[M].Ann Arbor,Ml:The University Michigan Press,1975.
[3] 余有明,劉玉樹.遺傳算法的編碼理論與應用[J].計算機工程與應用,2006,42(3):86-89.
[4] 陳國良,王煦法,莊鎮泉,等.遺傳算法及其應用[M].北京:人民郵電出版社,1996.
一、問題的提出
2003年，黨的十六屆三中全會上提出“建立績效預算評價體系”，七年來，我國已經在績效預算評價研究上取得了一定的成果，學界對績效預算的關注程度也逐漸提高，各級地方政府紛紛開展了績效預算的理論探索和試點實施工作。但是關于績效預算的一些基礎問題卻沒有得到明確的解決，比如績效預算的內容包括哪些？各部分內容的邏輯關系是什么？推行績效預算的根本目標是什么？具體目標是什么？為了實現各階段的目標，哪些部門應當完成哪些工作？如果這些問題沒有搞清楚，那么實施績效預算就像開了一艘沒有羅盤的輪船，不知道前進的方向在哪里。正是由于這些問題沒有得到回答，目前我國在實施績效預算過程中遇到了許多障礙，例如績效預算實施受到一些部門的抵觸、績效預算評價體系不規范、績效評價沒有貫穿預算全過程、績效評估工作流于形式等。本文的研究目的就是試圖對上述一系列基本問題給出一個清晰的回答，對如何正確、有效、規范地實施績效預算給出一個明確的可行的路徑規劃。
二、績效預算包含內容的邏輯關系界定
1.績效預算所包含的內容
績效預算的內涵是：績效預算是以結果為導向的，注重預算的效率和效果的科學化、民主化的預算。它的根本目的是試圖學習私人部門的績效管理和運行方式，以更有效率的方法為公眾提供公共產品。但僅僅了解績效預算的內涵是不夠的，我們同時應該弄清楚績效預算的具體內容，及其各方面內容之間的邏輯關系，以理解各種情況下所指“績效預算”的真實意思。筆者認為績效預算的內容應該包括以下幾個層次：
(1)將績效理論應用于財政資金支出結果的事后評
(2)將績效理論應用于財政資金的分配、使用、結果
(3)將績效理論應用于預算部門自身的工作評價
(4)將績效評價的結果應用于績效溝通和績效管理
(5)將績效理論擴展應用于政府行政管理的全過程
2.績效預算所包含內容的邏輯關系界定
績效預算是一個系統工程，短短四個字卻包含了十分豐富的內容?？冃ьA算應包括5個層次的內容，他們之間是循序漸進，由淺入深的關系。第一個層次只是對財政資金支出結果的評價，是實施績效預算試水階段。第二個層次是對預算的全程評價，主要目標是將績效方法引入到預算資金的分配和使用階段，實現預算全過程的績效管理。第三個層次是對預算工作自身的評價，即預算工作的的績效評價，它和第一和第二個層次的績效評價對象不同，預算績效評價的對象是預算工作或者預算部門自身，而第一、二層次的績效評價對象則是預算資金。第四個層次則是在獲得全面的績效預算評價結果的基礎上，有效地應用結果，切實發揮績效預算結果的價值，促進部門之間的預算工作的溝通，并為下一年度的預算制定作出指導?？冃ьA算的第五個層次則是將績效管理的思想應用到政府的各個部門和各項行政工作中，這既可以說包括在績效預算之中，因為它構成了績效預算實施的環境，也可以說已經超越了預算本身，成為政府的績效管理。
三、我國實施績效預算的目標規劃
在了解了績效預算的內涵與內容之后，我們進而探索績效預算是否可以在我國實施以及用它達到什么樣的目標。至于可行性和必要性研究，許多學者已經從理論和實踐方面給予了充分的論證，此處不再贅述。此處筆者試圖探索績效預算的根本目標，及其短期和長期的目標，以為績效預算的實施提供明確的行動方向和優先次序。
1.根本目標
政府實施績效預算的根本目標就是對預算過程實施科學化管理，追求財政資金的使用效率，并最終更加有效地向公眾提供公共產品。
2.短期目標
在績效預算實施的過程中普遍面臨的問題是績效評價指標的選擇，尤其是定性指標。相比較而言，項目預算比一般預算的結果和產出更容易定量化，更容易測量和評估。所以在短期，我們主要的主要目標是實現項目預算的全程績效管理，具體分為以下幾個目標：
(1)實現各地區、各部門項目預算的財政資金支出結果的績效評價，建立和完善績效預算評價指標體系，將績效預算的理論和方法在政府部門普及開來。
(2)將績效理論應用于預算資金的分配環節。即要求部門在申請項目預算時提交績效預算計劃報告，其中應包括該項目預算的績效目標，具體的績效評價指標，評價方法，以及該項目的工作程序、方法、所需資源等。由財政部門和相關主管部門共同對該項目的績效預算計劃報告進行績效預測和評估，決定是否撥款和撥款數量的多少，實現事前的績效評估。
(3)將績效預算應用于預算的執行環節，用事前的績效計劃報告對項目的實施進行全程監督。不僅要看花錢的進度，更追蹤促實際項目的實現的數量、質量；資監督源分配合理性、資金使用情況等，促進項目的按時、保質、保量的完成。
(4)在項目執行完成以后，由對該項目執行結果進行績效評價?？冃гu價的指標和方法主要依據初期項目預算申請部門提交的績效預算計劃報告中的各項指標；績效評價的執行主體是財政部門、主管部門、專家學者和公眾代表，公眾對項目實施結果的評價應當是績效評價的主要參考意見，注重公民取向。最終整理、分析出該項目的績效評價總體結果，并將評價結果向公眾公開說明。
3.中期目標
(1)實現對一般預算的績效管理
在實現對項目預算績效管理的基礎之上，我們可以開始對一般預算進行績效管理。這一預算的主要產出就是各單位的行政效率，行政人員工作技能，各單位提供特定公共產品的效率等。對一般預算進行績效管理，其實是為政府部門實現全面的績效管理奠定了基礎。
(2)建立績效評價結果與預算編制相結合的約束激勵機制
在實現對預算過程實施全面的績效管理的基礎上，績效評估的結果就應當開始發揮它的價值。通過對績效評價結果進行分析，財政部門可以辨別各個部門預算執行的質量，因而可以為后期的預算決策提供科學指導。對于預算執行質量高的部門，給予激勵，而對于預算執行質量差的部門給予指導，并且在后期的預算中調整預算計劃。這樣一來，就可以形成了預算決策、預算執行、預算評估的三位一體的激勵約束機制。
4.長期目標
通過一般預算的績效管理推進政府部門的全面績效管理，完成績效預算實施的制度環境改革。這一目標已經不僅僅局限于預算本身，而是擴展到整個政府行政管理體制的績效改革。也就是說績效預算的長期目標是以績效預算為突破口，最終實現政府績效管理，實現為公眾更好地提供公共產品的目的。
四、我國實施績效預算的路徑規劃
由于實現項目預算的全面績效管理是績效預算工作的當務之急，筆者僅就如何實現這個短期目標進行探討。筆者認為我國實現績效預算的路徑，就是一條掃除前進障礙，提供有利條件的路徑，其實也就是為績效預算的實現提供各種支持的這樣一條路徑。要成功地實現績效預算的短期目標，主要需要以下幾點現實支持：
1.思想支持
首先要突破傳統的行政觀念約束，轉變政府行政人員的思想，遏制官僚作風，樹立公共產品提供者和負責人的意識；其次要突破傳統的預算觀念，加強對績效預算的宣傳和推廣力度，樹立一種全新的要產出、要效果的預算意識；第三，要增加公眾參與預算的機會與能力，真正體現公眾作為公共產品需求者的角色，提高公眾對預算決策、預算執行、預算評估的參與度，因為一項預算執行好壞的最終評判標準是公眾的滿意度。最后，績效預算還需要領導者的高度支持，因為績效預算的改革必然會影響到部分既得利益者，必然會跟新興的模式作頑固抵抗，這就需要領導者有足夠的決心和魄力，推進績效預算的順利進行。
2.法律支持
完善預算法案，將績效預算思想融入法案，以法律的形式固定下來。在績效預算的法案中應當明確指出負責績效預算工作推進的具體機構，明確績效預算的主體、目標、績效評價體系構建原則、績效評估工作的要求、績效評估結果的應用等等。這樣一來，績效預算就不會僅僅是一句口號，一種意向，一種提倡，而是成為一項方針，一項具體的有明確負責人和明確執行計劃的改革任務。這樣，各個部門才能明白明確什么是績效預算，目的是什么，各個行政人員必須按照何種標準完成何種事項，以及相應的獎懲措施是什么。法律支持能夠讓績效預算的實施有法可依，增強績效預算實施的規范性和強制性。
3.技術支持
績效預算的核心就是構建規范、科學的財政資金支出的績效評價體系。首先要構建的便是項目預算的績效評價體系。在評價體系構建過程中應當注意以下幾點：
首先，當一些指標難以確定，或者指標評價之間存在沖突時，堅持以公眾的滿意度為最根本的評價標準。
其次，改變目前各地區、各部門各設一套體系，導致績效評價水準參差不齊，績效評價結果可信度差，可比性較差的局面。中央部門應該在百花齊放的同時，博采眾長，集中力量研究出一套質量較高的，并且可以在全國普遍使用的績效評價體系，使得績效評價更加規范化，統一化。另外，當制定一套固定的針對各個部門和各項支出的評價體系存在困難或者不合理性時，我們應當確立一些指定評價指標的原則、規范和指導思想，這樣就可以在遵循一定根本原則的基礎上，又能夠隨機應變，適應各種特殊情況。
第三，不同部門應設置不同的評價標準、模式，有的側重于定量分析，有的側重于定性分析。由此設置相應的共性指標，與個性指標。主要從預算執行情況、財務管理狀況、資產管理情況以及衡量績效目標完成程度的社會效益和經濟效益等方面評價。對適用于不同部門的個性指標，要針對項目實際，結合部門職能和項目管理目標，根據評價的目的，按照一定的程序來制定評價指標和確定評價標準。
4.人員支持
實現項目預算的全面績效管理需要大量的人員支持。一方面要培養績效預算、績效管理的專門人才，建立績效預算學者庫，專門對績效預算的相關理論進行研究。另一方面要對行政人員進行績效預算知識的培訓，使之具備績效預算操作的技能。除此之外，我們也更應當重視對公眾的培養，提高公眾對績效預算的參與積極性和參與能力，因為科學的績效預算的評價離不開公眾的廣泛和深度的參與。
5.制度支持
成功地實現績效預算同樣需要相關的制度支持。在實現短期目標的過程中，我們應當完成對以下制度的改革：進一步完善目前的部門預算制度；完善國庫集中收付制度；改革政府采購制度；完成會計制度由收付實現制向權責發生制度的過度；完善預算的監督制度，并且對預算過程實行問責機制，向單位問責，向個人問責；最后，要增加預算的公開透明度，對于預算信息哪些應該公開，公開到什么程度，政府應該做出明確的要求。
當然上述的每項制度的變革都是非常艱辛和復雜的過程，必然會對績效預算的實施形成阻力，但是它并不能夠阻止績效預算的腳步。即使制度環境不是那么優越，條件不是那么成熟，績效預算的推進也勢在必行。等待，只會延長上述一些不合理制度存在的時間。筆者認為，績效預算既是一種目標，也是一種手段，可以成為改革不合理制度的壓力和動力，最終在實現績效預算的過程中也完成了制度的改革。
參考文獻：
[1]馬國賢: 政府績效評價[M] . 上海:復旦大學出版社,2005.
[2]彭鍛煉 左武:推行政府績效預算管理改革的難點與目標[J]. 中南財經政法大學學報,2009,(6)
[3]白景明:全面認識績效預算[J].中國財政.2009.(24).
本文首先對車輛路徑規劃問題和算法應用，以及運輸貨損理論的研究現狀進行充分調研。在此基礎上，對鮮花配送車輛路徑規劃問題所關注的目標進行分析，除常規的車輛使用數量和車輛行駛里程外，加入了鮮花行業特有的運輸貨損目標，應用遺傳算法與節約算法相結合的兩階段啟發式算法，結合企業物流配送現狀及遠期發展規劃，得出一種鮮花配送車輛路徑規劃的可行方法。
1.車輛路徑規劃理論與研究現狀
作為物流配送中的一個熱門問題，車輛路徑規劃問題最早由Ramser和Dantzing提出，其可以描述為：在一定數量的配送中心和客戶構成的節點網絡中，通過安排合適的行車路線，使配送車輛從配送中心取貨并根據預先設定的路線至每個客戶點卸貨，完成各客戶點所需求的貨物配送量。
1.1車輛路徑規劃理論
1901年，美國的John F.Crowell在政府報告中最早提及物流的概念，用于分析影響農產品流通的不同因素和相關費用。隨著理論研究和實踐應用的不斷深入，為統一對物流的認識，需要對其進行準確的規范化定義。中國的物流術語標準將物流定義為：物流是物品從供應地向接收地的實體流動過程中，根據實際需要，將運輸、儲存、流通加工、包裝、裝卸搬運、配送、信息處理等功能有機結合起來實現用戶要求的過程。
1.2車輛路徑規劃問題研究現狀
VRP是一類具有極強應用性的優化調度問題，它在物流配送、交通運輸等領域獲得了廣泛的應用，其范例大量存在于日常生活之中。由于VRP在應用上的廣泛性和經濟上的重要價值，自1959年由Danzig和Ramser提出以來，一直是學界研究的重點和熱點問題，50多年來已經取得了大量的研究成果。從解法上來看，對VRP的求解算法主要可分為精確算法和啟發式算法，而最近10年來，對于VRP的求解算法研究，主要集中在現代啟發式算法。
2.車輛路徑規劃問題算法分類與概述
自從VRP問題被提出以后，由于其同時具有理論價值和現實意義，VRP問題迅速受到越來越多研究人員的重視，力求能夠發現求解各類VRP問題的高效算法。按照VRP問題發展與研究過程來看，算法大致可分為三類，即精確算法、經典啟發式算法和現代啟發式算法。
通過對大量文獻的分析研究，歸納得出三類算法的優勢與劣勢對比如下：
精確算法，能夠求出問題的精確解，當問題規模較大時，往往會導致計算量過大、存儲信息太多等問題，降低了計算效率，主要適用于較小規模的簡單路徑規劃問題求解。
經典啟發式算法，不斷對解的結果進行優化，能夠保證每次迭代后求得的解都是當前最優解；計算速度快、復雜度低，容易陷入局部搜索，可能無法跳出局部范圍找到全局最優解，與其他算法結合，廣泛應用于復雜大規模路徑規劃問題。
現代啟發式算法，具有能夠跳出當前搜索領域而進行全局搜索的能力；結構開放性，與問題無關性，應用理論要求較高，針對不同問題的研究還不完善，廣泛應用于復雜大規模路徑規劃問題。
3.考慮運輸貨損的鮮花配送車輛路徑規劃問題概述
中國鮮花行業伴隨供給側結構性改革與消費升級的浪潮，近幾年也在發生翻天覆地的變化。
隨著線下連鎖店數量逐漸增加，物流配送壓力與成本也不斷上升，配送車輛路徑規劃便成為亟待考慮并解決的問題。對于中心倉庫-連鎖店運營模式，采用巡回配送方式更優于點對點的直送方式。通過對運輸貨損研究的分析，一般整個配送過程中的貨損可分為兩部分：一是在配送運輸過程當中的損耗，由生鮮品時間累積產生損耗和路況引起的顛簸、碰撞損耗組成；二是在客戶點裝卸貨物時，由溫度變化與時間累積產生的損耗和裝卸操作（例如野蠻操作）引起的貨損損耗組成。
3.1參數定義及約束條件
設有n個客戶節點，每個客戶節點的需求量為（i=1，2，…，n）；有m輛配送車輛（型號種類完全一致），每輛車的最大載重量為Q。客戶i到客戶j的距離為， 0表示配送中心，則配送中心到客戶點的距離為 （i=1，2，…，n）。由于一條線路上所有客戶點由一輛車進行配送，所以要求考慮貨損量的前提下，每條線路客戶點需求量之和不超過每輛車的最大載重量。
4.小結
通過對考慮運輸貨損的鮮花配送車輛路徑規劃問題進行概述，介紹了中心倉庫-連鎖店運營模式下，車輛路徑規劃問題的多目標函數。本文求解的VRP問題屬于大規模VRP問題，參數定義和約束條件與一般VRP問題類似，同時根據問題實際情況增加了貨損相關的各類參數、例如多種貨物損耗比例等。具體建模階段，遵循“化繁為簡”思想以及多目標函數求解思路，將目標函數通過各自獨立的成本轉換因子轉化為成本相關的目標函數，最終通過疊加得到了以總成本為目標的車輛路徑規劃單目標函數，從而確定最經濟鮮花配送路徑。
參考文獻：
[1]丁秋雷，胡祥培，李永先.求解有時間窗的車輛路徑問題的混合蟻群算法[J].系統工程理論與實踐，2007，10：98.104.
[2]劉勇，崔炳謀，王小東.物流配送路徑優化問題的模型及改進混合算法[J].物流科技.2008（4）：88-90.
[3]李大衛，王莉，王夢光.遺傳算法在有時間窗車輛路徑問題上的應用[J].系統工程理論與實踐，1999，8：65.69.
