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

Abstract

Real-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.

Keywords:

• Capacitated vehicle routing
• metaheuristics
• multiobjective optimization

Acknowledgments

We gratefully acknowledge all the funding support for this work. We also thank the referees for providing many valuable comments that helped us improve the content of this article.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was partially supported by FEDER funds and the Spanish Ministry of Economy and Competitiveness (Projects ECO2013-47129-C4-3-R, ECO2016-76567-C4-2-R, and ECO2016-76567-C4-4-R), in particular, L. Delgado-Antequera acknowledges support from the Spanish Ministry of Science and Innovation through Project ECO2013-47129-C4-2-R (reference: BES-2014-068507) and the Regional Government of “Castilla y León” and FEDER funds (Projects BU329U14 and BU062U16).