Orienteringsløbsproblemet løst med en genetisk algoritme

Cecilie Lyshøj Olander, Christian Johannesen, Jannick Hynding Petersen & Sofie Søe

Student thesis: Termpaper

Abstract

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.

EducationsComputer Science, (Bachelor/Graduate Programme) Undergraduate or graduate
LanguageDanish
Publication date15 Jun 2012
SupervisorsKeld Helsgaun

Keywords

  • op
  • path planning
  • genetisk algoritme
  • orienteering problem
  • genetic algorithm
  • java
  • Turkkan
  • optimization
  • orienteringsløbsproblem
  • optimering
  • ga
  • Tasgetiren
  • ruteplanlægning