Graph reduction for the planar Travelling Salesman Problem

This paper presents an improved exact algorithm for solving the order picking problem, a special case of the planar Travelling Salesperson Problem. The algorithm heavily relies on graph reduction techniques: it removes unnecessary vertices and edges from the planar graph that are not necessary in the optimal solution. As a result, we achieve a significant increase in calculation speed and reduction in the running time. The order pickers routing problem entails collecting items from storage in response to customer requests. We use the Traveling Salesperson Problem (TSP) to optimize the routes taken by order pickers. In the literature, exact algorithms — typically based on dynamic programming — only exist for small warehouses with a small number of blocks (two), while for larger warehouse layouts mainly heuristic and metaheuristic methods are provided. The presented graph reduction method allows us to adequately solve larger — more realistic — instances in a short amount of time. Our algorithm is tested on different problem instances from the literature and its performance is compared with the current state-of-the-art. We conclude that our algorithm outperforms existing algorithms in terms of simplicity, size and calculation time.