基于改進(jìn)防碰撞策略的兩端式雙堆垛機(jī)出入庫(kù)優(yōu)化研究

耿 賽，王 雷，李東東

（安徽工程大學(xué)機(jī)械工程學(xué)院，蕪湖 241000）

自動(dòng)化倉(cāng)儲(chǔ)系統(tǒng)（Automated storage and re?trieval system，AS/RS）是一種新型的倉(cāng)儲(chǔ)技術(shù)，作為現(xiàn)代物流系統(tǒng)的核心部分，正越來(lái)越多地應(yīng)用于各個(gè)行業(yè)［1?3］。倉(cāng)庫(kù)的出入庫(kù)效率直接影響到整個(gè)物流系統(tǒng)的效率，因此出入庫(kù)路徑的優(yōu)化就成為提高整個(gè)物流系統(tǒng)效率的關(guān)鍵。堆垛機(jī)是AS/RS中運(yùn)輸和存取貨物的主要設(shè)備，其中堆垛機(jī)揀選出入庫(kù)貨物的時(shí)間占其整個(gè)作業(yè)周期的50%左右，因此解決堆垛機(jī)行駛路徑優(yōu)化問(wèn)題是提高自動(dòng)化倉(cāng)庫(kù)效率的有效手段［4］。

國(guó)內(nèi)外學(xué)者對(duì)立體化倉(cāng)庫(kù)出入庫(kù)堆垛機(jī)路徑優(yōu)化問(wèn)題做了大量的研究。Liu 等［5］、李媛媛等［6］、楊姣等［7］主要針對(duì)I/O 設(shè)在貨架同一側(cè)的情況，對(duì)堆垛機(jī)的不同工作模式建立了相關(guān)的數(shù)學(xué)模型，并分別結(jié)合遺傳禁忌搜索算法、近似動(dòng)態(tài)規(guī)劃算法和遺傳模擬退火算法對(duì)模型進(jìn)行優(yōu)化求解，提高了最優(yōu)解的收斂速度。Emanuele 等［8］以倉(cāng)庫(kù)設(shè)計(jì)、存儲(chǔ)策略和耗能作為重點(diǎn)對(duì)堆垛機(jī)進(jìn)行路徑優(yōu)化。Bortolini 等［9］建立了分析模型來(lái)評(píng)估堆垛機(jī)在單一作業(yè)和復(fù)合作業(yè)中的預(yù)期時(shí)間。韓東亞等［10］以堆垛機(jī)出入庫(kù)的復(fù)合作業(yè)和任務(wù)順序?yàn)檠芯糠较?，根?jù)問(wèn)題的特點(diǎn)設(shè)計(jì)了兩階段啟發(fā)式算法求解此問(wèn)題，有效地提高了倉(cāng)庫(kù)揀選效率和堆垛機(jī)的作業(yè)方式。Lerher［11］對(duì)跨巷道堆垛機(jī)倉(cāng)儲(chǔ)系統(tǒng)進(jìn)行研究，建立單、雙指令情況下堆垛機(jī)的行程時(shí)間模型，并對(duì)時(shí)間模型進(jìn)行性能分析。Torabizadeh 等［12］和Hao 等［13］建立新型的模型來(lái)研究倉(cāng)儲(chǔ)系統(tǒng)的可持續(xù)性可以通過(guò)存儲(chǔ)策略、堆垛機(jī)停頓點(diǎn)策略和出入庫(kù)調(diào)度策略等來(lái)有效地提高自動(dòng)化立體倉(cāng)庫(kù)的效率。卞和營(yíng)等［14］提出將I/O 分別設(shè)在貨架兩側(cè)，并建立堆垛機(jī)的單一、復(fù)合作業(yè)模型，結(jié)合一種改進(jìn)的遺傳算法對(duì)模型進(jìn)行優(yōu)化求解。上述研究雖然最終取得了不錯(cuò)的貨物出入庫(kù)優(yōu)化結(jié)果，但僅僅局限于算法上的優(yōu)化，并沒(méi)有對(duì)傳統(tǒng)立體化倉(cāng)庫(kù)I/O臺(tái)以及堆垛機(jī)的數(shù)量和位置布局上提出改良。蔡安江等［15?16］在碼頭雙堆碼起重機(jī)調(diào)度的構(gòu)思下，提出兩端式I/O 同軌雙車(chē)模式的雙堆垛機(jī)調(diào)度模型，并結(jié)合防碰撞原則，用改進(jìn)的化學(xué)反應(yīng)優(yōu)化算法進(jìn)行求解，有效地提高了立體倉(cāng)庫(kù)貨物出入庫(kù)的調(diào)度效率。雖然該方法避免了兩堆垛機(jī)在工作時(shí)發(fā)生碰撞，但防碰撞原則實(shí)現(xiàn)方法較繁瑣且最終的任務(wù)分配也非最優(yōu)，優(yōu)化效果仍存在較大改進(jìn)空間。基于此，本文以?xún)啥耸诫p堆垛機(jī)模式下的立體倉(cāng)庫(kù)為基礎(chǔ)，提出改進(jìn)的防碰撞原則和最優(yōu)防碰撞邊界檢驗(yàn)機(jī)制，并運(yùn)用新型改進(jìn)遺傳算法（New improved genetic algorithm，NIGA）進(jìn)行優(yōu)化求解，最大限度提高大型立體倉(cāng)庫(kù)的出入庫(kù)調(diào)度效率。

1 問(wèn)題描述

1.1 兩端式雙堆垛機(jī)問(wèn)題描述

