[QUESTION] Edge- or vertex-based model?

[kkdd]

Hello, Which does horizon use, edge-based or vertex-based algorithm/model?

I think that the edge-based one can be represented by the trellis transition diagram whose nodes correspond to road-network links (=edges), which can handle multiple edges in a multigraph of road network, whereas the vertex-based one's nodes correspond to road-network nodes.

[LdDl]

@kkdd Hello and welcome!

1. Routing problem (Dijkstra + Contraction hierarchies): edge relaxation for sure with PQ for eliminating redundant vertices. But I have to mention: it depends on source data really. For my purposes I use mesoscopic graph prepared from OSM data, where vertices are actually expanded edges.

Visual representation of different graph models: Mesoscopic level (used in my approach to pass OSM data to this library): Microscopic level (used in my private traffic simulation engine): Macroscopic level (OSM source data. Meso and Micro models inherit this data):

2. Spatial search (neighbor search): edges geometries
3. Hidden Markov Model (HMM) + Viterbi for hidden states: edges again. But some kind of the penalty is given for edges which have distant source/target vertices.

[kkdd]

Thank you for your explanation. I'm further going to think about this issue.

Can horizon get the result of the sequence of road-network links (=edges) instead of the one of road-network nodes?

The example of the road network with parallel edges is shown highlighted as follows:

[LdDl]

Oh, is that example for road network considering dual roads (e.g. dedicated bus school routes)? Green - GPS markers, black - just arrowheads of movement direction

I guess this could lead to some troubles since routing engine will try to find OPTIMAL way and 5-th point will be considered as redudant by HMM or Viterbi. You've made me think about it deeper (for public transport especially, e.g. snapping GTFS)

[kkdd]

Thank you for your deep consideration.

The 5th point seems important for selecting the optimal one of parallel edges in your example plot, shown as a yellow dashed line in the following:

I think that the edge-based HMM is requited and it is represented by the states of edges (= road-network links) and their transition, whereas the node-based one is represented by the states of nodes and their transition, prohibiting parallel edges.