自動小車存取系統的調度優化

（北京機械工業自動化研究所有限公司，北京 100120）

1 問題的提出

根據有關部門的數據，我國2015年社會物流總費用為10.8萬億，占GDP總量的16.0%。顯然，從商業的角度出發，發展物流行業，提高效率，減少支出比單純地提高制造效率有著更重要的價值。倉儲作為物流行業的一個重要環節很早就引起了重視。電子技術、電器技術、信息技術和機械設計制造的飛速發展使得一種新型的倉儲方式——自動化立體倉庫（Automated Storage/Retrieval System，AV/RS）的出現變得理所應當。美國的Malmborg教授領導團隊于2003年首先開始了一種新型的自動化立體倉庫——自動小車存取系統（Autonomous Vehicle Storage and Retrieval Systems，AVS/RS）（如圖1所示[1]）的研究。自動小車存取系統可以極大地提高存取效率、滿足多種復雜的存取需求，自動小車結構示意圖如圖2所示。它還可以避免傳統堆垛機式自動化立體倉庫高耦合的缺點，極大地提高存取系統的柔性。因此，對AVS/RS的研究有著非常重要的意義。

圖1 自動小車存取系統的立體示意圖

圖2 自動小車結構示意圖

當前，國內外關于AVS/RS的研究還處在起步階段。已有的研究主要集中如何建立AVS/RS的性能評估模型、減少阻塞或死鎖和AVS/RS的調度優化。Heragu等[2]先用開環排隊網絡（Open Queueing Network，OQN）對自動小車存取系統進行建模，然后用制造系統表現分析器（Manufacturing System Performance Analyzer，MPA）對一種AVS/RS配置進行了出入庫效率分析。接著，他對多種配置的AVS/RS進行了類似的仿真研究。結果表明，當自動小車的利用率在60%到85%之間時，開環排隊網絡可以有效地對自動小車存取系統進行出入庫效率分析。

Marchet等[3]同樣用開環排隊網絡構建了基于平均完成指令時間和等待時間等指標的自動小車存取系統評估模型。他們綜合了自動小車和升降機（Lift）的速度與加速度以及各種類型的貨格參數等情況，通過仿真證實了該模型的有效性。羅建[4]和吳長慶[5]指出環路死鎖是AVS/RS中死鎖出現的主要類型。該團隊運用著色賦時Petri網（Coloured Timed Petri Nets，CTPN）構建了自動小車存取系統的動態模型。他們基于CTPN模型，使用有向工具構建了防止環路死鎖的路線圖，給出了死鎖釋放的充分必要條件。文獻[6]和文獻[7]從儲位分配優化的角度來提高自動小車存取系統的出入庫效率。他們分別用離散粒子群算法、離散粒子群與模擬退火融合的算法建立了自動小車存取系統的貨位優化模型，并用仿真的方法驗證了該方法的有效性。程志江等[8,9]基于模糊控制理論，對智能小車的控制系統進行了研究。馮鋒等[10]為了讓自動小車適應不同場景的應用，設計了自組織模糊控制器來優化自動小車的控制。

2 問題的描述與建模

2.1 問題的描述

根據自動小車能否在升降機的協助下實現跨層作業，可將自動小車存取系統分為單層作業的自動小車存取系統和跨層作業的自動小車存取系統。為了更加體現問題的普遍性，本文選擇自動小車可跨層且可在平面內做二維運動的的自動小車存取系統作為研究對象（在不作特殊說明的情況下，下文所述自動小車存取系統指的都是這種形式）。圖3為自動小車存取系統水平剖面示意圖。如圖所示，網格線填充的矩形塊表示的是標準貨位，黑色填充矩形塊表示的是可運輸自動小車實現垂直運動的升降機，黑色填充的圓形塊則表示該層的I/O點（輸入或輸出點）。自動小車可在空白的巷道自由運行，并可在升降機的協助下完成跨層運動。

圖3 自動小車存取系統水平剖面示意圖

自動小車存取系統共有3種作業方式，分別為：單指令出庫方式，單指令入庫方式和雙指令出入庫復合作業方式。單指令出庫方式指的是AVS/RS在一段過程內只完成出庫任務。單指令入庫方式指的是AVS/RS在一段過程內只完成入庫任務。而，復合作業方式下，一個作業過程要完成出庫和入庫兩個任務，而每個任務都可能是跨層作業的。如圖4所示，復合作業方式下出庫貨位和入庫貨位是逐一交替進行的。

圖4 復合方式下的作業流程

復合作業方式可以有效地縮短自動小車和升降機的空載運行時間，因此可以大大提高整個系統的出入庫效率[11]。本文接下來主要研究復合作業方式。

