Product Location that Optimizes Collection Tours in a Simply Structured Warehouse

Potential supervisors: 

Minimizing operation times in warehouses is an active research direction of large practical relevance, however, this project aims at a piece of progress in the theory of such problems. The basic question is: How shall we store items in shelves, placed along one line, so as to minimize the average time needed to pick up and collect requested items (assuming known frequencies of typical requests from "historical" data)? The full problem is NP-hard, but here we consider only a special case: Every request consist of only one fixed item and an optional supplement. This case leads to the weighted bipartite matching problem, where the weights are not arbitrary but somewhat "structured". The work will begin with some literature study about related problems, followed by the design of an efficient algorithm (or heuristics) for the problem in question. Depending on the results, there may remain time for extending the study to somewhat more complicated cases.

Preferably two students should work on the project, but it could also be suitable for a single student with high research ambitions. You should be very good in Algorithms design and analysis. Having passed the Advanced Algorithms course would be an asset.

Date range: 
October, 2021 to October, 2024