Multiobjective Scatter Search for a Commercial Territory Design Problem

Abstract: In this paper, a multiobjective scatter search (SS) procedure for a bi-objective territory design problem is proposed. A territory design problem consist of partitioning a set of basic units into larger groups that are suitable with respect to some specific planning criteria. These groups must be compact, connected, and balanced with respect to the number of customers and sales volume. The bi-objective commercial territory design problem belongs to the class of NP-hard problems. Previous work showed that large instances of the problem addressed in this work are practically intractable even for the single-objective version. Therefore, the use of heuristic methods is the best alternative for obtaining approximate efficient solutions for relatively large instances. The proposed SSMTDP (Scatter Search for a Multiobjective Territory Design Problem) method contains a diversification generation method based on a GRASP framework. The improvement method is based on a relinked local search strategy (RLS). The combination method is a two-phase method that takes as input two given $p$-partitions with their corresponding set of territory centers, and solves an assignment problem to find new territory centers. A partial solution is created by keeping on each territory those nodes that belong to the same territory in both solutions. Three new solutions are obtained from this partial solution. Each of these new solutions is generated using a GRASP procedure with an independent merit function. For instance, the first new solution is generated by assigning those unassigned nodes to the partial solution such that a dispersion measure is minimized. The second solution is created by considering a merit function related to the deviation from the target number of customers, and the third one is created by taking into account the infeasibility with respect to the allowed quantity of sales volume. The proposed SSMTDP is evaluated over a variety of instances taken from literature. This includes a comparison with two of the most successful multiobjective heuristics from literature such as SSPMP (a scatter search metaheuristic) and NSGA-II (a genetic algorithm). Experimental work reveals that the proposed SSMTDP consistently outperforms both SSPMP and NSGA-II on all instances tested.