另外，自動小車在水平面選擇不同的運動路徑也會造成任務完成時間的不同。假設平面上有兩個不重合的點，分別為點A和點B。理論上，A到B之間的路徑有無數條。實際上有兩類路徑比較有代表性。如圖5所示，一類是A到B之間的路徑與經過A、B兩點的直線重合，即路徑2。路徑2的經過的路程叫做點A與點B的歐氏距離。另一類，路徑1和路徑3則代表著躲避規則分布障礙的路徑。容易證明，這類路徑的路程都是相等的。這類路徑所產生的距離可稱為曼哈頓距離或出租車距離。在倉庫的某一層內，自動小車需要在貨位、升降機電梯和I/O間運動。而這三者往往不是沿水平或垂直分布的，即將他們之間的距離簡單地認為是歐式距離是不合理的。即使只能沿水平和垂直分布的巷道運行，在確定的兩點間，自動小車的運行路徑也存在無數條。其中，曼哈頓距離是最短的。因此，本文在計算自動小車在水平運行的最短路程時都采用曼哈頓距離。

圖5 兩節點間的多種路徑

此外，選擇不同的任務完成順序和在需要跨層作業時選擇不同的升降機都會影響訂單的完成總時間。本文調度優化的目標就是在復合作業方式下、自動小車水平運動按照曼哈頓距離運動的前提下，選擇合適的任務完成順序和在需要跨層作業時選擇合適的升降機以使任務訂單的完成時間最短。

2.2 系統建模

現對自動小車存取系統做如下假定：

1）自動小車可以逆向行駛，即自動小車的運行是雙向的。

2）不考慮自動小車、升降機和貨架等硬件設備的故障等不利因素，且不考慮貨物的存取時間。

3）不考慮自動小車和升降機的加速和減速過程，即認為自動小車在水平方向上的運動和升降機在垂直方向上的運動都是勻速的。

4）系統中各層的I/O點（本文假設每層的I/O點有且只有一個）是等價的，即認為系統可借助任何一層的I/O點實現貨物離開系統或進入系統的操作，且不考慮各層I/O點到系統底層的距離。

5）自動小車和升降機都是單負載的，即認為自動小車在一段時間內只能攜帶一個貨物，升降機在一段時間只能攜帶一個自動小車。

6）系統中自動小車和升降機采取“上次完成位置處?？俊?的?？坎呗?，即自動小車和升降機完成任務后會停留在原地，不會主動去做空行程運動。

將單個復合作業過程（即，完成一次相鄰出庫操作和入庫操作）分解為3個過程。

1）過程1：自動小車從當前位置（第一個復合作業過程時，自動小車的出發位置為I/O點。之后的復合作業過程中，自動小車的出發位置是上一個入庫貨位處。本文統一稱之為上一個入庫貨位點）運行到出庫貨位處的過程。當上一次入庫貨位與當前復合作業過程中的出庫貨位在不同層時，系統的運行必須要用到升降機。否則，不需要升降機。

2）過程2：自動小車從出庫貨位運行到I/O點的過程。該過程不會涉及到升降機的調用。

3）過程3：自動小車從I/O點運行到入庫貨位處的過程。當自動小車當前所在的I/O點與入庫貨位不在同一層時，系統的運行必須要用到升降機。否則，不需要升降機。

假設當前有N個出庫任務和N個入庫任務，系統中有M個升降機。本文的研究側重于調度的空間路徑優化。因此，本文關于自動小車的數量設定與文獻[12]相同，即認為系統中有且僅有一個自動小車。不同的任務完成順序和在每一復合作業過程中選擇不同的升降機，會產生不同的調度方案P，而這些調度方案所產生的時間效率往往是不同的。本文優化的目標是找到一個使訂單完成總時間最短的作業方案。則，建立系統的數學模型如下：

其中，T(In→Out)n為第n個復合作業過程中過程1的自動小車耗時，T(Out→I/O)n為過程2的自動小車通過曼哈頓距離的耗時，T(Out→In)n為過程3的自動小車耗時。

當過程1中自動小車的運行需要借助于升降機時，自動小車的耗時如式(2)所示。

其中，TIn→Lift為過程1中，自動小車從上一次入庫貨位處運行到升降機電梯的耗時，TLiftwait,m為自動小車等待第m個升降機（m=1,2,3…M）的耗時，TLiftrun,m為自動小車乘坐該升降機的耗時。

當過程3中自動小車的運行需要借助于升降機時，自動小車的耗時如式(3)所示。

