Skip to content

Latest commit

 

History

History
40 lines (31 loc) · 2.2 KB

README.md

File metadata and controls

40 lines (31 loc) · 2.2 KB
Raw

TSPSim

A GUI Simulation for the Travelling Salesman Problem (TSP) and solving/approximation algorithms in comparison

(english localization coming)

The following algorithms are currently implemented:

  • Exact:
    • Brute-force (you guessed it)
    • Dynamic-programming
  • Heuristics for opening:
    • Nearest neighbour
    • Best nearest neighbour
    • Minimum Spanning Tree (MST) Transform
  • Optimization:
    • k-Opt (currently only 2-opt)

For testing and benchmarking purposes TSPSim is connected to a fork of Heidelberg's infamous TSP Library, allowing you to import any TSP File and make local changes to it. The Library is hosted at tsplib.felixcornelius.de

Creating a new instance

You have 3 options to create a new TSP instance: Generation pseudo-random vertices of a given number, adding vertices by mouse input or entering a weighted adjacency matrix (experimental. very experimental.)
A good practice strategy then would be to create a first tour with the Nearest neighbour method (or Best nearest neighbour, which is just independent of a starting point) and compare it with the transformed MST tour (click the stats checkbox for detailed tour info). The better one (which is NN in about 90% of all cases) can then be optimized by identifying and reconnecting crossing edges of vertex 2-pairs (2-Opt method)

Other features

  • Import/Export instance to TSPLib compatible .tsp File
  • Export instance as PNG Graphic (with optional alpha channel)
  • Color/weight customization of vertices and edges
  • Define a background image for any TSP instance.
    (with basic image manipulation such as zoom, translation and opacity). A few maps are also included

       

TODO

  • English localization
  • Fix 2-Opt issues
  • 3-Opt implementation
  • Commandline version for speed