A survey on the Traveling Salesman Problem and its variants in a warehousing context

Stefan Bock, Stefan Bomsdorf, Nils Boysen and Michael Schneider

European Journal of Operational Research, 2025, vol. 322, issue 1, 1-14

Abstract: With the advent of e-commerce and its fast-delivery expectations, efficiently routing pickers in warehouses and distribution centers has received renewed interest. The processes and the resulting routing problems in this environment are diverse. For instance, not only human pickers have to be routed but also autonomous picking robots or mobile robots that accompany human pickers. Traditional picker routing, in which a single picker has to visit a given set of picking positions in a picker-to-parts process, can be modeled as the classical Traveling Salesman Problem (TSP). The more involved processes of e-commerce fulfillment, however, require solving more complex TSP variants, such as the clustered, generalized, or prize-collecting TSP. In this context, our paper provides two main contributions: We systematically survey the large number of TSP variants that are known in the routing literature and check whether meaningful applications in warehouses exist that correspond to the respective TSP variant. If they do, we survey the existing research and investigate the computational complexity of the TSP variant in the warehousing context. Previous research has shown that the classical TSP is efficiently solvable in the parallel-aisle structure of warehouses. Consequently, some TSP variants also turn out to be efficiently solvable in the warehousing context, whereas others remain NP-hard. We survey existing complexity results, provide new ones, and identify future research needs.

Keywords: Routing; Warehousing; Traveling Salesman Problem; Complexity (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724002959
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:322:y:2025:i:1:p:1-14

DOI: 10.1016/j.ejor.2024.04.014

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().