蔡安江，史啟程

（西安建筑科技大學(xué) 機(jī)電工程學(xué)院，陜西 西安 710055）

1 引言

自動(dòng)化立體倉庫是當(dāng)代物流技術(shù)，倉儲(chǔ)技術(shù)、自動(dòng)化和計(jì)算機(jī)技術(shù)高度集成的產(chǎn)物[1]，衡量其存取效率的標(biāo)準(zhǔn)是單位時(shí)間內(nèi)貨物的存取量，為保證整個(gè)倉庫的性能指標(biāo)最優(yōu)，需要對(duì)堆垛機(jī)路徑進(jìn)行調(diào)度，降低存/取貨物所需時(shí)間，使其能夠高效協(xié)調(diào)運(yùn)轉(zhuǎn)[2]。

堆垛機(jī)調(diào)度問題是在倉庫模型和出/入庫位點(diǎn)確定的前提下，合理安排任務(wù)執(zhí)行順序，以求得所需時(shí)間最短的方案。國內(nèi)外學(xué)者對(duì)立體倉庫路徑優(yōu)化調(diào)度問題進(jìn)行了大量的研究，文獻(xiàn)[3]用遺傳算法對(duì)倉庫調(diào)度問題進(jìn)行研究，該算法很容易陷入“早熟”，對(duì)求解的精度有一定影響；文獻(xiàn)[4]將模擬退火算法和遺傳算法相結(jié)合，將每次迭代的結(jié)果當(dāng)作父代種群，兩種算法交替進(jìn)行，實(shí)際每次迭代種群進(jìn)化兩次，算法結(jié)合方式過于生硬；在上述研究中，均未對(duì)同軌雙車情況下堆垛機(jī)的調(diào)度路徑模型進(jìn)行研究，而雙車存儲(chǔ)效率遠(yuǎn)高于單車。細(xì)菌覓食優(yōu)化算法（Bacterial ForagingOptimization BFO）是文獻(xiàn)[5]于2002年提出的，引起不同領(lǐng)域廣泛關(guān)注和應(yīng)用，然而目前將BFO算法應(yīng)用于自動(dòng)化立體倉庫調(diào)度的并不多，該算法針對(duì)種群的單一性擴(kuò)大搜索范圍，因此文章通過BFO算法對(duì)趨化步長加以改進(jìn)，使其能夠?qū)?yōu)，在搜索過程中具有自適應(yīng)調(diào)節(jié)，從而提高收斂速度和倉儲(chǔ)效率。

2 問題描述

在生產(chǎn)物流中，傳統(tǒng)倉庫模型貨架縱深過長，導(dǎo)致單臺(tái)堆垛機(jī)運(yùn)行時(shí)間較長，出/入庫臺(tái)或其緩沖區(qū)經(jīng)常處于閑置狀態(tài)[6]。為縮短出/入庫臺(tái)到貨架深處庫位點(diǎn)的距離，提高庫位緩沖區(qū)的利用率，提出一種兩端式同軌雙車的倉庫模型。

同軌雙車模式下兩端式倉庫布局結(jié)構(gòu)圖，如圖1所示。通過在立體倉庫兩端各設(shè)置一個(gè)出/入庫臺(tái)，并在同一巷道上增加一臺(tái)堆垛機(jī)，將貨架深處庫位點(diǎn)轉(zhuǎn)移至倉庫中心位置，縮短堆垛機(jī)行進(jìn)路線，大幅提高存取效率。

針對(duì)同軌雙車倉庫布局模型，當(dāng)一批存/取任務(wù)輸入后，同一軌道上兩臺(tái)堆垛機(jī)同時(shí)工作，完成這批任務(wù)所需時(shí)間為兩臺(tái)堆垛機(jī)完成各自任務(wù)后，用時(shí)最長的堆垛機(jī)的運(yùn)行時(shí)間：

式中：TL，TR—貨架左右兩端堆垛機(jī)完成各自任務(wù)的運(yùn)行時(shí)間。

將一條入庫任務(wù)和一條出庫任務(wù)組合而成的復(fù)合任務(wù)，稱為DC任務(wù)；單獨(dú)執(zhí)行一條入庫任務(wù)或一條出庫任務(wù)，稱為SC任務(wù)[7]。組合成DC任務(wù)，可以減少堆垛機(jī)從出/入庫臺(tái)到庫位點(diǎn)的往返次數(shù)，因而效率更高。在實(shí)際應(yīng)用中，入庫任務(wù)數(shù)和出庫任務(wù)數(shù)往往不等，基于此，同軌雙車模式下，其中任意一臺(tái)堆垛機(jī)運(yùn)行的時(shí)間為

