Simplified Shelf Problem as a Binary Linear Integer Programming Problem
Loading...
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Author
Date
2022-06-13
Department
Major/Subject
Tietotekniikka (Macadamia)
Mcode
SCI3042
Degree programme
Master’s Programme in Computer, Communication and Information Sciences
Language
en
Pages
76
Series
Abstract
A planogram is a visual representation of a merchandising plan for the display of the available products in a store. Having the ability to create the most optimal planogram, based on some predefined criterion, can cut the costs generated by the manual labour related to the unpacking and placement of goods. One possible method that can be utilised for placing products into a fixture is a heuristic approach called simulated annealing. This technique does not necessarily yield true optimal results without verifying every combination, requiring vast computational efforts. Thus, some alternative solving method is required in order to provide a better planogram layout in a shorter time period. One such method utilised in this work, is called linear programming. Linear programming is a mathematical modeling technique that is able to generate an optimal solution for a linear objective function subjected to various constraints, given that all are represented with linear relationships. Usually, this approach requires polynomial computational complexity, meaning that it could generate a global optimum faster than a heuristic approach. With the use of linear programming the presented problems could be formulated in such a way, that either an optimal result or one greater compared to the heuristic approach could be obtained in considerably less time. Many various models were tested, and it was deduced that presenting the problems with solely binary variables (utilising binary linear programming) was computationally too exhaustive and was not a feasible way of solving the most complex of problems. Since planograms contain such a large number of possible configurations for product placements, an iterative algorithm was designed, relaxing the initial restrictions, which could yield up to a $30\%$ result increase up to $70$ times more efficiently compared to the simulated annealing approach. Though the achieved results were not necessarily optimal, a considerable improvement was achieved, which could provide a competitive edge for any supply chain company taking it into use.Description
Supervisor
Pollari-Malmi, KerttuThesis advisor
Viitanen, TuomasKeywords
simplex, optimisation, planogram, linear programming
