A guide on describing a routing network and how it can then be used generate a route, specific to someones needs, to show them how to get from A to B.
In this article, we’re going to learn about the Visioglobe routing solution. The art of showing someone how to get somewhere.
This article was updated on 23/11/2015 with intersection node information.
Step 1 – Describe the routing network
The routing network is described within VisioMapEditor. It’s created by hand to give you total control over the paths that are returned to the users. The annotated screenshot below was taken from VisioMapEditor and represents a part of a routing network.
The routing network consists of nodes and edges. It describes what paths can be taken, what modality can be used (i.e. pedestrian, bus, train). It takes into account different moving speeds for different edges and different ways of changing floors. It also describes different entry/exit points for the various places within the venue.
Below we’re going to learn how to configure our routing network so that it best represents the real world and provides the most accurate routing information to the end user.
An edge represents a potentially traversable path between two nodes.
An edge has a direction attribute, which indicates the direction that it may be traversed. This direction can configured individually for each edge. Possible directions are:
- bi-directional – may be traversed in both directions
- uni-directional – may be traversed in a single direction. The traversal direction may be swapped.
By default, when an edge is created, it’s bi-directional.
A good example of how you might use this attribute is an edge representing a travelator (aka a moving walkway). Unless you’re feeling sporty, you will only want to traverse this edge in a single direction!
An edge may have zero or more modalities associated with it. Think of modalities as tags that can be associated with an edge. The tag determines the ways that an edge can be traversed. Each modality has a default speed associated with it. The speed determines how quickly the edge may be traversed and therefore the time duration spent on that edge. It’s possible to edit the speed of a modality for an individual edge.
It’s possible to add any type of modality. This will probably depend on the mode of transport within the venue. Some examples might be:
- pedestrian – people on foot
- shuttle – any shuttle service (bus, train, taxi, etc)
- travelator – a moving walkway
- APM (Automated People Mover) – a fully automated, mass transit system.
- none – it’s possible an edge has no modality. This edge is effectively, non-traversable!
By default, a created edge will contain the pedestrian modality. If you manually modify an edge’s modalities, then the next edge that’s created will also contain those modalities.
Above, we see the selected edge (the dotted line) has two modalities, pedestrian and travelator. We also see, associated with those two edges, a traversal speed of 4km/h and 5km/h respectively.
A node occupies a physical position within the map. Computed routes will always start and end on a node. There are normal nodes without any special attributes (they’re white within VisioMapEditor) and then there are special nodes.
A node representing a point of entry/exit to a place. A place might have as many access nodes as it has points of entry. Access nodes are blue within VisioMapEditor. In order for a node to become an access node, it’s access id must correspond with a place’s ID.
Floor transition node
Floor transition nodes connect floors together. To be more precise, the attributes described by a floor transition node are used to create an floor transition edge.
Note: A floor transition node may also be an access node. For example, you want to be able to compute a route to a lift. In that case, the color of the node in VisioMapEditor will be the color associated with the floor transition node.
The id of a floor transition node must be coherent between the corresponding floor transition nodes on the other floors. For example, all the lift nodes that share the same vertical shaft should share the same floor transition id.
Floor transition IDs are created via the VisioMapEditor. Once we’ve created a floor transition ID, we assign it to all the floor transition nodes that correspond with each other.
Note: Nodes on the same floor must not share the same floor transition id.
A floor transition node may have one of the following types:
- Lift – lift node is connected to all the nodes that share the same floor transition ID.
- Escalator – an escalator node is connected to nodes directly one floor above and below that share the same floor transition ID
- Stairway – a stairway node is connected to nodes directly one floor above and below that share the same floor transition ID
- Unknown – Used when the other floor transition types don’t apply (for example, a fireman’s pole). An unknown node is connected to nodes directly one floor above and below that share the same floor transition ID
The direction that this floor transition nodes may change floors:
- Bidirectional – can change to lower and upper floors
- Ascending – can change to upper floors only
- Descending – can change to lower floors only. This might be a useful direction limitation for the fireman’s pole.
Intersection nodes can be used by the navigation algorithm to restrict the places where new instructions can start.
See Explicit Intersections Navigation Algorithm Blog for more information.
Step 2 – Publish the map
When the map is published via VisioMapEditor, it invokes the map builder. The map builder does lots of things. One of those things is generate the map database that gets packaged with the map bundle. Within the map database are specific tables containing all the routing information used for computing routes.
The routing table
Within the routing table, each edge has an associated length (in meters) and a duration (in seconds). Below, we will learn the rule on how these fields are populated.
An edges length (meters) is based on the physical length of the edge. No special processing is performed on this value. The length of the floor transition edges are determined by the distance between floors (which is a configurable map parameter within VisioMapEditor and by default is 10m).
An edge’s duration (seconds) is computed using two factors. The first factor, is the traversal speed (as indicated within VisioMapEditor). The higher the traversal speed, the smaller the edge’s duration. The floor transition edges are generated automatically by the map builder. These edges have a predefined/fixed speed that can’t be edited within VisioMapEditor. Note that the lift edge speed is much faster than the stairwell edge speed. However, to simulate waiting for a lift, a fixed waiting time is added to the duration of the lift transition edges.
The map builder automatically associates certain attributes with the floor transition edges to indicate the type of floor transition. Floor example edges connecting stairway nodes, will automatically have the “stairs” attribute.
The same modality tags indicated within VisioMapEditor are associated within the routing table.
Step 3 – Requesting a route
All the Visioglobe SDKs (VisioMobile, VisioKiosk, VisioWeb, etc) provide the functionality to request a route. This is the functionality that can be made available to the end user of the final solution. When requesting a route, it’s possible to pass parameters to refine the route based on some specific needs. In the following sections we will learn what types of parameters are supported.
Important: Below we talk in detail about what’s possible with the Visioglobe SDKs. All of this should be hidden to a certain degree from the end user. For example, the final solution might propose an “avoid Stairs” option, rather than “Exclude stairs and escalator”.
Route origin and destination
A route is computed, starting from an origin and ending at a destination. The origin and destination are always a route node. The nodes may be retrieved via two methods:
- from a physical position – the closest node in the routing network to the physical position will be returned
- from a place id – the virtual node associated with a place will be returned. We haven’t discussed virtual nodes before (virtual nodes aren’t visible within VisioMapEditor). When we use virtual nodes (as either an origin or destination), the computed route will start/end on an access node.
Note: before a route to a place can be created, it must have at least one access node.
Shortest vs Fastest
Sometimes people want the shortest route (distance), sometimes people want the quickest route (time) and sometimes they want to the choice.
The currently supported route request types are:
- shortest (distance)- returns the route with the shortest combined edge length. This route request type ignores the speed associated with each edge.
- quickest (time) – returns the route with the fastest combined edge duration. This option takes into account edge speed and waiting times.
It’s possible to exclude edge modalities from the route request. For example, the user wants to avoid the shuttle because they prefer to walk. The route request parameters should exclude the “shuttle” modality.
It’s possible to exclude edge attributes from the route request. For example, the user requires a wheelchair friendly route. The route request parameters should exclude the “stairs” and “escalator” attributes.
The default route request is:
- quickest route,
- no excluded modalities,
- no excluded attributes
Query the routing table
Note: there is currently an issue with the VgIRoute::getLength() method when requesting the quickest route. See this question on the forum for more details.