Tour expansion in snow removal problem

Abstract: The process of removing snow from the streets of cities in an optimal way can pose quite a challenge. In order to optimize the path of the snow removing vehicle, the city can be translated into a graph with nodes as crossings and links as roads. Once the city is modelled as a graph, all nodes with degree one can be eliminated and the snow removal time is added to the closest node. An optimization problem can then be solved in order to find a vehicle path in this reduced graph. The purpose of this thesis is to give an algorithm to reconstruct the reduced graph and then dictate the proper vehicle path in this reconstructed graph. The algorithm is constructed by reversing the node elimination process, piecing together the original graph and traversing the graph to get information about what to do on the eliminated links and nodes. The obtained algorithm is presented in this thesis.