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

• Published in: International transactions in operational research 2023-03, Vol.30 (2), p.1002-1030
• Main Authors: Ríos‐Mercado, Roger Z., González‐Velarde, José Luis, Maldonado‐Flores, Jabneel R.
• Format: Article
• Language: English
• Subjects: 90B80 Discrete location and assignment; 90C27 Combinatorial optimization; 90C90 Applications of mathematical programming; 90‐08 Computational methods; Bins; Combinatorial analysis; Electronic equipment; Garbage collection; Heuristic methods; Monopolies; Operations research; Optimization; Tabu search
• ISSN: 0969-6016; 1475-3995
• DOI: 10.1111/itor.12917

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$\mathcal {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.