四向穿梭車倉儲系統復合作業調度優化

許麗麗，詹燕，魯建廈，郎一丁

(1.浙江工業大學 機械工程學院，浙江 杭州 310032；2.寧波富佳實業股份有限公司，浙江 寧波 330200)

在土地成本不斷上升的背景下，為了降低倉庫成本，四向穿梭車（以下簡稱四向車）倉儲系統因其密集程度高、可低樓層存儲、靈活性好等優勢，被廣泛應用于家電、煙草和超市等領域.該系統主要由四向車和提升機協同作業，實現跨層和跨巷道的運輸，一臺四向車配合提升機就能到達倉庫任意儲位.當系統物流量增加時，可通過增加四向車的數量來滿足出入庫需求，應用靈活方便.在實際運行中，四向車系統存在堵塞問題，這主要與貨架上的四向車水平通道和垂直提升機的設置有關.特別在四向車系統的復合作業調度中，須對訂單任務進行排序，規劃四向車的作業路徑，并考慮四向車和提升機的協同作業方式，這增加了四向車系統調度的復雜性.因此，如何對四向車系統進行調度優化成為亟須解決的問題.

目前，國內外學者對倉儲系統調度問題的研究主要包括路徑規劃、貨位優化、訂單排序等問題[1].Roy 等[2]研究四向車系統中駐點位置以及交叉通道位置，指出不同位置的選擇對揀選效率的影響.Ekren[3]以最小化平均周期時間和平均能耗為目標確定四向車系統的物理結構設計.針對多層穿梭車倉儲系統，Wang 等[4]研究該系統的揀選作業問題，Carlo 等[5]研究2 臺提升機下多巷道的系統，建立以出入庫作業時間最短為目標的數學模型，確定2 臺提升機的作業順序.湯洪濤等[6]對跨層跨巷道穿梭車倉儲系統的復合作業路徑進行優化.

在單一作業的研究中，劉剛等[7]針對多層穿梭車系統研究穿梭車和提升機并行工作的約束機制，以出庫時間最小為優化目標建立數學模型，并提出Gurobi 與啟發式算法結合的方法求解，提高系統作業效率.何昕杰等[8]為了縮短雙深位四向車系統的出庫作業時間對訂單進行排序，并采用改進的遺傳算法求解.因單一作業在實際應用中效率低，采用復合作業更符合倉庫實際作業模式.

在復合作業的研究中，占翔南等[9]針對多深度的四向車系統，在水平方向解決了多臺四向車在同層作業時造成的沖突死鎖問題.張經天等[10]針對四向車系統的提升機設計調度策略，構建垂直方向的提升機作業的數學模型.在不同設備之間協同作業的研究中，周亞勤等[11]建立有軌車和穿梭車之間的協同作業模型和多出入庫任務的多設備作業調度模型.目前對四向車系統復合作業調度優化的研究主要集中于垂直或水平方向，對兩者協同作業的研究較少.然而，在實際應用中，對該作業的調度問題不可避免，因此須進行相關研究.

調度問題屬于多項式復雜程度的非確定性多項式（non-deterministic polynomial，NP）難問題，使用精確算法求解效率低，而使用智能優化算法可快速求解該問題[12-13].為了改進經典遺傳算法求解調度問題容易陷入局部最優這一缺點，隋振等[14]針對四向車系統處理多訂單任務的問題，提出自適應遺傳退火算法對系統的作業時間模型求解.季順松等[15]設計剪枝的改進遺傳算法，提高算法收斂精度.對改進遺傳算法在解決調度問題上的研究表明，對遺傳算法進行改進可有效彌補遺傳算法容易陷入局部最優的不足.

本研究基于四向車在水平方向上的作業特點，通過增設橫向軌道設計四向車系統，使系統在不進行移庫和占地面積小的情況下能夠存儲多種類型的物料.考慮到提升機與四向車復合作業的特點，進行水平和垂直方向上的建模，并采用基于任務分類的遺傳算法設計，以最小化作業時間為目標對模型進行求解.

