Space Filling Curves and the Traveling Salesman Problem

A number of projects I have done have had the flavor of the Traveling Salesman Problem (TSP). That is, they essentially look to  solve a problem of visiting a number of sites of interest in an efficient manner.  These include routing baseball road trips, visiting all the national parks, traversing Divvy bike share stations and planning golf road trips. Some of the solutions listed use genetic algorithms for routing , while a couple are pretty close to using a brute force method. Note that none of these implemented solutions guarantee optimality of the solution, but rather present a pretty good solution to the problem at hand. While it is a difficult problem in general, there is software available  to solve these problems optimally (especially given the size of the problem I was tackling), but I had no need for such optimality in my problem and wanted to develop them myself. It’s been on my ‘To Do’ list for a while to try and implement a more optimal solution, but I’ve yet to get to that.

Recently, the concept of using space filling curves to produce solutions to the TSP came to my attention. While this is not new work, nor does it guarantee optimality, I nevertheless found the concept intriguing and did some research on the subject.  Space filling curves themselves are a well researched topic going back as far as the great Hilbert himself. I found books by Bader and Sagan to be great resources, though some of the math was pretty deep for a layman such as myself.

Of particular interest to me was a work of Bartholdi entitled “A Routing System Based On
Spacefilling Curves“.  One of the appealing aspects of this approach is that it does not require the calculation of a distance matrix. One of the largest pieces of work involved when implementing my previous projects was producing the matrix of distances between all the sites being considered by the program.  I usually use the Google Maps API for this, and 100 sites requires 100^2 or 10,000 calls, which requires 4 days using the free API (free use is generally capped at 2500 calls a day for a user).  The Divvy project required 90,000 of these calls, which did not happen quickly in clock time ! And were I to do that project again (it was done in 2015), newly added stations would require over 250,000 such calls.

The next couple of posts will detail some points related to my investigation