Experiments

On another note I’ve been experimenting with finding the ‘true’
shortest path time, assuming that the passenger leaves the point of
origin just in time to catch transit. The strategy is to add an
integer initial_wait element to State objects. The first time any edge
with incurring a wait is traversed (if initial_wait is still zero),
the wait time is not added to the weight element of the State, only to
the time. It is also stored in the initial_wait element. Once the
winning path is found, the initial_wait can be subtracted from the
total travel time, or added to the departure time. This seems to work
pretty well, but my OSM-less station linking was preventing me from
comparing with ‘professional’ routing results from the TriMet web API.
Hence my need to use real streets. Of course rather than just ignoring
wait time, there should eventually be some limit to how much wait time
is tolerated, or a factor 0 < a < 1 for initial wait time.

I’ve also done a very very crude implementation of a parallel path
search algorithm that runs on GPU (CUDA). Guessing from the first
tests, it looks like it might be possible to get 50-100 single-source
all-destinations shortest path trees per second on this data set. The
intended application is doing an all origins to all destinations
travel time matrix, and calculating accessibility measures. However
it’s going to be a mess getting service calendars and so on working,
so for the moment I’m just trying to get realistic results from the
single-processor SPT algorithm… but if anyone is interested in
collaborating on thinking parallelization through, please let me know.

—Andrew Byrd