1 系統概述

1.1 系統描述

如圖1 所示為某四向車系統示意圖.平面示意圖如圖1（a）所示，采用貫通式貨架存儲，每四排貨架為一組，組與組之間由縱向軌道隔開，每組貨架兩端及貨架的列方向均可存儲不同類型貨物.每組貨架底部為四向車運動軌道，采用四向車對托盤進行存取，四向車沿貨架橫向、橫向軌道及縱向軌道運動.立面示意圖如圖1（b）所示，采用提升機作為四向車垂直方向上的轉運設備，位于橫向和（或）縱向軌道端點，圖1 中提升機位于橫向軌道左端，貨架存儲的第1 層與提升機相交處為托盤在系統中的出入口，即I/O 口.輸送線位于I/O 口旁邊，用于托盤的進出轉運.四向車搭乘提升機在垂直方向運動，在I/O 口實現出入庫.傳統穿梭車系統的貨架對稱排列在巷道兩側，每個巷道都配備提升機和穿梭車，這種系統結構單一，不適用于不規則的場地.而本研究所采用的系統允許提升機設置在貨架的橫向和縱向軌道兩端，這增加了系統適用的場景多樣性，同時還能根據出入庫數量的增加來增加四向車和提升機，以提高系統的運行效率.

圖1 四向穿梭車倉儲系統示意圖Fig.1 Diagram of four-way shuttle warehouse system

1.2 作業流程

四向車系統設備作業方式包含單一作業和復合作業：1）單一作業，提升機配合四向車從I/O 點出發一次只完成入庫或者出庫任務后再回到I/O 點；2）復合作業，提升機配合四向車從I/O 點出發完成入庫后再完成出庫任務回到I/O 點.當復合作業中某一作業貨位在I/O 點時為該作業下的單一作業，故僅介紹復合作業的作業流程.將一次復合作業劃分為入庫、空載和出庫作業，作業流程如圖2 所示.在垂直方向上，提升機從貨架底層完成一次復合作業到達第1 層的路徑如圖2（a）所示；在水平方向上，四向車從緩存區到目標貨位A 路徑如圖2（b）所示.圖中，紅色路徑為路徑1，綠色路徑為路徑2，記J為路徑，J=1 時為路徑1，J=2 時為路徑2.系統完成一次復合作業的流程如下.

圖2 四向車系統復合作業路徑示意圖Fig.2 Schematic diagram of compound operation path of four-way vehicle system

1）入庫作業：四向車移動至提升機內，提升機沿路徑3 從貨架底層運動至第1 層，隨后從輸送線傳送托盤至四向車上，再由提升機沿路徑4裝載滿載的四向車至入庫任務所在層，四向車離開提升機后完成提升機的入庫作業，最后由四向車裝載托盤運送至對應入庫貨位并釋放，完成四向車的入庫作業.其中，若該貨位與后列軌道之間沒有托盤，四向車將沿路徑1 至入庫貨位；反之，四向車將沿路徑2 至入庫貨位.

2）空載作業：在完成入庫作業后，提升機和四向車處于空載狀態.當入庫任務與出庫任務貨位在同一層時，四向車將以最短路徑從入庫貨位到達出庫貨位完成空載作業，該情況下不需要提升機，其空載時間為0；當入庫任務與出庫任務貨位在不同層時，四向車將沿路徑1 至該層緩存區等待提升機空閑，再由提升機移動至四向車所在層，隨后四向車搭乘提升機沿路徑5 至出庫任務所在層，四向車離開提升機后，提升機完成空載作業，四向車沿路徑1 至出庫貨位完成空載作業.

