GRASP with Path Relinking for Commercial Districting

Abstract: The problem of grouping basic units into larger geographic territories subject to dispersion, connectivity, and balance requirements is addressed. The problem is motivated by a real-world application from the bottled beverage distribution industry. For addressing dispersion minimization, a more robust measure based on the diameter of the formed territories is used. For solving this particular territory design problem, a greedy randomized adaptive search procedure (GRASP) that incorporates a novel construction procedure where territories are formed simultaneously in two main stages using different criteria is proposed. The GRASP is further enhanced with two variants of forwardbackward path relinking, namely static and dynamic. The proposed algorithm and its components have been extensively evaluated over a wide set of data instances. Experimental results reveal that the construction mechanism produces feasible solutions of acceptable quality, which are improved by an effective local search procedure. In addition, empirical evidence indicate that the two path relinking strategies have a significant impact on solution quality when incorporated within the GRASP framework. The ideas and components of the developed method can be further extended to other districting problems under balancing and connectivity constraints.