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 applications, distances are obtained on demand from a shortest-path engine or mapping service, generating millions to billions of origin–destination queries and making distance retrieval a major computational bottleneck. We treat these systems as distance oracles and build surrogate models that approximate these distances while preserving downstream solution quality. We train neural networks using decision-agnostic and decision-focused learning by representing the map as a grid and by using network-level features. Our theoretical analysis establishes convergence guarantees for the grid-based approximation and derives bounds linking distance-prediction errors to downstream solution quality. We consider the asymmetric traveling salesman problem (ATSP) and the p-median problem in a real last-mile service area in Montréal with the Open Source Routing Machine (OSRM) as the shortest-path oracle. Our computational study evaluates grid resolutions ranging from 50 to 250 cells along each dimension, compares multiple learning models, and tests downstream performance on optimization instances with up to 250 locations for the ATSP and 500 locations for the p-median problem. On the largest ATSP and p-median benchmarks, the strongest learned surrogates reduce the downstream gaps by about 95% relative to the Euclidean baseline. Decision-focused models trained on ATSP instances achieve the strongest ATSP performance, whereas decision-agnostic learning is stronger overall on the p-median benchmarks and is more robust across the two optimization problems.