A Hybrid Lehmer Code Genetic Algorithm and Its Application on Traveling Salesman Problems

<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>

Name thesis:degree_name

Doctor of Philosophy (PhD)

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Engineering Management & Systems Engineering

Year dc:date.available

2011

Author dc:creator

• Zhang, Jun

Contributors dc:contributor

• Shannon Bowling
• Resit Unal
• Ariel Pinto
• Leonardo Bedoya-Valencia

• Genetic algorithm
• Heuristics
• Lehmer code
• Traveling salesman problems
• Operational Research
• Systems Engineering

Identifier

9781124635538

OAI identifier oai:identifier

oai:digitalcommons.odu.edu:emse_etds-1140