This paper presents an attempt of combinatorial optimization using machine learning. Combinatorial optimization encapsulates a set of problems, where the best solution is sought in a finite set of possible solutions. We work on the vehicle routing problem. Machine learning aims to find an approximation of a desired function. In the work we first define the vehicle routing problem and established methods of solving it. The aim of this paper, is a solution to the vehicle routing problem using machine learning. We used a variational autoencoder, that makes use of structured sampling and constructs a vector embedding of the input graph. This representation is used in the decoder to find the solution to the vehicle routing problem. We successfully solve the problem on instances of size up to 100 nodes. Autoencoders were especially successful on dense graphs.
|
