自動化立體倉庫“一車雙箱”模式訂單分批與存取決策優化

李浩霖 譚哲一 汪小帆 鎮璐

摘 要：自動化立體倉庫使用雙工位穿梭車與升降機可實現兩件料箱同時搬運的“一車雙箱”存取模式。本文針對“一車雙箱”存取模式下穿梭車立體倉庫揀選作業訂單分批與存取選擇問題，建立數學規劃模型，并設計了雙層變鄰域禁忌搜索算法求解問題。雙層變鄰域禁忌搜索算法中，外層變鄰域禁忌搜索算法優化訂單分批決策，內層啟發式算法則可生成存取決策及時序安排。根據數值實驗結果，該算法能在一定時間內得到滿意解。與傳統“一車單箱”存取模式相比，“一車雙箱”存取模式可顯著提高存取效率。

關鍵詞：穿梭車立體倉庫;訂單分批;存取選擇;變鄰域禁忌搜索算法

中圖分類號：TP18文獻標識碼：A文章編號：2097-0145（2022）02-0041-08doi：10.11847/fj.41.2.41

Integrated Optimization of Order Batching and Retrieving Location

Assignment in Automated Storage and Retrieval Systems

with Double-load Storage and Retrieval Mode

LI Hao-lin， TAN Zhe-yi， WANG Xiao-fan， ZHEN Lu

（School of Management， Shanghai University， Shanghai 200444， China）

Abstract：The application of double-load shuttles and lifts in shuttle-based storage and retrieval systems makes it possible to retrieve or store two unit loads simultaneously， and introduces double-load storage and retrieval mode in warehouse operation. This paper investigates the operational problem of double-load mode in shuttle-based storage and retrieval systems， and proposes a mixed-integer linear programming model to jointly optimize the order batching and retrieving assignment. An efficient two-stage variable neighborhood tabu search algorithm is developed for problem solving. The upper level of the algorithm is a variable neighborhood tabu search algorithm developed for optimizing order batching assignment. The lower level of the algorithm is a heuristic algorithm for generating the retrieving plan and sequence. Numerical experiments show the efficiency of the proposed algorithm. Compared with traditional single-load storage and retrieval mode， the double-load storage and retrieval mode can significantly improve system efficiency.

Key words：shuttle-based storage and retrieval systems; order batching; retrieving problem; variable neighborhood tabu search algorithm

1 引言

近年來，智能倉庫系統極大地變革了倉儲運作模式，為電子商務等行業的發展提供了高效的物流服務支持。智能倉庫依靠多種多樣的智能化設備，實現了倉庫作業的自動化與集成化。在眾多智能倉庫系統中，穿梭車系統具有高速度、高靈活性、節能的特點，廣泛應用于倉庫內部水平方向物料搬運。部分倉庫將穿梭車系統與高層貨架相結合，對傳統自動化立體倉庫進行創新，設計了穿梭車立體倉庫（Shuttle-based storage and retrieval systems，見圖1）[1]。穿梭車立體倉庫應用穿梭車與升降機協同接力完成存取作業，豐富并發展了智能倉庫系統。多數文獻圍繞穿梭車與升降機等核心設備及其運行特征，論證了穿梭車立體倉庫在能耗、行程時間、系統投資等效率指標上的優勢[2，3]，并建立了系統評價模型，為系統設計等戰略決策提供決策參考[4～8]。一些文獻針對穿梭車立體倉庫中工作量平衡、巷道擁堵等運作問題展開探討[9～11]。一般的穿梭車立體倉庫中，穿梭車與升降機每次存取作業只可運載一件料箱，以“一車單箱”存取模式（下文簡稱“單箱模式”）進行。部分倉儲企業在穿梭車立體倉庫中應用了雙工位穿梭車及雙工位升降機（見圖1），實現了兩個料箱同時存取的“一車雙箱”存取模式（下文簡稱“雙箱模式”）。宋振波[12]建立了雙載位單深位多層穿梭車系統的出庫作業時間模型，并研究了儲位分配與任務調度優化等相關問題。雙箱模式一般應用于同層同巷道料箱的存取作業，而部分零散料箱存取作業則以單箱模式執行。雙箱模式可減少倉庫存取作業的執行次數，降低大規模料箱存取作業的時間消耗與總存取成本。雙箱模式需對哪些料箱在何時使用雙箱模式進行決策，這一決策過程直接改變了料箱存取選擇決策機制，同時與倉庫訂單揀選需求密切相關。41A2FBCC-B472-4D65-9D48-38B623931BB4

