In the recent Sense Making and Insights Discovery project, project teams were tasked to analyze data from publicly available datasets like the LTA data mall and come up with EPN (Event Processing Network) designs to reduce the occurrences of traffic jams.

One area that our team wanted to explore was to look at how we can creatively exploit the speed band data to find interconnected roads and segments which can then be used in other areas of analysis or computation. For example, in a routing algorithm or finding correlations between neighboring segments of roads.

The speed band data is updated in five minutes’ intervals. The response contains attributes such as the road name, road category, speed band information and start and end location in latitudes and longitudes. Every road is made up of one to many segments and long roads like expressways may be broken up into hundreds of segments. There are more than 50000 segments in the whole of Singapore. We imported one slice of data into PostgreSQL database with the PostGIS plugin enabled, creating a line string geometry field out of the start and end latitude and longitude from the data.

To easily visualize the data in our database, we can export a shapefile from any tables in PostgreSQL with a geo column using the bundled PostGIS Shapefile Import/Export Manager tool. We can then import it into ArcGIS or MapShaper (http://mapshaper.org/).

map1

In our first attempt, we realized that there are some gaps between roads. To help the intersection work better, we created a three-meter buffer around each road segment line string. The effect can be seen from the zoomed in figure below.

intersections

Intersections can now be easily found by running the ST_Intersect SQL command on the table. (http://postgis.net/docs/ST_Intersects.html)

Having found intersections, we proceeded to generate a graph database for both road and road segment levels. We used the python library networkX (https://networkx.github.io/) for creating the graphs and Graphviz (http://www.graphviz.org/) for visualization.

The road graph below is created using Graphviz using the sfdp (scalable force directed placement) command to layout the nodes. It contains all the roads in Singapore and contains about 4000 nodes. The red nodes are expressways and the green ones are major arterial roads.

graph

With the graph object, we can now perform some queries easily, for example if we wanted to find the roads that are connected to Heng Mui Keng Terrance (the road outside ISS):

neighbors = G.neighbors(‘HENG MUI KENG TERRACE’)

We can also get the segment level view.

graph2

After all the pre-processing, we are now ready to make use of our graph objects. In our EPN, we have proposed using the speed band information to help in routing vehicles in the event of a traffic jam or accident. If you look at the road segment graph, you can see that compared to the road graph, it is both directed and weighted. As we can easily find the distance for each road segment and we also have the speed band at any given time from the speed band data, we can use this information to derive the estimated time to travel across the segment at any given time. Using this as the weight, we can then find the shortest path (in terms of time to travel) between any two nodes in the graph using any shortest path algorithm like Dijkstra’s algorithm.

Another analysis that we can do is that we can find correlations between neighboring road segments in the graph to derive some insights. As mentioned earlier, there are more than 50000 road segments and it might be infeasible to perform correlation analysis on all the segments, especially since we are looking across time. For example, we might collect data across five days which results in 1440 data points for a single segment. It would probably make more sense (statistically and computationally) to zoom into clusters of segments of interest and look at correlations there, which can be done by getting n degrees of neighbors.

This is a short excerpt from our project and highlights some of the work done, thanks for reading.

By Team 5 (Chan Chia Hui, Randy Phoa and Zay Yar Lin)

 

Advertisements