張祥祥 楊智飛 胡祥濤 蘇春

一、引言

物流系統(tǒng)的效率及其作業(yè)質(zhì)量關(guān)系到智能制造車間的生產(chǎn)成本和經(jīng)濟(jì)效益。利用智能化導(dǎo)航裝置和自動化的裝卸機(jī)構(gòu)，自動導(dǎo)引車（Automated Guided Vehicle，AGV）可以實(shí)現(xiàn)物品搬運(yùn)和裝卸過程的自動化。目前，AGV在自動化倉儲、物流搬運(yùn)系統(tǒng)以及智能制造系統(tǒng)等領(lǐng)域得到廣泛應(yīng)用。

為滿足智能化生產(chǎn)車間的作業(yè)需求，近年來由多輛AGV構(gòu)成的集群式AGV系統(tǒng)（以下簡稱AGVs）成為AGV研究和工程應(yīng)用的熱點(diǎn)領(lǐng)域，主要內(nèi)容包括：

多調(diào)度任務(wù)的協(xié)調(diào)機(jī)制研究。研究提高AGVs響應(yīng)和工作效率的有效方法，保證物料的高效流動和準(zhǔn)時(shí)化（JustInTime，JIT）供應(yīng)。

AGVs無沖突運(yùn)行機(jī)理研究。根據(jù)生產(chǎn)需求，制定調(diào)度策略和路徑規(guī)劃，實(shí)現(xiàn)AGVs的無沖突高效運(yùn)行，避免碰撞和死鎖等現(xiàn)象。

AGVs再調(diào)度問題研究。當(dāng)系統(tǒng)發(fā)生突發(fā)情況、設(shè)備發(fā)生故障、接收緊急訂單或插單生產(chǎn)時(shí)，需要結(jié)束原先的計(jì)劃和任務(wù)，快速、重新完成AGVs調(diào)度策略的制定及其路徑規(guī)劃。

上述問題栢互作用、相互影響，極大地增加了問題求解的難度。

目前，在靜態(tài)路徑規(guī)劃和預(yù)先的任務(wù)分配領(lǐng)域，通常以時(shí)間最少、路徑最短或能耗最低等為目標(biāo)，采用整數(shù)規(guī)劃、動態(tài)規(guī)劃以及啟發(fā)式算法等方法，得到AGV調(diào)度問題的最優(yōu)解。但是，隨著研究規(guī)模的擴(kuò)大和約束條件的增加，已有算法的適應(yīng)性降低。Rashidi等針對集裝箱碼頭AGV調(diào)度問題，建立最小費(fèi)用流模型，采用擴(kuò)展標(biāo)準(zhǔn)網(wǎng)絡(luò)單純形法求解模型。NiShi等針對制造系統(tǒng)中AGVs調(diào)度和無碰撞問題，以總體任務(wù)權(quán)重最小化為目標(biāo)，建立AGVs調(diào)度模型，提出一種兩級分解算法。Reddy等利用進(jìn)化算法解決柔性制造環(huán)境下多目標(biāo)調(diào)度問題，同時(shí)考慮機(jī)器和車輛調(diào)度，以最小化完工時(shí)間、平均流時(shí)間以及平均延期時(shí)間為優(yōu)化目標(biāo)。Mohammed等提出同時(shí)考慮無沖突路徑和作業(yè)車間調(diào)度問題的兩階段蟻群算法，以最小完成時(shí)間為目標(biāo)，通過仿真驗(yàn)證ACA算法的有效性。雷定猷等分析多機(jī)多請求的AGVs調(diào)度問題，以最小化總路徑長度為目標(biāo)，考慮不同任務(wù)優(yōu)先級，提出基于混合遺傳算法的調(diào)度模型。

