Assessing a Metaheuristic for Large Scale Commercial Districting

Abstract: In this paper, we present an empirical evaluation of a metaheuristic approach to a commercial districting problem. The problem consists of partitioning a given set of basic units into p districts so as minimize a measure of territory dispersion. Additional constraints include territory connectivity and balancing with respect to several criteria. To obtain feasible solutions to this NP-hard problem, a reactive greedy randomized adaptive search metaheuristic procedure is used. Previous work addressed medium-scale instances. In this paper, we report our computational experience when addressing larger instances ressembling more closely the size of real-world instances. The empirical work includes full assessment of the algorithmic parameters and its local search phase, and a sensitivity analysis of the balance tolerance parameter in terms of solution quality and feasibility. The empirical evidence shows the effectiveness of the proposed approach, and how this approach is significantly better than the method used by the industrial partner. The complexity of the planning constraints make the current practice method struggling on getting feasible designs. Even for the larger cases, the proposed procedure successfuly solved instances with balance tolerance parameter values of as low as 3%, something impossible to achieve by the company current standars.