論匈牙利算法在倉儲指派作業中的應用

朱傳棟

(北京物資學院 北京 101149)

一、引言

在社會經營管理中，經常將人、物和事進行適當調配，以充分發揮人盡其才、物盡其用和事得其人的作用，提高管理效率。倉儲作業中也是如此，對于一批入出庫任務，如何指派入出庫作業效率最高，能夠使得總費用最少，這是一項典型的分配問題。以U形多道式倉儲系統為例，其模型的特殊性，一般都采用特殊的解法——匈亞利算法，其也是目前指派問題求解方法中應用最廣泛的解法。

二、匈牙利算法解決指派問題的基本思想

圖1 匈牙利算法流程圖

算法原理如下：C=(Cij)n·n為研究問題的目標系數矩陣，且滿足Cij≥0，首先需對每行/列元素減去該行/列最小元素，得到n個具有不同行/列的獨立0元素Cij，若獨立0元素數小于矩陣階數，進行覆蓋操作，直到含有n個獨立0元素，該方法得到的矩陣具有和原矩陣相同的最優解。其中，算法流程如圖1所示。

三、貨位分配優化方案

其中，物資存儲采取就近貨位分配和隨機分配相結合的ABC貨位分類方法，即在物資存儲工作中，都存在“少數關鍵和多數一般”這種規律，少數重要可對系統起到決定性作用，多數一般甚至不大重要但又不可或缺。如果能夠將重點工作用于解決這些少數但關鍵重要的事物上，對多數但一般重要事物進行一般管理，比起不分輕重同等對待，顯然前者效果要好得多。ABC貨位分類法，就是基于這種思想，并進行與之相應的管理。這里以入出庫頻率為主要指標，A類作業頻率較高，較靠近入出庫口；B類作業頻率中等，距離一般；C類作業頻率較低，距離較遠。

所以，根據存儲物資種類、特性及該系統運行特點，為集中巷道作業，提高堆垛機運行效率，需要對貨架區進行貨位分配優化。這里，不同于以往研究，即一巷道貨架放部分A類物資和部分B、C類物資，將剩余A、B和C類物資安排在另一條巷道兩排貨架上，具體如下圖所示。

圖2 ABC貨位分區安排示意圖

四、匈牙利算法在具體指派中的應用

以某U型多道式倉儲系統為研究對象，該系統貨架共4排、30列(雙貨位貨格)、12層，配有一臺轉彎型堆垛機，可管理兩條巷道、四排貨架。具體數據獲取方面，貨格規格為長1980mm*高925mm*寬1200mm。堆垛機直道階段水平方向速度為vXmax=1.67m/s，水平方向加速度為aX=±0.3m/s2；垂直方向速度為vYmax=0.5m/s，垂直方向加速度為aY=±0.3m/s2。彎道階段，為保證堆垛機安全，其水平方向速度較低且載貨臺降至較低位置，速度v彎=0.5m/s。ta、tb分別表示單一命令和復合命令作業巡回中包括定位、貨位探測和貨叉作業巡回等固定不變的時間總和，其中，ta=4s，tb=7.9s。進行換巷道作業時，為便于優化，不考慮堆垛機本身體積、直軌與彎軌間切換和轉彎前載貨臺降至較低位置等因素對實驗結果的影響。

表1為系統一初始任務單，作業位置(x,y,z)中x、y、z分別表示排、列、層。

表1 初始任務單數據

對任務單數據進行分析，平衡其入、出庫貨位數量，使入出庫貨位數量能夠配對一致，其入出庫貨位之間運行時間如下表2所示。

表2 系統一組各入出庫貨位之間堆垛機運行時間(s)

由于復合作業作業效率較高，因此其倉儲作業以復合作業為主，并基于ABC貨位分配優化、集中巷道方式為前提進行的。這里運用Matlab編程，可得表3最優指派方案。

表3 最優指派方案

為提高系統運行效率，我們以集中巷道作業為前提，對上述最優指派方案進行排序，并假設以跨巷道作業組合中入庫貨位巷道為堆垛機所在巷道，對每一巷道進行入出庫作業組合隨機排序，并用跨巷道作業組合銜接，其中，系統一任務序列如下：4-0，7-6，1-2，9-3，5-8。優化前總作業完成時間432.58s，優化后總作業完成時間為223.13s,不考慮其他影響因素，系統優化前后效率能夠提升45%以上。

五、結論

通過以上分析，可以得出以下結論：第一，合理進行貨位優化能夠提高系統運行效率；第二，復合作業較單一作業效率更高，利用匈牙利算法求解U形多道式倉儲系統作業指派問題具有良好的效果。