自動(dòng)化立體倉(cāng)庫(kù)中出入庫(kù)任務(wù)順序與出庫(kù)位置選擇集成優(yōu)化研究

韓東亞，陳 然，余玉剛，郭曉龍

(中國(guó)科學(xué)技術(shù)大學(xué)管理學(xué)院，安徽 合肥 230026)

1 引言

近年來(lái)，隨著電子商務(wù)的高速發(fā)展，以阿里、京東和蘇寧為首的電商企業(yè)迅猛崛起，我國(guó)的自動(dòng)倉(cāng)儲(chǔ)系統(tǒng)市場(chǎng)呈現(xiàn)穩(wěn)步高速增長(zhǎng)態(tài)勢(shì)，傳統(tǒng)的批量化、單一化產(chǎn)品越來(lái)越難以滿足消費(fèi)者的需求。電商物流呈現(xiàn)出訂單數(shù)目大、海量SKU、訂單時(shí)效性高、隨季節(jié)波動(dòng)性大的特點(diǎn)。傳統(tǒng)的自動(dòng)化立體倉(cāng)庫(kù)需要先使用堆垛機(jī)取出整托盤貨物，然后將整托盤通過(guò)傳送帶送至分揀系統(tǒng)。取貨人員按照訂單從整托盤中取出所需數(shù)量的貨物，并將托盤放回至傳送帶使其入庫(kù)。托盤在傳送帶往往花費(fèi)大量的等待時(shí)間，分揀作業(yè)效率低下，無(wú)法滿足電商物流中多品種、小批量的消費(fèi)需求。

多出庫(kù)位置的自動(dòng)化立體倉(cāng)庫(kù)(Automated Storage and Retrieval System with Multiple In-the-Aisle Pick Positions, 簡(jiǎn)稱ASRS-MIAPP)是一種新型的倉(cāng)庫(kù)技術(shù)，能有效地改善上述分揀作業(yè)效率低下的問(wèn)題。與傳統(tǒng)的單出入口自動(dòng)化倉(cāng)庫(kù)不同，ASRS-MIAPP在貨架底層有多個(gè)出庫(kù)位置，可被視為單入口多出口的倉(cāng)庫(kù)系統(tǒng)。ASRS-MIAPP中有兩種類型的過(guò)道：揀選過(guò)道和堆垛機(jī)過(guò)道。其中揀選過(guò)道比堆垛機(jī)過(guò)道略寬，為取貨人員提供移動(dòng)空間進(jìn)行貨物揀選。ASRS-MIAPP能夠有效地將存儲(chǔ)和分揀作業(yè)集成在一起，既減少了占地面積，提高了空間利用率，減少能量損耗，同時(shí)又能減少工人數(shù)量，降低人力成本。目前已得到眾多國(guó)際知名公司，如Publix Super Markets, Wal-Mart, Walkers, Ferrero GmbH等的廣泛使用[1]。

在ASRS-MIAPP中，出入庫(kù)任務(wù)的合理調(diào)度，對(duì)整個(gè)系統(tǒng)整體運(yùn)作起著至關(guān)重要的作用。當(dāng)出入庫(kù)任務(wù)的完成順序選擇較差時(shí)，堆垛機(jī)運(yùn)作的距離會(huì)變大，既延誤了完成下一批任務(wù)的時(shí)間，也延誤了出庫(kù)貨物到達(dá)顧客的時(shí)間，對(duì)企業(yè)造成不好的影響。同時(shí)，出口貨物釋放到出口的位置，也會(huì)影響到堆垛機(jī)完成兩個(gè)連續(xù)任務(wù)的運(yùn)作距離。因此，出入庫(kù)任務(wù)的調(diào)度和出庫(kù)位置的選擇，是緊密相連的聯(lián)合決策問(wèn)題。然而，隨著問(wèn)題規(guī)模的擴(kuò)大，求解難度急劇上升，如何快速求得最優(yōu)解或近似最優(yōu)解至關(guān)重要。

