{"id":{"repo_id":"unr","oai_identifier":"oai:scholarwolf.unr.edu:11714/6678"},"canonical_url":"https://search.dev.ndltd.org/etd/unr/oai:scholarwolf.unr.edu:11714/6678","repository":{"repo_id":"unr","name":"University of Nevada - Reno","base_url":"https://scholarwolf.unr.edu/server/oai/request"},"display":{"title":"Route Optimization for Automated Bridge Inspection with Genetic Algorithm","abstract":"We develop a Genetic Algorithm (GA) to generate efficient routes for a robotic bridge inspection team. Using robots to automate the process of bridge inspection will improve human safety and reduce time and money allocated to bridge inspections. To do this, we attack the problem of minimizing and balancing routes for a team of robots during a bridge inspection task. In this thesis, we present a GA with a new representation that utilizes Dijkstra's Algorithm to unfold routes. We apply our GA to this problem to minimize the time needed by a number of robots to cooperatively inspect every member of a steel truss bridge. We also improve this algorithm by incorporating a caching table to store previously computed routes; this results in much faster runtime at the cost of higher memory usage. This task maps well to the NP-Hard Min-Max k-Chinese Postman Problem (MM k-CPP), which is part of the family of Arc Routing Problems (ARPs). These represent a broad class of problems wherein the goal is to traverse every edge of a graph in the most optimal fashion, under some set of constraints. Some variants of this problem, including the MM k-CPP, are NP-hard and therefore optimal solutions for large problems are not tractable to produce in a reasonable amount of time. Results with our new representation demonstrate its ability to produce near-optimal solutions across a wide range of problem instances, under different sets of constraints. The genetic algorithm produces near optimal routes that are equally balanced among the robots, and as the number of inspection robots increases the generated routes produce a linear speedup in the time needed to inspect the entire bridge. We finally develop a methodology to use our GA to produce high-quality inspection routes on real-world bridges within a practical amount of time.","abstract_html":"We develop a Genetic Algorithm (GA) to generate efficient routes for a robotic bridge inspection team. Using robots to automate the process of bridge inspection will improve human safety and reduce time and money allocated to bridge inspections. To do this, we attack the problem of minimizing and balancing routes for a team of robots during a bridge inspection task. In this thesis, we present a GA with a new representation that utilizes Dijkstra's Algorithm to unfold routes. We apply our GA to this problem to minimize the time needed by a number of robots to cooperatively inspect every member of a steel truss bridge. We also improve this algorithm by incorporating a caching table to store previously computed routes; this results in much faster runtime at the cost of higher memory usage. This task maps well to the NP-Hard Min-Max k-Chinese Postman Problem (MM k-CPP), which is part of the family of Arc Routing Problems (ARPs). These represent a broad class of problems wherein the goal is to traverse every edge of a graph in the most optimal fashion, under some set of constraints. Some variants of this problem, including the MM k-CPP, are NP-hard and therefore optimal solutions for large problems are not tractable to produce in a reasonable amount of time. Results with our new representation demonstrate its ability to produce near-optimal solutions across a wide range of problem instances, under different sets of constraints. The genetic algorithm produces near optimal routes that are equally balanced among the robots, and as the number of inspection robots increases the generated routes produce a linear speedup in the time needed to inspect the entire bridge. We finally develop a methodology to use our GA to produce high-quality inspection routes on real-world bridges within a practical amount of time.","abstract_has_math":false,"creators":["Harris, Nicholas"],"institution":null,"degree_name":null,"degree_level":"Master's Degree","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Louis, Sushil J.","La, Hung M."],"committee_chairs":[],"committee_members":["Moustafa, Mohamed A"],"year":2019,"date_issued":"2019","date_published":"2019","updated_at":"2026-07-27T21:46:30Z","subjects":["Arc Routing","Bridge Inspection","Chinese Postman","Genetic Algorithm","Robotics","Vehicle Routing"],"languages":[],"rights":["Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 United States"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/11714/6678","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Louis, Sushil J.","La, Hung M."]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Moustafa, Mohamed A"]},{"key":"dc:creator","label":"Author","values":["Harris, Nicholas"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2020-01-30T23:11:59Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2020-01-30T23:11:59Z"]},{"key":"dc:date.issued","label":"Date","values":["2019"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Master's Degree"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Arc Routing","Bridge Inspection","Chinese Postman","Genetic Algorithm","Robotics","Vehicle Routing"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 United States"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/11714/6678"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["We develop a Genetic Algorithm (GA) to generate efficient routes for a robotic bridge inspection team. Using robots to automate the process of bridge inspection will improve human safety and reduce time and money allocated to bridge inspections. To do this, we attack the problem of minimizing and balancing routes for a team of robots during a bridge inspection task. In this thesis, we present a GA with a new representation that utilizes Dijkstra's Algorithm to unfold routes. We apply our GA to this problem to minimize the time needed by a number of robots to cooperatively inspect every member of a steel truss bridge. We also improve this algorithm by incorporating a caching table to store previously computed routes; this results in much faster runtime at the cost of higher memory usage. This task maps well to the NP-Hard Min-Max k-Chinese Postman Problem (MM k-CPP), which is part of the family of Arc Routing Problems (ARPs). These represent a broad class of problems wherein the goal is to traverse every edge of a graph in the most optimal fashion, under some set of constraints. Some variants of this problem, including the MM k-CPP, are NP-hard and therefore optimal solutions for large problems are not tractable to produce in a reasonable amount of time. Results with our new representation demonstrate its ability to produce near-optimal solutions across a wide range of problem instances, under different sets of constraints. The genetic algorithm produces near optimal routes that are equally balanced among the robots, and as the number of inspection robots increases the generated routes produce a linear speedup in the time needed to inspect the entire bridge. We finally develop a methodology to use our GA to produce high-quality inspection routes on real-world bridges within a practical amount of time."]},{"key":"dc:format","label":"Dc Format","values":["PDF"]},{"key":"dc:title","label":"Title","values":["Route Optimization for Automated Bridge Inspection with Genetic Algorithm"]}]}],"canonical_facts":{"dc:contributor.advisor":["Louis, Sushil J.","La, Hung M."],"dc:contributor.committeemember":["Moustafa, Mohamed A"],"dc:creator":["Harris, Nicholas"],"dc:date.accessioned":["2020-01-30T23:11:59Z"],"dc:date.available":["2020-01-30T23:11:59Z"],"dc:date.issued":["2019"],"dc:description.abstract":["We develop a Genetic Algorithm (GA) to generate efficient routes for a robotic bridge inspection team. Using robots to automate the process of bridge inspection will improve human safety and reduce time and money allocated to bridge inspections. To do this, we attack the problem of minimizing and balancing routes for a team of robots during a bridge inspection task. In this thesis, we present a GA with a new representation that utilizes Dijkstra's Algorithm to unfold routes. We apply our GA to this problem to minimize the time needed by a number of robots to cooperatively inspect every member of a steel truss bridge. We also improve this algorithm by incorporating a caching table to store previously computed routes; this results in much faster runtime at the cost of higher memory usage. This task maps well to the NP-Hard Min-Max k-Chinese Postman Problem (MM k-CPP), which is part of the family of Arc Routing Problems (ARPs). These represent a broad class of problems wherein the goal is to traverse every edge of a graph in the most optimal fashion, under some set of constraints. Some variants of this problem, including the MM k-CPP, are NP-hard and therefore optimal solutions for large problems are not tractable to produce in a reasonable amount of time. Results with our new representation demonstrate its ability to produce near-optimal solutions across a wide range of problem instances, under different sets of constraints. The genetic algorithm produces near optimal routes that are equally balanced among the robots, and as the number of inspection robots increases the generated routes produce a linear speedup in the time needed to inspect the entire bridge. We finally develop a methodology to use our GA to produce high-quality inspection routes on real-world bridges within a practical amount of time."],"dc:format":["PDF"],"dc:identifier.uri":["http://hdl.handle.net/11714/6678"],"dc:rights":["Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 United States"],"dc:subject":["Arc Routing","Bridge Inspection","Chinese Postman","Genetic Algorithm","Robotics","Vehicle Routing"],"dc:title":["Route Optimization for Automated Bridge Inspection with Genetic Algorithm"],"dc:type":["Thesis"],"thesis:degree_level":["Master's Degree"]},"updated_at":"2026-07-27T21:46:30Z"}