倉庫揀貨路徑問題研究文獻綜述

王賽男

摘 要：倉庫分為傳統倉庫和非傳統倉庫，揀貨路徑問題是倉庫研究重大課題，本文通過整理國內外文獻對此問題進行綜述。

關鍵詞：揀貨路徑;倉庫

0 引言

1959年，國外學者 Dantzig等首次提出揀貨路徑問題，這個問題是由倉庫中的訂單揀貨所產生的。1976年，S. Sahni等證明了倉儲分配問題是NP-Hard問題。從此，揀貨路徑問題引起了廣大國內外學者的關注，對該問題的研究也被賦予重大的理論意義和實際意義。

1 國內外文獻綜述

1.1 國內揀貨路徑問題研究現狀

國內關于倉庫揀貨路徑問題的研究，大致可以按照倉庫類型分為平面倉庫和立體倉庫兩大類。由于在平面倉庫中揀貨員在水平方向的多變性和堆垛機在垂直方向的恒定性，大多數學者對揀貨路徑的研究還是基于平面倉庫。

1.1.1 平面倉庫揀貨路徑研究

（1）關于不同規模大小的倉庫揀貨路徑問題研究

國內學者對平面倉庫的揀貨路徑問題研究中，最具有代表性的是傳統倉庫中的雙區型倉庫。2011年，李振等將揀貨路徑優化問題先轉化成TSP（Traveling Salesman Problem）問題，在不考慮揀貨車承載量約束前提下，采用小生境遺傳算法求取揀貨作業的最優路徑。2014年，李建斌等對雙區型倉庫建立TSP模型，分別采用蟻群算法、模擬退火算法和禁忌搜索對該問題進行求解，進而得出不同待揀貨品數量下各算法的優劣程度，待揀貨品數量較少時采用模擬退火算法收斂速度相對較快，待揀貨品數量較多時采用蟻群算法可以在更短時間內得到相對較優解。在非傳統倉庫方面，2013年，蔣美仙等在Fishbone式倉庫的基礎上進行改進，并結合貫通式貨架系統，有效地縮短了倉庫總揀貨距離。2017年，劉少華對Fishbone式倉庫建立揀貨路徑優化模型，并分別采用遺傳算法、蟻群算法和布谷鳥算法三種智能算法進行求解，將三種算法對揀貨路徑的優化效果進行了對比。2019年，張志等對單葉Leaf式倉庫進行改進，提出了雙葉Leaf式倉庫，與單葉Leaf式倉庫相比，在存儲空間和總揀貨距離上都有所改善。

（2）增加車載能力約束的倉庫揀貨路徑問題研究

2009年，王宏等將傳統雙區型倉庫揀貨路徑問題轉化為車輛路徑問題（Vehicle ?Routing ?Problem，VRP），也稱車輛調度問題（Vehicle ?Scheduling ?Problem，VSP），考慮了揀貨車承載量約束，將該問題分為一單一車和一單多車兩種情形，并分別設計了遺傳算法進行求解。2010年，雷娟娟根據雙區型倉庫中揀貨路徑問題的特點，將該問題分成不考慮揀貨車輛容積和考慮揀貨車容積兩種情況，針對不考慮揀貨車容積的情況，采用蟻群算法優化求解其揀貨路徑問題。但是，他們在考慮揀貨車承載量約束的同時，要求每個待揀貨位需要揀取的貨物重量不能超過揀貨車的承載量，也就是說揀貨員到每個待揀貨位只能經過一次。考慮到現實生活中商品的季節性需求和顧客對商品的偏好等，某個待揀貨位上需要揀取的貨物重量非常有可能超過揀貨車的承載量，揀貨員也會重復經過某個待揀貨位。在此基礎上，2014年，孫慧等運用TSP模型分析雙區型倉庫的揀貨路徑，基于遺傳算法求解，并通過仿真對是否考慮建貨車承載量約束的最優揀貨路徑進行了對比，說明了考慮承載量約束的有效性和實用性。

1.1.2 關于立體倉庫揀貨路徑問題研究

2017年，胡國松等考慮到庫存周轉率的情況，以可移動式貨架的立體倉庫為研究對象，建立揀貨路徑模型，分別采用蟻群算法和遺傳算法進行求解。2018年，李云以備品備件倉儲系統作為研究對象，設計出一套以自動化立體貨架為主體的備品備件倉庫方案，并基于Flexsim仿真軟件對設計方案進行建模與仿真。

1.2 國外揀貨路徑問題研究現狀

1.2.1 傳統倉庫揀貨路徑問題研究

2004年，Hwang等將商品依據每類體積指標決定儲位，考慮返回策略、穿越策略和中間返回策略，并建立其在偶數及奇數儲存通道下總期望行走距離的公式，并把模擬的結果作比較以確定其正確性。2005年，T.Le-Duc等建立了估計揀貨巡回行走距離平均值的概率模型，并提出了一種雙選擇交換啟發式算法來解決倉儲的分區問題。2008年，Roodbergen等對單區型、雙區型和多區型倉庫的期望揀貨距離進行了研究。2016年，Scholz等將傳統倉庫布局的具體結構考慮在內，運用數學規劃分別對TSP問題中揀貨員的訂單揀貨路徑進行了優化。

1.2.2 不同存儲策略下的倉庫揀貨路徑問題研究

1991年，Jarvis同樣根據倉庫歷史數據模擬產生了未來不同貨品的入庫概率，并為待入庫貨品設計了一種新的儲位指派方法，以使其獲得最佳儲位點，進而便可獲得更少的平均揀貨時間。1996年，Hausman分別研究了自動化倉庫中 ABC分類法與固定存儲、隨機存儲和分類存儲三種方式組合使用的情況。結果發現：固定存儲策略所得的揀貨路徑長度要比隨機存儲策略所得的路徑長度更短。

1.2.3 非傳統倉庫揀貨路徑問題研究

2009年，美國學者Gue和Meller突破傳統倉庫的特征，研究提出并實際應用了兩種非傳統倉庫——Flying-V和Fishbone式倉庫。這兩種非傳統倉庫分別能比傳統倉庫在總揀貨距離縮短約10%和20%，大幅提高了倉庫揀貨效率。同年，Pohl等研究了雙項作業指令下的Fishbone式倉庫優化問題。結果發現，雙項作業指令情形下會顯著降低Fishbone式倉庫相對傳統倉庫的優勢。2012年，.ztürkoglu等基于在傳統倉庫中增加主通道條數和優化主通道與揀貨通道角度的思想，研究提出了Chevron、Leaf和Butterfly等三種非傳統倉庫。研究分析表明，這三種非傳統倉庫在總揀貨距離上分別能比傳統倉庫縮短約19.53%、21.72%和22.52%。

2 總結

可以看出，大部分國內學者的研究局限于傳統倉庫，研究方法從啟發式路徑策略、數學最優化方法演變到現在的智能優化算法;國外學者的研究更加趨向于基于傳統倉庫進行布局改進，從建模優化、算法設計或仿真優化的角度對新布局進行更深入的研究。但是，國外學者的建模優化大部分是在單元貨載或者是雙向作業指令情形下，以托盤為揀貨單位，對總揀貨距離進行建模仿真分析。

參考文獻

[1]劉少華. 多種智能算法在魚骨布局揀選路徑決策中的比較研究[D].北京物資學院，2017.

[2]張志勇，王琴，梁艷.倉庫內部布局的雙葉Leaf方法及其通道角度優化[J].系統工程，2019，37（02）：70-80.