<dl id="jlhvx"><noframes id="jlhvx">
<dl id="jlhvx"></dl><del id="jlhvx"><noframes id="jlhvx">
<span id="jlhvx"><progress id="jlhvx"></progress></span><del id="jlhvx"></del><listing id="jlhvx"><strike id="jlhvx"><listing id="jlhvx"></listing></strike></listing>
<listing id="jlhvx"><noframes id="jlhvx"><listing id="jlhvx"></listing>
<listing id="jlhvx"><noframes id="jlhvx"><listing id="jlhvx"></listing>
<var id="jlhvx"></var>
<dl id="jlhvx"></dl>
<span id="jlhvx"></span>
<var id="jlhvx"><strike id="jlhvx"></strike></var>
<dl id="jlhvx"><noframes id="jlhvx">
<listing id="jlhvx"><strike id="jlhvx"></strike></listing><dl id="jlhvx"><noframes id="jlhvx">
<del id="jlhvx"></del>
<dl id="jlhvx"><noframes id="jlhvx">
<listing id="jlhvx"></listing>
<dl id="jlhvx"><strike id="jlhvx"></strike></dl>
<del id="jlhvx"><noframes id="jlhvx">
<var id="jlhvx"><noframes id="jlhvx"><var id="jlhvx"></var>
<del id="jlhvx"><strike id="jlhvx"></strike></del>
<dl id="jlhvx"><noframes id="jlhvx">

倉儲中心揀選作業研究綜述

2021-12-24 10:52| 發布者: www.artist-contribution.com| 查看:

摘要: 在倉儲中心揀選作業中, 以降低人員行走距離、提高揀選效率的研究為對象, 對揀選作業中的相關研究問題和解決方案進行了討論和綜述。 ...

1 引言

揀選作業 (order picking, 又稱揀貨作業, 配貨作業) , 是指根據客戶訂貨單所規定的商品品名、數量和儲存儲位, 將商品從貨垛或貨架上取出, 并分放在指定貨位, 完成用戶的配貨要求的過程。揀選過程一般包括訂單的分批, 訂單揀選順序和貨品揀選順序合理安排等。揀選作業是整個倉儲作業中勞動最密集、運營成本最高的環節。制造業正朝著單次批量小、批次數量多、響應時間短的方向發展。同時, 很多配送中心為了爭取到更多的客戶開始接受延遲訂單 (late order) , 因此對發貨速度的要求越來越高了。大量的規模較小的倉庫正在被少數的規模較大的配送中心所取代, 為了贏得市場, 這些配送中心都在朝著日配送量大、配送時間短的方向發展。制造業和配送中心的發展趨勢使揀選系統的設計和管理變得越來越重要, 同時也變得越來越復雜了。
揀選系統的追求目標是在一定資源條件下, 實現服務水平的最大化。而服務水平又與訂單交貨時間、訂單完整性和訂單準確性等多個因素相關。其中, 按訂單迅速找到客戶所需的貨物并完成裝運是提高配送企業服務水平的關鍵, 因此, 實現揀選時間的最小化是所有揀選系統共同追求的目標。揀貨時間、行走時間和找貨時間是構成揀選時間的三個主要因素, 其中行走時間又占到整個揀選時間的55%。因此, 行走時間或者說是行走距離是進行倉儲設計和優化時考慮的首要問題。國內外圍繞減少行走距離, 提高揀選效率的研究主要集中在以下幾個方面:布局設計 (layout design) 、儲位指派 (storage assignment) 、分區揀選 (zoning picking) 、批次配貨 (Order Batching) 和配貨路徑規劃 (routing) 。
2布局設計
揀選作業中的布局主要包括容納揀選系統的設施布局 (facility layout) 和揀選系統內部的布局 (internal layout) 。設施布局考慮不同部門 (如接收、揀貨、存儲、排序和配送等) 間的布局, 通常根據不同部門間的活動關聯進行規劃, 其目的是實現控制成本的最小化。文獻[1]描述了幾種有效的設施布局的設計過程。
內部布局設計, 也稱為巷道配置問題 (aisle configuration problem) , 考慮block的數目, 以及揀選區中每個block中的巷道的數量、長度和寬度。通常是尋找關于某一目標函數的“最好”的倉庫布局, 且最常見的目標函數就是行走距離。
對人工揀選系統的內部布局設計的研究并不是很多。文獻[2]使用分析和仿真的方法, 在倉儲內部布局的基礎上對存儲策略進行了研究。文獻[3]為確定巷道布局提出了非線性目標函數, 用于實現采用隨機存儲策略的倉儲中心的行走距離的最小化。同樣是平均行走距離的最小化為目標, Caron等人對基于COI (cube-per-order index) 的存儲策略下布局設計進行了研究[4]。
相對于人工揀選系統, 對自動存取系統 (AS/RS, Automated storage and Retrieval system) 的內部布局設計問題的關注要多一些。Bozer和White的研究表明, 當采用隨機存儲策略時, 貨架的高度與長度的比與揀選設備的垂直運動速度與水平運動速度的比應一致[5]。Larson等人1997年采用啟發式方法實現布局設計, 并根據貨品重量為貨品指派存儲位置, 以達到提高地面空間利用率和降低行走距離的目的[6]。

