倉庫揀選路徑問題研究綜述

顏偉，孫佳旭，崔若梁

(山東科技大學能源與礦業工程學院，青島 266590)

隨著經濟的發展、人民生活水平的提高，人們的需求逐漸朝個性化、獨特化的方向發展，為了適應市場需求，制造業的生產模式也逐漸轉變為多品種、小批量的生產方式，逐漸增多的貨品種類給倉庫的存儲及運輸帶來了巨大的挑戰。據統計，倉儲活動占據企業經營總成本的20%以上[1]，根據中國物流與采購聯合會公布的《2020年全國物流運行情況通報》顯示，2020年中國保管費用(即倉儲費用)5.1萬億元，同比增長7.4%，且近年來呈持續增長狀態[2]。中國制造業中原材料及半成品的揀選作業時間占整個運輸時間的30%～40%，揀選作業成本約占倉庫運作總成本的55%。貨物揀選是整個倉儲作業系統中工作量最多、復雜度最高的環節。因此，提高揀選環節的作業效率是降低倉儲成本的有效途徑。

揀選作業是指根據訂單明細對訂單處理，確定揀選策略，準確、高效的揀選貨物，并運送到相應位置的過程[3]。許多學者從貨位分配、訂單分批、車輛調度、路徑選擇等多個方面進行了研究。由于合理的規劃貨物揀選路徑能夠直接、有效地提高貨物揀選效率，所以諸多學者針對貨物揀選路徑問題進行了研究。

為此，查閱近年來中外文獻，從兩個角度對倉庫揀選路徑問題進行闡述。一方面，從作業類型的角度出發，對倉庫揀選路徑問題綜述，重點對單一作業進行分析；另一方面，從研究應用的方法技術的角度出發，對求解算法進行綜述，重點對算法的分類及改善進行討論。

1 庫揀選路徑問題綜述

首先從作業類型的角度出發，將作業模式分為單一作業和復合作業兩種，對近年來的文獻數據進行統計，得出圖1所示的統計圖。可以看出，對單一作業的研究始終多于對復合作業的研究，并且對單一作業的研究近年來有了大幅度增長。總體來看，有關倉庫揀選路徑問題的研究文獻呈增長趨勢，這說明隨著倉儲問題的突出，如何有效提升倉庫揀選效率的問題日益受到關注。

圖1 倉庫揀選路徑問題文獻統計圖

1.1 單一作業問題研究

單一作業表示僅進行出庫作業或進庫作業，主要流程如圖2所示。單一作業主要研究內容是通過路徑選擇[4-7]、揀選排序[8-11]及車輛分配[12-13]等舉措，提高貨物的揀選效率。按照研究的復雜程度由簡到繁，可以把單一作業分為3種類型：單車輛揀選單貨物作業、單車輛揀選多貨物作業及多車輛揀選多貨物作業。

圖2 單一作業流程圖

單車輛揀選單貨物作業是最簡單的作業方式，在近年的研究中，段建民等[4]將人工勢場的思想引入強化學習算法中，對揀選單貨物作業的路徑進行了研究，以達到快速找到一條較優的揀選路徑的目的；Lee等[5]提出了利用改進的Q-Learning算法和Dyna-Q算法，對單車輛揀選單貨物的路徑問題進行研究。單車輛揀選單貨物作業的作業效率相對較低，隨著經濟的快速發展，逐漸不符合時代的發展要求，因此，針對該作業方式的研究也逐漸減少。

一些學者考慮更加符合實際的單車輛揀選多貨物的作業方式，對貨物揀選順序及路徑選擇進行了研究。張新艷等[8]對魚骨型倉庫建立數學模型，以最小化總作業距離為目標，利用啟發式算法對貨物揀選順序進行了優化。傳統的啟發式算法常面臨收斂較慢、計算時間較長的問題，因此，王華東等[9]在對出貨量較大的電商倉庫研究時，采用了動態時間窗分揀策略，建立揀貨模型，同時設計了揀貨距離優化算法，極大地提高了多貨物的分揀效率；陳磊等[11]針對生產車間線邊庫存區進行了研究，利用貪婪算法優化堆垛機的揀選順序及行走路徑。

