Solving the TSP for warehouses
As E-commerce becomes more prevalent, most of us make our purchases online instead of shopping in person. Pickers are responsible for gathering our orders from various parts of the warehouse. They spend up to 60% of the time walking from one product to the next.
Picker routing is an example of the Travelling Salesman Problem. Although the TSP is hard to solve in general, in the case of moving around a warehouse, we can exploit the restricted movement to develop efficient algorithms. This talk will cover recent advances in solving the TSP for such cases.
Presented at Friday Hacks #162, 26th October 2018b
- Christofides algorithm
- A (Slightly) Improved Approximation Algorithm for Metric TSP