We study methods for approximating road-network distances on dense urban maps, with a focus on downstream optimization tasks such as route planning. In many ...