• Login
    View Item 
    •   Carroll Scholars Home
    • Mathematics, Engineering and Computer Science
    • Mathematics, Engineering and Computer Science Undergraduate Theses
    • View Item
    •   Carroll Scholars Home
    • Mathematics, Engineering and Computer Science
    • Mathematics, Engineering and Computer Science Undergraduate Theses
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

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

    Thumbnail
    View/Open
    2003_JohnsonK_THS_000833.pdf (4.765Mb)
    Author
    Johnson, Kylan
    Advisor
    Mark Parker; Philip Rose; Joan Stottlemyer
    Date of Issue
    2003-04-01
    Metadata
    Show full item record
    URI
    https://scholars.carroll.edu/handle/20.500.12647/3457
    Title
    Plowing the Streets of Helena An Exploration of Algorithmic Solutions to Connected Graph Traversal Optimization
    Type
    thesis
    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.
    Degree Awarded
    Bachelor's
    Semester
    Spring
    Department
    Mathematics, Engineering & Computer Science
    Collections
    • Mathematics, Engineering and Computer Science Undergraduate Theses

    Browse

    All of Carroll ScholarsCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    DSpace software copyright © 2002-2023  DuraSpace
    DSpace Express is a service operated by 
    Atmire NV