A method, apparatus and computer program product are provided for generating structured trajectories based on probe data while maintaining privacy and user information, and generating a map representation of a road network from the structured trajectories. Methods may include: receiving a plurality of trajectories of probe data points from a plurality of probe apparatuses; identifying splitting points in each of the plurality of trajectories of probe data points; identifying legs of the plurality of trajectories of probe data points between pairs of splitting points; assigning legs into bunches of legs; searching a solution space determined by leg bunch assignments; determining, from the bunches of legs, a selected solution representing a map of a road network; and facilitating at least one of navigational assistance or at least semi-autonomous vehicle control using the map of the road network.