The best strategy for two people lost in a large store may be to wait at the exit of the store on the grounds that the other person may eventually conclude that you have gone home and do likewise.
The maximum waiting time will then be from the time you lost each other until the store closes.
A strategy of staying still only works if just one person stays still. If you both decide to stay still, then the wait time is either infinite, if you get locked in, or again until the store closes.
Assuming that one person stays still while the other searches, then the maximum time is the time taken for one person to search the entire store.
This depends on the layout of the store.
If all the aisles can be readily seen from one vantage point, then the search is simplified. The problem is not dissimilar to that of designing prisons in which the warders can see down as many corridors as possible, or the design of forts that will give the defenders maximum cover.
In order to increase the odds of being located, the person staying still should stand at an intersection of aisles.
A random search will proceed with each person moving away from their initial starting point at a rate proportional to the square root of time.
The area being searched by each person is defined by two circles centred at their respective search starting points. Given that these circles will need to overlap significantly for the individuals to meet, the search time must be at least proportional to the square of their initial separation distance.
If some of the aisles are blocked during this search, then the rate of movement is reduced and the problem becomes one of motion on a fractal where the rate is proportional to some fractional exponent.
One must first know whether the two people have agreed in advance what to do if separated, for example, who should wait and who should search. If they can agree on independent search strategies in advance, the problem is the asymmetric version of the rendezvous search problem; otherwise it is the symmetric version.
In all these cases where exact solutions, to give a least expected time or minimax time, have been obtained, both searchers move at their maximum speed all the time. In these cases it is certainly not optimal for a searcher to stop while the other continues.
For example, in a simplified model in which two people are placed a unit distance apart, but neither knows the direction of the other, it would take an expected time of (1 + 3) / 2 = 2 for the searcher to find the stationary person, assuming visibility is nil. However, by moving optimally this time can be reduced to 13 / 8.
The only case where a searcher and a waiter may be optimal is for two people placed randomly on a circle, and then only when the people concerned have no common notion of clockwise; otherwise one person walking clockwise and the other anticlockwise is optimal.
All these results and questions assume that the searchers find each other only when they meet or alternatively when they come within a specified detection radius. This applies to aisles in a supermarket on a crowded day, when visibility along an aisle is limited.
The possibility of seeing a long distance along an aisle has not, as far as I know, been modeled.
We recommend that you walk along the edge of the supermarket where the tills are, looking down the aisles for the person you seek.
If you have no success, then walk back, still looking down the aisles, but also checking the tills. If you still have no success, then find the cold meat counter, as queues often develop there. Then have a final walk along the till edge, checking the aisles again.
If you are still unsuccessful then you should ask for an announcement to be made on the public address system or, if it’s not urgent, wait by the exit.