3 儲位指派

在根據客戶訂單對貨物進行揀選之前, 貨物必須要先保存在倉儲中心內的具體儲存位置。儲存作業應考慮最大限度的利用空間, 最有效的利用勞動力和設備, 最安全經濟的搬運貨物, 最良好的保護和管理貨物。存儲指派方法可以定義為用于為產品指定存儲位置的一組規則。好的儲存策略可以減少出入庫的移動距離, 縮短作業時間。下面對常采用的五種存儲策略進行討論, 它們分別是隨機存儲 (random storage) 、最近可用
存儲 (closest open location storage) 、定位存儲 (dedicated storage) 、全周轉率存儲 (full-turnover storage) 和分類存儲 (class-based storage) 。

3.1 隨機存儲策略與最近可用存儲策略

隨機存儲將入庫的每一托盤或一定數量的貨品, 按相同的概率指派到任意可使用的存儲位置。每一個貨品被指派的儲存位置不是固定的, 而是隨機且可以改變的, 也就是說, 任何品項可以被存放在任何可利用的位置。由于存儲位置可以共用, 儲區空間的利用效率較高, 但貨物的出入庫管理及盤點工作較難進行。同時, 因為周轉率高的貨品可能被儲存在離出入口較遠的位置, 增加了出入庫的搬運距離;且具有相互影響特性的貨品可能被存儲在相鄰位置, 可能造成貨品間的相互傷害或發生危險。對隨機儲存系統與定位儲存系統的模擬實驗, 發現定位存儲系統相對于隨機存儲系統可節省35%的移動儲存時間, 但卻增加了30%的儲存空間。隨機存儲指派方法通常以增加行走距離為代價獲得較高的空間利用率。隨機存儲策略一般只在計算機控制環境下采用。
如果允許存儲作業人員自主選擇他們所存儲貨物的存儲位置, 那么得到的存儲系統就是最近可用存儲系統。也就是說, 貨物會被指派到存儲作業人員所遇到的第一個可用的存儲位置。因此, 貨物通常按其入庫時間的先后順序被儲存于距離出入口 (depot) 由近至遠的存儲位置。如果倉儲中心中存在空閑的存儲位置, 在這種存儲指派方法下將會出現如下現象:越接近出入口位置的貨架越滿, 越接近倉庫后面的貨架越空。Hausman等人認為在以托盤為單位進行作業時, 隨機存儲策略和最近可用存儲策略具有相似的執行效率[7]。

3.2 定位存儲策略

如果采用定位儲存策略, 那么每一項貨物都有固定的儲位, 貨品不能互用儲位。定位儲存的一個優點是每種貨品都有固定儲存位置, 揀貨人員對貨物的位置比較熟悉。這種存儲策略的一個缺點是即使貨物不在儲位, 其存儲位置也要保留。此外, 這種指派方式要求每一種貨物規劃的儲位容量不得小于其可能的最大庫存量。因此是空間利用率最低的一種存儲指派方式。
零售企業的倉庫中產品與位置 (product-to-location) 的指派通常與商店的布局相一致, 因為產品按邏輯進行了分組, 可以減少店鋪中的工作量。此外, 可按周轉率大小或出貨頻率安排貨物的存儲儲位, 從而縮短出入庫時貨物搬運的距離;還可根據貨物的特性安排其存儲位置, 從而降低貨品之間的不良影響。最后, 如果產品重量不同, 固位存儲策略也是有幫助的。將較重的貨物放在貨盤的底部, 較輕的貨物放在貨盤的頂部。通過將貨物按重量進行排隊并安排相應的工人揀貨, 可以在不增加勞動的同時獲得較好的堆垛順序。