在一般倉(cāng)庫(kù)的運(yùn)輸調(diào)度中，一般采取單端I/O、單堆垛機(jī)的調(diào)度模型，通過(guò)對(duì)單一作業(yè)、復(fù)合作業(yè)出入庫(kù)任務(wù)的優(yōu)化，來(lái)提高調(diào)度效率。但隨著科學(xué)技術(shù)的發(fā)展，現(xiàn)代企業(yè)倉(cāng)庫(kù)規(guī)模不斷擴(kuò)大，這種傳統(tǒng)模式下，倉(cāng)庫(kù)的優(yōu)化效果往往不盡如人意。為了縮短堆垛機(jī)的最大工作行程、提高存取貨物效率，蔡安江等［15］提出兩端式雙堆垛機(jī)模型。圖1 為兩端式雙堆垛機(jī)立體倉(cāng)庫(kù)模型的結(jié)構(gòu)圖，在貨架兩端都設(shè)立相同規(guī)格的I/O 位置，貨架之間的巷道上放置了兩臺(tái)規(guī)格相同的堆垛機(jī)。將堆垛機(jī)的最大行駛距離“一分為二”，左右兩堆垛機(jī)分別負(fù)責(zé)自己的“工作區(qū)域”，極大地縮短了堆垛機(jī)的行駛路程，提高了大型倉(cāng)庫(kù)的出入庫(kù)調(diào)度效率。

圖1 中的堆垛機(jī)選用單立柱堆垛機(jī)，兩堆垛機(jī)貨叉相向，貨叉可以左右伸縮，以便向兩側(cè)的貨架存取貨物。當(dāng)兩堆垛機(jī)同時(shí)工作時(shí)，要保證兩堆垛機(jī)始終不會(huì)發(fā)生碰撞。即左端堆垛機(jī)處于貨架第I列，右端堆垛機(jī)處于貨架第I+1 列存取貨物時(shí)，此時(shí)兩堆垛機(jī)處于臨界安全距離，仍可正常工作不會(huì)發(fā)生碰撞。

圖1 兩端式雙堆垛機(jī)立體倉(cāng)庫(kù)模型結(jié)構(gòu)圖Fig.1 Structure diagram of the warehouse model with two?end double stacker

立體倉(cāng)庫(kù)兩端式雙堆垛機(jī)的調(diào)度模型下，兩堆垛機(jī)分別從對(duì)應(yīng)的I/O 臺(tái)完成出入庫(kù)任務(wù)的存取，工作時(shí)互不干預(yù)，僅負(fù)責(zé)自己工作區(qū)的任務(wù)。所以完成一批貨物存取所需的時(shí)間取決于兩臺(tái)堆垛機(jī)中耗時(shí)更長(zhǎng)的一方。

式中TL和TR分別為同一巷道左端堆垛機(jī)和右端堆垛機(jī)完成各自任務(wù)所花費(fèi)的時(shí)間。

堆垛機(jī)存取貨物的工作方式有兩種：（1）堆垛機(jī)每次從I/O 臺(tái)出發(fā)，僅執(zhí)行一個(gè)出庫(kù)任務(wù)指令或者入庫(kù)任務(wù)指令，稱(chēng)為單一作業(yè)（Single operation cycle，SC）；（2）堆垛機(jī)從I/O 臺(tái)出發(fā)，先執(zhí)行一個(gè)入庫(kù)任務(wù)指令，然后緊接著馬上執(zhí)行出庫(kù)任務(wù)指令，稱(chēng)為復(fù)合作業(yè)（Double operation cycle，DC）。因?yàn)閺?fù)合作業(yè)能夠減少堆垛機(jī)往返I/O 臺(tái)的次數(shù)，提高堆垛機(jī)的運(yùn)行效率，因此優(yōu)先選用復(fù)合作業(yè)方式。

若立體倉(cāng)庫(kù)為兩端式布局，同一巷道上有兩臺(tái)堆垛機(jī)負(fù)責(zé)貨物的出入庫(kù)調(diào)度?，F(xiàn)僅分析左堆垛機(jī)完成所有的單一作業(yè)任務(wù)，復(fù)合作業(yè)任務(wù)所用的時(shí)間為

式中：TSCi為左端堆垛機(jī)完成第i個(gè)SC 作業(yè)時(shí)所運(yùn)行的時(shí)間，TDCj為左端堆垛機(jī)完成第j個(gè)DC 作業(yè)時(shí)運(yùn)行的時(shí)間。其中

式中：除TSCi和TDCj外，T表示堆垛機(jī)從一個(gè)貨位到另一個(gè)貨位所用時(shí)間；IOL為左側(cè)出/入庫(kù)臺(tái)；Xi為堆垛機(jī)執(zhí)行第i個(gè)單一任務(wù)時(shí)，出庫(kù)/入庫(kù)貨位的位置；Xj1、Xj2分別為堆垛機(jī)執(zhí)行第j個(gè)復(fù)合作業(yè)時(shí)，入庫(kù)貨位的位置和出庫(kù)貨位的位置。

式（2～6）僅分析了左端堆垛機(jī)存取貨物的工作模型，右端堆垛機(jī)同理。當(dāng)倉(cāng)庫(kù)接收到一批出入庫(kù)混合任務(wù)指令時(shí)，需要兩堆垛機(jī)協(xié)同工作揀取完所有的貨物。因此要根據(jù)實(shí)際的工作情況，將一批出入庫(kù)貨物合理地分配給兩堆垛機(jī)，在保證兩堆垛機(jī)同時(shí)運(yùn)行無(wú)碰撞的前提下，取得最優(yōu)的調(diào)度效率。

因此，針對(duì)兩堆垛機(jī)運(yùn)行時(shí)無(wú)碰撞和任務(wù)分配最優(yōu)兩個(gè)關(guān)鍵問(wèn)題，本文提出了改進(jìn)防碰撞原則以及最優(yōu)防碰撞邊界檢驗(yàn)機(jī)制，并運(yùn)用NIGA 算法對(duì)包含SC、DC 兩種工作模式的立體倉(cāng)庫(kù)雙堆垛機(jī)模型進(jìn)行出入庫(kù)調(diào)度優(yōu)化。

1.2 相關(guān)參數(shù)的基本假設(shè)

