Graph reduction for the planar Travelling Salesman Problem

Farzaneh Rajabighamchi, Stan van Hoesel and Christof Defryn
Additional contact information
Farzaneh Rajabighamchi: Data Analytics and Digitalisation, RS: GSBE other - not theme-related research
Stan van Hoesel: RS: GSBE other - not theme-related research, RS: FSE DACS Mathematics Centre Maastricht, QE Operations research
Christof Defryn: RS: GSBE other - not theme-related research, RS: FSE DACS Mathematics Centre Maastricht, QE Operations research

No 4, Research Memorandum from Maastricht University, Graduate School of Business and Economics (GSBE)

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 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.

Date: 2023-05-11
New Economics Papers: this item is included in nep-des
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://cris.maastrichtuniversity.nl/ws/files/136145242/RM23004.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:unm:umagsb:2023004

DOI: 10.26481/umagsb.2023004

Access Statistics for this paper

More papers in Research Memorandum from Maastricht University, Graduate School of Business and Economics (GSBE) Contact information at EDIRC.
Bibliographic data for series maintained by Andrea Willems () and Leonne Portz ().