TSP solver

This page implements a solver for Travelling Salesman Problems. It is the type where you have to specify the distances between the places, where a place is defined with a unique identifier. The specified distances are bi-directional, meaning that the distance is the same for both directions. For distances that are not specified are calculated, where it is possible to specify a maximum number of intermediate places (hops) or a maximum distance through any number of hops. Setting both values to zero, will cause no additional distances to be calculating and thus only find solutions that never revisit a place. This is only possible if the problem contains at least one Hamiltonian cycle. Furthermore, it allows you to define a maximum distance. Solutions larger than the distance are not displayed. The algorithm works by extending a set of partial solutions one connection at the time. The bag size determines the maximum number solutions for each step. The larger the number, the more likely the algorithm finds a smaller solution, but the more time the algorithm takes to finish. (But it could also find less solutions. I do not understand exactly why.)

Traverse over at most hops or at most distance
Maximum distance
Bag size

Programs | Home