Exact optimization algorithms for an order picking problem

Abstract

We consider a combinatorial optimization problem arising when a set of pick-up and delivery orders must be satisfied within an Automated Storage/Retrieval System. The computational complexity of the problem is still open, but it is conjectured to be N P -hard. We point out some of its relevant properties and we describe three exact optimization algorithms to solve it, one based on dynamic programming and the other two on branch-and-bound. We also present a mixed-integer linear programming model to solve the problem by general purpose mathematical programming solvers. Computational results are provided to assess the effectiveness of these methods.