A Benders Decomposition Approach for an Integrated Bin Allocation and Vehicle Routing Problem in Municipal Waste Management

Abstract

The municipal solid waste system is a complex reverse logistic chain which comprises several optimisation problems. Although these problems are interdependent – i.e., the solution to one of the problems restricts the solution to the other – they are usually solved sequentially in the related literature because each is usually a computationally complex problem. We address two of the tactical planning problems in this chain by means of a Benders decomposition approach: determining the location and/or capacity of garbage accumulation points, and the design of collection routes for vehicles. We also propose a set of valid inequalities to speed up the resolution process. Our approach manages to solve mediumsized real-world instances in the city of Bahía Blanca, Argentina, showing smaller computing times in comparison to solving a full MIP model.