• norsk
    • English
  • English 
    • norsk
    • English
  • Login
View Item 
  •   Home
  • Fakultet for informasjonsteknologi og elektroteknikk (IE)
  • Institutt for datateknologi og informatikk
  • View Item
  •   Home
  • Fakultet for informasjonsteknologi og elektroteknikk (IE)
  • Institutt for datateknologi og informatikk
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Optimizing routes for snow plowing in Trondheim using evolutionary algorithms

Randby, Simon Glisic
Master thesis
Thumbnail
View/Open
14027_FULLTEXT.pdf (22.97Mb)
14027_ATTACHMENT.zip (1.692Gb)
14027_COVER.pdf (317.9Kb)
URI
http://hdl.handle.net/11250/2358379
Date
2015
Metadata
Show full item record
Collections
  • Institutt for datateknologi og informatikk [7361]
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.
Publisher
NTNU

Contact Us | Send Feedback

Privacy policy
DSpace software copyright © 2002-2019  DuraSpace

Service from  Unit
 

 

Browse

ArchiveCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsDocument TypesJournalsThis CollectionBy Issue DateAuthorsTitlesSubjectsDocument TypesJournals

My Account

Login

Statistics

View Usage Statistics

Contact Us | Send Feedback

Privacy policy
DSpace software copyright © 2002-2019  DuraSpace

Service from  Unit