A bi-objective solution approach to a real-world waste collection problem

AbstractReal-world situations often result in optimization problems with conflicting objectives for which the search space is constrained by several factors. In particular, performing an effective solution brings quantifiable benefits to companies in charge of the waste collection in urban areas, which are currently investing time and effort to improve their services in terms of financial, social and environmental objectives, while bearing in mind labor factors. In this work, we model a real waste collection problem as a Capacitated Vehicle Routing Problem (CVRP) with two objectives: travel cost minimization and route balancing. To generate the best approximation of the Pareto front, we develop a multi-phase procedure. The first phase constructs solutions in a semi-greedy fashion; the second phase seeks to improve those solutions with a local search; and the third phase consists of a pairwise path-relinking search. Finally, we apply it to real-world data of the problem that motivated this work.