A survey on the Traveling Salesman Problem and its variants in a warehousing context
Stefan Bock, Stefan Bomsdorf, Nils Boysen, Michael Schneider
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 correpond 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.