Congestion Modelling

Congestion Modelling

Abstract:

Recently a vast amount of geographic information system (GIS) data make road networks around the world as polylines with attributes. The shapefile format is a popular geospatial vector data format for geographic information system (GIS) software.

This paper displays congestion on our development of a GIS-based traffic network analysis system based on shapefiles which provides a graphical analysis platform to transportation planners and researchers for analysis of real time congestion on roads.

Various vehicle types are fitted with GPS and the real-time GPS data is received on back-end server which is then converted to find the speed of polyline. Many polyline combines to form road networks and this displays speed of the polylines and thus roads.

The speed of the road is then displayed graphically depicting different colours to predict congestion on road. This is useful for the analysis of large traffic network where the detailed local network structures of some intersections have to be taken into account.

The system links great volumes of traffic data and geography information data accumulated for visualization and traffic analysis. The system also enable us to predict heavy traffic jams in city  and helps us in showing traffic status at a geo-location. The model also involves complex and real time calculation of GPS data which is received every few seconds for all polylines of the city.

1. Introduction:

Traffic is also a global challenge with a direct impact on the economy, energy consumption, and the environment in today’s society. Congestion Modelling is a key tool to address both the challenges of traffic and its visualization. It takes place on a complex domain and realistic road networks. The main objective of this work is to create road network representations (a heatmap) from polyline and shapefile data that can be used directly for real-time traffic visualization.

Digital representations of real-world road networks are commonly available, but the level of detail of these data is not immediately usable for many queries related to traffic display. Traffic display take place on a network of lanes. This network needs to be represented with all its details, including the number of lanes on a road, intersections, merging zones, and ramps.

Optimizing vehicle routes in the context of current road congestion’s can reduce fuel consumption and transportation time. Maximizing the load of each vehicle in a transport company depending on route, will reduce the amount of trips per goods. Real time display of traffic can assist existing route guidance systems by predicting problems such as congestion. Accurate predictions require accurate status information about vehicles – the fact that vehicles are distributed over large-scale road infrastructure makes this particularly challenging but since the study has GPS fitted in all autos , buses , utility vehicles in the city makes the task easy and accurate.

The consideration of the influence of traffic volumes on travel times, and consequently on route choices of travelers based on congestion information can reversely change traffic volumes.

GIS data of road networks in form of shapefiles and polylines are intended to create heatmap of city which displays accurate information for intersections, ramps, and road geometries. The GPS data as available require filtering in order to be processed and mapped to specific polylines. These road networks are large in scale, and so efficient algorithms and implementations are required. The scale of the implementation itself is a challenge as this project is a combination of multiple systems, a road network importer, a road network representation, GPS  data filtering system , GPS data mapping system ,congestion calculation system, trip planner system and a visualization system.

The idea in this study is to consider active vehicles in the traffic as agents, which send traffic reports to a centralized server via GPS device using GPRS. A centralized server behaves as an agent which collects data from vehicle agents and estimates average traffic flow speed for each road piece on the map. The vehicles are able to retrieve real-time traffic flow speed of a specific set of road pieces when they wish to plan a route between two points. The purpose of the study is to investigate if route planning based on real-time data is more effective and efficient than route planning based on static and statistical traffic data and to display congestion choke points in the city.

2. Related work

While digital road networks are widely available, the amount of detail varies widely across sources.

Data for North America and Europe are freely available from the US Census Bureau’s TIGER/Line database and ―crowd-sourced‖ community projects like OpenStreetMaps, but these data sets contain polyline roads with minimal attributes–information about lanes and intersection structure is wholly missing. Commercially available data sets, such as those provided by NAVTEQ, often contain some further attributes, such as the lane arrangements at intersections, but they are expensive to obtain, the techniques used are not known, and they do not capture all of the desired detail.

Numerous methods have been proposed for automatic and semiautomatic GIS road extraction from aerial and satellite images. These methods are complementary to our work: the GIS network we assume as input could be the product of a satellite image extraction method.

Procedural modelling of cities and roads has been an active area of research interest in computer graphics. Commercial procedural city modelling software is also available. In our work, we construct the geometry for every lane, not just the roads; numerous spatial representations of curves have been developed over the years. Our method relies solely on coordinate frames, sins, and cosines.

3. The proposed method

3.1 PRELIMINARIES

