Waste collection route optimization based on real fill status data

The final version of the document is available in PDF.

People

This project was developed in Fraunhofer Portugal Research Center AICOS.

Student
Hugo Miguel Pereira Peixoto
Supervisor
Luís Paulo Reis (Ph.D.)
Second supervisor
Ana Cristina Aguiar (Ph.D.)

Abstract

Fraunhofer Portugal Research Center for Assistive Information and Communication Solutions is currently developing a system to monitor the fill status of waste containers. The introduction of a waste container fill status monitoring system in the city of Porto, Portugal, gives rise to several opportunities. For example, it allows the development of a detailed analysis of the city’s waste generation distribution and the optimization of waste collection routes.

This document describes the architecture design of the information system to store and retrieve data regarding the containers’ status. Furthermore, it provides a description of several algorithms that can be used to obtain efficient collection routes. This optimization problem is modeled as the Capacitated Vehicle Routing Problem. To address this problem, two approaches were analyzed; 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 neighbor — 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.

Results show that MAX-MIN ant system achieves more efficient routes when the number of ants is higher, although it increases the algorithm’s running time. When dealing with a scenario in which there is a limited time-frame, it is recommended that a low number of ants is used. The algorithm was also shown to be very sensitive to changes in parameter β, which indicates if an ant should give more importance to the distance between two vertices or to the pheromone levels in that arc. This analysis suggests that β should be close to 20.

When evaluating the performance of the presented techniques applied to the Capacitated Ve- hicle Routing Problem, MAX-MIN ant system produced, in average, more efficient routes than the other approaches.