Aarhus University Seal / Aarhus Universitets segl

Cand.scient.econ Peter Emil Tybirk modtager 2019 prisen for bedste speciale inden for Operationsanalyse

11.03.2020 | Lars Madsen

Cand.scient.econ Peter Emil Tybirk tildeles DORS prisen for 2019 for specialet "Reinforcement learning for combinatorial optimization with an application to the fixed charge transportation problem" for den "nyskabende metode, generaliteten af metoden samt de konkurrencedygtige resultater i forbindelse med et meget udfordrende problem".

DORS prisen uddeles årligt af Dansk Selskab for Operationsanalyse (DORS) til det bedste speciale inden for operationsanalyse.

Abstrakt for Peter Emils speciale:

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.

Priser