Queues of autos/buses/utility vehicles, represented as discrete agents. For traffic modelling, lane geometry is irrelevant as long as speed limits are available .These limits are used for assigning default speed values for a lane if traffic data is not available for a stretch for a lane. How-ever, geometry matters for visualization and for localizing GPS transmissions data sent to inform about traffic conditions. These lanes are connected in various ways to form a road network, and vehicles traverse these connected lanes by crossing intersections and merging between adjacent lanes. The creation of the network of lanes also entails determining the topological relationships between lanes (so that vehicles can change lanes and take on and off-ramps)

3.2 GIS DATA FILTERING

We filter the GIS data we use to remove the most commonly occurring errors. These changes are not meant to change the underlying geometry or topology of the network, only to correct sloppy data creation.

The first filter includes ensuring that one way roads are defined in the correct direction and that roads have been assigned the correct classification. The second filter removes GPS Data which is not latest. GPS data is determines as latest by dividing the entire day into slots of 2 minutes and if GPS data timestamp doesn’t belong to current or previous slot then it is rejected. Another filter rejects data if geo location of vehicle is reported outside the bounding box of the city or latitude-longitude is received as an ambiguous value like zero, negative. Another filter rejects data if vehicle speed value received is beyond a range. This speed limit check is configurable and is configured to different values based on road type and geo-spatial locality of the vehicle. Another filter rejects GPS data, if vehicle number of the vehicle is ambiguous. Further filtering includes based on heading of the vehicle data, if heading is received as less than equal to zero or greater than equal to 360 degree then the data is filtered out and not accepted.

Above ambiguities in GPS data could be due to an incorrect error handling at GPS device end or while transfer of these attributes in GPRS transmission. GPS data is parsed to generate following

The common formulations for traffic modelling are lane-based. These lanes are treated as parameters: vehicle type, vehicle number, latitude, longitude, altitude, speed, time, heading , on trip,ignition on/off, latest/history packet.

3.3 THE PROPOSED COMPONENTS

We have implemented heat map in C# using Maps-tool(a software purchased from 3rd Party).These heat maps are then further populated with shape files purchased from 3rd party vendor . Implementation of algorithms for GPS data parsing ,data filtering , data mapping and congestion calculation and representation of a speed for a polyline is done supporting object oriented paradigm in C++.The GPS data after being parsed is stored in relational SQL Server database tables. Required procedures are implemented in sql for writing final data in required formats to database table which is then read from c# code for congestion display on heat map. This congestion data along with its all attributes are algorithmic-ally used in creating a web service which displays congestion choke points in city showing traffic jams for last k minutes.

Map for the entire city is constructed very first time the binary is run. Polylines are created from shapefiles using gdal library api’s. A bounding box for the city is calculated from these polylines and GPS alerts mapping to this location is only considered. Polylines are the split based on if it is one way or two way. Maximum length considered for a poly-line is 500 meter , this helps in having more accurate data for even smaller section of the road.A hash-map is prepared from poly-lines end points. Point of interests (poi’s) are selected from this hash-map. These poi’s are then transformed to graph nodes and graph edges are initialized. Then nodes are initialized by adding directional edges to these nodes. This way entire city road network is mapped to a graph. This graph is then persisted to relational database with separate tables for storing nodes and edges information. If the binary is run again, then this entire process of constructing graph is skipped and the graph is loaded from the database itself.

3.4 DATA STRUCTURE

The characteristics of the geospatial data set are changing. First and foremost, in order to meet users demands effectively, the capacity for the real-time collection, synthesis and access must exist; data import and export is essential. In the general structure of GIS, spatial data can be divided into three groups:

1) geometric data – data for describing space characteristics of spatial data, also known as location data, positioning data;

2) attribute data– data for describing attributes of spatial data such as type, grade, name, status, and so on;

3) relational data –data for describing topological relationship between spatial data.

These three data groups are stored in separate tables in conventional GIS. In this study, the geometric data and relational data are placed in a unified data management table. The layer manager extracts data from data file in accordance with the requirements of the system, forms a graphic layer with the data of the geometric table, and then loads the required layer attribute data, and loads them into memory to output the required layer.

In C++, maps are used to construct the road network of the city. Each polyline end-points are stored as nodes of the graph and polylines/lanes are stored as the edge of the graph. Each node also stores number of incoming and outgoing edges as vector of edges. Each node and edge is assigned an id.

Starting node and ending node of an edge is stored. List of polylines that constitute the edge is represented as the vector of polylines. Other details like number of lanes, width, and road type is also maintained for the edge. Road type is classified as highway, collector, and colony roads. Travel time for an edge can be estimated based on speed and length of the polylines constituting the edge.

