The traveling salesman problem: a hierarchical model.

Area of Science:

• Cognitive Science
• Artificial Intelligence
• Operations Research

Background:

• Spatial information processing in perception, attention, and memory relies on hierarchical architectures.
• Hierarchical models offer a framework for understanding complex cognitive functions.

Purpose of the Study:

• To extend hierarchical models to problem-solving, specifically the Euclidean Traveling Salesman Problem (TSP).
• To compare human performance on the TSP with existing AI and operations research algorithms.
• To develop a new hierarchical algorithm that models human problem-solving behavior.

Main Methods:

• Human subjects solved Euclidean TSP instances with 6 to 30 cities.
• Subjective solution lengths and times were recorded.
• Performance was compared against five AI/OR algorithms for approximate TSP solutions.
• A novel hierarchical pyramid-based algorithm was developed for the TSP.

Main Results:

• Human subjects found optimal or near-optimal TSP solutions.
• Solution time scaled linearly with the number of cities.
• Existing AI/OR algorithms did not adequately model human psychological performance.
• The new hierarchical algorithm's performance closely matched human subject performance.

Conclusions:

• Hierarchical models are applicable to human problem-solving, including the TSP.
• Current AI/OR algorithms are insufficient as psychological models for TSP.
• A novel hierarchical algorithm effectively simulates human-like TSP solving strategies.