考慮裝車順序的四向穿梭車存儲系統儲位分配研究

摘 "要：四向穿梭車存儲系統具有自動化和高密度的性質，有緩解土地資源緊張和提高出入庫效率的雙重優勢，可以應用在發貨暫存區改善物流中心作業效率。系統多深位的特點會導致翻箱作業，增加車輛等待時間，因此如何通過儲位分配來降低翻箱率的決策至關重要。考慮一車多店且裝車順序信息已知的場景，以最小化翻箱數為目標建立整數規劃儲位分配模型，設計改進遺傳算法IGA進行求解，并以儲位數為基準設計不同規模的數值實驗進行分析。結果表明，在小規模算例中，與CPLEX得到的最優解相比，IGA精度在2.66%左右，而企業現有經驗決策算法EDA精度在171.69%左右；在中大規模算例中，與EDA算法相比平均翻箱數減少33.58%。

"關鍵詞：儲位分配；四向穿梭車系統；緊湊型倉庫；裝車順序；改進遺傳算法

"中圖分類號：F253 " "文獻標志碼：A " "DOI：10.13714/j.cnki.1002-3100.2023.07.034

Abstract： The Four-way shuttle storage and retrieval system has the nature of automation and high density， and has the dual advantages of alleviating the shortage of land resources and improving the efficiency of storage. It can be used in temporary delivery area to improve operation efficiency of logistics center. The multi-depth of the system will lead to the pallet reshuffle and increase the vehicle waiting time， so the decision on how to reduce the pallet reshuffle rate through storage space allocation is very important. Considering the scenario of one car with multiple stores and known information of loading sequence， an integer programming storage allocation model is established with the goal of minimizing the number of reshuffled pallets， an improved genetic algorithm IGA is designed to solve the problem， and numerical experiments of different sizes are designed based on the number of storage unit. The results show that in small-scale instances， compared with the optimal solution obtained by CPLEX， the accuracy of IGA is about 2.66%， while the accuracy of the existing empirical decision algorithm EDA is 171.69%. In medium and large-scale instances， the average number of reshuffled pallets is reduced by 33.58% compared with EDA algorithm.

Key words： storage allocation; four-way shuttle storage and retrieval system; compact warehouse; loading sequence; improved genetic algorithm

0 "引 "言

"隨著互聯網技術全面普及和電商市場繁榮發展，占據主要地位的B2B電子商務平臺迅速崛起，以京東小店、良品鋪子為代表的零售電商企業迅速擴張，每天需要配送的門店訂單和調撥訂單急劇增加，訂單類型逐漸向“多品種、小批量、多頻次、高時效”轉變[1]。為了實現對服務需求的快速響應，物流中心集貨以輪班模式運作：在收到訂單當天，貨物從存儲區揀選打包成整托到暫存區臨時存儲，次日凌晨裝車配送至各家門店。由于每家門店的托盤需求量極少，一輛車需要服務多家門店。為了節約配送時間，門店配送順序根據其地理位置、收貨時間窗等因素事先規劃，且先配送的門店托盤后裝車以方便卸貨。傳統的臨時存儲是將貨物搬運到門店對應的集貨位簡單堆存，占地面積大且搬運時間長，難以滿足集貨作業存儲大量貨物和快速準確裝車的需求。

"四向穿梭車存儲系統（Four-way Shuttle Storage and Retrieval System，FSS/RS）是一種基于穿梭車的新型存儲和檢索系統（Shuttle-Based Storage and Retrieval System，SBS/RS）[2]。如圖1所示，FSS/RS由一系列多深度貨架形成模塊化存儲，不僅能夠提高存儲密度，而且四向穿梭車可以直接把托盤運送到計劃裝載車輛，能夠有效提高出庫效率、縮短出庫時間。但由于系統多深度的特點，若托盤存儲位置不合理會在取貨過程中造成翻箱，增加車輛等待時間。因此，研究四向穿梭車緊湊存儲系統中儲位分配問題至關重要。

目前，國內外學者對四向穿梭車存儲系統的研究相對較少，現有文獻僅針對批量訂單排序優化和穿梭車路徑優化展開了研究，分別從減少穿梭車出入庫次數和避免多臺穿梭車產生沖突死鎖的角度，提高系統整體作業效率[3-4]。

