Acknowledging crossing-avoidance heuristic violations when solving the Euclidean travelling salesperson problem

If a salesperson aims to visit a number of cities only once before returning home, which route should they take to minimise the total distance/cost? This combinatorial optimization problem is called the travelling salesperson problem (TSP) and has a rapid growth in the number of possible solutions as the number of cities increases. Despite its complexity, when cities and routes are represented in 2D Euclidean space (ETSP), humans solve the problem with relative ease, by applying simple visual heuristics. One of the most important heuristics appears to be the avoidance of path crossings, which will always result in more optimal solutions than tours that contain crossings. This study systematically investigates whether the occurrence of crossings is impacted by geometric properties by modelling their relationship using binomial logistic regression as well as random forests. Results show that properties, such as the number of nodes making up the convex hull, the standard deviation of the angles between nodes, the average distance between all nodes in the graph, the total number of nodes in the graph, and the tour cost (i.e., a measure of performance), are significant predictors of whether crossings are likely to occur.