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 :)