A note on the complexity of the picker routing problem in multi-block warehouses and related problems

Thibault Prunet; Nabil Absi; Diego Cattaruzza

doi:10.1007/s10479-025-06481-3

A note on the complexity of the picker routing problem in multi-block warehouses and related problems

Thibault Prunet
, Nabil Absi
, Diego Cattaruzza

Research output: Contribution to journal › Article › peer-review

Abstract

The Picker Routing Problem (PRP), which consists of finding a minimum-length tour between a set of storage locations in a warehouse, is one of the most important problems in the warehousing logistics literature. Despite its popularity, the tractability of the PRP in multi-block warehouses remains an open question. This technical note aims to fill this research gap by establishing that the problem is strongly NP-hard. As a corollary, the complexity status of other related problems is settled.

Original language	English
Article number	107564
Pages (from-to)	1595-1605
Number of pages	11
Journal	Annals of Operations Research
Volume	347
Issue number	3
DOIs	https://doi.org/10.1007/s10479-025-06481-3
Publication status	Published - 1 Apr 2025

Keywords

Complexity
Intractability
NP-hard
Order picking
Picker routing

Access to Document

10.1007/s10479-025-06481-3

Cite this

@article{0ce087ce6a434d1384be18e11183abd1,

title = "A note on the complexity of the picker routing problem in multi-block warehouses and related problems",

abstract = "The Picker Routing Problem (PRP), which consists of finding a minimum-length tour between a set of storage locations in a warehouse, is one of the most important problems in the warehousing logistics literature. Despite its popularity, the tractability of the PRP in multi-block warehouses remains an open question. This technical note aims to fill this research gap by establishing that the problem is strongly NP-hard. As a corollary, the complexity status of other related problems is settled.",

keywords = "Complexity, Intractability, NP-hard, Order picking, Picker routing",

author = "Thibault Prunet and Nabil Absi and Diego Cattaruzza",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2025.",

year = "2025",

month = apr,

day = "1",

doi = "10.1007/s10479-025-06481-3",

language = "English",

volume = "347",

pages = "1595--1605",

journal = "Annals of Operations Research",

issn = "0254-5330",

number = "3",

}

TY - JOUR

T1 - A note on the complexity of the picker routing problem in multi-block warehouses and related problems

AU - Prunet, Thibault

AU - Absi, Nabil

AU - Cattaruzza, Diego

N1 - Publisher Copyright: © The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2025.

PY - 2025/4/1

Y1 - 2025/4/1

N2 - The Picker Routing Problem (PRP), which consists of finding a minimum-length tour between a set of storage locations in a warehouse, is one of the most important problems in the warehousing logistics literature. Despite its popularity, the tractability of the PRP in multi-block warehouses remains an open question. This technical note aims to fill this research gap by establishing that the problem is strongly NP-hard. As a corollary, the complexity status of other related problems is settled.

AB - The Picker Routing Problem (PRP), which consists of finding a minimum-length tour between a set of storage locations in a warehouse, is one of the most important problems in the warehousing logistics literature. Despite its popularity, the tractability of the PRP in multi-block warehouses remains an open question. This technical note aims to fill this research gap by establishing that the problem is strongly NP-hard. As a corollary, the complexity status of other related problems is settled.

KW - Complexity

KW - Intractability

KW - NP-hard

KW - Order picking

KW - Picker routing

UR - https://www.scopus.com/pages/publications/85217427624

U2 - 10.1007/s10479-025-06481-3

DO - 10.1007/s10479-025-06481-3

M3 - Article

AN - SCOPUS:85217427624

SN - 0254-5330

VL - 347

SP - 1595

EP - 1605

JO - Annals of Operations Research

JF - Annals of Operations Research

IS - 3

M1 - 107564

ER -

A note on the complexity of the picker routing problem in multi-block warehouses and related problems

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this