6533b7d5fe1ef96bd12652f1
RESEARCH PRODUCT
Using a TSP heuristic for routing order pickers in warehouses
Birger RaaChristophe TheysOlli BräysyWout DullaertWout Dullaertsubject
Mathematical optimizationOrder pickingInformation Systems and ManagementGeneral Computer ScienceEconomicsOrder pickingLogisticsManagement Science and Operations ResearchAisleSteiner tree problemTravelling salesman problemIndustrial and Manufacturing Engineeringsymbols.namesakeLocal search (optimization)WarehousingMathematicsRoutingComputer. AutomationHeuristicbusiness.industryModeling and SimulationsymbolsRouting (electronic design automation)HeuristicsbusinessMathematicsofComputing_DISCRETEMATHEMATICSorder picking routing warehousing logisticsdescription
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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2010-02-01 |