Combinatorial Optimization with Reinforcement Learning
| dc.contributor.author | Persson Hijazi, Aladdin | |
| dc.contributor.author | Persson, Sanna | |
| dc.contributor.department | Chalmers tekniska högskola / Institutionen för data och informationsteknik | sv |
| dc.contributor.department | Chalmers University of Technology / Department of Computer Science and Engineering | en |
| dc.contributor.examiner | Bernardy, Jean-Philippe | |
| dc.contributor.supervisor | Damaschke, Peter | |
| dc.date.accessioned | 2024-01-03T10:50:11Z | |
| dc.date.available | 2024-01-03T10:50:11Z | |
| dc.date.issued | 2023 | |
| dc.date.submitted | 2023 | |
| dc.description.abstract | 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. | |
| dc.identifier.coursecode | DATX05 | |
| dc.identifier.uri | http://hdl.handle.net/20.500.12380/307496 | |
| dc.language.iso | eng | |
| dc.setspec.uppsok | Technology | |
| dc.subject | Combinatorial optimization | |
| dc.subject | reinforcement learning | |
| dc.title | Combinatorial Optimization with Reinforcement Learning | |
| dc.type.degree | Examensarbete för masterexamen | sv |
| dc.type.degree | Master's Thesis | en |
| dc.type.uppsok | H | |
| local.programme | Data science and AI (MPDSC), MSc | |
| local.programme | Computer science – algorithms, languages and logic (MPALG), MSc |