Traveling Salesman algorithm with simulated Annealing

[Bungie]

If your a geek and love algorithms, here's a new take the on the traveling salesman problem.

https://toddwschneider.com/posts/traveling-salesman-with-simulated-annealing-r-and-shiny/

 

[beemerdons]

 

[Uncle Hud]

Looks interesting, especially since the 2016 Big Money Rally ( https://bigmoneyrally.com/2016/ ) kicks off in 2 weeks.

 

[El Toro]

Interesting link.

My take on it is that the concept of "naive hill climbing" is at best ... naive. Using naive hill climbing as a basis for comparison puts the simulated annealing in the best possible light.

When people cared about searching for optima by clever strategies (back in the days before exhaustive search became feasible for so many problems), heuristics were applied to keep out of cul de sacs, or to avoid local minima. One method was to use a shotgun approach to find starting points, or to choose starting points that were clearly separated. No guarantees, of course. But similated annealing doesn't offer any guarantees either.

FWIW, there are lots of ways to solve this problem.

Note that their initial route is a foolish route that only an incredibly stupid person would have chosen "at random."

Note that their final route is one that a good travelling salesman might have been quite close to by just using the strategy of finding the next nearest stopping point in the general direction of crossing the country from the current point.

Simulated annealing has been around for a long time now .... This algorithm might be useful for trip planning if the trip is strongly time limited, with regular changes in target destinations depending on events en route. At the worst, it would provide comfort and relief to the rider. At the best, it could offer a competitive advantage for the user.

Thanks for sharing the link.

 

[Uncle Hud]

El Toro posted: <snipped>
.... This algorithm might be useful for trip planning if the trip is strongly time limited, with regular changes in target destinations depending on events en route. At the worst, it would provide comfort and relief to the rider. At the best, it could offer a competitive advantage for the user.

Thanks for sharing the link.

Your points are solid, El Toro.

Touring rallies like the Big Money Rally and the IBR are real-world examples of the traveling salesman problem: "Here's a list of 10,000 bonus locations of varying point values. Visit as many as you can. Winner is the person with the most points at the end of the competition." (Note the non-trivial variable of differing point values.)

So now the puzzle retains the theoretical aspects of the traveling salesman problem, but adds real-world variables tied to your ability to ride and things completely out of your control (like traffic and weather):

1. Where are the bonus locations?

2. Find routes that yield the highest point totals.

a. How far can I ride in one day?
b. Day trip or spend the night on the road?
c. Will Interstate highways or local roads get me more locations and points? (Interstates are MUCH faster.)
d. Passing through any cities at rush hour?
3. How many days do I want to ride for this trip and for the entire rally?
4. What is the weather forecast for the day(s) of travel?

5. Are my bike, my gear, and my riding skills up to the task for this trip?

6. Where are good bail-out points if I get tired -- or the weather turns foul -- before I've run my entire route?

I have my own method, based on a strategy Ignacio reveals elsewhere on this site -- or maybe his blog. It relies heavily on your concept of "next nearest stopping point", but takes into account the valuable comparison of (1) gathering many low-point locations versus (2) gathering only a few high-point locations.

I've learned about point #6 the hard way. I regularly OVER estimated my endurance during my first BMR. When I bailed out on my route some days, I got home quickly. On a couple of days, I didn't get home any quicker than if I'd gone ahead and run the entire route. Now, I'll draw a line on my route plan as the "point of no return". If I'm beyond that point, there's no benefit in bailing out and riding straight home.

And no, I'm not a theoretical mathematician; I'm a


and engineers love to find solutions to problems. The Big Money Rally is a magnificently complex problem, and Bungie's link will get plenty use in my home as soon as the bonus listing is published.

 

[El Toro]

And no, I'm not a theoretical mathematician; I'm a

I should take the link to see what Hell of an Engineer means to you, but to me it means you're from Georgia Tech.

I did an MSME there about a hundred years ago. George P. Burdell was my roommate

.

I'll take the link in a minute:

Yup ... another Ramblin' Wreck.

I was in the first group of what they called President's Fellows. It was a great place. I was a camera buff in those days and took many pictures with my Pentax H3V. When I go back and look at those slides today, and compare them to the current appearance of the campus, I am dumbfounded.

When I got there Lester Maddox was still selling chicken, and at the Varsity, the first time this po' yankee walked in, they wanted me to pay for my food, and I kept saying "No thank you" because I thought they were asking me if I wanted something else. After you figure out what a nekkid stek is and whether or not you want to hab FO, the brain hurts too much to understand lebenty fitty.

I took my camera and a long lens to the first home football game, and they would not let me bring it in. The season pass for all sports cost $12, and I just went back to the dorm rather than give up my most prized possession.

And then there were all the young ladies from all over southern Tennessee and north Georgia out on the hunt. I barely escaped.

 

[Uncle Hud]

Yessirreeebob, I'm a Yeller Jackit. Glad you made it out safely, Mr. President's Fellow. Campus is nothing like it was even five years ago, because our location in Midtown Atlanta forces Tech's expansion plans to higher densities and taller buildings.

I'll confess that I get more excitement out of planning my BMR rides than actually riding them, although there's something to be said for putting 850 miles on the bike in one day as you travel through four states. Puts a smile on your face to reflect upon the day's accomplishments.

 

[El Toro]

On the location, back when I was there, there was a little restaurant across the street called Junior's. It's gone now, displaced by a high rise the last time I was through there. Junior's was the sort of place where you had to de-order the grits if you didn't want them. Grits were coming, no matter what you'd ordered. The grits were good, but they were one of the descriptors that set Junior's apart from the typical New England breakfast place where one might get a corn muffin, and a coffee regulah.

Juniors had taken checks for meal payment all term. It was the end of the term, and when I finished my breakfast, I went to the register. The cashier said "I'm sorry. We can't take any checks because it is the end of the term and students will leave and close their checking accounts before we can cash them."

I said "I've got no cash, but I'm not leaving. My check is good, but if you won't take it, do you want me to leave something of value with you and I'll go get the money to pay for my breakfast and come back directly?"

The cashier said "Oh no. Just give me your IOU for the bill and you can come back later and redeem it."

I was not asked to produce any ID. I just wrote an IOU on a scrap of paper and signed it. They put it in the cash register. I went to the bank and got some money, and came back later that morning to redeem the IOU. They literally would take an IOU, but not a real check ....

Sigh....

A few years ago we went back and stayed at the hotel that is on the property that was at one time the Fairmont. The Fairmont was French Provincial, beautifully appointed. The hotel that is there now was decorated like a Rave Club. Strange to my eye. Many places that were at one time really clean and nice seemed run down. I guess the good areas evolve. Cities are always in some cycle of life.

 

[Bungie]

The nature of the problem can only be optimized completely for one criteria. Be it, distance, time or in the case of a rally, bonii. Every other solution is a comprimise. The trick is to have it comprised in your favour.

As for the random starting point in the algorithm that no sane person would choose; That's precisely the reason for needing a bad one. It's a requirement of the algorithm. Like a quicksort, it does particularly badly on a list that at, or near, already sorted.

I posted it not as a discourse, but because if your of the geek persuasion, this shit is fun.

 

[El Toro]

You could handle the multiple objective problem by doing a Pareto optimization.

I published articles in refereed journals using Monte Carlo methods and simulated annealing over 20 years ago ... applications were in complex assembly tolerance assignment and in chaotic vibrations of thermally loaded plates, so I'm familiar with the ideas. As I said in the earlier post, simulated annealing is not new.

Still, the travelling salesman problem is a mature, well formulated problem, and it's a nice application that might be useful for rally participants.

Someone tagged it as a rally cheat. I don't think it would be cheating unless it was specifically prohibited.

 

[Uncle Hud]

Hell no it ain't cheating! It's only another optimization method! Use a machine to do your calculations; saves time and improves accuracy.

Cheating? Visit all the bonus locations by trailering your motorcycle.

 

[Uncle Hud]

Uncle Hud posted: <snipped> I have my own method, based on a strategy Ignacio reveals elsewhere on this site -- or maybe his blog .....

.... and, after much searching, here it is.

Notes:

1) The BMR issues pre-packaged GPX files of the bonus locations (or close by), so you really start picking up "the Jim Owen method" at step 3. I usually manipulate and trim the GPX or CSV files to bonus locations within my riding range (Virginia - Kentucky - Mississippi - Gulf - Atlantic) before loading them into Google Maps.

