We address the problem of incorporating uncertain location data in the generation of speed profiles for vehicles on roads with multiple lanes. Moving objects' location data can be obtained from different/multiple sources-e.g., GPS on-board the moving objects, roadside sensors, cameras. However, each source has inherent limitations that affect the precision-from pure measurement-errors, to sparsity of their distribution. Incorporating such imprecision is paramount in any query/analytics oriented system that deals with location data. The difficulties multiply when one needs to reason about localization with lane-awareness and attempts to use the location-in-time data to enable effective navigation systems. To tackle this problem, we take a step towards: (a) incorporating uncertainty of the objects' locations into traditional map-matching processes, thereby augmenting them with its impact on different lanes, (b) introducing an information theoretic distance function that can be used to decide when two 'units' qualify to belong to a same cluster. Our experiments demonstrate that the proposed approach offers a more effective way to generate spatio-temporal clusters with similar speed profiles which, in turn, enables more efficient routes generation.