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

Area of Science:

• Computational mathematics
• Operations research
• Human-computer interaction

Background:

• The travelling salesperson problem (TSP) is a combinatorial optimization challenge.
• The Euclidean TSP (ETSP) variant involves cities in 2D space.
• Humans often use visual heuristics, like avoiding path crossings, to solve ETSP efficiently.

Purpose of the Study:

• To investigate the geometric factors influencing path crossings in ETSP solutions.
• To model the relationship between geometric properties and the occurrence of path crossings.

Main Methods:

• Binomial logistic regression modeling.
• Random forest analysis.
• Systematic investigation of geometric properties and their impact on crossings.

Main Results:

• Several geometric properties significantly predict the likelihood of path crossings.
• Predictors include convex hull size, angular deviation, average inter-node distance, and total nodes.
• Tour cost, a performance measure, also predicts crossing occurrence.

Conclusions:

• Geometric properties are key determinants of path crossing occurrence in ETSP.
• Understanding these predictors can enhance algorithms for solving the travelling salesperson problem.
• Visual heuristics, particularly crossing avoidance, are effective for ETSP optimization.