Commercial Territory Design for a Distribution Firm with New Constructive and Destructive Heuristics

Abstract: A commercial territory design problem with compactness maximization criterion subject to territory balancing and connectivity is addressed. Four new heuristics based on Greedy Randomized Adaptive Search Procedures within a location-allocation scheme for this NP-hard combinatorial optimization problem are proposed. The first three (named GRLH1, GRLH2, and GRDL) build the territories simultaneously. Their construction phase consists of two parts: a location phase where p territory seeds are identified, and an allocation phase where the remaining basic units are iteratively assigned to a territory. In contrast, the other heuristic (named SLA) builds the territories one at a time. Empirical results reveals that GRLH1 and GRLH2 find near-optimal or optimal solutions to relatively small instances, where exact solutions could be found. The proposed procedures are relatively fast. We carried out a comparison between the proposed heuristic procedures and the existing method in larger instances. It was observed the proposed heuristic GRLH1 produced competitive results with respect to the existing approach.