1 引言
自動(dòng)化技術(shù)的快速發(fā)展，推動(dòng)了自動(dòng)導(dǎo)引車（automated guided vehicle，AGV）在制造業(yè)物流、電商物流等行業(yè)的大范圍應(yīng)用，并成為企業(yè)提高物流運(yùn)作效率的主要手段。以近年來蓬勃發(fā)展的電商物流為例，不少企業(yè)在揀貨環(huán)節(jié)大量引入AGV，來提升作業(yè)速度和準(zhǔn)確性，滿足客戶對(duì)時(shí)效性的要求。例如，亞馬遜引入Kiva 機(jī)器人系統(tǒng)，將訂單揀選時(shí)間由1 小時(shí)縮短至15 分鐘，效率提升4 倍左右。
倉庫的自動(dòng)化升級(jí)，使倉庫管理由“人管人”的傳統(tǒng)模式轉(zhuǎn)變?yōu)椤跋到y(tǒng)集中調(diào)度所有AGV”的自動(dòng)化模式。類似的模式也普遍存在于半導(dǎo)體等制造工廠、港口碼頭、機(jī)場(chǎng)、危險(xiǎn)品運(yùn)輸?shù)刃袠I(yè)。在該模式下，AGV 在線調(diào)度問題可定義為多AGV 的多周期循環(huán)任務(wù)指派和全局無碰撞路徑規(guī)劃。以電商倉庫和制造工廠為例，該問題可具體描述為：給定一個(gè)封閉的自動(dòng)化物流場(chǎng)景，如電商倉庫中包括貨架、揀選臺(tái)、AGV 和導(dǎo)引道路等，制造工廠則包含多個(gè)工序的加工機(jī)臺(tái)、AGV 與導(dǎo)引道路。在特定時(shí)間周期內(nèi)，有一批貨物需要從起點(diǎn)運(yùn)輸?shù)街付ㄎ恢茫娚?/span>
倉庫中將商品從貨架運(yùn)輸至揀選臺(tái)，或制造工廠中完成物料在不同工序之間的周轉(zhuǎn)配送）。倉庫或工廠內(nèi)的所有AGV 由一套調(diào)度系統(tǒng)統(tǒng)一管控。當(dāng)系統(tǒng)接收運(yùn)輸任務(wù)后，必須在秒級(jí)時(shí)間單位內(nèi)為AGV迅速?zèng)Q策搬運(yùn)任務(wù)和行駛路徑，以在最短時(shí)間內(nèi)滿足所有任務(wù)的運(yùn)輸需求，且不允許發(fā)生碰撞等安全事故。AGV 按照系統(tǒng)指令行駛，直至下一周期，系統(tǒng)對(duì)空閑AGV 重新調(diào)度。循環(huán)上述過程，直至當(dāng)天任務(wù)結(jié)束。上述過程同時(shí)涉及任務(wù)指派和路徑規(guī)劃，因此，AGV 在線調(diào)度問題具有高度復(fù)雜性。
尤其近年來，越來越多的倉庫不斷增加AGV 數(shù)量，規(guī)模的擴(kuò)大進(jìn)一步提高了調(diào)度系統(tǒng)的控制難度［1］。如何在有限的路網(wǎng)資源及AGV 時(shí)變狀態(tài)等約束下，實(shí)現(xiàn)多AGV 在線調(diào)度系統(tǒng)安全高效地運(yùn)作，是當(dāng)前大規(guī)模發(fā)展智能倉庫亟待解決的重要難題。任務(wù)指派和路徑規(guī)劃均屬于典型的NP-hard問題［2］，現(xiàn)有研究通常聚焦于其中一個(gè)方面。針對(duì)AGV 任務(wù)指派問題，已有不少學(xué)者利用啟發(fā)式算法展開詳細(xì)討論。Xu 等［3］融合遺傳算法與蟻群算法，
對(duì)AGV 任務(wù)分配及執(zhí)行順序進(jìn)行研究。Polten 和Emde［4］利用混合整數(shù)線性規(guī)劃模型和大規(guī)模鄰域搜索算法，研究了窄通道倉庫中的AGV 任務(wù)分配問題。還有不少學(xué)者提出了多種基于啟發(fā)式規(guī)則的指派方法［5，6］。其中，先到先得和最短行程距離優(yōu)先是最常用的啟發(fā)式規(guī)則［7］。但是，這些文獻(xiàn)通常假設(shè)AGV 可以按照無碰撞的最短路徑行駛，并未考慮AGV 的實(shí)際路徑規(guī)劃和沖突情況。另一方面，AGV 的路徑規(guī)劃問題是考慮因素更多的封閉場(chǎng)景車輛路徑規(guī)劃問題，具有三個(gè)明顯區(qū)別于傳統(tǒng)車輛路徑問題的特征：（1）在自動(dòng)化倉庫中，路網(wǎng)環(huán)境
可看作柵格式，柵格間的距離按曼哈頓距離公式計(jì)算。（2）AGV 是全自動(dòng)設(shè)備，多輛AGV 同時(shí)調(diào)度，必須考慮車輛碰撞、路口死鎖等情況。（3）AGV 路徑規(guī)劃決策需要精確到每輛AGV 經(jīng)過的柵格、AGV至每個(gè)柵格的到達(dá)時(shí)間及避撞等待時(shí)間、取貨時(shí)間、運(yùn)輸任務(wù)完成時(shí)間等。由于AGV 無沖突路徑規(guī)劃問題求解難度較大，現(xiàn)有文獻(xiàn)多采用啟發(fā)式算法進(jìn)行研究。Fransen 等［8］基于頂點(diǎn)權(quán)重動(dòng)態(tài)變化的網(wǎng)格化路網(wǎng)模型，提出了一種多AGV 動(dòng)態(tài)路徑規(guī)劃方法。張丹露等［9］則設(shè)計(jì)了一種基于交通規(guī)則和預(yù)約表的改進(jìn)A*算法。同樣采用A*算法，融合時(shí)間窗與優(yōu)先級(jí)策略對(duì)算法進(jìn)行改進(jìn)，研究了AGV 動(dòng)態(tài)避撞路徑規(guī)劃問題。但在此類研究中，大多數(shù)文獻(xiàn)假設(shè)任務(wù)分配結(jié)果事先已知。綜上，現(xiàn)有關(guān)于AGV 調(diào)度問題的研究多側(cè)重于任務(wù)指派或路徑規(guī)劃等單個(gè)子問題，僅能實(shí)現(xiàn)調(diào)度系統(tǒng)的局部優(yōu)化，同時(shí)研究AGV 任務(wù)指派及路徑規(guī)劃協(xié)同調(diào)度的文獻(xiàn)較少。
在少數(shù)同時(shí)考慮多AGV 任務(wù)指派與路徑規(guī)劃問題的研究中，李昆鵬等［11，12］利用兩階段算法，研究了靜態(tài)路網(wǎng)中的AGV 任務(wù)分配和路徑規(guī)劃問題。Wang 和Zeng［13］用分支定界算法進(jìn)行AGV 的作業(yè)分配，并基于避撞規(guī)則設(shè)計(jì)啟發(fā)式算法生成AGV的無沖突路徑。但上述研究將任務(wù)指派與路徑規(guī)劃分割為兩個(gè)相對(duì)獨(dú)立的決策過程，仍然不能達(dá)到協(xié)同優(yōu)化的效果。同時(shí)，由于求解過程涉及精確算法，無法滿足在線調(diào)度的時(shí)間要求?；诖?，余娜娜等［14］利用一種集中與分散決策相結(jié)合的在線協(xié)同調(diào)度算法，針對(duì)動(dòng)態(tài)環(huán)境下多AGV 任務(wù)指派與路徑規(guī)劃協(xié)同優(yōu)化問題展開研究。該研究假設(shè)路網(wǎng)為單向?qū)б缆?，這種路網(wǎng)布局相對(duì)簡單可靠，卻增加了AGV 繞行距離，降低路網(wǎng)效率［15］。相較之下，雙向?qū)б肪W(wǎng)布局則能夠有效提供路網(wǎng)資源利用率［16］，但是需要考慮更復(fù)雜的沖突情況，增加了問題復(fù)雜度，有關(guān)研究較少。此外，AGV 剩余電量、訂單最佳服務(wù)時(shí)間窗等是影響倉庫揀選系統(tǒng)安全高效運(yùn)作，保障服務(wù)質(zhì)量，降低管理成本和AGV損耗的重要因素，卻鮮少有研究綜合考慮上述約束。同時(shí)，一般情況下，AGV 完成任務(wù)后，在未指派新任務(wù)前，需返回?？繀^(qū)等待下一任務(wù)或充電等。
而現(xiàn)有文獻(xiàn)只考慮AGV 從接收任務(wù)到完成任務(wù)的調(diào)度過程，忽略了完成任務(wù)后空載AGV 的返回路徑，無法實(shí)現(xiàn)AGV 的實(shí)時(shí)閉環(huán)管控。在研究方法上，由于AGV 的任務(wù)指派和路徑規(guī)劃都是NP-hard 問題，大多數(shù)學(xué)者更傾向于采用啟發(fā)式算法，通過比較不同啟發(fā)式算法的結(jié)果，驗(yàn)證算法優(yōu)劣性。但是，這種對(duì)比策略無法分析所提出的啟發(fā)式算法與最優(yōu)解的差距。因此，有必要建立可解的數(shù)學(xué)模型，設(shè)計(jì)精確算法為衡量啟發(fā)式算法的效果提供參考。
基于以上分析：
①不同于已有文獻(xiàn)僅側(cè)重于任務(wù)指派或路徑規(guī)劃等單個(gè)子問題，本文研究規(guī)則路網(wǎng)環(huán)境下的多AGV 任務(wù)指派與路徑規(guī)劃協(xié)同優(yōu)化問題。在數(shù)學(xué)建模中，同時(shí)進(jìn)行任務(wù)指派與路徑規(guī)劃決策，以實(shí)現(xiàn)倉庫的整體運(yùn)營優(yōu)化。②為更符合智能倉庫實(shí)際運(yùn)作情況，本文設(shè)置雙向?qū)б肪W(wǎng)布局，并綜合考慮AGV 電量約束和任務(wù)時(shí)間窗、無碰撞等特性。以智能倉庫某一周期內(nèi)的所有空載AGV 為研究對(duì)象，對(duì)“接收任務(wù)→取貨→送貨→返回?？繀^(qū)”的整個(gè)過程展開研究，以實(shí)現(xiàn)AGV 的在線周期循環(huán)調(diào)度。③為滿足實(shí)時(shí)調(diào)度的時(shí)間要求，本文設(shè)計(jì)了一套啟發(fā)式解決方案。同時(shí)，還提出了一種分支切割算法，為驗(yàn)證啟發(fā)式解決方案的質(zhì)量提供更緊下界。本文主要工作包括：①以單周期內(nèi)所有AGV 的總運(yùn)行時(shí)間和任務(wù)延遲的懲罰成本之和最小為目標(biāo)，建立了混合整數(shù)線性規(guī)劃數(shù)學(xué)模型。
②提出了多AGV 任務(wù)指派與路徑規(guī)劃協(xié)同優(yōu)化算法（multi-AGV task assignment and path plan?ning co-optimization algorithm， MA-TAPPCOA）。
考慮任務(wù)與AGV 雙重優(yōu)先規(guī)則設(shè)計(jì)任務(wù)指派算法，并設(shè)置AGV 優(yōu)先級(jí)規(guī)則和多車沖突避免策略。同時(shí)提出“ 考慮等待時(shí)間、考慮轉(zhuǎn)向代價(jià)、考慮重調(diào)度效率懲罰、考慮停靠區(qū)和貨架柵格回避系數(shù)、強(qiáng)化方向因子”5 種策略改進(jìn)傳統(tǒng)A*算法，為AGV 設(shè)計(jì)適應(yīng)全局路網(wǎng)環(huán)境的路徑方案。
③利用三類有效不等式并提出相應(yīng)的分離算法，設(shè)計(jì)出一種Branch-and-cut 算法，來提高模型求解下界。
④利用CPLEX、分支切割算法和MA-TA-PPCOA 進(jìn)行算例測(cè)試。結(jié)果表明：本文引入的分支切割算法能夠有效改善模型求解下界，提出的MA-TA-PPCOA算法能夠在極短時(shí)間內(nèi)，提供高質(zhì)量近似最優(yōu)解。通過進(jìn)一步分析實(shí)驗(yàn)結(jié)果，得出了一些關(guān)于AGV引進(jìn)數(shù)量和任務(wù)批次劃分方面的管理啟示。研究成果不僅能夠?yàn)橹悄軅}庫的管理與AGV 調(diào)度提供決策支持，還能拓展應(yīng)用到智能生產(chǎn)車間、自動(dòng)化碼頭等路網(wǎng)相對(duì)規(guī)則、自動(dòng)化程度較高的封閉場(chǎng)景中，為自動(dòng)化車輛的無碰撞動(dòng)態(tài)調(diào)度提供參考借鑒。沿柵格左右、前后移動(dòng)；②所有AGV 同質(zhì)且不考慮
剎車、啟動(dòng)過程；③ 在一個(gè)調(diào)度周期內(nèi)，一輛AGV最多被指派一項(xiàng)任務(wù)。
2 問題描述及數(shù)學(xué)建模
2.1 問題描述
本文研究智能倉庫中多AGV 任務(wù)指派與全局路徑規(guī)劃協(xié)同優(yōu)化問題。環(huán)境建模是研究該問題的基礎(chǔ)，考慮到在智能倉庫場(chǎng)景中，路網(wǎng)相對(duì)規(guī)則、可行區(qū)域與非可行區(qū)域劃分明確、運(yùn)輸任務(wù)的起止點(diǎn)及車輛位置精確度要求高，本文采取柵格法進(jìn)行路網(wǎng)環(huán)境建模。如圖1 所示，研究問題具體描述如下：給定一個(gè)封閉場(chǎng)景，場(chǎng)景路網(wǎng)可劃分為等大的正方形柵格?；疑珔^(qū)域表示貨架、揀選站臺(tái)及AGV?？繀^(qū)。設(shè)置雙向?qū)б缆?，?chǎng)景內(nèi)共有K 輛AGV，由調(diào)度平臺(tái)統(tǒng)一指揮。AGV 空載時(shí)可在任意柵格轉(zhuǎn)向、暫停、行駛，但負(fù)載時(shí)，只能在非貨架柵格活動(dòng)。在周期T-1 內(nèi)，不斷有訂單任務(wù)到達(dá)，訂單對(duì)應(yīng)的貨架、揀選臺(tái)、最晚服務(wù)時(shí)間信息已知。
訂單處理系統(tǒng)將周期T-1 內(nèi)的任務(wù)需求劃為一個(gè)批次，并按照任務(wù)到達(dá)的先后順序進(jìn)行編號(hào)（先到的任務(wù)編號(hào)較?。?。在周期T 開始時(shí)刻，調(diào)度系統(tǒng)將指派AGV 完成訂單揀選任務(wù)，同時(shí)基于路網(wǎng)布局為每輛AGV 規(guī)劃無碰撞的行駛路徑?？烧{(diào)用AGV 包含停放在停靠區(qū)、空閑但在返回?？繀^(qū)途中兩種狀態(tài)（小車已完成上一批次任務(wù)，但仍在返回?？繀^(qū)途中時(shí)，可指派該批次新任務(wù)）。已分配任務(wù)的AGV 需從當(dāng)前位置出發(fā)，依次到達(dá)所分配任務(wù)指定的貨架與揀選站臺(tái)，最終返回停靠區(qū)。未分配任務(wù)的AGV 需從當(dāng)前位置出發(fā)回到?？繀^(qū)或靜止在?？繀^(qū)。AGV
設(shè)有統(tǒng)一的閾值電量，當(dāng)剩余電量降至閾值時(shí)，AGV需返回?？繀^(qū)。優(yōu)化目標(biāo)是周期T 內(nèi)，所有AGV 的總運(yùn)作時(shí)間和任務(wù)時(shí)間窗違反懲罰之和最小。為方便建模，本文考慮以下假設(shè)：①AGV 只能沿柵格左右、前后移動(dòng)；②所有AGV 同質(zhì)且不考慮剎車、啟動(dòng)過程；③ 在一個(gè)調(diào)度周期內(nèi)，一輛AGV最多被指派一項(xiàng)任務(wù)。
2.2 數(shù)學(xué)模型
本文建立了一個(gè)混合整數(shù)線性規(guī)劃模型，使用的參數(shù)、變量符號(hào)和定義如表1 所示。
式（1）為目標(biāo)函數(shù)，表示T 時(shí)段內(nèi)，所有AGV的總運(yùn)行時(shí)間和任務(wù)延遲懲罰之和最小。式（2）表示一個(gè)任務(wù)只能分配給一輛AGV，式（3）表示每輛AGV 最多負(fù)責(zé)同一批次的一個(gè)任務(wù)，式（4）表示任務(wù)m 的延遲時(shí)間。式（5）表示AGV 都要在時(shí)刻１離開當(dāng)前位置到達(dá)下一柵格，式（6）表示AGV 最終返回?？繀^(qū)。式（7）表示避免點(diǎn)沖突，即每個(gè)柵格同一時(shí)刻只能容納一輛AGV，式（8）表示避免邊沖突，即不允許多輛AGV 逆向行駛。式（9）表示每輛AGV 在同一時(shí)刻最多經(jīng)過一條邊。式（10）表示每個(gè)柵格的AGV 進(jìn)出流量平衡。式（11）表示AGV 總體路徑方案和各階段路徑方案的關(guān)系。式（12）表示AGV 運(yùn)輸任務(wù)前，第一階段的路徑柵格進(jìn)出流量平衡，式（13）表示AGV 完成任務(wù)后，第三階段的路徑柵格進(jìn)出流量平衡，式（14）~式（16）保證AGV 第二階段路徑的連續(xù)性。式（17）表示AGV k未被指派任務(wù)時(shí)，第二階段和第三階段的路徑不存在。式（18）~式（21）表示AGV 一定經(jīng)過所分配訂單的起點(diǎn)和終點(diǎn)。式（22）表示AGV k 負(fù)載后，將無法在貨架對(duì)應(yīng)的柵格區(qū)域通行。式（23）表示AGV k?？亢螅渌鸄GV 將無法在k 對(duì)應(yīng)的?？繓鸥裢ㄐ小Ｊ剑?4）表示執(zhí)行任務(wù)m 的AGV k 在第二階段到達(dá)fm 的時(shí)刻即是任務(wù)m 的完成時(shí)刻。式（25）為AGV 電量約束。式（26）、式（27）表示決策變量。
3 多AGV 任務(wù)指派與路徑規(guī)劃協(xié)同優(yōu)化算法
3.1 基于任務(wù)與AGV 雙重優(yōu)先規(guī)則的指派算法
考慮到任務(wù)設(shè)有最佳服務(wù)時(shí)間窗，AGV 行駛時(shí)間受電量限制，不合適的匹配結(jié)果可能導(dǎo)致AGV任務(wù)中斷或任務(wù)延誤時(shí)間過長。本文提出一個(gè)基于任務(wù)與AGV 雙重優(yōu)先規(guī)則的指派算法。其中，任務(wù)優(yōu)先規(guī)則考慮最小最晚服務(wù)時(shí)間窗優(yōu)先規(guī)則（規(guī)則1）、最短負(fù)載時(shí)間優(yōu)先（規(guī)則2）、最長負(fù)載時(shí)間優(yōu)先（規(guī)則3）、最大（負(fù)載時(shí)間/最晚服務(wù)時(shí)間） 優(yōu)先（ 規(guī)則4）4種，AGV優(yōu)先規(guī)則考慮任務(wù)-AGV唯一匹配優(yōu)先和最短空載時(shí)間優(yōu)先（即優(yōu)先指派距離任務(wù)起點(diǎn)最近的AGV）2 種。需要特別說明：① 每次算法只選定一種任務(wù)優(yōu)先規(guī)則，但同時(shí)考慮兩種
AGV 優(yōu)先規(guī)則。②此外，當(dāng)任務(wù)優(yōu)先規(guī)則與AGV優(yōu)先規(guī)則出現(xiàn)沖突時(shí)，規(guī)則的優(yōu)先級(jí)順序?yàn)椋喝蝿?wù)-AGV 唯一匹配優(yōu)先規(guī)則> 任務(wù)優(yōu)先規(guī)則>最短空載時(shí)間優(yōu)先規(guī)則。如：根據(jù)任務(wù)優(yōu)先規(guī)則，任務(wù)3應(yīng)優(yōu)先于任務(wù)1 指派AGV。但任務(wù)3 可由多輛AGV 搬運(yùn)，任務(wù)1 只能由AGV_1 搬運(yùn)，則首先考慮將任務(wù)1 指派至AGV_1，確定任務(wù)1 與AGV_1 的匹配關(guān)系，更新待搬運(yùn)任務(wù)和AGV 集。再考慮為任務(wù)3 指派距離其最近的AGV。
指派算法具體流程如下：
步驟1：選定一種任務(wù)優(yōu)先規(guī)則i，輸入待調(diào)度訂單集Task 和AGV 集AGV 的狀態(tài)信息。執(zhí)行步驟2。
步驟2：訂單排序。將Task 中的所有訂單按照任務(wù)優(yōu)先規(guī)則i 排序。執(zhí)行步驟3。
步驟3：構(gòu)建Task-AGV 匹配對(duì)。針對(duì)Task 中的每一個(gè)訂單，依次判斷每輛空閑AGV 執(zhí)行該訂單后，能否在電量允許時(shí)間內(nèi)回到停靠點(diǎn)。
若能，則將該AGV 歸到可執(zhí)行該項(xiàng)訂單的AGV 集合中。執(zhí)行步驟4。
步驟4：識(shí)別訂單與AGV 的唯一匹配。若某項(xiàng)訂單m 只能由某一輛AGV k 執(zhí)行，則確定訂單m 的唯一匹配對(duì)（m，k），將訂單m 指派給AGV k。更新待調(diào)度訂單集和剩余訂單對(duì)應(yīng)的可執(zhí)行AGV 集，如無法找到唯一匹配對(duì)，執(zhí)行步驟5，否則重復(fù)步驟4。
步驟5：若Task 為空集，則轉(zhuǎn)至步驟7，否則執(zhí)行步驟6。
步驟6：空閑AGV 排序。從Task 的第一個(gè)訂單m 開始，按照“空載時(shí)間最短”規(guī)則，依次為其分配AGV。更新Task 集和剩余訂單的可執(zhí)行AGV集，返回步驟4。
步驟7：算法停止，輸出訂單-AGV 指派結(jié)果。
3. 2 多車避撞算法
避撞和防死鎖是實(shí)現(xiàn)多輛AGV 路徑規(guī)劃需要考慮的重要內(nèi)容。本文將根據(jù)AGV 任務(wù)指派結(jié)果和剩余電量等約束，設(shè)計(jì)車輛優(yōu)先級(jí)規(guī)則和沖突避免策略。
3.2.1 車輛優(yōu)先級(jí)規(guī)則
規(guī)則1：負(fù)載AGV 與空載AGV 沖突：
（1）如空載AGV 的剩余工作時(shí)間為0，即剩余電量小于閾值電量，則空載AGV 優(yōu)先級(jí)高；
（2）如不滿足（1），則負(fù)載AGV 的優(yōu)先級(jí)高于空載AGV。
規(guī)則2：兩輛負(fù)載AGV 沖突：
（1）負(fù)載時(shí)間窗較小的任務(wù)的AGV 優(yōu)先級(jí)高；
（2）如不滿足（1），即任務(wù)時(shí)間窗相同，則預(yù)計(jì)最先完成當(dāng)前搬運(yùn)任務(wù)的AGV 優(yōu)先級(jí)高；
（3）如不滿足（1）和（2），則剩余工作時(shí)間較小的AGV 優(yōu)先級(jí)高；
（4）如不滿足（1）~（3），則累計(jì)已等待時(shí)間較長的AGV 優(yōu)先級(jí)高；
（5）如不滿足上述四種規(guī)則，則隨機(jī)指定AGV 優(yōu)先通行。
規(guī)則3：若兩輛空載AGV 沖突：
（1）剩余電量小于閾值電量的AGV 優(yōu)先級(jí)高。如兩輛AGV 的剩余電量都小于閾值電量，則剩余電量小的AGV 優(yōu)先級(jí)高；
（2）如不滿足（1），則剩余路程較短的AGV優(yōu)先級(jí)高；
（3）如不滿足上述兩種規(guī)則，則隨機(jī)指定AGV 優(yōu)先通行。
3.2.2 多車沖突避免策略
本文考慮3 種沖突情況：節(jié)點(diǎn)沖突，即AGV 在同一時(shí)刻到達(dá)同一柵格；相向沖突，即在雙向?qū)б缆分校瑑奢v相向而行的AGV 在同一柵格發(fā)生碰撞；追擊沖突，即一輛AGV ?？吭跂鸥竦却渌鸄GV 通行時(shí)，被另一輛AGV 追擊而發(fā)生碰撞。同時(shí)，本文考慮兩種避撞策略：等待法和更換路徑。
針對(duì)節(jié)點(diǎn)沖突，優(yōu)先考慮優(yōu)先級(jí)較低的AGV 在前一柵格停靠等待；針對(duì)相向沖突和追擊沖突，則選擇優(yōu)先級(jí)低的AGV 更換路徑。
3.3 考慮五種改進(jìn)策略的A*算法
A*算法是經(jīng)典的最短路徑搜索算法。在該算法中，代價(jià)函數(shù)的選取直接決定搜索的效率和質(zhì)量。傳統(tǒng)A* 算法的代價(jià)函數(shù)為F ( n )= g ( n )+h ( n )，其中，F(xiàn)（n）
表示從起點(diǎn)到終點(diǎn)的估計(jì)代價(jià)，g（n）表示從起點(diǎn)到位置n 的估計(jì)代價(jià)，h（n） 表示從位置n 到終點(diǎn)的估計(jì)代價(jià)。在尋找最短路徑問題中，通常以移動(dòng)距離作為估計(jì)代價(jià)。
但是，本文研究目標(biāo)是求解使得所有AGV 運(yùn)行時(shí)間、轉(zhuǎn)向效率懲罰和全部任務(wù)延誤時(shí)間之和最小的解決方案。路網(wǎng)存在多輛AGV 時(shí)，單一追求距離最短可能導(dǎo)致AGV 之間的沖突加劇，產(chǎn)生大量的等待時(shí)間和任務(wù)延遲。因此，本文結(jié)合問題特性，從時(shí)間維度設(shè)置代價(jià)函數(shù)，對(duì)傳統(tǒng)A*算法進(jìn)行改進(jìn)，具體策略如下：
（1）考慮等待時(shí)間。規(guī)劃AGV 路徑時(shí)，需要考
慮以下情況：AGV 從當(dāng)前柵格前往柵格n1，可能與已
規(guī)劃路徑AGV 沖突，進(jìn)而導(dǎo)致AGV 需要在當(dāng)前柵
格等待。但AGV 前往另一柵格n2，不會(huì)與其他任何AGV 產(chǎn)生沖突。由于AGV 暫停等待，會(huì)降低路網(wǎng)通行效率，增加繞路和重調(diào)度概率。因此，本文在計(jì)算AGV 從當(dāng)前位置到下一位置的估計(jì)代價(jià)時(shí)，考慮預(yù)計(jì)等待時(shí)間（如圖2（a）所示），用wk ( i → n )表示。
（2）考慮轉(zhuǎn)向代價(jià)。頻繁轉(zhuǎn)向會(huì)大大增加繞路和沖突概率，同時(shí)也會(huì)損耗AGV 使用壽命。此外，轉(zhuǎn)向代價(jià)也是目標(biāo)函數(shù)的組成部分。為更快找到最優(yōu)解，本文用pk ( i → n )表示車輛v 從柵格i 到柵格n、柵格n 到終點(diǎn)的最小轉(zhuǎn)向代價(jià)，其中α 表示單次轉(zhuǎn)向懲罰因子（如圖2（b）所示）。
（3）考慮重調(diào)度效率懲罰。當(dāng)為AGV k1規(guī)劃路徑時(shí)，存在k1 駛向柵格n1，會(huì)與已規(guī)劃路徑的AGVk2 發(fā)生相向碰撞或追擊碰撞，且k1 的優(yōu)先級(jí)較高，k2需要重調(diào)度的情況。如果重調(diào)度情況頻繁發(fā)生，則會(huì)降低算法整體效率。因此，本文考慮加入重調(diào)度效率懲罰，用ek ( i → n ) 表示，其中β 表示單車重調(diào)度效率懲罰因子（如圖2（c）所示）。
（4）考慮停靠區(qū)及貨架柵格回避系數(shù)。AGV 返回停靠區(qū)后將保持靜止直到下一調(diào)度周期被指派任務(wù)，AGV 優(yōu)先級(jí)規(guī)則對(duì)已?？緼GV 的柵格不起作用。因此，為已?？緼GV 柵格設(shè)置回避系數(shù)ak ( i → n )。當(dāng)AGV 下一柵格即將進(jìn)入?？繀^(qū)時(shí)，檢查下一柵格到目標(biāo)柵格之間是否有AGV 已?？浚ㄍ耆豢尚校Ｈ缬?，則將下一柵格的回避代價(jià)設(shè)置為3，否則為0。此外，當(dāng)AGV 處于搬運(yùn)狀態(tài)時(shí)，禁止從貨架柵格通行。因此，當(dāng)出現(xiàn)如圖2（d）所示的情況時(shí)，設(shè)置前往柵格n2的回避代價(jià)為3。
（5）強(qiáng)化方向因子。當(dāng)前柵格和目的柵格一旦確定，兩地之間的方向關(guān)系隨之確定。若AGV 背離目的柵格逆向繞路行駛時(shí)，很大程度上會(huì)增加轉(zhuǎn)向和全局行駛時(shí)間，
避開最優(yōu)解。雖然A*算法中，h（n）起到了一定的方向引導(dǎo)作用（式28，其中min Infk表示從n 到目的柵格至少經(jīng)過的柵格數(shù)），但由于行駛時(shí)間和等待時(shí)間，
h（n）的導(dǎo)向作用被弱化。因此，本文在代價(jià)函數(shù)中進(jìn)一步強(qiáng)化方向因子，增加背離目的柵格的代價(jià)。用dk ( i → n ) 表示AGV 從i到n 的方向代價(jià)，
采用式（29）進(jìn)行計(jì)算，其中γ 表示方向懲罰因子，正向行駛為負(fù)，逆向行駛為正。
3.4 MA-TA-PPCOA 算法流程
本文提出的多AGV 任務(wù)指派與路徑規(guī)劃協(xié)同優(yōu)化算法具體流程如下：
步驟1：輸入算例信息，調(diào)用3. 1 指派算法完成任務(wù)指派。執(zhí)行步驟2。
步驟2：根據(jù)任務(wù)指派順序決定AGV 路徑規(guī)劃順序：Om 表示排序后的訂單集合，Ak 表示Om 對(duì)應(yīng)的搬運(yùn)AGV 集合，Bk 表示按最小移動(dòng)距離由小到大排列的空閑AGV 集合，Dk 表示已規(guī)劃路徑的AGV 集合，Rk 表示需要重新調(diào)度的AGV 集合。執(zhí)行步驟3。
步驟3：若Ak ≠ ?，則按順序選擇AGVk 為其規(guī)劃行駛路徑，執(zhí)行步驟5。否則執(zhí)行步驟4。
步驟4：若Bk ≠ ?，則按順序選擇AGVk 為其規(guī)劃行駛路徑，執(zhí)行步驟5。否則執(zhí)行步驟6。
步驟5：調(diào)用3. 3“ 改進(jìn)A*算法”為AGVk 規(guī)劃路徑（具體流程如圖3 所示），更新Ak 或Bk，以及Dk、Rk，返回步驟3。
步驟6：完成所有AGV 的初始路徑規(guī)劃，執(zhí)行步驟7。
步驟7：若Rk ≠ ?，則進(jìn)入重調(diào)度流程：選擇Rk首位元素AGV k1 作為重調(diào)度車輛k。執(zhí)行步驟8。若Rk = ?，跳轉(zhuǎn)至步驟10。
步驟8：判斷與AGV k1 沖突的AGV k2 是否屬于Rk。若屬于，則k= k2。重復(fù)該過程，直至與重調(diào)度車輛k 的沖突車輛不在重調(diào)度集合中。
如找不到滿足條件的AGV，則k= k1。執(zhí)行步驟9。
步驟9：設(shè)置重調(diào)度AGV k 重調(diào)度節(jié)點(diǎn)的前一節(jié)點(diǎn)作為當(dāng)前位置，調(diào)用3. 3“ 改進(jìn)A* 算法”為
AGVk 規(guī)劃路徑，更新Dk、Rk。返回步驟7。步驟10：算法終止，輸出任務(wù)指派和路徑規(guī)劃結(jié)果。
4 分支切割算法
4.1 預(yù)處理
在大規(guī)模整數(shù)線性規(guī)劃問題中，設(shè)計(jì)一些簡單的有效不等式縮減可行域，能夠加速模型求解?？紤]到本文問題高度復(fù)雜且AGV 每一階段的路徑方案均具有明顯的“下界”限制，本文提出3 個(gè)有效不等式：式（31）~式（34）表示每輛AGV 在三個(gè)階段至少經(jīng)過的柵格數(shù)目。
4.2 有效不等式及分離算法
本文參考Lam 等［17］，提出有效不等式，并設(shè)計(jì)對(duì)應(yīng)的分離算法。規(guī)定X ke 為布爾變量，當(dāng)AGV k 經(jīng)過時(shí)空邊e（e = {( i1，t - 1 )，( i2，t ) }）時(shí)為1，否則為0；e1= {( i2，t - 1 )，( i1，t ) }是與邊e 方向互逆的邊。4. 2. 1 等待邊沖突不等式邊e1 和e11是一對(duì)互逆邊，即e1 = {( i1，t-1 )，( i2，t ) }，e11= {( i2，t - 1 )，( i1，t ) }，e2 ={( i1，t-1 )，( i1，t )}。則任意可行解應(yīng)當(dāng)滿足以下不等式：
該式對(duì)應(yīng)的分離算法為：首先，隨機(jī)選取一條小數(shù)邊(( i1，t - 1 )，( i2，t ) )，依次檢查每個(gè)AGV 是否經(jīng)過該小數(shù)邊的逆邊或在該邊的入口柵格處停留（即e2）。令集合S 表示路徑與小數(shù)邊沖突的AGV 集合，如果找到相應(yīng)的AGV，則將其添加至S中。直至找出所有的沖突AGV，檢查是否違反式（35）。然后，選取新的小數(shù)邊，重復(fù)以上過程。
4.2.2 兩輛AGV 等待邊沖突不等式
式（36）對(duì)應(yīng)的分離算法為：首先，隨機(jī)選取一條小數(shù)邊(( i1，t - 1 )，( i2，t ) )，S1 記錄經(jīng)過邊e1 e2 的AGV 集合，S2記錄經(jīng)過邊e11或集合E2中任意一邊的AGV 集合。對(duì)于S1中的每一個(gè)元素，依次檢查集合S2中的元素是否與其構(gòu)成違反不等式。然后，選取新的小數(shù)邊，重復(fù)以上過程。式（37）對(duì)應(yīng)的分離算法為：首先，隨機(jī)選取一條小數(shù)邊(( i1，t - 1 )，( i2，t ) )，S3記錄經(jīng)過邊e1 的AGV 集合，S4記錄經(jīng)過集合E3中任意一邊的AGV 集合。對(duì)于S3中的每一個(gè)元素，依次檢查集合S4中的元素是否與其構(gòu)成違反不等式。然后，選取新的小數(shù)邊，重復(fù)以上過程。
4.2.3 AGV ?？繘_突不等式
4.3 算法流程
5 仿真實(shí)驗(yàn)
本文進(jìn)行兩次實(shí)驗(yàn)：①設(shè)置12 組小規(guī)模算例，分別利用CPLEX 默認(rèn)算法、本文設(shè)計(jì)的Branchand-cut 算法、啟發(fā)式算法進(jìn)行測(cè)試，以驗(yàn)證BC 算法和啟發(fā)式算法的有效性。②設(shè)置48 組、144 個(gè)大規(guī)模算例。初步實(shí)驗(yàn)結(jié)果表明，當(dāng)柵格規(guī)模增大到10×10 時(shí)，CPLEX 及Branch-and-cut 算法無法啟動(dòng)。因此，第二次實(shí)驗(yàn)僅驗(yàn)證啟發(fā)式算法性能。兩次實(shí)驗(yàn)環(huán)境均為Intel Core i7-10510U 4. 1GHzCPU，RAM 為12GB 的個(gè)人計(jì)算機(jī)，模型求解器為CPLEX 22. 1，啟發(fā)式算法采用C++ 編碼，在Visual Studio2022 平臺(tái)上實(shí)現(xiàn)，Branch-and-cut 在C++中使用ILOG CPLEX 22. 1 的回調(diào)實(shí)現(xiàn)。參數(shù)設(shè)置規(guī)則：隨機(jī)生成任務(wù)對(duì)應(yīng)的貨架柵格和揀選臺(tái)柵格、每輛AGV 的起點(diǎn)柵格和?？繓鸥瘢ú恢貜?fù)）。設(shè)定AGV 單位柵格通行時(shí)間vt 為1 個(gè)時(shí)間單位，ct = vt，max Tk = U [ 0，300 ]，lm= U [ 0. 3T，T ]，小規(guī)模算例周期T=30，大規(guī)模算例周期T=300。問題規(guī)模設(shè)置見表2。
5.1 基于小規(guī)模算例的模型與算法效果測(cè)試
針對(duì)12 組小規(guī)模算例，設(shè)置CPLEX 和Branchand-cut 算法最大運(yùn)行時(shí)間為1800 秒、3600 秒、5400秒三種情況，進(jìn)行三次實(shí)驗(yàn)。MA-TA-PPCOA
算法中單次轉(zhuǎn)向懲罰因子α、單車重調(diào)度效率懲罰因子β、方向懲罰因子γ 取值為｛1，1，3｝，結(jié)果取四種指派規(guī)則下的較優(yōu)解。最終測(cè)試結(jié)果如表3 所示。其中，LB1、LB2 分別表示在最大時(shí)間限制為3600秒時(shí)，CPLEX 和Branch-and-cut算法所得下界值，LB1-1800秒、LB1-5400秒、LB2-1800秒、LB2-5400秒分別表示最大時(shí)間限制為1800 秒和5400 秒情況下的下界值。Obj表示啟發(fā)式算法目標(biāo)函數(shù)值，Time1、Time2、Time3 表示求解時(shí)間，Δ1=（LB2-LB1）/LB1×100%、Δ2=（Obj-LB2）/LB2×100%，Ave為平均值。加粗算例行，表示求得最優(yōu)解。
根據(jù)表3 結(jié)果可知：①兩種精確算法都僅能求得一個(gè)算例的最優(yōu)解。對(duì)于該算例， MA-TAPPCOA算法也可求得最優(yōu)解。②最大運(yùn)行時(shí)間限制會(huì)影響CPLEX 獲得的LB 質(zhì)量。在絕大多數(shù)算
例中，增加求解時(shí)間能夠改善LB 值。尤其將求解時(shí)間從1800 秒增加至3600 秒時(shí)，LB 值改善相對(duì)明顯。但從3600 秒增加至5400 秒后，LB 值改善效果不大。而對(duì)于Branch-and-cuts 算法，求解時(shí)間在1800 秒左右，LB 值基本固定。這也進(jìn)一步說明，本文設(shè)計(jì)的Branch-and-cut 算法能夠在較快時(shí)間內(nèi)，獲得比CPLEX 更高質(zhì)量的LB 值。③在最大求解時(shí)間限制=3600 秒情況下，針對(duì)未能求得最優(yōu)解的11 個(gè)算例，本文的Branch-and-cut 算法可將CPLEX 下界值平均提高59. 89%，下界改善效果明顯。說明本文的Branch-and-cut 算法能夠?yàn)轵?yàn)證啟發(fā)式解決方案提供有效參考。④ MA-TAPPCOA最大求解時(shí)間不超過0. 1 秒，求解結(jié)果與時(shí)間限制為3600 秒的Branch-and-cut 算法下界平均gap 值在7% 左右。其中，有3 個(gè)算例結(jié)果等于下界，為可證明的最優(yōu)解。因此，本文設(shè)計(jì)的MATA-PPCOA 算法求解效率極高，同時(shí)，提供的可行解絕大部分近似最優(yōu)，驗(yàn)證了該算法的有效性。
5. 2 基于大規(guī)模算例的算法有效性測(cè)試
5.2.1 4 種指派規(guī)則對(duì)比測(cè)試
在路徑規(guī)劃階段，本文提出的改進(jìn)A*算法中包含三個(gè)重要參數(shù)：單次轉(zhuǎn)向懲罰因子α、單車重調(diào)度效率懲罰因子β、方向懲罰因子γ。為保證參數(shù)設(shè)置的合理性，考慮8 種情況：( α，β，γ )=｛（1，1，2），（1，1，3），（1，2，2），（1，2，3），（2，1，2），（2，1，3），（2，2，2），（2，2，3）｝，分別測(cè)試4 種指派規(guī)則下的96 個(gè)算例。測(cè)試結(jié)果表明：① 在10×10 和20×20 兩種路網(wǎng)規(guī)模下，( α，β，γ ) 設(shè)置為（1，1，2）或（1，1，3）時(shí)，4種指派規(guī)則的求解效果均較好。但同種參數(shù)設(shè)置下，4 種指派規(guī)則的求解效果差別極小。②在40×40 和60×60 兩種路網(wǎng)規(guī)模下，對(duì)于4 種指派規(guī)則，( α，β，γ ) 設(shè)置為（1，1，3）時(shí)，求解效果最好。設(shè)置為（2，1，2） 或（2，1，3）時(shí)，求解效果最差。這是由于，當(dāng)轉(zhuǎn)向懲罰過高時(shí)，AGV 極易發(fā)生為避免轉(zhuǎn)向而繞路行駛，從而進(jìn)一步增加行駛時(shí)間和碰撞概率等。
綜合以上情況，最合理的參數(shù)設(shè)置為( α，β，γ )= (1，1，3)。下文所有實(shí)驗(yàn)均采取該參數(shù)設(shè)置。表4 展示了參數(shù)設(shè)置為( α，β，γ )= (1，1，3) 的算例測(cè)試結(jié)果，指派規(guī)則對(duì)應(yīng)3. 1 中4 種任務(wù)優(yōu)先規(guī)則，算例“10-3-2”表示（路網(wǎng)規(guī)模10×10、3 輛AGV、2 個(gè)任務(wù)）。表4 中展示的數(shù)據(jù)為每種規(guī)模下3個(gè)測(cè)試算例的平均目標(biāo)值，Ave 表示每種路網(wǎng)規(guī)模下的平均值。根據(jù)表4 結(jié)果可知：在小、中規(guī)模路網(wǎng)中，4種指派規(guī)則的求解效果總體相差不大，規(guī)則3 和規(guī)則1的求解效果略顯優(yōu)勢(shì)。而在60×60 的大規(guī)模路網(wǎng)中，規(guī)則1 求解效果明顯優(yōu)于其他三種指派規(guī)則。因此，總體來看，規(guī)則1 的求解效果和穩(wěn)定性優(yōu)于其他三種指派規(guī)則。下文所有實(shí)驗(yàn)均采用指派規(guī)則1。
5.2.2 5 種改進(jìn)策略效果測(cè)試
為測(cè)試5 種改進(jìn)策略的效果，本部分進(jìn)行5 次實(shí)驗(yàn)，每次實(shí)驗(yàn)加入一種新的改進(jìn)策略，測(cè)試結(jié)果如表5 和圖4 所示。Obj1_1~Obj1_5 分別表示添加“ 考慮等待時(shí)間”策略、同時(shí)添加“ 考慮等待時(shí)間+考慮轉(zhuǎn)向代價(jià)”策略、同時(shí)添加“考慮等待時(shí)間+考慮轉(zhuǎn)向代價(jià)+ 考慮重調(diào)度效率懲罰”策略、同時(shí)添加“考慮等待時(shí)間+考慮轉(zhuǎn)向代價(jià)+考慮重調(diào)度效率懲罰+考慮停靠區(qū)和貨架柵格回避系數(shù)”策略、 同時(shí)添加5 種改進(jìn)策略的目標(biāo)值。Time1_1~Time1_5表示相應(yīng)的求解時(shí)間，其中Time=0. 00 表示求解時(shí)間不足0. 01 秒。此外，考慮到AGV 轉(zhuǎn)向過多會(huì)造成車體損耗與碰撞概率增加，因此，在本部分及5. 2. 3 的實(shí)驗(yàn)中，將AGV 轉(zhuǎn)向次數(shù)統(tǒng)計(jì)到結(jié)果中。圖4 為5 次實(shí)驗(yàn)結(jié)果的堆積折線圖，相鄰折線之間的差距可表示新增策略的改進(jìn)效果。
結(jié)合表5 和圖4 的結(jié)果可知：①整體來看，同時(shí)添加5 種策略的算法能夠獲得絕大部分算例的較優(yōu)解，同時(shí)能夠在2 秒內(nèi)求出所有算例的可行解，效率較高。②根據(jù)圖4，“考慮轉(zhuǎn)向代價(jià)”策略對(duì)算法的改進(jìn)效果最為明顯，其次是“考慮重調(diào)度效率懲罰”策略，“考慮?？繀^(qū)和貨架柵格回避系數(shù)”策略的改進(jìn)效果相對(duì)較弱，而“強(qiáng)化方向因子”策略的改進(jìn)效果最弱。
5.2.3 與傳統(tǒng)A*算法對(duì)比測(cè)試
本文將添加5 種改進(jìn)策略的算法實(shí)驗(yàn)結(jié)果與傳統(tǒng)A* 算法對(duì)比，結(jié)果如圖5（主坐標(biāo)軸表示目標(biāo)值，次坐標(biāo)軸表示求解時(shí)間）和圖6（主坐標(biāo)軸表示轉(zhuǎn)向次數(shù)，次坐標(biāo)軸表示等待時(shí)間）所示：①本文算法求解效果明顯優(yōu)于傳統(tǒng)A*算法，可將傳統(tǒng)A* 算法的實(shí)驗(yàn)結(jié)果平均改善27. 69%，且隨著算例規(guī)模的增大，改善效果更加明顯。②本文算法求解效率更高。改進(jìn)A*算法可在2 秒內(nèi)得到所有算例的解決方案，平均求解時(shí)間為0. 25 秒，對(duì)比傳統(tǒng)A*算法效率提升130. 01%。③本文算法能夠極大降低AGV 轉(zhuǎn)向次數(shù)和等待時(shí)間，提高路網(wǎng)運(yùn)作效率和安全性。尤其在大規(guī)模路網(wǎng)中，算法改進(jìn)效果明顯。
5.3 靈敏度分析
（1）訂單數(shù)量/AGV 數(shù)量對(duì)各項(xiàng)成本的影響。本文設(shè)置｛0. 8，1，1. 2｝三種訂單數(shù)量與AGV 數(shù)量的比例，實(shí)驗(yàn)結(jié)果如圖7 所示，圖7 中主坐標(biāo)軸折線數(shù)據(jù)表示不同規(guī)模算例下，訂單與AGV 比例由0. 8上升為1、1 上升為1. 2 時(shí)，單車行駛時(shí)間（ADT）、轉(zhuǎn)彎次數(shù)（ATU）的增加比例。例如，單車行駛時(shí)間的計(jì)算方式為ADT1-0. 8=100×（ADT1-ADT0. 8）/ADT0. 8。次坐標(biāo)軸柱狀圖數(shù)據(jù)表示單車等待時(shí)間（AWT）和訂單延誤時(shí)間（ADA）的增加量。由圖7可知：
①當(dāng)訂單數(shù)量與AGV 數(shù)量比例由0.8 上升為1 時(shí)，單車行駛時(shí)間和單車轉(zhuǎn)向次數(shù)變化趨勢(shì)一致，但隨路網(wǎng)規(guī)模增大，增加幅度逐漸穩(wěn)定在15% 左右。當(dāng)訂單數(shù)量/AGV 數(shù)量由1 上升至1. 2 時(shí)，單車行駛時(shí)間和轉(zhuǎn)向次數(shù)的增加幅度減弱。
② 當(dāng)訂單數(shù)量/AGV 數(shù)量由1 上升至1. 2 時(shí)，等待時(shí)間的增長幅度較大。尤其當(dāng)AGV 數(shù)量/單列柵格數(shù)量=1.2時(shí)，等待時(shí)間增長明顯。③當(dāng)訂單數(shù)量/AGV 數(shù)量=0.8 時(shí)，幾乎不會(huì)出現(xiàn)訂單延誤情況。但當(dāng)比例上升至1 時(shí)，在大規(guī)模路網(wǎng)情況下，訂單延誤時(shí)間增長較多。當(dāng)比例上升至1. 2 時(shí)，延誤時(shí)間急劇上升。
此外，同比例下AGV 和訂單數(shù)量越多，延誤情況越嚴(yán)重。以上結(jié)論可用于指導(dǎo)倉庫實(shí)踐：日常運(yùn)營中，倉庫可通過計(jì)算不同時(shí)段內(nèi)空閑AGV 的平均數(shù)量，考慮動(dòng)態(tài)調(diào)整調(diào)度周期間隔或采用動(dòng)態(tài)調(diào)整訂單批次數(shù)量的方法，減少訂單延誤，提高AGV 利用率。當(dāng)訂單延誤對(duì)企業(yè)運(yùn)營影響嚴(yán)重且倉庫規(guī)模較大時(shí)，訂單批次可設(shè)置為0. 8×平均空閑AGV數(shù)量，以保證按時(shí)完成訂單出庫任務(wù)。
（2）AGV 密度對(duì)路網(wǎng)效率的影響。本文通過設(shè)置不同的AGV 數(shù)量，分析AGV 密度對(duì)路網(wǎng)運(yùn)作效率的影響，其中AGV 密度=AGV 數(shù)量/單列柵格數(shù)量。結(jié)果如表6 所示。AGV 密度增加對(duì)單車總成本的影響較小，但會(huì)導(dǎo)致單車等待成本和轉(zhuǎn)向次數(shù)的增加，即會(huì)產(chǎn)生更多的碰撞和轉(zhuǎn)向情況。尤其在大規(guī)模路網(wǎng)中，AGV 密度升高，對(duì)路網(wǎng)效率影響更大?？紤]到AGV 數(shù)量過少，則會(huì)造成訂單響應(yīng)不及時(shí)，但AGV 數(shù)量過多，又會(huì)造成路網(wǎng)效率大幅降低。結(jié)合表6 中結(jié)果，當(dāng)AGV 數(shù)量/單列柵格數(shù)量=1. 5 時(shí)，三項(xiàng)成本的增長幅度較小，更利于權(quán)衡訂單響應(yīng)速度與路網(wǎng)運(yùn)作效率。因此，建議管理者在導(dǎo)入AGV 時(shí)，可優(yōu)先考慮將AGV 數(shù)量設(shè)置為倉庫單列柵格規(guī)模的1. 5 倍。
6 結(jié)語
本文以智能倉庫為背景，針對(duì)規(guī)則路網(wǎng)雙向?qū)бh(huán)境下的AGV 在線任務(wù)指派與全局路徑規(guī)劃問題展開研究。首先，采用柵格法進(jìn)行環(huán)境建模，基于雙向?qū)б缆?、AGV 電量與任務(wù)時(shí)間窗約束、無碰撞等問題特性，以最小化周期T 內(nèi)所有AGV 的總運(yùn)行時(shí)間和任務(wù)時(shí)間窗違反懲罰之和為目標(biāo)，建立混合整數(shù)線性規(guī)劃模型。
其次，設(shè)計(jì)了多AGV 任務(wù)指派和路徑規(guī)劃協(xié)同優(yōu)化算法：
①同時(shí)考慮任務(wù)與AGV 雙重優(yōu)先級(jí)規(guī)則設(shè)計(jì)4 種指派算法。
②根據(jù)AGV 優(yōu)先級(jí)規(guī)則和多車沖突避免策略設(shè)計(jì)避撞算法；
③針對(duì)AGV 路徑規(guī)劃，在傳統(tǒng)A*算法的基礎(chǔ)上設(shè)計(jì)了5 種改進(jìn)策略，為AGV 設(shè)計(jì)適應(yīng)全局路網(wǎng)狀態(tài)的路徑方案，進(jìn)而形成一套從任務(wù)指派到路線規(guī)劃的完整調(diào)度算法MA-TA-PPCOA。④引入分支切割算法，為驗(yàn)證MA-TA-PPCOA 算法的效果提供高質(zhì)量下界。最后，利用CPLEX、分支切割算法和MA-TA-PPCOA 算法，針對(duì)12 組小規(guī)模算例和96 組大規(guī)模算例進(jìn)行測(cè)試。
結(jié)果表明：①本文引入的分支切割算法能夠有效改善模型求解下界，提出的MA-TA-PPCOA 算法能夠在極短時(shí)間內(nèi)，提供高質(zhì)量近似最優(yōu)解。②4 種優(yōu)先級(jí)規(guī)則中，采用“最小最晚服務(wù)時(shí)間窗優(yōu)先規(guī)則”求解效果最好。此外，5 種A*改進(jìn)策略均能提升算法求解效果，其中“ 考慮轉(zhuǎn)向懲罰”的改進(jìn)效果最為顯著。③本文算法求解效果和效率明顯優(yōu)于傳統(tǒng)A*算法。本文算
法可將傳統(tǒng)A*算法的實(shí)驗(yàn)結(jié)果平均改善27. 69%，效率提升130. 01%。且隨著算例規(guī)模的增大，改善效果更加明顯。④單批次訂單數(shù)量與AGV 數(shù)量的比例和AGV 密度對(duì)路網(wǎng)運(yùn)作效率的影響較大，是倉庫管理者重點(diǎn)決策和優(yōu)化的內(nèi)容。本文研究成果不僅能夠?yàn)橹悄軅}庫中的任務(wù)分配與車輛調(diào)度問題提供協(xié)同優(yōu)化決策支持，還能拓展應(yīng)用到智能生產(chǎn)車間、自動(dòng)化碼頭、無人駕駛物流園區(qū)等路網(wǎng)相對(duì)規(guī)則、自動(dòng)化程度較高的封閉場(chǎng)景中，為自動(dòng)化車輛的無碰撞動(dòng)態(tài)調(diào)度提供參考借鑒。在下一步研究中，可探索直接在目標(biāo)函數(shù)中考慮轉(zhuǎn)彎次數(shù)，并深入探討該問題的數(shù)學(xué)特性，設(shè)計(jì)更高效的精確算法或者更有效的啟發(fā)式策略。
參考文獻(xiàn)：
［1］ Yan R D， Jackson L， Dunnett S. A study for furtherexploring the advantages of using multi-load automatedguided vehicles［J］. Journal of Manufacturing Systems，2020， 57： 19-30.
［2］ Jia X， Meng M Q-H. A survey and analysis of task allo?cation algorithms in multi-robot systems［C］// Proceed?ings of 2013 IEEE international conference on roboticsand biomimetics （ROBIO）， Shenzhen， China，Decem?
ber 12-14， IEEE， 2013： 2280-2285.
［3］ Xu W X， Guo S S， Li X X， et al. A dynamic schedulingmethod for logistics tasks oriented to intelligent manufac?turing workshop［J］. Mathematical Problems in Engineer?ing， 2019， 2019（1）： 1-18.［4］ Polten L， Emde S. Scheduling automated guided vehiclesin very narrow aisle warehouses［J］. Omega， 2021， 99：1-20.
［5］ Chawla V K， Chanda A K， Angra S， et al. Simultane?ous dispatching and scheduling of multi-load AGVs inFMS-A simulation study［J］. Materials Today： Pro?ceedings， 2018， 5（11）： 25358-25367.
［6］ Heger J， Voss T. Reducing mean tardiness in a flexiblejob shop containing AGVs with optimized combinations
of sequencing and routing rules［J］. Procedia CIRP，
［7］ Singh N， Dang Q V， Akcay A， et al. A matheuristic forAGV scheduling with battery constraints［J］. EuropeanJournal of Operational Research， 2022， 298 （3） ：855-873.
［8］ Fransen K J C， Eekelen J A W M V， Pogromsky A，et al. A dynamic path planning approach for dense，large， grid-based automated guided vehicle systems［J］. Computers & Operations Research， 2020， 123：1-10.
［9］ 張丹露， 孫小勇， 傅順， 等. 智能倉庫中的多機(jī)器人協(xié)同路徑規(guī)劃方法［J］. 計(jì)算機(jī)集成制造系統(tǒng)， 2018， 24（2）：410-418.Zhang D L， Sun X Y， Fu S， et al. Cooperative pathplanning in multi-robots for · intelligentwarehouse ［J］.Computer Integrated Manufacturing Systems， 2018， 24（2）：410-418.
［10］ 張新艷， 鄒亞圣. 基于改進(jìn)A*算法的自動(dòng)導(dǎo)引車無碰撞路徑規(guī)劃［J］. 系統(tǒng)工程理論與實(shí)踐， 2021， 41（1）：240-246.Zhang X Y， Zou Y S. Collision-free path planning forautomated guided vehicles based on improved A* algo?
rithm［J］. Systems Engineering-Theory & Practice，2021， 41（1）： 240-246.［
［11］ 李昆鵬， 劉騰博， 阮炎秋. 半導(dǎo)體生產(chǎn)車間智能AGV路徑規(guī)劃與調(diào)度［J］. 計(jì)算機(jī)集成制造系統(tǒng)， 2022， 28（9）： 2970-2980.Li K P， Liu T B， Run Y Q. Intelligent AGV routingscheduling with applications in semi-conductor produc?tion［J］. Computer Integrated Manufacturing Systems，2022， 28（9）： 2970-2980.
［12］ 李昆鵬， 劉騰博， 賀冰倩， 等 .“ 貨到人”揀選系統(tǒng)中AGV 路徑規(guī)劃與調(diào)度研究［J］. 中國管理科學(xué)， 2022，30（4）： 240-251.Li K P， Liu T B， He B Q， et al. A study on routingand scheduling of automated guided vehicle in“ Cargoto-Picker” system［J］. Chinese Journal of Manage?ment Science， 2022， 30（4）： 240-251.
［13］ Wang Z H， Zeng Q C. A branch-and-boundapproach for AGV dispatching and routing problems inautomated container terminals［J］. Computers & Indus?trial Engineering， 2022， 166： 1-25.
［14］ 余娜娜， 李鐵克， 王柏琳. 自動(dòng)化分揀倉庫中多自動(dòng)導(dǎo)引小車在線協(xié)同調(diào)度算法［J］. 計(jì)算機(jī)集成制造系統(tǒng)， 2022， 28（11）： 3340-3353.Yu N N， Li T K， Wang B L. Multi-AGV online col?laborative scheduling algorithm in automated sortingwarehouse［J］. Computer Integrated Manufacturing Sys?tems， 2022， 28（11）： 3340-3353.
［15］ 王江華， 樓佩煌， 錢曉明. 基于改進(jìn)遺傳算法的AGVS 單雙向混合路徑規(guī)劃［J］. 機(jī)械設(shè)計(jì)與制造工程， 2015， 44（6）： 20-26.Wang J H， Lou P H， Qian X M. Configuring mixeduni/bidirectional guide-path network for automatedguided vehicle system based on improved genetic algo?rithm［J］. Machine Design and Manufacturing Engineer?ing， 2015， 44（6）： 20-26.
［16］ Kim C W， Tanchocoj J M A. Operational control of abidirectional automated guided vehicle system［J］. Inter?national Journal of Production Research， 1993， 31（9）：2123-2138.
［17］ Lam E， Bodic P L， Harabor D， et al. Branch-andcut-and-price for multi-agent path finding［J］. Com?puters & Operations Research， 2022， 144： 1-13.
注釋：本文源自中國管理科學(xué)期刊，摘錄于華中科技大學(xué)管理學(xué)院（李昆鵬，韓雪芳）
《智能倉庫中多AGV 在線任務(wù)指派與全局路徑規(guī)劃問題研究》論文。
