4.3. Using the Network object: Routing¶
This page goes through GeNet's capability in routing on the Network graph. Available as a jupyter notebook or wiki page.
You can find shortest path between two nodes in the graph, using a modal subgraph or otherwise.
import os
import shutil
from genet import read_matsim
path_to_matsim_network = "example_data/pt2matsim_network"
network = os.path.join(path_to_matsim_network, "network.xml")
schedule = os.path.join(path_to_matsim_network, "schedule.xml")
vehicles = os.path.join(path_to_matsim_network, "vehicles.xml")
n = read_matsim(
path_to_network=network, epsg="epsg:27700", path_to_schedule=schedule, path_to_vehicles=vehicles
)
# you don't need to read the vehicles file, but doing so ensures all vehicles
# in the schedule are of the expected type and the definition of the vehicle
# is preserved
n.print()
Graph info: MultiDiGraph with 1662 nodes and 3166 edges Schedule info: Schedule: Number of services: 9 Number of routes: 68 Number of stops: 118
from_node = "101982"
to_node = "101991"
The following will use the whole graph disregarding modes.
n.find_shortest_path(from_node, to_node)
['2030', '2453', '296', '3147', '3287']
The following will compute a modal subgraph and use it for routing. You can also pass a list e.g. ['bike', 'walk'].
n.find_shortest_path(from_node, to_node, modes="car")
['2030', '2453', '296', '3147', '3287']
If you have many node pairs to process, it may be beneficial to compute the modal subgraph of interest first and pass that to the method.
car_g = n.modal_subgraph("car")
n.find_shortest_path(from_node, to_node, subgraph=car_g)
['2030', '2453', '296', '3147', '3287']
Specifying 'modes' on top of giving the subgraph will also use given modes for preferential treatment if there is
ambiguity in which link should be chosen for the route (remember, there can be several links between the same two
nodes). For example, if using mode 'bus' and there are two links to choose from, one with modes: ['car', 'bus'] and
the other with just ['bus'], preference will be given to the link dedicated to that mode. Otherwise, preference
will be given to links with higher freespeed.
n.find_shortest_path(from_node, to_node, subgraph=car_g, modes=["bus"])
['2030', '2453', '296', '3147', '3287']
The anser is the same because this network does not have multiple bus only links.
You can also choose to return the chain of nodes instead:
n.find_shortest_path(from_node, to_node, return_nodes=True)
['101982', '1611082208', '2489433555', '25495406', '1514726033', '101991']
If you are looking to route a PT service in the Network's Schedule you have a few methods to choose from.
If the Network graph or the data on your graph has changed and you want to reroute a service that was previously snapped to the netowrk and routed you can use the reroute method. You can pass either a service or route ID, they should be unique and will be handled appropriately. You can specify additional_modes, e.g. car mode that will allow buses to use the links that allow the car mode as well as the route's own mode bus. Following this, the mode on the used links will be updated with the mode bus.
n.reroute("VJ375a660d47a2aa570aa20a8568012da8497ffecf", additional_modes={"car"})
2023-12-08 13:44:17,450 - Checking `linkRefId`s of the Route: `VJ375a660d47a2aa570aa20a8568012da8497ffecf` are present in the graph 2023-12-08 13:44:17,451 - Rerouting Route `VJ375a660d47a2aa570aa20a8568012da8497ffecf` 2023-12-08 13:44:17,492 - Changed Route attributes for 1 routes
It could happen that the snapping of a route or service is no longer valid after the changes, or you want to add something completely new. In this case you can use the route_service method which will find new links to snap and route the service on the network. You will need to have a solver set up, e.g. CBC. Again, you can specify additional_modes as in the method above. There are other parameters you can make use of, more details can be found in 5.2 which talks about modifying Schedules.
if shutil.which("cbc"):
n.route_service("20274", additional_modes={"car"})
else:
print("Cannot route service without a solver installed")
2023-12-08 13:44:18,258 - Routing Service 20274 with modes = {'bus'}
2023-12-08 13:44:18,274 - Building Maximum Stable Set for PT graph with 8 stops and 6 edges
2023-12-08 13:44:18,338 - Passing problem to solver
2023-12-08 13:44:18,339 - Initializing ordered Set vertices with a fundamentally unordered data source (type: set). This WILL potentially lead to nondeterministic behavior in Pyomo
2023-12-08 13:44:18,343 - Passing problem to solver
2023-12-08 13:44:18,838 - Stop ID changes detected for Routes: {'VJ6c64ab7b477e201cae950efde5bd0cb4e2e8888e', 'VJ812fad65e7fa418645b57b446f00cba573f2cdaf', 'VJ375a660d47a2aa570aa20a8568012da8497ffecf'}
2023-12-08 13:44:18,841 - Changed Route attributes for 3 routes
2023-12-08 13:44:18,845 - Changed Link attributes for 41 links
If you are creating a Network and want to snap and route the entire Schedule, or a larger number of services, the method route_schedule is advised. Bear in mind though that it will struggle with large networks and big and complicated schedules. Similar parameters apply to this method as the one above, and a solver is needed to undertake the routing.
if shutil.which("cbc"):
unsnapped_service_ids = n.route_schedule(services=["20274", "15660"])
else:
print("Cannot route schedule without a solver installed")
2023-12-08 13:44:18,854 - Building Spatial Tree
2023-12-08 13:44:19,530 - Extracting Modal SubTree for modes: {'bus'}
2023-12-08 13:44:19,544 - Routing Service 20274 with modes = {'bus'}
2023-12-08 13:44:19,545 - Building Maximum Stable Set for PT graph with 8 stops and 6 edges
2023-12-08 13:44:19,589 - Passing problem to solver
2023-12-08 13:44:19,590 - Initializing ordered Set vertices with a fundamentally unordered data source (type: set). This WILL potentially lead to nondeterministic behavior in Pyomo
2023-12-08 13:44:19,592 - Passing problem to solver
2023-12-08 13:44:19,696 - Routing Service 15660 with modes = {'bus'}
2023-12-08 13:44:19,698 - Building Maximum Stable Set for PT graph with 5 stops and 3 edges
2023-12-08 13:44:19,753 - This Maximum Stable Set Problem is partially viable.
2023-12-08 13:44:19,754 - Maximum Stable Set problem to snap the PT graph to the network is partially viable, meaning not all stops have found a link to snap to within the distance_threshold.Partial snapping is ON, this problem will proceed to the solver.
2023-12-08 13:44:19,754 - Passing problem to solver
2023-12-08 13:44:19,755 - Initializing ordered Set vertices with a fundamentally unordered data source (type: set). This WILL potentially lead to nondeterministic behavior in Pyomo
2023-12-08 13:44:19,756 - Passing problem to solver
2023-12-08 13:44:19,821 - Successfully snapped 4 stops to network links.
2023-12-08 13:44:19,830 - Stop ID changes detected for Routes: {'VJf2e0de4f5dad68cb03064e6064e372dde52cc678', 'VJ6c64ab7b477e201cae950efde5bd0cb4e2e8888e', 'VJ812fad65e7fa418645b57b446f00cba573f2cdaf', 'VJ375a660d47a2aa570aa20a8568012da8497ffecf', 'VJ3716910ec59c370d9f5c69137df7276b68cf0a08', 'VJ1cf651142378958b52229bfe1fa552e49136e60e'}
2023-12-08 13:44:19,834 - Changed Route attributes for 6 routes
2023-12-08 13:44:19,838 - Added 1 nodes
2023-12-08 13:44:19,900 - Generated 0 link ids.
2023-12-08 13:44:19,903 - Added 2 links
2023-12-08 13:44:19,907 - Changed Link attributes for 53 links
Some services may fail to snap. Method above returns IDs of the services which failed. It is worth re-running these, with the same or different parameters. Failing that, a service can also be teleported using the following method. If the stops are already snapped (i.e. have a linkRefId), those links will still be used as references, unless the link is no longer in the network.
n.teleport_service(service_ids="17732")
2023-12-08 13:44:19,925 - Added 0 nodes 2023-12-08 13:44:19,969 - Generated 0 link ids. 2023-12-08 13:44:19,973 - Added 8 links 2023-12-08 13:44:19,975 - Changed Stop attributes for 10 stops 2023-12-08 13:44:19,977 - Changed Route attributes for 2 routes
n.schedule.stop("490004695A.link:3017").print()
Stop ID: 490004695A.link:3017 Projection: epsg:27700 Lat, Lon: 51.51433903, -0.12977799 linkRefId: 3017
list(n.schedule["17732"].routes())[0].ordered_stops
['490004695A.link:3017', '490000235C.link:3068', '490000089A.link:823', '490000252X.link:86', '490000078Q.link:1239']
list(n.schedule["17732"].routes())[0].network_links
['3017', 'artificial_link===from:21665081===to:5434424322', '3068', 'artificial_link===from:3519133221===to:108045', '823', 'artificial_link===from:3079462268===to:4543005956', '86', 'artificial_link===from:25714232===to:4543005959', '1239']