針對多車輛揀選多貨物的情況，學者們在訂單批處理、車輛調度、車輛避碰及路徑選擇等方面進行了研究。王秀紅等[14]將車輛調度與路徑優化相結合，通過對比各車輛的最優路徑實現車輛的調度；Aaya等[15]提出了一種新的訂單批處理啟發式算法，將訂單進行批處理，實現訂單揀選總距離最小化。但是上述文獻缺乏對多貨物揀選順序以及車輛避碰的研究。Bao等[16]利用Dijkstra算法對車輛調度進行研究，同時設置了停留節點避免車輛碰撞的發生；孫兆臣等[17]提出了將Logistic函數融入A*算法對無人搬運車(automated guided vehicle，AVG)小車路徑優化，引入頻次負載因子降低車輛碰撞的可能，并提出了優先級避讓的方法。

1.2 復合作業問題研究

復合作業是指即進行入庫作業又進行出庫作業，并且先執行入庫作業，然后再進行出庫作業，且每次僅運輸一個單位的貨物，主要流程如圖3所示。復合作業的研究重點是如何將入庫作業與出庫作業合理搭配，提高貨物運輸效率。

圖3 復合作業流程圖

一些學者對倉庫的復合作業進行了研究。王姍姍等[18]以穿梭車倉儲系統為研究對象，提出將復合作業問題視為任務指派問題，對出入庫作業合理搭配，從而達到總作業時間最小；楊瑋等[19]針對雙載式多層穿梭車倉儲系統中的多個穿梭車，考慮實際調度路徑及啟停速度，對復合作業問題建立數學模型進行了研究；蔡安江等[20]對立體倉庫的堆垛機建立基于復合作業的多車輛調度模型，同時提出了統籌分配的分配原則，避免車輛碰撞。

綜上所述，有關倉庫揀選路徑問題的研究文獻中，以單一作業問題的研究居多，研究內容由原來的對單車輛揀選單貨物的研究，到對單車輛揀選多貨物的研究，再到對多車輛揀選多貨物進行研究，研究中考慮的因素逐漸增多，問題的復雜性越來越高，同時也更加符合實際情況。復合作業研究的主要是利用堆垛機或穿梭車進行出入庫作業，比單一作業問題的研究更加復雜，雖然近年來對于復合作業的研究較少，但其作業效率比單一作業高是不可否認的，因此，對復合作業問題的研究也是十分有必要的。無論是對單一作業的研究還是有關復合作業的研究，多數文獻是以最小化作業距離或者最小化作業時間為研究目標，提高作業效率固然重要，但把它作為唯一的研究目標是不可取的，所以今后的研究應朝著多元化研究目標的方向發展。

2 求解方法綜述

路徑規劃問題的求解方法在近幾十年里得到了飛速的發展。在研究初期，學者多利用圖形學的方法求解，如可視圖法[21]、自由空間法[22]等。隨著技術的發展，虛擬力場法(virtual force field，VFF)[23]、模糊綜合評價法(Fuzzy)[24]等傳統算法逐漸被應用。隨后，路徑規劃問題應用了更加先進的遺傳算法(genetic algorithm，GA)[25-27]、蟻群算法(ant colony optimization，ACO)[28-29]等啟發式算法求解。近年來，新興的Q-Learning算法[30-32]、DQN(deepQnetwork)算法[33-34]等機器學習的方法也逐漸被應用。路徑規劃問題求解方法的發展歷程如圖4所示。

粒子群優化算法(particle swarm optimization，PSO)；深度Q網絡算法(deep Q network，DQN)；向量場直方圖算法(vector field histogram，VFH)

在近年來的研究中，倉庫揀選路徑問題通常被看作NP-hard問題，此類問題求解過程復雜，難以遍歷所有解，多數中外學者將此類問題抽象為TSP(travelling salesman problem)問題，利用啟發式算法進行求解。此外，隨著人工智能領域的不斷發展，機器學習的方法也逐漸被應用到揀選路徑問題上來。對近年來倉庫揀選路徑問題的求解方法進行統計，如圖5所示。可以看出，在解決倉庫揀選路徑問題的方法中，啟發式算法的應用最為普遍，并且在近幾年的研究中猛烈增長，機器學習作為新興的方法，從2016年開始也逐漸被應用，并且在穩步發展之中。因此，將從應用最為普遍的啟發式算法和機器學習方法對揀選路徑問題的求解方法進行闡述。