其中，m=min（Npike，Nput），n=max（Npike，Nput）。

式中：TDCi—堆垛機(jī)執(zhí)行第i條DC任務(wù)花費(fèi)的時(shí)間；TSCi—堆垛機(jī)執(zhí)行第i條SC任務(wù)花費(fèi)的時(shí)間；Npike—出庫任務(wù)數(shù)量；Nput—入庫任務(wù)數(shù)量。

3 出入庫調(diào)度模型

在同軌雙車運(yùn)行模式下，兩堆垛機(jī)在同一巷道上同時(shí)工作，它們各自的水平位移和垂直位移互不干涉。故其中一臺(tái)堆垛機(jī)完成一次存/取任務(wù)所花費(fèi)的時(shí)間為水平、垂直作業(yè)所需時(shí)間的最大值。設(shè)一個(gè)貨架的長度為l、高度為h，堆垛機(jī)水平位移速度為Vx、垂直位移速度為Vy。則其中一臺(tái)堆垛機(jī)以位置［xa，ya］為起點(diǎn)，以位置［xb，yb］為終點(diǎn)，所需時(shí)間為：

3.1 任務(wù)分配方式

統(tǒng)籌分配原則的目標(biāo)是在一組出/入庫任務(wù)分配完成后，兩堆垛機(jī)完成各自任務(wù)的運(yùn)行時(shí)間最短；兩堆垛機(jī)運(yùn)行時(shí)間差的絕對(duì)值最小。數(shù)學(xué)模型表達(dá)如下：

3.2 DC作業(yè)方式

同軌雙車模式下的DC作業(yè)方式為：一批出/入庫任務(wù)分配給兩臺(tái)堆垛機(jī)后，兩堆垛機(jī)同時(shí)工作，各自從出/入庫臺(tái)運(yùn)載貨物運(yùn)行到入庫任務(wù)指定庫位點(diǎn)，卸載貨物后直接運(yùn)行到出庫任務(wù)指定庫位點(diǎn)裝載貨物，再將貨物運(yùn)至出/入庫臺(tái)。同軌雙車情況下，DC作業(yè)方式下堆垛機(jī)路徑示例，如圖2所示。

圖2 DC作業(yè)方式下堆垛機(jī)路徑示例圖Fig.2 DC Operating Mode Stacker Road Sample Diagram

圖中：IO—出/入庫臺(tái)；P1，P3—兩堆垛機(jī)的入庫貨位；P2，P4—兩堆

垛機(jī)的出庫貨位。

式中：TDC—兩臺(tái)堆垛機(jī)完成DC任務(wù)的運(yùn)行時(shí)間中較大值。

3.3 SC作業(yè)方式

在實(shí)際的應(yīng)用過程中，入庫任務(wù)數(shù)量和出庫任務(wù)數(shù)量并不相同，兩堆垛機(jī)在執(zhí)行完組合而成的數(shù)條DC任務(wù)后，剩下的入庫或出庫任務(wù)即為SC任務(wù)。同軌雙車情況下，SC作業(yè)方式下堆垛機(jī)路徑示例，如圖3所示。

圖3 SC作業(yè)方式下堆垛機(jī)路徑示例圖Fig.3 SC Operating Mode Stacker Road Sample Diagram

圖中：IO—出/入庫臺(tái)；P1—分配給堆垛機(jī)的入庫貨位；P2—分配給堆垛機(jī)的出庫貨位。

只討論其中一臺(tái)堆垛機(jī)，運(yùn)行路徑為IO→P1→IO，無論是入庫任務(wù)還是出庫任務(wù)，運(yùn)行時(shí)間為：

3.4 建立同軌雙車模式下調(diào)度模型

在實(shí)際執(zhí)行出/入庫任務(wù)中，一批任務(wù)在分配給兩臺(tái)堆垛機(jī)后，每臺(tái)堆垛機(jī)獲得的出庫任務(wù)、入庫任務(wù)的數(shù)量可能不一致。因此假設(shè)兩堆垛機(jī)分別獲得nL、nR個(gè)入庫任務(wù)與mL、mR個(gè)出庫任務(wù)，?。?/p>

