自動化立體倉庫中堆垛機(jī)路徑規(guī)劃方法研究

摘要：堆垛機(jī)是自動化立體倉庫中的關(guān)鍵設(shè)備，其路徑優(yōu)化效果直接影響到出入庫作業(yè)效率與立體庫運(yùn)行成本。當(dāng)前，多載貨臺堆垛機(jī)和出入庫復(fù)合作業(yè)模式受到廣泛應(yīng)用，這給堆垛機(jī)路徑規(guī)劃帶來巨大優(yōu)化空間。為實(shí)現(xiàn)堆垛機(jī)的總運(yùn)行路徑最短，通過建模并引入最近鄰點(diǎn)法和遺傳算法進(jìn)行研究分析，實(shí)驗(yàn)結(jié)果表明，最近鄰點(diǎn)法適用于小規(guī)模倉儲作業(yè)任務(wù)下的路徑規(guī)劃，當(dāng)任務(wù)較多時，遺傳算法能取得更優(yōu)的效果。

關(guān)鍵詞：堆垛機(jī);自動化;立體倉庫倉儲管理;路徑規(guī)劃

引言

自動化立體倉庫是現(xiàn)代物流的核心裝備，它集機(jī)械、電子、計(jì)算機(jī)、傳感器等多種技術(shù)于一體，廣泛應(yīng)用于機(jī)械制造、配送中心、醫(yī)藥、物流等行業(yè)。自動化立體倉庫是由立體貨架、堆垛機(jī)、出入庫托盤輸送機(jī)、自動控制系統(tǒng)、計(jì)算機(jī)監(jiān)控及管理系統(tǒng)等設(shè)備組成的復(fù)雜的自動化系統(tǒng)，通過系統(tǒng)間的協(xié)調(diào)動作，來完成對指定貨物的自動高效的出入庫作業(yè)。堆垛機(jī)是實(shí)現(xiàn)出入庫操作的關(guān)鍵設(shè)備，立體庫的倉儲作業(yè)效率取決于堆垛機(jī)的運(yùn)行速度與路徑選擇，其中，堆垛機(jī)最大速度一般為確定值，因此，堆垛機(jī)的路徑規(guī)劃成為立體庫管理中的一個主要研究問題，引起大量學(xué)者關(guān)注[1-5]。

一、問題描述

1.1 堆垛機(jī)路徑規(guī)劃問題模型

根據(jù)每次運(yùn)載貨物數(shù)量可將堆垛機(jī)分為單載貨臺型和多載貨臺型，其中單載貨臺型堆垛機(jī)由于每訪問一次貨位均需返回出入庫口，不存在路徑優(yōu)化空間，因此本文研究的模型為多載貨臺堆垛機(jī)，模型的主要變量定義如表 1 所示。

1.2 優(yōu)化目標(biāo)

在堆垛機(jī)需訪問的儲位集合和堆垛機(jī)運(yùn)行速度確定的情況下，使得堆垛機(jī)的總運(yùn)行時間最小，可等效為總運(yùn)行路徑最短，即目標(biāo)函數(shù)為：

二、堆垛機(jī)路徑規(guī)劃方法

堆垛機(jī)路徑規(guī)劃可以看成是一種特殊的（載貨數(shù)量受限）旅行商問題。針對該問題，國內(nèi)外學(xué)者主要使用近似算法或啟發(fā)式算法，其中代表性的有：遺傳算法[3]、蟻群算法[4]、粒子群算法[5]等。

2.1 基于最近鄰點(diǎn)法的路徑規(guī)劃

最近鄰點(diǎn)法是一種構(gòu)造性啟發(fā)式算法，由于最近鄰點(diǎn)法能夠快速產(chǎn)生較優(yōu)解，成為旅行商問題的一種常用方法。

針對堆垛機(jī)路徑優(yōu)化問題，采用最近鄰點(diǎn)法的步驟為：

（1） 初始化堆垛機(jī)起始位置、待揀選的貨位集合 Q、堆垛機(jī)的載貨臺容量 R、揀貨路徑 G;

（2） 從貨位集合 Q 中找到距離堆垛機(jī)最近的貨位 q，將 q 從 Q 中移出，作為路徑的首節(jié)點(diǎn)，設(shè)置載貨數(shù)量為 1;

（3） 從貨位集合 Q 中找到距離路徑 G 末節(jié)最近的貨位 q，將 q 從 Q 中移出，添加到路徑 G 末尾，載貨數(shù)量加 1，當(dāng)載貨數(shù)量等于堆垛機(jī)容量 R 時，路徑重新回到起始位置，載貨數(shù)量清零;