3.3 全周轉率存儲

全周轉率存儲根據貨物周轉率確定它們在存儲區域的位置。通常銷售率最高的貨物被擺放在最易取得的位置, 如靠近出入口的地方;搬動速度低的產品通常位于倉庫后面的存儲位置。早期的全周轉率存儲策略是Heskett的體積訂單指數 (Cube-Per-Order Index, COI) 規則。一類貨品的COI定義為一定時期內, 貨品所需全部空間與訂單數的比, 并將COI值最低的貨物安排在距離出入口最近的位置。相關研究還有Kallina and Lynn的文獻[8], Malmborg的文獻[9]。
實際中, 全周轉率存儲和定位存儲的結合較易實現。其缺點是由于用戶需求經常變化會導致產品COI排序的頻繁變化。采取基于COI或其他需求頻率的定位指派方法, 與隨機存儲相比需要更多的信息, 因為必須對訂單數據和存儲數據進行加工以對貨品排序和指派。

3.4 分類存儲

分類存儲, 將所有的儲存貨物按照一定特性劃分成不同類別, 每一類貨品的存放位置固定, 并按照一定的原則為同一類的不同貨物指派具體的存儲位置。分類儲存通常按產品相關性、流動性、尺寸、重量、特性等對貨物進行劃分, 是以上提到的方法的組合。
在進行庫存控制時, 將貨物劃分為不同類別的經典方法是帕雷托 (Pareto) 分析法、又稱為ABC分析法, 通常由COI或揀貨體積等衡量貨物需求頻率實現貨物的分類。習慣上將移動速度最快的貨物稱為A類, 次快的為B類, 并依次類推。盡管在某些情況下, 更多的分類能在行走時間方面帶來附加的收獲, 但分類的數目通常為三個。
根據仿真實驗結果, Petersen等人發現在人工揀選系統中考慮行走距離時, 全周轉率存儲優于分類存儲方法。兩者之間的差別在于類劃分策略 (如, 分類數、每類占存儲體積的百分比等) 以及所采用的路徑規劃方法。對于AR/RS系統, Yang和Van den Berg等人發現分類數為6的分類存儲方法是最好的選擇。這種方法的優點是可以將搬運速度快的貨品存儲在靠近出入口位置的同時, 又能滿足隨機存儲所具有的靈活性和低存儲空間要求。Graves等人發現為了保證入貨的貨品能保存到正確的區域, 分類存儲必須有空閑存儲位置, 類的數量會增加存儲空間的需求。因此, 分類存儲比隨機存儲需要更多的存儲空間。關于分類存儲的研究多集中于AS/RS。
分類儲存的優點是便于暢銷品的存取, 具有定位存儲的各項優點;各分類的儲存區域可根據貨品特性再做設計, 有助于貨品的儲存管理。分類儲存的缺點是儲位必須按各項貨品最大載庫量設計, 因此儲區空間平均的使用效率低;分類儲存比定位儲存具有彈性, 但也有與定位儲存同樣的缺點。

4 分區揀選

