Tabu Search with Strategic Oscillation for Improving Collection Assignment Plans of Waste Electric and Electronic Equipment

Abstract: This paper studies a districting problem arising in the collection of waste of electrical and electronic equipment (WEEE). Given a set of collection bins, where users return end-of-life electronic goods, located across a region or country, the design problem consists of assigning these bins to the companies responsible for the collection at a later stage. This assignment must meet certain planning and legal requirements such as a fair household distribution according to the market share of each company and a fair assignment based on the bin's infrastructure quality. According to the current WEEE II Directive, this assignment must be done in such a way so as to avoid, to the best possible extent, regional monopolies. This 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 so as to fully exploit the mathematical structure of the problem. In addition, a few upper bounding schemes are developed and tested. The empirical work shows the eectiveness of the tabu search and each of its components over a wide set of instances from the literature. In particular, the strategic oscillation idea turned out to have a very positive impact. Overall, the proposed metaheuristic clearly outperformed the best existing method for this problem.