發展一個有效率的指派順序演算法於多階段貨架指派問題

An Efficient Assignment Sequence Algorithm for the Multi-Stage Shelf Allocation Problem

林孟蓁(Meng-Jhen Lin)

指導教授 ： 蔡介元

元智大學/工程學院/工業工程與管理學系/碩士(2007年)

https://doi.org/10.6838/YZU.2007.00239

摘要

貨架指派是零售業中一個重要的研究議題，因為不同的展示策略會直接影響顧客的購買決策。在大多數的研究中，產品項目只依據項目的相似性將產品指派到貨架空間中，所以相同產品類別 (產品子類別) 可能會被指派到距離很遠的貨架中。但在實際的零售業環境中，相同類別、子類別的產品項目應該會被指派到鄰近的貨架空間中。另一方面，過去的研究者發展了不同的啟發式演算法來求解複雜的貨架指派問題，雖然這些演算法都有不錯的效果，但這些演算法的求解品質和計算效率仍然有改善的空間。
本研究將發展一個多階段的貨架指派方法，此方法能夠將產品項目依序依據產品的類別相似性、子類別相似性和項目相似性將產品指派到貨架中。本研究所提出的方法中，每個階段都有三項主要的工作。第一，每個項目的需求空間依據他們的表面長度和銷售量所計算而成。第二，應用本研究提出的關聯分群分析發展一個指派順序演算法，並藉由此演算法來得到一個較好的初始解集合。最後，將此初始解集合使用在基因演算法中來求解貨架指派問題。
根據本研究之結果，多階段的方法比起單階段方法能夠得到較好的貨架指派結果，而求解貨架指派的方法中，有使用初始解集合來改善基因演算法之初始解的方法不僅能得到較好的貨架指派結果，還有較少的計算成本。實驗結果顯示，本研究所提出的使用初始解集合之多階段貨架指派方法對於貨架指派問題而言，是個不錯的求解方法。

關鍵字

貨架指派 ； 指派順序 ； 多階段方法 ； 基因演算法 ； 關聯分群分析

並列摘要

Shelf allocation is one of the most important issues in retailing business, because different displaying strategies can directly impact customers’ purchasing decision. In most previous researches, items are allocated into shelf space according to their item similarity only, so that items in the same categories (or sub-categories) might be assigned in very different shelf. However, in practical retailing environment, items with the same category and sub-category should be allocated into adjacent shelf space. In addition, several researchers develop different heuristic algorithms for solving complicated shelf allocation problems. Although these methods are significant, the solution quality and computation efficiency of theses algorithms can be further improved.
In this thesis, this research develops a multi-stage shelf allocation method, which allocates items into the shelf spaces based on their category similarity, sub-category similarity, and item similarity, sequentially. There are three tasks in each level of the proposed shelf allocation method. First, the required shelf spaces for every item are obtained based on their facing length and sales volumes. Second, an assignment sequence algorithm applied the association clustering analysis is proposed to derive a nice initial solution setting. Finally, genetic algorithms with the initial solution setting derived in the second task are used to solve this shelf allocation problem.
Based on the experiment result, the multi-stage method can obtain better shelf space allocation solution than one-stage shelf allocation method. In addition, the method with initial solution setting can not only obtain a better shelf space allocation solution but also less computation cost. The experiment shows that the proposed multi-stage shelf allocation method with initial solution setting is a nice method for solving the shelf allocation problems.

並列關鍵字

Shelf Allocation ； Assignment Sequence ； Multi-Stage Method ； Genetic Algorithms ； Association Clustering Analysis

參考文獻

1. Agrawal, R., Imielinski, T., Swami, A, “Mining association rules between sets of items in large database,” Proceedings ACM SIGMOD Conference management of Data, pp. 207-216, 1993.

2. Agrawal, R., Srikant, R., “Fast algorithm for mining association rules,” Proceedings ACM VLDB Conference, pp. 487-499, 1994.

3. Ananthanarayana, V. S., Murty, M. N., Subramanian, D. K., “Multi-dimensional semantic clustering of large databases for association rule mining,” Pattern Recognition, 34 (4), pp. 939-941, 2001.

4. Anderson, E. E., Amato, H. N., “A mathematical model for simultaneously determining the optimal brand-collection and display-area allocation,” Operations Research, 22(1), pp. 13-21, 1974.

5. Andrew Lim, Brian Rodrigues, Fei Xiao, Xingwen Zhang, “Adjusted network flow for the shelf-space allocation problem,” Proceedings of the International Conference on Tools with Artificial Intelligence, 14, pp. 224-232, 2002.