diplomsko delo
Timotej Ciglarič (Avtor), Marko Robnik Šikonja (Mentor)

Povzetek

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.

Ključne besede

nevronska mreža;kombinatorična optimizacija;problem usmerjanja vozil;vložitve grafov;računalništvo in informatika;univerzitetni študij;diplomske naloge;

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.11 - Diplomsko delo
Organizacija: UL FRI - Fakulteta za računalništvo in informatiko
Založnik: [T. Ciglarič]
UDK: 004(043.2)
COBISS: 77579779 Povezava se bo odprla v novem oknu
Št. ogledov: 300
Št. prenosov: 41
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Graph search optimization using graph embeddings
Sekundarni povzetek: 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.
Sekundarne ključne besede: neural net;graph;combinatorial optimization;vehicle routing problem;graph embeddings;computer and information science;diploma;Računalništvo;Univerzitetna in visokošolska dela;
Vrsta dela (COBISS): Diplomsko delo/naloga
Študijski program: 1000468
Konec prepovedi (OpenAIRE): 1970-01-01
Komentar na gradivo: Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani: 29 str.
ID: 13345762