An exact algorithm for designing optimal districts in the collection of waste electric and electronic equipment through an improved reformulation

摘要

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.