混合整數(shù)規(guī)劃與匈牙利法的自動化立體倉庫貨位優(yōu)化研究

宋紫浩 張水旺 鮑薔

摘 要：針對自動化立體倉庫貨位優(yōu)化問題，在常規(guī)存儲策略的基礎(chǔ)上，依據(jù)周轉(zhuǎn)效率最高原則建立了合適的貨位優(yōu)化數(shù)學模型，同時將0～1整數(shù)規(guī)劃原理引入模型求解過程，據(jù)此建立整數(shù)規(guī)劃模型，并利用實例數(shù)據(jù)進行計算。結(jié)果表明，在模型求解過程中引入0～1整數(shù)規(guī)劃思想，再利用匈牙利法求解使得原模型求解大大簡化，結(jié)果也是全局最優(yōu)，是解決貨位優(yōu)化問題的優(yōu)良方法。

關(guān)鍵詞：自動化立體倉庫;貨位優(yōu)化;整數(shù)規(guī)劃;匈牙利法

中圖分類號：F253.4;F224文獻標識碼：A文章編號：1003-5168（2020）28-0051-04

Research on Space Optimization in Automated Warehouse Based

on Integer Programming and Hungarian Method

SONG Zihao ZHANG Shuiwang BAO Qiang

（School of Management Science and Engineering， Anhui University of Technology，Maanshan Anhui 243032）

Abstract： Aiming at the problem of space optimization in automatic three-dimensional warehouse， on the basis of conventional storage strategy and according to the principle of maximum turnover efficiency， an appropriate mathematical model of space optimization was established， and the principle of 0～1 integer programming was introduced into the process of model solving. Based on this， the integer programming model was established， and the calculation was carried out with the example data. The results show that the introduction of 0～1 integer programming in the process of solving the model and then using Hungarian method to solve the original model greatly simplifies the solution of the original model， and the result is also global optimal， which is an excellent method to solve the problem of freight location optimization.

Keywords： automated warehouse;space optimization;integer programming;Hungarian Method

為了提高倉庫的存儲量和作業(yè)效率，自動化立體倉庫越來越普遍，其貨物存儲策略問題也逐漸成為企業(yè)家和學者關(guān)注的熱點問題。一般來說，常規(guī)的存儲策略主要包括隨機、分類、分類隨機、定位和共享存儲五種。目前，大多自動化立體倉庫采取的是隨機存儲策略，但當貨品種類日益增多以及訂單量增加時，會造成儲位混亂，大大提高存儲管理成本。因此，研究自動化立體倉庫貨位優(yōu)化問題，以提高倉庫的出入庫效率、降低存儲成本尤為必要。

國內(nèi)外學者紛紛對貨位優(yōu)化問題進行了大量的深入研究。Elisa FM 等人通過按順序索引分析所需的空間和總順序采摘距離的帕累托最優(yōu)計算，提出了一種基于類的存儲過程和存儲位置分配方法[1];侯忠和鄭國華針對汽車配件庫貨物的特點，建立了基于貨位優(yōu)化的多目標規(guī)劃模型[2]，但只對倉庫單排貨架上的貨物進行了貨位優(yōu)化;李永偉等人將貨位優(yōu)化問題分為貨位選擇層和貨位順序?qū)?，建立了以工作人員行走總路程最小為目標的普通立體倉庫貨位優(yōu)化模型[3];高楠等人以入庫效率、貨架穩(wěn)定和能耗為目標構(gòu)建了多目標貨位優(yōu)化模型，并采用遺傳算法對問題進行了求解[4];徐偉華等人同樣采用遺傳算法，求解了自動化立體倉庫貨位分配優(yōu)化問題[5];Shuiwang Zhang等人構(gòu)建了以貨物穩(wěn)定性、出入庫能耗和貨物關(guān)聯(lián)規(guī)則的貨位分配模型，并采用人工魚群算法對算例進行了求解，驗證了文中所提模型和求解算法的可行性和優(yōu)越性[6];郭娟等人則采用粒子群算法求解了以貨架中心最低（貨架穩(wěn)定性）、揀選路徑最短和出入庫效率最大為目標的立體倉庫貨位優(yōu)化多目標模型[7]。