倉庫出庫作業工作量較大，作業較為復雜，因而常需對訂單及存取任務進行排序、分批等方式處理[13，14]。訂單分批的要義在于整合不同訂單中的零碎需求，以批次為單位進行揀選，以降低需求的零碎性與揀選復雜程度，減少揀選作業中的無用功。基于電商倉庫的背景，許多學者對傳統人到貨倉庫中訂單分批與揀貨路徑[15]、訂單分批與存儲策略[16]、訂單分批與配送[17]等問題的集成優化問題展開了研究。智能倉庫系統中，機器人訂單揀選系統的訂單分批與貨位分配[18]、存取選擇[19]、機器人排程[20]等問題的集成優化也得到了學者關注。訂單分批應用于穿梭車立體倉庫等智能倉庫系統，可通過改變各批次需求特征影響料箱存取決策，減少料箱、托盤出庫及回庫作業次數，同時為雙箱模式應用創造條件。

通過歸納現有研究，可發現穿梭車立體倉庫運營管理研究得到了國內外學者的廣泛關注，訂單分批操作在穿梭車立體倉庫揀選中具有實踐價值。現有文獻中，穿梭車立體倉庫相關研究多通過建立解析模型分析系統行程時間，或通過仿真等方法研究穿梭車路徑規劃、死鎖控制等問題，針對雙箱模式下穿梭車立體倉庫的研究較少。盡管已經有學者研究了自動化倉庫系統的訂單分批問題，然而穿梭車立體倉庫的訂單分批研究較為少見。本文以“一車雙箱”存取模式穿梭車立體倉庫為研究主體，研究了雙箱模式下倉庫揀選作業的訂單分批決策與存取選擇決策，并運用數學規劃方法建立模型，設計了雙層變鄰域禁忌算法求解問題，通過數值實驗驗證了算法的有效性及雙箱模式對系統運行效率的提升。本文的創新點可歸納為以下三點：（1）本文研究了穿梭車立體倉庫雙箱模式，豐富了智能倉庫的運作研究。（2）實現了穿梭車立體倉庫中的訂單分批決策與存取選擇決策的集成優化，為倉庫揀選作業提供了指導。（3）設計的雙層變鄰域搜索算法具有較高的求解效率，為問題的實際應用提供了有效的工具。

2 問題描述

本文從訂單揀選總成本的角度研究了雙箱模式穿梭車立體倉庫訂單揀選，通過存取決策與訂單分批的優化，實現系統效率的提升。本節通過對穿梭車立體倉庫流程介紹，闡述各部分決策之間的內在聯系機理。

訂單分批通過將不同待分揀訂單組合為一個批次，整合不同訂單不同品項的零散需求，以降低訂單需求零散度與波動性，減少不必要的存取作業。訂單分批為各揀貨臺提供了揀選任務的指導，各揀貨臺需按一定先后順序執行分配的各批次揀選任務。受揀貨臺處理能力限制，每個批次的訂單數量、每個揀貨臺執行的批次任務數量需限制在合理范圍內。本文的訂單分批決策包含著將訂單組合為批次、將批次任務分配至揀貨臺的決策問題，同時還關聯著各揀貨臺各批次任務執行順序。為簡化決策流程，本文將每個揀貨臺所有可執行批次進行統一編號，并按照編號順序規定了各揀貨臺批次執行先后順序，建立起批次-揀貨臺間的對應關系，將訂單分批決策定義為將訂單分配至某一編號的批次，從而將揀貨臺分配、批次執行順序決策合并至訂單分批決策中。

訂單分批后需進行料箱存取作業計劃。穿梭車立體倉庫中所有零散的商品由料箱裝載，并存儲于高層貨架內的指定庫位。訂單揀選中需根據各批次需求對料箱執行取貨作業，使用穿梭車、升降機以單箱模式或雙箱模式協同接力將料箱出庫，再由傳送帶送至各揀貨臺。料箱出庫后若有剩余貨物即為散數箱，需執行存儲作業（即取貨作業的相反操作）將散數箱回庫至原貨位等待后續揀選。料箱內若無剩余貨物則為空箱，不需回庫。存取決策中還包含著料箱作業時序安排問題，即對料箱在各批次中的取貨作業開始時間、存儲作業完成時間、料箱間存取作業先后順序進行決策。所有作業都必須在一定的時間窗限制內完成。升降機處以串行作業的順序依次執行各存取任務，而不同層的穿梭車可并行作業。根據作業關系可得出各存取作業間最短時間間隔，并通過時間間隔卡控的方式，保證穿梭車與升降機在執行完前一個任務后，有充足時間運動到下一個任務的作業位置。

倉庫運營管理決策常關注時間及成本兩個目標。時間目標直接體現了倉庫系統的運行效率，常與訂單排序等調度決策相關聯。成本目標則