圖5 研究方法統計圖

2.1 啟發式算法在倉庫揀選路徑問題上的應用

近年來，倉庫揀選路徑問題中啟發式算法的應用情況如圖6所示，可以明顯看出，常用的啟發式算法有：遺傳算法、蟻群算法等。常用的啟發式算法的優缺點如表1所示。利用啟發式算法求解有時會得到很壞的解或搜索效率極差，因此，將從改進算法和混合算法兩個方面對啟發式算法的優化進行論述。

圖6 啟發式算法應用情況

表1 常用算法優缺點

針對啟發式算法存在的缺點，一些學者對算法進行了改進。

(1)改進遺傳算法。田欣等[35]針對遺傳算法收斂過慢問題，引入先驗知識并提出參數自適應調整方式，加快算法的收斂速度，并針對易陷入局部最優的問題，將模擬退火算法的Metropolis準則引入，減少搬運機器人的行走時間。利用實例進行驗證，結果證明改進后的算法在收斂速度、尋有能力上都有明顯的提升。Han等[36]為解決遺傳算法易陷入局部最優的缺點，提出采用三交換交叉啟發式算子產生最優子代的方法改進遺傳算法，通過對AGV行駛總路徑和單AGV行駛路徑兩方面最小化的約束，求得最優路徑；易琦等[37]將某個魚骨型倉庫作為研究對象，考慮車輛的載重和體積限制，將揀選路徑問題看作多目標問題進行研究，在多種約束條件下建立多目標數學模型，采用多層編碼遺傳算法進行求解，同時利用MATLAB軟件進行仿真模擬，從而證明了該算法的有效性；此外，還有學者通過多層嵌套[38-39]、適應性函數[40]等方法提高遺傳算法的性能。

(2)改進蟻群算法。蟻群算法存在的最大的缺點是收斂速度過慢，對于此，李龍澍等[41]針對蟻群算法，提出利用方向指導信息優化初始信息素的分布情況，改善了算法前期收過慢的缺點，同時利用區域安全因素對轉移概率進行改進，避免陷入局部最優，最后通過在多個不同復雜程度的模擬倉庫中實驗，從而驗證了改進效果；賀智明等[42]提出了一種自適應動態搜索蟻群算法，將偽隨機分布和自適應轉移概率相結合，加快收斂過程，同時將信息素強度分段化，避免陷入局部最優；Santis等[43]提出將運籌學的方法Floyd-Warshall(FW)算法融入傳統的蟻群算法中，增強識別最短路徑的能力。

(3)改進其他算法。除了常用的算法之外，還有學者利用其他啟發式算法進行相關研究。羅如學等[44]利用人工魚群算法對路徑規劃進行了研究，為防止算法陷入局部最優，對算法中的視野范圍進行了改進，同時修改擁擠度函數加快算法收斂速度；徐翔斌等[45]為解決多AGV擁堵問題，設計了系統優化策略，建立考慮避碰的數學模型，同時設計了時空模擬退火算法求解，通過實驗驗證了算法的有效性；Wu等[46]將圖像處理與路徑規劃避碰技術相結合，將障礙物的頂點轉化為網絡節點，改進Dijkstra算法，利用代價函數尋找最優路徑。

