There isn't a cheap way to do it without using some data. People don't often research stores in an area, once they find one in an area, so you're basically left to hope that people drive by and see the store name to Google it -- but those are people who were going to your site already.
Again, I don't want my thought processes hijacked, so the only acceptable context would be me searching for general stores or things that you carry, which I usually.. don't. If I'm looking at a map it is a good fit as well.
On the other hand, I'd really like a searchable inventory of all city stores, even in general terms. Sometimes it's not even clear which store might carry some obscure item and I'm left to guess and check all possibilities in person, often in vain.
Three weeks later I've hired a lawyer and bought a rolling pin and I don't need those ads anymore, they are perhaps the least profitable ads to show me.