分區揀選是將揀選區劃分為多個分區, 每個揀選人員只負責揀選訂單中屬于其所處分區的貨物。其優點是揀貨人員只需在一個較小的區域進行作業, 不但可以減少交通擁擠, 還可以使揀選人員熟悉貨品在分區中的位置。分區揀選的主要缺點是由于訂單在揀貨時進行了分割, 在發貨給客戶前還必須將其進行整合。
Speaker在文獻[10]中對配送中心分區策略做了一般性的介紹與說明。De Koster在1994年構建了分區揀選和傳送系統的Jackson隊列網絡模型, 能快速估算訂單的揀選時間和平均在揀訂單數。De Koster通過模擬實驗對結果進行了比較, 其估算結果可用于確定分揀系統大小和分區的數量[11]。Brynzér和Johansson通過案例對批次揀選與分區揀選進行了分析, 認為在串行分區 (progressive zoning) 揀選系統中, 實現揀選人員間的工作負載平衡是很重要的[12]。Jane給出了幾種啟發式算法用于串行分區揀選系統中不同分區中揀貨人員的工作負載的平衡和分區大小的調節[13]。Jane和Laih還針對并行分區 (synchronized zoning) 分揀系統中工作負載平衡問題, 提出了貨物儲位指派的啟發式算法。算法將出現在同一訂單中的貨品存儲在同一個分揀區中[14]。
動態分區揀選是相對于分區大小固定的靜態分區而言的, 其特點是以動態的方式確定分區的大小, 并實現分區揀選作業人員的指派和管理。將生產運作領域中bucket-brigades理念應用于分區分揀作業就是動態分區揀選的一個例子。bucket-brigades可以協調生產線上工人的工作, 以實現生產的連續進行和效率的提高。在串行分區揀選系統中, 揀貨作業人員揀選完屬于其所屬分區的貨品后將已部分完成的訂單遞交給下一分區的揀貨作業人員, 一直到揀貨作業完成。其要點是確定訂單在揀貨作業人員之間傳遞的時間。Bartholdi等人在文獻中對Bucket-Brigades在配送中心中的實現進行了報告, 該方法既能提高配貨效率, 又能減少管理工作量[15], 其它相關成果可參閱文獻[16]。

5 批次配貨

訂單揀貨 (single order picking) 以訂單為單位進行貨品的揀取, 適用于單張訂單訂購品項多, 且同一品項在不同訂單重復率不高的情形。對于單張訂單訂購品項較少的情況, 如果在一次揀選作業中完成一組訂單而非一個訂單的揀選就能減少揀選作業人員的行走時間。訂單批次配貨的思路是, 先將某一數量的訂單匯總成一批次訂單, 再針對該批次訂單進行總量揀取, 最后再以訂單為單位對所揀取品項進行二次分類。分批揀選中訂單的分批方式主要有兩種, 一種是訂單相似度 (Order Proximity) 分批, 另一種是時間窗口 (Time windows) 分批。
訂單相似度分批方法根據訂單中貨物的存儲位置與其它訂單中貨物的存儲位置的相似度進行訂單分批。Gademann等人在2001年對人工揀貨系統中的訂單相似分批問題進行了討論, 在證明問題的NP復雜性后, 分別通過分支定界 (branch-and-bound) 算法和2-opt啟發式算法解決小規模訂單配貨問題和大規模訂單配貨問題[17]。訂單相似度分批的關鍵是訂單之間相似度的衡量, 常采用的兩種啟發式算法是種子算
法 (seed algorithm) 和節約算法 (saving algorithm) 。
種子算法又可分為種子選取和訂單成批兩個階段。種子選取階段為每批訂單選擇一個種子訂單;訂單成批階段則確定下一步該將那一個尚未分批的訂單加到當前分批。通常根據訂單與種子訂單的“距離”決定是否加入該訂單。常見的“距離”測算方法有:增加該訂單到當前批訂單后所增加的需訪問的巷道數;批訂單中的所有貨物位置的“重心”與備選訂單的所有貨物位置“重心”的距離;備選訂單中所有貨品與種子訂單中貨品最近的距離的和;備選訂單貨品位置所覆蓋的區域數量。節約算法源于Clarke和Wright1964年的車輛調度問題 (VRP:Vehicle Routing Problem) 算法, 其基本思想是將大量較短的行走 (tour) 組合成少數較大的行走, 從而達到降低行走距離的目的。
De Koster等人在多貨架人至物 (picker-to-parts) 揀選系統中對種子算法和節約算法進行了比較研究, 從行走時間、分批數量和實際應用等方面對算法進行了評價。結論是最簡單的分批方法也比先進先服務 (FCFS, First Come First Service) 的常規分批方法效率高。同時, 種子算法與S形路徑算法和較大揀選設備結合使用效率最好, 而節約算法則與最大間隙路徑算法和小容量揀選設備結合使用效率最好。
時間窗口分批方式, 將在同一時間段到達的一組訂單合為一個分批, 時間段的長度可以是固定的, 也可以是變化的。根據是否允許分割訂單, 訂單分批后的貨物分類方式也有所區別:如果訂單可分割, 可采用邊揀選邊分類的策略 (sort-while-pick strategy) ;如果訂單不可分割, 則應采取分揀后再分類的策略 (pick-and-sort strategy) 。文獻[18]討論了人工揀貨系統中, 訂單隨機達到的情況下, 時間窗口可變的分批問題。

