How can I route way in both direction?

[Guo-astro]

OSRM is an amazing piece of work! I have some questions when using it, any idea will be helpful.
In our case, I want to calculate 4 routes as in the picture(start heading in 2 directions and target heading in 2 directions)

The idea I can think about is

1. Get the way bearings before using routing service?
2. Use backward/forward edge in Dijkstra?

Really like to contribute back and a big Thanks !!

[danpat]

@Guo-astro Currently, both the forward and backward edges are inserted into the heap at the beginning of the Dijkstra search. The route that gets returned is the one that meets in the middle first.

The code doesn't currently support continuing the search to discover when the other directions meet, but I can definitely understand why that'd be useful.

Here are your options:

1. Modify the routing algorithm to continue the search until all 4 combinations are found. Potentially return the other options as alternatives. This requires doing work inside OSRM.
2. Get the initial route, then use the departure and arrival bearings to construct 3 additional queries that you run - use the bearings= parameter to force the arrival/departure directions for the remaining 3 combinations. This would all be done on the query side.

[Guo-astro]

@danpat Thank you very much!
The second option can be difficult because if routing start from a T intersection, we need to know not only 4 combinations, but 2*3=6 combinations, the problem depends on the if I start to route from road or intersection.

1.it will be very kind if you can tell me the line number in the code of " both the forward and backward edges are inserted into the heap at the beginning of the Dijkstra search" (possible from https://github.com/Project-OSRM/osrm-backend/blob/master/include/engine/routing_algorithms/routing_base_mld.hpp#L242 ?)

2. As the intersection problem described above, I need to obtain the number of snapped edges before running Dijkstra. it will be very kind if you can tell me the related line number in the code(possible from https://github.com/Project-OSRM/osrm-backend/blob/master/include/engine/routing_algorithms/routing_base_mld.hpp#L249 ?)

3. In plugin_base.hpp, I found the following comments
   // Decides whether to use the phantom node from a big or small component if both are found.
   // Returns true if all phantom nodes are in the same component after snapping.

I would like to naively ask what is "a big or small component". I guess it is related to SCC...? Any docs or references will be helpful!

4. What is a source_boundary ? https://github.com/Project-OSRM/osrm-backend/blob/master/include/partitioner/cell_storage.hpp#L142
   Thanks!

[danpat]

@Guo-astro By default, OSRM inserts either 1 or 2 starting nodes into the forward search heap, and 1 or 2 ending nodes into the backward search heap. Each node represents the forward and backward directions on the snapped road.

If a coordinate is on or closest to an intersection, one of the edges will be selected at random and two nodes from that edge will be inserted - OSRM doesn't yet consider multiple edges if there are several that are equi-distant from the input coordinate (see this ticket for more details: #4465).

You can find the logic that inserts the initial nodes into the heap in the common https://github.com/Project-OSRM/osrm-backend/blob/master/include/engine/routing_algorithms/routing_base.hpp#L48 - this is used by all routing algorithms (MLD and CH).

The shortest path I can see to getting multiple routes returned, with specific directions, would be:

1. Modify the geospatial_query.hpp to return a vector PhantomNode nodes for all equidistance matches, instead of a single PhantomNode
2. Modify the search algorithm and change:
   a. Instead of inserting both the forward/reverse directions for every edge, instead, iterate over all combinations of start/end nodes (in OSRM, a node is a single direction of travel on a road, so there are two nodes for bidirectional roads), and repeat the route finding for each combination.
   b. Modify the viaroute plugin so that it returns an array of routes, rather than just one (you can piggyback on the behaviour of the alternative route finder here).

The "big or small component" behaviour is SCC related - OSRM only tries to route between nodes that share the same component ID. This blog post describes the end result of this selection: https://blog.mapbox.com/robust-navigation-with-smart-nearest-neighbor-search-dbc1f6218be8

source_boundary refers to the position within the overall storage vector of the start of source nodes for that cell. OSRM stores several data structures as simple vector<int>, and variables like this refer to offsets within those larger vectors.

[Guo-astro]

@danpat Thanks very much for the explanation, the blog post helps a lot!

1. With respect to the statement "Modify the geospatial_query.hpp",

a). My understanding of the code https://github.com/Project-OSRM/osrm-backend/blob/master/include/util/static_rtree.hpp#L627, all possible nearest distance EdgeBasedNodeSegments are retrieved and therefore I do not need to modify that part, is that correct? (Expecting correction of my naive understanding ...)

b). If a) is correct, in line https://github.com/Project-OSRM/osrm-backend/blob/master/include/engine/geospatial_query.hpp#L300, why are we expecting the largest possible results.size() == 2 ?

2.Sorry for bothering with some more questions Any explanation or blogs link will help!

a.   What is the concept of a view i.e., vector_view.hpp
b.  What is the concept of Container,View,External in the following enum class(or in the design of OSRM datastructure)?

enum class Ownership
{
Container,
View,
External
};

[danpat]

1a. That's correct, I don't think any changes are needed in the static_rtree.hpp logic - it simply iterates over edges from nearest to furthest. It will expand to search the whole planet if the terminate callback never returns true - we've had bugs like this in the past.

1b. The rtree.Nearest() takes two lambda functions as parameters - const FilterT filter, and const TerminationT terminate. The filter determines whether the candidate edge is acceptable for snapping at all. The terminate function decides when enough results have been found. The current terminate logic should stop at either 1 or 2 results - you need to change this to implement the feature we've been discussing.

2a. vector_view is a std::vector-like class that can be pointed at an existing block of memory (i.e. one that is mmap()-ed from a file), but behaves like a read-only vector of that data.

2b. This enum is related to the various ways OSRM can allocate memory:

1. During data building (e.g. osrm-extract), a Container view is created, which is read-write and data can be added.
2. During runtime (e.g. osrm-routed), either a read-only View is created (if using normal memory loading with osrm-routed file.osrm), or a read-only External is created (if using IPC shared memory via osrm-datastore).

It's basically there to capture the different memory ownership models, but allow code re-use during all phases of the data processing pipeline.

[Guo-astro]

@danpat Thanks very much for the detail explanations!
Now I have summarized the questions in the following picture. I guess I have solved question 1.

Got the coding guideline in wiki!! Thank you!

[github-actions]

This issue seems to be stale. It will be closed in 30 days if no further activity occurs.