Calculate shortest path through a grocery store

Question

I'm trying to find a way to find the shortest path through a grocery store, visiting a list of locations (shopping list). The path should start at a specified start position and can end at multiple end positions (there are multiple checkout counters). Also, I have some predefined constraints on the path, such as "item x on the shopping list needs to be the last, second last, or third last item on the path". There is a function that will return true or false for a given path. Finally, this needs to be calculated with limited CPU power (on a smartphone) and within a second or so. If this isn't possible, then an approximation to the optimal path is also ok.

Is this possible? So far I think I need to start by calculating the distance between every item on the list using something like A* or Dijkstra's. After that, should I treat it like the traveling salesman problem? Because in my problem there is a specified start node, specified end nodes, and some constraints, which are not in the traveling salesman problem.

Answer 1

It seems like viewing it as a TSP problem makes it more difficult. Someone pointed out that grocery stories aren't that complicated. In the grocery stores I am familiar with (in the US), there aren't that many reasonable routes. Especially if you have a given starting point. I think a well thought-out heuristic will probably do the trick.

For example: I typically start at one end-- if it's a big trip I make sure I go through the frozen foods last, but it often doesn't matter and I'll start closest to where I enter the store. I generally walk around the outside, only going down individual aisles if I need something in that one. Once you go into an aisle, pick up everything in that one. With some aisles its better to drop into one end, grab the item, and go back to your starting point, and others you just commit to the whole aisle-- it's a function of the last item you need in that aisle and where you need to be next-- how to get out of the aisle depends on the next item needed-- it may or may not involve a backtrack-- but the computer can easily calculate the shortest path to the next items.

So I agree with the helpful hints of the other problems above, but maybe a less general algorithm will work. And will probably work better with limited resources. TSP tells us, however, you can't prove that it's the optimal approach but I suspect that's not really necessary...