"由于FSS/RS巷道多深度的特點，優先取出較深儲位貨物可能產生翻箱，部分學者研究了在多深度緊湊型存儲系統中通過儲位分配減少翻箱的問題。Revillot-Narváez et al[5]將不同類型的貨物基于停留時間共享同一巷道，以最小化翻箱為目標函數，建立有和沒有預編組兩個ILP模型為托盤分配位置，但考慮的是采用人工操作叉車的非自動化存儲系統。在自動化存儲系統中，Zaerpour et al[6]利用卡車預計到達時間，避免把不同卡車且取貨時間窗重疊的兩個托盤放入同一巷道，當卡車不能按照約定時間到達時，這種魯棒存儲分配的新方法能夠避免過多翻箱工作。在此基礎上，Boywitz和Boysen[7]使用最小化占用巷道數代替取貨時間，因為當系統只有一個I/O點時，最靠近I/O點巷道的取貨時間最短。隨后，Boysen et al[8]把巷道從單側存取設計為雙側，通過比較兩種系統發現卡車到達時間窗難以預測時，雙側存儲系統能夠有效減少翻箱。這些文獻將裝載到同一卡車的貨物視為同樣的取貨順序，對于配送多家門店的情況并不適用。

"四向穿梭車存儲系統作為一種新興的存儲系統，鮮有文獻研究儲位分配的調度問題。倉庫貨物儲位分配與堆場集裝箱箱位分配存在共性，對減少集裝箱裝船階段翻箱數的研究由來已久，相關文獻較為豐富。Chen和Lu[9]提出了混合序列堆放策略減少裝船階段的翻箱數。Gharehgozli et al[10]提出一種決策樹堆疊啟發式算法，以最小化集裝箱碼頭的預期翻箱數。劉嬋娟和胡志華[11]考慮了出口集裝箱進場時間的隨機性，建立多目標優化模型求解避免翻箱。He et al[12]基于船舶到港信息不確定的視角，采用啟發式算法研究箱位分配問題。Gharehgozli和Zaerpour[13]提出了一種替代堆垛策略，允許不同類型的集裝箱共享同一堆棧，減少集裝箱的總搬運時間。但是堆場與倉庫環境對于翻箱數的定義不同，原因在于起重機一次可以搬運多個集裝箱而四向穿梭車一次只能移動一個托盤。

上述文獻要么對四向穿梭車存儲系統中儲位分配以外的調度問題進行研究，要么是在其他緊湊型存儲系統中研究儲位分配問題，要么是在堆場集裝箱場景研究箱位分配問題，但針對FSS/RS儲位分配的研究尚未展開。本文考慮一輛車配多家門店且托盤出庫后裝車順序已知的情況，為托盤在FSS/RS中選擇具體的存儲位置，以裝車階段所有托盤翻箱數最小為目標函數構建整數規劃儲位分配模型，設計改進遺傳算法求解并驗證算法性能。

1 "問題描述與模型構建

1.1 "問題描述。四向穿梭車存儲系統每層有多個巷道，每個巷道有多個儲位，每個儲位可以存儲一個托盤。現有一系列托盤等待存儲，每個托盤按照其到達I/O點的時間生成到達順序，系統無緩沖區必須先到先存，將托盤依次搬運到FSS/RS儲位，使得所有托盤由裝車順序遞增取出階段產生翻箱數最小。如圖2所示，顯示了15個托盤存入FSS/RS后的狀態，括號內、外的數值分別是托盤的到達順序和裝車順序，托盤編號默認裝車順序。假設每個托盤只能從箭頭方向單側存取，由巷道約束可得從左到右的到達順序必須遞增排列，而取出目標托盤時，若巷道出口方向有其他托盤阻擋則需提前翻箱，例如巷道2需要依次取出編號為2、5、8、11、12的托盤，但托盤2被托盤5阻擋，計為1次翻箱。取出目標托盤后會將之前翻箱的所有托盤重新放回原位置存儲，若后續過程阻擋則重新計算翻箱數。

1.2 "模型假設。為建立線性整數規劃儲位分配模型，假設如下：（1）初始狀態為空，當貨物不足整托時仍按整托入庫；（2）卡車預計到達時間和配載計劃已知；（3）無緩沖區，托盤必須先到先存；（4）各巷道均單側存取；（5）阻擋的托盤會重新放回原位置存儲，再次阻擋仍會翻箱。

1.3 "相關定義

