Map Routing Service

[imartinezl]

• Define functionalities
• Create map file

[doorleyr]

The routing service only needs to find routes between the Blue Bike stations, right? Or does it also need to find routes between arbitrary locations in the city?

There are only ~400 stations so it may be more efficient to pre-cook each route as a sequence of nodes and save the results as a file. Then, the routing service would simply look up the route by origin and destination.

What is the required format of the returned routes? I'm thinking it should be a list of lon, lat coordinates with the cumulative distance along the route. eg.

[
[-71.1, 43.25, 0], 
[-71.5, 43.24, 100], 
[-71.7, 43.23, 175], 

...
]

[NaroaCS]

Hi @doorleyr,

The routing needs to calculate routes from any location, because we will also be simulating dockless and autonomous bicycles so the route can start from any point. As for the format of the return, I think it makes sense to have that structure.

Thanks!

[doorleyr]

Ok I added a Router class with d13c750 Let me know if the usage us clear. The network had to be pretty large to include all of the Blue Bike stations, so if you are doing very frequent requests, performance may become an issue. If that's the case, we can think of some ways to optimise.

[imartinezl]

Hi @doorleyr ,

Thank you so much for your contribution! The usage is very clear and I believe the Network class covers all functionalities needed for the simulation. Yep, the network is pretty large. At this moment performance is not a priority, but in case the simulation is slowed down to an unsuitable point, further optimization will be necessary. Totally agree on that.

[imartinezl]

Hi @doorleyr ,

A quick note on possible performance issues you previously commented:

Ok I added a Router class with d13c750 Let me know if the usage us clear. The network had to be pretty large to include all of the Blue Bike stations, so if you are doing very frequent requests, performance may become an issue. If that's the case, we can think of some ways to optimise.

@NaroaCS has been testing an initial version of the simulator and has found a performance issue when doing very frequent requests. For instance, when the user wants to select a bike-station, it has to find which one is the closest to its current location, and for that the shortest path length is needed to every station. Even though a subset of stations can be used (by removing stations that are too far away in the kd-tree of nodes), the number of users n the simulation would make the a very slow run of the simulation.

The following table summarizes a benchmark of some libraries that I have found.

library	method	backend	time shortest path (sec)	time shortest path to 300 stations (sec)
networkx	dijkstra_path	python	0.1	25
networkx	dijkstra_path_length	python	0.06	17
networkx	bidirectional_dijkstra	python	0.07	16
igraph	shortest_paths	c++	0.012	2.5
pandana	shortest_path_length	c++	0.009	2
pandana	shortest_path_lengths	c++	-	0.05

The fastest option in this benchmark is the vectorized function shortest_path_lengths of the pandana library, which implements contraction hierarchies + bidirectional dijkstra algorithm. As you have much more experience on this matter, it would be great to know your impressions, and expand this list with more libraries that can help on the shortest path problem performance-wise, or, look for other alternatives as well.

Thanks!

[doorleyr]

Hi @imartinezl, Pandana may be the best option. However, we may be able to reduce the computation time much more by doing some pre-cooking. For example, we could run a script which finds the closest station to every H3 cell in the simulation area and saves the results as a table. Then during the simulation runs, when a user needs to choose a station, they simply check which h3 cell they're in and then lookup the closest station- no need to check all the routes. What do you think?

[NaroaCS]

Thanks @doorleyr and @imartinezl ! We can discuss this on Tuesday if you want. Also, I'm pasting here a No Path error that I'm sometimes getting.

Traceback (most recent call last): File "C:\Users\Naroa\Anaconda3\envs\py3\lib\site-packages\networkx\algorithms\shortest_paths\weighted.py", line 744, in multi_source_dijkstra return (dist[target], paths[target]) KeyError: 27209

During handling of the above exception, another exception occurred:

Traceback (most recent call last): File "c:/Users/Naroa/Desktop/AutonomousBicycleSimulation/BikeFleetSimulation.py", line 380, in process [station, station_location, visited_stations]=self.select_start_station(self.location,self.visited_stations) File "c:/Users/Naroa/Desktop/AutonomousBicycleSimulation/BikeFleetSimulation.py", line 420, in select_start_station selected_station_info=self.datainterface.select_start_station(location,visited_stations) File "c:/Users/Naroa/Desktop/AutonomousBicycleSimulation/BikeFleetSimulation.py", line 608, in select_start_station distance = self.dist(location, station.location) File "c:/Users/Naroa/Desktop/AutonomousBicycleSimulation/BikeFleetSimulation.py", line 596, in dist route=network.get_route(a[1], a[0], b[1], b[0]) File "c:\Users\Naroa\Desktop\AutonomousBicycleSimulation\Router.py", line 97, in get_route node_path=self.get_node_path(o_node, d_node) File "c:\Users\Naroa\Desktop\AutonomousBicycleSimulation\Router.py", line 82, in get_node_path node_path=nx.dijkstra_path(self.G,o_node, d_node, 'weight') File "C:\Users\Naroa\Anaconda3\envs\py3\lib\site-packages\networkx\algorithms\shortest_paths\weighted.py", line 167, in dijkstra_path weight=weight) File "C:\Users\Naroa\Anaconda3\envs\py3\lib\site-packages\networkx\algorithms\shortest_paths\weighted.py", line 480, in single_source_dijkstra weight=weight) File "C:\Users\Naroa\Anaconda3\envs\py3\lib\site-packages\networkx\algorithms\shortest_paths\weighted.py", line 746, in multi_source_dijkstra raise nx.NetworkXNoPath("No path to {}.".format(target)) networkx.exception.NetworkXNoPath: No path to 27209.

The above exception was the direct cause of the following exception:

Traceback (most recent call last): File "c:/Users/Naroa/Desktop/AutonomousBicycleSimulation/BikeFleetSimulation.py", line 811, in env.run(until=1000) File "C:\Users\Naroa\Anaconda3\envs\py3\lib\site-packages\simpy\core.py", line 137, in run self.step() File "C:\Users\Naroa\Anaconda3\envs\py3\lib\site-packages\simpy\core.py", line 229, in step raise exc networkx.exception.NetworkXNoPath: No path to 27209.

[imartinezl]

Hi @NaroaCS

At https://github.com/NaroaCS/AutonomousBicycleSimulation/commit/f077b204696d130bde523f37e061b5ff3dbfb73d you can find an adaptation of the Network.py class from Networkx to Pandana library. To be clear with names, this new file is called Graph.py, instead of Network.py.

The next step should be to adapt the existing simulation source code to this new class. I already created the same get_route(from_lon, from_lat, to_lon, to_lat) method, but we could also discuss other additional functions to optimize certain tasks. In this sense, maybe introducing an auxiliary class, as proposed at Location could help us managing all the locations of bikes, users, etc.

[NaroaCS]

Hi @imartinezl,

As we mentioned the other day, we should change the way we choose the nearest station by implementing a spatial tree first and identifying the closest 10 (or maybe less, like 5?) stations using linear distance. Ref here And, after that, make a single call to Pandana to get the distances to those stations.