The Traveling Salesman with Simulated Annealing, R, and Shiny

And, for the case of trips regularly planned, e.g., using one car to get the same several people to work each day, would have a deterministic problem. Of course, part of the problem would be which people shared which car.

Otherwise there is something of a probabilistic problem where the driver gets a travel request at some random time for some random origin and destination and has to decide what to do, e.g., accept the offer or not and how to fit the offer in with what else he is doing.

Might be a lot of work, but might save some money and/or give better service to the customers.

At one time, my Ph.D. advisor wanted me to work on dial a ride scheduling. But I already had a problem I'd made good progress on and used that for my dissertation instead! One reason: For the problem I used, I could claim to have a solution that was optimal in a quite strong sense, but for dial a ride any solution would be only a big mess probabilistically, some big mess that was just heuristic, and that could be evaluated only empirically. Bummer.

Now, I also have another problem! So, anyone who wants to work on combinatorial optimization and hope to get interest from Uber, Lyft, Sidecar, etc. -- go for it!

We should keep in mind that the OP is doing the traveling salesman problem (TSP) in the plane. So we should recall the nice Karp result in about 1972: With meager assumptions on the probability distribution of the cities, for any number x, no matter how small, as the number of cities n goes to infinity, there is a simple approach that will come within x% of optimality with probability 1 - x.

This simple approach? Start by connecting the cities with a minimum spanning tree. Then for the TSP tour, just traverse the spanning tree except going directly to the next city in the tree traversal not already visited. That is, when following the tree would cause visiting a city a second time, just go directly, not following an arc in the tree, to the next city in the tree traversal not yet visited.

So intuitively the value is, for large n, get about as close, about as often as wish, and for small n just enumerate!

Intuitively what is going on is that one of the main challenges is identifying the appropriate clusters of cities and, then, connecting the clusters, and the minimum spanning tree tends to find the right clusters.

Of course, there are at least two algorithms for finding minimum spanning trees, and as I recall both run in time proportional to n^2. So, we have a polynomial algorithm that is, for large n, for TSP in the plane, as close as we please.

For the "plane", I meant R^2, where R is the set of real numbers, that is, ordinary Euclidean 2-space. But Karp's approach also works the same in R^m for any positive integer m.

I would love to see this applied to the NYC taxi data to see how to optimise taxi movements and see how much ridesharing would decrease car traffic.

Code is here: https://github.com/toddwschneider/shiny-salesman

[0] http://stackoverflow.com/questions/2444125/crossing-edges-in... [1] http://stackoverflow.com/a/2444288 [2] http://www.ams.org/samplings/feature-column/fcarc-tsp

Slide 5 of this deck shows some of the problems in chip-design, most of which have been heavily optimized by simulated annealing. http://www.ispd.cc/slides/ISPD12Slides/ISPD12_3_2.pdf

I love the beauty of the analogy to annealing a metal in metallurgy, and how surprisingly well it translates into software. The fact that the result is non-deterministic, but always useful, makes me smile.

The paper contains a historical context of the problem and their methods towards finding and proving (important!) that their solution was in fact optimal.

For those interested in Dantzig, he was the famed PhD student who came late to class one day and wrote down two open problems mistakenly thinking it was homework. He ended up using those solutions as a portion of his PhD thesis [2].

Here's an excerpt from Dantzig himself:

It happened because during my first year at Berkeley I arrived late one day at one of [Jerzy] Neyman's classes. On the blackboard there were two problems that I assumed had been assigned for homework. I copied them down. A few days later I apologized to Neyman for taking so long to do the homework — the problems seemed to be a little harder than usual. I asked him if he still wanted it. He told me to throw it on his desk. I did so reluctantly because his desk was covered with such a heap of papers that I feared my homework would be lost there forever. About six weeks later, one Sunday morning about eight o'clock, [my wife] Anne and I were awakened by someone banging on our front door. It was Neyman. He rushed in with papers in hand, all excited: "I've just written an introduction to one of your papers. Read it so I can send it out right away for publication." For a minute I had no idea what he was talking about. To make a long story short, the problems on the blackboard that I had solved thinking they were homework were in fact two famous unsolved problems in statistics. That was the first inkling I had that there was anything special about them.

A year later, when I began to worry about a thesis topic, Neyman just shrugged and told me to wrap the two problems in a binder and he would accept them as my thesis.

The second of the two problems, however, was not published until after World War II. It happened this way. Around 1950 I received a letter from Abraham Wald enclosing the final galley proofs of a paper of his about to go to press in the Annals of Mathematical Statistics. Someone had just pointed out to him that the main result in his paper was the same as the second "homework" problem solved in my thesis. I wrote back suggesting we publish jointly. He simply inserted my name as coauthor into the galley proof.

[1] http://www.iro.umontreal.ca/~gendron/IFT6551/LECTURES/TSP.pd...

[2] http://www.snopes.com/college/homework/unsolvable.asp

Monte Carlo < Hill climbing < Simulated annealing < Genetic algorithm < Differential evolution