Solving Traveling Salesman Problems with Spacefilling Curves
Some combinatorial applications of spacefilling curves
I developed a spacefilling curve heuristic to solve routing challenges like the Traveling Salesman Problem efficiently. Unlike heavy optimization packages requiring massive computing power, this method generates near-optimal tours in seconds on standard hardware. We applied this approach to real-world logistics, including Meals-on-Wheels in Atlanta and blood delivery for the American Red Cross, proving its value in parallelizable, fast, and distance-free routing systems.
Use our heuristic and you get a route immediately, but you must travel for an extra month. Alternatively, configure a network of 110 processors and spend two months to compute the shortest route — to save a month of driving.
- shoo
> To target a space-based laser for the Strategic Defense Iniative (commonly known as the "Star Wars" program)
I'm guessing this application would be selecting an ordering to engage multiple simultaneous targets in minimal-ish time - MIRV warheads or missiles launched in a barrage.
- kmschaal
Space-filling curves as a traveling salesman heuristic is a really nice application I was not aware of. I have mostly seen them in the context of domain decomposition for parallel computing, where you cut the curve at n points to obtain n+1 disjoint domains.
- shoo
space filling curves can also be used under the hood in data structures that support efficient spatial queries: https://en.wikipedia.org/wiki/Hilbert_R-tree