Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2009.01.036 Byline: Christophe Theys (a), Olli Braysy (b), Wout Dullaert (a)(c), Birger Raa (d) Keywords: Routing; Order picking; Warehousing; Logistics Abstract: 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. Author Affiliation: (a) Institute of Transport and Maritime Management Antwerp (ITMMA), University of Antwerp, Keizerstraat 64, 2000 Antwerp, Belgium (b) Agora Innoroad Laboratory, University of Jyvaskyla, Agora Center, P.O. Box 35, FI-40014, Finland (c) Antwerp Maritime Academy, Noordkasteel Oost 6, 2030 Antwerp, Belgium (d) Department of Management Information and Operations Management, Ghent University, Tweekerkenstraat 2, 9000 Gent, Belgium Article History: Received 20 August 2007