Optimization Models and Algorithms for Sustainable Waste Collection

The waste collection sector stands out for its high operating costs and significant contribution to environmental pollution. This research aims to explore whether optimization methods can help address these issues. Specifically, through the collaboration with AcegasApsAmga, a company in this field, we aim to encourage the exchanges between academia and the private sector, ensuring that theoretical results can be spent in real-world applications. To improve sustainability, we considered employing electric vehicles for waste collection. In particular, we focused on optimizing collection routes of electric trucks, including stops at charging stations to extend their limited range. Regarding the improvement of the current collection system of our partner company, we focused on optimizing multi-period planning. Therefore, this thesis addresses the electric vehicle routing problem with non-linear charging functions and load-dependent discharging and the periodic vehicle routing problem with intermediate facilities. We have developed novel constraints, enhanced compact formulations, and a branch-cut and price algorithm to solve the aforementioned problems. The tests on instances from the literature, as well as on novel instances, demonstrate the efficacy of the proposed algorithms. It is worth noting that few authors employ exact methods for these problems. Indeed, to the best of our knowledge, this represents the first study on exact methods for the periodic vehicle routing problem with intermediate facilities. To contribute effectively to practical application, we considered case studies. However, we did not just test our algorithm on these instances. Instead, we collaborated closely with our partner company to identify key operational rules and incorporate them into our case studies. The encountered issues and the implementation of operational rules are described in detail to provide valuable information for researchers and practitioners. We have shown through these tests that electric trucks are a viable option for collecting litter bins. Moreover, we have improved the waste collection process managed by our partner company in Trieste. These results underline the relevance of the collaboration between research and industry.