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