其中，TI/O→Lift為過程3中，自動小車從I/O點運行到升降機電梯的耗時，TLiftwait,s為自動小車等待第s個升降機（s=1,2,3…m）的耗時，TLiftrun,s為自動小車乘坐該升降機的耗時。

3 基于改進遺傳算法的自動小車存取系統的調度優化

AVS/RS的調度優化問題可以用智能搜索算法求解。由于，遺傳算法具有可并發處理和應用范圍廣泛等優點而被廣泛應用于求解此類問題。而簡單遺傳算法又存在著收斂速度低和收斂精度差等缺點。因此，本文將使用改進的遺傳算法來求解AVS/RS的調度優化問題。

3.1 編碼與解碼

符號編碼是滿足本文需求的最理想的編碼方式。為了方便編程操作，編碼的符號選用正整數。例如，第2個出庫任務表示為2，第5個入庫任務表示為5，升降機3表示3。將出庫任務、入庫任務和升降機的編碼依次排列，則可得到染色體個體的基因型。將出庫任務記為向量O，入庫任務記為向量I，升降機組記為向量E，則染色體個體可表示為D=（O，I，E）。例如，某任務訂單的完成順序為A2→B2→A5→B4→A3→B1→A1→B3→A4→B5，且在5個復合作業過程中使用的電梯分別為（1，3）、（2，4）、（3，4）、（3，1）和（3，2），那么染色體個體可表示為：

假設，某任務訂單中出庫任務和入庫任務的數量都為N，那么染色體的長度為4N。

可按照相同的原理進行解碼操作。解碼操作是編碼操作的逆過程。例如，現有某染色體個體為：

則它表示的意義為：訂單按照順序A3→B1→A4→B2→A5→B3→A1→B5→A2→B4依次完成。在5個復合作業過程中使用的電梯分別為（3，1）、（4，1）、（2，3）、（2，1）和（2，4）。

3.1 編碼與解碼

這里采用傳統的種群初始化方法。將染色體個體的第一部分（出庫任務）、第二部分（入庫任務）和第三部分（升降機組）記為Part1、Part2和Part3，并設種群規模為Popsize，且D為某個可行解的基因型，即染色體個體。

在接受康復護理前，2組患者的ADL評分、FMA評分均較低且對比差異無統計學意義（P＞0.05）；在康復護理后，觀察組患者ADL評分、FMA評分結果均高于對照組，差異有統計學意義（P＜0.05）。 見表 1。

按照隨機的方式分別產生基因片段Part1、Part2和Part3。拼接這三個部分，即可得一個染色體個體。如此重復Popsize次，即可得到規模為Popsize的初始化種群。

3.2 線性調整適應度值

這里的目標函數可根據上文的分析通過編寫計算機程序求得，記為f(x)。為了使適應度值與任務完成時間成負相關，本文按照式(4)求適應度函數。

在遺傳算法的前期，個體的適應度值往往相差較大。種群中評價特別優異的個體會得到過量的繁殖機會，容易造成早熟，即過早收斂。而，在遺傳算法的后期，個體的適應度值則往往相差無幾，算法的選擇、交叉和變異過程幾乎變成了隨機過程。

為了避免以上兩種情況的發生，本文采用動態的方法對適應度函數進行線性調整。將原適應度函數簡記為f，調整后的適應度函數簡記為f '。線性調整的表達式為：

其中，a和b為待確定的調整系數。

將種群的最大和最小適應度值分別記為fmax和fmin，平均適應度值記為favg。另外，引入復制期望參數c。一般情況下，c的取值在1.3到1.9之間。

則，調整后的適應度函數為：

則，調整后的適應度函數為：

3.3 基于混合方法的選擇策略

本文采用輪盤賭法選擇方式和精英個體保留法相結合的方式進行選擇。該方式既可以提高優秀個體參與繁殖的機會，又可以保護優秀個體，使其不受破壞。則，遺傳算法可以有效率地提高收斂速度。

具體操作過程如下：

Step1：計算個體被選中的概率。

種群中個體i被選中的概率可用式(12)表示。

其中，POPsize為種群的規模，f '(i)為個體的經過線性優化后的適應度函數。

Step2：生成一個零到適應度總和之間的隨機數。

先隨機生成一個0到1之間的實數w0，則待求的隨機數w可表示如下：

Step3：找出滿足條件的單個個體進入交叉和變異操作。

找出唯一同時滿足式(14)和式(15)的個體j。

Step4：選擇M個個體進入交叉和變異操作。

這里的M也是一個由概率產生的正整數。設定種群中參與到交叉和變異的概率為p，p一般為0.8到1之間的實數。M可以按照式(16)確定。

即，POPsize與p的乘積取整，可得M。

