An Iterated Greedy Heuristic for a Market Segmentation Problem with Multiple Attributes

Abstract: This paper addresses a real-world customer segmentation problem from a beverage distribution firm. The firm wants to partition a set of customers, who share geographical and marketing attributes, into segments according to certain requirements: (a) customers allocated to the same segment must have very similar attributes: type of contract, type of store and the average difference of purchase volume; and (b) compact segments are desired. The main reason for creating a partition with these features is because the firm wants to try different product marketing strategies. In this work, we propose a detailed attribute formulation and an iterated greedy heuristic that iteratively destroys and reconstructs a given partition. The initial partition is obtained by using a modified K-means algorithm that involves a GRASP philosophy to get the initial configuration of centroids. The heuristic includes an improvement method that employs a variable neighborhood search procedure. Computational results and statistical analyses show the effectiveness of the proposed approach.