王 婷，王潔慈

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

0 引言

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

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

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

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

1 問(wèn)題描述

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

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

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

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

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

2.1 指令分組

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

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

表1 分組結(jié)果表

2.2 行走模式

對(duì)于已經(jīng)分組后的子行程，每個(gè)子行程對(duì)應(yīng)堆垛機(jī)的一次行走過(guò)程。堆垛機(jī)按照其行走模式完成各個(gè)子行程。堆垛機(jī)“滿載”情況下，必須先存入一個(gè)貨物后才有空載位存放要取的貨物，根據(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)問(wèn)題分析，提出模型假設(shè)：（1）給定撥次內(nèi)，存取貨指令已知，且對(duì)應(yīng)貨位信息已知；（2）入庫(kù)順序一定，不可調(diào)換；出庫(kù)順序可以調(diào)整；（3）堆垛機(jī)為勻加速運(yùn)動(dòng)；（4）貨物裝載時(shí)間忽略不計(jì)。

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

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

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

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

3 混合人工蜂群算法

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

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

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

算法流程如圖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ù)。采蜜蜂對(duì)更新后的蜜源采用貪婪選擇策略進(jìn)行選取。觀察蜂以概率值選擇蜜源，表達(dá)式為：

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

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

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

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

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

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

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

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

4 實(shí)例仿真

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

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

圖3 貨架貨位編號(hào)

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

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

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

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

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

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

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

圖4 不同算法收斂效果對(duì)比圖

4.3 三載具AS/RS性能分析

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

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

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

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

5 結(jié)語(yǔ)

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