A Location-Allocation Heuristic for a Territory Design Problem in a Beverage Distribution Firm

Abstract: In this paper a real-world territory design problem arising in a beverage distribution firm is addressed. The firm seeks to find a partition of a set of geographic units into a given number of territories in such a way that a dispersity measure of the formed territories is minimized. In addition it is required that the territories are balanced with respect to two different node activity measures. A heuristic methodology based on a location-allocation technique is proposed to solve this problem. This location-allocation scheme consists of a two-stage iterative process where territory centers are first located and then customers are allocated to centers. This methodology has been used with relative success for territory design problems involving single balancing constraints. In our work, we extend this approach and propose an adaptation of this technique to handle multiple balancing constraints and contiguity constraints simultaneously. In addition a local search technique is applied to improve solution quality. Several experiments were conducted and the results show a good performance of the heuristic.