I recently came across an interesting article on the Mapbox blog that discusses when to use radius circles and when to use isodistances. While we don't have the 'empty gas tank' use-case, when walking around a new city looking for nearby articles the Haversine formula can be punishing in hilly areas with winding roads.
