An Exact Algorithm for Designing Optimal Districts in the Collection 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 collection of waste electric and electronic equipment. For a given geographic region, the problem is to partition a set of collection or basic units such that each district in the region is assigned to a different company in a way that maximizes a dispersion function 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. Next, an exact algorithm based on the reformulated model is presented along with the newly derived upper bound. The 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.

Extensive testing indicates that the new bound yields speed-ups with respect to the best existing bound of up to 23%. The computations also show that the new covering-type model has a tighter linear programming relaxation, and thus is faster to solve than the standard model. The proposed exact algorithm is able to find optimal solutions to instances with up to 800 basic units and 12 companies, and to instances with up to 1400 basic units and 8 companies. Previously, the largest instances solved optimally had between 40 and 100 basic units and 4 companies.