Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Analysis of Computational Efficiency in Iterative Order Batching Optimization

Oxenstierna, Johan LU orcid ; Krueger, Volker LU orcid and Malec, Jacek LU orcid (2022) 11th International Conference on Operations Research and Enterprise Systems, ICORES 2022 p.345-353
Abstract
Order Picking in warehouses is often optimized with a method known as Order Batching, which means that
one vehicle can be assigned to pick a batch of several orders at a time. Although there exists a rich body of
research on Order Batching Problem (OBP) optimization, one area which demands more attention is that of
computational efficiency, especially for optimization scenarios where warehouses have unconventional
layouts and vehicle capacity configurations. Due to the NP-hard nature of the OBP, computational cost for
optimally solving large instances is often prohibitive. In this paper we compare the performance of two
approximate optimizers designed for maximum computational efficiency. The first optimizer, Single... (More)
Order Picking in warehouses is often optimized with a method known as Order Batching, which means that
one vehicle can be assigned to pick a batch of several orders at a time. Although there exists a rich body of
research on Order Batching Problem (OBP) optimization, one area which demands more attention is that of
computational efficiency, especially for optimization scenarios where warehouses have unconventional
layouts and vehicle capacity configurations. Due to the NP-hard nature of the OBP, computational cost for
optimally solving large instances is often prohibitive. In this paper we compare the performance of two
approximate optimizers designed for maximum computational efficiency. The first optimizer, Single Batch
Iterated (SBI), is based on a Seed Algorithm, and the second, Metropolis Batch Sampling (MBS), is based on
a Metropolis algorithm. Trade-offs in memory and CPU-usage and generalizability of both algorithms is
analysed and discussed. Existing benchmark datasets are used to evaluate the optimizers on various scenarios.
On smaller instances we find that both optimizers come within a few percentage points of optimality at
minimal CPU-time. For larger instances we find that solution improvement continues throughout the allotted
time but at a rate which is difficult to justify in many operational scenarios. SBI generally outperforms MBS
and this is mainly attributed to the large search space and the latter’s failure to efficiently cover it. The
relevance of the results within Industry 4.0 era warehouse operations is discussed. (Less)
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Proceedings of the 11th International Conference on Operations Research and Enterprise Systems
pages
345 - 353
publisher
SciTePress
conference name
11th International Conference on Operations Research and Enterprise Systems, ICORES 2022
conference location
Online
conference dates
2022-02-03 - 2022-02-05
external identifiers
  • scopus:85143078911
ISBN
978-989-758-548-7
DOI
10.5220/0010837700003117
project
RobotLab LTH
language
English
LU publication?
yes
id
e7f56838-ff8e-4bf8-884c-b8923a6d0fbb
date added to LUP
2022-09-21 02:22:51
date last changed
2025-04-04 14:23:49
@inproceedings{e7f56838-ff8e-4bf8-884c-b8923a6d0fbb,
  abstract     = {{Order Picking in warehouses is often optimized with a method known as Order Batching, which means that<br/>one vehicle can be assigned to pick a batch of several orders at a time. Although there exists a rich body of<br/>research on Order Batching Problem (OBP) optimization, one area which demands more attention is that of<br/>computational efficiency, especially for optimization scenarios where warehouses have unconventional<br/>layouts and vehicle capacity configurations. Due to the NP-hard nature of the OBP, computational cost for<br/>optimally solving large instances is often prohibitive. In this paper we compare the performance of two<br/>approximate optimizers designed for maximum computational efficiency. The first optimizer, Single Batch<br/>Iterated (SBI), is based on a Seed Algorithm, and the second, Metropolis Batch Sampling (MBS), is based on<br/>a Metropolis algorithm. Trade-offs in memory and CPU-usage and generalizability of both algorithms is<br/>analysed and discussed. Existing benchmark datasets are used to evaluate the optimizers on various scenarios.<br/>On smaller instances we find that both optimizers come within a few percentage points of optimality at<br/>minimal CPU-time. For larger instances we find that solution improvement continues throughout the allotted<br/>time but at a rate which is difficult to justify in many operational scenarios. SBI generally outperforms MBS<br/>and this is mainly attributed to the large search space and the latter’s failure to efficiently cover it. The<br/>relevance of the results within Industry 4.0 era warehouse operations is discussed.}},
  author       = {{Oxenstierna, Johan and Krueger, Volker and Malec, Jacek}},
  booktitle    = {{Proceedings of the 11th International Conference on Operations Research and Enterprise Systems}},
  isbn         = {{978-989-758-548-7}},
  language     = {{eng}},
  pages        = {{345--353}},
  publisher    = {{SciTePress}},
  title        = {{Analysis of Computational Efficiency in Iterative Order Batching Optimization}},
  url          = {{http://dx.doi.org/10.5220/0010837700003117}},
  doi          = {{10.5220/0010837700003117}},
  year         = {{2022}},
}