三載具AS/RS作業(yè)調(diào)度優(yōu)化

王 婷，王潔慈

（陜西國際商貿(mào)學(xué)院，陜西 西安 712046）

0 引言

傳統(tǒng)堆垛機(jī)只有一個貨位，每次進(jìn)出最多只能裝載一個貨物，這不僅極大的浪費(fèi)了存取調(diào)度時間，而且加速了設(shè)備的損耗。隨著社會需求的不斷發(fā)展，這種一進(jìn)一出的工作方式已不能滿足企業(yè)倉儲和配送的需求。為解決上述問題，提出一種新型的倉庫，即多載具自動化立體倉庫（multi-shuttle-automated Storage and Retrieval System）。三載具堆垛機(jī)作為多載具自動化立體倉庫中常見的一種設(shè)備形式，一個子行程可以完成最多三個存貨和三個取貨任務(wù)，很好地解決了傳統(tǒng)堆垛機(jī)一次只能裝載一個貨物的問題，提高了存儲效率。單載具AS/RS 目前的研究成果已經(jīng)不能滿足新型AS/RS運(yùn)作上的要求，故而研究合理調(diào)度策略以提高三載具AS/RS作業(yè)效率刻不容緩。

現(xiàn)有文獻(xiàn)中，諸多研究仍為單載具AS/RS，卞和營，等詳細(xì)分析了堆垛機(jī)出入庫的作業(yè)方式，建立了數(shù)學(xué)模型，提出了一種基于改進(jìn)遺傳算法的路徑優(yōu)化方法；蔡安江，等以堆垛機(jī)執(zhí)行任務(wù)所需總時間為評價標(biāo)準(zhǔn)，建立了一種基于混合命令序列的堆垛機(jī)調(diào)度模型；靳萌，等采用免疫遺傳算法求解串列立體倉庫的存取作業(yè)調(diào)度問題；李博文，等采用遺傳算法優(yōu)化的集束搜索對堆垛機(jī)運(yùn)行路徑進(jìn)行優(yōu)化，提高運(yùn)行效率。Hachemi K，等以雙倍命令周期時間最小對單載具AS/RS 的存取作業(yè)進(jìn)行排序處理；Chung E，等將存取調(diào)度問題處理為廣義的排序問題，并引入啟發(fā)式方法進(jìn)行求解，優(yōu)化效果顯著；文獻(xiàn)[7-9]對單載具重力式移動貨架存取調(diào)度作業(yè)進(jìn)行研究，以旅行時間最小建立數(shù)學(xué)模型，并進(jìn)行求解。上述文獻(xiàn)均在單載具存取系統(tǒng)作業(yè)調(diào)度中取得了良好的優(yōu)化效果，但對于三載具存取系統(tǒng)而言，要在單載具基礎(chǔ)上考慮分組問題及子行程內(nèi)部順序問題。

關(guān)于多載具AS/RS 的研究，文獻(xiàn)[10-11]和文獻(xiàn)[12-13]分別以雙載具和三載具AS/RS為研究對象，但主要對AS/RS的工作效率和績效性能進(jìn)行評價；Yang P，等研究雙載具AS/RS進(jìn)出庫復(fù)合作業(yè)，并采用一種可變鄰域搜索的方法進(jìn)行求解。只考慮了單周期下的優(yōu)化改進(jìn)，并未對整個訂單任務(wù)進(jìn)行分析研究；Drazen Popovic，等在分類存儲策略下，對三載具AS/RS的進(jìn)出庫調(diào)度問題進(jìn)行求解，實(shí)例結(jié)果表明了遺傳算法求解該問題的優(yōu)越性；Tanaka S，等將給定貨位的多載具AS/RS作業(yè)排序問題歸納為車輛路徑（有載貨量限制）問題并對其進(jìn)行探究；文獻(xiàn)[15-16]雖涉及多載具AS/RS存取貨作業(yè)調(diào)度問題，但是忽略了作業(yè)分組配對，只是從作業(yè)排序角度進(jìn)行了探究。

