A truck has to make deliveries in 50 cities. Can a clever computer program find the shortest, most economic round-trip route?

UPS!

Their routing system avoids left-turns because they take much longer!

Question is of course, will this system receive dynamic updates about current road and traffic conditions, if so, in what intervals and what is the quality of such information received. You will always have a “prediction factor”, no matter how often you update, problem is, if your software works on a predictive basis, “optimal” will always be relative to t.

Ergo, the answer is No.

UPS and FedEx spent buckets of money doing this. Obviously it will never be perfect. But they tried. You would have to take into account variables like traffic and construction for it to be perfect. It would be doable but not really worth it.

Why not use a garmin or any other GPS system. I know that with garmin you can create a route using waypoints. Check out their website at www.garmin.com

I have a friend that works for a trucking company shipping tractor trailer loads of cabbage from Holley NY to a Chinese eggroll manufacturer in NJ. Then they pick up creamers and deliver to Fairport NY then dairy prioducts to Wegmans in Rochester NY then back to Holley.
The entire schedule is regularly blown becasue the guy on the dock didn’t show or the driver can’t unload, or a driver backed up with a door open and ripped it off its hinge. (550 pounds so they need a fork lift to move it.)
They have build a huge cushion into the times to prevent disaster.
They guys who put together the UPS, FedEx and USPS systems are geniuses.

Or was this a hypothetical, programming question? Then, no 50! is too big a number.

@LuvBubble – How would a GPS system help you find the optimal solution?

@Lupin – Well, one might look at this as hypothetical, but 50 cities are very real and delivery by trucks are very real. So realistically how close can we get to the optimal solution? Because the other alternative is finding a computer the size of Jupiter.

This is called the Traveling Salesman problem, and for a long time, it was one of the great unsolved problems in mathematics. The most widely (if not universally) accepted solution to it is Karmarkar’s Algorithm.‘s_algorithm.However, the rigorousness of Karmarkar’s proof and applicability to this problem is disputed.

There are brute force methods for solving it. The Mathworld article has some discussions of these.

@IchtheosaurusRex

impressive

If it’s real, I’d go with a hub system like FedEx and split the issue into 3, 17! problems. Then you’ll be able to do it on laptop.

@TaoSan , I once worked at Bell Labs (as did Karmarkar himself) and this problem came up a lot. It was a matter of interest because the same problem applies to things like trunk lines and microwave repeaters. You want to connect, say, 50 cities, using as little expensive cable as possible. The same thing applies to rail lines and, of course, truck routes.

Yes, very much. The number of variables is mind boggling. I wish I had a big brain like that :)

Software like this is in wider use then one might think. It’s even used in hospitals that incorporate outreach services like phlebotomists and visiting nurses. Call them. Also messenger services. They probably do NOT need absolute perfect.

@Lupin – A clever approach, but you can’t be sure about the optimal solution.

@IchtheosaurusRex – Interesting link. Are you convinced that Karmarkar’s algorithm can work on a computer smaller than the size of Jupiter to find the optimal solution?

I’m sorry, but prediction and optimal in the same sentence doesn’t sit right with me ;)

@mattbrowne , I just remember all the ballyhoo about Karmarkar’s algorithm when it was announced in the Bell Labs News. I was not convinced that it was a rigorous solution. I don’t know how it’s been implemented, or if it has been. I’d think something like Blue Gene might be up to the task.

@IchtheosaurusRex – But even Blue Gene will have limitations. Suppose the truck has to make deliveries in 60 cities. There are more possible routes than there are atoms in the universe. 10^82 is a huge number. If the algorithm is any good and really groundbreaking, it shouldn’t really matter whether it runs on a PC or a supercomputer, right?

I believe that ichtheosaurusRex is correct. I recall from a mathematical modeling class I took while in Grad School that it is currently impossible to find THE optimal solution to this problem. You can use computer programs to find “local maximums,” meaning the computer has found what it thinks is the best solution, but that, with 50 cities and hundreds of different routes from and to each of them, the sheer number of possible solutions make it impossible for a computer to run through all of them in enough time to make it useful to the user (i.e. it would take a million years or something like that).

well, a high-quality algorithm can take a huge load off the CPU, but at the current limitation the number of possible flops is still a huge factor.

Remember when they thought it was impossible to have a computer play chess? Now they are looking 17 moves ahead. That’s a lot of combinations to evaluate but still possible. But 50? That’ll take another week or two. ;-)

@mattbrowne , I didn’t study it in detail. In my work, I applied probability theory and numerical analysis, but integer programming was a bit beyond me. I’m an engineer, I like to make sparks, haha.

I do remember discussions of Karmarkar; it was supposed to have provided shortcuts to the exhaustive search method which, as you have pointed out, would take ice ages to compute.

This problem has been classically solved using Genetic Algorithms. Typically fitness based problems like the traveling salesman can be solved in this way. Whilst you do not exhaust all possibilities, if you generate enough children paths you end up with a very high likelihood of solving the problem with a very high level of accuracy, ie: > 99.99% while using fractions of the computing cycles that a recursion method would require.

Some links: http://www.ads.tuwien.ac.at/raidl/tspga/TSPGA.html
http://ai-depot.com/Articles/51/TSP.html

@mjoyce – Thanks!