目前，針對(duì)自動(dòng)化立體倉(cāng)庫(kù)系統(tǒng)運(yùn)作績(jī)效問(wèn)題，國(guó)內(nèi)外有很多學(xué)者進(jìn)行了研究。Roodbergen和Vis[2]，Gagliardi等[3]，Boysen和Stephan[4]從不同的角度對(duì)現(xiàn)有研究進(jìn)行了綜述分析。Roodbergen和Vis[2]提出可以通過(guò)四種控制決策包括存儲(chǔ)策略、批處理、堆垛機(jī)停頓點(diǎn)策略和出入庫(kù)調(diào)度策略等來(lái)有效地提高自動(dòng)化立體倉(cāng)庫(kù)的績(jī)效。Han等[5]指出，自動(dòng)化立體倉(cāng)庫(kù)存取順序問(wèn)題類似于旅行商問(wèn)題。對(duì)于動(dòng)態(tài)環(huán)境下的存取順序問(wèn)題，可以通過(guò)兩種方法來(lái)解決：塊調(diào)度和動(dòng)態(tài)調(diào)度。塊調(diào)度是指選擇一個(gè)塊，對(duì)其中的所有出入庫(kù)任務(wù)進(jìn)行調(diào)度，當(dāng)此塊內(nèi)的所有作業(yè)全部完成后，再進(jìn)行下一個(gè)塊調(diào)度；而動(dòng)態(tài)調(diào)度則是指每次有新的任務(wù)加入時(shí)對(duì)所有任務(wù)重新排序，采用截止日期優(yōu)先的方式，確保不會(huì)過(guò)度延遲出庫(kù)任務(wù)。Lee和Schaefer[6]研究了一種特殊情況，即系統(tǒng)中的任意空位均可作為存貨位置使用，作者首先求解一個(gè)線性指派模型，然后使用排序算法求解，此算法在空位數(shù)量較小時(shí)可以找到系統(tǒng)最優(yōu)解。在Lee和Schaefer[7]的另一項(xiàng)研究中，根據(jù)先來(lái)先服務(wù)(FCFS)規(guī)則操作入庫(kù)任務(wù)，而通過(guò)指派問(wèn)題的算法優(yōu)化出庫(kù)任務(wù)順序。Chen等[8]在考慮每個(gè)單元負(fù)載的停留持續(xù)時(shí)間的情形下建立混合整數(shù)模型，并構(gòu)造啟發(fā)式以及禁忌搜索算法解決此問(wèn)題。Eynan和Rosenblatt[9]提出最近鄰域搜索算法并應(yīng)用于分類存儲(chǔ)策略中。Gharehgozli等[10]針對(duì)具有兩個(gè)進(jìn)出口的自動(dòng)化立體倉(cāng)庫(kù)提出了一種多項(xiàng)式時(shí)間的算法解決出入庫(kù)調(diào)度問(wèn)題。

以上研究均假設(shè)堆垛機(jī)每次只能存取一個(gè)負(fù)載單元，與之相反，雙梭立體倉(cāng)庫(kù)可以一次存(或取)兩個(gè)負(fù)載單元，因此，出入庫(kù)任務(wù)的組合更多更復(fù)雜。Keserla和Peters[11]用基于最小周長(zhǎng)的優(yōu)先規(guī)則方法解決雙梭立體倉(cāng)庫(kù)調(diào)度問(wèn)題。Sarker等[12,13]針對(duì)類似的問(wèn)題提出了基于最近鄰的簡(jiǎn)單啟發(fā)式方法。Yang Peng等[14]則研究多梭立體倉(cāng)庫(kù)調(diào)度問(wèn)題，建立了混合整數(shù)模型并用可變鄰域搜索方法求解。對(duì)于類似的問(wèn)題，一個(gè)兩階段禁忌搜索方法和遺傳算法結(jié)合修改最近鄰啟發(fā)法分別在文獻(xiàn)[15]和[16]中給出。目前很少有學(xué)者針對(duì)ASRS-MIAPP系統(tǒng)進(jìn)行研究，Ramtin和Pazour[17]在隨機(jī)存儲(chǔ)策略下，建立了堆垛機(jī)行走時(shí)間模型，分析不同系統(tǒng)尺寸，不同系統(tǒng)構(gòu)造(單層多出庫(kù)位置和雙層多出庫(kù)位置)對(duì)系統(tǒng)績(jī)效的影響。Ramtin和Pazour[1]考慮了不同需求曲線下貨物的存儲(chǔ)問(wèn)題，在假設(shè)有無(wú)限多的出庫(kù)位置下，他們建立了連續(xù)的數(shù)學(xué)模型，并與離散事件仿真的結(jié)果作對(duì)比，發(fā)現(xiàn)只有0.1%的差距，驗(yàn)證了此連續(xù)模型的有效性。