針對三載具AS/RS作業(yè)調(diào)度問題，根據(jù)其工作方式，本文在研究時不再局限于單周期下的優(yōu)化而是針對整批訂單，將問題轉(zhuǎn)化為分組問題、模式問題以及順序問題。且上述文獻(xiàn)中，堆垛機(jī)均假設(shè)為勻速運(yùn)動，而堆垛機(jī)在實(shí)際運(yùn)行中，具有一定的加速度，本文以更加接近實(shí)際的角度考慮堆垛機(jī)行走過程中的加速度，建立數(shù)學(xué)模型，利用混合人工蜂群算法求解模型。并采用三種算法對實(shí)例進(jìn)行優(yōu)化比較。在此基礎(chǔ)上，選用混合人工蜂群算法對單、雙、三載具堆垛機(jī)的運(yùn)行效率進(jìn)行計(jì)算對比。

1 問題描述

三載具AS/RS 的作業(yè)調(diào)度是指堆垛機(jī)根據(jù)訂單情況載入貨物，以適合的進(jìn)出庫方式完成作業(yè)任務(wù)。由于三載具堆垛機(jī)一次可以同時載多個貨物，在考慮整個訂單存取順序的同時，也要考慮堆垛機(jī)一個子行程內(nèi)的存取順序，完成合理配置，提高工作效率。

三載具AS/RS與單載具AS/RS相比，一個子行程可以完成最多三個貨物的存貨和取貨作業(yè)。在三載具AS/RS 配置下，對于一個訂單內(nèi)的存取貨復(fù)合作業(yè)，首先進(jìn)行指令分組，分組后每個組就是一個子行程。為了提高堆垛機(jī)工作效率，每個子行程往往采取“滿載”作業(yè)，即一個子行程可同時處理3個存貨作業(yè)和3個取貨作業(yè)，每個子行程相當(dāng)于遍歷6個位置的小型TSP問題。考慮到企業(yè)的實(shí)際操作情況，在入庫時為了避免多次搬運(yùn)造成的浪費(fèi)，入庫順序一定，即采取先到先服務(wù)規(guī)則，而出庫貨位是由系統(tǒng)生成，出庫順序不定，由后續(xù)解確定最佳出庫順序。

本文研究三載具AS/RS的出入庫聯(lián)合作業(yè)，是指接收到出入庫指令后，對出入庫任務(wù)進(jìn)行配對聯(lián)合、劃分任務(wù)組，使整個訂單上的任務(wù)指令都以任務(wù)組的形式呈現(xiàn)，每組完成3個入庫任務(wù)和3個出庫任務(wù)，每組內(nèi)的完成順序需再進(jìn)一步分析，直到完成所有任務(wù)組。在優(yōu)化過程中，統(tǒng)一考慮訂單任務(wù)分組、堆垛機(jī)行走模式以及行走順序問題。

2 三載具AS/RS調(diào)度優(yōu)化

傳統(tǒng)單載具AS/RS的復(fù)合調(diào)度作業(yè)中，堆垛機(jī)一次行程載入一個貨物同時載出一個貨物，在行程中只考慮作業(yè)配對問題，而對于三載具AS/RS作業(yè)調(diào)度的優(yōu)化還需考慮指令分組、堆垛機(jī)行走模式以及子行程內(nèi)部順序問題。

2.1 指令分組

指令分組是指三載具AS/RS 中對出入庫任務(wù)進(jìn)行劃分任務(wù)組的過程，當(dāng)出入庫任務(wù)不相等時，以補(bǔ)充虛擬入庫/出庫點(diǎn)進(jìn)行調(diào)整，使得撥次中的任務(wù)都以任務(wù)組的形式呈現(xiàn)，然后再對任務(wù)組內(nèi)的行走順序進(jìn)行分析，計(jì)算行程時間。

