Home page for spacefilling curves and applications

Spacefilling curves, particularly the Sierpinski curve, can be used as a fast heuristic for the Travelling Salesman Problem (TSP). The approach, invented by Platzman and Bartholdi, visits locations in the order they appear along the curve, producing tours roughly 25% longer than optimal for random point sets. The method is extremely fast (sub-second on a laptop) compared to exact solvers that require years of compute time on processor networks. The heuristic has been applied to vehicle routing, geographic information systems, and commercial logistics platforms. A concrete comparison with an exact TSP solver on a 15,112-city German instance shows the heuristic produces a 34% longer tour but computes almost instantly versus 22.6 processor-years.

Nguồn: https://www2.isye.gatech.edu/~jjb/research/mow/mow.html. 8sync News chỉ tóm tắt và dẫn link; bản quyền nội dung thuộc tác giả và nguồn gốc.