itinero / routing2 Goto Github PK

Some obstacles (e.g. street lights) can have a (profile specific) cost. This should be added to the time calculation.

Ping @pietervdvn when this is exposed in the lua profiles.

E.g. Blankenbergse Steenweg - Oostendse steenweg rotonde

Itinero already depends on System.Text.Json, remove the Newtonsoft dependency.

Internal data model

Let's go for full turn-weight support. We model turning weights on vertices using a turn-weights table. This idea is loosely is based on this research paper and it seems the CRP paper more or less contains this approach too.

We maintain a single table per vertex and the edges around that vertex are the indexes in that table. We model this as follows:

• Each vertex has an optional pointer to a turn weight table.
• Each edge has an optional local index indicating the index in the turn weight table. Each edge has two of these, one for it's first vertex, one for the second.

Turn weight table storage

Similar to edge types we maintain one index of highly common turning weight tables we can point to. The edge indexes are rewritten to maximize reuse of common turning weight tables. This means we have two types of turn weight tables:

• global: Commonly reused, global turn weight tables.
• local: Unique local versions at tile level.
  The turn weight table pointer has to contain a flag at vertex level to determine the type of table.

The turn weight tables can also different per used profile. We given them a string ID describing what they are for, for example 'bicycle', 'car'. These can then be reused for multiple profiles. The commonly used turning weight tables are shared.

Relation to (turn-)restrictions

There are three main types of restrictions:

• Single vertex restrictions: In this case the turning weights table will have infinite weights in all directions.
• Two edge restrictions: In this case the turning weights table will have infinite weights for the excluded turn.
• Three or more edge restrictions: These are the exception and are relative uncommon compared to the other two types. These will be modeled using conditional turn-tables. A table that is only valid if a vertex has been reached via a path beyond it's incoming edges. The path that this condition is based on has to be stored along with the table. This turn weight table is always local.

Conceptual data model

TBD

How is this handled from a profile perspective, what do we ask the profile and what do we store in the routing graph? The turn weight tables are the edge type equivalent, they can only be built after the routing graph has been interpreted by the profile(s).

Ideas:

• Storage of attributes at the vertex level. This can be used to model:
  • Traffic lights.
  • Nodes in a node cycle network.
  • Single node restrictions.
• Enable storage of edge sets for turn restrictions.
  • We can use this to model turn restrictions.
  • We would probably need to also define roles or and ordering (?). Does not seem to be a very good fit for turn restrictions.

Implementation

Implement turn-restriction support on a per-tile base. What needs to be done:

• Add turn weight tables to tiles.
  • Add a way to store pointers on vertices.
  • Add functionality to get edges a local index per vertex.
  • Add local storage for the weight tables.
  • Implement a way to compare tables, even though their columns may be in a different order.
  • Implement a global weight table index similar to the edge types.
• Implement turn weight support on Dykstra.

E.g.: 'parking:lane:left=no_stopping; parking:lane:right=yes' will have different results

For performance reasons we need to precalculate profile metrics. A profile is a function:

• { attributes-set } -> { factors and speeds }

We need to store this inline to remove the need to load attributes sets for each edge and translate them to factors and speeds again and again. We should also consider storing aspects to enable highly flexible profiles based on a set of precalculated fixed edge properties or 'aspects'.

A solution could be:

• { attribute-set } -> [ { aspect1, value1 }, { aspect2, value2 } ] -> { factors and speeds }

The aspect key value pairs are stored where appropriate.

Hi:

I am using the Class PBFOsmStreamTarget of the OsmSharp API.
This class has methods for adding nodes and ways in the PBF file, but I cannot find the methods to delete them.

How can I delete a way or a node in the PBF file?

Any idea?

Thanks for advance!

Implement elevation support similar to what was done in Itinero1.

• Add an ElevationHandler to get elevation.
• Store elevation on the graph.
• Return elevation in the routes.

Observed behaviour: when doing oneway routing, the tile boundary clips and reverts one of the ways, resulting in two oneway segments pointing to each other, resulting in a way that can never be taken:

The screenshot above is located here: https://www.openstreetmap.org/search?query=Bertem#map=18/50.86156/4.62973