此外，一些學者將兩個甚至多個算法結合，形成混合算法。針對遺傳算法收斂速度較慢的問題，Maryam等[47]提出了將遺傳算法與粒子群算法混合，充分發揮粒子群算法收斂速度快的優點，解決AGV車輛調度及路徑選擇的問題；閆軍等[6]為了解決遺傳算法易陷入局部最優的缺點，將模擬退火算法與遺傳算法相結合，充分發揮模擬退火算法局部尋優的特性，改善遺傳算法易于“早熟”的缺點，為了驗證效果，采用實例分別利用遺傳算法和遺傳模擬算法求解計算，結果表明：遺傳模擬算法的揀選路徑更優，用時更短。針對粒子群算法易陷入局部最優的問題，楊瑋等[48]提出了粒子群算法和模擬退火算法相結合，從而防止因過早收斂陷入局部最優；朱永強等[49]將A*算法與蟻群算法相結合，首先利用A*算法預先搜索出來一條最短路徑作為較優解，然后利用蟻群算法繼續尋找更優解；唐磊等[50]考慮旅行商問題(travelling salesman problem，TSP)貨位僅能訪問一次的缺陷，將貪心算法與遺傳算法相結合，提高混合算法的尋優能力。

啟發式算法作為解決路徑問題最常用的求解方法，在解決倉庫揀選路徑問題上發揮著重大作用。但不可否認，啟發式算法也存在諸多問題，雖然通過各式各樣的改進，最大可能的減少了收斂過慢、局部最優等不足之處，但同樣也增加了運算的復雜度，因此在解決復雜的路徑問題時，容易出現運算時間過長、解的質量較差等問題。因此，啟發式算法更適用于求解較為簡單的路徑問題。

2.2 機器學習在倉庫揀選路徑問題上的應用

機器學習是研究機器如何模仿人類的動作、語言等活動的一門學科。近年來，強化學習作為機器學習的重要分支逐漸發展起來，它被認為是未來人工智能的核心技術之一[51]。

正是具有較強的學習能力和可以與環境交互的特點，強化學習逐漸被應用到路徑選擇問題的研究中。與啟發式算法相比，強化學習具有不同的優缺點，如表2所示。可以看出，強化學習在倉庫揀選路徑問題上的應用更加靈活，適應性更強。Q-Learning算法[52]作為強化學習中最為經典、成熟的算法之一，成為中外學者在研究路徑選擇問題上應用最多的算法。同樣，Q-Learning算法也存在前期收斂過慢及易出現維數災難的缺點，因此，諸多學者針對這兩點不足進行大量的研究和優化。

表2 啟發式算法和強化學習優缺點對比

強化學習是一種試錯學習，在前期需要不斷地嘗試學習，積累經驗，從而找到最優路徑。所以，計算前期漫無目的的搜索導致前期收斂過慢。針對此問題，中外學者采取各種措施加快收斂速度。

(1)優化Q-Learning算法。近年來，學者們針對Q-Learning算法提出諸多優化方法。徐曉蘇等[53]將引力勢場應用到算法之中，在初始環境下，目標點附近設置引力場，并構造勢場函數，同時增加了動作數量和動作步長，提高了路徑的平滑度，加快了算法的收斂速度，以達到縮短了收斂時間的目的；毛國君等[54]提出對Q-Learning算法中的貪婪因子進行改進，將傳統的算法中固定的貪婪因子動態化，當探索以失敗告終時增大貪婪因子的值，當探索成功時減小貪婪因子的值，在加快收斂速度的同時保證算法的探索性；Zhao等[55]提出將神經網絡與Q-Learning算法相結合，用于無人機路徑規劃與避碰，使得無人機能夠獲得先驗知識，提高算法的學習效率。

(2)構造新算法。唐恒亮等[56]在Q-Learning算法的基礎上結合時序差分[temporal-difference，TD(λ)]的回報思想，考慮采樣后λ個狀態，同時引入了啟發因子和調和函數，并對ε-greedy(ε為貪婪因子)探索策略加入調和函數，設計出改進的多步Q學習算法[Q(λ)算法]，加快了尋找最優路徑的速度。利用MATLAB設計仿真實驗，驗證新算法在搜尋速度、探尋次數、路徑質量等方面更優。成怡等[57]為解決強化學習方法在未知環境下收斂速度慢的問題，提出了一種基于深度圖像信息的深度強化學習算法，提高機器人的探索能力，加快了收斂速度。

