Plowing the Streets of Helena An Exploration of Algorithmic Solutions to Connected Graph Traversal Optimization

Abstract

Due to fierce winter conditions, Montana streets can become blocked with snow and ice. It is up to the snowplow operators to ensure the safety of travelers across the state by plowing and sanding roads before traffic becomes congested and accidents occur. Through algorithms and graph theory a plan can be made to optimally plow the streets so that snow and ice do not interfere with the daily commute. Through the use of two algorithms, this thesis addresses the task of optimal plowing. The first is a Greedy Algorithm, the other a Look Ahead algorithm. The Greedy Algorithm assesses the priorities of every street connected to the current intersection and chooses to plow the highest priority street. The Look Ahead algorithm allows the user to input how many streets beyond local streets are to be considered. For example, the program could look many streets into the future to seek out a street that may not have been plowed yet but is surrounded by other streets that are. Algorithms can be used in any user-defined sequence. Users are also able to create, edit, and save their own maps through a graphical user interface. The editing program allows users to create and delete both streets and intersections as well as edit properties such as position and name on existing intersections and streets. This interface allows the user to enter more complex maps, such as the sectors of Helena for more realistic optimization.