（1）參數：托盤集合I=1，2，…，p，i為裝車順序（托盤編號），i∈I，p表示托盤數；巷道集合R=1，2，…，m，r為巷道編號，r∈R，m表示巷道總數；儲位集合T=1，2，…，n，t為巷道內儲位編號，t∈T，n表示巷道總數；W表示托盤i的到達順序，i∈I；slotr，t表示第r巷道，t儲位的位置；M為大數，M？垌0；

（2）中間變量和決策變量：Y，0～1變量，t，k∈T， kgt;t，若slotr，t的托盤編號比slotr，k托盤編號小，Y=1，否則Y=0；X，0～1變量，若托盤i放置在位置slotr，t，X=1，否則X=0。

1.4 "數學模型。以最小化翻箱數為目標函數的儲位分配模型如下：

minf=Y " " " " " " " " " " " " " " " " " " " " " "（1）

s.t.

X=1， ？坌i∈I " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " （2）

X≤1， ？坌r∈R， t∈T " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " （3）

X≥X， ？坌r∈R， t∈T＼1 " " " " " " " " " " " " " " " " " " " " " " " " "（4）

X≤mn " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " （5）

W·X+1-XM≥W·X， ？坌r∈R， t∈T＼1 " " " " " " " " " " " " " " " （6）

i·X+1-X-i·X+Y·M≥0， ？坌r∈R， t∈T， k∈T， kgt;t " " " " " " " " " " " "（7）

X∈0，1， ？坌i∈I， r∈R， t∈T " " " " " " " " " " " " " " " " " " " " " " " " " " " "（8）

Y∈0，1， ？坌r∈R， t∈T， k∈T， kgt;t " " " " " " " " " " " " " nbsp; " " " " " " " " " " "（9）

式（1）為目標函數，表示最小化裝車產生的翻箱數；式（2）表示一個托盤只能位于一個儲位；式（3）表示一個儲位最多放置一個托盤；式（4）確保同一巷道中托盤緊挨存儲；式（5）表示托盤數量不超過四向穿梭車緊湊存儲系統容量；式（6）表示同一巷道中儲位值較小的位置優先存儲托盤；式（7）表示決策變量滿足的約束條件，若slotr，t的托盤編號比slotr，k放置托盤編號小，計為1次翻箱；式（8）和式（9）分別定義了決策變量和中間變量的取值范圍。

2 "算法設計

"本文設計IGA（Improved Genetic Algorithm）求解托盤儲位分配問題，考慮同一布局的系統滿載率不固定造成存儲托盤數變動，染色體長度隨托盤數改變，因此對全部儲位進行整數編碼；同時引入啟發式規則生成初始種群加快收斂速度；采用精英保留和輪盤賭混合的選擇策略，調整子代種群中精英個體的比例，平衡質量和多樣性之間的關系；并將交叉和變異過程設定為一定會生成新個體，稱之為交叉體和變異體。如圖3所示，第gen+1代種群由三部分組成：（1）精英染色體直接保留；（2）選擇兩個父代交叉產生的交叉體；（3）選擇父代新生成的變異體。根據提出問題的特點改進了傳統遺傳算法的不足，旨在獲得更高質量的可行解，IGA流程設計如圖4所示。

2.1 "染色體編碼。編碼方式采用整數編碼，染色體長度為FSS/RS總儲位數，染色體的一個基因位對應一個儲位，基因為儲位放置托盤的裝車順序值，0表示此位置不存儲托盤。如圖5所示，系統布局為巷道數m=2，巷道深位n=5，有9個帶有編號的托盤依次存入，染色體為6，3，1，9，0，7，5，2，8，4，位置Slot1，1放置裝車順序為6的托盤。

2.2 "初始種群。生成解的過程如下：

"Step1：根據現存托盤狀態確定可存巷道集合；

Step2：在可存巷道集合中，將擬存儲托盤與每個巷道最后存入托盤編號依次比較，選擇比擬存儲托盤編號大且數值最接近的托盤所在巷道存入；否則返回Step1，直接對下一個托盤執行操作；

"Step3：對所有托盤重復以上操作；

Step4：將剩余托盤隨機分配儲位，直到所有托盤均完成入庫。

2.3 "可行性修復。結合模型中對托盤到達順序的約束易產生不可行解，設計一種適合本問題的修復操作。根據圖6所示的映射關系，首先將不可行解一一對應為到達順序，然后在每個巷道內按照編號從小到大進行修復，如圖7所示，在第2個巷道中5、7、4不可行，將其修復為4、5、7，再轉換成裝車順序得到可行解。