國(guó)內(nèi)學(xué)者也對(duì)自動(dòng)化立體倉(cāng)庫(kù)的運(yùn)作績(jī)效進(jìn)行了深入的研究。田國(guó)會(huì)等[18]考慮自動(dòng)化立體倉(cāng)庫(kù)固定貨架系統(tǒng)中出入庫(kù)策略優(yōu)化問(wèn)題，提出了一種新的自適應(yīng)啟發(fā)式方法，使用最近點(diǎn)搜索算法獲得初始種群的解，然后進(jìn)行逐步迭代，結(jié)果表明算法能在較短的時(shí)間里獲得很好的解。王雯等[19]提出一種基于層次分析法和遺傳算法相結(jié)合的出入庫(kù)調(diào)度優(yōu)化算法，并使用仿真的方式驗(yàn)證了算法的有效性。劉韜等[20]采用面向?qū)ο蟮馁x時(shí)Petri網(wǎng)研究了出入庫(kù)調(diào)度問(wèn)題，建立了數(shù)學(xué)模型，并分析了該模型的死鎖問(wèn)題。鄧愛(ài)民等[21]以醫(yī)藥倉(cāng)庫(kù)為例，建立了基于時(shí)間的多目標(biāo)貨位優(yōu)化模型，并使用遺傳算法求解模型。李鵬飛和馬航[22]以出入庫(kù)效率和貨架穩(wěn)定性作為優(yōu)化目標(biāo)建立數(shù)學(xué)模型，采取病毒協(xié)同遺傳算法進(jìn)行仿真對(duì)比，結(jié)果顯示此算法能夠獲得較好的解。靳萌等[23]針對(duì)軍用維修器材倉(cāng)庫(kù)，提出了考慮物資周轉(zhuǎn)率和相關(guān)性的貨位優(yōu)化模型，并設(shè)計(jì)了一套基于Pareto保持和模擬退火的算法，驗(yàn)證了此模型的有效性。劉臣奇等[24]構(gòu)建了貨物揀選路徑問(wèn)題的優(yōu)化模型，提出了改進(jìn)的蟻群算法，結(jié)果顯示該算法相較于基本蟻群算法收斂速度顯著提高，具有很好的可行性。常發(fā)亮等[25]考慮了周轉(zhuǎn)貨箱的容量限制，根據(jù)自動(dòng)化倉(cāng)庫(kù)貨物揀選的特點(diǎn)建立了數(shù)學(xué)模型，用遺傳算法對(duì)該模型進(jìn)行求解，數(shù)值結(jié)果表明此算法高效可靠。

本文與以上學(xué)者研究的區(qū)別在于(1)本文研究一個(gè)單入口、多出口的自動(dòng)化立體倉(cāng)庫(kù)，因此即需要考慮出入庫(kù)任務(wù)的操作順序，也要考慮出庫(kù)任務(wù)被分配到哪一個(gè)出庫(kù)位置的問(wèn)題。而以上學(xué)者主要研究單入口單出口的倉(cāng)儲(chǔ)系統(tǒng)，只需要考慮出入庫(kù)任務(wù)的操作順序既可。(2)目前研究此系統(tǒng)的文獻(xiàn)聚焦于系統(tǒng)績(jī)效，以及貨物存儲(chǔ)策略方面的研究，本文首次研究此系統(tǒng)出入度調(diào)度策略問(wèn)題。

2 出入庫(kù)調(diào)度與出庫(kù)位置選擇集成優(yōu)化模型

2.1 問(wèn)題描述

本文的問(wèn)題可以描述為：在一個(gè)多出口位置的自動(dòng)化立體倉(cāng)庫(kù)(如圖1所示)中，有一系列貨物等待存儲(chǔ)，同時(shí)還有一系列貨物等待取出。堆垛機(jī)既可以每次只完成一個(gè)入(或出)庫(kù)任務(wù)，也可以每次先完成入庫(kù)任務(wù)，再完成出庫(kù)任務(wù)。

圖1 ASRS-MIAPP示意圖，左圖為左視圖，右圖為側(cè)視圖(引自Ramtin和Pazour[1])

上述堆垛機(jī)操作過(guò)程中存在以下特點(diǎn)：

(1)入庫(kù)任務(wù)順序約束：一般來(lái)說(shuō)，需要存放的貨物會(huì)在傳送帶上等待堆垛機(jī)完成入庫(kù)任務(wù)。由于很難在傳送帶上改變待存放貨物的位置，因此入庫(kù)任務(wù)按照先到先服務(wù)的模式進(jìn)行。

