Section 3.1 explains in formal terms the particular class of STDNs under consideration, and section 3.2 motivates the experiments performed in the present investigation. The network topology is an grid with the origin in the lower left and the destination in the upper right, as in Figure 2 . More specifically, edges in the network are associated with sequences of bus departures, where each departure has a departure time d , an earliest arrival time M , and an expected delay . A bus that departs at time d is expected to arrive at time . Obviously, we must require that , and in order to satisfy the stochastic consistency condition each bus on a given route must dominate all buses on the same route with later departure times.
Buses depart along each route every f time units.
No buses run after a time specified by a global parameter . Travelers who arrive at a node after the last bus has departed must walk, and the time required to walk is given by . The parameters and are chosen in such a way that stochastic consistency is preserved and walking is never faster than taking a bus. The experiments reported here address a number of issues related to the performance of PFSD in computing fastest paths in the bus networks described in section 3.1 . The most important question is the rate at which the number of paths considered by PFSD grows as the grid size parameter n increases.