No, that’s not a swear word up there! A few weeks ago, a co-worker of mine suggested, in the vein of EFC, that I should visit every Wal-Mart in Ohio. After a bit of searching, I came across this pretty cool map – it lists the location of every Wal-Mart in Ohio. I started trying to figure out if this was doable in 24 hours, but I don’t think it is. I started out at the Marietta Wal-Mart (SE Ohio just north of Parkersburg WV) and started going up the eastern border of Ohio, but it was taking an hour or so to get between Wal-Marts. Since there are 79 of them, and that’s not even considering the time it would take at each one (it was decided that you had to at least go inside and see the greeter), I scrapped it.

A week or so later, I thought it might be cool to visit every Kroger in the area. Hence the name EFCK – Every Freakin Cincinnati Kroger. I think this conversation came up from talks of the Kikkoman deal that has been going on for the past few weeks (I think it ends today – I’ll recap in a few days). I went to Kroger.com and pulled up their list of the Cincinnati region Krogers. Kroger’s Cincinnati region also includes Dayton (as far north as Sidney OH), and out to Hillsboro and Maysville KY, and to the west includes Connersville IN and Batesville IN – here’s the full list of 108. Actually that list includes some Krogers that are closed now and missed a few that have recently opened.

So I decided to see if it was possible to visit all 108 in 24 hours. I started out trying to figure out the best path by hand, but then tried to use a program. This trip is very similar to a classical mathematical problem – the Traveling Salesman Problem. Though, since I don’t have to start and end in the same place, it’s somewhat different – it’s actually called a Hamiltonian Path. There’s actually quite a few programs out there that implement good algorithms to the TSP – though there is no actual solution yet that works for all problems. One good web site is here. It has a computer program called Concorde, but the problem with Concorde is that it only lets you input nodes in X-Y format. But since that computes distances “as the crow flies”, that wouldn’t be quite accurate, since I would have to actually travel on roads and such.

Then I found this – which will do exactly what I need. It’s kind of funny that there are people (lots of people – including this guy) who have done PhD dissertations on this topic, and here I am using it to just mess around. Several people have commented that if only I could harness all this energy for good :-). In any case, I have taken some time over the past few days to figure out the travel distances between each of the 108 Krogers. Actually though, I only computed the nearest few Krogers for each one. As an example, for the Madeira Kroger, I only computed the distances between Madeira and the Kenwood, Mariemont, Montgomery, Blue Ash, Loveland, Milford, Roselawn, Hyde Park and Norwood Krogers (5, 8, 9, 10, 15, 12, 13, 12 and 12 minutes respectively). My thinking was that the optimal path is never going to have you going from Madeira to, say, West Chester, without hitting a few other Krogers on the way. This cut down the total number of distances from 108! (which is approximately 10 to the 174th power) down to a reasonable number of 762 distances – 381 pairs. I put in each pair separately because due to one way roads or highway exits or whatever, the distance / time from Kroger A to Kroger B is not necessarily the same as the distance / time from Kroger B to Kroger A, though usually it’s the same or at least close. Technically, since I’m sure you all care, that makes this an Asymmetric Traveling Salesman Problem.

In any case, I finished out all the distances. Then I wrote a computer program to convert the times from my spreadsheet into the format that this program was expecting, and then I ran the program.

And….. it actually worked! I was not really expecting it to actually work, but it did. Popped out the optimal tour within 5-10 seconds. Because I’m crazy, I wrote a Google Map website with a picture of the tour. Please note that although the lines between Krogers on the website show straight lines, the distances were actually computed using real road travel times. I just didn’t feel like making the map that complicated. The total time was 1346 minutes, which is about 22 1/2 hours. Though this is for a circuitous route, so I can probably get that down to 21 hours or so, but that doesn’t include any in and out time. It was decided for this trip that you’d have to buy something to get a receipt with a timestamp.

So when I saw how long that would take, I thought I would limit it to just what I consider actual Cincinnati-area Krogers. After culling all the non-Nati ones, I came down to a list of 58. Since I already had the distances, it was an easy job to come up with this site. It says 434 minutes for this tour, which is just over 7 hours, so certainly doable. It remains to be seen if I’ll ever actually do this (probably not).