20.500.12556/RUL-119840 Strojno učenje za kombinatorično optimizacijo na problemu usmerjanja vozil Machine learning for combinatorial optimization for the vehicle routing problem 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. 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. kombinatorična optimizacija strojno učenje problem userjanja vozil combinatorial optimization machine learning vehicle routing problem true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2020-09-11 17:50:00 2020-09-11 17:50:03 2024-02-02 11:13:12 0000-00-00 00:00:00 2020 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 25942 30831363 Skornik_Jakob_-_Strojno_ucenje_za_kombinatoricno_optimizacijo_na_problemu_usmerjanja_vozil.pdf Skornik_Jakob_-_Strojno_ucenje_za_kombinatoricno_optimizacijo_na_problemu_usmerjanja_vozil.pdf 1 ADC85ED560C7F1925C034C5AB30561AF 247c19576170c098b1aafa49d4c158693f03b0a71e4acf5c339e2ffbe85c2f13 ef6b3b78-a1b9-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=134576 Fakulteta za računalništvo in informatiko 0 0 0