現(xiàn)有研究中，多數(shù)在貨位分配模型求解階段采取算法求解，本文則將貨位分配的問題看成是整數(shù)線性規(guī)劃問題中的指派問題，建立貨位優(yōu)化模型后，將其轉(zhuǎn)化為指派問題求解，從而得到最優(yōu)解決方案。

1 問題描述

以自動化立體倉庫的高位貨架為研究對象。設(shè)倉儲區(qū)共有[n]個高位貨架，且每個高位貨架有[i]列[j]層。選定出入口為零點，即最靠近倉庫口的貨架為第一個，最靠近傳送帶的第一豎排貨位為第一列，最靠近地面的第一橫排貨位為第一層。以出入口為原點，建立三維坐標系，其中[X]軸方向為傳送帶方向，垂直于貨架，速度為[Vx];[Y]軸方向為平行貨架方向，速度為[Vy];[Z]軸方向為豎直向上方向，速度為[Vz]。存儲區(qū)平面圖如圖1所示。

圖1 存儲區(qū)俯視圖

此類自動化立體倉庫多為標準化包裝，在出入庫作業(yè)時，并不需要考慮貨品外觀因素。此外，貨品出入存儲區(qū)是其出入庫作業(yè)最重要的組成部分。因此，評價倉庫效益最重要的指標便是出入庫效率。

2 模型構(gòu)建

2.1 基本假設(shè)

①貨位貨品相適應(yīng)，同一貨位貨品無混放;②使用一種通用托盤;③堆垛機和傳送帶在其運動方向上均是勻速運動，倉儲區(qū)作業(yè)均采用同種堆垛機，面對貨架正面一側(cè)作業(yè);④單出入庫口模式，出入庫口在同一側(cè);⑤貨位貨格形狀為正方體，即長、寬、高相同，且相鄰貨位緊挨。

2.2 數(shù)學模型

通常用單位時間內(nèi)流轉(zhuǎn)的某類貨品的數(shù)量來表示貨物的周轉(zhuǎn)率[P]，計算公式為：

由于堆垛機在水平和豎直方向上是勻速運動，因此它將貨品入庫送至指定貨位和指定貨位取貨的耗時一定。如在某一貨位[（i，j）]上的周轉(zhuǎn)率為[Pij]，出入庫作業(yè)總時間為[T]，則該貨位單位時間內(nèi)出入庫作業(yè)總耗時為：

用[Tijk]表示位于貨位[（i，j，k）]處的貨品被搬運到出口耗費的時間（單位：s），經(jīng)分析，可得：

其中，[h]表示相鄰兩個貨位直接的平均距離，m;[f]表示每兩個相鄰貨架之間平均距離，m。

只要知道所有貨位上單位時間內(nèi)的周轉(zhuǎn)率及每個貨位對應(yīng)的單次出入庫作業(yè)時間，就能知道單位時間內(nèi)倉儲區(qū)堆垛機所需要進行出入庫作業(yè)的總耗時，如式（4）所示：

其中，[Pijk]表示位于貨位[（i，j，k）]處貨品的周轉(zhuǎn)率，件（臺）/月。

將式（3）代入式（4）中，有

本模型約束條件如下：

最終確定貨位優(yōu)化模型如下：

通過分析，由于單個貨品只能放入一個貨位，且不同貨品不能共用一個貨位，此類思想類似于0～1整數(shù)規(guī)劃問題中的指派問題，因此可以引入指派問題的思想和方法簡化求解過程。得出指派模型為：

其中：

3 案例研究

3.1 選定對象

本文隨機截取了某倉庫休閑食品區(qū)的存儲貨架8列5層共計40個貨位進行研究。給選定的貨品進行編碼：1號貨品用[u1]表示，2號貨品用[u2]表示，以此類推，[v]號貨品用[uv]表示。

