A Divide-and-Conquer Approach to Commercial Territory Design

Abstract: In this paper, a commercial territory design problem with compactness maximization criteria subject to multiple territory balancing and connectivity constraints is addressed. A divide-and-conquer approach attempting to exploit recent results on successful solution of related integer quadratic models is developed with the aim of obtaining good quality solutions to large problem instances. The procedure consists of a successive dichotomy process where at each iteration a given subproblem is divided into two smaller subproblems by solving an associated territory design problem with two territories. This division process is applied until the subproblem has a tractable size and can be solved exactly by means of an integer quadratic programming model. The proposed heuristic is the rst developed, to the best of our knowledge, for this particular territory design problem. Computational results showed that this proposed procedure is an attractive technique for obtaining locally optimal solutions for large instances that are intractable by using exact optimization methods.