儲分一體倉中多穿車復合作業順序優化問題研究＊

王玉聰，何杰明，廖云飛

（1.天津大學管理與經濟學部，天津 300072；2.廣東煙草惠州市有限責任公司，廣東 惠州 516003；3.中國煙草總公司廣東省公司，廣東 廣州 510620）

近年來，隨著經濟社會的發展和互聯網的普及，網上購物已經進入尋常百姓家，這給中國的物流倉儲業提出了更高的要求。傳統人工作業耗時又耗力，已無法滿足當前物流中心的運作需求，自動化的智能倉庫應運而生?；诙啻┸囘\行的儲分一體倉是新型智能倉的一種，利用多穿車代替人工完成存取貨工作，極大地提高了倉儲運作系統的效率和準確率。多穿車的調度是儲分一體倉的運行關鍵，由于訂單和貨物較為零散，又涉及多穿車和提升機的相互作用，如何優化調度使得系統的效率最高，成為企業和學者關注的問題。

1 問題及模型

1.1 問題描述

本文研究了一個儲分一體倉的多穿車存取貨任務順序優化問題。已知某物流配送中心的儲分一體倉貨架有m層n列（共m×n個貨位），貨位的長度為l、高度為h，每個貨位可存放一個托盤。貨架的每一層均配有一臺多穿車，所有多穿車完全相同，多穿車只需完成本層的出入庫任務。貨架的前后兩端分別設有出入庫平臺（在貨架的底層）和出入庫提升機軌道，多穿車與提升機在每層的交接區進行貨物交接，提升機負責貨物在豎直方向的運輸。出入庫提升機與多穿車的移動速率分別為vx、vy和vz，所有設備每次均只能搬運一個托盤。現有一批待入庫和待出庫的任務單，已知任務與貨位一一對應。該問題的目標是，合理規劃出入庫任務的調度順序，綜合考慮任務和設備的等待時間和多穿車的移動距離，使得儲分一體系統整體作業效率最高。

1.2 模型假設

不考慮貨架上的實際存貨情況，即默認入庫任務對應的貨位為空貨位，出庫任務對應的貨位存有貨物。出入庫提升機和多穿車均為勻速移動，移動速率為已知常數。不考慮出入庫提升機和多穿車的啟動和制動過程，忽略裝卸貨時間。不考慮托盤（貨物）的實際大小，貨位間距即為出入庫和多穿車的移動距離。任務開始前，多穿車的初始位置在貨架入庫提升機一側，所有任務完成后，多穿車須返回初始位置。

1.3 模型建立

1.3.1 符號

符號代表的含義如表1所示。

表1 符號所表示的含義

表1（續）

1.3.2 模型

1.3.2.1 目標1：等待時間最短

整個系統的等待時間可分為2部分：①任務的等待時間，即貨物到達交接區后，為等待交接所停留的時間；②設備的等待時間，即設備完成上一任務至接收到下一任務間的空閑時間。式（1）表示了等待時間最短這一目標，式（2）—式（4）分別給出了出入庫提升機和多穿車的等待時間的計算方法。

1.3.2.2 目標2：移動距離最短

經簡單分析，發現出入庫提升機的移動均為往返運動，任務確定后則移動確定，故移動距離的優化只涉及多穿車。式（5）表示了多穿車移動距離最短這一目標，須根據任務的先后順序，分別對移動距離進行討論。

該模型同時考慮貨物和設備的等待時間以及設備的移動距離，為雙目標規劃問題。為方便求解，利用復合函數將雙目標問題轉化為單目標問題，這里取2個目標的線性組合作為最終考慮的目標。

1.3.2.3 數學模型

數學模型具體如下。

式（16）—式（31）中：式（6）為目標函數，表示最小化等待時間和設備移動距離；式（7）—式（9）描繪了某一任務的開始時刻；式（10）—式（14）描繪了某一任務到達交接區的時刻；式（15）—式（18）描繪了某一任務在交接區的等待時間；式（19）—式（20）描繪了某一任務的完成時刻；式（21）—式（23）表示每個任務只能由一臺出入庫提升機和多穿車完成一次；式（24）—式（28）確保出入庫提升機和每層多穿車的任務范圍，即出庫提升機只完成出庫任務，入庫提升機只完成入庫任務，每層的多穿車只完成本層的任務；式（29）—式（31）為決策變量的取值范圍。

1.3.2.4 線性化

由于該模型存在非線性的目標函數和約束條件，無法使用求解器直接求解，因此需要線性化。模型中的非線性表達式分為2種，max函數和0-1變量與連續變量相乘，分別出現于目標函數公式（2）—公式（4）和約束條件公式（15）（16）（18）中，通過引入輔助變量μ、u和δ對其進行線性化操作。

對于max函數部分，由于非線性部分的結構相似，為方便表示，表示如下：

根據max函數的線性化方法，式（33）可等價轉化為線性約束組，即式（35）—式（40），具體如下：

同理，式（34）也可等價轉化為一組線性約束。

對于0-1變量與連續變量相乘的部分，以式（2）為例，式（2）所表達的含義等價于以下公式，即：

根據相關線性化方法，式（41）可等價轉化為線性約束組，即式（42）—式（45）。

同理，式（3）和式（4）也可分別轉化為一組線性約束。

2 算法設計

