Skip to main content
main-content
Top

Tip

Swipe om te navigeren naar een ander artikel

12-06-2017 | Original Article | Uitgave 5/2018

Psychological Research 5/2018

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

Tijdschrift:
Psychological Research > Uitgave 5/2018
Auteurs:
Markos Kyritsis, Stephen R. Gulliver, Eva Feredoes

Abstract

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.

Log in om toegang te krijgen

Met onderstaand(e) abonnement(en) heeft u direct toegang:

BSL Psychologie Totaal

Met BSL Psychologie Totaal blijft u als professional steeds op de hoogte van de nieuwste ontwikkelingen binnen uw vak. Met het online abonnement heeft u toegang tot een groot aantal boeken, protocollen, vaktijdschriften en e-learnings op het gebied van psychologie en psychiatrie. Zo kunt u op uw gemak en wanneer het u het beste uitkomt verdiepen in uw vakgebied.

Literatuur
Over dit artikel

Andere artikelen Uitgave 5/2018

Psychological Research 5/2018 Naar de uitgave