楊姣，楊旭東，李露莎，劉旭

（1.貴州大學(xué)機(jī)械工程學(xué)院，貴州 貴陽(yáng) 550025；2.貴州省煙草公司黔南州公司，貴州 黔南 558000）

0 引言

自動(dòng)化立體倉(cāng)庫(kù)/自動(dòng)倉(cāng)儲(chǔ)系統(tǒng)（AS/RS）具有高效自動(dòng)化、強(qiáng)大出入庫(kù)能力和較高空間利用率等特點(diǎn)，越來(lái)越被廣泛地應(yīng)用到煙草、醫(yī)藥、電商物流、食品等各個(gè)行業(yè)中，成為現(xiàn)代物流不可或缺的重要環(huán)節(jié)。特別是在電商物流行業(yè)，如何在最短的時(shí)間內(nèi)快速而準(zhǔn)確的將大批量訂單在立體庫(kù)中進(jìn)行存儲(chǔ)和取出成為進(jìn)一步研究的內(nèi)容。通常，AS/RS主要由貨架、運(yùn)輸系統(tǒng)、堆垛機(jī)、計(jì)算機(jī)、自動(dòng)控制系統(tǒng)等組成，其中堆垛機(jī)作為AS/RS中搬運(yùn)貨物的運(yùn)輸設(shè)備，當(dāng)相同訂單出入庫(kù)順序不同時(shí)，其路徑也不同，完成任務(wù)的時(shí)間也不同，所以堆垛機(jī)的運(yùn)行效率直接決定AS/RS的工作效益。

衛(wèi)三軍，等利用遺傳算法和模擬退火算法相結(jié)合的優(yōu)化方法對(duì)堆垛機(jī)的不同運(yùn)行模式進(jìn)行求解分析；唐磊，等在遺傳算法的基礎(chǔ)上提出用貪心算法將已完成出庫(kù)的庫(kù)位作為新的入庫(kù)位對(duì)堆垛機(jī)路徑進(jìn)行尋優(yōu)；卞和營(yíng)，等引入一種貪心交叉算子和高斯變異算子的改進(jìn)遺傳方法對(duì)堆垛機(jī)的出入庫(kù)作業(yè)方式路徑進(jìn)行了優(yōu)化；華紅艷，等將堆垛機(jī)路徑抽象成旅行商問(wèn)題，利用蟻群算法對(duì)堆垛機(jī)路徑進(jìn)行了優(yōu)化求解；張新陽(yáng)，等利用改進(jìn)遺傳算法對(duì)貨物分配和堆垛機(jī)路徑進(jìn)行了優(yōu)化。

以上研究一方面是將堆垛機(jī)看成無(wú)限容量，忽略了當(dāng)貨物重量達(dá)到堆垛機(jī)重量限制時(shí)返回出/入庫(kù)點(diǎn)，再?gòu)某?入庫(kù)點(diǎn)到下一貨物點(diǎn)所產(chǎn)生的路徑；另一方面是每取一次貨物就返回一次出/入庫(kù)點(diǎn)，兩種方式都不適用于大批量的揀選作業(yè)。所以本文以堆垛機(jī)裝載件數(shù)為限制條件，建立以堆垛機(jī)出庫(kù)時(shí)間最短為目標(biāo)函數(shù)的調(diào)度模型，并設(shè)計(jì)提出了一種模擬退火算法（SA）與傳統(tǒng)遺傳算法（GA）相結(jié)合的遺傳模擬退火算法（SAGA）對(duì)模型進(jìn)行求解，通過(guò)仿真進(jìn)一步驗(yàn)證了該方法的有效性和實(shí)用性。

1 問(wèn)題描述

1.1 自動(dòng)化立體倉(cāng)庫(kù)

本文所研究的自動(dòng)化立體倉(cāng)庫(kù)平面圖如圖1所示，出/入庫(kù)臺(tái)分別在貨架兩側(cè)，貨架采取單元貨架格式分布在每一巷道的兩側(cè)，每一排貨架都含有不同種類的貨物，當(dāng)巷道中的堆垛機(jī)接收到貨物出入庫(kù)任務(wù)后，從貨架上取出貨物送到出庫(kù)臺(tái)上或?qū)⑷霂?kù)臺(tái)上的貨物運(yùn)送到貨位上，進(jìn)行貨物的存取任務(wù)。

