Empirical Evaluation of a Metaheuristic for Commercial Territory Design with Joint Assignment Constraints

Abstract: In industry, territory design is motivated by changes in the number or properties of customers served by a given company. The goal of territory design is to group the customers into manageable-sized territories. It is often required to balance the demand among the territories in order to delegate responsibility fairly. In this paper, we present a metaheuristic solution approach based on GRASP (Greedy Randomized Adaptive Search Procedure) to a particular commercial territory design problem motivated by a real-world application in a beverage distribution company in the city of Monterrey, Mexico. Our empirical work includes an evaluation of the overall algorithmic performance. In addition, we study the effect of the weight parameter of the GRASP greedy function (which is a convex combination of the original dispersion-based bjective function and the relative violation of the balance constraints) on the quality of the final solution. The experiments were carried out over a set of randomly generated instances based on real-world data from the industrial partner.