Project Title: Applying Machine learning to Orienteering Problem 
Student: Kehan WANG
Course: MSc in Computer Science  

Abstract:
Orienteering problem is a famous combinatorial optimization problem. Under this circumstance, 
there are many viewpoints in a certain area, each viewpoint has a relative score to be collected. A person 
or a team needs to visit as many locations as possible to obtain score in a given time, the one who gets 
the highest score becomes the last winner. In past decades, combinatorial optimization problems were 
mostly solved by typical optimization approaches, including exact method, heuristic and metaheuristic 
algorithm. However, machine learning has become one of the most important technologies in computer 
science in recent years. Researches have shown that machine learning, especially neural network and 
reinforcement learning has already been applied to a large number of typical combinatorial problems, 
such as travel salesman problem and tourist trip design problem, two original patterns of orienteering 
problem.
This paper reviews past researches of orienteering problem from emergence to prosperity and 
introduces a new machine learning structure GQN to solve this problem, then compares the result with 
mainstream methods and state-of-art particular heuristic algorithm on orienteering problem datasets that 
newly created based on the authoritative rules of benchmark instances publicized by Centre for 
Industrial Management, KU Leuven. Results demonstrate that according to orienteering problem, GQN 
has the ability to obtain a comparable solution which could be a reference for future study applying 
other machine learning algorithms to relevant combinatorial optimization problems.