Skip to Main content Skip to Navigation
Journal articles

An efficient and general approach for the joint order batching and picker routing problem

Olivier Briant 1 Hadrien Cambazard 2 Diego Cattaruzza 3 Nicolas Catusse 2 Anne-Laure Ladier 4 Maxime Ogier 3
1 G-SCOP_OC [2020-....] - Optimisation Combinatoire [2020-....]
G-SCOP [2020-....] - Laboratoire des sciences pour la conception, l'optimisation et la production [2020-....]
2 G-SCOP_ROSP [2020-....] - Recherche Opérationnelle pour les Systèmes de Production [2020-....]
G-SCOP [2020-....] - Laboratoire des sciences pour la conception, l'optimisation et la production [2020-....]
3 INOCS - Integrated Optimization with Complex Structure
ULB - Université libre de Bruxelles, Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : Order 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 routes 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. 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.
Complete list of metadatas

Cited literature [38 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-02078547
Contributor : Maxime Ogier <>
Submitted on : Monday, March 25, 2019 - 2:21:06 PM
Last modification on : Wednesday, September 16, 2020 - 11:26:02 AM
Long-term archiving on: : Wednesday, June 26, 2019 - 2:44:24 PM

File

2019_An efficient and general ...
Files produced by the author(s)

Identifiers

Citation

Olivier Briant, Hadrien Cambazard, Diego Cattaruzza, Nicolas Catusse, Anne-Laure Ladier, et al.. An efficient and general approach for the joint order batching and picker routing problem. European Journal of Operational Research, Elsevier, 2020, 285 (2), pp.497-512. ⟨10.1016/j.ejor.2020.01.059⟩. ⟨hal-02078547⟩

Share

Metrics

Record views

535

Files downloads

1015