Rješavanje problema pakiranja

undergraduate thesis

• Title (english): Bin Packing Problem
• Author: Samuel Lucić
• Mentor: Marko Čupić (mentor)
• Committee member: Marko Čupić (predsjednik povjerenstva)
• Committee member: Fran Jelenić (član povjerenstva)
• Committee member: Filip Karlo Došilović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2023-07-06, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Problem pakiranja spremnika je optimizacijski problem koji pripada problemima grupiranja. To su problemi gdje je cilj grupirati elemente nekog skupa. U ovom radu koristit ćemo grupirajući genetski algoritam. To je inačica genetskog algoritma čiji su operatori i način kodiranja prilagođeni problemima grupiranja. Pokazat ćemo hibridizirani pristup koji koristi različite heuristike i algoritme lokalne pretrage. Izvršit ćemo testiranja za oba pristupa. Skupovi podataka za testiranje dijele se na lakše i teže. Za svaku instancu problema poznato je optimalno rješenje. Rezultati pokazuju znatno bolje performanse za hibridizirani algoritam u odnosu na običan.

Abstract (english)

Bin packing problem is an optimization problem which belongs to the grouping problems. Those are the problems where the goal is to group the elements of a set. In this paper we will use the grouping genetic algorithm. Grouping genetic algorithm is a variant of genetic algorithms whose operators and encoding are designed specifically for grouping problems. We will also show the hybrid approach which uses various heuristics and local search algorithms. Finally, we will run tests for both approaches. Test sets are divided into easier and harder sets. For every test instance optimal solution is known. The results show much better performance for the hybrid approach.

• Keywords: problem pakiranja spremnika; grupirajući genetski algoritam; hibridizirani grupirajući genetski algoritam; lokalna pretraga; heuristike
• Keywords (english): bin packing problem; grouping genetic algorithm; hybrid grouping genetic algorithm; local search; heuristics
• Language: croatian
• URN:NBN: urn:nbn:hr:168:637495
• 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-10-11 09:34:37