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