A column generation approach for the joint order batching and picker routing problem
Olivier Briant  1, *@  , Hadrien Cambazard  1, *@  , Diego Cattaruzza  2, *@  , Nicolas Catusse  1, *@  , Anne-Laure Ladier  3, *@  , Maxime Ogier  2, *@  
1 : Laboratoire des sciences pour la conception, lóptimisation et la production  (G-SCOP)  -  Website
Université Joseph Fourier - Grenoble 1, Institut Polytechnique de Grenoble - Grenoble Institute of Technology, Institut National Polytechnique de Grenoble, Centre National de la Recherche Scientifique : UMR5272, Université Grenoble Alpes
GSCOPLaboratoire des Sciences pour la Conception, lÓptimisation et la Production de GrenobleUMR 527246, avenue Félix Viallet - 38031 Grenoble Cedex 1 - France -  France
2 : Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189  (CRIStAL)  -  Website
Ecole Centrale de Lille, Institut National de Recherche en Informatique et en Automatique, Institut Mines-Télécom [Paris], Université de Lille, Centre National de la Recherche Scientifique : UMR9189
Bâtiment M3, Université Lille 1, 59655 Villeneuve dÁscq Cedex FRANCE -  France
3 : Décision et Information pour les Systèmes de Production
Institut National des Sciences Appliquées (INSA) - Lyon
* : Corresponding author

Picking is the process of retrieving products from inventory. It is mostly done manually by dedicated employees called pickers and is considered the most expensive of warehouse operations. To reduce the picking cost, customer orders can be grouped into batches that are then collected by traveling the shortest possible distance.

This work presents an exponential linear programming formulation to tackle the joint order batching and picker routing problem. Variables, or columns, are related to the picking routes in the warehouse. Computing such routess is generally an intractable routing problem and relates to the well known traveling salesman problem (TSP). Nonetheless, the rectangular warehouse's layouts can be used to efficiently solve the corresponding TSP and take into account in the development of an efficient subroutine, called oracle. We therefore investigate whether such an oracle allows for an effective exponential formulation. In order to tackle the exponential number of variables, we develop a column generation heuristic with performance guarantee. The pricing problem approximates the distances, and when finding a solution the oracle is used to get the optimal distance of this solution. The performance of the proposed column generation is strenghten using stabilization techniques and a rich column set.

Experimented on a publicly available benchmark, the algorithm proves to be very effective. It improves many of the best known solutions and provides very strong lower bounds. Finally, this approach is applied to another industrial case to demonstrate its interest for this field of application.

Online user: 1 RSS Feed