Geodaten verwenden wie z.B. die OpenGeoDB.
Da gibt es das kleine Problem, dass diese zwar Koordinaten kennt aus denen sich eine Luftlinienentfernung errechnen lässt - aber man darf nicht unbeachtet lassen, dass es Flüsse und Inseln gibt.
Die zu fahrenden Kilometer unterscheiden sich oft von der Luftlinie um weit mehr als die klassische Annahme eines Aufschlages von 50%. (Der sich auf längeren Strecken als recht brauchbarer Durchschnittswert erweist).
Hier eine recht gute, auf OpenGeoDB beruhende Distanzberechnung nebst einer Ortsbibliothek.
Fred