早期的路徑規(guī)劃問題要求AGV沿固定路徑運(yùn)動，實(shí)現(xiàn)難度較低，但是對環(huán)境的適應(yīng)能力差。隨著智能制造的興起，對AGV智能化提出了更高要求，智能制造車間中AGV的路徑規(guī)劃和任務(wù)調(diào)度緊密結(jié)合，需要精確控制AGV的行駛時(shí)間、等待時(shí)間和?？课恢玫取３Ｓ玫穆窂揭?guī)劃方法包括運(yùn)籌學(xué)方法、啟發(fā)式算法等。Savelsbergh等利用分支定界法實(shí)現(xiàn)實(shí)現(xiàn)車輛路徑的動態(tài)規(guī)劃。Gans等將無沖突路徑規(guī)劃問題定義為一個(gè)經(jīng)典的集合覆蓋問題，以路徑堵塞程度作為評價(jià)指標(biāo)。將時(shí)間窗算法應(yīng)用于AGV路徑規(guī)劃問題中，以提高路徑利用率、避免AGV之間的沖突。

綜上所述，至今尚未形成AGVs調(diào)度的有效方法體系，理論研究與工程應(yīng)用之間還存在著較大差距。本文結(jié)合某汽車倒車?yán)走_(dá)裝配生產(chǎn)線智能調(diào)度項(xiàng)目，以智能生產(chǎn)車間AGV調(diào)度系統(tǒng)設(shè)計(jì)為目標(biāo)，在分析該制造系統(tǒng)結(jié)構(gòu)組成和工作原理的基礎(chǔ)上，提出改進(jìn)遺傳算法，并將Dijkstra算法、時(shí)間窗算法等啟發(fā)式算法嵌入到遺傳算法中，實(shí)現(xiàn)AGV無沖突運(yùn)行和AGV最大配送時(shí)間的最小化。

二、智能生產(chǎn)車間和AGV運(yùn)行環(huán)境

1、智能生產(chǎn)車間結(jié)構(gòu)組成與功能

某車載雷達(dá)生產(chǎn)車間總體布局如圖1所示。該車間為無人化智能生產(chǎn)車間，其配送模式選自動化物流系統(tǒng)。因此，物料的高效流動可以有效提高生產(chǎn)系統(tǒng)的效率。對于AGV調(diào)度系統(tǒng)，如何為AGV分配運(yùn)輸任務(wù)，并為其安排好執(zhí)行裝卸操作的具體順序和路徑，是本文的研究重點(diǎn)。

AGV運(yùn)行區(qū)域包括物料柜區(qū)域和生產(chǎn)車間。生產(chǎn)車間內(nèi)包括a、b、…、p共16條產(chǎn)線。AGV運(yùn)行軌道由9條環(huán)線組成，包括一條的主軌道以及8條運(yùn)行于產(chǎn)線上方的子軌道。主軌道用于往返于物料柜與生產(chǎn)車間，AGV可通過主軌道前往物料柜取料或完成取料后前往車間上料，當(dāng)AGV到達(dá)上料任務(wù)指定位置時(shí)，可通過岔撥機(jī)構(gòu)從主軌道轉(zhuǎn)移到該任務(wù)對應(yīng)產(chǎn)線上方的子軌道，當(dāng)?shù)竭_(dá)任務(wù)目的地時(shí)，下降至產(chǎn)線旁進(jìn)行卸料。完成任務(wù)后，AGV返回主軌道在軌道上合適位置等待下個(gè)任務(wù)。主軌道上包含一個(gè)上料點(diǎn)0，用于AGV下降至物料柜完成取料，每條子軌道上含有兩個(gè)卸料點(diǎn)，每個(gè)卸料點(diǎn)對應(yīng)一條產(chǎn)線。

2、AGV調(diào)度優(yōu)化模型

AGV調(diào)度的目標(biāo)對運(yùn)輸任務(wù)和不同AGV小車進(jìn)行排序，確定合理的任務(wù)分配方案，實(shí)現(xiàn)運(yùn)輸任務(wù)和車輛之間的最佳匹配，提升系統(tǒng)整體效率、降低運(yùn)行成本。本研究中，AGV調(diào)度的任務(wù)如下：在物流運(yùn)輸系統(tǒng)中，有n輛AGV、m個(gè)待執(zhí)行任務(wù)、若干個(gè)工作站點(diǎn)和物料倉庫站點(diǎn)，通過合理地分配運(yùn)輸任務(wù)、AGV數(shù)量及其工作任務(wù)，在運(yùn)行路徑、運(yùn)行時(shí)間和車輛性能受限的條件下，滿足指定的調(diào)度指標(biāo)和車間生產(chǎn)需求。

