Traversing a vehicle transportation network, by a vehicle, may include determining vehicle operational information, determining a metric location estimate for the vehicle using the vehicle operational information, determining operational environment information of a portion of the vehicle transportation network, determining a topological location estimate for the vehicle within the vehicle transportation network using the metric location estimate and the operational environment information, and traversing the vehicle transportation network based on the topological location estimate for the vehicle. The operational environment information can include sensor data of a portion of the vehicle transportation network that is observable to the vehicle. To determine the metric location estimate, a non-linear loss function with a Kalman filter may mitigate effects of un-modeled sensor error(s). Techniques using Hidden Markov Models and the Earth Mover's Distance to determine the topological location estimate are also described.