2.4 "選擇操作。選擇操作采用精英保留和輪盤賭相結合的策略，首先計算pop_size個染色體的適應度值并對其排序，選擇α

·pop_size適應度高的染色體作為精英個體，直接復制到子代種群，防止種群中適應度高的個體在下一代丟失。剩余1-α

·pop_size個染色體均采用輪盤賭方式選擇，以保證適應度高的個體更容易被選中，使種群向好的方向進化，提高解的質量。

2.5 "交叉操作。針對問題特征，在傳統順序交叉[14]的基礎上進行三點改進。第一，隨機選擇父代中幾個基因時位置可不連續，但兩個父代被選交叉點位置相同；第二，將代表一個巷道的連續等位基因作為一個片段，每個片段只選擇一個交叉點，隨機選擇的交叉點數量與巷道總數m相同，每個交叉點位置都是從區間1，n隨機生成的整數，例如圖8中m=2， n=5，隨機生成兩個整數為3和1，則對應到染色體的位置為3和6；第三，在順序交叉前加入隨機交換巷道操作，隨機交換片段在染色體的位置組成新染色體，避免染色體高度相似下交叉無效。改進的順序交叉算子具體步驟如下：

"Step1：從父代隨機選擇m個交叉點；

"Step2：將父代2被選擇的基因復制到子代1；

"Step3：子代1其余基因按照父代1中的順序依次復制，如果已經插入則排除該值，直到所有位置都被填滿；

"Step4：子代2同理。

"交叉操作示意圖如圖8所示。

2.6 "變異操作。變異操作采用多點變異，變異點數量與染色體長度成正比。與交叉隨機選點的方式相同，代表一個巷道的染色體片段只選擇一個基因，隨機選擇的基因數隨機重排得到子代，如圖9所示。

2.7 "進化逆轉。為了提高遺傳算法的局部尋優能力，在選擇、交叉和變異操作后加入進化逆轉。如圖10所示，隨機產生染色體長度范圍內的兩個隨機整數，染色體被分成三個片段，選擇中間一個片段發生斷裂再逆轉插入原位置。在進化逆轉操作中，只接受使適應度值提高的逆轉，否則逆轉無效[15]。

3 "數值實驗

3.1 "實驗設計。考慮裝車順序的FSS/RS儲位分配問題由實際業務演變而來，目前還沒有權威的文獻和數據可以用來驗證模型和算法的有效性。本文結合武漢市L企業實際業務場景和數據結構，進行一般化處理，根據總儲位數m·n模擬生成三種規模的算例對比分析。針對每一種系統布局和空位數，取100個算例的均值得到平均翻箱數AT（Average Turnovers）。具體算例參數見3.2節。

"算法利用MATLAB 2018a軟件編碼，操作系統為Windows11，所得結果均出于Intel（R）Core（TM）i5-10210U CPU@1.60GHz 2.11 GHz平臺，并使用CPLEX 12.8對調度模型進行求解，求解時間設定7 200s停止。經初步測試，選擇種群規模pop_size=100，最大迭代次數gen_max=100～500，精英比例α=0.4，交叉比例β=0.1，變異比例γ=0.5。最大迭代次數與總儲位數m·n相關，當0lt;m·n≤100時，gen_max=500；當100lt;m·n≤1 000時，gen_max=300；當1 000lt;m·n≤10 000時，gen_max

=100，而其他參數設置值不隨規模大小變化。

3.2 "算法性能分析。為驗證IGA在求解儲位分配調度問題的性能，在不同系統布局和空位下隨機生成小規模算例，與CPLEX精確解進行對比實驗。系統布局3～5個巷道數，巷道深位均為5；空位數量1或2個儲位，即入庫托盤數分別為14～24不等。求解結果如表1所示，Eff/All表示設定時間范圍內CPLEX可得到精確解的算例與所有算例比值，ACT（Average CPU Time）表示100個算例的平均CPU時間。IGA求得的函數值與CPLEX得到的精確解之間的最小差距GAP僅為0.25%，最大為5.83%，在可接受范圍之內；當布局擴大到5個巷道、1個空位時，CPLEX在規定時間范圍內只能獲得98次計算結果，而IGA仍可以在比較短的時間內得到全部近似最優解，且運行時間均小于或等于CPLEX，如圖11所示。可以看出，IGA在求解儲位分配問題時，同時具備求解時間短、求解效果好的性能。