對于n×m的車輛調(diào)度問題中，本算法以最大配送時(shí)間的最小化作為優(yōu)化目標(biāo)，目標(biāo)函數(shù)可以表示為：

式中X_{i，j，k}為0-1變量，當(dāng)?shù)趇輛AGV的第j個(gè)任務(wù)編號為k時(shí)值為1，否則為0;T_i，j表示第i輛AGV執(zhí)行第j號任務(wù)所需時(shí)間。

約束條件如下：

（]）每輛AGV的同一時(shí)間只執(zhí)行一個(gè)任務(wù)：

（2）每個(gè)任務(wù)有且只有一輛AGV來完成：

（3）全部任務(wù)均需被完成：

3、路徑規(guī)劃

任務(wù)分配是AGV調(diào)度算法的核心，其作用在于確定分配方案，實(shí)現(xiàn)運(yùn)輸任務(wù)和車輛之間的最佳匹配。此外，在任務(wù)調(diào)度的基礎(chǔ)上完成路徑規(guī)劃，為每一輛AGV分配一條無沖突路徑，以提升系統(tǒng)運(yùn)作效率。多輛AGV（AGVs）路徑規(guī)劃是AGV調(diào)度算法另一個(gè)研究重點(diǎn)，其目的是在保證系統(tǒng)無沖突運(yùn)行的情況下，為每輛AGV規(guī)劃出一條無碰撞且性能指標(biāo)最優(yōu)的路徑。

為提高貨物運(yùn)送效率，AGV占用公用道路不可避免。因此，研究避碰問題具有重要意義。本文中，AGV運(yùn)行軌道均為單道單向軌道，并且當(dāng)前序AGV在取料點(diǎn)、卸料點(diǎn)或岔道位買執(zhí)行動作時(shí)，后序AGV需要等待其完成操作。因此，根據(jù)地圖建模和AGV執(zhí)行任務(wù)的狀況，AGVs中存在的沖突主要包括兩種類型，即路口沖突和趕超沖突，如圖2所示。

解決上述沖突的常用方法包括：

路徑鋪設(shè)法通過設(shè)置主副車道和若干規(guī)則避碰，算法簡單穩(wěn)定，但不具備通用型。

交通規(guī)則法根據(jù)系統(tǒng)需求確定AGV任務(wù)優(yōu)先級，以盡可能全面的規(guī)則指導(dǎo)AGV運(yùn)動。例如：等待策略可以很好地解決路口沖突問題。

單向圖方法：為拓?fù)渲兴新范我?guī)定運(yùn)行方向，其效率取決于路徑規(guī)劃是否合理，搜索出優(yōu)化路徑可能存在轉(zhuǎn)彎頻繁等現(xiàn)象。

重新規(guī)劃路徑法：若所設(shè)置的沖突路段不可用，則從AGV當(dāng)前位置的下一節(jié)點(diǎn)重新規(guī)劃路徑以避免沖突。

預(yù)測式避碰：AGV規(guī)劃好最優(yōu)路徑，預(yù)測AGV之間路徑是否會發(fā)生沖突，通過合適的沖突檢測和沖突消除方法，完成系統(tǒng)運(yùn)行優(yōu)化。

Rajotia等提出一種半動態(tài)時(shí)間窗約束的路徑規(guī)劃策略，使用保留時(shí)間窗和自由時(shí)間窗來管理車輛的運(yùn)動，并采用Dijkstra算法為AGV找到最短路徑。基于時(shí)間窗的方法可以有效避免AGV因競爭同一任務(wù)而引起的并發(fā)操作，廣泛應(yīng)用于AGV沖突的規(guī)避問題。

本文采用改進(jìn)型遺傳算法實(shí)現(xiàn)AGV調(diào)度系統(tǒng)任務(wù)分配，設(shè)計(jì)滿足約束條件的編碼規(guī)則和符合優(yōu)化目標(biāo)的適應(yīng)度評價(jià)函數(shù)，利用遺傳算法優(yōu)勝劣汰的特性，決定最優(yōu)調(diào)度方案。采用與Dijkstra算法相結(jié)合的時(shí)間窗算法完成AGVs路徑規(guī)劃，為每輛AGV規(guī)劃提供最優(yōu)路徑，同時(shí)保證系統(tǒng)的無沖突運(yùn)行。