對(duì)于本文中的兩端式雙堆垛機(jī)立體倉(cāng)庫(kù)模型布局，為了研究更具有普遍性以及實(shí)用價(jià)值，參考文獻(xiàn)［9］中的相關(guān)參數(shù)，現(xiàn)假設(shè)堆垛機(jī)作業(yè)時(shí)勻速運(yùn)行，加速和制動(dòng)時(shí)間忽略不計(jì)，不考慮貨叉存取貨物時(shí)間，設(shè)貨位的長(zhǎng)度和高度分別為l和h。根據(jù)上述假定參數(shù)可知，堆垛機(jī)從貨位（x1，y1）到貨位（x2，y2）的運(yùn)行時(shí)間為

2 出入庫(kù)調(diào)度模型

兩端式雙堆垛機(jī)出入庫(kù)調(diào)度模式下，首要問(wèn)題就是避免兩堆垛機(jī)執(zhí)行任務(wù)時(shí)發(fā)生碰撞以及合理分配左、右兩堆垛機(jī)執(zhí)行任務(wù)。因此本節(jié)首先提出了改進(jìn)的防碰撞原則，并以此為約束條件，建立相關(guān)的雙堆垛機(jī)調(diào)度模型，最后嵌入最優(yōu)防碰撞邊界檢驗(yàn)機(jī)制。

2.1 改進(jìn)的防碰撞原則

當(dāng)接收到一批出入庫(kù)貨物混合訂單時(shí)，把出庫(kù)貨物、入庫(kù)貨物對(duì)應(yīng)貨位的橫坐標(biāo)提取出來(lái)構(gòu)成集合U。為了防止兩端堆垛機(jī)在揀選、存放貨物時(shí)發(fā)生碰撞，將這批貨物分為兩組，各組任務(wù)對(duì)應(yīng)貨位的橫坐標(biāo)分別構(gòu)成集合L＝｛xi1，xi2，…，xil｝和R＝｛xj1，xj2，…，xjr｝，在保證集合L中各元素均小于集合R中各元素外，為了方便后續(xù)優(yōu)化算法的操作，將集合L和集合R中的貨物橫坐標(biāo)元素xi1，xi2，…，xil以及xj1，xj2，…，xjr按從小到大的順序依次排列。集合L中元素對(duì)應(yīng)的出/入庫(kù)任務(wù)交由左端堆垛機(jī)執(zhí)行，集合R中元素對(duì)應(yīng)的出/入庫(kù)任務(wù)交由右端堆垛機(jī)執(zhí)行。以此來(lái)劃分兩臺(tái)堆垛機(jī)的工作區(qū)域，使左端堆垛機(jī)執(zhí)行的出/入庫(kù)任務(wù)對(duì)應(yīng)貨位的橫坐標(biāo)均小于右端堆垛機(jī)執(zhí)行出/入庫(kù)任務(wù)對(duì)應(yīng)貨位的橫坐標(biāo)，從而實(shí)現(xiàn)左右堆垛機(jī)在相同巷道同時(shí)作業(yè)時(shí)不會(huì)發(fā)生碰撞干預(yù)現(xiàn)象。

改進(jìn)的防碰撞原則數(shù)學(xué)表達(dá)式為

采用式（8，9）表示的改進(jìn)的防碰撞原則，可將左、右兩堆垛機(jī)負(fù)責(zé)執(zhí)行的出/入庫(kù)貨物，根據(jù)其所處貨位的列坐標(biāo)從左往右按大小排列，劃分為沒(méi)有重疊部分的左、右兩工作區(qū)域。

2.2 雙堆垛機(jī)調(diào)度模型

雖然該調(diào)度模型下堆垛機(jī)型號(hào)完全一致，但是左、右堆垛機(jī)被分配的出庫(kù)任務(wù)、入庫(kù)任務(wù)的數(shù)目可能完全不同。假設(shè)左側(cè)堆垛機(jī)需要執(zhí)行n1個(gè)入庫(kù)任務(wù)，m1個(gè)出庫(kù)任務(wù)，右側(cè)堆垛機(jī)需要執(zhí)行n2個(gè)入庫(kù)任務(wù)，m2個(gè)出庫(kù)任務(wù)，取

由式（12）可知，兩端式雙堆垛機(jī)模式下，左側(cè)堆垛機(jī)要執(zhí)行Q1個(gè)DC 作業(yè)和Q2-Q1個(gè)SC 作業(yè)，右側(cè)堆垛機(jī)要執(zhí)行P1個(gè)DC 作業(yè)和P2-P1個(gè)SC 作業(yè)，結(jié)合式（2～6），參考文獻(xiàn)［10］的相關(guān)內(nèi)容，可得左、右兩側(cè)堆垛機(jī)完成各自任務(wù)所運(yùn)行的總時(shí)間為

式中：TL為左側(cè)堆垛機(jī)完成任務(wù)所用的時(shí)間；TR為右側(cè)堆垛機(jī)完成任務(wù)所用的時(shí)間；IOR為右端貨物出/入庫(kù)臺(tái)。

兩端式雙堆垛機(jī)模式下，堆垛機(jī)運(yùn)輸完一批出入庫(kù)任務(wù)的總時(shí)間應(yīng)該取決于兩堆垛機(jī)中耗時(shí)較長(zhǎng)的一方，綜上所述，兩堆垛機(jī)完成一批出/入庫(kù)貨物訂單的總時(shí)間如式（1）所示。則兩端式雙堆垛機(jī)模式下完成這批出入庫(kù)作業(yè)，雙堆垛機(jī)的最優(yōu)路徑模型為

2.3 最優(yōu)防碰撞邊界檢驗(yàn)機(jī)制

