Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Efficient Order Batching Optimization Using Seed Heuristics and the Metropolis Algorithm

Oxenstierna, Johan LU orcid ; Malec, Jacek LU orcid and Krueger, Volker LU orcid (2023) In SN Computer Science 4(2).
Abstract

Order Picking in warehouses is often optimized using a method known as Order Batching, which means that one vehicle can be assigned to pick a batch of several orders at a time. There exists a rich body of research on Order Batching Problem (OBP) optimization, but one area which demands more attention is 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... (More)

Order Picking in warehouses is often optimized using a method known as Order Batching, which means that one vehicle can be assigned to pick a batch of several orders at a time. There exists a rich body of research on Order Batching Problem (OBP) optimization, but one area which demands more attention is 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 analyzed 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
Contribution to journal
publication status
published
subject
keywords
Computational efficiency, Metropolis algorithm, Order Batching Problem, Order picking, Seed algorithm, Warehousing
in
SN Computer Science
volume
4
issue
2
article number
107
publisher
Springer Nature
external identifiers
  • scopus:85144205820
ISSN
2662-995X
DOI
10.1007/s42979-022-01496-0
project
RobotLab LTH
language
English
LU publication?
yes
id
a466faad-dd3e-41f6-8e65-fa62b17cc5aa
date added to LUP
2023-02-01 15:27:17
date last changed
2023-11-20 05:49:18
@article{a466faad-dd3e-41f6-8e65-fa62b17cc5aa,
  abstract     = {{<p>Order Picking in warehouses is often optimized using a method known as Order Batching, which means that one vehicle can be assigned to pick a batch of several orders at a time. There exists a rich body of research on Order Batching Problem (OBP) optimization, but one area which demands more attention is 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 analyzed 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.</p>}},
  author       = {{Oxenstierna, Johan and Malec, Jacek and Krueger, Volker}},
  issn         = {{2662-995X}},
  keywords     = {{Computational efficiency; Metropolis algorithm; Order Batching Problem; Order picking; Seed algorithm; Warehousing}},
  language     = {{eng}},
  number       = {{2}},
  publisher    = {{Springer Nature}},
  series       = {{SN Computer Science}},
  title        = {{Efficient Order Batching Optimization Using Seed Heuristics and the Metropolis Algorithm}},
  url          = {{http://dx.doi.org/10.1007/s42979-022-01496-0}},
  doi          = {{10.1007/s42979-022-01496-0}},
  volume       = {{4}},
  year         = {{2023}},
}