{"id":{"repo_id":"utahstate","oai_identifier":"oai:digitalcommons.usu.edu:etd-8158"},"canonical_url":"https://search.ndltd.org/etd/utahstate/oai:digitalcommons.usu.edu:etd-8158","repository":{"repo_id":"utahstate","name":"Utah State University","base_url":"https://digitalcommons.usu.edu/do/oai/"},"display":{"title":"Multi-Stop Routing Optimization: A Genetic Algorithm Approach","abstract":"In this research, we investigate and propose new operators to improve Genetic Algorithm’s performance to solve the multi-stop routing problem. In a multi-stop route, a user starts at point x, visits all destinations exactly once, and then return to the same starting point. In this thesis, we are interested in two types of this problem. The first type is when the distance among destinations is fixed. In this case, it is called static traveling salesman problem. The second type is when the cost among destinations is affected by traffic congestion. Thus, the time among destinations changes during the day. In this case, it is called time-dependent traveling salesman problem. This research proposes new improvements on genetic algorithm to solve each of these two optimization problems. First, the Travelling Salesman Problem (TSP) is one of the most important and attractive combinatorial optimization problems. There are many meta-heuristic algorithms that can solve this problem. In this paper, we use a Genetic Algorithm (GA) to solve it. GA uses different operators: selection, crossover, and mutation. Sequential Constructive Crossover (SCX) and Bidirectional Circular Constructive Crossover (BCSCX) are efficient to solve TSP. Here, we propose a modification to these crossovers. The experimental results show that our proposed adjustment is superior to SCX and BCSCX as well as to other conventional crossovers (e.g. Order Crossover (OX), Cycle Crossover (CX), and Partially Mapped Crossover (PMX)) in term of solution quality and convergence speed. Furthermore, the GA solver, that is improved by applying inexpensive local search operators, can produce solutions that have much better quality within reasonable computational time. Second, the Time-Dependent Traveling Salesman Problem (TDTSP) is an interesting problem and has an impact on real-life applications such as a delivery system. In this problem, time among destinations fluctuates during the day due to traffic, weather, accidents, or other events. Thus, it is important to recommend a tour that can save driver’s time and resources. In this research, we propose a Multi-Population Genetic Algorithm (MGA) where each population has different crossovers. We compare the proposed MG against Single-Population Genetic Algorithm (SGA) in terms of tour time solution quality. Our finding is that MGA outperforms SGA. Our method is tested against real-world traffic data [1] where there are 200 different instances with different numbers of destinations. For all tested instances, MGA is superior on average by at least 10% (for instances with size less than 50) and 20% (for instances of size 50) better tour time solution compared to SGA with OX and SGA with PMX operators, and at least 4% better tour time compared toga with SCX operator.","abstract_html":"In this research, we investigate and propose new operators to improve Genetic Algorithm’s performance to solve the multi-stop routing problem. In a multi-stop route, a user starts at point x, visits all destinations exactly once, and then return to the same starting point. In this thesis, we are interested in two types of this problem. The first type is when the distance among destinations is fixed. In this case, it is called static traveling salesman problem. The second type is when the cost among destinations is affected by traffic congestion. Thus, the time among destinations changes during the day. In this case, it is called time-dependent traveling salesman problem. This research proposes new improvements on genetic algorithm to solve each of these two optimization problems. First, the Travelling Salesman Problem (TSP) is one of the most important and attractive combinatorial optimization problems. There are many meta-heuristic algorithms that can solve this problem. In this paper, we use a Genetic Algorithm (GA) to solve it. GA uses different operators: selection, crossover, and mutation. Sequential Constructive Crossover (SCX) and Bidirectional Circular Constructive Crossover (BCSCX) are efficient to solve TSP. Here, we propose a modification to these crossovers. The experimental results show that our proposed adjustment is superior to SCX and BCSCX as well as to other conventional crossovers (e.g. Order Crossover (OX), Cycle Crossover (CX), and Partially Mapped Crossover (PMX)) in term of solution quality and convergence speed. Furthermore, the GA solver, that is improved by applying inexpensive local search operators, can produce solutions that have much better quality within reasonable computational time. Second, the Time-Dependent Traveling Salesman Problem (TDTSP) is an interesting problem and has an impact on real-life applications such as a delivery system. In this problem, time among destinations fluctuates during the day due to traffic, weather, accidents, or other events. Thus, it is important to recommend a tour that can save driver’s time and resources. In this research, we propose a Multi-Population Genetic Algorithm (MGA) where each population has different crossovers. We compare the proposed MG against Single-Population Genetic Algorithm (SGA) in terms of tour time solution quality. Our finding is that MGA outperforms SGA. Our method is tested against real-world traffic data [1] where there are 200 different instances with different numbers of destinations. For all tested instances, MGA is superior on average by at least 10% (for instances with size less than 50) and 20% (for instances of size 50) better tour time solution compared to SGA with OX and SGA with PMX operators, and at least 4% better tour time compared toga with SCX operator.","abstract_has_math":false,"creators":["Hommadi, Abbas"],"institution":"Hosted by Utah State University Libraries","degree_name":"Master of Science (MS)","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Vicki Allan","Nick Flann","Vladimir Kulyukin"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-11-19T08:50:32Z","subjects":["Routing","Genetic Algorithm","Optimization","Time-Dependent Routing","Traveling Salesman Problem","Computer Sciences"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.26076/4afd-6d89"],"render_values":[{"text":"https://doi.org/10.26076/4afd-6d89","href":"https://doi.org/10.26076/4afd-6d89","code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.usu.edu/etd/7048","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.usu.edu/etd/7048","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.usu.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.usu.edu%3Aetd-8158","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Vicki Allan","Nick Flann","Vladimir Kulyukin"]},{"key":"dc:creator","label":"Author","values":["Hommadi, Abbas"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2010-01-01T08:00:00Z"]},{"key":"dc:date.created","label":"Dc Date Created","values":["2018-05-01T07:00:00Z"]},{"key":"dc:publisher","label":"Institution","values":["Hosted by Utah State University Libraries"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science (MS)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Routing","Genetic Algorithm","Optimization","Time-Dependent Routing","Traveling Salesman Problem","Computer Sciences"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.usu.edu/etd/7048"]},{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.26076/4afd-6d89"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["In this research, we investigate and propose new operators to improve Genetic Algorithm’s performance to solve the multi-stop routing problem. In a multi-stop route, a user starts at point x, visits all destinations exactly once, and then return to the same starting point. In this thesis, we are interested in two types of this problem. The first type is when the distance among destinations is fixed. In this case, it is called static traveling salesman problem. The second type is when the cost among destinations is affected by traffic congestion. Thus, the time among destinations changes during the day. In this case, it is called time-dependent traveling salesman problem. This research proposes new improvements on genetic algorithm to solve each of these two optimization problems. First, the Travelling Salesman Problem (TSP) is one of the most important and attractive combinatorial optimization problems. There are many meta-heuristic algorithms that can solve this problem. In this paper, we use a Genetic Algorithm (GA) to solve it. GA uses different operators: selection, crossover, and mutation. Sequential Constructive Crossover (SCX) and Bidirectional Circular Constructive Crossover (BCSCX) are efficient to solve TSP. Here, we propose a modification to these crossovers. The experimental results show that our proposed adjustment is superior to SCX and BCSCX as well as to other conventional crossovers (e.g. Order Crossover (OX), Cycle Crossover (CX), and Partially Mapped Crossover (PMX)) in term of solution quality and convergence speed. Furthermore, the GA solver, that is improved by applying inexpensive local search operators, can produce solutions that have much better quality within reasonable computational time. Second, the Time-Dependent Traveling Salesman Problem (TDTSP) is an interesting problem and has an impact on real-life applications such as a delivery system. In this problem, time among destinations fluctuates during the day due to traffic, weather, accidents, or other events. Thus, it is important to recommend a tour that can save driver’s time and resources. In this research, we propose a Multi-Population Genetic Algorithm (MGA) where each population has different crossovers. We compare the proposed MG against Single-Population Genetic Algorithm (SGA) in terms of tour time solution quality. Our finding is that MGA outperforms SGA. Our method is tested against real-world traffic data [1] where there are 200 different instances with different numbers of destinations. For all tested instances, MGA is superior on average by at least 10% (for instances with size less than 50) and 20% (for instances of size 50) better tour time solution compared to SGA with OX and SGA with PMX operators, and at least 4% better tour time compared toga with SCX operator."]},{"key":"dc:title","label":"Title","values":["Multi-Stop Routing Optimization: A Genetic Algorithm Approach"]}]}],"canonical_facts":{"dc:contributor":["Vicki Allan","Nick Flann","Vladimir Kulyukin"],"dc:creator":["Hommadi, Abbas"],"dc:date.available":["2010-01-01T08:00:00Z"],"dc:date.created":["2018-05-01T07:00:00Z"],"dc:description.abstract":["In this research, we investigate and propose new operators to improve Genetic Algorithm’s performance to solve the multi-stop routing problem. In a multi-stop route, a user starts at point x, visits all destinations exactly once, and then return to the same starting point. In this thesis, we are interested in two types of this problem. The first type is when the distance among destinations is fixed. In this case, it is called static traveling salesman problem. The second type is when the cost among destinations is affected by traffic congestion. Thus, the time among destinations changes during the day. In this case, it is called time-dependent traveling salesman problem. This research proposes new improvements on genetic algorithm to solve each of these two optimization problems. First, the Travelling Salesman Problem (TSP) is one of the most important and attractive combinatorial optimization problems. There are many meta-heuristic algorithms that can solve this problem. In this paper, we use a Genetic Algorithm (GA) to solve it. GA uses different operators: selection, crossover, and mutation. Sequential Constructive Crossover (SCX) and Bidirectional Circular Constructive Crossover (BCSCX) are efficient to solve TSP. Here, we propose a modification to these crossovers. The experimental results show that our proposed adjustment is superior to SCX and BCSCX as well as to other conventional crossovers (e.g. Order Crossover (OX), Cycle Crossover (CX), and Partially Mapped Crossover (PMX)) in term of solution quality and convergence speed. Furthermore, the GA solver, that is improved by applying inexpensive local search operators, can produce solutions that have much better quality within reasonable computational time. Second, the Time-Dependent Traveling Salesman Problem (TDTSP) is an interesting problem and has an impact on real-life applications such as a delivery system. In this problem, time among destinations fluctuates during the day due to traffic, weather, accidents, or other events. Thus, it is important to recommend a tour that can save driver’s time and resources. In this research, we propose a Multi-Population Genetic Algorithm (MGA) where each population has different crossovers. We compare the proposed MG against Single-Population Genetic Algorithm (SGA) in terms of tour time solution quality. Our finding is that MGA outperforms SGA. Our method is tested against real-world traffic data [1] where there are 200 different instances with different numbers of destinations. For all tested instances, MGA is superior on average by at least 10% (for instances with size less than 50) and 20% (for instances of size 50) better tour time solution compared to SGA with OX and SGA with PMX operators, and at least 4% better tour time compared toga with SCX operator."],"dc:identifier":["https://digitalcommons.usu.edu/etd/7048"],"dc:identifier.doi":["https://doi.org/10.26076/4afd-6d89"],"dc:publisher":["Hosted by Utah State University Libraries"],"dc:subject":["Routing","Genetic Algorithm","Optimization","Time-Dependent Routing","Traveling Salesman Problem","Computer Sciences"],"dc:title":["Multi-Stop Routing Optimization: A Genetic Algorithm Approach"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["Master of Science (MS)"]},"updated_at":"2026-11-19T08:50:32Z"}