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

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

引言

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

一、問題描述

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

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

1.2 優(yōu)化目標

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

三、實驗分析與結論

為驗證和評估兩種算法的路徑規(guī)劃效果，以某物流中心具體自動化立體倉庫構建實驗模型，其中，貨架規(guī)格為10 行 20 列共 200 個貨位，設定堆垛機載貨臺容量為 2、3、4， 出 庫 任 務 通 過 隨 機 算 法 模 擬 生 成 ， 實 驗 代 碼 采 用python3 構建。對每一批出庫任務，分別應用最近鄰點法和遺傳算法進行堆垛機路徑規(guī)劃實驗。

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

參考文獻：

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

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

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

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

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

作者簡介：

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

基金項目：（省級）安徽普通高校重點實驗室開放基金項目，編號：CS2020-01

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