對于三載具AS/RS而言，一個子行程要完成三個存貨和三個取貨任務(wù)，現(xiàn)以一個入庫任務(wù)多于出庫任務(wù)的訂單為例，入庫任務(wù)為（56，105，19，223，417，29，2，88，76，25，312，74），出庫任務(wù)為（12，542，411，30，79，300，49，66，211，315），對于該訂單任務(wù)，有多種分組方式，在不同分組下，有著不同的行程，將直接影響到整個行程時間。不同分組結(jié)果見表1。

表1 分組結(jié)果表

2.2 行走模式

對于已經(jīng)分組后的子行程，每個子行程對應(yīng)堆垛機(jī)的一次行走過程。堆垛機(jī)按照其行走模式完成各個子行程。堆垛機(jī)“滿載”情況下，必須先存入一個貨物后才有空載位存放要取的貨物，根據(jù)載位的空、滿狀態(tài)可以得出存取貨物的關(guān)系必須滿足：存貨先于取貨，需有空載位可以存放要取的貨物。

根據(jù)實(shí)際情況，三載具AS/RS中堆垛機(jī)子行程的可行行走模式有以下五種，如圖1所示：S表示存貨作業(yè)，R表示取貨作業(yè)。L1：存→取→存→取→存→取，如圖1（a）所示；L2：存→取→存→存→取→取，如圖1（b）所示；L3：存→存→取→取→存→取，如圖1（c）所示；L4：存→存→取→存→取→取，如圖1（d）所示；L5：存→存→存→取→取→取，如圖1（e）所示。

圖1 三載具堆垛機(jī)行走模式圖

2.3 行走順序

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

結(jié)合以上相關(guān)問題分析，提出模型假設(shè)：（1）給定撥次內(nèi)，存取貨指令已知，且對應(yīng)貨位信息已知；（2）入庫順序一定，不可調(diào)換；出庫順序可以調(diào)整；（3）堆垛機(jī)為勻加速運(yùn)動；（4）貨物裝載時間忽略不計(jì)。

假設(shè)貨架水平方向即列方向?yàn)椋怪狈较蚣磳臃较驗(yàn)?，可得堆垛機(jī)的實(shí)際運(yùn)行時間，其公式為：

根據(jù)三載具AS/RS 的出入庫作業(yè)方式建立數(shù)學(xué)模型，需要考慮分組、模式以及順序問題。

對于每組的子行程而言，主要考慮行走模式和出庫作業(yè)順序問題，一個子行程內(nèi)可以有多個可行解，不同模式下不同順序造成三載具AS/RS 的子行程內(nèi)的解具有多樣化。設(shè)行走模式中出庫任務(wù)為1，2，3，取值為{123} 并且1 ≠p2 ≠p3。則對于每個子行程，貨物出入庫的時間行程時間為

Z為決策變量，當(dāng)Z=1時表示取貨指令在第個子行程中被訪問到，否則Z=0。式(6)表示每個指令對應(yīng)的貨位都會被訪問；式(7)表示每個子行程執(zhí)行三個取貨任務(wù)。

3 混合人工蜂群算法

人工蜂群算法(Artificial Bee Colony，ABC)是由Karaboga于2005年提出的一種新穎的基于群智能的全局優(yōu)化算法，蜜蜂根據(jù)各自的分工采蜜，并交流信息，從而找到問題的最優(yōu)解。

蜜蜂執(zhí)行搜索活動的過程可以概括為：

（1）采蜜蜂確定蜜源，對其進(jìn)行開采并記錄相關(guān)數(shù)據(jù)，尋找新密源并與觀察蜂分享數(shù)據(jù)；（2）觀察蜂在舞蹈區(qū)等待采蜜蜂分享的數(shù)據(jù)，并在臨近處選擇蜜源；（3）偵查蜂隨機(jī)找一個有意義的新蜜源。

算法流程如圖2所示。

圖2 人工蜂群算法流程圖

3.1 初始化階段

初始化人工蜂群規(guī)模(2*SN)。蜜源代表了算法在搜索空間內(nèi)的可行解，初始化搜索空間內(nèi)的可行解依照式（8）隨機(jī)產(chǎn)生。