三、改進(jìn)遺傳算法設(shè)計(jì)

分析系統(tǒng)模型特征和AGVs調(diào)度的功能需求，可以將上述問題轉(zhuǎn)換為多個(gè)子系統(tǒng)獨(dú)立的優(yōu)化問題，并在此基礎(chǔ)上完成系統(tǒng)級綜合協(xié)調(diào)。首先，將AGV調(diào)度任務(wù)分解為任務(wù)調(diào)度和路徑規(guī)劃兩個(gè)功能子系統(tǒng);采用兩階段控制策略，即離線生成路徑庫、基于時(shí)間窗算法完成在線路徑規(guī)劃，以實(shí)現(xiàn)避碰。兩階段調(diào)度的求解框架如圖3所示。

離線階段生成路徑庫，利用圖論中單AGV路徑規(guī)劃方法，采用Dijkstra算法求取最短路徑，并基于Dijkstra算法提出生成包含最短路徑和次短路徑的最短路徑庫，有效避免隨機(jī)生成解質(zhì)量不高的現(xiàn)象。在線階段的規(guī)劃路徑考慮交通規(guī)則法、預(yù)測式避碰方法控制系統(tǒng)中各節(jié)點(diǎn)、AGV通過時(shí)間等因素，基于運(yùn)行時(shí)間、停車次數(shù)、等待時(shí)間等約束條件，利用遺傳算法優(yōu)化路徑選擇方案，解決AGVs的靜態(tài)車間調(diào)度問題。

1、任務(wù)調(diào)度

當(dāng)用戶完成向系統(tǒng)中輸入生產(chǎn)計(jì)劃后，首先基于生產(chǎn)能力和物料供應(yīng)能力，考慮生產(chǎn)現(xiàn)場的信息反饋，將生產(chǎn)計(jì)劃動態(tài)地分解成滾動作業(yè)計(jì)劃。在生產(chǎn)計(jì)劃分解的基礎(chǔ)上，輸出短期需AGV執(zhí)行的任務(wù)，并將其傳遞給任務(wù)調(diào)度模塊。本任務(wù)調(diào)度模塊采用改進(jìn)型遺傳算法實(shí)現(xiàn)AGV任務(wù)分配以及AGV運(yùn)行路徑的組合優(yōu)化。任務(wù)調(diào)度模塊流程如圖4所示。

（1）基因編碼

在設(shè)計(jì)遺傳算法編碼時(shí)，需要考慮基因的完備性、健全性和非冗余性。多AGV調(diào)度系統(tǒng)中基因?yàn)锳GV編號信息。因此，本算法采用實(shí)數(shù)編碼方式，以便于解碼操作和基因操作。編碼長度由任務(wù)數(shù)量M決定，染色體生產(chǎn)中每條染色體長度均為M。初始化時(shí)在染色體每個(gè)基因位上設(shè)置為[1，N]（N為AGV數(shù)量）的隨機(jī)數(shù)，代表AGV編號。

（2）種群初始化

種群規(guī)模過小，可能會導(dǎo)致所包含的信息不充分，容易使算法產(chǎn)生局部收斂;種群規(guī)模過大，計(jì)算量過大，降低算法的效率。本算法設(shè)置初始種群為100個(gè)個(gè)體。

（3）適應(yīng)度函數(shù)設(shè)計(jì)

對于給定的調(diào)度方案，采用Dijkstra算法離線計(jì)算每輛AGV完成任務(wù)所需遍歷的節(jié)點(diǎn)，得到AGV的運(yùn)行路徑。采用AGV時(shí)間窗、節(jié)點(diǎn)時(shí)間窗和路段時(shí)間窗多時(shí)間窗的概念，計(jì)算多AGVs在給定路徑下完成調(diào)度任務(wù)需要的運(yùn)行時(shí)間。

2、路徑規(guī)劃

AGVs發(fā)生碰撞的原因有兩種，即節(jié)點(diǎn)沖突和路段沖突。沖突的表現(xiàn)形式包括相向沖突和追及沖突。本研究中AGV速度為定值，因此系統(tǒng)僅存在相向沖突。此外，為保證AGV正常運(yùn)行，本文通過設(shè)定時(shí)間窗保證AGV之間有一定的安全距離，通過預(yù)測AGV行駛的位置和交通規(guī)則避免發(fā)生節(jié)點(diǎn)沖突和路段沖突。具體流程如圖5所示。

