Non-Euclidean Traveling Salesman Problem

John Saalweachter () and Zygmunt Pizlo ()
Additional contact information
John Saalweachter: Purdue University
Zygmunt Pizlo: Purdue University

A chapter in Decision Modeling and Behavior in Complex and Uncertain Environments, 2008, pp 339-358 from Springer

Abstract: The traveling salesman problem (TSP) is usually studied on a Euclidean plane. When obstacles are placed on the plane, the distances are no longer Euclidean, but they still satisfy the metric axioms. Three experiments are reported in which subjects were tested on the TSP and on the shortest-path problem with obstacles. When the obstacles were simple, and they did not change the global structure of the problem, the subjects were able to produce near-optimal solutions, but the complexity of the mental mechanisms was higher than in the case of the Euclidean TSP. When obstacles were complex and changed the problem's global structure, the solutions were no longer near-optimal. Several computational models are proposed that can account for the psychophysical results.

Keywords: Short Path; Travel Salesman Problem; Travel Salesman Problem; Visibility Graph; Visual Noise (search for similar items in EconPapers)
Date: 2008
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-0-387-77131-1_14

Ordering information: This item can be ordered from
http://www.springer.com/9780387771311

DOI: 10.1007/978-0-387-77131-1_14

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().