A Bi-objective Model for the Bins Allocation and Collection Routing Problem in Waste Management

Abstract

Effective municipal solid waste (MSW) management is critical for modern cities due to its environmental, social, and economic impacts. Given the complexity of these systems, computational tools are essential to support decision-making. This work addresses an integrated problem that combines two traditionally separate tasks: determining bin capacities at collection sites and planning collection routes. The proposed model considers two conflicting objectives: minimizing travel time and reducing the amortized costs of bin installation and maintenance. To solve the problem, we implement both an exact Mixed-Integer Linear Programming (MILP) formulation and the Non-dominated Sorting Genetic Algorithm II (NSGA-II). For NSGA-II, two encoding strategies (binary and permutation) are explored, and a factorial design is used to calibrate crossover and mutation operators along with their probabilities. Experimental results on benchmark instances show that the MILP produces high-quality reference solutions, consistently achieving more than 97% of the relative hypervolume (RHV) and lower Inverted Generational Distance (IGD) values (e.g., IGD of 1.03 in i.1 versus 3.73 for NSGA-II). However, its computational burden increases rapidly with instance size. By contrast, NSGA-II offers a scalable alternative, attaining competitive approximations in larger instances (RHV of 94.4% in i.3) with substantially lower computing effort. Overall, the MILP serves as a benchmark for solution quality, while NSGA-II provides a practical approach for real-world applications where exact optimization is infeasible.