根據(jù)在同軌雙車情況下對(duì)DC任務(wù)、SC任務(wù)的分析，兩堆垛機(jī)分別有QL2、QR2個(gè)DC任務(wù)和QL1-QL2、QR1-QR2個(gè)SC任務(wù)。

基于此，貨架兩端堆垛機(jī)完成各自任務(wù)的運(yùn)行時(shí)間為：

因此，完成一批出/入庫任務(wù)時(shí)，堆垛機(jī)最優(yōu)路徑模型為：

4 進(jìn)出庫調(diào)度優(yōu)化

利用BFO算法對(duì)堆垛機(jī)進(jìn)行路徑優(yōu)化分析，通過四種基元反應(yīng)操縱，求得同軌雙車的最優(yōu)或近似最優(yōu)任務(wù)序列。

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

為了方便問題的求解，采用基于任務(wù)編號(hào)排序的間接編碼法[8]將每臺(tái)堆垛機(jī)的出庫任務(wù)和入庫任務(wù)分別寫成兩段編碼。

4.2 算法步驟

同軌雙車運(yùn)行模式下，采用統(tǒng)籌分配原則不能保證一次分配的結(jié)果為最優(yōu)，通過在BFO算法中增加調(diào)整分配結(jié)果的操作，可逐步尋得最優(yōu)解[9]。細(xì)菌覓食優(yōu)化算法具體步驟如下：

步驟1設(shè)定初始參數(shù)，包括出/入庫任務(wù)庫位點(diǎn)坐標(biāo)，初始分子個(gè)數(shù)，最大反應(yīng)次數(shù)Max-BFO；

步驟2根據(jù)統(tǒng)籌分配原則將任務(wù)分配給兩臺(tái)堆垛機(jī)，產(chǎn)生初代分子；

步驟3：初始化細(xì)菌種群個(gè)體位置，定義初始化參數(shù)Niter、Nc、Ns、Nre、Ned；

步驟4：種群進(jìn)化代數(shù)：n=n+1；

步驟 3：遷移代數(shù)：l=l+1；

步驟 4：繁殖行為：k=k+1；

步驟 5：趨化行為：j=j+1；

步驟6：不可行解可能攜帶若干可行解無法獲取的有用信息，如距離全局最優(yōu)解較近，能夠快速獲取搜索全局最優(yōu)解，采用提出的部分不可行解保留策略以提高算法收斂速度；

步驟7：若j≤Nc，則返回步驟5繼續(xù)趨化操作；

步驟8：種群繁殖，達(dá)到臨界趨化次數(shù)時(shí)細(xì)菌將完成一個(gè)生命周期，并根據(jù)健康評(píng)價(jià)標(biāo)準(zhǔn)進(jìn)行優(yōu)勝劣汰，將給定的序號(hào)為1到N的N個(gè)細(xì)菌個(gè)體，定義第i個(gè)細(xì)菌健康程度為：

式中表示種群中每個(gè)細(xì)菌在趨化過程中完成適應(yīng)度的累加之和，并對(duì)N個(gè)細(xì)菌健康程度指標(biāo)按降序進(jìn)行排列，只保留健康程度較好的部分細(xì)菌。

步驟9：若k≤Nre，則返回步驟4繼續(xù)繁殖操作；

步驟10：遷移操作，為了增強(qiáng)細(xì)菌的全局尋優(yōu)能力，保持規(guī)則進(jìn)行概率遷移，種群內(nèi)的所有細(xì)菌將會(huì)按照自身指定的概率遷移到解空間中一個(gè)隨機(jī)位置；

步驟11：若l≤Ned，則返回步驟3繼續(xù)執(zhí)行遷移操作；

步驟12：若n≤Niter，則返回步驟2繼續(xù)種群進(jìn)化操作；否則輸出優(yōu)化結(jié)果。

統(tǒng)籌分配原則的BFO算法流程圖，如圖4所示。

圖4 統(tǒng)籌分配原則的BFO算法流程圖Fig.4 Flow Chart of BFO Algorithm of Overall Allocation Principle

通過上述融入統(tǒng)籌分配原則的BFO算法的操作步驟，可以對(duì)路徑優(yōu)化問題進(jìn)行有效的全局搜索[10]，通過分解與合成操作，不易使算法陷入局部最小值。

