prip logo

Graph Pyramid Solution of Travelling Salesman Problem

Traveling salesperson problem (TSP) is a combinatorial optimization task of finding the shortest tour of n cities given the intercity costs. When the costs between cities are Euclidean distances, the problem is called Euclidean TSP (E-TSP). TSP as well as E-TSP belongs to the class of difficult optimization problems called NP-hard and NP-complete if posed as a decision problem [1]. The straightforward approach by using brute force search would be using all possible permutations for finding the shortest tour. It is impractical for large n since the number of permutations is (n-1)!/2.

Because of the computational intractability of TSP, researchers concentrated their efforts on finding approximating algorithms. Good approximating algorithms can produce solutions that are only a few percent longer than an optimal solution and the time of solving the problem is a low-order polynomial function of the number of cities [2, 3, 4]. The last few percent to reach optimality are computationally the most expensive to achieve.

It is by now well established that humans produce close-to-optimal solutions to E-TSP problems in time that is (on average) proportional to the number of cities [5, 6, 7]. This level of performance can not be reproduced by any of the standard approximating algorithms. Some approximating algorithms produce smaller errors but the time complexity is substantially higher than linear, other algorithms are relatively fast but produce substantially higher errors. It is therefore of interest to identify the computational mechanism used by the human brain.

A simple way to present E-TSP to a subject is to show n cities as points on a computer screen and ask the subject to produce a tour by clicking on the points. In the Figure 1 (a), an E-TSP example of 10 cities is shown; in (b) the solution given by a human, and in (c) by the optimal solver. The tours produced by the subjects are, on average, only a few percent longer than the shortest tours (in the Figure 1 (b) the cross depicts the starting position and the arrow the orientation used by the subject). The solution time is a linear function of the number of cities [5, 6]. Two attempts to emulate human performance by a computational model were undertaken in [5, 6]. In [5], authors attempt to formulate a new approximating algorithm for E-TSP motivated by the failure to identify an existing algorithm that could provide a good fit to the subjects' data. The main aspects of the models in [5, 7, 13] are its
  1. (multiresolution) pyramid architecture, and
  2. a coarse to fine process of successive tour approximations.

Figure 1. E-TSP and solutions given by human (b) and optimal solver (c)
tsp tsp tsp
10 city problem

They showed that performance of this model (proportion of optimal solutions and average solution error) is statistically equivalent to human performance. Pyramid algorithms have been used extensively in both computer and human vision literature (e.g. [8]), but not in problem solving. The work of [5, 9] was the first attempt to use pyramid algorithms to solve the E-TSP. One of the most attractive aspects of pyramid algorithms, which make them suitable for problems such as early vision or E-TSP, is that they allow to solve (approximately) global optimization tasks without performing a global search. A similar pyramid algorithm for producing approximate E-TSP solutions with emphasis on trade-off between computational complexity (speed) and error in the solution (accuracy) and not on modeling human performance is formulated in [4, Chapter 5], and [10].

Approximating TSP by MST based Graph Pyramid
The Model

In the graph pyramid framework, the TSP input is represented by graphs where cities are represented by vertices, and the intercity neighborhoods by edges. Each vertex of the constructed input graph must have at least two edges for the TSP tour to exist. A level (k) of the graph pyramid consists of a graph Gk. Moreover the graph is attributed, G=(C,N,wv,we), where we:N→ R+ is a weighted function defined on edges N. The weights we are Euclidean distances in the E-TSP and wv:C → R+ is a weighted function defined on cities C. I.e. each vertex (city) has as a weight its position in the Cartesian coordinate system. Finally, the sequence Gk, 0 < k < h is called irregular graph pyramid.

Let G0=(C,N,wv,we) be the input graph, with weights on edges given as distances in L2 space. The goal of the TSP is to find an nonempty ordered sequence of vertices and edges (v0,e1,v1,...,vk-1,ek,vk,...,v0) over all vertices of G0 such that all the edges and vertices are distinct, except the start and the end vertex v0. This tour is called the optimal tour topt and the sum of edge weights in this tour is minimal, i.e.
topt =
e∈ t 
we min
where we is the weight of edge e.

We use local to global and global to local processes in the graph pyramid to find a good solution t*, approximating the E-TSP. The main idea is to use:
  • bottom-up processes to reduce the size of the input, and
  • top-down refinement to find an (approximate) solution.
The size of the input (number of vertices in the graph) is reduced such that an optimal (trivial) solution can be found by the combinatorial search, e.g. for a 3 city instance (not all cities are co-linear) there is only one solution, not needing any search, and this is the optimal one. For a 4 city input (not all co-linear) there are three solutions from which two are non-optimal since they cross edges. A pyramid is used to reduce the size of the input in the bottom-up process. The (trivial) solution is then found at the top of the pyramid and refined in a process emulating fovea by humans using lower levels of this pyramid, i.e. the vertical neighborhoods (parent-children relations) are used in this process to refine the tour. The final, in general non-optimal, solution is found when all the cities at the base level of the pyramid are in the tour. The steps needed to find the E-TSP solution are shown below.

