Various examples are directed to systems and methods for routing an autonomous vehicle. For example, a system may access temporal data comprising a first temporal data item. The first temporal data item may describe a first roadway condition, a first time, and a first location. The system may also access a routing graph that comprises a plurality of route components and determine that a first route component of the routing graph corresponds to the first location. The system may generate a constrained routing graph at least in part by modifying the first route component based at least in part on the first roadway condition. The system may additionally generate a route for an autonomous vehicle using the constrained routing graph; and cause the autonomous vehicle to begin traversing the route.