An iterated greedy heuristic for a market segmentation problem with multiple attributes

A real-world customer segmentation problem from a beverage distribution firm is addressed. 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 paper, a detailed attribute formulation and an iterated greedy heuristic that iteratively destroys and reconstructs a given partition are proposed. The initial partition is obtained by using a modified k-means algorithm that involves a GRASP philosophy to get the initial configuration of centers. The heuristic includes an improvement method that employs two local search procedures. Computational results and statistical analyses show the effectiveness of the proposed approach and its individual components. The proposed metaheuristic is also observed very competitive, faster, and more robust when compared to existing methods.