雖然上述改進(jìn)的防碰撞原則可以將貨架分為左、右工作區(qū)域，避免了兩堆垛機(jī)在執(zhí)行各自任務(wù)時(shí)發(fā)生碰撞。但如果左右區(qū)域劃分不當(dāng)，就會(huì)出現(xiàn)兩堆垛機(jī)工作量差異較大的狀況，導(dǎo)致任務(wù)量較少的堆垛機(jī)過(guò)早地完成任務(wù)，而任務(wù)量較大的堆垛機(jī)仍要“加班”工作的情況，極大降低了堆垛機(jī)的利用效率，與本文提出的雙堆垛機(jī)提高貨物出入庫(kù)效率的想法相悖。于是為了解決這個(gè)問(wèn)題，在改進(jìn)的防碰撞原則的基礎(chǔ)上，提出最優(yōu)防碰撞邊界檢驗(yàn)機(jī)制。

最優(yōu)防碰撞邊界檢驗(yàn)機(jī)制判斷依據(jù)如下：根據(jù)改進(jìn)的防碰撞原則得到左、右工作區(qū)分界線e；左、右堆垛機(jī)執(zhí)行完各自分配任務(wù)所運(yùn)行的時(shí)間TL、TR。

（1）當(dāng)TL≥TR時(shí)，左、右工作區(qū)分界線左移取e左邊較小元素，enew=U（i-1），將［enew，e］區(qū)間內(nèi)橫坐標(biāo)對(duì)應(yīng)的任務(wù)從左堆垛機(jī)負(fù)責(zé)的任務(wù)集合L中刪去添加進(jìn)右端堆垛機(jī)負(fù)責(zé)的集合R中，重新計(jì)算任務(wù)更新后，左、右堆垛機(jī)執(zhí)行各自任務(wù)的運(yùn)行時(shí)間TLnew，TRnew。比較兩者大?。?/p>

①當(dāng)TLnew≤TRnew時(shí)，此時(shí)分界線enew必為最優(yōu)的防碰撞邊界線。因?yàn)楣ぷ骺倳r(shí)間T=max（TL，TR），所以比較TL與TRnew大小，若TL≥TRnew則保留最新的出入庫(kù)任務(wù)分配結(jié)果，記錄最優(yōu)解Tbest=TRnew；反之保留原出入庫(kù)任務(wù)分配結(jié)果，記錄最優(yōu)解Tbest=TL。

②當(dāng)TLnew>TRnew時(shí)，令TL=TLnew，更新左、右堆垛機(jī)出入庫(kù)任務(wù)分配結(jié)果，邊界enew繼續(xù)左移取U中最近的較小元素……按上述規(guī)則繼續(xù)循環(huán)判斷，直 至TLnew≤TRnew時(shí)，比 較TL與TRnew大 小，若TL≥TRnew則保留最新的出入庫(kù)任務(wù)分配結(jié)果，記錄最優(yōu)解Tbest=TRnew；反之保留原出入庫(kù)任務(wù)分配結(jié)果，記錄最優(yōu)解Tbest=TL。

（2）當(dāng)TL

①當(dāng)TLnew≥TRnew時(shí)，此時(shí)分界線enew必為最優(yōu)的防碰撞邊界線。比較TL與TRnew大小，若TR≥TLnew則保留最新的出入庫(kù)任務(wù)分配結(jié)果，記錄最優(yōu)解Tbest=TLnew；反之保留原出入庫(kù)任務(wù)分配結(jié)果，記錄最優(yōu)解Tbest=TR。

②當(dāng)TLnew

針對(duì)自動(dòng)化立體倉(cāng)庫(kù)的兩端式雙堆垛機(jī)模式，在采用改進(jìn)防碰撞原則的基礎(chǔ)上，校驗(yàn)通過(guò)防碰撞原則得到的左、右工作區(qū)的劃分界線e是否為最優(yōu)分界線，從而保證了兩堆垛機(jī)最優(yōu)的貨位分配，極大地縮短了堆垛機(jī)的最大行程，提高了出入庫(kù)作業(yè)的效率。將上述的最優(yōu)防碰撞邊界檢驗(yàn)機(jī)制嵌入到算法后續(xù)優(yōu)化的每一次迭代中，根據(jù)TL、TR以及TLnew、TRnew的大小情況對(duì)左、右兩堆垛機(jī)任務(wù)的分配結(jié)果進(jìn)行自適應(yīng)地調(diào)整，最終得到最優(yōu)的任務(wù)分配方案（具體步驟見(jiàn)3.3 節(jié)）

3 出/入庫(kù)調(diào)度路徑的優(yōu)化

為了解決自動(dòng)化立體倉(cāng)庫(kù)出入庫(kù)調(diào)度優(yōu)化的多目標(biāo)、多約束性等問(wèn)題，通常采用啟發(fā)式算法進(jìn)行求解，常用的就是遺傳算法。而在遺傳算法中，交叉操作和變異操作對(duì)遺傳算法的優(yōu)化結(jié)果和收斂速度影響頗深，傳統(tǒng)遺傳算法中先進(jìn)行交叉操作后進(jìn)行變異操作，若種群的適應(yīng)度值比較集中，交叉操作可能導(dǎo)致遺傳算法（Genetic algorithm，GA）過(guò)早收斂，即使再進(jìn)行變異操作，算法也很難跳出局部最優(yōu)，在解決實(shí)際問(wèn)題中，往往很難取到最優(yōu)值［17?18］。針對(duì)傳統(tǒng)遺傳算法“爬山能力差”，跳出局部最優(yōu)能力弱的問(wèn)題，本文提出了一種基于種群適應(yīng)度疏密程度的不同而自適應(yīng)調(diào)節(jié)進(jìn)化過(guò)程的新型改進(jìn)遺傳算法NIGA。

