Assessing a Metaheuristic for Large-Scale Commercial Districting

ABSTRACT

In this article, 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 in order to 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 (GRASP) is used. Previous work addressed medium-scale instances. In this study, we report our computational experience when we addressed larger instances ressembling more closely the size of real-world instances. The empirical work includes full assessment of the algorithmic parameters and the 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 struggle to obtain 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’s current standards.

KEYWORDS:

• Combinatorial optimization
• metaheuristics
• territory design
• multiple balancing requirements
• reactive GRASP
• territory design

Acknowledgments

I am grateful to the anonymous referees for reviewing this paper.