(1) Graduate Program in Systems Engineering
Universidad Autónoma de Nuevo León, Mexico
(2) Xpertal Global Services
Monterrey, Mexico
Abstract: A districting problem consisting of the minimization of a dispersion function subject to multiple-activity balancing and contiguity costraints is addressed. This problem arises from a real-world application in a commercial firm responsible for ditsributing bottled beverage products. The objective is to find a partition of a set of city blocks into a given number of territories that minimizes a p-median problem-based dispersion function. Minimizing this measure allows for territory compactness. Districts must be connected and balanced with respect to both activities: number of customers and workload. A heuristic procedure based on a location-allocation scheme is proposed for this NP-hard problem. This technique has been successfully used for similar territory design problems with single-activity balancing constraints. This is an iterative algorithm that consists of two phases: first centroids are determined or fixed (location phase) and then units are assigned to centroids (allocation phase). The success of this technique relies in some theoretical properties that no longer hold for problems having multiple-activity balancing constraints. The novely of our work is to design a framework for handling both connectivity and multiple-activity balancing constraints simultaneously. The solution framework is enhanced by a local search phase that attempts to improve the quality of solutions found in the allocation phase. The empirial work includes a through study of the different components of the algorithm, solution of very large scale instances, and comparison with existing work. Extensive empirical testing reveals the effectiviness of the proposed approach, including the tremendous positive impact of its local search component based on an intelligent exploitation of problem structure. The algorithm significantly outperforms the best known heuristic for this problem.