3.2 蜂群搜索階段

人工蜂群算法中采蜜蜂的搜索方程表達(dá)式為：

式中：V表示新蜜源；X為蜜源的第維位置，X為隨機(jī)選擇的不等于的蜜源的第維位置；?控制X領(lǐng)域內(nèi)蜜源的出現(xiàn)，為[-11]內(nèi)的隨機(jī)數(shù)。采蜜蜂對更新后的蜜源采用貪婪選擇策略進(jìn)行選取。觀察蜂以概率值選擇蜜源，表達(dá)式為：

式中：為解的適應(yīng)度值；為種群中解得個數(shù)。

偵察蜂在其領(lǐng)域范圍內(nèi)搜索新蜜源，蜜源的搜索次數(shù)存在一個閥值lim it，當(dāng)蜜源經(jīng)過限定最大開采次數(shù)lim it 后，如果仍然沒有改進(jìn)，此時采蜜蜂轉(zhuǎn)變偵察蜂，并按照式(8)進(jìn)行隨機(jī)搜索產(chǎn)生新蜜源，新蜜源將代替該蜜源。

ABC的尋優(yōu)方式傾向于不斷開發(fā)新的解，但開發(fā)效率低，為此，受到粒子群算法尋優(yōu)方程的啟發(fā)，提出混合人工蜂群算法（HABC），即將粒子群算法中的粒子不斷向個體最優(yōu)和全局最優(yōu)粒子靠近的尋優(yōu)策略代入ABC算法中，可以得出一個新的搜索方程：

式中：ψ為[0，1.5]之間的隨機(jī)數(shù)；p為個體最優(yōu)解；p為種群最優(yōu)解。

個體最優(yōu)解p是指個體經(jīng)歷位置變化后，計(jì)算得到的適應(yīng)度值最優(yōu)位置，種群最優(yōu)解p是指種群中的所有蜜源的適應(yīng)度最優(yōu)位置。蜜源每更新一次，計(jì)算一次適應(yīng)度值，并且通過比較新蜜源的適應(yīng)度值和個體最優(yōu)值、種群最優(yōu)值的適應(yīng)度值更新個體最優(yōu)和種群最優(yōu)位置。

3.3 編碼方式、適應(yīng)度函數(shù)

編碼方式：采用十進(jìn)制編碼方式。

適應(yīng)度函數(shù)：本文優(yōu)化的目標(biāo)是完成所有訂單任務(wù)的出入庫聯(lián)合作業(yè)用時最小，其計(jì)算公式為：

4 實(shí)例仿真

4.1 算例數(shù)據(jù)與算法參數(shù)設(shè)置

本文以某汽車零部件公司倉庫為實(shí)例分析對象，針對倉庫中某一排貨架進(jìn)行實(shí)際數(shù)據(jù)統(tǒng)計(jì)。單排貨架為12 層，60 列，共720 個貨位。按照圖3 的方式對貨架貨位進(jìn)行編碼。貨格寬度和高度尺寸為1.2m×0.8m。堆垛機(jī)水平方向最大速度v=2m/s，加速度a=0.4m/s，堆垛機(jī)垂直方向最大速度v=0.4m/s，加速度a=0.08m/s。

圖3 貨架貨位編號

在本文仿真實(shí)驗(yàn)中，分別對出入庫任務(wù)對為30，60，90 的不同訂單進(jìn)行仿真分析。以30 個出入庫任務(wù)的訂單為例，其編碼方式見表2。設(shè)置混合人工蜂群算法蜂群大小為200，其中采蜜蜂和觀察蜂各為100，蜂群食源數(shù)量即解的個數(shù)為100，最大開采次數(shù)為20；遺傳算法中取種群數(shù)n=100，變異概率Pm=0.05，交叉概率Pc=0.8。GA、ABC、HABC 算法的最大迭代次數(shù)均為6 000。

