Solving the routing problems in R: stplanr

The stplanr provides Functionality and data access tools for solving the routing problems in R, mainly using the shortest path algorithm. It is based on the sp and igraph packages. So the shortest path algorithms are from the igraph package?

Basically, it provides a SpatialLinesNetwork class. Some very useful functions are in the follows:

• overline: turn a SpatialLines into a route network. Return a SpatialLines object.

• SpatialLinesNetwork: turn the SpatialLines object into a SpatialLinesNetwork

• sln2points: find the nodes in the network

• sum_network_links: summarise the use of linkes between the origin-destinatin (O-D) pairs.

• sum_network_route: summarise the length of the shortest paths between the O-D pairs.

Note that both sum_network_links and sum_network_route are quite slow and eats up a lot of memory for a large number of O-D pairs. Both function use the shortest route, and summarise of the link use or route length of all pairs, rather than that of an individual O-D. In order to obtain the link use or route length between an O-D, the mapply or map function or their parallel versions can be used. According to experiments, using an apply function on many O-D pairs is almost as efficient as that of calling sum_network_links or sum_network_route in one go.

I have done a project using stplanr, to solve the following problem: given a road network and a set of O-D coordinates not on the network, summarise the road use from the shortest paths between the O-D.

This is done through the following steps:

• Create the SpatialLinesNetwork object and the nodes.

• Check if the SpatialLinesNetwork object is connected, i.e. containing only one connected component, using the nt.connect function from the shp2graph package. Revise the network if necessary.

• Obtaining the nodes in the network using sln2points

• For each pair of O-D, determining the nearest nodes on the network to the origin and destination, using the nabor::knn function. Is this step called snapping?

• Calling sum_network_links and sum_network_route to obtain the link use or the route lengths on all shortest paths.

• Coupling sum_network_* functions with parallel::clusterMap to get the individual information of each shortest path.

The unsolved problem: although the network is identified as connected by the nt.connect function, meaning that all nodes in the network are connected, the sum_network_* function returns NA for some O-D pairs.