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

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

1 引言

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

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

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

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

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

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

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

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

2.1 問題描述

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

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

上述堆垛機操作過程中存在以下特點：

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

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

空心圓代表停頓點；實心圓代表出庫位置；實心方塊代表入庫位置；實線代表堆垛機負(fù)載移動路線；虛線代表空載移動路線圖2 堆垛機可能的移動情形

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

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

(2)堆垛機可以沿水平方向和豎直方向同時運動，且速度為常數(shù)；

(3)堆垛機的停頓點策略為停留策略，即堆垛機會在完成出庫(或入庫)任務(wù)的位置處停留，等待下一個任務(wù)；

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

2.2 模型構(gòu)建

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

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

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

決策變量定義為：當(dāng)堆垛機完成任務(wù)i后立即完成任務(wù)j，同時任務(wù)i的停頓點為k，任務(wù)j的停頓點為p時，Xijkp=1，否則為0。其中X0jIp，XiTkE取1時，分別表示第一個任務(wù)為j，且停頓點為p和最后一個任務(wù)是i，且停頓點是k；任務(wù)i完成的次序ui。于是，多出口位置的自動化立體倉庫出入庫調(diào)度與出庫位置選擇集成優(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)表示最小化堆垛機完成所有任務(wù)的移動距離；約束(2)和(3)確保堆垛機有起始任務(wù)和終止任務(wù)；約束(4)和(5)表示每個任務(wù)的前后均有任務(wù)；約束(6)和(7)表示堆垛機在每個停頓位置最多停頓一次；約束(8)表示每個任務(wù)對應(yīng)的停頓點唯一；約束(9)、(10)和(11)表示避免產(chǎn)生子回路；約束(12)表示入庫任務(wù)按照次序完成；約束(13)給出決策變量的取值范圍。

2.3 復(fù)雜度分析

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

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

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

3 算法設(shè)計

3.1 多項式時間求解子問題

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

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

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

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

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

(14)

(15)

(16)

yjk={0,1}.

(17)

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

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

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

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

3.2.1 編碼方式

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

3.2.2 生成初始種群

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

圖3 編碼表示

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

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

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

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

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

3.2.5 選擇

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

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

3.2.6 交叉操作

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

3.2.7 變異操作

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

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

圖4 算法流程圖

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

4 數(shù)值實驗

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

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

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

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

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

5 結(jié)語

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

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