Generiranje stupaca podržanim učenjem za problem usmjeravanja vozila

završni rad

• Naslov (engleski): Reinforcement learning column generation for the vehicle routing problem)
• Autor: Ela Kumer
• Mentor: Mario Brčić (mentor)
• Član povjerenstva: Mario Brčić (predsjednik povjerenstva)
• Član povjerenstva: Mihael Kovač (član povjerenstva)
• Član povjerenstva: Kristijan Poje (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2023-06-28, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Generiranje stupaca je iterativni algoritam koji se koristi za rješavanje mješovitih cjelobrojnih linearnih programa sa prevelikim brojem varijabli. Uobičajena implementacija koristi pohlepnu heuristiku za odabir stupca u svakoj iteraciji. Ovaj rad istražuje primjenu podržanog učenja za generiranje stupaca u rješavanju problema usmjeravanja vozila. Cilj ovog rada jest naučiti bolje heuristike za odabir stupaca korištenjem metoda podržanog učenja i primijeniti ih na probleme usmjeravanja vozila koji spadaju u skupinu NP-teških problema.

Sažetak (engleski)

Column generation is an iterative algorithm used to solve mixed-integer linear programs with a large number of variables. The typical implementation employs a greedy heuristic for column selection at each iteration. This paper explores the application of reinforcement learning to column generation in solving the vehicle routing problem. The aim of this paper is to learn improved heuristics for column selection using reinforcement learning methods and apply them to vehicle routing problems, which belong to the class of NP-hard problems.

• Ključne riječi: linerano programiranje; generiranje stupaca; podržano učenje; problem usmjeravanja vozila
• Ključne riječi (engleski): linear programming; column generation; reinforcement learning; vehicle routing problem
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:705746
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-07-13 10:14:44