Traveling salesman problem with a lot of time version 5; using incremental method and Delaunay triangulation(Open 22/Aug/2010 : The 0th Revision Sunday, 22-Aug-2010 22:48:17 JST)
In this page, we can find the shortest route passing through the points you clicked.
Please click black screen. When you click more than 4 points, the screen shows the shortest route to pass through the points. But if the points are a lot (about more than 10), it takes a lot of time to obtain the solution, sorry.
In this version 2, I delete some combinations for quick computation. The condition of combinations are that two line segments cross each other.
In this version 3, further, comparing the shortest paths from Delaunay triangulation. In some cases, two paths have difference.
In this version 4, further, FURTHER, for more quick response, some technic are used.
1 Set Delaunay shortest path.
2. Compute Exact shortest paths. But I don't compute when lengths are longer than Delaunay path.
In this version 5, further, some revision I tried. At first, using incremental method for initial solution. By comparing initial solution, obtaining earlier in Delaunay step. But still very slow...
Mail Form