NIGA 算法在優(yōu)化過(guò)程中先求出種群個(gè)體適應(yīng)度的最小值fmin、最大值fmax和平均值favg，再判斷不等式“（fmax-favg）/（fmax-fmin）≥1/2”是否成立，若成立則說(shuō)明當(dāng)前種群的最大適應(yīng)度值、平均適應(yīng)度值的差值與最大適應(yīng)度值、最小適應(yīng)度的差值比較接近，且比值比1/2 大得越多，則說(shuō)明此時(shí)種群的適應(yīng)度值越密集，多樣性不強(qiáng)，個(gè)體之間交叉產(chǎn)生優(yōu)秀后代的幾率不大，且算法容易陷入局部最優(yōu)解，因此先執(zhí)行變異操作，能增加算法跳出局部最優(yōu)的能力，然后再執(zhí)行交叉操作；若不成立則表明當(dāng)前種群的最大適應(yīng)度值、平均適應(yīng)度值的差值與最大適應(yīng)度值、最小適應(yīng)度的差值存在偏差，且比值比1/2 小的越多，說(shuō)明此時(shí)的種群的適應(yīng)度值分布比較分散，種群的基因多樣性豐富，個(gè)體之間交叉產(chǎn)生優(yōu)秀后代幾率較大，極大地提高了算法收斂效率，因此先執(zhí)行交叉操作，再執(zhí)行變異操作。

3.1 編碼設(shè)計(jì)

由于算法優(yōu)化的目的是找到雙堆垛機(jī)調(diào)度的最優(yōu)任務(wù)執(zhí)行順序，高效地安排貨物的出入庫(kù)。若NIGA 算法采用二進(jìn)制編碼，則不能直觀地描繪出堆垛機(jī)揀取貨物的路徑軌跡，反而會(huì)使編碼過(guò)程變得更加復(fù)雜。因此本文NIGA 算法采用實(shí)數(shù)編碼，每個(gè)實(shí)數(shù)代表待執(zhí)行任務(wù)的編號(hào)。

每臺(tái)堆垛機(jī)接收到的出入庫(kù)任務(wù)指令按照前后順序（左堆垛機(jī)Chrom1、右堆垛機(jī)Chrom2）分別編寫(xiě)成兩段編碼，每段編碼中的實(shí)數(shù)代表著相應(yīng)任務(wù)的序號(hào)。第1 段編碼X=［x1，x2，…，xi，…，xm］表示堆垛機(jī)接收到的入庫(kù)指令順序，第2 段編碼Y=［y1，y2，…，yj，…，yN］表示堆垛機(jī)接收到的出庫(kù)指令順序，Chrom=X∪Y=［x1，x2，…，xi，…，xM，y1，y2，…，yj，…，yN］，其中M為入庫(kù)任務(wù)的個(gè)數(shù)，N為出庫(kù)任務(wù)的個(gè)數(shù)，xi為第i個(gè)入庫(kù)貨物在貨架中的坐標(biāo)位置，yj為第j個(gè)出庫(kù)貨物在貨架中的坐標(biāo)位置。自左往右，從X、Y的第一位開(kāi)始，對(duì)應(yīng)編號(hào)的出入庫(kù)任務(wù)優(yōu)先組成DC 作業(yè)，最后落單的出庫(kù)或入庫(kù)任務(wù)按SC 作業(yè)執(zhí)行。例如，在經(jīng)過(guò)防碰撞原則的任務(wù)分配后，左端堆垛機(jī)可能收到4 個(gè)入庫(kù)任務(wù)和6 個(gè)出庫(kù)任務(wù)的指令，隨機(jī)生成的任務(wù)序列為Chrom1=［2，4，1，3，5，2，3，4，6，1］，其中入庫(kù)任務(wù)為X1=［2，4，1，3］，出庫(kù)任務(wù)Y1=［5，2，3，4，6，1］，則左側(cè)堆垛機(jī)編碼Chrom1 對(duì)應(yīng)的任務(wù)執(zhí)行順序是：先執(zhí)行DC 作業(yè)：先執(zhí)行入庫(kù)任務(wù)2，出庫(kù)任務(wù)5；再執(zhí)行入庫(kù)任務(wù)4，出庫(kù)任務(wù)2；以此類(lèi)推先執(zhí)行完DC 作業(yè)，最后執(zhí)行落單的出庫(kù)任務(wù)6 和出庫(kù)任務(wù)1 兩個(gè)SC 作業(yè)，右端堆垛機(jī)工作模式與其一致。

目標(biāo)函數(shù)為耗時(shí)較長(zhǎng)一側(cè)堆垛機(jī)完成所有任務(wù)運(yùn)行時(shí)間的最小值，因此采用個(gè)體目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度函數(shù)，定義為

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

（1）選擇操作

對(duì)群體中個(gè)體使用輪盤(pán)賭選擇法進(jìn)行選擇操作，個(gè)體被選擇的概率與適應(yīng)度函數(shù)值有關(guān)，個(gè)體適應(yīng)度值越高，被選中的概率越大，并在選擇過(guò)程中加入精英保留策略，將上代中最優(yōu)染色體保留到下一代。每個(gè)染色體被選中的概率為

式中：f（i）為第i個(gè)染色體的適應(yīng)度值，m為種群個(gè)體的數(shù)目。

（2）交叉操作

分別對(duì)左、右兩堆垛機(jī)的出/入庫(kù)任務(wù)序列Chrom1、Chrom2 采用兩點(diǎn)交叉，將相鄰的兩染色體分為一組，當(dāng)每組染色體的隨機(jī)概率rand≤pc時(shí)，從區(qū)間［1，m］隨機(jī)選取兩交叉點(diǎn)，對(duì)入庫(kù)任務(wù)序列進(jìn)行交叉操作，子代1 繼承父代1 交叉點(diǎn)兩側(cè)的基因，中間缺失的基因按順序從父代2 的基因中獲得；子代2 同理獲得。從區(qū)間［1，n］隨機(jī)選取兩交叉點(diǎn)對(duì)出庫(kù)任務(wù)序列進(jìn)行相同操作。用交叉后的子代染色體代替父代染色體。

（3）變異操作