3）出庫作業：四向車在出庫貨位上取出托盤后，將其運送至該層的緩存區等待提升機的空閑.若出庫貨位和后列軌道之間沒有托盤，四向車將托盤裝載，并沿路徑1 運送至緩存區；若出庫貨位和后列軌道之間已經有托盤，四向車將按路徑2將托盤運送至緩存區.如果入庫貨位與出庫貨位位于同一層，則四向車將搭乘提升機沿路徑4運送至貨架的1 層.反之，如果入庫貨位與出庫貨位不在同一層，則四向車將搭乘提升機沿路徑6運送至貨架的1 層.在到達貨架1 層后，釋放托盤到輸送線上，從而完成提升機和四向車的出庫作業.此外，如果任務已完成，四向車搭乘提升機沿路徑3 前往底層并釋放，四向車停靠在底層；如果任務尚未完成，則將繼續執行任務.

2 系統建模

為了對四向車系統建模，建立如圖1 所示坐標軸.任務task 在貨架中的坐標為(x(task),y(task),z(task))：x(task) 為任務task 所在列，當x(task)＜0時，貨位在橫向軌道的上方，當x(task)＞0 時，貨位在橫向軌道的下方；y(task) 為任務task 所在排；z(task)為任務task 所在層.

2.1 問題描述

四向車系統通過提升機和四向車的協同作業實現托盤的出入庫.在提升機將四向車運送至目標任務層后，為了減少設備作業等待時間，四向車在水平方向運動時，提升機可根據其他四向車的作業情況對其作業進行分配.將系統中的任務分配給提升機和四向車執行，以橫向軌道左端的提升機為例，構建在該提升機下的數學模型，并將四向車和提升機完成一次復合作業劃分為入庫、空載和出庫作業進行研究.其調度問題的數學描述如下：系統有一臺提升機和m臺四向車，須完成n個出/入庫任務，作業次數為3n次，四向車作業集合B={B1,B2,···,Bm}，四向車集合S={s1,s2,···,sm},第i臺四向車的作業集合Bi=E為第i臺四向車的作業次數，提升機的作業集合A={a1,a2,···,a3n}.type 為與aj的作業類型，與aj/3 的余數為1 時為入庫作業；余數為2 時為空載作業；余數為0 時為出庫作業.在滿足約束條件下，合理安排四向車和提升機的任務分配及任務的執行順序.約束條件構建如下：

式（1）表示每臺四向車至少分配一個作業；式（2）表示四向車將執行所有任務；式（3）表示一個任務只能由一臺四向車執行；式（4）表示提升機將執行所有任務；式（5）表示每個任務僅由一輛提升機完成一次.

2.2 系統假設

針對四向車系統復合作業調度問題，建立以作業時間最短為目標的模型.為了簡化研究對象，對系統進行如下假設：

1）初始狀態時升降臺和四向車均在貨架底層；

2）四向車一次只運送一個托盤；

3）提升機一次只運送一臺四向車；

4）提升機設置在橫向軌道左端；

5）每臺四向車完成該層任務后在緩存區等待提升機空閑；

6）四向車和提升機均勻速行駛；

7）貨物出入庫位置已知.

2.3 水平方向建模

在四向車系統中，當四向車載著貨物從提升機上駛出到達任務所在層的緩存區后，四向車在水平方向行駛到達任務所在儲位，完成任務后返回緩存區，等待提升機空閑后載著該四向車完成后續任務.四向車從緩存區O到提升機I/O 點的時間ts=w/vx，w為單個貨格寬度，vx為四向車的運行速度.對于一次出入庫任務所劃分的入庫、空載、出庫作業，記系統中一次復合作業的入庫任務為u，坐標為 (x(u),y(u),z(u))，出庫任務為v，坐標為 (x(v),y(v),z(v))，對四向車在水平方向的作業建模.

1）入庫作業，即四向車從該層緩存區處出發到達入庫所在貨位，其行駛距離表達式為

式中：d(Oz(u),u)為四向車從點Oz(u)到點u的行駛距離，Oz(u)表示任務u所在層的緩存區點位；mod(y(u),5)為y(u) 除以5 的余數；l為單個貨格的長度.

