-
Notifications
You must be signed in to change notification settings - Fork 9
Usage: 4.3. Using Network: 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.
from genet import read_matsim
import os
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: Name:
Type: MultiDiGraph
Number of nodes: 1662
Number of edges: 3166
Average in degree: 1.9049
Average out degree: 1.9049
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'})2022-07-14 15:40:37,681 - Checking `linkRefId`s of the Route: `VJ375a660d47a2aa570aa20a8568012da8497ffecf` are present in the graph
2022-07-14 15:40:37,685 - Rerouting Route `VJ375a660d47a2aa570aa20a8568012da8497ffecf`
2022-07-14 15:40:37,784 - 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.
n.route_service('20274', additional_modes={'car'})2022-07-14 15:40:40,387 - Routing Service 20274 with modes = {'bus'}
2022-07-14 15:40:40,429 - Building Maximum Stable Set for PT graph with 8 stops and 6 edges
2022-07-14 15:40:40,896 - Passing problem to solver
2022-07-14 15:40:40,898 - Initializing ordered Set vertices with a fundamentally unordered data source (type: set). This WILL potentially lead to nondeterministic behavior in Pyomo
2022-07-14 15:40:40,915 - Passing problem to solver
2022-07-14 15:40:41,597 - Stop ID changes detected for Routes: {'VJ375a660d47a2aa570aa20a8568012da8497ffecf', 'VJ6c64ab7b477e201cae950efde5bd0cb4e2e8888e', 'VJ812fad65e7fa418645b57b446f00cba573f2cdaf'}
2022-07-14 15:40:41,601 - Changed Route attributes for 3 routes
2022-07-14 15:40:41,608 - 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 abov
unsnapped_service_ids = n.route_schedule(services=['20274', '15660'])2022-07-14 15:40:41,615 - Building Spatial Tree
2022-07-14 15:40:43,833 - Extracting Modal SubTree for modes: {'bus'}
2022-07-14 15:40:43,882 - Routing Service 15660 with modes = {'bus'}
2022-07-14 15:40:43,884 - Building Maximum Stable Set for PT graph with 5 stops and 3 edges
2022-07-14 15:40:44,283 - This Maximum Stable Set Problem is partially viable.
2022-07-14 15:40:44,284 - 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.
2022-07-14 15:40:44,285 - Passing problem to solver
2022-07-14 15:40:44,286 - Initializing ordered Set vertices with a fundamentally unordered data source (type: set). This WILL potentially lead to nondeterministic behavior in Pyomo
2022-07-14 15:40:44,288 - Passing problem to solver
2022-07-14 15:40:44,383 - Successfully snapped 4 stops to network links.
2022-07-14 15:40:44,408 - Routing Service 20274 with modes = {'bus'}
2022-07-14 15:40:44,410 - Building Maximum Stable Set for PT graph with 8 stops and 6 edges
2022-07-14 15:40:44,673 - Passing problem to solver
2022-07-14 15:40:44,674 - Initializing ordered Set vertices with a fundamentally unordered data source (type: set). This WILL potentially lead to nondeterministic behavior in Pyomo
2022-07-14 15:40:44,677 - Passing problem to solver
2022-07-14 15:40:44,790 - Stop ID changes detected for Routes: {'VJ375a660d47a2aa570aa20a8568012da8497ffecf', 'VJ6c64ab7b477e201cae950efde5bd0cb4e2e8888e', 'VJ812fad65e7fa418645b57b446f00cba573f2cdaf', 'VJ3716910ec59c370d9f5c69137df7276b68cf0a08', 'VJ1cf651142378958b52229bfe1fa552e49136e60e', 'VJf2e0de4f5dad68cb03064e6064e372dde52cc678'}
2022-07-14 15:40:44,804 - Changed Route attributes for 6 routes
2022-07-14 15:40:44,813 - Added 1 nodes
2022-07-14 15:40:45,325 - Generated 0 link ids.
2022-07-14 15:40:45,341 - Added 2 links
2022-07-14 15:40:45,364 - 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')2022-07-14 15:40:45,436 - Added 0 nodes
2022-07-14 15:40:45,858 - Generated 0 link ids.
2022-07-14 15:40:45,866 - Added 8 links
2022-07-14 15:40:45,869 - Changed Stop attributes for 10 stops
2022-07-14 15:40:45,874 - 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].route['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']