Strojno učenje za kombinatorično optimizacijo na problemu usmerjanja vozil

ŠKORNIK, JAKOB (author), Robnik Šikonja, Marko (mentor)

Delo predstavlja poskus kombinatorične optimizacije s pomočjo strojnega učenja. Kombinatorična optimizacija zajema množico problemov, kjer iščemo najboljšo rešitev iz končne množice možnih rešitev. Izbrali smo problem usmerjanja vozil. S strojnim učenjem iščemo dober približek iskane funkcije. Na začetku definiramo problem usmerjanja vozil in predstavimo metode za njegovo reševanje. Glavna tema dela je reševanje problema usmerjanja vozil s strojnim učenjem. Uporabimo variacijski samokodirnik, ki z uporabo vzorčenja grafa ustvari vektorsko vložitev grafa. V dekodirniku uporabimo naučeno predstavitev za iskanje rešitve problema. S samokodirnikom uspešno rešimo problem na grafih z manj kot 100 vozlišči. Posebej uspešni so samokodirniki na gostih grafih.

• Language: Slovenian
• Keywords: kombinatorična optimizacija, strojno učenje, problem userjanja vozil
• Work type: Bachelor thesis/paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2020
• PID: 20.500.12556/RUL-119840
• COBISS.SI-ID: 30831363
• Publication date in RUL: 11.09.2020

Secondary language

• Language: English
• Title: Machine learning for combinatorial optimization for the vehicle routing problem

Abstract

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.

• Keywords: combinatorial optimization, machine learning, vehicle routing problem