6 路徑優化

路徑或順序優化的目的是合理安排配貨順序, 以實現行走距離或行走時間的最小化。如果將所揀取貨品的存儲位置抽象為點, 存儲位置之間的行走距離抽象為點之間的弧, 該類型問題就是一類特殊的旅行商問題 (TSP:Traveling Salesman problem) 。按照倉儲中心的分揀系統配置的不同, 路徑優化問題可分為四類:傳統矩形分揀系統配貨路徑優化問題、單元荷載系統 (Unit-Load AS/RS) 配貨路徑優化問題、MOB AS/RS (Man-on-Board AS/RS) 配貨路徑優化問題、旋轉貨架 (Carousel) 系統配貨路徑優化問題。

6.1 矩形分揀系統配貨路徑優化

Ratliff和Rosenthal的S形 (S-Shape) 路徑是一種最簡單的配貨路徑, 揀貨人員從巷道一端進入巷道, 沿平行貨架單向移動, 并只能在巷道的另一端改變巷道。另一種簡單的啟發式算法是返回法 (return method) , 揀貨人員從巷道的一端進入走道揀取貨品, 并且從進入巷道一端改變巷道。當每一巷道中待揀取的貨品數較少時, 返回法的效果較S形算法好。相關的算法還有很多, 如Goetschalckx and Raliff的算法可以實現揀貨人員能雙向移動時的路徑規劃問題[19], Roodbergen和De Koster的算法用于解決具有三個cross巷道的分揀系統中的路徑優化問題[20]。

6.2 單元載荷系統配貨路徑優化

單元載荷系統中作業人員以交叉的方式進行儲存操作和揀取操作, 其解決方法可分為靜態算法和動態算法兩類。靜態算法根據給定的一組儲存與揀選需求對問題進行求解, 不考慮作業期間出現的新需求;動態算法則考慮作業期間出現的新需求。
進行儲存作業時, 如果采用定位儲存策略, 靜態揀存路徑優化問題就可轉化為傳統的物料調配運輸問題和任務分配問題, 從而得到多項式精確算法。通常認為隨機儲存或分類儲存的靜態揀存路徑優化問題是NP復雜問題, 其研究重點是高效的啟發式算法。Han等人1987年提出的匹配算法, 可在儲存與揀選任務之間存在物品位置對應關系的前提下, 實現分揀系統中揀貨人員行走距離的最小化[21]。Lee和Schaefer通過任務分配問題模型解決中等規模問題, 可找到最優或近最優的解[22]。
動態揀存路徑優化算法多由靜態算法發展而來, 通常的做法是先尋求已到達的揀存任務順序的解, 再在此基礎上對新加入任務進行動態重排序。人工智能技術被用于動態路徑優化問題的求解, 效果良好。某些情況下, 配貨作業不但要考慮人員行走距離的最小化, 還要考慮客戶訂單及時性的需求。因此, 在進行配貨路徑優化時還必須考慮訂單的交貨期問題。
有學者對存在臨時??奎c (Dwell Point) 的單元荷載系統的優化問題進行了研究。揀貨作業人員完成某一作業后不必返回集貨點或停留點, 而可??吭谀骋慌R時??奎c, 直接等待下一作業的開始。文獻[23]將前面所提出的配貨排序規則、臨時??奎c選擇規則和儲存位置分配規則應用于具有不同產品的混合配貨系統, 進行仿真研究。Kim等人對一特殊的自動揀存系統的路徑優化問題進行了研究, 并給出了分族啟發式算法。該系統中揀貨操作和儲存操作不是交叉進行的, 而是完全分開的, 且集貨點完全分散[24]。

