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?

Observation

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

Screenshot



Sponsored Link

Incoming search terms:

Related posts

5 thoughts on “TSP Flaming – Quickly finds a solution of the Travelling Salesman Problem

  1. 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:

    tspflaming

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

    qt4-dev-tools:

    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.

    [Reply]

  2. 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.

    [Reply]

  3. 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!

    [Reply]

Leave a comment

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