分別對(duì)左、右兩堆垛機(jī)的出/入庫(kù)任務(wù)序列Chrom1、Chrom2 采用位置變異，每組染色體的隨機(jī)概率rand≤pm時(shí)，從區(qū)間［1，m］隨機(jī)產(chǎn)生兩個(gè)變異點(diǎn)，對(duì)入庫(kù)任務(wù)序列進(jìn)行變異操作，交換兩個(gè)變異點(diǎn)位置的基因形成新的染色體，同時(shí)從區(qū)間［1，n］隨機(jī)產(chǎn)生兩個(gè)變異點(diǎn)，對(duì)出庫(kù)任務(wù)序列進(jìn)行相同操作。用變異后的子代染色體代替父代染色體。

3.3 算法步驟

立體倉(cāng)庫(kù)出入庫(kù)調(diào)度同軌雙車(chē)的工作模式下，采用改進(jìn)的防碰撞原則雖然能有效防止兩車(chē)干預(yù)碰撞，但并不能使第1 次得到的貨架的左右分界線e為最優(yōu)分界線，所以在新型改進(jìn)的自適應(yīng)遺傳算法的每一次優(yōu)化迭代中插入滿足改進(jìn)防碰撞原則的最優(yōu)防碰撞邊界檢測(cè)機(jī)制，對(duì)分界線e進(jìn)行最優(yōu)處理，結(jié)合算法，最終得到同軌雙車(chē)調(diào)度模型的最優(yōu)解。

改進(jìn)的防碰撞原則劃分左右兩端貨區(qū)初始任務(wù)種群的詳細(xì)處理步驟如下：

步驟2 把出庫(kù)貨物、入庫(kù)貨物對(duì)應(yīng)的貨位坐標(biāo)的橫坐標(biāo)提取出來(lái)構(gòu)成集合U。且按照從小到大的順序進(jìn)行排列。設(shè)定左右兩側(cè)堆垛機(jī)工作區(qū)域的分界線為e=U（i），i∈［1，n］。工作區(qū)域分界線e代表的含義為從第1 列到第e列貨位的貨物為左端堆垛機(jī)的工作區(qū)域，第e+1 列到第I列為右側(cè)堆垛機(jī)的工作區(qū)域。

步驟4 判斷tL≤tR，若成立，則令i=i+1，e=U（i），i∈［1，n］，轉(zhuǎn)步驟3；否則，執(zhí)行步驟5。

步驟5 左右兩側(cè)堆垛機(jī)任務(wù)分配完成，獲得初始種群工作序列。從第1 列到第e列貨位為左側(cè)堆垛機(jī)的工作區(qū)域，此工作區(qū)的出/入庫(kù)貨物由左側(cè)堆垛機(jī)完成；從第e+1 列到I列貨位為右側(cè)堆垛機(jī)的工作區(qū)域，此工作區(qū)的出/入庫(kù)貨物由右側(cè)堆垛機(jī)完成。

步驟6 將左端堆垛機(jī)所分配的出/入庫(kù)貨物的任務(wù)序列隨機(jī)排序，生成若干任務(wù)序列；對(duì)右端堆垛機(jī)所分配的出入庫(kù)貨物的任務(wù)序列隨機(jī)排序，生成相應(yīng)的任務(wù)數(shù)列。

滿足改進(jìn)防碰撞原則的最優(yōu)防碰撞邊界檢測(cè)機(jī)制的具體操作如下：

步驟1 把左端堆垛機(jī)負(fù)責(zé)的左側(cè)工作區(qū)的出入庫(kù)任務(wù)種群根據(jù)式（13）分別計(jì)算出它們的個(gè)體適應(yīng)度值FL1，F(xiàn)L2，…，F(xiàn)Ln1，把右端堆垛機(jī)負(fù)責(zé)的右側(cè)工作區(qū)的出入庫(kù)任務(wù)種群根據(jù)式（14）分別計(jì)算出他 們的個(gè)體適應(yīng)度值FR1，F(xiàn)R2，…，F(xiàn)Rn2，其中n1、n2分別為左右兩端堆垛機(jī)負(fù)責(zé)出入庫(kù)任務(wù)序列的 個(gè) 體 個(gè) 數(shù)，然 后，定 義TL= min（FL1，F(xiàn)L2，…，F(xiàn)Ln1），TR= min（FR1，F(xiàn)R2，…，F(xiàn)Rn2）。

步驟2 判斷TL與TR的大小。

步驟3 如果TL≥TR，工作區(qū)分界線enew=e（i-1），即e取貨位坐標(biāo)的橫坐標(biāo)集合U左側(cè)上一元素，根據(jù)新工作區(qū)分界線重新調(diào)整兩堆垛機(jī)任務(wù)分配后，計(jì)算兩堆垛機(jī)的運(yùn)行時(shí)間TLnew，TRnew。判斷TLnew≤TRnew，如果成立，記錄下TRnew，比較TL與TRnew大小，若TL≤TRnew，記錄最優(yōu)解Tbest=TL，左右兩堆垛機(jī)的任務(wù)分配結(jié)果不變，若TL>TRnew，記錄最優(yōu)解Tbest=TRnew，將［enew，e］區(qū)間，原屬于左堆垛機(jī)任務(wù)序列的對(duì)應(yīng)任務(wù)刪除，添加到右堆垛機(jī)的任務(wù)序列中；如果不成立，同理循環(huán)。

步驟4 如果TL

在上述的最優(yōu)防碰撞邊界檢測(cè)機(jī)制操作步驟中，重新劃分的左右工作區(qū)分界線enew，仍然約束著如下關(guān)系：左側(cè)堆垛機(jī)分配任務(wù)所處貨架的最大橫坐標(biāo)小于右側(cè)堆垛機(jī)分配任務(wù)所處貨架的最小橫坐標(biāo)，所以經(jīng)過(guò)最優(yōu)防碰撞原則檢測(cè)機(jī)制優(yōu)化后的左右堆垛機(jī)分配的任務(wù)依然滿足改進(jìn)的防碰撞原則，能夠有效防止兩堆垛機(jī)在運(yùn)行時(shí)發(fā)生碰撞干預(yù)的現(xiàn)象。將最優(yōu)防碰撞原則檢測(cè)機(jī)制在NIGA 算法的步驟7 中調(diào)用，插入到在NIGA 的每一次優(yōu)化迭代中。