6.3 Mo B系統 (Man-on-Board AS/RS) 配貨路徑優化問題

在MOB AS/RS分揀系統的揀貨方式與傳統矩形配貨系統的揀貨方式相似, 也是一次性把所需貨品揀選至集貨點, 但移動方式不同。矩形分揀系統中, 揀選人員或設備只能沿著巷道的方向前行或后退, 且只能在巷道的首尾兩端改變巷道;在MOB AS/RS系統中存在三種模式移動:直線模式 (Rectilinear norm) , 柴比雪夫移動模式 (Chebyshev norm) 和歐式距離模式
(Euclidean norm) 。
Gudehus對柴比雪夫移動模式下的路徑最優問題進行了研究, 提出了分段啟發式算法 (Band heuristic) 。該方法沿垂直方向把貨架劃分為高度相等的兩部分, 下面部分貨架上的貨品按水平坐標由大到小的順序揀取, 上面部分的貨品則按相反順序揀選。如果一次揀選貨物較多, 可將貨架按高度劃分為更多相等的部分[25]。Goetschalckx和Ratliff通過凸多邊形算法對相同問題進行了求解。具體的做法是, 先將水平坐標或垂直坐標最大的貨品 (存儲位置) 連成一凸多邊形, 然后將不在凸多邊形上的待揀取的貨品根據Chebyshev距離特性逐一加入凸多邊形, 加入的過程中遵循增加路徑最小的原則[26]。分段算法與凸殼算法各有優缺點, 分段算法計算速度快、易于實現, 但解有時不理想;凸殼算法通常能得到最優或較滿意解, 但計算量大、不易實現。為克服以上算法的缺陷, Bozer等人提出了1/2分段插入啟發式算法, 并建議采用中心席卷算法 (Center Sweep heuristic) 求解問題[27]。
為了保證揀貨人員的安全, 某些MOB揀貨系統對高位貨架和低處貨架采取不同的移動模式。文獻[28]對采用混合移動模式的揀貨系統的路徑優化問題進行了研究, 通過混合凸多邊形啟發式算法進行問題的求解。該系統在低處采用柴比雪夫移動模式, 高處采用直線移動模式。文獻[29]則通過仿真對解決傳統旅行商問題的鄰近域搜索算法、連續插入算法和局部搜索算法等進行了比較和評估。

6.4 旋轉貨架系統配貨路徑優化問題

旋轉貨架系統中, 揀貨作業人員或設備位于集貨點, 配貨時揀貨人員控制貨品旋轉到集貨點進行揀取。根據具體配置又可分為水平旋轉貨架系統 (Horizontal Carousel) 、垂直旋轉貨架系統 (Vertical Carousel) 和雙向旋轉貨架系統 (Rotary Carousel) 三類。合理解決旋轉貨架系統配貨作業優化調度能顯著提高旋轉貨架系統的作業效率。
文獻[30]最先提出了此類系統的揀選作業優化調度問題, 將一次揀選多個訂單任務的揀選作業優化調度問題轉化為每個訂單中貨品的揀選順序和訂單的揀選順序。其研究表明, 在訂單到達率比訂單揀取率小得多時, 訂單內貨品的揀選順序是關鍵;當訂單到達率對揀選作業有顯著影響時, 就必須考慮訂單需求與訂單配貨作業之間貨架的無用旋轉時間了。文獻[31]給出了訂單順序固定的情況下, 揀選順序的最優問題的動態規劃算法。文獻[32]在此基礎上將訂單順序未確定的作業優化調度問題轉化為傳統的中國郵遞員問題, 并提出最優算法。文獻[33]對雙操作作業在對單旋轉貨架和雙旋轉貨架下的揀選效率進行了研究, 研究表明采用雙旋轉貨架時效率較高。Litvak等人2001年對所揀貨品在旋轉貨架中呈獨立均勻分布時貨架的最小旋轉距離進行了討論, 2004年對以上問題進行了進一步研究, 計算出最小旋轉距離的上界和概率分布[34,35]。