Calculate shortest path through a grocery store

Question

Hi, 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 startposition and can end at multiple endpositions (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 travelling salesman problem? Because in my problem there is a specified startnode, specified endnodes, and some constraints, which are not in the travelling salesman problem.

Any help would be appreciated :)

Answer 1

Well, basically it is a traveling salesman problem, but with your requirements you limit the search space pretty well. If there are not too many locations, you could try to calculate all possible options, but if that is not feasible, you need to limit the search space even more.

You can make the search time limited so that you will return the shortest path you can find in 1 second, but that might not be the shortest of them all, but pretty short anyway.

You could also apply Greedy algorithm to find the next closest location, then using Backtracking select the next closest location etc.

Pseudo code for possible solution:

def find_shortest_path(current_path, best_path):
  if time_limit()
    return

  if len(current_path) == NUM_LOCATIONS:
      # destionation reached
      if calc_len(current_path) < calc_len(best_path):
          best_path = current_path
      return

  # You need to sort the possible locations well to maximize your chances of finding the
  # the shortest solution
  sort(possible_locations)

  for location in possible_locations:
      find_shortest_path(current_path + location, best_path)

Answer 2

Well, you could limit the search-space using information about the layout of the store. For instance, a typical store (at least here in Germany) has many shelves in it that can be considered to form lanes. In between there are orthogonal lanes that connect the shelf-lanes. Now you define the crossings to be the nodes and the lanes to be edges in a graph. The edges are labeled with all the items in the shelves of that section of lane. Now, even for a big store this graph would be pretty small. You would now have to find the shortest path that includes all the edge-labels (items) you need. This should be possible by using the greedy/backtracking approach Tuomas Pelkonen suggested.

This is just an idea, and I do not know if it really works, but maybe you can take it from here.

Answer 3

Only breadth first searching will make sure you don't "miss" a path through the store which is better than you're current "best" solution, but you need not search every node in the path. Nodes which are "obviously" longer than the current "best" solution may be expanded later.

This means you approach the problem like a "breath first" search, but alter the expansion of your nodes based on the current distance travelled. Some branches of the search tree will expand faster than others, because the manage to visit more nodes in the same amount of time.

So if node expansion is not truly breath-first, why do I keep using that word? Because after you do find a solution, you must still expand the current set of "considered nodes" until each one of those search paths exceed the solution. This avoids missing a path which has a lot of time consuming initial legs, but finishes faster than the current solution because the last step is lighting fast.

Answer 4

The requirement of a start node is fictitious. Using the TSP you'll end up with a tour where you can chose the start node that you want without altering the solution cost.

It's somewhat trickier when it comes to the counters: what you need is to solve the problem on a directed graph with some arcs missing (or, which is the same, where some arcs have a really high cost).

Starting with the complete directed graph you should modify the costs of the proper arcs in order to:

1. deny going from the items to the start node
2. deny going from the counters to the items
3. deny going from the start node to the counters
4. allow going from the counters to the start node at zero cost (this are only needed to close the path)
5. after having drawn the thing down, tell me if I missed something :)

HTH

Answer 5

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...