改良型粒子群優化法應用於聯合訂單分批與曼哈頓繞徑揀貨問題

Abstract

顧客訂單之總搬貨距離是衡量物流倉儲中心揀貨效率優劣的重要指標之一。實務上不同顧客訂單的產品品項各異，為了減少不必要的重覆行走以有效縮減搬貨距離，會盡可能將品項相似度高的顧客訂單集中處理並歸類於同一個批次後再進行搬貨路徑的規劃。然而當顧客訂單數量龐大且產品品項複雜時，難以人工方式作有效的整體規劃。故本研究探討同時考慮了訂單分批與曼哈頓繞徑揀貨之聯合問題，當中以顧客訂單之總搬貨距離最小化為目標，並滿足揀貨台車承載容量、多產品品項之顧客訂單等限制。由於此問題不存在多項式時間演算法解，故本研究提出改良型粒子群優化法來解決此問題，當中我們所提出之可行解編碼方式可同時處理顧客訂單之批次組合與各批次內之品項搬貨順序。不同於過去之演算法，額外考慮粒子過去不好的經驗，使求解可避開不佳的解並加速往最優解方向進行。我們的設計概念是將倉儲空間設定為格子圖並定義虛擬的「訂單重心」與「批次重心」，藉由計算兩者之距離來決定使品項相似的訂單歸類於相同批次。根據實驗結果顯示，本研究所提出之方法能有效縮減顧客訂單之總搬貨距離，進而提升物流倉儲中心之揀貨效率。

In picking product items in a warehouse center to fulfill customer orders, the orders with high degrees of similarity, in practice, are categorized as the same batch to be picked, and then the routing of moving each batch of product items is planned so that repetitive traveling routes are avoided to shorten the total order picking distance. However, when the number of orders is huge and the types of product items are complicated, it is a challenging task to manually establish an overall order picking plan. As a result, this paper investigates how to efficiently solve the joint problem that integrates the order batching and the Manhattan picker routing, which aims to minimize the total order picking distance, while taking into account the capacity constraint of the picking car and the orders with multiple product items. We further propose an improved particle swarm optimization approach that additionally considers each particle’s previous bad experience to avoid bad solutions and increase the convergence efficiency, in which our solution representation can simultaneously handle the order batching combination as well as the picker routing. The idea behind our design is to transform the warehouse space into a grid, where virtual “order center” and “batch center” are defined. By calculating the distance between the two centers, similar orders are classified into the same batch. In addition, the theoretical analysis of convergence and stability of this approach is also derived. We predict that the proposed method can efficiently shorten the total order picking distance and further increase the picking efficiency.