重復M次Step2到Step3的操作，則可得到M個參與交叉和變異的個體。

Step5：保留（POPsize-M）個個體。

先記錄下（POPsize-M）個適應度值較高的個體。然后，將該（POPsize-M）個個體的適應度值逐一與經過交叉和變異操作的個體的適應度進行比較。如果，該（POPsize-M）個個體中的某個個體的適應度值高于M個經過交叉和變異的個體的適應度值，則用該個體替換種群中適應度最低的個體。被替換的個體數在0到（POPsize-M）之間。

3.4 交叉算子和變異算子的設計

1）交叉算子

本文將個體的編碼分為三個部分，分別為出庫貨位排列Part1，入庫貨位排序Part2和升降機組Part3。其中，交叉算子必須使Part1和Part2在交叉操作后保持不重復、不遺漏。也就說，Part1和Part2在交叉以后，仍然是一個嚴格的新的排列。則本文針對Part1和Part2部分分別使用位置基礎交叉法。而Part3的各基因片段之間并沒有絕對的邏輯關系。因此，可以選擇簡單交叉法。

例如，D1和D2為兩個未經交叉操作的染色體個體，如下：

Step1：在染色體個體D1的Part1部分隨機抽取若干個基因位，將這些位置上的基因作為新個體D1'中Part1部分對應位置的基因。去掉染色體個體D2中Part1部分對應位置的基因，并將D2中Part1部分剩下的基因依次填到D1'的Part1部分剩下的基因位。

Step2：隨機抽取個體D1中Part2部分的若干個基因位，將這些基因逐一復制到新個體D1'中Part2部分的對應位置。去掉染色體個體D2中Part2部分與個體D1中Part2被抽取到的相同基因，將D2中Part2部分剩下的基因依次填到D1'的Part2部分剩下的基因位。

Setp3：隨機抽取個體D1中Part3部分的若干個基因位。在個體D2中Part3部分選取相同的基因位。將個體D1中Part3部分被抽取到的若干個基因位替換為個體D2中Part3部分所選取的對應位置的相同基因，則可得到新個體D1'中Part3部分。

算法經過Step1到Step3的操作，可以得到新的個體D1'。進行類似的操作以后可以得到新的個體D2'，新的個體D1'和D2'如下：

2） 變異算子

同樣地，變異操作也要按照三個部分分別進行變異操作。這三個部分都可以使用移位變異法進行變異操作。

以原染色體個體D為例。其中D為：

則，對原染色體個體D中的三個部分分別使用移位變異法，可得到新的染色體D'為：

3.5 基于改進遺傳算法的AVS/RS調度優化的執行步驟

基于AVS/RS自身的特點，結合本文提出的改進遺傳算法，可將算法過程描述如下：

步驟1：符號式編碼 本文選擇符號式編碼的方式編碼；

步驟2：種群初始化；

步驟3：求適應度值并做線性調整 本文通過取目標函數的倒數的方法獲得適應度函數，進而求得適應度值，并根據適應度值分布情況做線性調整；

步驟4：判斷是否滿足終止條件 如果滿足終止條件，則輸出可能的最優解或次優解，并對應于符號式編碼進行解碼得到表現型。如果不滿足終止條件，則重復步驟5到步驟6；

步驟5：基于混合方式的選擇操作 本文設計并采用輪盤賭法和精英個體保留法相結合的選擇策略進行選擇操作；

步驟6：交叉操作和變異操作。

4 實驗及結果分析

4.1 實驗參數

本文已經建立了自動小車存取系統的數學模型、分析了自動小車存取系統的調度內容并提出了一種改進的遺傳算法以實現調度優化。為了研究優化方案的可行性，需要設計合理實驗以進行仿真比較。

現對AVS/RS的各項參數做如下設定。系統包含升降機個數M=4；貨架的層數T=20；巷道單側的貨位數C=11；倉儲水平方向上的巷道數A=2；貨位的寬度μw=1m；貨位的高度μh=0.6m；貨位深度為μd=0.5m；μA=0.5m；自動小車在水平X方向上的運動速度vx=1.8m/s，在水平Y方向上的運動速度vy=1.8m/s；升降機在垂直方向上的速度為2m/s。

隨機生成10個出入庫任務。其中，5個出庫貨位分別為（4，7，20）、（6，11，5）、（7，9，17）、（2，5，11）和（3，7，5），5個入庫貨位分別為（3，9，11）、（8，7，17）、（3，7，19）、（5，11，13）和（9，6，17）。結合系統的各項參數，可得5個出庫貨位和5個入庫貨位的自動小車映射位置的水平坐標分別如表1和表2所示。