(2)多種出入庫(kù)路徑情形：我們考慮堆垛機(jī)的停頓點(diǎn)策略為停留策略，即堆垛機(jī)會(huì)在完成出庫(kù)(或入庫(kù))任務(wù)的位置處停留，等待下一個(gè)任務(wù)。當(dāng)完成的任務(wù)為入庫(kù)任務(wù)時(shí)，堆垛機(jī)會(huì)停留在完成上架的標(biāo)準(zhǔn)化托盤所在的位置上；當(dāng)完成的任務(wù)為出庫(kù)任務(wù)時(shí)，堆垛機(jī)會(huì)停留在完成出庫(kù)的標(biāo)準(zhǔn)化托盤所在的出庫(kù)位置處。因此，堆垛機(jī)啟動(dòng)的位置取決于前一個(gè)任務(wù)。另一方面，堆垛機(jī)的作業(yè)模式有以下三種：(1)單一入庫(kù)任務(wù)：堆垛機(jī)從完成上一個(gè)任務(wù)的停頓點(diǎn)處空載到入口，將從入口處將要存放的標(biāo)準(zhǔn)化托盤運(yùn)送到給定存儲(chǔ)位置上。(2)單一出庫(kù)任務(wù)：堆垛機(jī)從完成上一個(gè)任務(wù)的停頓點(diǎn)處空載到所需托盤所在位置，從貨架上取下并將它運(yùn)送到某個(gè)揀貨位置處。(3)復(fù)合作業(yè)：堆垛機(jī)從完成上一個(gè)任務(wù)的停頓點(diǎn)處空載到入口，將要存放的標(biāo)準(zhǔn)化托盤運(yùn)送到給定存儲(chǔ)位置上，空載到需要取出的托盤所在位置，從貨架上取下并將它運(yùn)送到某個(gè)揀貨位置處。考慮到停頓點(diǎn)和堆垛機(jī)作業(yè)模式之間的組合，堆垛機(jī)會(huì)根據(jù)出入庫(kù)任務(wù)順序和出庫(kù)位置選擇按照相應(yīng)的路徑移動(dòng)。如圖2所示，堆垛機(jī)一共有6種可能的路徑移動(dòng)：(a) 停頓點(diǎn)在貨架上的單一入庫(kù)任務(wù)；(b) 停頓點(diǎn)在貨架上的單一出庫(kù)任務(wù)；(c) 停頓點(diǎn)在貨架上的復(fù)合作業(yè)；(d) 停頓點(diǎn)在出庫(kù)位置處的單一入庫(kù)任務(wù)；(e) 停頓點(diǎn)在出庫(kù)位置處的單一出庫(kù)任務(wù)；(f) 停頓點(diǎn)在出庫(kù)位置處的復(fù)合作業(yè)。

空心圓代表停頓點(diǎn)；實(shí)心圓代表出庫(kù)位置；實(shí)心方塊代表入庫(kù)位置；實(shí)線代表堆垛機(jī)負(fù)載移動(dòng)路線；虛線代表空載移動(dòng)路線圖2 堆垛機(jī)可能的移動(dòng)情形

本文考慮如何進(jìn)行出入庫(kù)任務(wù)的調(diào)度并確定出庫(kù)任務(wù)釋放到哪一個(gè)出庫(kù)位置，使得堆垛機(jī)完成所有任務(wù)的總距離最短。該問(wèn)題的決策包括出入庫(kù)任務(wù)的完成順序，以及出庫(kù)位置的選擇。為了方便問(wèn)題表述和模型建立，我們假設(shè)上述倉(cāng)儲(chǔ)系統(tǒng)：

(1)堆垛機(jī)既可以進(jìn)行單一作業(yè)，也可以進(jìn)行復(fù)合作業(yè)，其運(yùn)作能力為每次一個(gè)標(biāo)準(zhǔn)化托盤；

(2)堆垛機(jī)可以沿水平方向和豎直方向同時(shí)運(yùn)動(dòng)，且速度為常數(shù)；

(3)堆垛機(jī)的停頓點(diǎn)策略為停留策略，即堆垛機(jī)會(huì)在完成出庫(kù)(或入庫(kù))任務(wù)的位置處停留，等待下一個(gè)任務(wù)；

(4)系統(tǒng)采用專用存儲(chǔ)策略。因此，對(duì)于要存放的標(biāo)準(zhǔn)化托盤，其存儲(chǔ)位置已知。

2.2 模型構(gòu)建

考慮有m個(gè)入庫(kù)任務(wù)，n-m個(gè)出庫(kù)任務(wù)，以及K個(gè)出口位置。不失一般性，對(duì)任務(wù)進(jìn)行編號(hào)，i=1,2,…,m表示入庫(kù)任務(wù)，j=m+1,…,n表示出庫(kù)任務(wù)，另定義任務(wù)0和T為虛擬任務(wù)，分別表示開始和結(jié)束任務(wù)；令Si為對(duì)應(yīng)入庫(kù)任務(wù)i的位置，Rj為對(duì)應(yīng)出庫(kù)任務(wù)j的位置，Ok為出口位置k，I和E分別為對(duì)應(yīng)虛擬任務(wù)0和T的位置。

定義lk為出庫(kù)位置k=1,2,…,K到入口的距離；dijkp為堆垛機(jī)從完成任務(wù)i后所停留的位置k，移動(dòng)到完成任務(wù)j后所停留的位置p的距離，其中d0jIk表示堆垛機(jī)從入口I移動(dòng)到完成第一個(gè)任務(wù)所在停留點(diǎn)位置k的距離，diTkE表示堆垛機(jī)從完成最后一個(gè)任務(wù)i所停留位置k，移動(dòng)到虛擬任務(wù)T所在停留點(diǎn)位置E的距離，具體計(jì)算公式見(jiàn)表1。其中四元數(shù)組(A,B,C,D)定義為堆垛機(jī)從任務(wù)A移動(dòng)到任務(wù)B，任務(wù)A和B的停頓點(diǎn)分別為C和D；堆垛機(jī)按照切比雪夫距離移動(dòng)；此外(xi,yi)，(lk,0)分別是任務(wù)i和出庫(kù)位置k的笛卡爾坐標(biāo)。

