Combinatorial Optimization with Reinforcement Learning

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.