This project utilizes a genetic algorithm to solve the orienteering problem. The theoretical foundation is the work of M. Fatih Tasgetiren, whose genetic algorithm has provided excellent results, which we try to replicate. As a start the authors translate a genetic algorithm for solving nonlinear minimization problems, written in C++ by Noyan Turkkan, into Java. It is then changed according to Tasgetirens principles to solve the orienteering problem. The resulting program is tested by running Tsiligirides’ test sets 1-4 and Chao’s test sets 64 and 66. Overall, it does not achieve as good results as Tasgetiren’s, as the results for some problems are a few percent below his. Still, in most problems it gives as good results and in certain problems it surpasses Tsiligirides’ and even Chao’s results. The algorithm has problems getting good results is in the middlesized problems, while the bigger the problem, the better results are achieved.
|Educations||Computer Science, (Bachelor/Graduate Programme) Undergraduate or graduate|
|Publication date||15 Jun 2012|
- path planning
- genetisk algoritme
- orienteering problem
- genetic algorithm