K shortest routes

[jamiedtor]

Is there a way to programmatically capture not just the least cost or shortest route but also alternatives, such as the second or third shortest routes?

[mpadge]

Not at present, no. Current code could be adapted to implement it, but there's been no demand until now. If it was an important or interesting use case, I might be able to find time to give it a go?

[jamiedtor]

Thanks, mpadge! Since I forgot to mention it before, really appreciate this package. It's been incredibly useful. In terms of k-shortest routes or alternatives, we're working on identifying likely primary pedestrian routes in newly densified in-fill areas to help prioritize active travel infrastructure. We've been relying on the shortest routes between origins and destinations but given the variability in pedestrian route selection, we think it might be more realistic to include weighted alternatives. We've seen it done with Andres Sevstuk's fantastic Urban Netork Analysis toolkit for Rhino, python and Arc. (Essentially some percentage of the O-D demand for a given pair is allocated to altenative routes based on assumptions about willingness to detour, i.e., the shortest route might get 70 percent of the demand while two alternative routes get 15 percent each.). But we'd really like to keep our entire workflow in R. It's definitely beyond my ability to write the code, but if it does seem like an interesting enough use case that you take it on, I'd been happy to contribute to writing up a vignette or tutorial for others.

[mpadge]

Thanks @jamiedtor , that's definitely a use case that piques my interest. My motivation for all this work is advancing active travel in all ways possible. That sounds to me like what you're looking for is along the lines of the original motivation for this package, which started life as https://osm-router.github.io/osmprob/. The idea was to implement probabilistic routing, using algorithms presented here and here. That turned out to only be possible in very restricted scenarios, and was dependent on direct matrix inversions, which severely limited the scale of networks that could be analysed.

dodgr grew out of that, and eventually discarded notions of probabilistic routing so that the algorithms could be applied to arbitrarily large networks. But the notion of generating a probability density field throughout a network remains central to my ongoing motivations here, so definitely interested in pursuing this. I won't say anything more specific for the moment, but guess it would help to have an idea of your envisioned timetable? We can easily move to private communication if you prefer - feel free to email me anytime to chat further.

One further central question would be the rough scale of your envision queries, primarily via an estimate of how many typical destination points you'd be wanting for each point of origin? I mostly use everywhere-to-everywhere implementations, which also do not scale at all for typical k-paths queries. But even if you just wanted somewhere-to-everywhere, where somewhere was relatively restricted, that would make things feasible.

[jamiedtor]

Thanks, Mark! Great to hear it might be interesting. In terms of the scale we're looking at, it's mostly areas of say 3 to 4 square kilometres. In terms of origins and destinations, probably the max we'd ever be considering would be a matrix of about 500 potential destinations for each origin. More often than not, closer to 200 potential destinations per origin. And for something like identifying priority routes to higher-order transit stations, we're actually looking at a much smaller basket of destinations ... something like three or four possible destinations from origins represented by building centroids within a radius of about 1000 m. (200 to 300).

[mpadge]

@jamiedtor I've figured out how I could implement an efficient probabilistic allocation algorithm. That would produce densities along each edges in a network accounting for the probabilities of every potential path between each A->B pair. But it seems that's not quite what you want. If you want explicit alternative routes, then even standard k-shortest paths won't give you that, because all algorithms for deriving those are only based on the smallest possible path modifications, so the variation between paths will be definitively minimal.

An analogous problem for which i have previously adapted dodgr is a kind of "preferential routing." An example is routing to maximise length of travel through or along natural spaces. That generates very realistic alternative routes that reflect personal preferences for that kind of travel. I would also assert that it reflects the kind of consideration necessary to generate realistic scenarios of alternative routes, like it seems that you want here. For any particular problem or area of application, I think the best approach is to first identify scenarios reflecting a diversity of likely realistic routing choice models. Adapting dodgr for sets of those is then relatively straightforward.

In your case, routing preferences might be something like comparing default shortest routes with routes which maximise under constraint the proportion of the journey travelling alongside or near things like:

• local activity centres (shops, entertainment, whatever)
• points of interest
• natural spaces

Routes can also be extracted which minimise exposure to undesirable aspects, such as traffic noise or pollution (generally very similar but not identical). What do you think?

[FlxPo]

Could we just add some (small) noise to edges travel times and call dodgr_paths multiple times, and then compute the distribution of path selection ? This would be like sampling from a discrete choice model, where we can aggregate some known utility value based on travel time (+ other factors possibly) and the utility value of unobserved factors (sampled from a known distribution).

I'm not sure about the theoretical soundness and value of this approach. But I think it would correctly reflect the fact that two almost equivalent paths should be selected 50% of the time by travelers, for example.