假如只研究單一貨架時，底層距離出入口更近，因此頻次更大貨品更應(yīng)該靠下;假如研究多個貨架時，就應(yīng)該將周轉(zhuǎn)率高的貨品放置在靠近出入庫口的貨架上面。據(jù)此將所選的貨位分為A、B、C三個區(qū)域，分別用于存儲周轉(zhuǎn)率高、中和低的貨品。選取的貨位已存儲有貨品，其貨位固定不變。貨位示意圖如圖2所示。

在此基礎(chǔ)上，根據(jù)選取的8類貨品周轉(zhuǎn)率的差異，將其分類a、b、c三類，分別對應(yīng)A、B、C存儲區(qū)，貨品分類表如表1所示。

3.2 案例計算

利用公式（2）可以求得每個貨品指派到每個貨位上的[f]值，即為指派模型的系數(shù)，可以得出指派模型的系數(shù)矩陣，求得指派方案。部分[f]值如表2所示。

首先得到a類貨品分配到A區(qū)每個貨位的系數(shù)值，得到可行分配方案的系數(shù)矩陣為：

既而，通過匈牙利法計算得到最終解矩陣為：

同理，得到b類貨品分配到B區(qū)每個貨位的系數(shù)值，可行分配方案的系數(shù)矩陣為：

計算得到解矩陣為：

同樣，得到c類貨品分配到C區(qū)每個貨位的系數(shù)值，可以得到系數(shù)矩陣為：

計算得到解矩陣為：

綜上，最終得到貨位分配方案如圖3所示。其中，貨物和貨位的對應(yīng)關(guān)系如表3所示。

3.3 結(jié)果分析

實例計算完成后，可得到貨位分配方案如表3所示，既而可求出該策略下的目標函數(shù)值為645。

依據(jù)原隨機存儲策略，貨品一般依照就近原則先入先放，其存儲策略如表4所示，該策略下的目標函數(shù)值為739.6?？梢?，通過本文的優(yōu)化方法，效率可以提高14.67%。

通過上述分析可知，本文的優(yōu)化方法能較大幅度地提升貨品出入庫效率。同時，在有限貨位的情景下，本文的貨位分配方法相較于以往隨機分配方法更易于理解和操作，兼顧了入庫和出庫的效率。

4 結(jié)語

通過對自動化立體倉庫性質(zhì)和業(yè)務(wù)特征的分析，制定了貨品存儲策略，構(gòu)建了基于出入庫效率最高的貨位優(yōu)化模型，通過求得的有限個[f]值構(gòu)成全部可行解矩陣，將貨位分配的問題轉(zhuǎn)化為整數(shù)規(guī)劃的指派問題，接著利用匈牙利法得到解矩陣。最后通過實例驗證了本文方法的可行性和合理性。

參考文獻：

[1] Elisa FM， Cavalcante Cristiano Alexandre Virgínio. Using the Efficient Frontier to Obtain the Best Solution for the Storage Location Assignment Problem[J]. Mathematical Problems in Engineering，2014（10）：1-10.

[2]侯中，鄭國華.基于遺傳算法的汽車零配件倉庫貨位優(yōu)化研究[J].鐵道科學與工程學報，2016（11）：2305-2312.

[3]李永偉，劉樹安，郭晉秦.普通立體倉庫的貨位優(yōu)化模型與算法研究[J].計算機工程與科學，2019（2）：321-327.

[4]高楠，王蓮花，李筱燁.基于揀選型立體倉庫的貨位優(yōu)化問題研究[J].物流科技，2019（5）：153-157.

[5]徐偉華，沈文喆，巫仁亮，等.基于遺傳算法的密集型自動化立體倉庫貨位分配優(yōu)化研究[J].物流科技，2019（9）：165-168.

[6] Zhang S ， Fu L ， Chen R ， et al. Optimizing the Cargo Location Assignment of Retail E-Commerce Based on an Artificial Fish Swarm Algorithm[J]. Mathematical Problems in Engineering， 2020（5）：1-14.

[7]郭娟，錢吳永.基于粒子群算法的立體倉庫貨位優(yōu)化研究[J].物流科技，2020（4）：156-160.