Optimized Trash Collection Routes

Optimization of Municipal Solid Waste Collection Routes based on the Containers’ Fill Status Data


The main goal of this thesis was to implement and compare algorithms for calculation of efficient trash collection routes for a pre-defined number of collection trucks according to different scenarios and constraints.

Besides, a description of the architecture design of the information system to store and retrieve data regarding the containers’ status is provided. Furthermore, it provides a description of several algorithms that can be used to obtain efficient collection routes.

This optimization problem is modelled as the Capacitated Vehicle Routing Problem. To address this problem, two approaches were analysed; the first involves solving the associated Asymmetric Traveling Salesman Problem - in which vehicle capacity constraints are ignored - followed by clustering the resulting tour into feasible routes.

This approach is called route-first-cluster-second. The second approach relies on the usage of a construction heuristic by Clarke and Wright.

Regarding the optimization of the Asymmetric Traveling Salesman Problem solution, this study compares several techniques: two construction heuristics - greedy and repetitive nearest neighbour - and three meta-heuristics - hill climbing, genetic algorithms and MAX-MIN ant system. Additionally, MAX-MIN ant system was subjected to a parameter sensibility analysis.


For any additional information regarding this project, please contact us using the inquiries form.