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

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.

• Publication year

  2023

• Venue

  Annals of Operations Research

• Publication date

  2023-12-04

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s10479-025-06481-3arXiv 2312.01857
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Storage Location Assignment and Picker Routing Problem: A Generic Branch-Cut-and-Price Algorithm

  2024cited by this paper
• The single picker routing problem with scattered storage: modeling and evaluation of routing and storage policies

  2024cited by this paper
• Routing Replenishment Workers: The Prize Collecting Traveling Salesman Problem in Scattered Storage Warehouses

  2023cited by this paper
• A note on the linearity of Ratliff and Rosenthal's algorithm for optimal picker routing

  2022cited by this paper
• A method for efficiently routing order pickers in the leaf warehouse

  2021cited by this paper
• Inventory routing in a warehouse: The storage replenishment routing problem

  2021cited by this paper
• Order picker routing in warehouses: A systematic literature review

  2020cited by this paper
• An efficient and general approach for the joint order batching and picker routing problem

  2020cited by this paper
• Optimal order picker routing in the chevron warehouse

  2019cited by this paper
• Optimal Picking Policies in E-Commerce Warehouses

  2019cited by this paper
• Order picking in parallel-aisle warehouses with multiple blocks: complexity and a graph theory-based heuristic

  2018influential reference
• Picker routing in rectangular mixed shelves warehouses

  2018cited by this paper
• Exact algorithms for the order picking problem

  2017cited by this paper
• Designing efficient order picking systems by combining planning problems: State-of-the-art classification and review

  2017cited by this paper
• Computers And Intractability A Guide To The Theory Of Np Completeness

  2016cited by this paper
• A new mathematical programming formulation for the Single-Picker Routing Problem

  2016cited by this paper
• Fixed-Parameter Algorithms for Rectilinear Steiner tree and Rectilinear Traveling Salesman Problem in the plane

  2015cited by this paper
• Order picking under random and turnover-based storage policies in fishbone aisle warehouses

  2014cited by this paper
• Optimal unit-load warehouse designs for single-command operations

  2012cited by this paper
• Research on warehouse operation: A comprehensive review

  2007cited by this paper
• Design and control of warehouse order picking: A literature review

  2006cited by this paper
• Order batching to minimize total travel time in a parallel-aisle warehouse

  2005cited by this paper
• Routing order pickers in a warehouse with a middle aisle

  2001cited by this paper
• Order-Picking in a Rectangular Warehouse: A Solvable Case of the Traveling Salesman Problem

  1983cited by this paper
• Hamilton Paths in Grid Graphs

  1982influential reference
• Reducibility Among Combinatorial Problems

  1972cited by this paper
• Shortest connection networks and some generalizations

  1957cited by this paper

• Picker Routing and Batching in Multi-Block Parallel-Aisle Warehouses: An Application from the Logistics Service Provider

  2025cites this paper
• Do non-traditional aisle designs outperform traditional ones? A comparative study for order picking warehouses

  2025cites this paper
• The Storage Location Assignment and Picker Routing Problem: A Generic Branch-Cut-and-Price Algorithm

  2024cites this paper