引言 
            在柔性制造系統(tǒng)(Flexible Manufacturing System,FMS)中最具柔性和發(fā)展最快的物料輸送系統(tǒng) 之一是自動(dòng)導(dǎo)向小車系統(tǒng)(Automated Guided Ve— hicleSystem，以下簡(jiǎn)稱AGV系統(tǒng))。物料輸送是制 造過程中的關(guān)鍵活動(dòng)。物料輸送包括物料在生產(chǎn)的 各個(gè)階段的拾取、運(yùn)送、存儲(chǔ)和包裝。物料輸送的準(zhǔn)確及時(shí)對(duì)于提高FMS的生產(chǎn)效率和降低成本意義重大。 
            一個(gè)AGV系統(tǒng)由若干臺(tái)計(jì)算機(jī)控制的無人駕 駛小車組成。大部分現(xiàn)有AGV是在計(jì)算機(jī)調(diào)度下 沿導(dǎo)向軌道行駛，雖然其導(dǎo)向方法具有高可靠性，但卻降低了AGV系統(tǒng)的柔性。自由分布AGV系統(tǒng)使 用超聲波或激光視覺等裝置引導(dǎo)小車，使小車可在 車間內(nèi)自由行駛，從而增加了系統(tǒng)的通用性。
            自由分布AGV系統(tǒng)所碰到的一個(gè)主要問題是 小車的調(diào)度和控制，需要有效的AGV控制器監(jiān)測(cè) 設(shè)備的狀態(tài)和調(diào)節(jié)物料的運(yùn)送，以使得能在適當(dāng)?shù)?時(shí)間將適當(dāng)?shù)奈锪纤偷竭m當(dāng)?shù)牡攸c(diǎn)。
             本文論述在FMS中，如何以最有效的方式在 調(diào)節(jié)時(shí)間間隔內(nèi)處理同時(shí)發(fā)生的多個(gè)請(qǐng)求AGV運(yùn) 送的情況。探討了AGV路徑規(guī)劃和分配問題，提出 了相應(yīng)數(shù)學(xué)模型，提供了自組織神經(jīng)網(wǎng)絡(luò)解決方案 的算法。
1、一般FMS的物流情況 
             對(duì)于一般FMS而言，每臺(tái)機(jī)床都是通用的，可實(shí)施多種操作。現(xiàn)場(chǎng)備有一個(gè)儲(chǔ)備庫，在線工件(Work—In—Process WIP)需由 AGV從儲(chǔ)備庫運(yùn)送到機(jī)床。與每臺(tái)機(jī)床相連的是輸入緩沖站(1nput Buffer IB)和輸出緩沖站(OutputBuffer OB)。當(dāng)一項(xiàng)操作完成之后，機(jī)床會(huì)自動(dòng)地將WIP卸載到OB 并發(fā)出運(yùn)走請(qǐng)求。WIP一直等在OB上直到AGV 來拾取為止。由于緩沖站容量有限，一臺(tái)機(jī)床可能出現(xiàn)“撐死”或“饑餓”現(xiàn)象。“撐死”發(fā)生在一臺(tái)機(jī)床要 卸載剛完成的WIP到已經(jīng)飽和的OB上時(shí)，此時(shí)，該機(jī)床發(fā)出緊急運(yùn)走請(qǐng)求。相應(yīng)地，“饑餓”則發(fā)生在一臺(tái)機(jī)床從已經(jīng)空了的IB上取下一個(gè)加工工件時(shí)，此時(shí)，該機(jī)床發(fā)出緊急運(yùn)來請(qǐng)求。緊急運(yùn)走請(qǐng)求也會(huì) 發(fā)生在當(dāng)儲(chǔ)備庫中的WIP已到了該對(duì)其實(shí)施操作時(shí)。
              除了緊急運(yùn)走、緊急運(yùn)來請(qǐng)求外，WIP運(yùn)送請(qǐng) 求還包括一般運(yùn)走與運(yùn)來請(qǐng)求。當(dāng)任何一臺(tái)機(jī)床其 IB空了時(shí)，則發(fā)出運(yùn)來請(qǐng)求，當(dāng)一工件從儲(chǔ)備庫或上位機(jī)床運(yùn)來并傳送到IB上后，該運(yùn)來請(qǐng)求就被滿 足了。而運(yùn)走請(qǐng)求的滿足是在從OB運(yùn)走了WIP之后。
