え、検索・表示ごとに毎回探索すんの？
それこそあらかじめ一定程度絞り込んでも負荷がバカにならんのでは

総当りで店舗Aと店舗Bと距離をあらかじめ計算しておいて
要求ごとにソートするだけ、が現実的に最良な解じゃないの