從經濟角度考察倉庫系統運行。穿梭車立體倉庫中，穿梭車與升降機執行存取作業時需消耗電能，并隨之產生相應的存取成本。本文對存取成本的控制，可直接減少電能消耗，為倉庫系統節能減排目標的實現提供指導。根據雙箱模式所使用設備可知，雙箱模式只在貨位-貨架出入口區域執行，因此本文以貨架出入口為界，將料箱出庫與回庫的存取成本拆分為兩部分，即貨架區域存取成本及揀貨臺區域存取成本。貨架區域存取成本和料箱貨位直接相關，貨位距離貨架出入口越遠，則貨架區域存取成本越高，耗時越長。揀貨臺區域存取成本與揀貨臺位置有關，揀貨臺距離貨架出入口越遠，則成本也越高。為簡化模型，本文利用前述批次與揀貨臺間的對應關系，將揀貨臺區域存取成本轉化為各批次在揀貨臺區域的存取成本表示，即根據各批次所對應的揀貨臺，計算出該批次在揀貨臺區域的存取成本。

為簡化問題，本文根據上述問題設定，提出如下假設：（1）所有訂單的需求信息均為已知信息。（2）每一料箱內只可存儲一個品項的商品，料箱內商品數量已知，各料箱具有固定的庫位。（3）考慮到調度復雜度與升降機運行效率，雙箱模式只可應用于同一層料箱的取貨或存儲作業。（4）料箱存取成本與搬運時間根據歷史運行數據歸納，取穿梭車、升降機、傳送帶在不同工況下的運行成本平均值，因而假設單箱雙箱模式存取成本相同，作業耗時相同，與穿梭車、升降機所承載的料箱數量與重量、運動方向無關。

3 數學模型

3.1 符號說明

模型中所涉及到的符號及其含義如下：

集合與下標。

I為所有料箱的集合，下標為i。

P為所有品項的集合，下標為p。

O為所有訂單的集合，下標為o。

B為所有批次的集合，下標為b。y（b），y′（b）表示開始與結束的虛批次，并由此定義集合B0=B∪{y（b）}，BT=B∪{y′（b）}。41A2FBCC-B472-4D65-9D48-38B623931BB4

參數。

dp，o為訂單o中品項p的需求量。

ui，p為料箱品項參數，若料箱i中產品品項為p，則為1，反之為0。

ci為料箱i從其貨位到出入口間的搬運成本。

cb′為料箱在批次b對應揀貨臺與貨架出入口間的搬運成本。

qb1，b2，若批次b2允許在批次b1揀選完成后開始揀選，則為1，反之為0。

zi1，i2，若箱i1與箱i2位于同一層，且i1存取成本大于i2，則為1，反之為0。

ki，b為箱i在批次b的最短處理時間。

k′i，b為箱i在批次b允許最長處理時間。

li1，i2為箱i1與i2出庫（回庫）作業最短時間間隔。

l′i1，i2為箱i1某批次回庫作業與箱i2某批次出庫作業最短時間間隔。

l″i1，i2為“一車雙箱”操作時箱i1與i2出庫（回庫）作業的時間間隔。

決策變量。

βo，b，0-1變量，若訂單o被分配至批次b，則為1，反之為0。

αi，b，整數變量，為箱i在批次b中的取貨量。

γi，b，0-1變量，若箱i需在批次b揀選，則為1，反之為0。

ιi，b，若箱i需在批次b揀選，則該變量表示箱i批次b揀選作業的開始時間。

κi，b，若箱i需在批次b揀選且料箱未被取空，則該變量表示箱i批次b揀選作業的結束時間。

δi，b，0-1變量，若箱i在批次b揀選后被取空，則為1，反之為0。

λi，b1，b2，整數變量，若箱i先在批次b1揀選，后在批次b2揀選，則為批次b1取貨量，反之為0。

θb1，b2，0-1變量，若批次b1完成時間早于批次b2開始時間則為1，反之為0。

νi1，b1，i2，b2，0-1變量，若箱i1批次b1揀選開始時間需早于箱i2批次b2揀選開始時間則為1，反之為0。

ξi1，b1，i2，b2，0-1變量，若箱i1批次b1揀選結束時間需早于箱i2批次b2揀選結束時間則為1，反之為0。

οi1，b1，i2，b2，0-1變量，若箱i1批次b1揀選結束時間需早于箱i2批次b2揀選開始時間則為1，反之為0。πi1，b1，i2，b2，0-1變量，若箱i1批次b1與箱i2批次b2取貨作業可通過雙箱模式取貨則為1，反之為0。

ρi1，b1，i2，b2，0-1變量，若箱i1批次b1與箱i2批次b2存儲作業可通過雙箱模式存儲則為1，反之為0。

3.2 數學模型

min∑i∈Ici∑b∈B（2γi，b-δi，b-∑i2∈I∑b2∈B