本文研究的多穿車存取貨路徑規劃問題較為復雜，不論是目標函數還是約束條件中均包含非線性的部分，即使采用一些轉化方法將其線性化，使得求解器可直接對模型進行求解，但隨著問題規模的增加，求解難度增加，求解器難以在有限時間內得出最優解。遺傳算法是一種仿照生物遺傳進化而提出的基于種群的啟發式算法，被廣泛應用于生車間調度、組合優化、路徑優化等問題中，為了提高求解效率，本文采用遺傳算法對大規模問題進行求解。

本文所使用的考慮模擬退火的遺傳算法基本流程如圖1所示。

圖1 考慮模擬退火的遺傳算法流程圖

2.1 編碼

本文采用順序編碼方式，為每個出入庫任務編號，每個任務即為一個基因，一個個體即為一個出入庫方案，其編碼順序即為一個可實施的任務完成順序。例如某次任務共包含10個出入庫任務，分別編號為1—10，則個體[7 8 5 3 10 1 9 2 4 6]表示以7—8—5—3—10—1—9—2—4—6的順序依次完成相應任務。

2.2 初始種群

本文采用隨機生成的方式，根據預設的種群規模，隨機生成相應數量的個體組成初始種群。

2.3 適應度函數

基于模型的目標函數，規定對于任意個體i的適應度函數為：

可以看出，某個方案完成出入庫任務時的效率越低（等待時間長、多穿車移動距離長），則目標函數越大，該個體的適應度越小，能夠遺傳給下一代的概率越小。

2.4 選擇算子

選擇算子用于從種群中選出進行交叉和變異的父代個體，這里采用輪盤賭的方法，根據種群中個體的適應度，按一定的概率隨機選取，適應度越高的個體被選中作為父代的概率越大。

2.5 交叉算子

交叉算子仿照的是遺傳學中基因重組，即將選中的2個父代個體的基因按一定規則交叉重組后，遺傳給子代。本文采用了幾種經典交叉算子，包括部分匹配交叉、循環交叉、次序交叉、基于位置交叉和替換交叉算子。

2.6 變異算子

變異算子仿照的是遺傳學中的基因突變，即按照一定規則改變某個體的一個或幾個基因。本文采用的變異算子包括替換變異、交換變異、簡單倒位變異、倒位變異和爭奪變異。

2.7 模擬退火接收準則

在整個遺傳算法的迭代過程中，考慮模擬退火的接受原則。當經過交叉和變異產生的子代個體適應度小于種群中適應度最小的個體時，則按照的概率接受子代個體加入種群，并將原種群中適應度最小的個體移出，其中Ef為子代個體的適應度的倒數（即對應方案的效率）；Eworst為當前種群中最小的適應度的倒數；T為溫度，T0=0.85×Eworst0，溫度以λ（0＜λ＜1）的速率下降。

3 實驗結果

為驗證算法和模型的有效性，本文隨機生成了一些算例，通過JAVA調用求解器和編寫遺傳算法，對問題進行求解。調用的求解器為IBMILOG CPLEX 12.8，運行環境為Intel（R）Core（TM）i5-6200U CPU@2.30 GHz 2.40 GHz處理器和4 GB內存計算機。

3.1 算例及參數

根據實際情況，設貨架共包含12層，每層16組通道，每組5個，通道寬0.5 m，由于一組通道放置一種卷煙，這里將一組通道看作一個長2.5 m的貨位，層高為0.3 m。出入庫提升機的移動速率為1 m/s，多穿車的移動速率為2 m/s。

隨機生成一批出入庫混合任務及其對應貨位的坐標。除隨機擺放的算例外，根據貨物在豎直方向集中擺放位置，即上（H）、中（M）和下（L），將算例分為3類；根據貨物在水平方向集中擺放的位置，即左（L_）、中（M_）和右（R_），將算例分為另外3類，每個算例包含100個任務。其他各參數設置如表2所示。

表2 參數表

3.2 實驗結果

對于每種算例，將遺傳算法運行5次，取其中的最優解，表3為遺傳算法求解各類算例的平均結果。可見，遺傳算法的求解效率遠高于求解器。

表3 遺傳算法求解各類算例的平均結果

圖2為不同貨物擺放情況的算例的求解結果對比。從圖2中可以看出，貨物擺放對多穿車的移動距離影響不大，L_類算例，即貨物集中擺放于貨架左側時，多穿車的移動距離較其他算例略少。L_、M_、R_類算例的等待時間普遍長于H、M、L類算例，說明貨物在豎直方向擺放越分散，可能導致等待時間越長；而L_、M_、R_類算例等待時間依次遞增，說明貨物集中在貨架左側時的等待時間較短，集中在貨架右側時的等待時間較長。整體上來看，L類算例的求解結果較好，因此若貨位多于貨物量，應優先放置于貨架下部，能夠獲得最高的運作效率。

圖2 不同貨物擺放情況的算例的求解結果對比

4 結論

本文研究了儲分一體倉中單層多穿車的復合作業優化問題，用出入庫任務和設備的共同等待時間和多穿車的移動距離來衡量系統的效率，旨在通過優化，找出使系統效率最高的作業順序?；诙啻┸嚨淖鳂I流程，建立了相應的數學優化模型，通過隨機生成的算例對模型進行求解。由于模型較為復雜，本文使用了一種考慮模擬退火的遺傳算法對問題進行求解。

通過設置貨物不同的擺放位置，生成7類不同的算例，對比實驗結果發現，貨物擺放對多穿車的移動距離影響不大，但貨物在豎直方向擺放越分散（即占用的層數越多），總的等待時間會越長，總體來看，貨物集中于貨架左下側時系統的效率最高。