表1 不同情況下對(duì)應(yīng)的邊權(quán)重計(jì)算公式

決策變量定義為：當(dāng)堆垛機(jī)完成任務(wù)i后立即完成任務(wù)j，同時(shí)任務(wù)i的停頓點(diǎn)為k，任務(wù)j的停頓點(diǎn)為p時(shí)，Xijkp=1，否則為0。其中X0jIp，XiTkE取1時(shí)，分別表示第一個(gè)任務(wù)為j，且停頓點(diǎn)為p和最后一個(gè)任務(wù)是i，且停頓點(diǎn)是k；任務(wù)i完成的次序ui。于是，多出口位置的自動(dòng)化立體倉(cāng)庫(kù)出入庫(kù)調(diào)度與出庫(kù)位置選擇集成優(yōu)化模型可以表示為：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

u1=1,

(9)

2≤ui≤n,?i≠1,

(10)

(11)

ur

(12)

Xijkp={0,1},?i,j∈J,?k,p∈L.

(13)

目標(biāo)函數(shù)(1)表示最小化堆垛機(jī)完成所有任務(wù)的移動(dòng)距離；約束(2)和(3)確保堆垛機(jī)有起始任務(wù)和終止任務(wù)；約束(4)和(5)表示每個(gè)任務(wù)的前后均有任務(wù)；約束(6)和(7)表示堆垛機(jī)在每個(gè)停頓位置最多停頓一次；約束(8)表示每個(gè)任務(wù)對(duì)應(yīng)的停頓點(diǎn)唯一；約束(9)、(10)和(11)表示避免產(chǎn)生子回路；約束(12)表示入庫(kù)任務(wù)按照次序完成；約束(13)給出決策變量的取值范圍。

2.3 復(fù)雜度分析

本節(jié)分析模型的復(fù)雜性，證明此類問(wèn)題是NP-hard問(wèn)題。

定理1出入庫(kù)調(diào)度與出庫(kù)位置選擇集成問(wèn)題是NP-hard問(wèn)題。

證明：本文將該問(wèn)題的一類特殊情況轉(zhuǎn)化為TSP旅行商問(wèn)題。構(gòu)造研究問(wèn)題的實(shí)例如下：設(shè)有m個(gè)出庫(kù)任務(wù)，m個(gè)出庫(kù)位置。我們?cè)O(shè)置一個(gè)虛擬點(diǎn)AP代表堆垛機(jī)的初始點(diǎn)和終止點(diǎn)，并假設(shè)虛擬點(diǎn)AP到出庫(kù)任務(wù)所在位置和出庫(kù)位置的距離均為0。為了防止堆垛機(jī)從任務(wù)所在位置(或出庫(kù)位置)直接移動(dòng)到另一個(gè)任務(wù)所在位置(或出庫(kù)位置)，設(shè)任意兩個(gè)任務(wù)所在位置(或出庫(kù)位置)之間的距離足夠大。原問(wèn)題轉(zhuǎn)化為求解從AP點(diǎn)出發(fā)，訪問(wèn)每一個(gè)任務(wù)位置和出庫(kù)位置并回到AP點(diǎn)的最短回路。因此，求解此類特殊問(wèn)題等同于求解TSP旅行商問(wèn)題，由于TSP是NP-hard問(wèn)題[26]，原問(wèn)題也是NP-hard問(wèn)題。

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

3.1 多項(xiàng)式時(shí)間求解子問(wèn)題

本文研究的堆垛機(jī)出入庫(kù)調(diào)度與出庫(kù)位置選擇集成問(wèn)題屬于NP-hard問(wèn)題，隨著問(wèn)題規(guī)模的擴(kuò)大，無(wú)法在有效時(shí)間內(nèi)獲得精確的最優(yōu)解。然而，我們可以在多項(xiàng)式時(shí)間內(nèi)求解一個(gè)重要的子問(wèn)題，即給定入庫(kù)和出庫(kù)任務(wù)的操作順序，如何確定各個(gè)出庫(kù)任務(wù)對(duì)應(yīng)的出庫(kù)位置。將此子問(wèn)題命名為SP，并在之后利用其求解原問(wèn)題。

定理2SP問(wèn)題能夠在O(n3)的時(shí)間內(nèi)求解出最優(yōu)解，其中n為出入庫(kù)任務(wù)的數(shù)量。