（πi2，b2，i，b+ρi2，b2，i，b））+∑b∈Bcb′∑i∈I（2γi，b-δi，b）（1）

s.t.∑b∈Bβo，b=1o∈O（2）

∑o∈Oβo，b≤nb∈B（3）

∑i∈Iui，pαi，b=∑o∈Odp，oβo，bp∈P，b∈B（4）

αi，b≤Mγi，bi∈I，b∈B（5）

M（θi，b1，b2-1）≤ιi，b2-κi，b1≤Mθi，b1，b2i∈I，b1，b2∈B（6）

θi，b1，b2≤qb1，b2i∈I，b1，b2∈B（7）

ιi，b+ki，b（γi，b-δi，b）≤κi，b≤ιi，b+ki，b′（γi，b-δi，b）i∈

I，b∈B（8）

si-∑b1∈Bλi，b1，b≤M（1-δi，b）i∈I，b∈B（9）

δi，b≤γi，bi∈I，b∈B（10）

λi，b1，b2≤Mθi，b1，b2i∈I，b1，b2∈B，b1≠b2（11）

αi，b1-M（1-θi，b1，b2 ）≤λi，b1，b2≤αi，b1i∈I，b1，b2∈B，b1≠b2（12）

λi，b，b=αi，bi∈I，b∈B（13）

ιi1，b1-ιi2，b2≥li1，i2-M（2+νi1，b1，i2，b2 -γi1，b1-γi2，b2）i1，i2∈I，i1≠i2，b1，b2∈B（14）

κi1，b1-κi2，b2≥li1，i2-M（2+ξi1，b1，i2，b2-γi1，b1-γi2，b2+δi1，b1+δi2，b2）i1，i2∈I，i1≠i2，b1，b2∈B（15）

κi1，b1-ιi2，b2≥l′i1，i2-M（2+οi1，b1，i2，b2+δi1，b1-

γi1，b1-γi2，b2）i1，i2∈I，i1≠i2，b1，b2∈B（16）

νi1，b1，i2，b2+νi2，b2，i1，b1 -πi1，b1，i2，b2-πi2，b2，i1，b1=1i1，i2∈I，i1≠i2，b1，b2∈B（17）

ξi1，b1，i2，b2+ξi2，b2，i1，b1-ρi1，b1，i2，b2-ρi2，b2，i1，b1=1i1，i2∈I，i1≠i2，b1，b2∈B（18）

οi1，b1，i2，b2+οi2，b2，i1，b1=1i1，i2∈I，i1≠i2，b1，b2∈B（19）

2πi1，b1，i2，b2≤zi1，i2（γi1，b1+γi2，b2）i1，i2∈I，b1，b2∈B（20）

2ρi1，b1，i2，b2≤zi1，i2（γi1，b1-δi1，b1+γi2，b2-δi2，b2）i1，i2∈I，b1，b2∈B（21）

∑i2∈I∑b2∈B（πi，b，i2，b2+πi2，b2，i，b）≤1i∈I，b∈B（22）

∑i2∈I∑b2∈B（ρi，b，i2，b2+ρi2，b2，i，b）≤1i∈I，b∈B（23）41A2FBCC-B472-4D65-9D48-38B623931BB4

M（πi1，b1，i2，b2-1）-l″i1，i2≤ιi1，b1-ιi2，b2≤M（1-πi1，b1，i2，b2）-l″i1，i2i1，i2∈I，b1，b2∈B，i1≠i2（24）

M（ρi1，b1，i2，b2-1）+l″i1，i2≤κi1，b1-κi2，b2≤M（1-ρi1，b1，i2，b2）+l″i1，i2i1，i2∈I，b1，b2∈B，i1≠i2（25）

αi，b≥0i∈I，b∈B（26）

γi，b，δi，b∈{0，1}i∈I，b∈B（27）

βo，b∈{0，1}o∈O，b∈B（28）

λi，b1，b2≥0i∈I，b1，b2∈B（29）

θi，b1，b2∈{0，1}i∈I，b1，b2∈B（30）

ιi，b，κi，b≥0i∈I，b∈B（31）

νi1，b1，i2，b2，ξi1，b1，i2，b2，οi1，b1，i2，b2，πi1，b1，i2，b2，

ρi1，b1，i2，b2∈{0，1}i1，i2∈I，b1，b2∈B，i1≠i2（32）

