20.500.12556/RUL-130322 Optimizacija preiskovanja grafov z vložitvami grafov Graph search optimization using graph embeddings Problem usmerjanja vozil s kapaciteto je NP-poln kombinatorični problem. Poleg njegove uporabnosti za dostavne službe se lahko nanj učinkovito preslika tudi veliko drugih problemov. Za reševanje problema uporabim rekurenčno nevronsko mrežo GRU z mehanizmom pozornosti. Po fazi učenja, ki traja toliko časa kot uporaba stohastičnih optimizacijskih algoritmov na več tisoč primerih, dobimo na majhnih grafih primerljivo dobre rezultate, na večjih grafih pa se zaradi povečevanja kompleksnosti problema nevronski model ne uči več dovolj hitro in je slabši. Med vložitvami grafov, ki sem jih preizkusil, dajeta najboljše rezultate node2vec in GraRep. The capacitated vehicle routing problem is an NP-complete combinatorial problem. In addition to its usefulness for delivery services, many other problems can be efficiently mapped to it. To solve the problem, I use the GRU recurrent neural network with the attention mechanism. After a learning phase that lasts as long as using stochastic optimization algorithms on thousands of cases, we get comparatively good results on small graphs. On larger graphs the neural models do not learn fast enough and produce worse results due to an increasing problem complexity. Among the tested graph embedding methods, node2vec and GraRep give the best results. nevronska mreža graf kombinatorična optimizacija problem usmerjanja vozil vložitve grafov neural net graph combinatorial optimization vehicle routing problem graph embeddings true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2021-09-13 18:20:00 2021-09-13 18:20:05 2022-09-09 04:15:53 0000-00-00 00:00:00 2021 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 30241 77579779 Ciglaric_Timotej_-_Optimizacija_preiskovanja_grafov_z_vlozitvami_grafov.pdf Ciglaric_Timotej_-_Optimizacija_preiskovanja_grafov_z_vlozitvami_grafov.pdf 1 4CD52369EA54C4E2CB91AA8A005066CE 9abf385dee96dd494c4f698116bf9bef6d3c001e8af973b2d69f2b4f6787f686 33510bb3-14ae-11ec-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=147413 Fakulteta za računalništvo in informatiko 0 0 0