2）空載作業，即四向車從入庫貨位到達出庫貨位，其行駛路徑分為2 種情況：z(u)=z(v)

a）出入庫貨位位于同一層，即.

四向車從入庫貨位到出庫貨位行駛路徑如圖3 所示，其距離表達式為

圖3 四向車在 z (u)=z(v) 時完成空載作業路徑圖Fig.3 Diagram of idle load operation path completed by four-way shuttle underz(u)=z(v)

當 α=1 時，

b）出入庫貨位位于不同層，即z(u)≠z(v).

將四向車的空載作業行駛路徑分為2 部分：四向車從入庫貨位出發到達該層緩存區的行駛距離d(u,Oz(u))，此時四向車須等待提升機空閑，然后將四向車運送到出庫貨位所在層，四向車再運動至該層緩存區；四向車從出庫緩存區出發到達出庫貨位行駛距離d(Oz(v),v).表達分別如下：

3）出庫作業，即四向車從出庫貨位出發到達該層緩存區，其行駛距離表達式為

2.4 垂直方向建模

當系統完成任務時，提升機先完成每臺四向車的第1 個入庫作業，則a1～am均為入庫作業，且作業對象分別為四向車完成的，p(a1)=1，p(a2)～p(am) 的值分別為a2～am對應入庫作業所在層.提升機am+1～a3n的作業與四向車完成作業時間、作業類型和四向車位置有關，對其討論如下.

1）提升機完成的aj為入庫作業（t ype(aj)=1，j＞m）.

若提升機完成的aj為入庫作業，則提升機完成的aj-1為出庫作業，且該作業完成后依舊由四向車i完成入庫作業，因此提升機完成作業aj后不一定繼續由同一輛四向車完成aj+1,且該作業類型未知.提升機完成aj-1作業后位于系統第1 層，則

式中：to為提升機從傳送帶摟取或釋放托盤時間，h為單個貨格的高度，vz為提升機在垂直方向上的運行速度.

式中：tl為四向車舉起或釋放托盤時間.

2）提升機完成的aj為空載作業（t ype(aj)=2，j＞m）.

由于提升機完成的aj為空載作業，同時四向車i完成的空載作業，而提升機前一次完成的作業為空載作業或入庫作業，此時提升機開始aj作業所在層則為完成aj-1作業所在層，即

將該空載作業分為2 種情況進行討論：

3）提升機完成的aj為出庫作業（t ype(aj)=0，j＞m）.

提升機完成一次出庫作業后下一作業為入庫作業，因此aj-1不為出庫作業，故而該作業結束后提升機所在層為z(aj-1)，即

綜上所述，采用一臺提升機時完成n個出入庫任務所需時間為

上述水平方向和垂直方向的模型均基于一臺位于橫向軌道左端的提升機而構建，對于系統中存在2 臺提升機且另一臺位于橫向軌道右端時，須在水平方向建模時以該提升機處緩存區的坐標進行構建，并對提升機進行選取.為了減少系統作業時間，選擇距目標貨位行駛時間更短的提升機.記橫向軌道右端提升機位置，即該處的出入口為 I′/O′.如圖4 所示，目標貨位C距 I′/O′的行駛距離更近，其時間更短，此時該任務由右端提升機完成.在確定行駛距離時須考慮該任務的屬性（入庫或出庫）以及貨架的狀態（空載或滿載），其具體方式如2.3 節水平方向作業路徑所示.當該提升機須完成的任務數為n′時，完成任務所需時間為

圖4 2 臺提升機路徑示意圖Fig.4 Ptah diagram of two elevators

綜上所述，當系統完成 (n+n′) 個任務時：若僅使用一臺提升機，完成任務時間T=EE(a3(n+n′)) ；若采用2 臺提升機，完成任務時間T=max(T1,T2)，為了使系統完成任務時間最短，定義目標函數為

3 算法設計

