Cartography Salesman on the Web My implementation on the web. Maybe it will help your roadtrip.

Blog. The closest thing to documentation, you will get.

Project Source List of all projects we have on github. Cartography Salesman isn’t there yet, but the Google Maps Cloud Webservice proxy code for c# is. If you need coordinates. The Haversine Equation for distances between coordinates is also there somewhere, though there is a WPF library that will do it for you if you reference the dll (System.Devices…BasicGeolocation?).

A painful labor of interest, I have been scouring the internet for implementations of the Traveling Salesman Problem. You’d think being a famous problem, that it would have a lot of concrete material on the Internet about it. Not for undergraduate level. Either for a laymen, or for a PhD. But here is my implementation. The project might be posted in Github as soon as I cleanup the code. It’s a mess. But the C# proxies for geocoding location to coordinates and map images, which traveling salesman depends on, is already posted. If you’re an undergraduate and if you’re going to plagiarize (ahem, research), do me a favor and at least cite or leave a nice comment at bottom to counter all the trolls and automated phishers I get.

The material on the internet has a lot of scholarly stuff, but not a lot of implementation details. And what is out there, is extremely “naive”.

From, Speeding up Held-Karp (a little bit):

Speeding Up The Traveling Salesman Using Dynamic Programming

To…, I swear to God, the unintelligible (But they have a great graphic of what I think a minimum spanning tree is, using Kruskals, but they describe it as a diagram of proof of cutting plane algorithm):

…The Traveling Salesman Problem is one of the most intensively studied problems in computational mathematics…

To… the only clue that I understood… a minimum span tree implementation, which I didn’t understand except for the traversal of the graph, which I implemented as another kind of permutation generator.

Christofides algorithm…It is an approximation algorithm that guarantees that its solutions will be within a factor of 3/2 of the optimal solution length…

Here is a general interest article, but provides no clue to implementation. And as you know, I was travelling thru the USA and I thought that the traveling salesman problem could provide a decent route for about 200 locations in the continental United States.

A rough architecture diagram, of the layers of the components of the program:

Yes, I am a 40+ year old man. I just don’t have my Visio. You try UML in Paint.

A general explanation of the algorithms would be:

static public IEnumerable> GetAllPermutations(int distinct)
{
    if (distinct > 1)
        foreach (var p in GetAllPermutations(distinct - 1))
        {
            int len = distinct;
            for (int i = 0; i < len; i++)
            {
                List newlist = new List(p);
                newlist.Insert(i, distinct-1);
                yield return newlist;
            }
        }
    else if (distinct == 1)
        yield return new List() { 0 };
}

The other algorithm was randomly made up by me, to iterate on improving the solution the Greedy algorithm produced, as it had obvious flaws that could be easily corrected.

Poor Voyageurs got left behind. Wouldn't it be better if they remembered him in the Dakotas? Now they have to go back for him.

So the first Orange points below describe the performance of a naive greedy algorithm, which produces a kind of absurd result. But it's much better than the random result that Held Karp begins with. So in 1st second, greedy gets the best results. The blocks are how long that algorithm is "the king of the hill".

Performance chart of around 12 locations. The y=0 axis shows which color represents the algorithm has the best result at that time(x-axis). It starts as orange b/c greedy produces a very fast result, but improvement algorithm searches for longest stretches, and sees if there is better place to put it. Not-Christofides will typically result in a faster result, since it doesn't leave behind destinations, and has an idea of which changes produces the biggest improvements (or un-improvements). Usually it will keep the lead finding better solutions faster, but in this example improvements to greedy produces a shorter route faster and it is the best solution, until Held-Karpe searches thru every possible solution and it unfortunately was the very last solution it searched for.

Not-Christofides (or my implementation of what I I thought was Christofides) uses a minimum spanning tree, so the computer knows which locations are clustered around each other. With this knowledge, it tries different combinations. The time it takes to "acquire this knowledge" slows it initially, but it eventually produces the next best result, faster than the other algorithms. This is going to be the general case. It's blue.

The improvement algorithm on the Greedy solution, eventually find a better improvement later, though this is rare. It is orange as well, though, the naive greedy is really only the first point. The later orange points are the improvement algorithm, which is essentially going back to get the one left behind, and putting it in a more convenient place.

But Held Karp eventually finds the very best combination, though it takes 5 times longer, and this is a small set of about 10 to 12 locations. Held Karp takes so long with even the slightest bigger dataset, it will never finish. The typical Held-Karp never curves down anywhere near the other solutions. But at less than 10 locations, it completes imperceptibly as fast as the other algorithms bc it goes thru many combinations very quickly, but the number of combinations grow so fast, it simply can't keep up. It is the grey points. The grey line is the general shape of the improvement curve.

Held Karp's main value after 10 locations, is to serve as a comparison against how the other algorithms are performing. And to ensure that the best solution, often picked up by another algorithm first, is actually the best, if you're willing to wait that long. Truthfully, it shouldn't be expected to return anything, if more than 12 locations.

So this is how the program keeps popping out solutions thru out the 10min runtime, though the chart shows the first 5 seconds of a run. You can cancel at anytime. Most solutions are produced at less than 2minutes. Some as late as 5min. But few ever are produced after that, as Christofides will complete and Held Karp keeps trudging along testing minor alterations that produce no real result.

F'ing smug comics! For his information, the prototype was finished by Santa Fe, NM.

Here is a video of how Car2graphy salesman works after you press the "play" button, using a list of Canadian colleges, and universities in USA that smart Canadians might goto.

[youtube https://www.youtube.com/watch?v=dMoPEhnatLw]

When I post the code, I hope the video helps make sense of the code.

CartographySalesman is build on a few components

HTML page
Google Javascript Maps
poller (back to MVC controllers, for JSON)

MVC2 controllers
Session management
JSON constructor

Map image
Google Static Maps

Threading Mechanism (a lot like javascript promise, actually)
To order concurrent operation of algorithms

Algorithms
Held-Karpe (slow, but complete results)
Greedy (fast but crappy results)
Shorten longest (experiment, a few seconds)
10 item window of heldkarpe (experiment, few minutes)
Not Christofides (experiment, Maybe variation of Djikstra, after Kruskals, few minutes)

Location verification
Google Geocode
Distance Calculator
Google Distance Matrix
Location Descriptor
Google results HtmlScraper