嵌入改進(jìn)防碰撞原則以及最優(yōu)防碰撞原則檢測(cè)機(jī)制的NIGA 算法對(duì)立體倉(cāng)庫(kù)同軌雙車(chē)出入庫(kù)調(diào)度優(yōu)化的具體步驟如下：

步驟1 設(shè)定初始參數(shù)，包括兩端I/O 臺(tái)O1、O2的坐標(biāo)，設(shè)置初始種群的規(guī)模m、以及NIGA 算法的最大迭代次數(shù)MAXiter。

步驟2 調(diào)用經(jīng)過(guò)改進(jìn)的防碰撞原則產(chǎn)生的兩個(gè)初始分配的種群Chrom1、Chrom2。Chrom1代表左端堆垛機(jī)需要負(fù)責(zé)的工作序列，種群Chrom2 代表右端堆垛機(jī)需要負(fù)責(zé)的工作序列。

步驟3 設(shè)定初始代數(shù)iter=0，若iter

步驟4 判斷（fmax-favg）/（fmax-fmin）≥1/2 是否成立，如果成立，則分別對(duì)種群Chrom1、Chrom2 先進(jìn)行選擇操作，然后進(jìn)行變異操作，最后進(jìn)行交叉操作；反之，先對(duì)種群進(jìn)行選擇操作，然后進(jìn)行交叉操作，最后進(jìn)行變異操作。

步驟5 經(jīng)過(guò)上述步驟，分別記錄進(jìn)化后Chrom1、Chrom2 兩種群的最優(yōu)值TL、TR。

步驟6 調(diào)用最優(yōu)防碰撞邊界檢驗(yàn)機(jī)制的具體步驟，檢驗(yàn)左、右工作區(qū)分界線e是否最優(yōu)，調(diào)整左右兩堆垛機(jī)的任務(wù)分配，并記錄最優(yōu)解Tbest；轉(zhuǎn)步驟4。

步驟7 迭代結(jié)束，輸出最優(yōu)解Tbest以及最優(yōu)解對(duì)應(yīng)的兩堆垛機(jī)最佳調(diào)度序列Chrom1、Chrom2。

嵌入改進(jìn)防碰撞原則和最優(yōu)防碰撞邊界檢驗(yàn)機(jī)制的NIGA 算法流程圖如圖2 所示。

圖2 嵌入改進(jìn)防碰撞原則的NIGA 算法流程圖Fig.2 Flow chart of NIGA algorithm embedded with improved anti-collision principle

改進(jìn)后的NIGA 算法，可以根據(jù)種群適應(yīng)度值的集中分散程度，來(lái)調(diào)整算法的進(jìn)化結(jié)構(gòu)，有效地提高了算法跳出局部最優(yōu)的能力，加快了算法的收斂速度。結(jié)合改進(jìn)防碰撞原則和最優(yōu)防碰撞邊界檢驗(yàn)機(jī)制后，NIGA 算法有效地解決了兩堆垛機(jī)工作時(shí)發(fā)生碰撞的問(wèn)題，并為它們分配了最優(yōu)的作業(yè)區(qū)域和任務(wù)序列，最終獲得了理想的堆垛機(jī)任務(wù)分配方案。

4 實(shí)驗(yàn)仿真及分析

為證明本文所提出改進(jìn)遺傳算法的有效性，現(xiàn)通過(guò)一個(gè)具體的立體倉(cāng)庫(kù)貨物出入庫(kù)實(shí)例來(lái)進(jìn)行驗(yàn)證。某企業(yè)的自動(dòng)化立體倉(cāng)庫(kù)的一個(gè)貨架有12層80 列，共有960 個(gè)貨位。每個(gè)貨位的位置固定，且大小相同，每個(gè)貨位每次最多存儲(chǔ)一個(gè)貨物。貨架的兩端各分布著一個(gè)I/O 臺(tái)，倉(cāng)庫(kù)的巷道左右兩端分別放置了型號(hào)規(guī)格完全相同的兩堆垛機(jī)，兩堆垛機(jī)在巷道上可以同時(shí)工作，且分別為各自負(fù)責(zé)的I/O 臺(tái)執(zhí)行貨物的出入庫(kù)作業(yè)，貨架及兩堆垛機(jī)的具體信息見(jiàn)表1。

表1 立體倉(cāng)庫(kù)規(guī)格信息及堆垛機(jī)配置信息Table 1 Specification information of warehouse and con?figuration information of stacker

立體倉(cāng)庫(kù)內(nèi)有一批要執(zhí)行的出入庫(kù)任務(wù)，包含17 個(gè)入庫(kù)任務(wù)和15 個(gè)出庫(kù)任務(wù)，任務(wù)坐標(biāo)位置信息如表2 所示。

表2 出入庫(kù)任務(wù)坐標(biāo)Table 2 Coordinates of storage and retrieval tasks

為了驗(yàn)證本文算法的可行性以及優(yōu)越性，以NIGA 算法為基準(zhǔn)，分別利用GA，自適應(yīng)遺傳算法（Adaptive genetic algorithm，AGA）對(duì)上述的一批出入庫(kù)任務(wù)坐標(biāo)進(jìn)行優(yōu)化求解。對(duì)初始參數(shù)進(jìn)行設(shè)定，初始種群的規(guī)模m=100，最大迭代次數(shù)MAXiter=100，pc=0.6，pm=0.2。使用matlab2018b對(duì)上述立體倉(cāng)庫(kù)參數(shù)以及出/入庫(kù)任務(wù)信息進(jìn)行編程實(shí)現(xiàn)，分別用NIGA、GA、AGA3 種算法對(duì)上述所給的出入庫(kù)貨物相關(guān)信息進(jìn)行優(yōu)化。