針對四向車系統復合作業調度問題，先將任務分配給提升機，再根據任務類別分配四向車并隨機排序，然后對提升機完成的任務依據調度規則進行排序.此時提升機和四向車均獲得初始的任務順序，為了找到調度問題的優化解，采用基于任務分類的遺傳算法進行求解.

3.1 任務調度規則

在系統作業中，基于訂單信息、四向車和提升機的工作狀態信息以及系統貨架存儲狀態信息對任務進行調度.其中，訂單信息包含出入庫貨位信息和任務緊急程度信息.系統調度須先對任務進行分配再排序，規則如下.

1）任務分配規則.

a）若系統中存在多臺提升機，將任務分配給距目標貨位行駛距離較近的提升機，按提升機的任務量分配合理臺數的四向車.

為了保證完成任務時間最短，應盡量讓四向車在完成一次復合作業時的入庫貨位與出庫貨位處于同一層，此時四向車空載作業時間減少，提升機的空載作業時間為0，使得任務作業時間減少.因此優先將xc與yc的任務進行匹配，若匹配完成后仍存在任務未完成，再將其與其他任務進行匹配.將任務配對后隨機分配給四向車.

2）任務排序規則.

基于分配給提升機的四向車及其隨機分配的任務，確定提升機完成任務順序，排序須遵循以下規則.

a）提升機將所有四向車的第1 次入庫作業依次完成后再繼續后面的任務，保證四向車均在系統中并已開始作業.

b）提升機優先完成訂單緊急作業.

c）提升機選擇距離最近的四向車作業.

基于規則a）將四向車輸送至系統中，若存在規則b），則優先考慮規則b），否則按規則c）進行排序.

3.2 改進遺傳算法設計

作為成熟的隨機尋優算法，遺傳算法能夠較好地解決調度問題，但因其存在局部搜索能力較差的問題須進行改進.所研究的調度問題已將任務進行分類，而基于任務分類對遺傳算法的種群初始化有助于找到更優的初始解，提高遺傳算法的搜索能力，因此采用改進的遺傳算法（improved genetic algorithm，IGA）對文中的調度問題進行求解.對提升機和四向車進行任務分配和初步排序，然后采用IGA 優化作業時間，以單臺提升機作業為例，算法流程如圖5 所示.

圖5 改進遺傳算法流程圖Fig.5 Flow chart of improved genetic algorithm

1）初始化貨架狀態.

對四向車系統中貨架存儲狀態進行初始化.在系統中，當四向車對貨物進行揀選后，貨架上的存儲狀態發生改變.本研究主要考慮的是對一批訂單進行四向車的路徑規劃，在規劃前初始化貨架狀態，即貨位上是否存儲貨物，若是，記該貨架狀態為1，否則記為0.

2）種群初始化與編碼.

基于3.1 節的任務分配規則將n個出入庫任務信息轉換成3n個提升機和四向車的作業信息，對出入庫任務進行分類，初始化染色體種群，對染色體進行編碼，生成長度為3n的染色體，1 ≤r≤n.1 條染色體一共5 層，第1 層為四向車的作業順序編碼，當染色體處于 (3r-2) 位時該作業為入庫作業，其值為1～n的隨機排列，當染色體處于 (3r-1) 位時該作業為空載作業，其值為(3r-2)位和3r位的組合數，當染色體處于3r位時該作業為出庫作業，其值為以規則a）為基礎與入庫作業匹配后產生的值；第2 層為四向車的編號編碼，由于3 個作業由同一輛四向車完成，其值以3 個值為一組，大小為1～m的隨機整數；第3 層為提升機的作業順序編碼，其值須根據規則b）、c）及第1、2 層的染色體來決定；第4 層為提升機的作業類型編碼，值為1 時為入庫作業，值為2 時為空載作業，值為3 時為出庫作業；第5 層為提升機對應四向車的編號.在對染色體進行變換的時候，只變換第1、2 層的染色體，后3 層根據規則3、4 用前2 層2 條染色體計算得出.

