An Exact Algorithm for Designing Optimal Districts in the Recycling of Waste Electric and Electronic Equipment through an Improved Reformulation

Abstract: In this paper, a maximum dispersion districting problem is considered that arises in the recycling of electric and electronic equipment. For a given geographic region, the problem is to partition a set of basic units (collection bins) such that each district in the region is assigned to a different company in a way that maximizes dispersion subject to a set of planning requirements. Starting with the traditional mixed-integer programming model, a covering-type model is proposed that is shown to be much more effective. In addition, a new upper bound for the maximum dispersion partitioning problem – a relaxation of the problem studied – is developed. A very efficient procedure for computing this bound is presented. Next, an exact optimization algorithm based on the reformulated model and the newly derived upper bound is proposed. The exact algorithm intelligently exploits properties of the problem in a manner that allows for a large number of binary variables to be fixed and eliminated in a pre-processing step. The actual number depends on the new upper bound and a lower bound that can be computed by means of a heuristic. Extensive computational experiments are carried out to assess the effectiveness of each component of the algorithm. The results indicate that the new bound yields speed-ups of 40-99% with respect to the best existing bound. The empirical work also shows that the new covering-type model has considerably fewer binary variables, and thus is faster to solve than the standard model. As a consequence of these improvements, the proposed exact algorithm is able to find optimal solutions to problems with up to 800 basic units and 10 companies. Previous to this research, the largest instances solved optimally had between 40 to 100 basic units and 4 companies.