The Demostration of the MST Pyramid Solution of the E-TSP

In this demo processes emplyoed on the the solution of a 50 city travelling salesman problem using a minimum spannig tree approach are shown. In the bottom-up process, the cities near each other are brought together using the Borŏkas step, shown by the black eges appearing in the animation. This edges are then contracted and the father vertices are created (shown with orange). This process is iterated until there are only 4 cities at the top of the pyramid, shown with yellow. This pyramid has 3 levels. The optimal solution is then found and the top-down approximation of the E-TSP solution starts. First a vertex at the top level is chosen to be expanded to its children. Using the full search the path with the smallest contribution to the overall tour is found. And the top-down process is iterated until all the vertixes (cities) in the finest resolution are reached. (~2MB)

←   ↑