2、AGV路徑規(guī)劃和分配問題
2.1、問題的特征及解決方法 
                每一個(gè)AGV運(yùn)送請(qǐng)求都涉及到兩個(gè)任務(wù)，即從一起始點(diǎn)拾取WIP，將其運(yùn)送至一預(yù)先確定的送達(dá)點(diǎn)卸下。任務(wù)優(yōu)先關(guān)系要求先拾取后運(yùn)送WIP，而拾取運(yùn)送任務(wù)必須由同一臺(tái)AGV完成。在本研究背景下，一臺(tái)AGV一次只承載一個(gè)單位負(fù)荷，所謂一個(gè)單位負(fù)荷是指作為一個(gè)整體被夾持和傳輸?shù)墓ぜ�的集合。例如，一個(gè)裝有幾個(gè)工件的托盤[1]。因此，AGV在載有一個(gè)單位負(fù)荷去送達(dá)點(diǎn)途中再拾取另一個(gè)WIP是不允許的。
                與傳統(tǒng)的執(zhí)行單一運(yùn)送請(qǐng)求而尋找最短路線的AGV規(guī)劃問題不同[2]，本研究尋找最短路徑涉及到的是執(zhí)行多項(xiàng)運(yùn)送請(qǐng)求而不是一項(xiàng)。由于在自由分布AGV環(huán)境下，起始點(diǎn)到送達(dá)點(diǎn)間的最短路線變?yōu)闅W氏距離。因此傳統(tǒng)的方法不再適用，本研究致力于用神經(jīng)網(wǎng)絡(luò)方法來解決問題。
以下先闡述所開發(fā)系統(tǒng)的特點(diǎn)：
(1)系統(tǒng)每接受到一個(gè)運(yùn)送請(qǐng)求時(shí)，都會(huì)進(jìn)行規(guī)劃演算，立即分配一項(xiàng)AGV任務(wù)，以達(dá)到實(shí)時(shí)性要求；
(2)進(jìn)行規(guī)劃演算時(shí)，將所有新的運(yùn)送請(qǐng)求和所有系統(tǒng)內(nèi)還未被AGV拾取的WIP一起考慮，重新進(jìn)行規(guī)劃。一般情況下，按先申請(qǐng)先享受服務(wù)的規(guī)劃 處理優(yōu)先次序。但也考慮根據(jù)當(dāng)前系統(tǒng)狀態(tài)，原先的一般請(qǐng)求可能變成緊急請(qǐng)求，而緊急請(qǐng)求具有高優(yōu)先權(quán)；
(3)由于存在機(jī)床輸入和輸出緩沖站，并無必要在發(fā)出一般運(yùn)送請(qǐng)求后立即將WIP運(yùn)走。當(dāng)一般運(yùn)送請(qǐng)求發(fā)出時(shí)機(jī)床正在忙于下一工件的加工，因此，即使規(guī)劃演算開始于運(yùn)送請(qǐng)求產(chǎn)生之后，機(jī)床的利用率并沒有受影響。
除以上所述之外，還有其他一些AGV系統(tǒng)問題需要解決。其中最重要的是車間內(nèi)的交通管理問 題。當(dāng)無人駕駛小車遇到障礙物時(shí)需要避讓，當(dāng)小車之間發(fā)生路線沖突時(shí)，需要沖突解決方法。通常設(shè)計(jì)一些控制區(qū)或緩沖區(qū)用于發(fā)生沖突時(shí)讓小車暫時(shí)避讓。為避免交通堵塞和小車干涉，文獻(xiàn)[2]提出了一些沖突解決方法，有幾何方法，if—then—else產(chǎn)生式 規(guī)則方法以及先到先服務(wù)規(guī)則(thefirst—comefirst— serve rule)方法。在本研究的自由分布AGV系統(tǒng)中，目標(biāo)之一是確定每臺(tái)AGV的最短路徑。當(dāng)運(yùn)行 在該路徑上的AGV發(fā)生交通沖突時(shí)，應(yīng)用先到先服務(wù)規(guī)則。
2.2 數(shù)學(xué)模型
                首先將AGV從起始點(diǎn)拾取工件運(yùn)送到送達(dá)點(diǎn)卸下工件定義為一項(xiàng)任務(wù)(Job)，則產(chǎn)生如下數(shù)學(xué)符號(hào)含義：
