TY - JOUR
T1 - Using a TSP heuristic for routing order pickers in warehouses
AU - Theys, Christophe
AU - Bräysy, Olli
AU - Dullaert, Wout
AU - Raa, Birger
PY - 2010/2/1
Y1 - 2010/2/1
N2 - 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.
AB - 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.
KW - Logistics
KW - Order picking
KW - Routing
KW - Warehousing
UR - http://www.scopus.com/inward/record.url?scp=69749126279&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=69749126279&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2009.01.036
DO - 10.1016/j.ejor.2009.01.036
M3 - Article
AN - SCOPUS:69749126279
SN - 0377-2217
VL - 200
SP - 755
EP - 763
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 3
ER -