Quotient Algorithm: A Simple Human-Inspired Heuristic for Addressing the Travelling Salesperson Problem
Markos Kyritsis, Shahab Ud Din, Stephen R. Gulliver · 2018
The Travelling Salesperson Problem (TSP) is a classic example of a non-polynomial (NP) hard problem, which cannot be practically solved using exhaustive algorithmic approaches. This study explores the human approach, and presents a Quotient Algorithm (Quot) - a modification to the nearest neighbor algorithm-inspired by human path crossing avoidance behavior when solving graphs presented in 2D Euclidean space. We compared the developed Quot results against standard heuristic algorithms and found that this simple modification outperforms other existing heuristic approaches.