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

undergraduate thesis

• Title (english): Reinforcement learning column generation for the vehicle routing problem)
• Author: Ela Kumer
• Mentor: Mario Brčić (mentor)
• Committee member: Mario Brčić (predsjednik povjerenstva)
• Committee member: Mihael Kovač (član povjerenstva)
• Committee member: Kristijan Poje (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2023-06-28, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: linerano programiranje; generiranje stupaca; podržano učenje; problem usmjeravanja vozila
• Keywords (english): linear programming; column generation; reinforcement learning; vehicle routing problem
• Language: croatian
• URN:NBN: urn:nbn:hr:168:705746
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-07-13 10:14:44