旋轉(zhuǎn)貨架揀選作業(yè)優(yōu)化的交叉蟻群算法求解

摘 要：單伺服機(jī)分層水平旋轉(zhuǎn)貨架存取路徑優(yōu)化問題是一個(gè)特殊的TSP問題，為NP完全難題。使用蟻群算法來求解該問題，搜索時(shí)間長、收斂速度慢、易陷于局部最優(yōu)解。為此，根據(jù)遺傳算法中的交叉操作對(duì)該算法進(jìn)行了改進(jìn)， 構(gòu)造交叉蟻群算法，并進(jìn)行計(jì)算機(jī)仿真，結(jié)果表明該算法能較快地找到最優(yōu)解。

關(guān)鍵詞：交叉蟻群算法；蟻群算法；遺傳算法；分層水平旋轉(zhuǎn)貨架；揀選路徑優(yōu)化

Crossover Self-adaptive Ant Colony Algorithm Solving the Order-picking

[J]Optimization of a Multi-carousel Single Server

TIAN Bingli，LIU Changbo，XIE Guixin

(Naval Submarine Academy，Qingdao，266071，China

Abstract：The order-picking optimization for a multi-carousel single server system is a special TSP problem，which is a NP complete problem.The ant system algorithm is applied to resolve this problem in this paper.But，the algorithm has several shortages including long searching time，slow convergence rate and limiting to local optimal solution easily.So，on the bases of the operation of the crossover of the genetic alogorithm，a crossover ant colony algorithm is constructed. Simulation examples show that the optimal result can be obtained quickly using this method.

eywords：crossover ant colony algorithm;ant colony algorithm;genetic algorithm;multi carousel single server;order-picking optimization

1 引 言

旋轉(zhuǎn)貨架是自動(dòng)化立體倉庫的重要組成部分，其高靈活性、快速度的特點(diǎn)，已成為高效自動(dòng)化倉庫的重要存儲(chǔ)形式。對(duì)單伺服機(jī)水平旋轉(zhuǎn)貨架揀選路徑的優(yōu)化將極大地提高自動(dòng)化倉庫的作業(yè)效率，從而提高自動(dòng)化倉庫的整體效益。蟻群算法ACA (Ant Colony Algorithm是由意大利學(xué)者M(jìn).Dorigo，V.Maniez-zo，A.Colorni等人首先提出來的^［1-5］，后來又有許多學(xué)者提出對(duì)它的改進(jìn)方案，例如最大最小蟻群算法Max-MinAntSystem Algorithm(MMASA^［6］，具有新型遺傳特征的蟻群算法^［7］等，但是在求解這種大規(guī)模的組合優(yōu)化問題時(shí)，算法本身所固有的搜索時(shí)間長、收斂速度慢、易陷于局部最優(yōu)解等弊端暴露無遺^［6］。為了克服常規(guī)蟻群算法的缺陷，提高求解速度和質(zhì)量，根據(jù)遺傳算法中的交叉操作對(duì)該算法進(jìn)行了改進(jìn)，提出更為合理的一種算法。仿真試驗(yàn)驗(yàn)證了這種算法能夠快速高效實(shí)現(xiàn)中、大規(guī)模組合優(yōu)化問題的求解。

2 分層水平旋轉(zhuǎn)貨架的揀選路徑優(yōu)化問題的提出

分層水平旋轉(zhuǎn)貨架由多層水平旋轉(zhuǎn)的貨架重疊放置構(gòu)成，各層貨架可以獨(dú)立的正向或反向旋轉(zhuǎn)。在旋轉(zhuǎn)貨架的一端有一臺(tái)升降機(jī)(伺服機(jī)，可以上升或下降到某層的高度，升降機(jī)與旋轉(zhuǎn)貨架的運(yùn)動(dòng)是相互獨(dú)立的。結(jié)構(gòu)如圖1所示：

分層水平旋轉(zhuǎn)貨架是通過順序執(zhí)行一個(gè)個(gè)貨單完成入庫出庫作業(yè)，貨單由管理計(jì)算機(jī)發(fā)送到旋轉(zhuǎn)貨架的控制計(jì)算機(jī)。每個(gè)貨單包含若干條目，每1個(gè)條目對(duì)應(yīng)1條對(duì)旋轉(zhuǎn)貨架某一個(gè)貨箱的存取命令。分層水平旋轉(zhuǎn)貨架的作業(yè)過程為：當(dāng)旋轉(zhuǎn)貨架接收到管理計(jì)算機(jī)發(fā)送過來的貨單后，升降臺(tái)和各層旋轉(zhuǎn)貨架同時(shí)開始運(yùn)動(dòng)，為下一次訪問做準(zhǔn)備。當(dāng)升降臺(tái)和第一條目所對(duì)應(yīng)的層的旋轉(zhuǎn)貨架均已準(zhǔn)備就緒后，升降臺(tái)的操作員對(duì)第一條目所對(duì)應(yīng)的貨箱進(jìn)行存取貨物操作，操作完畢再訪問貨單中的下一條目。依次類推，直到順序執(zhí)行完貨單中的所有條目。最后升降臺(tái)升降到貨臺(tái)的高度，送出貨箱。整個(gè)過程中，升降臺(tái)和各層旋轉(zhuǎn)貨架每時(shí)每刻都在為下一次做準(zhǔn)備工作，直到不再被訪問為止。至此，一個(gè)完整的貨單執(zhí)行過程結(jié)束，旋轉(zhuǎn)貨架等待接收下一個(gè)貨單。