Reload
Automatic versionTraveling Salesman problem
(end point coincides with start point)
end point differs from start pointstart point is given and end point is arbitrarystart point and end point are given
Traveling Salesman problem by incremental methodby using Hilbert Curve
by using Approximating polygon of Hilbert Curve
TSP with a lot of time
TSP with a lot of time version 2
TSP with a lot of time version 3; using Delaunay triangulation
TSP with a lot of time version 4; using Delaunay triangulation part 2
TSP with a lot of time version 5; using incremental method and Delaunay triangulation
TSP with a lot of time, a variation; using second order Delaunay triangulation
TSP with a lot of time, a variation 2; using third order Delaunay triangulation
TSP with a lot of time version 8; more effort but not enough
Longestic traveling routeLongeric traveling route
Shortestic traveling routeShorteric traveling route
Traveling route to some points
Perpendicular bisectors for TSPExtended perpendicular bisectors for TSP
Click versionTraveling Salesman problem
(end point coincides with start point)
end point differs from start pointstart point is given and end point is arbitrarystart point and end point are given
TSP with a lot of time
TSP with a lot of time version 2
TSP with a lot of time version 3; using Delaunay
TSP with a lot of time version 4; using Delaunay part 2
TSP with a lot of time version 5; using incremental method and Delaunay triangulation
TSP with a lot of time, a variation; using second order Delaunay triangulation
TSP with a lot of time, a variation 2; using third order Delaunay triangulation
TSP with a lot of time version 8; more effort but not enough
Differences of the Optimal path of Traveling Salesman Problem and Optimal path from Delaunay triangulation







Screensaver
Traveling salesman problem with a lot of time version 8; more effort but not enough(Click version)(Open 11/Sep/2010 : The 0th Revision Saturday, 11-Sep-2010 21:55:33 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...

In this variation, using the second order Delaunay triangulation in place of the (first order )Delaunay triangulation. In case of first order triangulation, some path for TSP is not exact shortest path. But second order triangulation has more edges than first order, so I believe the probability that we can obtain exact TSP path is higher, but no guarantee.

In this version 8, I try 2 more efforts.
1. Using Array.
2. If distance ABCD is longer than ACBD, then skip ABCDE and later step.
But not enough. Still, very slow...
tspv8cli.java

If you have a message, don't hesitate to send it by using
E-mail:Mail Form
or
BBS

Use of Takashi Ohyama's website
English Home of Takashi Ohyama
Japanese Home of Takashi Ohyama