For the last year or so, my wife and I have decided to eat better by doing more “real” cooking. A great help in this has been a magazine “Real Simple“. Every month, the magazine publishes a series of recipes, each generally requiring only 20-30 minutes of preparation time. We like these recipes because they use real ingredients: none of this “Pour a can of cream of celery soup over everything”. We’ve agreed to cook everything, whether it sounds appealing or not, and of the dozens of recipes we have gone through, essentially all of them were edible, with most very good and a few definite keepers (*). The authors of the recipes do seem to have a fondness for leeks and fennel, but we have grown used to that. Alexander, my six year old son, eats the same food of course, and generally approves of what we are cooking.
I was delighted with this month’s issue where they had a short blurb on the website route4me.com. The description appeals to their readership:
You need to get to the library before closing, but you also have to pick up the dry cleaning, the kids from school (don’t forget that one), and the inevitable snack along the way. Enter up to 10 addresses on this site and it will calculate the shortest route to get it all done, complete with driving directions.
The Traveling Salesman Problem makes an appearance in our cooking magazine! Naturally I went over to the site, and checked it out by putting in a few cities (seems a limit of 6 but maybe signing up gets you more): Pittsburgh, Cleveland, Atlanta, Winnipeg, Minot (ND), and Los Angeles. Clicked “round trip” to get back home and ended up … with a somewhat surprising route:
Hmm… that crossing in Illinois is a little suspicious. This doesn’t look like the optimal route. Is it? Maybe it is hard to get from Cleveland to Winnipeg due to the lakes? Perhaps here was an example were the underlying road network really has a strong effect on the optimal tour.
I checked things out, and compared this route to the route going from Pittsburgh-Cleveland-Winnipeg-Minot-LA-Atlanta-Pittsburgh. Turns out the route from route4me is about 10 hours (driving) longer than the crossing-free route. What kind of optimization is this?
It took a bit more playing around before I figured out what route4me was doing. Their definition of a “round trip” is the minimum path visiting all the cities from the starting point, followed by going from the final city back to the starting point. The best path is Pittsburgh-Cleveland-Atlanta-Winnipeg-Minot-LA; they then just add in the LA-Pittsburgh leg. Kind of a funny definition, but I am sure they document it someplace.
Overall, I think I will stick with Real Simple for telling me how best to prepare kale, and leave the traveling salesman information to other sources.
[Thanks to Ilona for pointing out the blurb in the magazine.]
(*) Our favorite recipe so far has been “Scallops with Sweet Cucumber and Mango Salsa”. Call it the official recipe of Michael Trick’s Operations Research Blog!
Ingredients
- 1 cup long-grain white rice (such as jasmine)
- 2 mangoes, cut into 1/2-inch pieces
- 2 Kirby cucumbers or 1 regular cucumber, peeled and cut into 1/2-inch pieces
- 1 tablespoon grated ginger
- 2 teaspoons fresh lime juice
- 2 tablespoons extra-virgin olive oil
- 1/2 cup fresh cilantro, chopped
- kosher salt and pepper
- 1 1/2 pounds large sea scallops
Directions
- Cook the rice according to the package directions.
- Meanwhile, in a medium bowl, combine the mangoes, cucumbers, ginger, lime juice, 1 tablespoon of the oil, the cilantro, 1/2 teaspoon salt, and 1/8 teaspoon pepper; set aside.
- Rinse the scallops and pat them dry with paper towels. Season with 1/4 teaspoon salt and 1/8 teaspoon pepper. Heat the remaining oil in a large skillet over medium-high heat. Add the scallops and cook until golden brown and the same color throughout, about 2 minutes per side. Divide among individual plates and serve atop the rice with the salsa.
Of course they use the shortest path – *everyone* knows that a shortest path can be solved in polynomial time, while the TSP is NP hard! Now if they had a good MIP solver, they might be able to solve the TSP. I think I know where they can find one…
The problem might be the distance matrix. A route service may put a limit on the number of requests one can make or otherwise ban the application. Google maps does exactly that.
Still, with the low number of cities it should not be such a trouble. There are other services that’ve been doing that for much longer. E.g. http://www.gebweb.net/optimap/ (the corresponding blog post dates back to 2007)
Last year, when I planned my vacations in Belgium (I wanted to visit the seven trappist abbeys https://secure.wikimedia.org/wikipedia/en/wiki/Trappist_beer) I used this website: http://www.tsp.gatech.edu/maps/index.html . This is from the website of concorde, the tsp solver, and it works pretty well (at least better than the link in your magazine).
My earlier comment was in jest. Don is absolutely right – with so few cities, you can solve the TSP through brute force enumeration.
On a less technical note, Jamie Oliver’s iPhone app contains a number of simple dinner recipes of the sort you describe. The measurements will be in British, but other than that, its quite good.