（4） 重復(fù)步驟（3），直到貨位集合 Q 中的剩余數(shù)量為 0;

（5） 最后，輸出建好路徑表 G。

其中，兩貨位之間的距離使用曼哈頓距離公式計(jì)算：

2.2 基于遺傳算法的路徑規(guī)劃

遺傳算法是針對復(fù)雜問題的一種搜索算法，其將問題的嘗試解進(jìn)行編碼，形成“染色體”，利用生物的遺傳、交叉與變異等特性形成新的嘗試解，通過多次迭代，獲得穩(wěn)定結(jié)果即為問題的近似最優(yōu)解。

運(yùn)用遺傳算法進(jìn)行堆垛機(jī)路徑規(guī)劃首先需要對路徑進(jìn)行編碼，將待出庫的貨位號用二進(jìn)制的基因值表示，一組排序的基因?qū)?yīng)一條路徑表。算法步驟為：

（1）初始化種群，即生成設(shè)定數(shù)量的染色體;

（2）交叉操作，隨機(jī)抽取兩個染色體，隨機(jī)截取部分基因進(jìn)行交叉，形成新的染色體;

（3）變異操作，基于路徑排序問題特性，對染色體的變異操作是采取基因隨機(jī)交換位置實(shí)現(xiàn)，從而形成新的染色染;

（4）對染色體進(jìn)行解碼并根據(jù)目標(biāo)函數(shù)進(jìn)行計(jì)算評估，保留優(yōu)秀解，淘汰劣勢解;

（5）對步驟 2-4 進(jìn)行迭代，直到滿足迭代次數(shù)，對最優(yōu)解進(jìn)行解碼輸出。

三、實(shí)驗(yàn)分析與結(jié)論

為驗(yàn)證和評估兩種算法的路徑規(guī)劃效果，以某物流中心具體自動化立體倉庫構(gòu)建實(shí)驗(yàn)?zāi)Ｐ停渲?，貨架?guī)格為10 行 20 列共 200 個貨位，設(shè)定堆垛機(jī)載貨臺容量為 2、3、4， 出 庫 任 務(wù) 通 過 隨 機(jī) 算 法 模 擬 生 成 ， 實(shí) 驗(yàn) 代 碼 采 用python3 構(gòu)建。對每一批出庫任務(wù)，分別應(yīng)用最近鄰點(diǎn)法和遺傳算法進(jìn)行堆垛機(jī)路徑規(guī)劃實(shí)驗(yàn)。

實(shí)驗(yàn)結(jié)果表明：最近鄰點(diǎn)法是一種基于局部尋優(yōu)的規(guī)劃方法，在堆垛機(jī)路徑規(guī)劃問題中往往不能取得全局最優(yōu)解，其優(yōu)點(diǎn)是算法效率高，當(dāng)任務(wù)數(shù)較少時能取得近似最優(yōu)解，當(dāng)任務(wù)數(shù)較多或載貨臺容量越大時，遺傳算法越能取得更優(yōu)秀的路徑規(guī)劃效果。

參考文獻(xiàn)：

[1]楊瑋， 劉江， 岳婷，等. 多載具自動化立體倉庫貨位分配與作業(yè)調(diào)度集成優(yōu)化[J]. 計(jì)算機(jī)集成制造系統(tǒng)， 2019，25（01）：251-259.

[2]蔡安江， 史啟程. 自動化立體倉庫調(diào)度模型分析及優(yōu)化[J]. 機(jī)械設(shè)計(jì)與制造， 2018， 334（12）：53-56.

[3]曾強(qiáng)，張澤斌，楊龍飛.有容量限制的自動化立體倉庫堆垛機(jī)路徑規(guī)劃優(yōu)化方法[J].機(jī)械設(shè)計(jì)與制造，2015（01）：172-176.

[4]楊玲，關(guān)志偉.自動化立體倉庫揀選路徑優(yōu)化問題研究[J].中國制造業(yè)信息化，2011，40（07）：47-50.

[5]楊瑋，李程，傅衛(wèi)平等.自動化立體倉庫固定貨架揀選路徑問題研究[J].上海理工大學(xué)學(xué)報，2015，37（01）：84-88.

作者簡介：

徐斌（1984—），男，漢族安徽潛山人，安徽工業(yè)大學(xué)工學(xué)博士，講師，從事智能制造、工業(yè)工程與信息化、物流工程等研究。

基金項(xiàng)目：（省級）安徽普通高校重點(diǎn)實(shí)驗(yàn)室開放基金項(xiàng)目，編號：CS2020-01

安徽工業(yè)大學(xué)管理科學(xué)與工程學(xué)院? 徐斌