Aarhus University Seal

Reinforcement learning for combinatorial optimization with an application to the fixed charge transportation problem

Peter Emil Tybirk
Tuesday 25 June 2019 11:00 Aud. D2 (1531-119)
Final Examination for the Master's degree
In this thesis we propose a novel framework for combinatorial optimization with reinforcement learning. To this end, we first cover basic theory on combinatorial optimization, reinforcement learning, function approximation and approximate methods in reinforcement learning. The proposed framework, which may be seen as a kind of hyper-heuristic, is tested on the fixed charge transportation problem, and we validate experimentally that it is capable of discovering effective heuristics. In addition, it provides insights into the efficiency of other heuristic methods. Our experiments indicate that reinforcement learning for combinatorial optimization is a promising research direction. Furthermore, we develop a new population based iterated random neighbourhood local search heuristic. We test this heuristic on 120 well known instances against the best heuristic from the literature, and in comparable computation time improve the best known solution on 81 of these instances. The heuristic is conceptually simple and easy to implement. Throughout our experiments we in total improve the best known solution on 112 of the 120 considered instances.
Contact: Andreas Klose Revised: 21.06.2019