N——所涉及到的任務(wù)數(shù)目
di——任務(wù)i的起始點(diǎn)至送達(dá)點(diǎn)間的距離
dij——任務(wù)i的送達(dá)點(diǎn)至任務(wù)j的起始點(diǎn)間的距離
xij——當(dāng)任務(wù)j在任務(wù)i完成后被立即執(zhí)行時(shí)為1，否則為0
U——不包括任務(wù)全集和單一任務(wù)子集的任務(wù)子集 
             約束條件(1)意味著在任務(wù)i之后立即執(zhí)行的只有一項(xiàng)任務(wù)。約束條件(2)表明緊接任務(wù)J．之前僅有一項(xiàng)任務(wù)。約束條件(3)限制一些子路徑：若任務(wù)j出現(xiàn)在任務(wù)i之后，那么禁止任務(wù)i在任務(wù)j之后。
                本研究采用被廣泛引用的自組織神經(jīng)網(wǎng)絡(luò)Ko honen網(wǎng)絡(luò)[3]。Kohonen網(wǎng)絡(luò)方法計(jì)算效率高并具有適應(yīng)不同情況的柔性，比如，上述數(shù)學(xué)模型僅適用于單一小車情況。當(dāng)涉及多個(gè)小車時(shí)，Kohonen網(wǎng)絡(luò)方法也能夠提供綜合分配和路徑規(guī)劃的復(fù)雜模型。
3 AGV路徑規(guī)劃問題的Kohonen自組織神經(jīng)網(wǎng)絡(luò)
                在AGV規(guī)劃問題中，將要執(zhí)行的任務(wù)數(shù)目從1 計(jì)到N，即J1，J2，…，JN。每一個(gè)任務(wù)J由一對(duì)坐標(biāo) 表示，對(duì)應(yīng)于任務(wù)J的起始點(diǎn) 和送達(dá)點(diǎn)的坐標(biāo)。任務(wù)集中的一個(gè)排列可被看成為一組具體的拾取與送達(dá)任務(wù)指令。排列的目標(biāo)是找 到最短的行駛距離。
                假設(shè)σ＝{1，2，…，N}為任務(wù)所涉及機(jī)床固定 位置的固定編號(hào)集，則路徑規(guī)劃任務(wù)就是給σ集中的每一位置分配唯一的一項(xiàng)任務(wù)i，并使得總的行駛距離最小。換句話說，在滿足最優(yōu)路徑?jīng)Q策的條件下，需要建立任務(wù)集(J1，J2，…，JN}與位置集σ＝ {1，2，…，N}間的一對(duì)一映射。運(yùn)送任務(wù)所對(duì)應(yīng)的起始點(diǎn)和送達(dá)點(diǎn)的坐標(biāo)是引導(dǎo)網(wǎng)絡(luò)學(xué)習(xí)的輸入樣本。當(dāng)一輸入樣本存在時(shí)，與該 輸入樣本對(duì)應(yīng)的最小距離輸出節(jié)點(diǎn)(獲勝節(jié)點(diǎn))，既全部輸出元素中對(duì)應(yīng)距離最短之元素被允許建立該輸入樣本的權(quán)重，同時(shí)在輸出層中的相鄰節(jié)點(diǎn)也建立該輸入樣本的較低權(quán)重。這樣做的目的是使得獲 節(jié)點(diǎn)處的相鄰節(jié)點(diǎn)在相同輸入樣本再次出現(xiàn)時(shí)也具有相類似反映。由于相鄰節(jié)點(diǎn)間的相互位置關(guān)系導(dǎo)致兩相鄰節(jié)點(diǎn)間距離最小，因而產(chǎn)生最短路徑。通過權(quán)重調(diào)節(jié)減低鄰域的長(zhǎng)度，輸出節(jié)點(diǎn)相互間將變得越來越獨(dú)立，最終使得每一輸出節(jié)點(diǎn)被分配一個(gè)運(yùn)送請(qǐng)求。
                在實(shí)際網(wǎng)絡(luò)訓(xùn)練開始時(shí)，在輸出層并不存在輸 出節(jié)點(diǎn)，節(jié)點(diǎn)的數(shù)目按節(jié)點(diǎn)插入不斷增加，節(jié)點(diǎn)插入 過程對(duì)于改善網(wǎng)絡(luò)訓(xùn)練速度和處理緊急請(qǐng)求以及多臺(tái)小車情況是很有用的。