2) Each category of bonus is a separate layer on Google Maps, and has a distinct color/shape. This becomes important as you start to plan a route and need to place an emphasis on the high-point locations.

3) This year, the BMR has time-limited bonus locations, too, so I'll probably revert to Mr Owens' fomatting: colors for point value, shapes for time-limited bonii.

4) Until now, I'd look at the map and select a collection of high-value locations that are geographically close. Using Google's routing algorithm, I'll slowly add new high-value locations. If a low-value location ends up within a few miles of the high-value route, it gets added.

5) Now comes the artsy-touchy-feely part of route planning: How close is close enough? It's an art, people, and you need to understand that stopping for the photo will cost you at least 10 minutes. Add those 10 minutes to the extra travel time, and you begin to see that it isn't worth 40 minutes and a gallon of gas to bag a 0.76 point bonus.

6) This year, I'll load the routes into my Garmin and go. In the past, I built a small spreadsheet with Lat, Lon, Bonus and Code, miles/minutes from last location, and ETA to this location. The last elements are for QC control. If it looks weird, check the Lat/Lon in the paper Bonus Listing carried in the topbox. If I'm running behind schedule, it allows to to decide which locations to drop.

7) This year, I'll probably still use a printed spreadsheet to keep the time windows posted on my FJR dashboard. For example, it may be possible to bag the NC and AL Bubbler Center bonii if you boogie directly from one to the other. If I get significantly off schedule, it would be nice to realize that before riding an extra 2 hours and arriving too late.