（1）式表示本模型的目標為最小化存取總成本，即各存取任務貨架區域存取成本與揀貨臺區域存取成本的和。（2），（3）式表示每個訂單能且只能被分配至一個批次，每個批次最多可包含n個訂單。（4）式通過各批次各品項揀選需求使訂單分批與存取選擇決策相關聯。（5）式表示箱存取與取貨量的邏輯關系。（6）式用以確定某一箱各批次揀選作業間的時間先后順序關系。（7）式保證各料箱各批次存取順序的合理性。（8）式定義各箱各批次揀選開始時間與結束時間的時間差關系。（9），（10）式用于判斷料箱在某一批次是否被取空。（11）～（13）式計算料箱各批次揀選作業結束后的剩余貨量。（14）～（16）式要求兩料箱兩批次存取作業未以雙箱模式進行時需根據時間順序滿足最小時間間隔限制。（17）～（19）式定義了兩料箱兩批次非雙箱模式時存取作業時序關系的唯一性。若兩料箱兩批次存取任務以雙箱模式進行，則不受非雙箱模式時序關系限制。（20），（21）式表示雙箱模式需滿足雙箱模式的要求。（22），（23）式確保雙箱模式只可對兩個料箱執行。（24），（25）式定義雙箱模式時兩箱的存取時間差。約束（26）～（32）式定義了各決策變量。

4 算法設計

根據前序章節論述，本文主要決策包含訂單分批與存取選擇兩大部分。與常見的訂單分批問題類似，本文問題亦為NP-hard問題，采用商業求解工具或精確解算法難以在較短時間內求解實際應用中的大規模問題。現有訂單分批研究多采用變鄰域搜索、禁忌搜索算法等啟發式算法求解問題[16，21～23]。本文根據問題特征設計了基于變鄰域禁忌搜索算法的雙層啟發式算法，其中外層針對訂單分批問題，應用變鄰域禁忌搜索算法迭代優化，內層則設計了啟發式算法，輸出相應的存取方案及存取總成本。本文算法流程整體思路如下：

（1）應用初始解算法生成初始訂單分批方案。（2）使用外層算法進行訂單分批決策鄰域變換，并應用內層算法計算適應度值，對比選出局部最優解，然后多次迭代，通過禁忌策略避免在后續迭代過程中重復搜索該局部最優解。（3）若算法在多次迭代后無法進一步優化現有局部最優解，則觸發擾動策略，生成新的初始解，并應用新初始解重新執行第二步操作，避免陷入局部最優。

4.1 外層變鄰域禁忌算法設計

本文外層算法使用變鄰域禁忌算法，通過不同鄰域結構對解向量進行鄰域變換，搜索局部最優解，不斷迭代，逐步向全局最優解靠近。本文外層的變鄰域禁忌算法流程如算法1所示。

算法1外層變鄰域禁忌搜索算法

輸入：最大迭代次數iterMax，歷史最優解保持不變迭代次數閾值iterHisMax

輸出：全局最優解

1.初始化已迭代次數iter←0， 歷史最優解保持不變的迭代次數iterHis←0， 清空禁忌表tabuList

2.調用種子算法得到初始解與擾動策略備選解，并調用內層算法計算初始解的適應度值，將初始解賦值于局部最優解curr與歷史最優解hist

3.While iter

4.通過鄰域變換生成一組候選解，并使用內層算法計算候選解適應度值，選取適應度最優候選解作為候選最優解cand

5.If candtabuList，或cand∈tabuList，且cand滿足蔑視準則，then

6.curr←cand

7.End if

8.If curr優于hist， then

9.hist←curr，? iterHis←0

10.Else iterHis←iterHis+1

11.End if

12.If iterHis=iterHisMax， then

13.觸發擾動策略，重新生成當前解，iterHis←0

14.End if

15.iter←iter+1

16.End while

17.Return? hist

4.1.1 編碼策略

外層算法選取訂單在各批次的分配決策變量β作為關鍵變量，并對這一變量使用自然數編碼方式降維，以便后續算法計算與迭代。定義共有B·n個元素的解向量L表示訂單分批的解。解向量中每一個元素代表一個訂單的訂單編號，前n個元素表示批次1所分配的訂單，第 n+1到2n個元素表示批次2所分配的訂單，以此類推，同時使用占位符-1表示某一元素不對應任何訂單。根據（4）式可知，每個訂單只可被分配到一個批次，因而此編碼策略中，除占位符-1外，其余元素的數字不能重復。41A2FBCC-B472-4D65-9D48-38B623931BB4

4.1.2 初始解的確定

為生成迭代初始解，本文對訂單分批中常用的啟發式算法——種子算法，應用了不同的標準，即存取次數標準與平均存取成本標準進行改進，設計了本文的初始解算法。批次b中包含的所有訂單可使用集合Ob表示，而品項p料箱中初始存貨量可通過sp表示。存取次數標準以訂單存取次數作為算法計算的標準，單獨執行每一個訂單存取作業的存取次數為TSRo=∑p∈P「dp，osp，其中「a為向上取整函數。算法首先選取訂單存取次數最少的訂單作為種子，然后選取與目前批次內訂單組合后壓縮率最低的訂單加入批次內，直到該批次達到訂單數量上限后停止該批次分批，開啟新一批次分批，其中訂單批次b的壓縮率為