5 仿真驗(yàn)證

以某企業(yè)實(shí)際自動(dòng)化倉庫為研究對(duì)象，驗(yàn)證數(shù)學(xué)模型的適應(yīng)性和BFO算法的有效性。倉庫貨架位置固定，大小一致，每排貨架共840個(gè)貨位，分為12層，70列，每排貨架兩端各一個(gè)出/入庫臺(tái)，出/入庫臺(tái)坐標(biāo)分別為［0，1］，［71，1］，用于工業(yè)產(chǎn)品的出庫運(yùn)輸和入庫存儲(chǔ)。

在某批出/入庫任務(wù)中，對(duì)應(yīng)的庫位點(diǎn)坐標(biāo)，如表1所示。提出的細(xì)菌覓食算法可以使可搜索的解空間得到擴(kuò)大的同時(shí)，可以有效地引導(dǎo)BFO向最優(yōu)解靠近，不僅提高求解質(zhì)量，也提高收斂速度。利用所建立的堆垛機(jī)調(diào)度模型對(duì)上述出/入庫任務(wù)運(yùn)用MATLAB進(jìn)行仿真優(yōu)化，堆垛機(jī)運(yùn)行所需時(shí)間的優(yōu)化曲線，如圖5所示。

表1 出/入庫任務(wù)坐標(biāo)Tab.1 Out/In Bound Task Coordinates

圖5 堆垛機(jī)運(yùn)行時(shí)間優(yōu)化曲線Fig.5 Optimization Curve of Stacker Running Time

由圖5可以看出，堆垛機(jī)的運(yùn)行時(shí)間隨著算法迭代次數(shù)的增加不斷減小，于第42代求得最優(yōu)解。

出/入庫任務(wù)優(yōu)化前后，堆垛機(jī)運(yùn)行時(shí)間的對(duì)比，如表2所示。由表2知，通過優(yōu)化后堆垛機(jī)的調(diào)度效率提高了29.5%。在求得堆垛機(jī)路徑調(diào)度最優(yōu)解后，根據(jù)輸出的最優(yōu)解任務(wù)序列，其堆垛機(jī)運(yùn)行路徑圖，如圖6所示。

表2 優(yōu)化前后堆垛機(jī)運(yùn)行時(shí)間Tab.2 Stacker Running Time Before and After Optimization

圖6堆垛機(jī)運(yùn)行路徑圖Fig.6 Stacker Running Path Map

圖6 中，白色方塊為倉庫兩端出/入庫臺(tái)；黑色方塊及實(shí)線為SC任務(wù)的運(yùn)行路徑；灰色方塊及虛線為DC任務(wù)的運(yùn)行路徑?？梢钥闯?，兩臺(tái)堆垛機(jī)各自執(zhí)行分配所得的出/入庫任務(wù)，不存在碰撞情況。

結(jié)合表2，兩堆垛機(jī)運(yùn)行時(shí)間差的絕對(duì)值為ΔT=2；Right堆垛機(jī)先完成任務(wù)后，如果執(zhí)行用時(shí)最短的編號(hào)為9的出庫任務(wù)，所需時(shí)間為tmin=34.27。滿足式（14）的分配原則，故分配結(jié)果為最優(yōu)解。

6 結(jié)束語

為提高立體倉庫的存儲(chǔ)效率，滿足物流系統(tǒng)性能要求，研究了在同軌雙車情況下，堆垛機(jī)的路徑優(yōu)化調(diào)度模型。取得以下成果：（1）基于BFO算法鄰域搜索能力和跳出局部極小值能力強(qiáng)的特點(diǎn)，對(duì)所建立的同軌雙車堆垛機(jī)調(diào)度模型進(jìn)行優(yōu)化分析，縮短了堆垛機(jī)工作時(shí)長，通過優(yōu)化，堆垛機(jī)的調(diào)度效率提高了29.5%。（2）結(jié)合實(shí)際任務(wù)進(jìn)行仿真驗(yàn)證表明，所建立的調(diào)度模型對(duì)兩端為出/入庫臺(tái)的同軌雙車調(diào)度問題有很好的適應(yīng)性，采用統(tǒng)籌分配原則可有效避免碰撞和產(chǎn)生無效任務(wù)序列，其分配結(jié)果是合理、高效的。BFO算法在解決此類問題上是有效可行的。