Title
Using a TSP heuristic for routing order pickers in warehouses Using a TSP heuristic for routing order pickers in warehouses
Author
Faculty/Department
Institute for Transport en Maritime Management (ITMMA)
Publication type
article
Publication
Amsterdam ,
Subject
Economics
Computer. Automation
Source (journal)
European journal of operational research. - Amsterdam
Volume/pages
200(2010) :3 , p. 755-763
ISSN
0377-2217
ISI
000270701200013
Carrier
E
Target language
English (eng)
Full text (Publishers DOI)
Affiliation
University of Antwerp
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 (LinKernighanHelsgaun) 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.
E-info
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000270701200013&DestLinkType=RelatedRecords&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000270701200013&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000270701200013&DestLinkType=CitingArticles&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
Handle