Using a TSP heuristic for routing order pickers in warehouses

Christophe Theys*, Olli Bräysy, Wout Dullaert, Birger Raa

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

In this paper, we deal with the sequencing and routing problem of order pickers in conventional multi-parallel-aisle warehouse systems. For this NP-hard Steiner travelling salesman problem (TSP), exact algorithms only exist for warehouses with at most three cross aisles, while for other warehouse types literature provides a selection of dedicated construction heuristics. We evaluate to what extent reformulating and solving the problem as a classical TSP leads to performance improvements compared to existing dedicated heuristics. We report average savings in route distance of up to 47% when using the LKH (Lin-Kernighan-Helsgaun) TSP heuristic. Additionally, we examine if combining problem-specific solution concepts from dedicated heuristics with high-quality local search features could be useful. Lastly, we verify whether the sophistication of 'state-of-the-art' local search heuristics is necessary for routing order pickers in warehouses, or whether a subset of features suffices to generate high-quality solutions.

Original languageEnglish
Pages (from-to)755-763
Number of pages9
JournalEuropean Journal of Operational Research
Volume200
Issue number3
DOIs
Publication statusPublished - 1 Feb 2010

Keywords

  • Logistics
  • Order picking
  • Routing
  • Warehousing

Fingerprint

Dive into the research topics of 'Using a TSP heuristic for routing order pickers in warehouses'. Together they form a unique fingerprint.

Cite this