Abstract
Recent advances in deep and reinforcement learning have led to breakthroughs in several fields (e.g. game of Go, protein structure prediction, ChatGPT), in some contexts achieving superhuman performance. The progress made in these fields of Artificial Intelligence naturally leads us to study approaches based on neural networks trained by reinforcement learning for tackling complex combinatorial problems. Today, many of these problems are, more or less effectively and satisfactorily, dealt with by solving approaches relying on time-consuming definition proposed by experts in the field of Operations Research.In this context, this thesis focuses on the study of deep and reinforcement learning for the solution of two combinatorial optimization problems known as vehicle routing problems (VRP): the Capacitated Vehicle Routing Problem (CVRP), and the Ride-Hailing Problem (RHP). The former is a well-known classical optimization problem, while the latter is a more recent variant involving uncertainty, e.g. trip duration. Our main line of research focuses on the study of solvers based on deep neural networks trained using reinforcement learning (policy gradient and Deep Q-learning algorithms) on large datasets of unsolved instances. Among other things, these solvers make it possible to overcome the need for manual definition of solving methods and delegate this task to a deep neural network. For example, the network will estimate a conditional probability that is useful for iteratively constructing a candidate solution, e.g. the probability that visiting a specific client given a list of previously visited customers and the problem configuration, willbring us closer to the optimal solution. More specifically, we are studying neural network architectures based on the attention mechanism. The latter makes our solvers agnostic to instance size, enabling us to empirically study their generalization capacity, particularly in their reuse on VRP instances of a different nature or size from those considered during the training phases.This manuscript is structured around three contributions. The first one aims at studying the contribution of transfer learning to the resolution of combinatorial optimization problems using neural networks. Our study is based on the implicit transfer of knowledge from the traveling salesman problem (TSP) to the CVRP.The aim is to study whether a model trained to solve a given VRP problem can be used to solve another similar problem following the application of a few additional training steps. In the second contribution, we propose a new two-steps method involving deep neural networks and a shortest path algorithm to handlethe capacity constraint. Through our various experiments, we demonstrate the competitiveness of this method with neural approaches in the literature, as well as with classical CVRP heuristics. In our final contribution, we study the contribution of deep neural network-based solution methods to a ride-hailing problem that includes a dimension of uncertainty (stochastic nature of request observation and travel time). We propose a neural approach based on reinforcement learning, capable of handling variable numbers of requests and vehicles. Our results demonstrate the effectiveness of such an approach in tackling this type of problem.