儲位指派問題之全域最佳化方法

Abstract

儲位指派問題所探討的是在物流中心內，如何將貨品指派到適合的儲位放置，使得滿足所有訂單需求的總揀貨距離可以達到最小。本研究將儲位指派問題建構成一個二次指 派問題，此類問題屬於 NP-Hard 問題，其複雜性高而不容易求得其全域最佳解。因此很多 不同的啟發式演算法被開發出來快速地求解此問題，但這些啟發式方法都無法保證求解品 質。本研究以 Nyberg and Westerlund (2012) 針對二次指派問題所提出線性化技術為基礎， 加入特殊序列集合第一型之改良方法來減少模型中的二元變數，以提昇二次指派問題全域最佳解的求解效率。在實證分析中，本研究將所提出的方法用在求解物流中心儲位指派問 題的真實案例，並和實務上常用的 EIQ分析法做比較。在兩種不同揀貨路徑下，分析結果 顯示所提出的方法皆可以達到較小的總揀貨距離。對物流中心而言，揀貨程序是最勞力密集及花費成本的運作，透過最佳的儲位指派來降低總揀貨距離，可藉由改善揀貨作業的效率來增進物流中心的運作績效。

The storage location assignment problem focuses on appropriately locating the stock items in storage locations to minimize the total travel distance in a distribution center for fulfilling customer demand orders. This study formulates the storage location assignment problem as a quadratic assignment problem that belongs to NP-hard problems and is not easy to be globally solved due to the high complexity. Therefore, a large number of different heuristic approaches have been developed to quickly solve this kind of problems. But those approaches cannot guarantee the quality of the solution. This study bases on the linearization technique presented by Nyberg and Westerlund (2012) for solving quadratic assignment problems, and integrates the improved model for special ordered set of type 1 to reduce the number of binary variables for enhancing computational efficiency. In the empirical analysis, the proposed method is used to solve the real case of storage location assignment problem and compare the results with the commonly used EIQ analysis method. Under two different picking paths, the proposed method results in a shorter total travel distance than the EIQ analysis method. For almost every distribution center, order picking processes are the most labor-intensive and costly activity. Through an optimal storage location assignment to decrease the total travel distance, the operation performance of a distribution center can be enhanced by improving the efficiency of order picking processes.