基于購物數據的超市布局設計算法

李驍，陳汶濱，程敏，徐媛媛，閔帆

?

基于購物數據的超市布局設計算法

李驍*，陳汶濱，程敏，徐媛媛，閔帆

(西南石油大學計算機科學學院，四川成都610500)

超市商品種類繁多，合理的布局能有效節約消費者時間，提升購物體驗。最優布局是一個困難的組合優化問題。本文利用平面圖建模，提出啟發式搜索算法以解決該問題。首先，對空間進行離散化建模，生成節點和無向邊表示的平面圖。其次，結合消費者的購物清單，根據商品屬性進行種類區分，并與相應的商品種類區域一一映射，用啟發式搜索算法生成消費者快速完成購物的近似最優布局。最后，使用優化算法優化生成最終布局。實驗基于人造數據集顯示：這項研究提出的方法是有效的和可靠的,能夠成功設計出超市合理布局。

超市布局；組合優化；啟發式算法；離散化建模

引言

數據挖掘[1-4]抽取出數據中隱藏的規律，為社會的各個方面提供決策支持[17-20]。超市商品布局是一個非常具有現實意義的問題。本文的主要研究目的是找到超市合理布局，節約消費者購物時間，提升購物體驗。

去大型超市購物已逐漸成為人們生活的一部分，但由于超市體積龐大，并不是每個人都對超市的環境、布局熟悉，需要花費消費者大量的時間搜尋商品。據統計，消費者通常花費20%的時間在商品的挑選上，剩余的80%時間用在對商品的搜尋或者其它方面[5]。普遍的消費者都希望能夠快速完成購物。因此，對超市布局進行研究就變得很有必要。

文獻[7]研究發現，現代人的生活節奏都很快，據相關統計結果顯示，人們逛超市的時間一般是1-2個小時，生活的快節奏要求超市能夠在最短的時間內滿足人們的購物需求。文獻[8]研究發現，在超級市場商品陳列中特別需要強調的一個重點問題，就是關聯性原則。所謂關聯性要求是指把分類不同但有互補作用的商品陳列在一起。由以上文獻可知，以消費者最快完成購物為目的和引入關聯性原則的超市布局是非常具有研究意義的。文獻[9]研究了具體的某一種類商品內部貨架布局的問題，以促進銷售為目的。文獻[10]研究了根據消費者的購買心理，提出大型超市合理安排賣場布局, 科學設計商品陳列的方式方法。上述兩個研究雖然考慮到超市商品布局，但是都沒有以消費者最快完成購物為目的進行超市布局。目前還有一部分研究是直接向消費者推薦導購路線，節約購物時間。如文獻[11]研究發現了消費者在購物時都在尋找一條有效路徑來進行有序地商品采購。文獻[12]根據消費者歷史購物記錄研究發現，結合關聯規則為其推薦可能感興趣的下一個商品，引導進行購物。文獻[13]研究發現可以利用遺傳算法來對消費者進行超市最短導購路徑推薦，提升購物體驗。通過向消費者推薦導購路徑，確實能夠節約消費者購物時間，但是關注點沒有集中到超市布局上。如果能夠在超市布局重排過后，進行導購路線推薦，效果可能會更好。

本文基于消費者購物數據，以消費者希望在較短的時間內完成行走過程，買完所需的東西[6]為目標，對超市商品進行布局。首先，根據圖論知識[14]對超市空間進行離散化建模，生成節點和邊表示的平面圖。接著，用數字（從1 開始的整數）與超市商品種類個數進行一一映射，隨機排列在超市平面圖中。然后，優化消費者達到購物需求總距離最小的布局，確定最終超市布局。

1 問題描述與模型建立

1.1 問題描述

問題：最小購物總路程的超市商品布局 輸入：消費者購物記錄 輸出：超市商品布局 優化目標：消費者完成購物的總路程

1.2 超市空間環境建模

超市空間建模的目的是通過對超市空間環境的特征進行考慮，轉化成能夠進行路徑計算的計算機模型[13]，并且對超市布局優化能夠更加的直觀。在實際的超市賣場中，由于商品貨架等物理障礙的存在，消費者的移動是嚴重受限的，消費者不能夠在這個特定空間自由的行走。正是由于這個限制，對超市布局進行離散化建模顯得十分的恰當。

如圖1所示的離散化建模后的超市平面拓撲結構圖，小方塊部分為商品貨架，其它空白部分為可行走部分（過道），暫時沒有考慮超市入口和出口的設置。根據商品的屬性，把商品分成若干種類，并對其分別進行編號，從1到來表示。如日用品類編為1號等。編號過后的商品貨架和行走區域一起構成了超市的整個空間物理結構。

