Combinatorial Optimization with Reinforcement Learning
Ladda ner
Typ
Examensarbete för masterexamen
Master's Thesis
Master's Thesis
Program
Data science and AI (MPDSC), MSc
Computer science – algorithms, languages and logic (MPALG), MSc
Computer science – algorithms, languages and logic (MPALG), MSc
Publicerad
2023
Författare
Persson Hijazi, Aladdin
Persson, Sanna
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
This master’s thesis delves into the topic of solving combinatorial optimization problems with methods based on reinforcement learning, and specifically, we explore the potential of iterative route decoding and gradient updates in enhancing the performance of route decoding. In this context, route decoding refers to determining the most efficient route for a set of destinations, a combinatorial optimization problem often encountered in logistics and transportation planning. We introduce two methods for iteratively updating solutions for the heterogeneous capacitated vehicle routing problems. They are built upon a reinforcement learning algorithm with an attention graph encoder and use previously computed routes for an instance to improve solution quality. Our results show improved performance, in particular, on out-of-distribution data, which suggests the practical applicability of the methods. In particular, our results show that a pre-trained route planner can, with a few gradient updates with a policy gradient method, significantly improve on out-ofdistribution data.
Beskrivning
Ämne/nyckelord
Combinatorial optimization , reinforcement learning