圖1 自動(dòng)化立體庫(kù)平面圖

1.2 模型假設(shè)

為了更好的對(duì)模型進(jìn)行數(shù)學(xué)建模，做出如下假設(shè)：

（1）每排貨架上的貨位大小相同，且單個(gè)貨位只能存放一件貨物；

（2）出/入庫(kù)臺(tái)分別在貨架兩側(cè)；

（3）堆垛機(jī)雙向勻速運(yùn)行，不考慮加減速過(guò)程；

（4）裝卸貨物時(shí)間忽略不計(jì)；

（5）貨架位置用二維坐標(biāo)表示，貨物中心位于該貨位的幾何中心。

1.3 堆垛機(jī)作業(yè)模式

在某次出庫(kù)任務(wù)中，當(dāng)堆垛機(jī)接受到n個(gè)揀選任務(wù)時(shí)，堆垛機(jī)從出庫(kù)臺(tái)出發(fā)依次按照調(diào)度順序運(yùn)行到指定揀選貨位，經(jīng)過(guò)一系列貨位點(diǎn)后，當(dāng)貨物總件數(shù)達(dá)到堆垛機(jī)托盤承載件數(shù)上限時(shí)，堆垛機(jī)需返回出庫(kù)臺(tái)卸載后再進(jìn)行下一輪揀選任務(wù)，直至全部訂單揀選完成，如圖2所示。其路徑就可以抽象成一個(gè)組合優(yōu)化問(wèn)題中的TSP問(wèn)題，如果n個(gè)揀選任務(wù)需要往返m次，那么就是m個(gè)TSP問(wèn)題的復(fù)合，屬于NP-hard問(wèn)題。所以本文的目的是合理安排堆垛機(jī)的揀選路徑，實(shí)現(xiàn)目標(biāo)函數(shù)即出庫(kù)時(shí)間的最小化。

圖2 堆垛機(jī)揀選作業(yè)示意圖

2 建立數(shù)學(xué)模型

2.1 目標(biāo)函數(shù)

為了便于模型描述，各種變量的符號(hào)說(shuō)明見表1。

表1 變量說(shuō)明

基于以上設(shè)定，第i個(gè)揀選貨物信息可表示為數(shù)組（X，Y），X和Y表示該貨位所在的列數(shù)和層數(shù)坐標(biāo)。當(dāng)有n個(gè)揀選任務(wù)，需往返m次時(shí)，目標(biāo)函數(shù)為：

式（1）表示總的出庫(kù)時(shí)間最小，其中t表示堆垛機(jī)完成一次揀選任務(wù)所用的時(shí)間，包括堆垛機(jī)從出庫(kù)點(diǎn)移動(dòng)到折返點(diǎn)所用時(shí)間和從折返點(diǎn)返回到出庫(kù)臺(tái)時(shí)間，具體表達(dá)式如下：

其中（X，Y）是當(dāng)貨物件數(shù)達(dá)到堆垛機(jī)托盤件數(shù)時(shí)，需折返回出庫(kù)點(diǎn)O（X,Y）的貨位點(diǎn)，（X，Y）為最終揀選的貨位點(diǎn)。

2.2 約束條件

式（3）表示每輪揀選貨物的件數(shù)不能大于堆垛機(jī)托盤件數(shù)，最后一輪可能會(huì)存在不滿載的情況。式（4）表示m的取值范圍。式（5）為整數(shù)約束。

3 模擬退火遺傳算法的求解

遺傳算法（GA）是一種模仿生物進(jìn)化過(guò)程的算法，具有全局最優(yōu)特性和局部搜索能力差等特點(diǎn)。模擬退火算法（SA）的出發(fā)點(diǎn)是基于物理退火過(guò)程，包含加溫、等溫和冷卻過(guò)程，其中等溫過(guò)程所采用的Metropolis準(zhǔn)則，可以以一定的概率接受惡化解，從而跳離局部最優(yōu)的陷阱。