Tervuren.zip
bicycle.short.lua.txt

Basic principles

There are some improvements possible in graph tile storage. We make the distinctions between:

• Routing data: data that is used during route planning:

  • edge length
  • edge type
  • vertex ids.
  • edge enumeration
  • turn costs: includes turn restrictions and vertex attributes.

• Meta data: data is not used during route planning but is needed for a good output and for preprocessing:

  • Edge attributes.
  • Vertex attributes.
  • Turn restrictions and their attributes.

The focus should be on getting storing the routing data as efficiently as possible. The meta data has to be accessible but doesn't not have to be available immediately when accessing an edge.

Current structure

The vertices have the following data:

• pointer to first edge.
• turn cost table id.
• attributepointer: pointer to the attributes. meta

The current graph edges has the following data:

• vertex1, vertex2 ids.
• nextedgepointer1, nextedgepointer2
• (optional) edgeid: only in case the edge doesn't originate in the tile.
• edge type: the type of edge.
• edge length: the length of the edge.
• tail and head orders: turn restrictions.
• shapepointer: pointer to the shape. meta
• attributepointer: pointer to the attributes. meta

Improvements

Ideal would be to have a data structure where we have vertexids and edgeids that increase by one each time a vertex or edges is added. These IDs remain constant even when changing some of the edge payloads.

The new structure could be

Routing data

One byte array with vertex routing data:

• pointer to the first edge.
• pointer to turn cost table (if any).
• vertex id: The by-one-increasing vertex id. This is considered meta, it won't be used during routing and we won't need to read it unless we want to access the vertex's meta data.

One edge array with edge routing data:

• vertex1 pointer: not the vertex id, but the pointer.
• vertex2 pointer: not the vertex id, but the pointer.
• edge type id: the edge type id (optional).
• edge length: the edge length (optional).
• head and tail indexes: the head and tail indexes for the turn cost tables (optional).
• nextedge1 pointer offset: the offset relative to this edge's pointer.
• nextedge2 pointer offset: the offset relative to this edge's pointer.
• edge id: the by-one-increasing edge id. This is considered meta, it won't be used during routing and we won't need to read it unless we want to access the edge's meta data.

Meta data

Now that we have one-increasing ids that won't change we can store all meta-data using those ids. We store the edge attributes identified by edge id, the same for the shapes, turn restrictions and vertex attributes.

When the lua-profile returns '120' as 'forward_priority', it becomes zero in the debug output.

I did put in a 'debug'-statement for a testcase.

When the profile is called with

highway = motorway
oneway = both
_direction = against
access = yes
speed = 120

the resulting object is:

forward_speed = 120
backward_speed = 120
forward = 0.008333333333333333
backward = 0.008333333333333333
canstop = true

Other tags and their results in this document

However, the route mysteriously fails. When trying a very synthetic testcase, it won't take the motorway but will make the detour for car.fast:

(The motorway is the straight line, the detour are residentials)

When dumping the routerdb to geojson, the following data is obtained.
testcase-motorway.osmcar.fast.geojson.txt

Note that _forward:factor is 0 for the motorway, but not for the residential area

To avoid too much overhead and to make things clear for users of Itinero1 we need to:

• Provide a basic roadmap and an idea about where this project is going to go.
• Cleanup the readme, build processes and provide packages.
• ...

https://github.com/coverlet-coverage/coverlet

Hi,
I have seen that this functionality to deal with no-go and speed zones is already implemented. I have just seen in Itinero roadmap.
What code would I have to include to define a no-go polygon, to include it in the profile and finally to be able to treat it in a routerdb file?
The goal is to get a valid route between an origin and destination on the map with the "Calculate (profile, start, end)" method and to take into account no-go and speed areas. The no-go zones are forbidden and the method "Calculate" must know it to return a right route.
I would be very grateful if you could help me.

Kind regards.

Luz María.

An example use case for this is to generate instructions such as:

• Look out for the bollard
• Turn right on the speed table
• Welcome at cycling node 42

In the following case, a crash happens:

