Fraunhofer Center for Assistive Information and Communication Solutions – AICOSDescription:
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 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-firstcluster-second. The second approach relies on the usage of a construction heuristic by Clarke and Wright. Regarding the optimization of the Asymmetric Traveling Salesman Problemsolution, 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.
Author: Hugo Peixoto
Type: MSc thesis
Partner: Faculdade de Engenharia da Universidade do Porto
Year: 2010