a-b-street / a-b-street/abstreet

More realistic static routing

Aperta
#494 15 commenti 0 reazioni 0 assegnatari Vedi su GitHub
Lingua principale
Rust
Stelle
8.2k
Fork
380
Metriche di merge delle PR
Nessuna PR unita negli ultimi 30g

Descrizione

A/B Street's cost functions for [driving/biking](https://github.com/a-b-street/abstreet/blob/2bbc43b5292efd1646a78d2c7ccd06912768c52c/map_model/src/pathfind/driving.rs#L222) and [walking](https://github.com/a-b-street/abstreet/blob/2bbc43b5292efd1646a78d2c7ccd06912768c52c/map_model/src/pathfind/walking.rs#L388) are laughably simple. They're used to pathfind for agents and to determine walksheds in the 15 min tool. This issue will focus on improving these cost functions for the static case; not going to worry about dynamic conditions like traffic delays or congestion charges yet.

Some thoughts/questions:
- Do we express the cost just as an estimated time, subject to constraints? That's easier to communicate with people and matches the 15 min neighborhood intuition, but it doesn't directly express quietness / safety / pleasantness.
- Multiple factors will influence a single cost. Should we use linear combination with parameters we have to somehow tune? Or a lexicographic comparison of each factor, arbitrarily choosing that a slight safety benefit warrants any increase in expected time?
- Bucket list of factors:
- For driving: speed limit and road length, waiting at traffic signals (could use actual fixed timing, or at least cycle length), unprotected left/right turns onto a bigger road
- For biking: road length, elevation (don't have data yet), biking on/adjacent to a higher speed limit road, bike lanes in the door zone of parking, preferring totally separated trails, some OSM-based measure of road beauty (tree cover?) or quietness
- For walking: same as biking, except the door zone factor doesn't matter
- Individual people's preferences differ
- Biking examples: fearless and fastest route possible, wanting hills for training, wanting safe/quiet routes
- Do we need to support any arbitrary set of parameters, or just make up a few fixed profiles? Implementation-wise, since we're using contraction hierarchies, a few profiles is more reasonable.
- Parameter tuning and testing
- How do we verify resulting paths for different preferences are reasonable? I could manually audit some examples around Seattle that I'm intimately familiar with.
- Should we set up goldenfile unit tests, or is this likely to be super brittle as we get new upstream OSM data?
- Using the cost functions for reporting
- Today, the main metric used as a score in the game is trip time savings
- We can measure anything we simulate. It's a matter of how to report it -- total cyclist miles spent in a door zone?

Some initial tasks
- [ ] Research how CycleStreets, Valhalla, GraphHopper and other open source routing engines solve these problems. (We're going to end up doing something way simpler of course, but at least get ideas)
- [ ] Make a new `RoutingProfile` enum that subsumes `PathConstraints`, pass it in a limited number of places
- [ ] Refactor internal CH / Dijkstra impls to work off the profile enum
- [x] Make a new debug UI to specify a start/end. Automatically show the route for all profiles.
- [x] Add sliders for the parameters to the UI and allow changing live. (Maybe for pathfinding, that always winds up calling the Dijkstra impl instead of rebuilding the CH)
- [ ] Investigate using routing tables from CycleStreets directly (is https://github.com/cyipt/actdev/blob/main/data-small/great-kneighton/routes-fast.geojson an example?)

@Robinlovelace , @mvl22 as FYI -- I'm going to start some amount of this to improve the routes taken for actdev.

Guida per i contributori

Nessuna guida per i contributori indicizzata per questo repository

Valutazione

Questa issue non è ancora stata valutata.

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.