證明：當(dāng)給定出入庫(kù)任務(wù)的操作順序后，任意出庫(kù)任務(wù)的下一個(gè)任務(wù)有三種情況且已知。(1)當(dāng)下一個(gè)任務(wù)是入庫(kù)任務(wù)時(shí)，堆垛機(jī)從出庫(kù)任務(wù)的位置出發(fā)，移動(dòng)到出庫(kù)位置，再空載返回入口；(2)當(dāng)下一個(gè)任務(wù)是出庫(kù)任務(wù)時(shí)，堆垛機(jī)從出庫(kù)任務(wù)的位置出發(fā)，移動(dòng)到出庫(kù)位置，再空載移動(dòng)到下一個(gè)任務(wù)的位置；(3)當(dāng)出庫(kù)任務(wù)為最后一個(gè)任務(wù)時(shí)，堆垛機(jī)從出庫(kù)任務(wù)的位置出發(fā)，移動(dòng)到出庫(kù)位置并結(jié)束。我們引入二分圖理念，節(jié)點(diǎn)表示為出庫(kù)任務(wù)j和出庫(kù)位置k。如有必要，我們?cè)黾犹摂M任務(wù)使得出庫(kù)任務(wù)和位置的數(shù)量相等。任意出庫(kù)任務(wù)均和所有出庫(kù)位置相連，根據(jù)不同情況設(shè)置不同的邊權(quán)重cjk見(jiàn)表2(其中q已知)。

表2 不同情況下對(duì)應(yīng)的邊權(quán)重計(jì)算公式

針對(duì)上述問(wèn)題，我們可以建立整數(shù)規(guī)劃模型如下：

(14)

(15)

(16)

yjk={0,1}.

(17)

目標(biāo)函數(shù)(14)表示最小化總的邊權(quán)重；約束(15)和(16)表示出庫(kù)任務(wù)和出庫(kù)位置一一對(duì)應(yīng)；約束(17)表示決策變量的取值范圍。此問(wèn)題為指派問(wèn)題，可使用匈牙利算法在O(n3)的時(shí)間內(nèi)獲得最優(yōu)解。

注意到SP問(wèn)題本身也是實(shí)踐中的一個(gè)重要優(yōu)化問(wèn)題。對(duì)于入庫(kù)任務(wù)來(lái)說(shuō)，需要存放的貨物會(huì)在傳送帶上等待堆垛機(jī)操作，由于很難在傳送帶上改變待存放貨物的位置，因此，入庫(kù)任務(wù)按照先到先服務(wù)的模式完成；對(duì)于出庫(kù)任務(wù)來(lái)說(shuō)為及時(shí)滿足客戶訂單是許多倉(cāng)庫(kù)的重要準(zhǔn)則，因此，出庫(kù)任務(wù)通常根據(jù)到期時(shí)間排序，此時(shí)，出庫(kù)任務(wù)的取貨順序也確定。

3.2 兩階段啟發(fā)式算法

原問(wèn)題分解成為兩個(gè)子問(wèn)題：(1)找到出入庫(kù)任務(wù)的最優(yōu)操作順序，(2)在給定操作順序下，決策如何將出庫(kù)任務(wù)分配給出庫(kù)位置。后一個(gè)子問(wèn)題可以通過(guò)求解3.1小節(jié)中的指派問(wèn)題獲得最優(yōu)解。為此，本文設(shè)計(jì)基于遺傳算法和指派算法的混合求解算法對(duì)模型進(jìn)行求解。遺傳算法是一種通過(guò)模擬生物界自然選擇和遺傳機(jī)制的隨機(jī)搜索算法，具有收斂速度快，不易陷入局部最優(yōu)等特點(diǎn)。具體流程如下：

3.2.1 編碼方式

編碼方式為整數(shù)編碼。入庫(kù)任務(wù)按照先到先服務(wù)方式完成，編號(hào)為1,2,…,m；出庫(kù)任務(wù)編號(hào)為m+1,…,n。采用一個(gè)n維序列表示一條染色體，即為子問(wèn)題1的一個(gè)解。其中第i維上的數(shù)字為fi，表示任務(wù)fi被第i個(gè)處理。例如，圖3(a)表示有6個(gè)任務(wù)(3個(gè)入庫(kù)任務(wù)，3個(gè)出庫(kù)任務(wù))的子問(wèn)題1的一個(gè)解的編碼，在此調(diào)度方案中，堆垛機(jī)按照1-5-4-2-3-6的次序完成任務(wù)。

3.2.2 生成初始種群

定義種群規(guī)模為Npop的初始種群?？紤]到入庫(kù)任務(wù)按照先到先服務(wù)方式完成，有相對(duì)完成順序的約束，在此基礎(chǔ)上產(chǎn)生初始種群。例如圖3(b)并不是可行解，因?yàn)槿霂?kù)任務(wù)2先于1完成，違背約束。

