TSP Flaming – Quickly finds a solution of the Travelling Salesman Problem

Sponsored Link
TSP Flaming quickly finds a good solution of the Travelling Salesman Problem using the method of Simulated Annealing.
Problem Statement

Given a map with cities locations, what is the least-cost round-trip route that visits each city exactly once and then returns to the starting city?


Size of solution space is n!, where n is number of cities. The most direct solution rapidly becomes impractical.

Simulated Annealing

Instead of using exhaustive enumeration a generic probabilistic meta-algorithm is used. In fixed amount of time it finds a good approximation to the global optimum in a large search space.

Install TSP Flaming in Ubuntu

Download .deb package from here .Install this .deb package by double clicking on it or run the following command from your terminal

sudo dpkg -i tspflaming_1.2-0~ppa1_i386.deb


Sponsored Link

You may also like...

5 Responses

  1. jordanwb says:

    What am I looking at?

  2. SquishyOctopus says:

    This is quite the confusing post.

  3. TerryG says:

    TSP is a great problem to solve and it would be good to see this generalised to 3D TSP at some point but..I can’t get this to install. I have an up to date
    Ubuntu 9.10 (karmic) Kernel Linux 2.6.31-21-generic-pae GNOME 2.28.1 and the latest qt4 libraries that the Synaptic Package Manager will provide but still get installation errors…

    dpkg: dependency problems prevent configuration of tspflaming:

    tspflaming depends on libqtcore4 (>= 4:4.6.1); however:

    Version of libqtcore4 on system is 4.5.3really4.5.2-0ubuntu1.

    tspflaming depends on libqtgui4 (>= 4:4.5.3); however:

    Version of libqtgui4 on system is 4.5.3really4.5.2-0ubuntu1.

    dpkg: error processing tspflaming (–install):

    dependency problems – leaving unconfigured

    Errors were encountered while processing:


    If I try apt-cache policy qt4-dev-tools, I get


    Installed: 4.5.3really4.5.2-0ubuntu1

    Candidate: 4.5.3really4.5.2-0ubuntu1

    Version table:

    *** 4.5.3really4.5.2-0ubuntu1 0

    500 http://nz.archive.ubuntu.com karmic/main Packages

    100 /var/lib/dpkg/status

    Do I wait for a package update, Ubuntu 10.01 to come off beta or a bug fix? Any thoughts welcome.

  4. Ralph Keesley says:

    I think it depends on what Video Card you’re using.
    Integrated Video Cards work better since they come
    pre-installed.(Time=Money) And I wouldn’t use a PC that a salesman has been working on. (Unless he’s
    a PC salesman). Runs with RHE, no problem.

  5. Samoul says:

    You tile is false. You should replace find with approximate…. otherwise P=NP, knowing that TSP is NP-Complete. Beside TSP is such a nice way to introduce people to computer complexity and simulated annealing is also quite a beautiful way to overcome such complexity!

Leave a Reply

Your email address will not be published. Required fields are marked *