王賽男

摘 要：倉庫分為傳統(tǒng)倉庫和非傳統(tǒng)倉庫，揀貨路徑問題是倉庫研究重大課題，本文通過整理國內(nèi)外文獻(xiàn)對(duì)此問題進(jìn)行綜述。

關(guān)鍵詞：揀貨路徑;倉庫

0 引言

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

1 國內(nèi)外文獻(xiàn)綜述

1.1 國內(nèi)揀貨路徑問題研究現(xiàn)狀

國內(nèi)關(guān)于倉庫揀貨路徑問題的研究，大致可以按照倉庫類型分為平面?zhèn)}庫和立體倉庫兩大類。由于在平面?zhèn)}庫中揀貨員在水平方向的多變性和堆垛機(jī)在垂直方向的恒定性，大多數(shù)學(xué)者對(duì)揀貨路徑的研究還是基于平面?zhèn)}庫。

1.1.1 平面?zhèn)}庫揀貨路徑研究

（1）關(guān)于不同規(guī)模大小的倉庫揀貨路徑問題研究

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

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

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

1.1.2 關(guān)于立體倉庫揀貨路徑問題研究

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

1.2 國外揀貨路徑問題研究現(xiàn)狀

1.2.1 傳統(tǒng)倉庫揀貨路徑問題研究

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

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

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

1.2.3 非傳統(tǒng)倉庫揀貨路徑問題研究

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

2 總結(jié)

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

參考文獻(xiàn)

[1]劉少華. 多種智能算法在魚骨布局揀選路徑?jīng)Q策中的比較研究[D].北京物資學(xué)院，2017.

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