A column generation approach to solve the Joint Order Batching and Picker Routing Problem including picker congestion

Torrealba-González, Pablo; Feillet, Dominique; Ogier, Maxime; Semet, Frédéric

Type de document :

Autre communication scientifique (congrès sans actes - poster - séminaire...): Communication dans un congrès avec actes

Titre :

A column generation approach to solve the Joint Order Batching and Picker Routing Problem including picker congestion

Auteur(s) :

Torrealba-González, Pablo [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Feillet, Dominique [Auteur]
École des Mines de Saint-Étienne [Mines Saint-Étienne MSE]
Ogier, Maxime [Auteur]

Integrated Optimization with Complex Structure [INOCS]
Semet, Frédéric [Auteur]

Integrated Optimization with Complex Structure [INOCS]

Titre de la manifestation scientifique :

The 23rd Conference of the International Federation of Operational Research Societies

Ville :

Santiago (Chile)

Pays :

Chili

Date de début de la manifestation scientifique :

2023-07-10

Discipline(s) HAL :

Computer Science [cs]/Operations Research [math.OC]

Résumé en anglais : [en]

Order picking is a crucial process in warehouse operations; in a human-operated warehouse, pickers prepare different customer orders. From a managerial perspective, two major decisions need to be made: (i) grouping orders ...
Lire la suite >Order picking is a crucial process in warehouse operations; in a human-operated warehouse, pickers prepare different customer orders. From a managerial perspective, two major decisions need to be made: (i) grouping orders to be collected together by a picker, and (ii) for each picker, determining the route to retrieve the needed items. The Joint Order Batching and Picker Routing Problem (JOBPRP) integrates both decisions into a single problem, usually minimizing either total distance or time. In the literature, the JOBPRP usually assumes a situation without any congestion caused by the pickers, however - unrealistic when there are many pickers in a warehouse. In practice, congestion causes inefficiency, increases costs, reduces performance, and leads to accidents; it occurs when multiple pickers use the same space simultaneously, resulting in a delay in normal picker operations. To estimate congestion levels, we divide the planning horizon of the picking activity into different time intervals and timing variables are introduced. If two or more pickers are in the same sub-aisle during the same time interval, a delay in travel time is imposed. The delay is determined by an increasing function, depending on the number of pickers. Because picking activities are performed by humans, practical considerations must be taken into account when defining a feasible picking route, e.g. a picker cannot unnecessarily wait and cannot follow complicated or long paths between two consecutive picking positions. To solve the JOBPRP, including the effect of picker congestion, an extended mathematical formulation is presented, with the main objective of minimizing the total time, including delay. A heuristic solving approach is proposed based on solving of the linear relaxation of the formulation by an exact column generation procedure. In each iteration, a negative reduced column is produced using a dedicated labelling algorithm, exploring routes associated to congestion level for each sub-aisle and time interval. When the linear relaxation is solved, variables are defined as binaries to provide a feasible solution for the problem. To evaluate the modelling and the performance of the solutions provided by the proposed approach, a discrete event simulation tool is developed. Several experiments are performed to compare the results with optimal JOBPRP solutions not considering congestion.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Projet ANR :

Aide à la Gestion Intelligente des Ressources dans les Entrepôts

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

A column generation approach to solve the ... BibTeX CSV Excel RIS

A column generation approach to solve the ...

BibTeX

CSV

Excel

RIS