表2 出入庫任務(wù)對應(yīng)貨位編碼

4.2 算法性能與仿真結(jié)果分析

為了證明所設(shè)計(jì)混合人工蜂群算法（HABC）的有效性，采用GA、ABC和HABC算法進(jìn)行求解分析。為驗(yàn)證所用算法的穩(wěn)定性，將三種算法在30任務(wù)對、60任務(wù)對以及90 任務(wù)對等不同訂單規(guī)模下分別運(yùn)行100 次，利用統(tǒng)計(jì)學(xué)方法求得均值和平均偏差。表3給出了不同訂單規(guī)模下的進(jìn)出庫作業(yè)時間的初始解，所用算法在不同訂單規(guī)模下的進(jìn)出庫作業(yè)時間最優(yōu)解、優(yōu)化效率、計(jì)算精度和計(jì)算效率。圖4給出了三種算法在不同訂單規(guī)模情況下的收斂圖。

表3 三種算法在不同規(guī)模問題下的實(shí)驗(yàn)結(jié)果對比

通過對表3 中三種算法的計(jì)算結(jié)果進(jìn)行對比分析，得到以下結(jié)論：在不同作業(yè)規(guī)模下，HABC相較于ABC算法，雖然計(jì)算偏差較大，但是優(yōu)化效率明顯提高，平均調(diào)度時間最?。幌噍^GA求解的運(yùn)算精度及優(yōu)化效果都有很大程度的提高。表明本文所采用的HABC算法在解決調(diào)度優(yōu)化問題上具有很好的適用性與可行性。

分析圖4中曲線可得，HABC求解得到的結(jié)果雖然收斂速度較慢，但是求解精度高，與GA對比，在迭代過程中，可以不斷的跳出局部搜索，尋找最優(yōu)解。

圖4 不同算法收斂效果對比圖

4.3 三載具AS/RS性能分析

本文研究對象為三載具AS/RS，為了說明其運(yùn)作效率及其在工廠中更高的實(shí)用價值，利用HABC算法對單載具、雙載具AS/RS在。處理同樣訂單規(guī)模時所需時間進(jìn)行計(jì)算，對比分析三載具AS/RS 的性能狀況。表4為三種訂單規(guī)模下的單、雙、三載具AS/RS的進(jìn)出庫時間對比分析表。圖5為不同載具數(shù)AS/RS作業(yè)調(diào)度算法收斂圖。

表4 不同載具數(shù)AS/RS運(yùn)作效率對比表

圖5 三種不同載具作業(yè)調(diào)度算法收斂圖

通過對不同載具數(shù)AS/RS的運(yùn)作效率進(jìn)行對比，實(shí)例結(jié)果表明，三載具AS/RS較雙載具AS/RS在同樣訂單規(guī)模下，其運(yùn)作效率提升了14%左右；三載具AS/RS的運(yùn)作時間遠(yuǎn)小于單載具，效率大大提升，在同樣訂單規(guī)模下，其運(yùn)作效率提升了42%左右。

5 結(jié)語

本文從分組配對、行走模式以及行走順序三個方面對三載具AS/RS的作業(yè)調(diào)度問題進(jìn)行全面分析，建立了出入庫聯(lián)合作業(yè)的優(yōu)化模型，并采用混合人工蜂群算法對模型進(jìn)行求解，利用實(shí)例對算法性能進(jìn)行分析，在30、60、90任務(wù)對的不同訂單規(guī)模下，將三種算法性能進(jìn)行比較分析，結(jié)果表明：混合人工蜂群算法的優(yōu)化效果最佳，優(yōu)化效率分別達(dá)到18.81%、18.27%和15.98%。通過與單、雙載具AS/RS在處理同種規(guī)模訂單下的處理時間進(jìn)行對比，結(jié)果表明，三載具AS/RS性能遠(yuǎn)高于單、雙載具AS/RS，具有更高的實(shí)用價值，可以有效縮短作業(yè)時間，提升運(yùn)作效率，降低企業(yè)成本。