表1 出庫貨位映射坐標

表2 入庫貨位映射坐標

4.2 實驗結果分析

為了驗證本文提出的改進遺傳算法IGA在解決自動小車存取系統調度優化方面的優越性，本文將改進遺傳算法IGA與基本遺傳算法GA和離散粒子群算法PSO進行對比分析。設置這三個算法的種群規模Popsize同為30，最大迭代次數MAX_GEN為1000。IGA對適應度值做線性調整，采用混合選擇策略，并采用線性下降的交叉和變異概率。GA采用簡單輪盤賭選擇策略，并保持交叉率和變異不變，其中Pc=0.9，Pm=0.2。PSO的學習因子設置為C1=1，C2=1，慣性權重設置為從0.8曲線下降到0.3。這三種算法分別獨立運行20次，取最短訂單完成時間，即目標函數的最優結果為最終的優化結果。三種算法最終優化結果的迭代趨勢如圖6所示。

圖6 三種算法收斂過程對比圖

由改進遺傳算法求得的最優個體為[4 1 2 5 3丨1 4 2 5 3丨3 4 4 2 2 2 1 1 2 4]。解碼得，最優完成順序為（2，5，11）→（3，9，11）→（4，7，20）→（5，11，13）→（6，11，5）→（8，7，17）→（3，7，5）→（9，6，17）→（7，9，17）→（3，7，19）。其中第1個復合作業組使用升降機3和升降機4，第2個復合作業組使用升降機4和升降機2，第3個復合作業組使用兩次升降機2，第4個復合作業組使用兩次升降機1，第5個復合作業過程使用升降機3和升降機4。

由圖5可知，相比于簡單遺傳算法和離散粒子群算法，本文提出的改進遺傳算法具有更快的收斂速度和較好的收斂精度。證明了IGA是快速和較精確解決自動小車存取系統調度優化的方法。

5 結束語

本文以自動小車可跨層作業的AVS/RS的調度優化作為研究目標。分析了AVS/RS在復合作業方式下的出入庫工作流程，建立了AVS/RS調度優化的數學模型。提出了一種根據現有分布線性調整適應度值，和以輪盤賭法和精英個體保留法相結合的混合選擇策略的改進遺傳算法。最后，通過一組實驗證明了該算法在解決AVS/RS的調度優化求解時是有效的。未來可以將神經網絡等人工智能算法引入到AVS/RS的調度優化求解中。

[1]Fukunari M,Malmborg C J. A network queuing approach for evaluation of performance measures in autonomous vehicle storage and retrieval systems[J].European Journal of Operational Research,2009,193(1):152-167.

[2]Heragu S S,Cai X, Krishnamurthy A,et al.Analysis of autonomous vehicle storage and retrieval system by open queueing network[A].IEEE International Conference on Automation Science and Engineering. IEEE[C],2009:455-459.

[3]Gino Marchet, Marco Melacini, Sara Perotti, et al. Analytical model to estimate performances of autonomous vehicle storage and retrieval systems for product totes[J].International Journal of Production Research,2012,50(24):7134-7148.

[4]Luo J. Deadlock control of autonomous vehicle storage and retrieval systems via coloured timed Petri nets and digraph tools[J].International Journal of Production Research,2009,47(12):3253-3263.

[5]Chang-Qing W U, Shan-Jun H E, Luo J.Cycle-deadlock control of RGVs in autonomous vehicle storage and retrieval systems[J].Computer Integrated Manufacturing Systems,2008,14(9):1766-1773.

[6]羅鍵,鐘壽桂,吳長慶.基于離散粒子群算法的AVS/RS貨位優化[J].廈門大學學報(自然版),2009,48(2):212-215.

[7]鐘壽桂.基于離散粒子群與模擬退火融合算法的自動小車存取系統貨位優化[D].廈門大學,2009.

[8]程志江,李劍波.基于模糊控制的智能小車控制系統開發[J].計算機應用,2008,28(s2):350-353.

[9]程志江,李劍波.基于遺傳算法的智能小車模糊控制系統的研發[J].自動化儀表,2009,30(8):4-7.

[10]馮鋒,鄧志良,趙旭.AGV自動導航小車自組織模糊控制器研究[J].微計算機信息,2008,24(10):84-86.

[11]喬巖,錢曉明,樓佩煌.基于改進時間窗的AGVs避碰路徑規劃[J].計算機集成制造系統,2012,18(12):2683-2688.

[12]羅鍵,蘇海墩,何善君,等.基于改進遺傳算法的自動小車存取系統升降機調度建模與優化控制[J].廈門大學學報(自然版),2010,49(3):328-332.