Template-type: ReDif-Paper 1.0
Author-Name: Rajabighamchi, Farzaneh
Author-workplace-name: Data Analytics and Digitalisation, RS: GSBE other - not theme-related research
Author-Name: van Hoesel, Stan
Author-workplace-name: RS: GSBE other - not theme-related research, RS: FSE DACS Mathematics Centre Maastricht, QE Operations research
Author-Name: Defryn, Christof
Author-workplace-name: RS: GSBE other - not theme-related research, RS: FSE DACS Mathematics Centre Maastricht, QE Operations research
Title: Graph reduction for the planar Travelling Salesman Problem
Abstract: 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<br/>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.<br/>
Series: GSBE Research Memoranda
Creation-Date: 20230511
Number: 004
File-URL: https://cris.maastrichtuniversity.nl/ws/files/136145242/RM23004.pdf
File-Format: application/pdf
File-Size: 1886396
Handle: Repec:unm:umagsb:2023004
DOI: 10.26481/umagsb.2023004