3）染色體解碼.

假設某條染色體如圖6 所示，該染色體包含3 次復合作業：入庫3 對應出庫2；入庫1 對應出庫3；入庫2 對應出庫1.提升機載著四向車2 完成入庫3，四向車2 繼續完成空載作業32，提升機回到底層載著四向車1 完成入庫作業1，四向車1繼續完成空載作業13，提升機將載著四向車1完成空載作業13，接著四向車1 和提升機完成出庫作業3 回到底層，再由提升機和四向車1 完成入庫作業2，四向車1 繼續完成空載作業21，提升機完成空載作業回到底層，再由提升機和四向車1完成入庫作業2，四向車1 繼續完成空載作業21，提升機完成空載作業32，接著四向車2 和提升機完成出庫作業2 回到底層，四向車2 任務結束，提升機繼續完成空載作業21，接著四向車1 和提升機完成出庫作業1 回到底層完成所有作業.

圖6 染色體示例Fig.6 Chromosome Examples

4）適應度函數計算.

以系統完成任務的時間最短為目標，將該目標作為適應度，在進行計算時須考慮系統完成一次復合作業后貨架狀態再計算下一次復合作業的時間.適應度函數為

5）選擇.

在進行選擇交叉變異時，僅對染色體的第1、2 層進行操作，第3～5 層根據前2 層的值進行計算.在選擇父代時，由于染色體之間適應度的方差較大，最大值大于最小值的一倍，不宜采用輪盤賭的方式進行選擇，故而采取精英選擇加隨機選擇的方式，進行交叉變異產生新的子代.首先進行精英選擇，將每一代種群中適應度在前10%的個體挑選進入下一代種群，然后用隨機選擇的方法進行每個個體的挑選，按照選擇概率確定每個個體是否被選擇作為父代.

6）交叉.

在交叉操作時，在滿足規則a）的情況下，生成一個1～Tier 的隨機數i，將父代第1 層染色體1 在xi與yi中的值與父代第1 層染色體2 中xi或yi進行隨機交叉，再隨機生成一個1 或3 的值，若產生的值為1，則對入庫作業編號進行交叉，若產生的值為3，則出庫作業進行交叉，即完成同層任務之間的交叉操作，其他染色體不變，生成子代染色體.假設產生的層數為2，對入庫作業進行交叉操作，x2={3,5,7}，染色體第1 層的交叉過程如圖7所示.在對染色體第2 層交叉操作時，將父代1 中入庫作業為3、5、7 對應的四向車編號隨機與父代2中入庫作業為3、5、7 對應的四向車編號交叉操作.

圖7 第1 層染色體交叉操作示意圖Fig.7 Schematic diagram of chromosome crossing operation in first layer

為了增加個體多樣性，提高搜索效率，采用自適應交叉算子和變異算子，自適應交叉算子表達式為

式中：f=max (ft,ft+1)，t為迭代次數，f為迭代t次時種群適應度的平均值；fmax、fmin分別為f的最大值、最小值；Pc,max，Pc,min分別為交叉算子最大值和最小值，Pc,max=0.8，Pc,min=0.5；ρ=Pc,max-Pc,min[16].

7）變異.

在變異操作時，隨機產生2 個1～n的隨機數r1和r2，再隨機產生一個1 或3 的值，若產生的值為1，則對入庫作業編號進行變異，即位數為(3r1-2)和 (3r2-2)；若產生的值為3，則出庫作業進行編號，即位數為3r1和 3r2.將對應父代染色體第1 層相應的作業順序進行交換，第2 層將 (3r1-2)、(3r1-1)、3r1對應的四向車編號與 (3r2-2)、(3r2-1)、3r2對應的四向車編號進行交換.自適應變異算子表達式為

式中：Pm,max、Pm,min分別為變異算子最大值、最小值，Pm,max=0.05，Pm,min=0.001；η=Pm,max-Pm,min[16].