CRTOb=∑p∈P「∑o∈Obdp，osp∑o∈ObTSRo

壓縮率數值越低，表示這一分批方案的存取次數節約量越大。平均存取成本標準以存取次數標準為基礎，將每一品項的平均存取成本

CPp=∑i∈I∑b∈Bui，p×ci，b|B|×∑i∈Iui，p

作為權重，對訂單存取次數進行加權，得到單獨執行每一個訂單存取作業的存取成本TSRo=∑p∈P「dp，osp×CPp與將幾個訂單合并為同一批次后批次Ocomp的壓縮率

CRTOb=∑p∈P「∑o∈Obdp，osp×CPp∑o∈ObTSRo

兩套標準一般可生成兩組不同的初始訂單分批方案，此時應用內層啟發式算法，求得兩訂單分批方案各自的適應度值，選取存取成本最低的一組為初始解進行后續迭代，將另一組解暫存作為后續擾動策略中所運用的備選解，在觸發擾動策略時調用。

4.1.3 變鄰域搜索策略

根據前述解向量的編碼策略與解的結構特征，本文選取了點交換策略與2-opt策略用于鄰域變換。點交換策略隨機選取解向量中屬于不同批次的兩個元素進行交換。2-opt策略隨機選取解向量中至少包含三個元素，且各元素至少分別屬于兩個批次的連續片段，將該片段中元素以相反順序排列。

4.1.4 禁忌搜索策略

本文將禁忌算法融合于變鄰域算法中，以避免問題陷入局部最優。單次迭代禁忌表記錄每次鄰域變換的變換方式，以避免該次迭代中重復同一鄰域搜索操作，并在該次迭代結束后清空。問題求解全局禁忌表記錄每次鄰域變換后求得的最優解，并保證在規定的長度內禁忌解無法被再次采用。通過這一策略，可避免算法在某一特定鄰域結構上的無意義迭代，擴大搜索范圍。本文禁忌搜索算法中應用了蔑視準則與釋放準則。蔑視準則為若某鄰域解的目標函數值小于當前全局最優解的目標值，無論該解是否在全局禁忌表中，該解均應作為下次迭代的初始解。釋放準則為每次迭代中，全局禁忌表中的解均存在一定概率可被釋放。當禁忌表長度達到一定閾值后，隨著新的禁忌解的加入，舊禁忌解按照“先進先出”原則，從禁忌表中刪去。

4.1.5 擾動策略設計

若某一局部最優解在經過一定迭代次數后無法被繼續優化，則觸發擾動策略，根據擾動策略生成新的解作為當前解，用于下一次迭代。擾動策略被觸發時，首先檢查是否有暫存擾動解，若有則調用擾動解，若沒有則執行隨機種子算法，隨機生成新的擾動解與備選解。隨機種子算法原理與本文初始解算法中的種子算法類似，其不同之處在于隨機種子算法的“種子”解為待分配訂單中隨機選出的一個訂單，其余流程與前述初始解算法類似。隨機種子算法生成兩備選解后，選取其中適應度較小的解替換當前解，適應度較大的解作為擾動策略備選解。

4.2 內層啟發式算法設計

本文算法內層根據穿梭車立體倉庫的存取作業特征設計了啟發式算法，用于求解存取作業方案，具體包括如下三個步驟：

第1步 應用首次適應降序算法（First-Fit Decreasing Algorithm，FFD），得出各個批次需取貨料箱γi，b與取貨量αi，b。首次適應降序算法是裝箱問題中的一個近似算法。本文問題中，每一批次每一品項的需求可視為裝箱問題中的“貨物”，而裝載該品項產品的所有料箱則可視為容量為其初始貨量的箱。本文的問題目標存取成本最小化與裝箱問題中的目標使用箱數量最小化具有一致性，因而本文的存取選擇問題即可轉化為裝箱問題進行求解。

第2步 基于第1步中求得的初步揀選方案，調整第1步求解結果，并據此求解變量δi，b，以及一車雙箱方案πi1，b1，i2，b2與ρi1，b1，i2，b2。方案修正的基本思想為通過對需求進行拆分、重組，排序等方式，減少存取成本較高的料箱的存取次數，并充分利用取空與一車多件等存取成本節省方式。

第3步 根據前序兩步驟得到的γi，b、πi1，b1，i2，b2與ρi1，b1，i2，b2，形成存取任務taskj，將排序問題轉化為有

∑i∈I∑b∈Bγi，b-∑i1∈I∑b1∈B∑i2∈I∑b2∈B（πi1，b1，i2，b2+ρi1，b1，i2，b2）