3.1 單一AGV路徑規(guī)劃算法
                在以上所描述的算法中，在給定一個(gè)完整的任務(wù)集J1，J1，…JN的基礎(chǔ)上，如果在同一次迭代中，有兩個(gè)不同的任務(wù)都選擇同一節(jié)點(diǎn)作為獲勝點(diǎn)，則該節(jié)點(diǎn)被復(fù)制，新建立起的節(jié)點(diǎn)以相同的權(quán)重被插在輸出層獲勝點(diǎn)相鄰的左或右邊。如果在3次迭代中一個(gè)節(jié)點(diǎn)都沒有被選中為任何運(yùn)送任務(wù)的獲勝點(diǎn)，則該節(jié)點(diǎn)被刪除。
3.2 多臺(tái)AGV路徑規(guī)劃和分配問題
             當(dāng)涉及到多臺(tái)AGV時(shí)，系統(tǒng)需要保證每臺(tái) AGV都以最短運(yùn)行距離分配到任務(wù)，以使得每個(gè)物 料輸送系統(tǒng)的性能最優(yōu)化。算法的基本原理一是平 衡多臺(tái) AGV的工作負(fù)荷，二是使所有被分配的 AGV的總運(yùn)行距離最短。以下描述建立在Koho— nen自組織特征映射[3]基礎(chǔ)上的適用于多臺(tái) AGV 情況的算法。
算法2
第1步：應(yīng)用算法1，在已給任務(wù)集基礎(chǔ)上獲得 單一路徑規(guī)劃結(jié)果。
第2步：令為當(dāng)前AGV位置坐標(biāo)(s＝l，2，…，M)，d1為所有送運(yùn)任務(wù)應(yīng)當(dāng)完成的時(shí)間界 限，分組匯集運(yùn)送任務(wù)(保留路徑規(guī)劃次序)，使得每 組任務(wù)都能在時(shí)間界限d1之前完成，轉(zhuǎn)到第3步。
第3步：若在第2步中的任務(wù)組數(shù)小于等于M， 則對(duì)于每一任務(wù)組分配一臺(tái)距離組中第一節(jié)點(diǎn)位置 最近的AGV，讓其完成該組的所有運(yùn)送任務(wù)；若任 務(wù)組數(shù)大于M(意味著AGV臺(tái)數(shù)不足夠)，則對(duì)每 一前M個(gè)組分配距離最近的的AGV前往。 在算法2 中還可以使用不同的策略。如不以時(shí) 間界限d1作為分組指標(biāo)，可采用其他指標(biāo)來分 組。再如當(dāng)任務(wù)組數(shù)大于從時(shí)，可讓 AGV在超過 時(shí)間界限眾1之后繼續(xù)任務(wù)直到完成。策略的選擇應(yīng) 基于系統(tǒng)的條件以及其操作成本的大小。
4 結(jié)束語
                由于AGV路徑規(guī)劃和分配問題在整個(gè)FMS 運(yùn)行中需反復(fù)被解決，所以有效的解決方法是很重要的。本文分析了一般FMS物流情況，研討了自由分布式AGV規(guī)劃問題的特征及相應(yīng)對(duì)策，并提出相應(yīng)的數(shù)學(xué)模型，闡述了在FMS環(huán)境下AGV的分配與路徑規(guī)劃問題的Kohonen自組織神經(jīng)網(wǎng)絡(luò)解 決方案的算法。這一算法和相應(yīng)的數(shù)學(xué)模型已應(yīng)用于一有兩臺(tái)AGV的FMS的實(shí)際運(yùn)行中，目前運(yùn)行情況良好。