8）判斷是否終止算法.

若迭代次數小于或等于最大迭代次數，返回步驟2），繼續迭代；若迭代次數大于最大迭代次數，則輸出最優解.

4 實例分析

為了對IGA 進行評價并驗證該算法的可行性和有效性，以某四向車系統為例，采用MATLAB2016b 軟件對四向車系統的調度優化問題進行實例分析.對系統和算法設置參數如下：貨架排、列、層數分別為10、20 和5；貨格的長、寬、高分別為1.0、1.0、0.8 m；四向車在水平面上運動速度為3 m/s；提升機的運動速度為2 m/s；提升機摟取或釋放托盤的時間為3 s；四向車從緩存區到提升機的時間為0.33 s；四向車舉起或釋放托盤的時間為3.00 s；算法的種群大小為100；迭代次數為1 000；四向車搬運成本c1=10 元/s；倉庫使用成本c2=50 元/s；提升機搬運成本c3=15 元/s；四向車使用成本c4=800 元/臺；提升機使用成本c5=3 000 元/臺.

4.1 實例驗證

為了對研究問題進行實例驗證，選取四向車系統執行復合作業20 次，即入庫任務20 次，出庫任務20 次，分別由1、2、3、4 臺四向車和一臺位于橫向軌道左端的提升機完成，具體出入庫任務如表1 所示.表中，加粗標記的任務須在任務開始后40 s 內完成.初始化倉庫貨架狀態，如表2 所示的貨位為裝載貨位，其他為空閑貨位（入庫貨位應為空閑貨位，出庫貨位應為裝載貨位）.

表1 出入庫任務列表Tab.1 Inbound and outbound tasks list

表2 初始狀態下的裝載貨位Tab.2 Loading position under initial status

基于貨架初始狀態以及訂單信息，采用IGA 對該任務進行排序和分配，對四向車臺數分別為1、2、3、4 臺的系統完成任務.一般而言，若不考慮提升機，僅對四向車的任務進行分配，則四向車臺數越多，完成效率越高.但由于只考慮一臺提升機，且存在提升機和四向車的任務分配及提升機和四向車之間的協同作業，會降低四向車的利用率.隨著四向車臺數的增加，提升機的等待時間也會增加.通過IGA 對研究問題進行求解，每種情況分別運行30 次取平均值，其結果如表3 所示.表中，TZ 為四向車的作業時間，TW 為四向車的等待時間，TM 為提升機的運動時間，TC 為總任務完成時間.系統中四向車臺數越多，完成任務時間越短.

表3 不同四向車臺數下IGA 優化的系統作業時間Tab.3 System operation time of IGA optimization under different number of four-way shuttle

為了確定四向車臺數，對系統成本的計算如下：

式中：t1為四向車的作業時間，t2為倉庫的使用時間，t3為提升機的運動時間.由于已考慮提升機的使用成本，提升機等待狀態下的成本忽略不計.根據表3 求出的設備作業時間，可以計算出系統成本和各設備成本，如圖8 所示.可以看出，隨著臺數的增加，四向車花費成本逐漸增加；提升機花費成本基本持平，在四向車臺數為3 時成本最少；倉庫使用成本隨著四向車臺數的增加而減少；系統成本在四向車臺數為3 時取得最小值.綜上所述，系統成本的變化主要取決于四向車和倉庫使用成本，在該實例中，為了使系統完成任務花費成本最少，應采用3 臺四向車，此時四向車完成任務順序如表4 所示.提升機的作業順序可以根據四向車的作業順序及系統的調度規則進行計算.

表4 四向車臺數為3 時的作業順序Tab.4 Sequence under number of four-way vehicles of three

圖8 不同四向車臺數下的成本Fig.8 Cost under different numbers of four-way shuttles

上述實例采用IGA 對復合作業為20 次的任務進行優化，未體現該算法在研究該問題上的性能，因此須對算法性能進行分析.

