A system for reconstructing vehicle itinerary include a processor and a memory storing instructions, implemented by the processor, to cluster historical trip records into a plurality of clusters, each of the plurality of clusters including a set of historical trip records that describe events occurring within a predetermined time range at one location; identify a sequence of clusters that includes a cluster at each location; and estimate an itinerary for a vehicle based on the sequence of clusters and constraint data describing physical constraints, the itinerary for the vehicle describing a sequence of arrival and departure times at a sequence of locations for the vehicle.