基于遺傳模擬退火算法的堆垛機(jī)路徑優(yōu)化

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

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

0 引言

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

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

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

1 問題描述

1.1 自動化立體倉庫

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

圖1 自動化立體庫平面圖

1.2 模型假設(shè)

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

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

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

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

（4）裝卸貨物時間忽略不計；

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

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

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

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

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

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

為了便于模型描述，各種變量的符號說明見表1。

表1 變量說明

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

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

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

2.2 約束條件

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

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

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

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

圖3 SAGA流程圖

3.1 編碼

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

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

3.2 種群初始化

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

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

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

3.4 選擇

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

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

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

3.5 交叉

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

圖4 交叉算子

3.6 變異

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

圖5 變異算子

3.7 模擬退火

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

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

Step2：計算經(jīng)過遺傳操作得到的父代個體適應(yīng)度值Fit和經(jīng)過模擬退火后的子代個體適應(yīng)度fit值；

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

3.8 終止條件

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

4 案例仿真分析

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

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

表2 自動化立體倉庫參數(shù)

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

表5 貨物坐標(biāo)

4.2 仿真結(jié)果分析

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

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

表4 SAGA參數(shù)

由表6可知，采用遺傳模擬退火算法的貨物揀選完成時間最短，其最優(yōu)作業(yè)時間為528.06s，相對于隨機(jī)算法的最優(yōu)作業(yè)時間提升了23.09%，相較于遺傳算法增加了9.7%。利用遺傳模擬退火算法得到的一條堆垛機(jī)最優(yōu)路徑用貨物編號可表示為：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表示出庫點(diǎn)。

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

圖6 GA迭代過程

圖7 SAGA迭代過程

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

5 結(jié)語

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