個客戶點的旅行商問題，并應用內層的變鄰域禁忌算法對這些任務進行排序。內層變鄰域禁忌算法將各個存取任務作為客戶點，形成存取任務的序列，并對存取任務序列運用點交換策略與2-opt策略進行鄰域變換，逐步迭代尋找最優解。若某次迭代后求得的最優解小于等于存取時間限制，則可停止迭代，輸出當前最優解，表示存取方案可行。若當前最優解大于存取時間限制，則進入下一步迭代，逐步尋找滿足存取時間限制要求的解。若多次尋找仍無法找到滿足存取時間限制要求的解，則表示該存取方案不可行。

5 數值實驗

本文通過數值實驗，檢驗本文算法有效性，并進行敏感性分析。本文研究所用實驗平臺CPU為Intel i7-6500U@2.50GHz，內存8GB，采用Windows 10 64位操作系統，在Visual Studio 2015環境中運用C#語言進行代碼編寫與實現。實驗中調用了IBM ILOG CPLEX 12.6.1求解器。41A2FBCC-B472-4D65-9D48-38B623931BB4

5.1 算法測試

本節將本文提出的算法最優解與CPLEX求解器求得解、算法初始解的目標值進行比較，在不同問題規模下進行實驗，驗證算法的有效性。算例規模以|I|-|O|-|B|-|P|-|W|-n的形式表示，其中|W|表示揀貨臺數量。為保證可在適當時間內求得解，本文設定算法與CPLEX求解器的求解時間上限為7200秒。算法最大迭代次數為25次，每次生成候選解數量為10個，禁忌表長度為15，并設定若累計4次迭代后最優解未更新，則觸發擾動策略，即歷史最優解保持不變迭代次數閾值為4。

由表1可知，在小規模算例中，CPLEX能在多數算例中求得最優解。隨著訂單數量增加，CPLEX求解時間逐步增長，當料箱數量達到50個時，CPLEX已無法在7200秒時限內求得最優解。與此同時，本文設計的算法在小規模算例中平均求解時間55秒，在求解時間整體上優于CPLEX。另外本文設計算法在25個料箱的算例中可在較短時間內求得最優解，在50個料箱的算例中求得的解可接近或優于CPLEX在7200秒內求得的可行解。

大規模算例中，CPLEX已無法在7200秒內求出可行解。由表2可計算出本文算法平均求解時間336秒，這說明本文算法可在一定時間內求解大規模問題。本文小規模算例中初始解與最優解平均相對差異為10.57%，大規模算例中初始解與最優解平均相對差異為10.49%，本文算法在大規模問題中依然保持了一定的優化能力，因而本文設計的算法表現出了較強的實際規模問題求解能力。

5.2 “一車雙箱”模式的有效性分析

本文通過敏感性分析實驗，比較雙箱模式與傳統單箱模式在揀選同樣訂單時的揀選成本，說明雙箱模式對總揀選成本的影響。實驗使用本文模型及算法進行，而單箱模式實驗則通過在本文模型中令πi1，b1，i2，b2與ρi1，b1，i2，b2為零，使穿梭車以單箱模式運行，得出“一車單箱”的揀選成本。由表3中結果可知，與單箱模式相比，雙箱模式平均可節省約20%存取成本。

6 結論與啟示

本文研究了雙箱模式下穿梭車自動立體倉庫的訂單分批決策與存取決策的集成優化問題，建立了以總存取成本最小化為目標的混合整數規劃模型，并通過建立雙層變鄰域禁忌搜索算法，提供了穿梭車立體倉庫多種模式下訂單分批與存取決策的指導工具。數值實驗表明，本文設計的算法可高效求解這一問題，雙箱模式在大規模存取作業下可有效降低系統運行成本。

“一車雙箱”存取模式是對一般“一車單箱”模式穿梭車立體倉庫在設備上、效率上、運作模式上的全方位突破。“一車雙箱”存取模式的推廣對推動倉庫系統機電設備更新換代，推行實現倉儲行業設備的全面自動化與流程的全面集成化具有顯著意義。盡管在近期，“一車雙箱”模式的推廣仍受系統投資大、建設要求高、運營管理要求高等瓶頸因素制約，但隨著相關倉庫設備與系統的大范圍應用及倉庫系統運營管理研究的逐步完善，該模式進一步推廣應用的瓶頸將被逐步打破。根據本文研究結果，“一車雙箱”存取模式可節省約20%的存取成本，這說明了“一車雙箱”存取模式在倉庫運作效率提高方面的潛力。“一車雙箱”對倉庫訂單揀選總時間系統效率的影響，還可從總揀選時間、料箱等待時間等指標的角度進行進一步論述，同時對存取成本進行細化，詳細計算穿梭車與升降機在不同工況下的存取成本與時間，得出更為精準的結論。

