Optimizing routes for snow plowing in Trondheim using evolutionary algorithms

Abstract

In this thesis route optimization for snow plowing in Trondheim municipality (Norway) is explored. It is modeled as a node, edge, and arc routing problem, which has been shown to be NP-hard. To generate the routes a memetic algorithm is used, which is a type of genetic algorithm, where instead of mutation a simple local search to improve each genome can be performed. The routes that are generated by this algorithm are optimized for being as short as possible weighted by speed limits, so that longer stretches that can be passed through faster are preferred over shorter ones with a lower speed limit.

When working on the routes, map data from the municipality and the Norwegian Public Roads Administration is used. To verify the routes that are generated, they are compared with how the routes that cover the same set of roads are currently being driven by processing both with the algorithms fitness function.

The results show that the algorithm is capable of finding better routes than the ones that are currently driven in terms of the used fitness function, but has never found an optimal solution, even in simple constructed test cases. The fitness function however suffers from that it is rather simple, and does not take into account important factors such as the width of the roads and what that means for how many times a given road has to be traversed for it to be sufficiently clean.

What that means is that while the routes generated are not good for practical use (even though the drivers seem to like the perspective a third party suggestion gives on their work). The routes show that it is possible to draw up routes with better fitness than what is being driven by humans, and that processing routes for areas with the same amount of roads as the city center in Trondheim is feasible.