4.2 算法性能分析

為了對算法性能進行分析，在系統中采用一臺四向車和一輛提升機完成訂單，并在不同訂單規模下對IGA 與GA 的優化結果進行比較，優化后所需的訂單時間如表5 所示.表中，no為訂單數，AVE 為算法求解的任務平均完成時間，δ 為算法優化效率，VAR 為算法求解的方差，δ=(AVE(GA)-AVE(IGA))/AVE(GA).其結果顯示當訂單規模增大時，δ 呈現上升的趨勢，意味著IGA 所優化的結果更好.IGA求解的方差也小于GA 的，效率至少提高了10.3%.算法在訂單數為500 時的算法迭代圖如圖9 所示.IGA 在迭代到582 代時達到優化解，而GA 在822 代時才達到.為了進一步對IGA的性能進行分析，分別采用IGA 和GA 對單雙臺提升機在訂單數為200 時不同四向車臺數下的任務完成時間進行比較，其結果如圖10 所示.可以看出，在同一任務下采用IGA 優化后的任務完成時間均明顯比GA 的時間短，而且在系統采用2 臺提升機時所優化的結果更明顯.因此，相較于GA，IGA 具有更高的效率和魯棒性.

表5 不同訂單規模下算法優化結果Tab.5 Algorithm optimization results under different order sizes

圖9 訂單規模為500 時算法迭代圖Fig.9 Algorithm iteration diagram under order size of 500

圖10 訂單規模為200 時算法優化的系統作業時間Fig.10 System operation time optimized by algorithm under order size of 200

4.3 系統結構分析

為了進一步對系統結構分析，比較單臺和2 臺提升機的情況對系統的影響.根據圖9 中IGA 優化后的結果可知：1）隨著四向車臺數的增多，任務完成時間減少地越慢；2）采用2 臺提升機的平均作業效率比采用1 臺時高0.33%.為了驗證訂單規模對單雙臺提升機作業效率的影響，在單臺提升機完成訂單數為20 時選擇3 臺四向車可獲得最低成本，因此在對單雙臺提升機分析時，選擇6 臺四向車完成訂單數為50、100、200和500 的任務，其結果如圖11 所示，選擇2 臺提升機相比于1 臺提升機的效率分別提高了24.4%、38.7%、33.7%和43.2%，基本上隨著訂單的增加，2 臺提升機相對于1 臺提升機的效率優勢也越來越明顯.當系統中存在2 臺提升機時，效率應比只有1 臺提升機時快一倍.然而，由于四向車和提升機之間的相互作業會導致作業時間增加，隨著訂單數的增加，分配給2 臺提升機的訂單處于同一層并進行分類的概率增加.研究結果表明，在訂單數為500 時效率達到43.2%，接近一倍.因此，在四向車臺數大于提升機臺數的情況下，訂單數越大，采用2 臺提升機的效率優勢越大.

圖11 不同訂單規模不同提升機臺數下完成任務時間Fig.11 Completion time under kinds of elevators and order sizes

5 結語

（1）建立以系統總任務作業時間為目標的數學模型.將系統的復合作業劃分為入庫作業、空載作業和出庫作業，構建提升機和四向車在這3 種作業方式下完成任務所需時間的模型.

（2）設計改進的遺傳算法.在系統提升機和四向車作業特點下，將出入庫任務進行分類并對遺傳算法進行改進.

（3）實例仿真結果表明，改進后的算法能有效解決所研究問題，四向車和提升機的臺數對系統作業時間存在影響，為了提高系統作業效率，可根據訂單規模安排設備臺數.

本研究未考慮設備的加減速和四向車在同層作業的沖突問題，為了符合倉庫實際運行情況，進一步研究可以在水平方向建模時考慮四向車的沖突問題，在設備上考慮加減速問題，在系統結構上可考慮依據存儲貨物類型增減每組貨架的排數.