為了計算方便，本文對相鄰的商品貨架區域之間的距離做標準化處理。假設相鄰的商品貨架之間的距離為一個單位，消費者在相鄰的商品貨架之間可以直接走一步到達，在不相鄰的商品貨架，消費者不能直接到達，必須經過其它的區域。

圖1 離散化的超市布局平面圖

將超市空間結構離散化建模，使其表示成結點和邊的無向圖，通過無向圖的性質可知，已經把貨架等物理約束考慮在內。此外，根據消費者的購物清單，對其要購買商品的類別屬性進行區域匹配，消費者在超市內的行走轉化為在有限節點集合上的移動，這樣可以更加方便求出消費者走的總距離，對商品布局優化的進展起到了一定的推動作用。

1.3 超市商品布局優化數學模型

已知存在位消費者的消費數據，假設現已存在一種超市布局，以第一位消費者為例，通過其購物清單知道有種商品，以商品種類屬性對這種商品進行種類劃分得到有種商品種類，將商品種類與具體的節點進行匹配，得到消費者需要訪問的節點集合N = {l| i =1, 2, 3。表示離散化建模后的超市平面圖，V = {v | i = 1, 2, 3，為結點總數；為相鄰節點之間的無向邊集合。即為一條路徑方案，通過計算找出訪問完集合中的節點所走的最短路徑以及此時的路徑長度。假設中任意兩節點的最短距離為，建立如下數學模型：

式（1）表示第一位消費者達到購物所需的總路徑長度。其余消費者總路徑長度計算同理可得，然后把所有消費者的總路徑長度進行累加。建立如下數學模型：

(2)

接著使用Apriori算法對交易數據集進行頻繁項集挖掘，利用挖掘出的2-階頻繁項作為優化算法的輸入優化超市布局。此過程中，盡可能讓是2-階頻繁項的商品種類距離最近，直到掃描完所有的2-階頻繁項，并計算出當前布局下，消費者走的總距離，我們定義只要在優化過后的超市布局中計算出的小于優化前計算出的就認為優化成功。在計算最短距離問題的本質上等同于問題，本文首先是利用曼哈頓思想計算節點之間的距離，然后根據啟發式算法求出節點之間的最短距離，最后構造優化算法對超市布局進行優化，確定最終的超市布局。

2 超市商品布局規劃

本文以節約消費者購物時間為出發點做超市布局研究。超市布局設計分二步進行：第一步，用啟發式搜索算法生成近似最優布局；第二步，使用優化算法優化近似最優布局，生成最終布局。

2.1 近似最優布局

本文采用整數和商品種類進行映射。如圖1所示，根據超市商品種類屬性進行分類，分別對其編號。假設某超市有商品種類2種，構造*的矩陣，并分別把這些商品隨機擺放在這個矩陣中，產生一種按商品種類擺放的超市布局。

在當前超市布局下，以交易數據集中的某一位消費者購物清單來計算出此消費者完成購物需求的總距離。首先根據該消費者購物清單上的商品屬性，對其進行種類匹配，得到個區域，每個區域用對應的節點號進行編號，得到節點集合為{2,15,12,4,8,10}；該節點集合就為該消費者購買所需商品要走的區域。

在得到上述節點集合后，采用曼哈頓距離計算思想，構造啟發式算法來計算最小距離。具體的，首先根據節點集合構造如圖2所示的鄰接矩陣。矩陣中V表示節點集合中的第個節點，1 ≤ V≤ n，，為節點數。定義若兩個節點之間相鄰，則它們的距離等于1，否則就使用曼哈頓距離計算，如節點V(X,Y)和V(X,Y)，它們之間的距離由此公式計算d(V,V)=|X – X|+|Y – Y|。節點自身的距離為0。

圖2 鄰接矩陣D

基于啟發式算法求解走完節點集合中所有節點的最短距離步驟為：

1、依次把節點集合中的節點作為起點，以節點V開始，構造如圖2所示的鄰接矩陣D；

2、遍歷鄰接矩陣的每一行。首先遍歷節點V所在的行，找到與節點V距離最近的節點V(1≤i≤m)，記錄節點V和節點V之間的距離，然后在遍歷節點V所在的行，已遍歷過的節點直接跳過，找到與V距離最近的節點，記下此距離；采用遞歸思想，直到遍歷完所有的節點；最后計算出以V為起始節點的路徑中的最短距離（即最短路徑）。

3、使節點V和節點V相互交換，產生新的節點集合，以節點V開始，構造如圖2所示的鄰接矩陣D；以同樣的思想計算出V為起始節點的最短距離。依次循環，直到所有節點都作為過起始點就終止；最后比較出以這個節點為起始點所計算出的距離中的最短距離（即所求的最小距離）。

其余消費者最短距離計算同理可得。最后把所有消費者完成購物所需的最短路徑長度累加起來，此長度即為該交易數據集中所有消費者在當前超市布局下走的總距離。假設隨機產生100種超市布局，交易數據集不變，分別計算出每種布局下的最短距離，通過比較得到距離最短的超市布局，此布局即為近似最優布局。其流程圖如圖3所示。

圖3 啟發式算法流程圖

2.2 優化近似最優布局

Apriori[15]算法是一種挖掘關聯規則的頻繁項集算法，其核心思想是通過候選集生成和情節的向下封閉檢測兩個階段來挖掘頻繁項集[16]。

本文在對近似最優布局優化前，利用Apriori算法對交易數據集進行數據挖掘，篩選出2-階頻繁項集，構造以此為輸入源的優化算法對超市布局進行優化。例如：

假設篩選出的長度為2的頻繁項集為{1,2,1,7,1,10,2,10}，已知近似最優布局下的最短距離為miniDis。以其中的{1,2}為例解釋其優化思想。如圖4所示。

圖4 優化方法圖

首先從左邊的矩陣中找出1所在的位置，接著以1為中心遍歷找出與1距離為1的點（圖中紅色線條標記的點）；然后把2依次和紅色線條標記的點進行互換，分別計算出當前距離并進行存儲，直到遍歷完距離為1的點，比較得到當前最短距離；如果此距離比minDis小，矩陣改為變換后的形式排列；否則遍歷與1距離為2 的點；依次循環，盡最大可能讓1和2的相距最近。直到循環完所有長度為2的頻繁項集，達到優化目的。其流程圖如圖5所示。

圖5 優化算法流程圖

3 實驗結果

這一部分中，將通過實驗驗證超市布局研究是否具有一定的意義、能否成功設計出合理的超市布局。

3.1 數據集

本文是通過人造數據集進行實驗。構造出的數據集分為稀疏數據集、均勻數據集和密集數據集三種類型；文中選取均勻數據集進行實驗，即5000位消費者分別在商品種類為16種、36種和64種中的交易數據集。

實驗結果

隨機排列6*6的矩陣100次，分別計算出100種布局中5000位消費者達到購物需求的總路程；從中挑選出10種布局，具體如圖6所示。

圖6 研究意義結果圖

從圖6可知，最壞的布局下，消費者完成購物所走的總距離為71692，而相對最好的距離只有56197，它們相差15495，相差比例接近22%。所以說，超市布局研究的確存在一定的研究意義。然后，我們分別在超市商品種類為16種、36種、64種的情況下，計算出優化前和優化后消費者達到購物需求的總距離。如圖7所示。

圖7 優化前后距離比較圖

圖8 超市布局圖

由圖7可知，優化超市布局是相對成功的。特別是在超市商品種類為36種和64種情況下，優化前后的距離比例相差接近12%，優化情況是相當可觀的。同時也體現出本文的布局設計算法是穩定的，能夠有效的設計出合理的布局，成功率較高。下面以6*6的矩陣顯示超市商品種類為36種的優化過后的超市商品布局，如圖8所示。

4 結語

本文旨在為超市布局提供建設性方案，設計合理布局。首先，通過將超市空間離散化建模，生成用節點表示商品各類區域，用無向邊表示兩個相鄰區域之間可達的路線平面圖。其次，結合消費者購物清單上的商品預先通過商品屬性進行種類區分，并映射到相應的商品種類區域上，用啟發式搜索算法生成近似最優布局；最后，利用優化算法確定最終的超市布局。通過實驗結果顯示，本文的方法能夠成功的設計出合理的超市布局，布局設計算法簡單高效。

[1] FAYYAD U. From Data Mining to Knowledge Discovery in Databases [J]. Ai Magazine, 1996, 17(3):37-54.

[2] HE X, MIN F, ZHU W. Parametric Rough Sets with Application to Granular Association Rule Mining [J]. Mathematical Problems in Engineering, 2013, 2013(2):1-13.

[3] PEDRO D. MetaCost: a general method for making classifiers cost-sensitive[C] International Conference on Knowledge Discovery & Data Mining. 1999:155-164.

[4] AZUAJE F. WITTEN IH, FRANK E: Data Mining: Practical Machine Learning Tools and Techniques [J]. Biomedical Engineering Online, 2006, 5(1):1-2.

[5] BELL D R, LATTIN J M. Shopping Behavior and Consumer Preference for Store Price Format: Why "Large Basket" Shoppers Prefer Edlp[J]. Marketing Science, 1998, 17(1):66-88.

[6] JIA H W,JIANG T,ZHAO F. Research on route recommendation for indoor multi-travel destinations[J]. World Automation Congress. Mexico:[s.n.],2012,50(6):1-4.

[7] 莊鑫雁,魏珍珍,張麗. 超市的布局設計比較分析——以北京華聯、美廉美超市為例[J]. 企業研究, 2005(7):60-62. (ZHUANG X Y, WEI Z Z, ZHANG L. Comparative analysis of supermarket layout design, such as beijing hualian and meinianmei supermarket[J]. Corporate Research, 2005(7):60-62.).

[8] CIL I. Consumption universes based supermarket layout through association rule mining and multidimensional scaling [J]. Expert Systems with Applications, 2012, 39(10):8611-8625.

[9] WU W Y, LEE C L, FU C S, et al. How can online store layout design and atmosphere influence consumer shopping intention on a website? [J]. International Journal of Retail & Distribution Management, 2013, 42(1):4-24.

[10] FOXALL G R, GOLDSMITH R E, BROWN S. Consumer psychology for marketing [M]. Cengage Learning EMEA, 1998.

[11] LARSON J S, BRADLOW E T, FADER P S. An exploratory look at supermarket shopping paths[J].International Journal of Research in Marketing，2005,22(4):395-414.

[12] RUDIN C, LETHAM B, SALLEB-AOUISSI A, et al. Sequential event prediction with association rules[C] Proceedings of 24th Annual Conference on Learning Theory, Budapest:[s.n.],2011:1-13.

[13] 韓建妙,劉業政. 基于遺傳算法的超市最短導購路徑推薦[J]. 計算機工程與應用, 2016, 52(4):238-242. (HAN J M, LIU Y Z. Genetic algorithm-based shortest shopping guide route recommendation in supermarket [J]. Computer Engineering and Applications, 2016, 52(4):238-242.)

[14] KAY E. Graph theory with applications [M]. London: Macmillan, 1976:237-238.

[15] AGRAWAL R, SRIKANT R (1994) Fast algorithms for mining association rules. In: Proceedings of the 20th VLDB conference, pp 487–499

[16] BORGELT C, KRUSE R. Induction of association rules: A priori implementation[C] Compstat. Physica-Verlag HD, 2002: 937-944.

[17] YAO Y. Three-way decisions with probabilistic rough sets [J]. Information Sciences, 2010, 180(3):341-353.

[18] ZHANG H R, MIN F, SHI B. Regression-based three-way recommendation [J]. Information Sciences, 2016.

[19] LIU D, YAO Y. Three-way Investment Decisions with Decision-theoretic Rough Sets [J]. International Journal of Computational Intelligence Systems, 2012, 4(1):66-74.

[20] YANG X B, QI Y S, SONG X N, YANG J Y (2013) Test cost sensitive multigranulation rough set: model and minimal cost selection. Inf Sci 250:184–199.

An Algorithm for Supermarket Layout Design with the Shopping Data

LI Xiao, CHEN Wenbin, CHENG Min, XU Yuanyuan, MIN Fan

(School of Computer Science, Southwest Petroleum University, Chengdu 610500, China)

Reasonable layout can effectively save the consumers’ time and tailor the shopping experience for there are a wide variety of goods in supermarket. The optimal allocation is based on a difficult combinatorial optimization problem. This paperproposed a heuristic algorithm with the plane modeling to solve it. First, the floor plan made up of nodes and undirected edge was generated by discretization modeling for space. Second, customers’ shopping lists are mapped into specific zones based on the goods type. The approximate optimal layout which can meet the needs of rapid shopping was generated by using the heuristic algorithm. Finally, we used the optimization algorithm to create the final layout. The experiments on our artificial data sets show that: the research method is effective and reliable, and it can successfully design a legitimate layout in supermarket.

supermarket layout; combinatorial optimization; heuristic algorithm; discretization modeling

1672-9129(2016)02-0036-05

TP3

A

2016-09-08；

2016-09-19。

國家自然科學基金61379089。

李驍(1992-)，男，四川達州，學生，碩士，主要研究方向：數據挖掘、關聯規則；陳汶濱(1965-)，男，四川隆昌，教授，主要研究方向：油田信息化、數據庫技術與應用、計算機模擬與仿真。

(*通信作者電子郵箱：swpusccdlx@163.com)