所以本文采用遺傳模擬退火算法（SAGA），先由遺傳算法進(jìn)行全局搜索，再由模擬退火算法進(jìn)行局部搜索。取長(zhǎng)補(bǔ)短，可以有效的克服傳統(tǒng)遺傳算法的早熟現(xiàn)象，并且使局部搜索能力加強(qiáng)且優(yōu)化速度加快，其算法流程如圖3所示。

圖3 SAGA流程圖

3.1 編碼

采用整數(shù)排列編碼方法，對(duì)于n個(gè)揀選任務(wù)，可以用1～n的整數(shù)來(lái)表示待揀選貨物的貨位點(diǎn)，不同的排列順序就是不同的行駛路徑。每個(gè)基因上包含一個(gè)一行兩列的數(shù)組，分別表示該貨物點(diǎn)所在列和層的坐標(biāo)位置，即在第X列、第Y層。如對(duì)10個(gè)貨位點(diǎn)進(jìn)行染色體編碼：

上述編碼代表堆垛機(jī)從出入庫(kù)出發(fā)，依次經(jīng)過(guò)1→4→6→7→9→10→2→5→3→8貨 位 點(diǎn) 進(jìn) 行 揀選。如當(dāng)堆垛機(jī)承載件數(shù)Q=5時(shí)，堆垛機(jī)需兩次往返才能完成全部出庫(kù)任務(wù)。首先第一輪揀選：從出入庫(kù)點(diǎn)到貨位點(diǎn)1取貨，再依次到貨位點(diǎn)4→6→7→9取貨，最后在貨位點(diǎn)9取貨后達(dá)到堆垛機(jī)承載件數(shù)，從而返回出入庫(kù)點(diǎn)卸貨；第二輪揀選：從出入庫(kù)點(diǎn)到貨位點(diǎn)10取貨，最終到貨位點(diǎn)8取貨后返回出入庫(kù)點(diǎn)卸貨。貨物偶爾會(huì)在最后一輪揀選時(shí)有不滿載的情況存在。

3.2 種群初始化

在進(jìn)行下面一系列的遺傳操作之前，在完成染色體編碼后，需隨機(jī)產(chǎn)生一個(gè)種群規(guī)模為N的表示起始搜索點(diǎn)數(shù)據(jù)的初始種群。

3.3 適應(yīng)度函數(shù)

遺傳算法中的適應(yīng)度函數(shù)一般是由目標(biāo)函數(shù)變換得到，求目標(biāo)函數(shù)的最小值時(shí)，可將函數(shù)值的倒數(shù)作為個(gè)體的適應(yīng)度值，函數(shù)值越小的個(gè)體，適應(yīng)度值越大，個(gè)體越優(yōu)。所以個(gè)體適應(yīng)度函數(shù)為：

3.4 選擇

根據(jù)每個(gè)染色體的適應(yīng)值以一定的概率選擇個(gè)體到新群體中，選擇方法有輪盤賭選擇、隨機(jī)遍歷抽樣、局部選擇、截?cái)噙x擇和錦標(biāo)賽選擇等。個(gè)體i采用輪盤賭方法被選中的概率為：

Fit：個(gè)體i的適應(yīng)度函數(shù)值；

M：種群個(gè)體數(shù)目。

3.5 交叉

交叉運(yùn)算，主要是指對(duì)兩個(gè)相互配對(duì)的父代個(gè)體按照某種方式相互交換部分基因，從而形成兩個(gè)新的子代個(gè)體。兩點(diǎn)交叉方式如圖4所示（假定有10個(gè)待揀選的貨位點(diǎn)）。

圖4 交叉算子

3.6 變異

遺傳算法中的變異運(yùn)算是指將個(gè)體中的某些基因用該個(gè)體生的其他等位基因來(lái)替換，從而形成一個(gè)新的個(gè)體。通過(guò)變異運(yùn)算，可以維持種群的多樣性和防止過(guò)早收斂而出現(xiàn)早熟現(xiàn)象。每組重復(fù)圖5所示的換位過(guò)程。