由圖3 可知，NIGA 算法和AGA 算法隨著迭代次數(shù)的增加均收斂到了最優(yōu)解307 s，而NIGA算法在第9 代就收斂到最優(yōu)值，其迭代速度更快，而GA 算法則陷入局部最優(yōu)，在第14 代才得到局部最優(yōu)解328 s，具體比較結(jié)果見(jiàn)表3。與GA、AGA 算法相比，NIGA 算法收斂速度更快，跳出局部最優(yōu)能力更強(qiáng)，迭代效果更優(yōu)。

圖3 針對(duì)表2 任務(wù)的目標(biāo)函數(shù)進(jìn)化曲線Fig.3 Evolution curves of the objective function for tasks in Table 2

表3 3 種算法結(jié)果對(duì)比Table 3 Comparison results of three algorithms

由NIGA 算法對(duì)表2 的出入庫(kù)貨物序列優(yōu)化后的最優(yōu)解輸出的左堆垛機(jī)調(diào)度序列為（3 8 5 4 7 6 2 1 1 7 4 3 5 6 2），右堆垛機(jī)調(diào)度序列為（4 9 2 3 6 7 5 8 1 3 7 8 1 2 6 4 5）。相應(yīng)的堆垛機(jī)工作路線如圖4 所示。

根據(jù)圖4 可知，通過(guò)NIGA 算法對(duì)表2 中的出入庫(kù)貨物信息進(jìn)行優(yōu)化，工作區(qū)的分界線為e=40，即從貨架的第1～40 列的出入庫(kù)貨物由左堆垛機(jī)負(fù)責(zé)調(diào)度，貨架第41～80 列貨物由右堆垛機(jī)負(fù)責(zé)調(diào)度，左右兩堆垛機(jī)分別在自己的工作區(qū)域內(nèi)工作，不會(huì)發(fā)生碰撞干預(yù)現(xiàn)象。

圖4 針對(duì)表2 任務(wù)得到優(yōu)化后兩堆垛機(jī)的行駛路線圖Fig.4 Driving routes of the two stackers after optimization for tasks in Table 2

為了證明嵌入改進(jìn)防碰撞原則以及最優(yōu)防碰撞邊界檢驗(yàn)機(jī)制后的NIGA 算法能為堆垛機(jī)最大程度合理分配任務(wù)，使出入庫(kù)調(diào)度結(jié)果達(dá)到最佳，同文獻(xiàn)［15］的防碰撞原則以及任務(wù)分配機(jī)制作比較，用本文改進(jìn)遺傳算法對(duì)文獻(xiàn)［15］中的出入庫(kù)任務(wù)數(shù)據(jù)進(jìn)行優(yōu)化求解。兩算法參數(shù)調(diào)整一致，NI?GA 算法優(yōu)化后堆垛機(jī)運(yùn)行時(shí)間進(jìn)化曲線如圖5 所示，兩堆垛機(jī)行駛路線圖如圖6 所示。文獻(xiàn)［15］中利用改進(jìn)的化學(xué)反應(yīng)優(yōu)化（Improved chemical reac?tion optimization，ICRO）算法求解得到的優(yōu)化值為312.67 s，兩堆垛機(jī)的工作區(qū)間的分界線為e=39，而利用本文NIGA 算法求得的優(yōu)化值為251 s，減少了61.67 s，得到的兩堆垛機(jī)的工作區(qū)間的最佳分界線為e=37。

圖5 目標(biāo)函數(shù)最優(yōu)值進(jìn)化路線圖Fig.5 Evolution curve of the objective function

圖6 兩堆垛機(jī)優(yōu)化后行駛路徑圖Fig.6 Driving routes of the two stackers after optimization

5 結(jié) 論

針對(duì)目前大型企業(yè)的自動(dòng)化立體倉(cāng)庫(kù)規(guī)模較大，調(diào)度難的現(xiàn)象，分析了兩端式雙堆垛機(jī)出入庫(kù)調(diào)度問(wèn)題，建立了相應(yīng)的數(shù)學(xué)模型。在該模型的基礎(chǔ)上提出了改進(jìn)防碰撞策略以及最優(yōu)防碰撞邊界檢測(cè)機(jī)制的解決方法，并提出一種新的改進(jìn)遺傳算法進(jìn)行優(yōu)化。對(duì)比實(shí)驗(yàn)結(jié)果表明，該算法能夠根據(jù)種群適應(yīng)度值的集中分散情況，從而自適應(yīng)地調(diào)節(jié)進(jìn)化過(guò)程中交叉操作、變異操作的先后順序，加快了算法的收斂速度，提高了算法避免陷入局部最優(yōu)的能力，并在每次迭代中嵌入改進(jìn)防碰撞策略以及最優(yōu)防碰撞邊界檢測(cè)機(jī)制，有效地確定了兩堆垛機(jī)工作區(qū)的最佳分界線，避免了堆垛機(jī)運(yùn)行中的碰撞，平衡了兩堆垛機(jī)的工作時(shí)間，有效地解決了大型自動(dòng)化立體倉(cāng)庫(kù)雙堆垛機(jī)的出入庫(kù)調(diào)度問(wèn)題。本文對(duì)立體倉(cāng)庫(kù)的布局僅考慮了兩端式I/O 臺(tái)布置，在實(shí)際工作中，為了生產(chǎn)調(diào)度的方便，I/O 臺(tái)也可能放置在貨架中間。另外，本文假設(shè)堆垛機(jī)的水平和垂直速度是恒定的，堆垛機(jī)每次完成任務(wù)后都返回至I/O 臺(tái)。因此在今后的工作中，堆垛機(jī)的水平、垂直加減速和?？奎c(diǎn)的位置選擇也是未來(lái)研究中有待解決的問(wèn)題。