Tabu search with strategic oscillation for improving collection assignment plans of waste electric and electronic equipment

This paper studies a districting problem arising in the collection of waste of electrical and electronic equipment. Given a set of collection bins, where users return end-of-life electronic goods, located across a region or country, the design problem involves assigning these bins to the companies responsible for the collection at a later stage. This assignment must meet specific planning and legal requirements such as a fair household distribution according to each company's market share and a fair assignment based on the bin infrastructure quality. According to the current law, this assignment must be done in such a way to avoid, to the best possible extent, regional monopolies. This anti-monopoly requirement is achieved by maximizing a dispersion function. A tabu search metaheuristic with an advanced feature of strategic oscillation is proposed for this NP-hard combinatorial optimization problem. The particular components are designed to exploit the mathematical structure of the problem entirely. Besides, a few upper bounding schemes are developed and tested. The empirical work shows the tabu search's effectiveness and its components over a broad set of instances from the literature. In particular, the strategic oscillation idea turned out to have a very positive impact. Overall, the proposed metaheuristic outperformed the best existing method for this problem.