王玉聰，何杰明，廖云飛

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

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

1 問題及模型

1.1 問題描述

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

1.2 模型假設(shè)

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

1.3 模型建立

1.3.1 符號

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

表1 符號所表示的含義

表1（續(xù)）

1.3.2 模型

1.3.2.1 目標(biāo)1：等待時(shí)間最短

整個(gè)系統(tǒng)的等待時(shí)間可分為2部分：①任務(wù)的等待時(shí)間，即貨物到達(dá)交接區(qū)后，為等待交接所停留的時(shí)間；②設(shè)備的等待時(shí)間，即設(shè)備完成上一任務(wù)至接收到下一任務(wù)間的空閑時(shí)間。式（1）表示了等待時(shí)間最短這一目標(biāo)，式（2）—式（4）分別給出了出入庫提升機(jī)和多穿車的等待時(shí)間的計(jì)算方法。

1.3.2.2 目標(biāo)2：移動距離最短

經(jīng)簡單分析，發(fā)現(xiàn)出入庫提升機(jī)的移動均為往返運(yùn)動，任務(wù)確定后則移動確定，故移動距離的優(yōu)化只涉及多穿車。式（5）表示了多穿車移動距離最短這一目標(biāo)，須根據(jù)任務(wù)的先后順序，分別對移動距離進(jìn)行討論。

該模型同時(shí)考慮貨物和設(shè)備的等待時(shí)間以及設(shè)備的移動距離，為雙目標(biāo)規(guī)劃問題。為方便求解，利用復(fù)合函數(shù)將雙目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題，這里取2個(gè)目標(biāo)的線性組合作為最終考慮的目標(biāo)。

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

數(shù)學(xué)模型具體如下。

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

1.3.2.4 線性化

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

對于max函數(shù)部分，由于非線性部分的結(jié)構(gòu)相似，為方便表示，表示如下：

根據(jù)max函數(shù)的線性化方法，式（33）可等價(jià)轉(zhuǎn)化為線性約束組，即式（35）—式（40），具體如下：

同理，式（34）也可等價(jià)轉(zhuǎn)化為一組線性約束。

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

根據(jù)相關(guān)線性化方法，式（41）可等價(jià)轉(zhuǎn)化為線性約束組，即式（42）—式（45）。

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

2 算法設(shè)計(jì)

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

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

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

2.1 編碼

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

2.2 初始種群

本文采用隨機(jī)生成的方式，根據(jù)預(yù)設(shè)的種群規(guī)模，隨機(jī)生成相應(yīng)數(shù)量的個(gè)體組成初始種群。

2.3 適應(yīng)度函數(shù)

基于模型的目標(biāo)函數(shù)，規(guī)定對于任意個(gè)體i的適應(yīng)度函數(shù)為：

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

2.4 選擇算子

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

2.5 交叉算子

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

2.6 變異算子

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

2.7 模擬退火接收準(zhǔn)則

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

3 實(shí)驗(yàn)結(jié)果

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

3.1 算例及參數(shù)

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

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

表2 參數(shù)表

3.2 實(shí)驗(yàn)結(jié)果

對于每種算例，將遺傳算法運(yùn)行5次，取其中的最優(yōu)解，表3為遺傳算法求解各類算例的平均結(jié)果。可見，遺傳算法的求解效率遠(yuǎn)高于求解器。

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

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

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

4 結(jié)論

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

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