The article provides a review of recent research on human performance on the traveling salesman problem (TSP) and related combinatorial optimization problems. We discuss what combinatorial optimization problems are, why they are important, and why they may be of interest to cognitive scientists. We next describe the main characteristics of human performance on the TSP and related problems, and discuss the main theoretical explanations that have been offered. We then review some related developments in animal studies, spatial cognition, and neuropsychology. The article closes with a brief look at possible future directions.