路徑規(guī)劃的核心內(nèi)容包括：

（1）利用Dijkstra算法生成AGV運(yùn)行狀態(tài)時(shí)間窗，即無節(jié)點(diǎn)和路段阻礙情況下AGV調(diào)度方案中節(jié)點(diǎn)、路段的時(shí)間窗，包括占用節(jié)點(diǎn)、路段AGV編號、起始時(shí)間和結(jié)束時(shí)間和時(shí)間窗長度等信息。

（2）通過生成節(jié)點(diǎn)時(shí)間窗，防止AGV在節(jié)點(diǎn)時(shí)間窗產(chǎn)生重疊的方式避免節(jié)點(diǎn)沖突的發(fā)生，包括相向沖突和十字交叉節(jié)點(diǎn)沖突。在節(jié)點(diǎn)時(shí)間線上標(biāo)注每個(gè)AGV在該節(jié)點(diǎn)上占用的時(shí)間窗，并對節(jié)點(diǎn)上各AGV的時(shí)間窗按時(shí)間線進(jìn)行排序。

（3）本算法設(shè)定AGV為勻速來避免發(fā)生追及沖突;通過生成路段時(shí)間窗，防止AGV在路段時(shí)間窗產(chǎn)生重疊的方式避免路段相向沖突的發(fā)生。

四、案例分析

基于圖1所示的智能生產(chǎn)車間，配送任務(wù)如表所列。其中，終點(diǎn)表示該任務(wù)由AGV配送原材料至對應(yīng)編號的產(chǎn)線加工;產(chǎn)線生產(chǎn)節(jié)拍為30min;原材料由三輛AGV完成配送，AGV每次運(yùn)載的各類產(chǎn)品原材料數(shù)量均為5套;AGV運(yùn)行速度為0.5m/s，AGV上料、卸料耗時(shí)10s;每輛AGV起始站點(diǎn)均為O號站點(diǎn).

由圖6可知，各AGV完成相應(yīng)任務(wù)的耗時(shí)相近。這是由于本研究中的車間布局為距離相近的環(huán)線，并且假設(shè)總路徑長度和裝卸時(shí)間相同，在AGV無沖突運(yùn)行的理想狀態(tài)下AGV完成各任務(wù)耗時(shí)應(yīng)相等。因此，本文所設(shè)計(jì)的調(diào)度方案可以將系統(tǒng)中多AGV沖突的影響降低至最小，實(shí)現(xiàn)AGV平準(zhǔn)化配送.

圖7所示調(diào)度算法最優(yōu)解收斂圖。由圖7可知，利用遺傳算法可以實(shí)現(xiàn)調(diào)度方案的優(yōu)化。與初始的隨機(jī)分配方案相比，最終的優(yōu)化調(diào)度方案可以節(jié)省配送時(shí)間約24.35%。此外，本算法最優(yōu)值出現(xiàn)在80代左右，獲得最優(yōu)解的計(jì)算時(shí)間約為48s，收斂速度較決，能夠滿足生產(chǎn)實(shí)際對AGVs的調(diào)度要求。

五、結(jié)論

遺傳算法具有隱含并行性、全局搜索能力和較強(qiáng)的魯棒性，對問題的依賴性小，適合作為AGVs調(diào)度算法的主體。本文將多AGV調(diào)度系統(tǒng)分解為三個(gè)功能子系統(tǒng)，將遺傳算法的全局搜索能力與時(shí)間窗算法的預(yù)測規(guī)避沖突能力有機(jī)結(jié)合，構(gòu)造出改進(jìn)遺傳算法，并應(yīng)用于汽車倒車?yán)走_(dá)智能生產(chǎn)車間AGVs的調(diào)度問題中，獲得了較優(yōu)的調(diào)度方案，驗(yàn)證了算法的有效性。后續(xù)將進(jìn)一步完善調(diào)度模型，豐富訂單信息，考慮插單生產(chǎn)和AGV充電過程等因素對生產(chǎn)的影響，以便更加準(zhǔn)確地反映此類系統(tǒng)對AGV的工程需求。