圖3 編碼表示

3.2.3 計(jì)算個(gè)體目標(biāo)函數(shù)

在獲得子問(wèn)題1的解，即入出庫(kù)任務(wù)的操作順序(記為Ai,i=1,2,…,Npop)后，通過(guò)3.1節(jié)所提出的求解指派問(wèn)題的方法確定各個(gè)出庫(kù)任務(wù)對(duì)應(yīng)的出庫(kù)位置(記為Bi,i=1,2,…,Npop)。當(dāng)出入庫(kù)任務(wù)順序，出庫(kù)任務(wù)對(duì)應(yīng)的出庫(kù)位置均已知時(shí)，可計(jì)算出目標(biāo)函數(shù)F(Ai,Bi)。

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

目標(biāo)函數(shù)為求堆垛機(jī)完成所有任務(wù)運(yùn)行總距離的最小值，因此，采用個(gè)體目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度函數(shù)，定義如下：

fitnessi=1/F(Ai,Bi)，i=1,2,…,Npop.

3.2.5 選擇

對(duì)每代個(gè)體，通過(guò)輪盤賭法進(jìn)行選擇，每個(gè)個(gè)體的選擇概率為

產(chǎn)生一個(gè)在[0,1]之間的均勻隨機(jī)數(shù)，將該隨機(jī)數(shù)作為選擇指針確定被選個(gè)體。

3.2.6 交叉操作

采用單點(diǎn)交叉的方法，先從區(qū)間[1,n]中隨機(jī)抽取交叉點(diǎn)，子個(gè)體Offspring1在交叉點(diǎn)左側(cè)的基因與父?jìng)€(gè)體Parent1在交叉點(diǎn)左側(cè)的基因相同，Offspring1缺失的基因按順序從父?jìng)€(gè)體Parent2處獲得；同理獲得子個(gè)體Offspring2。由于模型對(duì)入庫(kù)任務(wù)有嚴(yán)格的順序約束，因此，為了避免產(chǎn)生非可行解，在交叉操作完成后增加一個(gè)步驟：不改變出庫(kù)任務(wù)的順序，將入庫(kù)任務(wù)按照編號(hào)從小到大的順序重新排序。

3.2.7 變異操作

隨機(jī)產(chǎn)生兩個(gè)變異點(diǎn)位置，交換兩個(gè)變異點(diǎn)位置的基因，形成新的染色體。為避免變異產(chǎn)生非可行解，只對(duì)兩個(gè)出庫(kù)任務(wù)，或者不影響入庫(kù)順序的一個(gè)入庫(kù)任務(wù)和一個(gè)出庫(kù)任務(wù)進(jìn)行變異操作。

綜上，該算法的流程圖和偽代碼分布如圖4和表3所示。

圖4 算法流程圖

表3 兩階段啟發(fā)式算法偽代碼

4 數(shù)值實(shí)驗(yàn)

實(shí)驗(yàn)使用MatlabR2014a開發(fā)算法程序。由于遺傳算法的參數(shù)設(shè)置會(huì)影響算法效率，我們對(duì)參數(shù)的選擇進(jìn)行多次測(cè)試，其中種群規(guī)模大小、交叉概率和變異概率的集合分別為Npop={50,80,100}，α={0.7,0.8,0.85,0.9}，β={0.05,0.1,0.15,0.2}。通過(guò)預(yù)先實(shí)驗(yàn)獲得了一組較好的遺傳算法參數(shù)組合：Npop=50，α=0.8，β=0.15。本文制定2個(gè)遺傳算法終止規(guī)則：一是當(dāng)最優(yōu)目標(biāo)值保持不變次數(shù)達(dá)到最大迭代數(shù)的三分之一時(shí)終止；二是算法的迭代次數(shù)達(dá)到預(yù)設(shè)的最大迭代次數(shù)時(shí)終止(本文采取文獻(xiàn)中常用的100次迭代)。倉(cāng)庫(kù)參數(shù)設(shè)計(jì)選用Ramtin和Pazour[17]，設(shè)置倉(cāng)庫(kù)長(zhǎng)為60 m，高為24 m，托盤大小為1.2 m*1.2 m。為了驗(yàn)證所建立模型與本文設(shè)計(jì)的兩階段啟發(fā)式算法的有效性，對(duì)每個(gè)算例進(jìn)行20次計(jì)算取平均值，并使用CPLEX求解模型，通過(guò)結(jié)果比較來(lái)驗(yàn)證算法效率。所有實(shí)驗(yàn)均運(yùn)行在1.8 GHz Intel Core 4 CPU和8GB內(nèi)存的計(jì)算機(jī)上。

