Retour à la vue des calendrier
Jeudi 2 Juin
Heure: 11:45 - 12:30
Lieu: Visio - https://bbb.lipn.univ-paris13.fr/b/wol-ma9-vjn -code 514019
Résumé: On two two-level problems for operational warehouse planning in person-to-parts order picking systems
Description: Stefan Irnich We present a new modeling and solution approach for two-level problems in warehousing where one level concerns picking operations in a manual picker-to-parts warehouse. In particular, we consider the single picker routing problem with scattered storage (SPRP-SS) and the joint order batching and picker routing problem (JOBPRP). The SPRP-SS assumes that an article is, in general, stored at more than one pick position. The task is then the simultaneous selection of pick positions for requested articles and the determination of a minimum-length picker tour collecting the articles. In the JOBPRP, a set of orders is given, each with one or several order lines requesting a number of articles. The problem is here to group the given orders into capacity-feasible batches so that the total length of the picker tours collecting the respective articles is minimized. It is a classical result of Ratliff and Rosenthal that, for given pick positions, an optimal picker tour is a shortest path in the state space of a dynamic program with a linear number of states and transitions. We extend the state space of Ratliff and Rosenthal so that every feasible picker tour is still a path. Furthermore, the additional requirement to make consistent selections and grouping decisions can be modeled as additional constraints in shortest-path problems. We propose to solve these problems with a MIP solver. We will explain why this approach is not only convenient and elegant but also generic: it covers optimal solutions to integrated problems that use heuristic routing policies for the picker tours, consider different warehouse layouts, and incorporate further extensions. Computational experiments with a direct MIP solver-based approach for the SPRP-SS and a branch-price-and-cut algorithm for the JOBPRP show that the new modeling and solution approach outperforms the available exact algorithms. The latter computes hundreds of new best and provably optimal solutions to open instances of three JOBPRP benchmark sets. (joint work with Katrin Heßler)