Master's Thesis presentation, Joseph Löfving

Abstract: With the rise of online shopping, the demand for fast and reliable warehousing operations has grown, and with it, the desire for optimizing warehouse operations. One possible measure is optimized batching, i.e., the partitioning of a set of items waiting to be picked into subsets (batches), such that the sum of the distance walked for each batch is minimized. In this project, the batching problem is solved through column generation, an efficient method for solving linear optimization problems with an enormous number of possible variables (which, in this case, represent possible batches), in which only a small set of variables are initially considered, and this set being expanded iteratively. The iterative generation of new variables is done by solving a subproblem, which in the case of the batching problem corresponds to a version of the computationally intensive prize-collecting travelling salesperson problem. Exact solutions to the subproblem are necessary to verify that the column generation has achieved optimality, and to obtain lower bounds on the problem before optimality is reached, which is useful as an early termination criteria. To solve this computationally intensive subproblem exactly, a novel algorithm is developed. The algorithm uses a dynamical programming approach with a heuristic guide, and exploits the simple and predictable geometry of warehouses to obtain exact solutions in a matter of milliseconds, even when the number of products grows large and the subproblem is further restricted by additional batch constraints imposed by the branch-and-price search tree of the column generation.

Supervisor: Ann-Brith Strömberg