針對(duì)每一個(gè)算例，分別用CPLEX和本文提出的啟發(fā)式算法求解，對(duì)比CPU計(jì)算時(shí)間和求得的結(jié)果。其中GAP1=(本文算法目標(biāo)值-CPLEX目標(biāo)值)/CPLEX目標(biāo)值*100%，GAP2 =(FCFS方法目標(biāo)值-本文算法目標(biāo)值)/本文算法目標(biāo)值*100%。記SN、RN和K分別表示入庫(kù)任務(wù)、出庫(kù)任務(wù)和出庫(kù)位置的數(shù)量。實(shí)驗(yàn)結(jié)果如表4所示，且有以下結(jié)論：(1)當(dāng)出入庫(kù)任務(wù)數(shù)量多于27個(gè)時(shí)，CPLEX已無(wú)法求解，而本文算法在所有算例中均能求出近似最優(yōu)解，與CPLEX求出的最優(yōu)解最多相差2.82%。同時(shí)，本文算法花費(fèi)的CPU時(shí)間也非常短，求解20個(gè)任務(wù)15個(gè)出庫(kù)位置的問(wèn)題只需不到6秒，運(yùn)算效率遠(yuǎn)遠(yuǎn)高于CPLEX。綜上，本文算法在效率和有效性兩個(gè)方面上表現(xiàn)均較好。(2)本文提出的算法相較于先到先服務(wù)方法最大改善了25.09%，平均改善了20.47%，表明本文算法明顯優(yōu)于企業(yè)中常用的先到先服務(wù)方法。

表4 算例結(jié)果對(duì)比

接下來(lái)研究出庫(kù)位置的數(shù)量變化對(duì)數(shù)值結(jié)果的影響。我們隨機(jī)產(chǎn)生10組出入庫(kù)任務(wù)的數(shù)量和所在位置，對(duì)于每組算例，出庫(kù)位置的數(shù)量K變化為{10,12,14,16,18,20}。使用本文提出的算法求解目標(biāo)值并對(duì)10組算例取平均值。數(shù)值結(jié)果如圖5所示。我們發(fā)現(xiàn)隨著出庫(kù)位置數(shù)量的增加，堆垛機(jī)移動(dòng)的距離從636 m逐步降低，最終保持平緩到596 m。注意到出庫(kù)位置的增加也會(huì)帶來(lái)運(yùn)作成本的增長(zhǎng)，如揀選人員的人力成本等。因此，企業(yè)管理人員需要權(quán)衡每多開一個(gè)出庫(kù)位置帶來(lái)的堆垛機(jī)移動(dòng)成本的減少和其他運(yùn)作成本的增加，以確定最優(yōu)的出庫(kù)位置的數(shù)量。

圖5 出庫(kù)位置數(shù)量對(duì)目標(biāo)值的影響

5 結(jié)語(yǔ)

本文主要研究了一種新型自動(dòng)化倉(cāng)儲(chǔ)系統(tǒng)，其特征是在貨架的底層有多個(gè)出口位置以供揀選人員做訂單揀選任務(wù)。此倉(cāng)儲(chǔ)系統(tǒng)將存儲(chǔ)和分揀任務(wù)統(tǒng)一于一處，既提高了空間利用率，又降低了能源消耗。本文聚焦于出入庫(kù)任務(wù)調(diào)度和出口位置選擇問(wèn)題，需要同時(shí)決策出入庫(kù)任務(wù)的順序以及出庫(kù)任務(wù)與出口位置的匹配。我們提出了求解該問(wèn)題的混合整數(shù)規(guī)劃模型，并將問(wèn)題分解成兩個(gè)子問(wèn)題：先確定出入庫(kù)任務(wù)的順序，再在給定順序的情況下決策出庫(kù)貨物釋放到哪一個(gè)出庫(kù)位置。后一個(gè)子問(wèn)題可以在多項(xiàng)式時(shí)間內(nèi)求出最優(yōu)解。根據(jù)此性質(zhì)我們?cè)O(shè)計(jì)了基于遺傳算法和指派問(wèn)題的兩階段啟發(fā)式算法，并與CPLEX求解的結(jié)果進(jìn)行比較。數(shù)值實(shí)驗(yàn)的結(jié)果表明了該模型和算法的有效性。

本文可以在以下幾個(gè)方面進(jìn)行擴(kuò)展研究：首先，本文考慮了倉(cāng)儲(chǔ)系統(tǒng)采用專用存儲(chǔ)策略，而針對(duì)不同的存儲(chǔ)策略對(duì)調(diào)度問(wèn)題影響的研究對(duì)實(shí)踐也有重要的指導(dǎo)意義。其次，在理論方面，如何為該優(yōu)化問(wèn)題設(shè)計(jì)求解一個(gè)緊的下界也很值得期待。