為了進一步驗證IGA算法求解性能，對L企業實際應用的啟發式算法EDA（Empirical Decision Algorithms）進行比較。EDA是由該企業算法工程師依據現場工作經驗設計的啟發式算法，即存儲每個托盤時，找到當前存儲狀態下與擬存入托盤的裝車順序最接近的托盤，然后在其臨近位置緊挨存儲。以總儲位數m·n和空位數為基準生成26種算例，圖12顯示了IGA相對于EDA對AT的優化程度，具體數據如表2所示，得到實驗結論如下：（1）同一種規模和系統布局下，隨空位增加GAP越來越小；（2）同一種規模和空位數時，算例的系統布局越大GAP越小，中小規模時IGA算法優勢更明顯，滿足實際應用需求。

4 "結 "論

"本文在裝車順序信息已知的基礎上，構建了FSS/RS整數規劃儲位分配的模型，設計改進遺傳算法IGA進行求解，并在不同系統規模下與企業現有經驗決策的EDA算法進行對比實驗。實驗結果表明：與CPLEX相比，IGA算法求解時間短、求解效果好；與企業所用EDA算法相比，IGA使得裝車階段的平均翻箱數減少33.58%，且中小規模時使用效果更好。

參考文獻：

[1] "BOYSEN N， DE KOSTER R， WEIDINGER F. Warehousing in the e-commerce era： A survey[J]. European Journal of Operational Research， 2019，277（2）：396-411.

[2] 王婷. 穿梭車式密集倉儲系統資源配置優化研究[D]. 西安：陜西科技大學，2019.

[3] 田彬，吳穎穎，吳耀華，等. “四向車”揀選系統訂單排序優化[J]. 機械工程學報，2019，55（18）：225-232.

[4] "LIYUN X， CONG L， XIANGNAN Z， et al. Task scheduling for Tier-to-tier Four-way shuttle warehousing system[J]. Procedia CIRP， 2021，104：1083-1088.

[5] "REVILLOT-NARV？魣EZ D， P？魪REZ-GALARCE F， ？魣LVAREZ-MIRANDA E. Optimising the storage assignment and order-picking for the compact drive-in storage system[J]. International Journal of Production Research， 2020，58（22）：6949-6969.

[6] "ZAERPOUR N， YU Y， DE KOSTER， et al. Storing fresh produce for fast retrieval in an automated compact cross-dock system[J]. Production and Operations Management， 2015，24（8）：1266-1284.

[7] "BOYWITZ D， BOYSEN N. Robust storage assignment in stack-and queue-based storage systems[J]. Computers amp; Operations Research， 2018，100：189-200.

[8] "BOYSEN N， BOYWITZ D， WEIDINGER F. Deep-lane storage of time-critical items： One-sided versus two-sided access[J]. OR Spectrum， 2018，40（4）：1141-1170.

[9] "CHEN L， LU Z. The storage location assignment problem for outbound containers in a maritime terminal[J]. International Journal of Production Economics， 2012，135（1）：73-80.

[10] "GHAREHGOZLI A H， YU Y， DE KOSTER R， et al. A decision-tree stacking heuristic minimising the expected number of reshuffles at a container terminal[J]. International Journal of Production Research， 2014，52（9）：2592-2611.

[11] 劉嬋娟，胡志華. 集裝箱堆場出口箱箱位分配多目標優化模型[J]. 大連理工大學學報，2015（6）：589-596.

[12] "HE Y， WANG A， SU H. The impact of incomplete vessel arrival information on container stacking[J]. International Journal of Production Research， 2020，58（22）：6934-6948.

[13] "GHAREHGOZLI A， ZAERPOUR N. Stacking outbound barge containers in an automated deep-sea terminal[J]. European Journal of Operational Research， 2018，267（3）：977-995.

[14] "P KORA， P YAERLAPALLI. Crossover operators in genetic algorithms： A review[J]. Intemational Journal of Computer Applications， 2017，162（10）：34-36.

[15] "VARUN KUMAR S G， PANNEERSELVAM R. A study of crossover operators for genetic algorithms to solve VRP and its variants and new sinusoidal motion crossover operator[J]. International Journal of Computational Intelligence Research， 2017，13（7）：1717-1733.