圖5 變異算子

3.7 模擬退火

對(duì)原始種群進(jìn)行選擇、交叉及變異等操作之后會(huì)產(chǎn)生一個(gè)新的種群，將此種群作為模擬退火算法的初始種群，再對(duì)新的種群中各個(gè)個(gè)體進(jìn)行模擬退火操作后得到最新一代的種群群體，具體步驟如下：

Step1：初始化控制參數(shù)；

Step2：計(jì)算經(jīng)過(guò)遺傳操作得到的父代個(gè)體適應(yīng)度值Fit和經(jīng)過(guò)模擬退火后的子代個(gè)體適應(yīng)度f(wàn)it值；

Step4：若滿足鏈長(zhǎng)L，輸出當(dāng)前解進(jìn)入下一代；否則返回Step2，直到找到可接受的新種群。

3.8 終止條件

若當(dāng)前迭代次數(shù)為G（最終迭代次數(shù)）時(shí)，停止迭代輸出當(dāng)前最優(yōu)解；否則調(diào)整控制溫度T=rand×T（其中rand為降溫速率），返回步驟3、4開始新一輪的遺傳操作。

4 案例仿真分析

4.1 仿真參數(shù)設(shè)定

某自動(dòng)化立體倉(cāng)庫(kù)的貨架為9層23列形式，從中隨機(jī)選取10種不同待出庫(kù)的貨物進(jìn)行模擬仿真優(yōu)化，所得數(shù)據(jù)和參數(shù)設(shè)置見表2-表5。

表2 自動(dòng)化立體倉(cāng)庫(kù)參數(shù)

表3 貨物出庫(kù)件數(shù)

表5 貨物坐標(biāo)

4.2 仿真結(jié)果分析

對(duì)遺傳算法和上述遺傳模擬退火算法在MATLAB中分別進(jìn)行20次的仿真實(shí)驗(yàn)，得到揀選時(shí)間對(duì)比和任務(wù)耗時(shí)的提升效果見表6。

表6 仿真結(jié)果對(duì)比

表4 SAGA參數(shù)

由表6可知，采用遺傳模擬退火算法的貨物揀選完成時(shí)間最短，其最優(yōu)作業(yè)時(shí)間為528.06s，相對(duì)于隨機(jī)算法的最優(yōu)作業(yè)時(shí)間提升了23.09%，相較于遺傳算法增加了9.7%。利用遺傳模擬退火算法得到的一條堆垛機(jī)最優(yōu)路徑用貨物編號(hào)可表示為：0→35→41→20→34→36→0→27→16→21→30→17→0→32→42→39→40→33→0→22→38→37→31→23→0→14→15→19→18→28→0→12→11→29→13→24→0→10→9→8→4→2→0→6→3→1→5→7→0→25→26→0。其中0表示出庫(kù)點(diǎn)。

仿真結(jié)果中遺傳算法和遺傳模擬退火算法的全局最優(yōu)解進(jìn)化過(guò)程曲線如圖6、圖7所示。

圖6 GA迭代過(guò)程

圖7 SAGA迭代過(guò)程

由圖6、圖7可知，遺傳算法迭代到167次后就得到了最優(yōu)解，遺傳模擬退火算法只需迭代到126次后就得到了全局最優(yōu)解，說(shuō)明改進(jìn)后的遺傳模擬退火算法能夠更快的收斂和找到全局最優(yōu)解，具有較強(qiáng)的全局搜索能力。

5 結(jié)語(yǔ)

針對(duì)自動(dòng)化立體倉(cāng)庫(kù)的堆垛機(jī)出庫(kù)路徑優(yōu)化問(wèn)題，加入堆垛機(jī)最大裝載件數(shù)這一約束條件，建立了以出庫(kù)時(shí)間最短為目標(biāo)的調(diào)度模型，采用遺傳模擬退火算法對(duì)模型進(jìn)行了求解。仿真結(jié)果表明，遺傳模擬退火算法在一定程度上提高了AS/RS中貨物的出庫(kù)效率，具有一定的應(yīng)用價(jià)值。