var routerDb = new RouterDb...
routerDb.prepareFor(profile1)
routerDb.prepareFor(profile2)
routerDb.useOsmStream(...)
routerDb.WriteTo(file)
routerDb = RouterDb.ReadFrom(file)

routerDb.prepareFor(profile1)
routerDb.prepareFor(profile2)
routerDb.Snap( ... ) // crashes

I spent quite some hours figuring this out. I assumed that 'prepareFor' would be idempotent; but it clearly isn't. Maybe an error could be thrown in case of this misuse?

The idea is to take an OSM-stream and amend it with more data, e.g. relations, elevation, ... by generating more tags from external datasets.

This stream can then become a routerdb or a new .osm-file (aka fun preprocessing for others)

At last, this should be easily configurable with a configfile.

See also #4

Problem

We need to be able to handle route relations and networks:

• Cycling networks
• Pedestrian networks
• Public transport networks.

Other case this could apply to:

• Low emission zones.
• A country ID with country specific rules.

These are usually not modeled as part of the edge attributes and have the following issues:

• An edge can be part of multiple sets.
• The attributes can be similar but different making copying the attributes to the attributes set problematic:

Workarounds

Copying the attributes:

This could be done using a namespace prefix set1_(key)=(value) for example. This is problematic because these semantics will have to be taken over and used everywhere:

• Profiles interpreting the edges will need to know about the set prefix.
• The resulting routes or the part building the route object need to know about this part of they let this internal bookkeeping leak to client applications.
• The order of the sets is irrelevant and it becomes harder to compare profiles for edges.

Suggested solution:

We add another layer on top of the current attributes and edge has in the form of 'edge sets'. These sets could be used to express general properties about edges that are generally not part of the their attributes. This includes but is not limited to: cycling|foot|transit networks, low emissions zones, country ids

Advantages

• The data model is clearer, an edge has properties but can be part of a set that is independent on it's own properties (for example a route or 'zone').
• The attributes or the sets are store in one location (or per tile) and can be update without updating all member edges.
• No attributes in the edges attribute set that are artificial.

Disadvantages

• The concept needs to be introduces in Itinero and bleeds through everywhere:
  • The profiles need to implement set membership as a option.
  • The route output needs to become more advanced and include sets.
  • The data model of a tile has to be adapted to be able to store set membership.
  • The data model of cached edge types needs to include set membership.

I had a testcase where the target point lies close to a road non-accessible to the profile under testing. Ideally, it would be possible to snap to the closest routable road. However, this testcase would snap to the non-routable road, causing the test to fail.

To progress:

• How can this be done?
• Document how this can be done and make it obvious from using the API/docs how to pass the profile

The new test case of the routing profiles fails with this input and bicycle.short

It is mentioned in Itinero.IO.Osm.Tiles.csproj

I'mma remove it in my branch, but for others to build it, it would be cool if a default version is added, or at least some indication on how to download it is present somewhere.

This is especially important for ferries, but also for aerialways.

While debugging the test bench, I got this case:

The new route planner follows the pedestrian area:

The area is tagged with area=yes.

So far so good - in order to fix the test, I attempted to add an access restriction so that ways with area=yes can not be accessed anymore (in most cases, they give truly weird routeplanning). However, when debugging, the area-tag is not passed to the profile, but it seems to disappear mysteriously.

In a route object, TotalDistance and TotalTime should be multiplied by 100 to get the distance in meters and seconds respectively. This is done by the routebuilder

I know this is done to have more precision, but is that really needed? Having it in meters and seconds is more intuitive and makes using the library easier.

We need to figure out how to manage the data in the graph. Specifically with the following cases in mind:

• We don't want to reprocess all routeable tiles when the routeplanner restarts.
• We want to be able to update the graph while the routeplanner is running and still keep the graph consistent.
• We want to store and keep meta-data about what tiles have been loaded and what their timestamps. This to prevent the routeplanner having to rerequest alle tiles in use on restart.

At minimum we need the following features:

• A way to persist to disk individual tiles.
• A way to update the graph by writing to it but only 'committing' the data once the loading is finished.
• Store meta-data in the data provider along with the tiles or the routerdb.

Open questions:

• Do we store this data along with the tiles on disk or in a global structure?