Approaching Unsplittable Multicommodity Capacitated Fixed-Charge Network Design Problems with Reinforcement Learning

Specialeforsvar: Victor Todd-Moir

Titel:  Approaching Unsplittable Multicommodity Capacitated Fixed-Charge Network Design Problems with Reinforcement Learning

Abstract: The purpose of this paper is to apply a variety of reinforcement learning techniques to solve the Unsplittable Multicommodity Capacitated Fixed-Charge Network Design (UMCFND). In order to do, we derive a new formulation of the problem in a deterministic setting which fits into a Markov Decision Process (MDP) framework. Several obstacles of the combinatorial structure of the problem is addressed and we propose numerous methods of overcoming them. We construct similar instances of the problem and solve them to compare the solution quality of each technique but also to compare how the characteristics of the problem affect the running time of each technique. Furthermore, each solution technique is compared with the commercial solver, Gurobi. The results of the paper should be seen as a foundation for future research of the UMCFND problem rather than a finalized study.


Vejleder:  Trine Krogh Boomsma
Censor:     Pierre Pinson, DTU