在復雜環境中利用Q-Learning算法容易出現維數災難的問題，這是因為在傳統的Q-Learning算法中，會內置一個Q表用于儲存產生的Q值信息，智能體每進行一個動作，環境就會變化一次，Q表也會更新一次。因此，當環境十分復雜，智能體的動作數量將十分龐大，導致Q無法儲存全部的Q值，造成維數災難。為了解決這一問題，一些學者也進行了相關研究。針對維數災難的問題，現行最佳解決辦法是與深度學習相結合。李輝等[58]將神經網絡與Q-Learning算法相結合，提出改進的深度強化學習算法，利用值函數近似法代替了Q-learning算法中的動作值函數，利用神經網絡代替Q表，從而避免了Q-learning算法在復雜環境中容易出現的維數災難問題；董永峰等[33]提出了動態融合深度雙Q算法，利用神經網絡代替Q表，對DQN算法進行改進；Kim等[59]提出了不預先生成Q表，根據所需的學習速度調整探索策略，從而降低了維數災難發生的可能性，同時加快了收斂。

與啟發式算法相比，利用強化學習解決路徑問題不需要建立復雜的數學模型，同時強化學習在未知環境下具有較強的探索能力。但傳統的強化學習算法同樣也面臨著收斂過慢的問題，因此也僅適用于較為簡單的路徑問題。隨著深度學習的發展，學者們創建了像DQN等深度強化學習的算法，更加適用于較為復雜的環境中。

2.3 其他方法在倉庫揀選路徑問題上的應用

除傳統的啟發式算法和新興的機器學習外，還有一些學者利用射頻識別技術(radio frequency identification，RFID)、偏移度、整數規劃等知識對倉庫揀選路徑問題進行研究。李軍等[60]利用RFID技術對出入庫及揀選過程自動識別，從而對倉庫狀態實時更新，并提出了基于偏離度的路徑優化方法，提高揀選效率；Miao等[61]針對存在較多障礙物的復雜環境，提出基于矩形映射分解的路徑規劃方法，促進全覆蓋的路徑規劃；Zhen等[62]利用拓撲法創建倉庫地圖模型，提出Floyd算法搜索倉庫中任意兩個儲位的最優路徑。

綜上所述，在針對倉庫揀選路徑問題的求解方法中，以啟發式算法為主。此外，近年來倉庫揀選路徑問題的求解方法呈多元化方向發展，其中，強化學習的相關算法應用最為突出，在未來具有較大的發展空間。

3 結論與展望

根據中外學者對倉庫揀選路徑問題的研究，主要從作業類型和研究方法進行了論述。從倉庫揀選路徑問題的研究現狀以及發展前景來看，未來的研究主要集中在以下三個方面。

(1)多樣化的研究目標。目前對倉庫揀選路徑問題的研究中，多數文獻以最小化作業時間或作業距離為目標。但一味地追求高效并非最佳策略，例如，危險品儲存倉庫要在最大化安全性的前提下高效運輸，易碎品儲存倉庫要以最大化穩定性為目標，同時，一些倉庫還會以最大化綠色度等為目標。因此，如何平衡多種目標之間的比重，以符合倉庫的實際情況，成為在今后研究中需要解決的問題。

(2)多元化的研究方法。自對路徑規劃問題研究以來，圖形學方法、啟發式算法、強化學習等知識逐漸被應用。目前，啟發式算法作為倉庫揀選路徑問題中應用最多的算法，但大部分啟發式算法在收斂性、求解速度、求解質量等方面存在不足。另外，強化學習在路徑規劃領域的應用依然處于初始階段，具有較強的自我學習能力和試錯能力，因此在倉庫揀選路徑領域有很大的發展潛力，但也存在前期收斂過慢、易出現維數災難等缺點。因此，為了求解更加復雜多樣的研究目標，探尋更加優秀求解方法或混合算法是今后研究中的難點之一。

(3)更加符合實際的作業模式。在目前的研究中，多數文獻僅研究了單車輛揀選貨物或揀選單個貨物的情況。而在實際倉庫中，多個車輛同時揀選多個貨物為常態。隨著研究的深入，揀選任務及倉庫環境將逐漸變得復雜多變，也更加符合實際情況。例如，考慮多車輛協同、訂單的緊急程度等因素。因此，未來的研究將朝著復雜化、動態化發展。