參 考 文 獻：

[1]Marchet G， Melacini M， Perotti S， 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.

[2]Tappia E， Roy D， Melacini M， et al.. Integrated storage-order picking systems： technology， performance models， and design insights[J]. European Journal of Operational Research， 2019， 274（3）： 947-965.

[3]Wu Y， Zhou C， Ma W， et al.. Modelling and design for a shuttle-based storage and retrieval system[J]. International Journal of Production Research， 2020， 58（16）： 4808-4828.

[4]Ning Z， Lei L， Zhang S， et al.. An efficient simulation model for rack design in multi-elevator shuttle-based storage and retrieval system[J]. Simulation Modelling Practice and Theory， 2016， 67： 100-116.

[5]Ekren B Y. Graph-based solution for performance evaluation of shuttle-based storage and retrieval system[J]. International Journal of Production Research， 2017， 55（21）： 6516-6526.

[6]Lerher T， Ekren B Y， Dukic G， et al.. Travel time model for shuttle-based storage and retrieval systems[J]. International Journal of Advanced Manufacturing Technology， 2015， 78（9-12）： 1705-1725.41A2FBCC-B472-4D65-9D48-38B623931BB4

[7]Dantonio G， De Maddis M， Bedolla J S， et al.. Analytical models for the evaluation of deep-lane autonomous vehicle storage and retrieval system performance[J]. International Journal of Advanced Manufacturing Technology， 2018， 94（5-8）： 1811-1824.

[8]Lerher T， Ekren Y B， Sari Z， et al.. Simulation analysis of shuttle based storage and retrieval systems[J]. International Journal of Simulation Modelling， 2015， 14（1）： 48-59.

[9]Ha Y， Chae J. Free balancing for a shuttle-based storage and retrieval system[J]. Simulation Modelling Practice and Theory， 2018， 82： 12-31.

[10]Roy D， Krishnamurthy A， Heragu S， et al.. Stochastic models for unit-load operations in warehouse systems with autonomous vehicles[J]. Annals of Operations Research， 2015， 231（1）： 129-155.

[11]Lerher T. Travel time model for double-deep shuttle-based storage and retrieval systems[J]. International Journal of Production Research， 2016， 54（9）： 2519-2540.

[12]宋振波.雙載位單深位多層穿梭車系統建模與優化[D].濟南：山東大學，2020.

[13]黃敏芳，張源凱，王顏新.網上超市拆分訂單的合并打包優化決策方法[J].系統工程理論與實踐，2021，41（2）：286-296.

[14]馮曉春，胡祥培.基于學習效果的蔬菜電商成組揀貨排序方法[J].系統工程理論與實踐，2020，40（2）：449-461.

[15]Li J， Huang R， Dai J. Joint optimisation of order batching and picker routing in the online retailers warehouse in China[J]. International Journal of Production Research， 2017， 55（2）： 447-461.

[16]Yang P， Zhao Z， Guo H. Order batch picking optimization under different storage scenarios for e-commerce warehouses[J]. Transportation Research Part E-Logistics and Transportation Review， 2020， 136： 101897.

[17]Zhang J， Liu F， Tang J， et al.. The online integrated order picking and delivery considering Pickers learning effects for an O2O community supermarket[J]. Transportation Research Part E-Logistics and Transportation Review， 2019， 123： 180-199.

[18]Xiang X， Liu C， Miao L. Storage assignment and order batching problem in Kiva mobile fulfilment system[J]. Engineering Optimization， 2018， 50（11）： 1941-1962.

[19]Li Z， Zhang J， Zhang H， et al.. Optimal selection of movable shelves under cargo-to-person picking mode[J]. International Journal of Simulation Modelling， 2017， 16（1）： 145-156.

[20]Li Z， Barenji A V， Jiang J， et al.. A mechanism for scheduling multi robot intelligent warehouse system face with dynamic demand[J]. Journal of Intelligent Manufacturing， 2020， 31（2）： 469-480.

[21]Scholz A， Schubert D， Wscher G. Order picking with multiple pickers and due dates-simultaneous solution of order batching， batch assignment and sequencing， and picker routing problems[J]. European Journal of Operational Research， 2017， 263（2）： 461-478.

[22]Zulj I， Kramer S， Schneider M. A hybrid of adaptive large neighborhood search and tabu search for the order-batching problem[J]. European Journal of Operational Research， 2018， 264（2）： 653-664.

[23]Muter I， Oncan T. Order batching and picker scheduling in warehouse order picking[R]. IISE Transactions， 10.1080/24725854.2021.1925178.13， 2021.41A2FBCC-B472-4D65-9D48-38B623931BB4