Traveling Salesman Problems (TSP) is a widely studied combinatorial optimization problem. The goal of the TSP is to find a tour which begins in a specific city, visits each of the remaining cities once and returns to the initial cities such that the objective functions are optimized, typically involving minimizing functions like total distance traveled, total time used or total cost.
Genetic algorithms were first proposed by John Holland (1975). It uses an iterative procedure to find the optimal solutions to optimization problems.
This research proposed a hybrid Lehmer code Genetic Algorithm. To compensate for the weaknesses of traditional genetic algorithms in exploitation while not hampering its ability in exploration, this new genetic algorithm will combine genetic algorithm with 2-opt and non-sequential 3-opt heuristics. By using Lehmer code representation, the solutions created by crossover parent solutions are always feasible.
The new algorithm was used to solve single objective and multi-objectives Traveling Salesman Problems. A non Pareto-based technique will be used to solve multi-objective TSPs. Specifically we will use the Target Vector Approach. In this research, we used the weighted Tchebycheff function with the ideal points as the reference points as the objective function to evaluate solutions, while the local search heuristics, the 2-opt and non-sequential 3-opt heuristics, were guided by a weighted sum function.
","abstract_html":"<p>Traveling Salesman Problems (TSP) is a widely studied combinatorial optimization problem. The goal of the TSP is to find a tour which begins in a specific city, visits each of the remaining cities once and returns to the initial cities such that the objective functions are optimized, typically involving minimizing functions like total distance traveled, total time used or total cost.</p> <p>Genetic algorithms were first proposed by John Holland (1975). It uses an iterative procedure to find the optimal solutions to optimization problems.</p> <p>This research proposed a hybrid Lehmer code Genetic Algorithm. To compensate for the weaknesses of traditional genetic algorithms in exploitation while not hampering its ability in exploration, this new genetic algorithm will combine genetic algorithm with 2-opt and non-sequential 3-opt heuristics. By using Lehmer code representation, the solutions created by crossover parent solutions are always feasible.</p> <p>The new algorithm was used to solve single objective and multi-objectives Traveling Salesman Problems. A non Pareto-based technique will be used to solve multi-objective TSPs. Specifically we will use the Target Vector Approach. In this research, we used the weighted Tchebycheff function with the ideal points as the reference points as the objective function to evaluate solutions, while the local search heuristics, the 2-opt and non-sequential 3-opt heuristics, were guided by a weighted sum function.</p>","abstract_has_math":false,"creators":["Zhang, Jun"],"institution":null,"degree_name":"Doctor of Philosophy (PhD)","degree_level":"Dissertation","degree_discipline":"Engineering Management & Systems Engineering","degree_department":null,"school":null,"contributors":["Shannon Bowling","Resit Unal","Ariel Pinto","Leonardo Bedoya-Valencia"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-04-01T07:00:00Z","date_published":"2011-04-01T07:00:00Z","updated_at":"2026-07-24T03:34:25Z","subjects":["Genetic algorithm","Heuristics","Lehmer code","Traveling salesman problems","Operational Research","Systems Engineering"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["9781124635538"],"render_values":[{"text":"9781124635538","href":null,"code":true}]}]},"links":{"outbound_url":"https://digitalcommons.odu.edu/emse_etds/140","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Shannon Bowling","Resit Unal","Ariel Pinto","Leonardo Bedoya-Valencia"]},{"key":"dc:creator","label":"Author","values":["Zhang, Jun"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2019-03-19T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Engineering Management & Systems Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy (PhD)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Genetic algorithm","Heuristics","Lehmer code","Traveling salesman problems","Operational Research","Systems Engineering"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["9781124635538","https://digitalcommons.odu.edu/emse_etds/140"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Traveling Salesman Problems (TSP) is a widely studied combinatorial optimization problem. The goal of the TSP is to find a tour which begins in a specific city, visits each of the remaining cities once and returns to the initial cities such that the objective functions are optimized, typically involving minimizing functions like total distance traveled, total time used or total cost.
Genetic algorithms were first proposed by John Holland (1975). It uses an iterative procedure to find the optimal solutions to optimization problems.
This research proposed a hybrid Lehmer code Genetic Algorithm. To compensate for the weaknesses of traditional genetic algorithms in exploitation while not hampering its ability in exploration, this new genetic algorithm will combine genetic algorithm with 2-opt and non-sequential 3-opt heuristics. By using Lehmer code representation, the solutions created by crossover parent solutions are always feasible.
The new algorithm was used to solve single objective and multi-objectives Traveling Salesman Problems. A non Pareto-based technique will be used to solve multi-objective TSPs. Specifically we will use the Target Vector Approach. In this research, we used the weighted Tchebycheff function with the ideal points as the reference points as the objective function to evaluate solutions, while the local search heuristics, the 2-opt and non-sequential 3-opt heuristics, were guided by a weighted sum function.
"]},{"key":"dc:title","label":"Title","values":["A Hybrid Lehmer Code Genetic Algorithm and Its Application on Traveling Salesman Problems"]}]}],"canonical_facts":{"dc:contributor":["Shannon Bowling","Resit Unal","Ariel Pinto","Leonardo Bedoya-Valencia"],"dc:creator":["Zhang, Jun"],"dc:date.available":["2019-03-19T07:00:00Z"],"dc:description.abstract":["Traveling Salesman Problems (TSP) is a widely studied combinatorial optimization problem. The goal of the TSP is to find a tour which begins in a specific city, visits each of the remaining cities once and returns to the initial cities such that the objective functions are optimized, typically involving minimizing functions like total distance traveled, total time used or total cost.
Genetic algorithms were first proposed by John Holland (1975). It uses an iterative procedure to find the optimal solutions to optimization problems.
This research proposed a hybrid Lehmer code Genetic Algorithm. To compensate for the weaknesses of traditional genetic algorithms in exploitation while not hampering its ability in exploration, this new genetic algorithm will combine genetic algorithm with 2-opt and non-sequential 3-opt heuristics. By using Lehmer code representation, the solutions created by crossover parent solutions are always feasible.
The new algorithm was used to solve single objective and multi-objectives Traveling Salesman Problems. A non Pareto-based technique will be used to solve multi-objective TSPs. Specifically we will use the Target Vector Approach. In this research, we used the weighted Tchebycheff function with the ideal points as the reference points as the objective function to evaluate solutions, while the local search heuristics, the 2-opt and non-sequential 3-opt heuristics, were guided by a weighted sum function.
"],"dc:identifier":["9781124635538","https://digitalcommons.odu.edu/emse_etds/140"],"dc:subject":["Genetic algorithm","Heuristics","Lehmer code","Traveling salesman problems","Operational Research","Systems Engineering"],"dc:title":["A Hybrid Lehmer Code Genetic Algorithm and Its Application on Traveling Salesman Problems"],"thesis:degree_discipline":["Engineering Management & Systems Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Doctor of Philosophy (PhD)"]},"updated_at":"2026-07-24T03:34:25Z"}