Nächstgelegene Adresse/Anschrift finden

Hi,

für ein neues Projekt bräuchte ich einen kleinen Denkanstoß.

Ich habe eine Datenbank in der die Benutzer meiner Webseite ihre Hausadressen hinterlegen. Andere Besucher der Webseite können jetzt ihre Adresse eingeben und ich möchte die nächstgelegensten Adressen aus meiner Datenbank finden.
Ein Besucher der Webseite gibt also seine Hausadresse ein und meine Webseite soll dann (sortiert nach Entfernung) die nächstgelegensten eingetragenen Adressen aus der Datenbank ausgeben.

Ich bin mir nur noch nicht sicher, ob ich die Luftlinie oder die "richtige" (Benutzung von Straßen) Entfernung benötige. Es geht darum, dass Leute von anderen Personen etwas abholen anstatt es sich per Post zuschicken zu lassen.

Es gibt ja Karten-APIs (bing maps, google maps) aber diese sind auf X Abfragen pro Tag begrenzt und kosten dann etwas.
Wie mache ich es am geschicktesten so wenig API-Aufrufe wie möglich zu verbrauchen?

Ein Ansatz wäre ja pro eingegebener Adresse eine Entfernungsmessung zu allen eingetragenen Adresse zu machen und dann sortiert auszugeben. --> Viele API-Aufrufe und exakte Entfernung.

Ein anderer Ansatz wäre schon beim Anlegen der Adressen den Längen- und Breitengrad per API zu ermitteln und mit in der Datenbank abzuspeichern. Dann kann man wenigstens die Luftlinie berechnen. --> Wenig API-Aufrufe aber ungenau.

Wie macht man es richtig?

Du kannst OSM verwenden.

OSM liefert Dir in der germany.osm alle Adressen und Koordinaten in Deutschland.

Das Snippet hier hät ich Dir für die Luftlinienberechnung (Great-circle distance):

public static Double GetDistance(Double lat1, Double lon1, Double lat2, Double lon2, Double radius)
{
    return radius * Math.Acos( Math.Sin( lat1 ) * Math.Sin( lat2 ) + Math.Cos( lat1 ) * Math.Cos( lat2 ) * Math.Cos( lon2 - lon1 ) );
}

Willst Du eine Wegberechnung musst Du entweder auf eine andere API umsteigen und mit dem Request-Limit leben oder Du kaufst Dir eine Bibliothek, die das Anhand von OSM-Daten bewerkstelligt. Frei gibts da meines Wissens nichts. Weder bei Google noch bei OSM.
http://wiki.openstreetmap.org/wiki/Routing