A stl map is maintained for polyline to vehicle Alert Map where vehicle Alert Map is another stl map for maintaining vehicle number to list of alert received. Finally a map is maintained which stores all polylines to vehicle Alert Map in a slot id. This map is continuously filled for current slot with vehicle details (all speed alerts generated from raw GPS data) and polyline mapping.

GPS data is stored in a queue unless it is parsed, filtered and converted to an alert with required information like vehicle type, vehicle speed, time slot, mapped polyline and heading. A map is created for default speed values based on the width and type of road.

3.5 DATA PROCESSING

GPS data is received every k seconds from buses, autos and utility vehicles. After parsing data, the filtered data is temporary stored in a map data-structure. (A map for storing all polyline to vehicle Alert Map in a slot id.)Every t minutes, this map values are retrieved and updated in database. Firstly, Polyline vector for current slot id is retrieved. If sufficient alerts are received on a polyline for a sliding window (here sufficient alerts is a configurable parameter and set to m for this experiment and sliding window is also configurable and set to M) which means that if sufficient number of alerts are received in M previous time slots including current (each slot t minutes) on a polyline then only that polyline is considered for congestion calculation in that slot. Another criteria when a polyline is considered for a slot is if it receives alerts from at least p distinct vehicles.

For congestion calculation, represented speed of each vehicle for a polyline is calculated by removing outliers and then taking average of all speed for a vehicle. Represented speed for a polyline is calculated by taking weighted average of represented speed of each vehicle and weightage depends on the vehicle type and number of alerts from each vehicle. A general weightage calculation includes taking average by considering weightage as number of alerts for each vehicle type. So if there are 3 alerts from autos and 2 from buses, then final values has weightage of auto and bus speed in the ratio 3:2.

A distributed system is built by running separate executables for receiving feeds from different vehicle and updating separate tables in same relational database in parallel. Special checks are added to exclude cases like autos standing and weighting for the customers, buses standing at bus stops and vehicles gathered at a traffic signal.

Along with the live congestion calculation, alerts are also stored as previous history in database every s minutes where all polyline that receives sufficient number of alerts are inserted into the table.

Here the speed of polyline is not updated but inserted every s minutes which helps in storing past congestion information in database and these tables grows rapidly with time. This data is used in displaying past congestion for a location on a particular day. Along with it this data is used in predictive modelling for predicting congestion in future for a time-slot. This data is only kept in memory for last q/k slots that means only for q minutes.

4 Experiments

Congestion on all arterial, collector and highway roads for a city is calculated and displayed except the colony roads as in colony roads there are not many vehicles that we get a feed from at a time. On comparison with google map congestion, it was found that congestion displayed more accurately (field-tested) and on many roads which was not shown on google and other similar products.

Congestion Speed is calculated more accurately as live GPS data from almost 1 lakh  vehicles are combined to get the speed of polyline.

5 Conclusions

I have presented a method for transforming GIS data into a topological and geometric representation suitable for use in traffic display. Our geometric representation of roads is visually smooth and congestion is displayed discretely. The congestion calculated is also ised in

References

[1] Mena J 2003 State of the Art on Automatic Road Extraction for GIS Update: A Novel Classification

Pattern Recognition Letters 24 3037-58

[2] projekter.aau.dk/projekter/files/61070977/1181652577.pdf

[3] vldb2005.org/program/paper/fri/p853-brakatsoulas.pdf

[4] Treiber M, Hennecke A, Helbing D 2000 Congested Traffic States in Empirical Observations and

Microscopic Simulations Physical Rev E 62(2) 1805-24

[5] Sewall J, Wilkie D, Merrell R, Lin M 2010 Continuum Traffic Simulation Computer Graphics

Forum 29(2) 439-48

[6] Maps.google.com

[7] Traffline.com

[8] personal.cege.umn.edu/~liu/ce8217/Wardrop_1952.pdf

[9] graphics.eiu.com/files/ad_pdfs/eiu_ibm_traffic_wp.pdf

[10] nber.org/papers/w15376.pdf

[11] rff.org/rff/Documents/RFF-DP-08-35.pdf

[12] rff.org/Documents/RFF-DP-03-56.pdf

[13] econ.ucsb.edu/~tedb/Courses/Ec1F07/traffic.pdf

[14] vtpi.org/tca/tca0505.pdf

[15] discovery.ucl.ac.uk/1259/1/2004_25.pdf

[16] bath.ac.uk/e-journals/jtep/pdf/Volume_XXV1_No_3_213-243.pdf

Leave a Reply

Your email address will not be published. Required fields are marked *