An Evolutionary Algorithm for Waste Collection in Complex City Environments

As the population of the world is in rapid growth and economic development leads to larger rates of consumption, the field of waste management is growing ever more important. This thesis is based on the waste collection problem faced by the public waste management agency in Oslo, Norway. The purpose of the thesis is to develop an algorithm able to generate collection routes for waste collection problems based on real-world infrastructure. We model the task of waste collection as a Capacitated Arc Routing Problem (CARP), a well-known routing problem in which demand occurs along the arcs of a network. The CARP is known to be "very NP-hard", and the potential for exact approaches is limited. As such, we present an evolutionary algorithm, developed to deal with large-scale CARP instances. Two extensions are added to the CARP to realistically model the task of waste collection, namely intermediate facilities and time constraints on shifts. The performance of the algorithm is tested on three sets of benchmark instances for the CARP. The algorithm performs well for the smaller instances but struggles to find optimal solutions for more complex instances within the maximum number of iterations and with the given run parameters. However, the algorithm performs best on the instances having a topology most similar to the network representing Oslo. Four real-world instances are generated based on the infrastructure of Oslo. The smallest instance represents about 2% of the city, whereas the largest instance represents the city in its entirety. The EA is applied to the four instances, and the results are discussed in light of the algorithm's performance on the benchmark instances. The proposed EA is able to generate a valid collection plan for Oslo in its entirety. However, running the algorithm on the largest instance is very time-consuming. Because of time limitations, the EA was only run for 20 iterations on the instance representing Oslo. For the smaller instances, significant improvements in the solution quality were observed especially during the 200 first iterations. For the larger instances, significant improvements were still being made within the 500 iterations they were run for. Thus, it is likely that the routing plan obtained for the entire city is far from optimal