Approximating E-TSP Solution by an MST Graph Pyramid
Input: Attributed graph G0=(C,N,wv,we), and parameters r and s
  1. partition the input space by preserving approximate location:
    create graph G0
  2. reduce number of cities bottom-up until the graph contains s vertices:
    build graph pyramid Gk, k=0,...,h, where s=|Gh|, and such that a father can have maximum of r childrens
  3. find the optimal tour ta for the graph Gh
  4. refine solution top-down until all vertices at the base level are processed:
    refine ta until level 0 is reached
Output: Approximate TSP solution t*.
The main idea in step (b) is that cities being close neighbors are put into a cluster and considered as a single city at reduced resolution. By doing this recursively one produces a pyramid representation of the problem. It is well known that the human visual system represent images on multiple level of scales and resolution [11,12]. In Figure 2. this step is illustrated for two levels of the pyramid.
Figure 2. Building the graph pyramid and finding the first TSP tour approximation.
(a) Bottom-up reduction of resolution (b) Initial tour ta
Bottom-up Trivial Solution
r=4 and s=3

The main idea in step (d) is using the tour ta found at level h of the graph pyramid as the first approximation of the TSP tour t*. This tour is then refined using the pyramid structure already built. The refinement process starts by choosing (randomly) a vertex v in the tour ta. Using the parent-child relationship, this vertex is expanded into the subgraph G'h-1. In this subgraph a path between vertices (children) is found that makes the overall path t'a the shortest one (see Figure 3. a). Since the number of children from a father in G'h cannot be larger than r, a complete search is a plausible approach to find the path with the smallest contribution in the overall length of the tour t'a.
Figure 3. Building the graph pyramid and finding the first TSP tour approximation.
(a) Top-down refinement of ta in t'a (b) The flow of processing
Top down Flow

For more details consult reference [14].

  1. Local Search in Combinatorial Optimization.
    Johnson, D.S., McGeoch, L.A.
    In: The Traveling Salesman Problem: A Case Study in Local Optimization. John Wiley and Sons (1997) 215--310

  2. Graph Theory - An Algorithmic Approach.
    Christofides, N.
    Academic Press, New York, London, San Francisco (1975)

  3. The Traveling Salesman Problem.
    Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.
    Wiley, New York (1985)

  4. The traveling salesman problem and its variations.
    Gutin, G., Punnen, A.P.
    Kluwer (2002)

  5. The travelling salesman problem: A hierarchical model.
    Graham, S.M., Joshi, A., Pizlo, Z.
    Memory and Cognition 28 (2000) 1191--1204

  6. A model of human performance on the traveling salesperson problem.
    MacGregor, J.N., Ormerod, T.C., Chronicle, E.P.
    Memory and Cognition 28 (2000) 1183--1190

  7. Pyramid algorithms as models of human cognition.
    Pizlo, Z., Li, Z.
    In: Proceedings of SPIE-IS&T Electronic Imaging, Computational Imaging, SPIE (2003) 1--12

  8. A Pyramid Framework for Early Vision.
    Jolion, J.M., Rosenfeld, A.
    Kluwer (1994)

  9. Problem solving in human beings and computers.
    Pizlo, Z., Joshi, A., Graham, S.M.
    Technical Report CSD TR 94-075, Department of Computer Sciences, Purdue University (1994)

  10. Polynomial-time approximation schemes for euclidean tsp and other geometric problems.
    Arora, S.
    Journal of the Association for Computing Machinery 45 (1998) 753--782

  11. Scanning from coarse to fine spatial scales in the human visual system after the onset of a stimulus.
    Watt, R.J.
    Journal of the Optical Society of America 4 (1987) 2006-2021

  12. An exponential pyramid model of the time-course of size processing.
    Pizlo, Z., Rosenfeld, A., Epelboim, J.
    Vision Research 35 (1995) 1089-1107

  13. Traveling Salesman Problem: a Foveating Pyramid Model.
    Z. Pizlo, E. Stefanov, J. Saalweachter, Z. Li, Y. Haxhimusa and W. G. Kropatsch
    Journal of Problem Solving, 1(1):83--101, October 2006. Purdue University Press. [paper]

Pyramid Solution of Travelling Salesman Problem (TSP)

This tool allows to solve the Traveling Salesman problem in a coarse to fine strategy.

  1. Approximating TSP by MST based Graph Pyramid.
    Y. Haxhimusa, W. G. Kropatsch, Z. Pizlo, A. Ion, and A. Lehrbaum.
    In the International Graph-based Representation for Pattern Recognition Workshop, June 2007, Alicante, Spain. [paper]

  2. MST based Pyramid Model of TSP.
    W. G. Kropatsch, Y. Haxhimusa, and Z. Pizlo.
    In the 39th Annual Meeting of Mathematical Psychology , August 2006, Vancouver, Canada. [abstract] [paper]

Tool to work with Usage notice

MST Pyramid Solution of Travelling Salesman Problem - Demo

A demostration of the minimum spanning tree solution strategy in solving the travelling salesman problem.

Start the demostration or Start the application. In order for the program to start you need to install Java Web Start, if the application does not start please read me.

Usage notice

© 2001-2012. Yll Haxhimusa. Last modified: May 05, 2007. Best viewed with Mozilla. Valid HTML 4.01 Transitional Valid CSS!