李浩霖 譚哲一 汪小帆 鎮(zhèn)璐

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

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

中圖分類號：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 引言

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

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

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

2 問題描述

本文從訂單揀選總成本的角度研究了雙箱模式穿梭車立體倉庫訂單揀選，通過存取決策與訂單分批的優(yōu)化，實現(xiàn)系統(tǒng)效率的提升。本節(jié)通過對穿梭車立體倉庫流程介紹，闡述各部分決策之間的內(nèi)在聯(lián)系機理。

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

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

倉庫運營管理決策常關(guān)注時間及成本兩個目標。時間目標直接體現(xiàn)了倉庫系統(tǒng)的運行效率，常與訂單排序等調(diào)度決策相關(guān)聯(lián)。成本目標則

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

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

3 數(shù)學(xué)模型

3.1 符號說明

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

集合與下標。

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

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

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

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

參數(shù)。

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

ui，p為料箱品項參數(shù)，若料箱i中產(chǎn)品品項為p，則為1，反之為0。

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

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

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出庫（回庫）作業(yè)最短時間間隔。

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

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

決策變量。

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

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

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

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

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

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

λi，b1，b2，整數(shù)變量，若箱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揀選結(jié)束時間需早于箱i2批次b2揀選結(jié)束時間則為1，反之為0。

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

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

3.2 數(shù)學(xué)模型

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

4 算法設(shè)計

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

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

4.1 外層變鄰域禁忌算法設(shè)計

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

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

輸入：最大迭代次數(shù)iterMax，歷史最優(yōu)解保持不變迭代次數(shù)閾值iterHisMax

輸出：全局最優(yōu)解

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

2.調(diào)用種子算法得到初始解與擾動策略備選解，并調(diào)用內(nèi)層算法計算初始解的適應(yīng)度值，將初始解賦值于局部最優(yōu)解curr與歷史最優(yōu)解hist

3.While iter

4.通過鄰域變換生成一組候選解，并使用內(nèi)層算法計算候選解適應(yīng)度值，選取適應(yīng)度最優(yōu)候選解作為候選最優(yōu)解cand

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

6.curr←cand

7.End if

8.If curr優(yōu)于hist， then

9.hist←curr，? iterHis←0

10.Else iterHis←iterHis+1

11.End if

12.If iterHis=iterHisMax， then

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

14.End if

15.iter←iter+1

16.End while

17.Return? hist

4.1.1 編碼策略

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

4.1.2 初始解的確定

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

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

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

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

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

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

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

4.1.3 變鄰域搜索策略

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

4.1.4 禁忌搜索策略

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

4.1.5 擾動策略設(shè)計

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

4.2 內(nèi)層啟發(fā)式算法設(shè)計

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

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

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

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

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

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

5 數(shù)值實驗

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

5.1 算法測試

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

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

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

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

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

6 結(jié)論與啟示

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

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

參 考 文 獻：

[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]宋振波.雙載位單深位多層穿梭車系統(tǒng)建模與優(yōu)化[D].濟南：山東大學(xué)，2020.

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

[14]馮曉春，胡祥培.基于學(xué)習(xí)效果的蔬菜電商成組揀貨排序方法[J].系統(tǒng)工程理論與實踐，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