An open-source, cross-platform, lightweight, and fast Python MapMatching4GMNS engine for mapping GPS traces to the underlying network using General Modeling Network Specification (GMNS). Its most likely path finding algorithm takes about 0.02 seconds to process one GPS trace with 50 location points in a large-scale network with 10K nodes.
Project description
Matching2Route
Please send your comments to xzhou74@asu.edu if you have any suggestions and questions.
Based on input network and given GPS trajectory data, the map-matching program of Matching2Route aims to find most likely route in terms of node sequence in the underlying network, with the following data flow chart.
The 2D grid system aims to speed up the indexing of GSP points to the network. For example, a 10x10 grid for a network of 100 K nodes could lead to 1K nodes in each cell. We first identify all cells traveled by a GPS trace, so only a small subset of the network will be loaded in the resulting shortest path algorithm.
The link cost estimation step calculates a generalized weight/cost for each link in the cell, that is, the distance from nearly GPS points to a link inside the cell. The likely path finding algorithm selects the least cost path with the smallest generalized cumulative cost from the beginning to the end of the GPS trace.
- Data flow
| Input files | Output files |
|---|---|
| node.csv | agent.csv |
| link.csv | |
| input_agent.csv |
-
Input file description
File node.csv gives essential node information of the underlying (subarea) network in GMNS format, including node_id, x_coord and y_coord.
File link.csv provides essential link information of the underlying (subarea) network, including link_id, from_node_id and to_node_id.
Input trace file as input_agent.csv. The geometry field describes longitude and latitude of each GPS point along the trace of each agent. In the following example there are exactly 2 GPS points as the origin and destination locations, while other examples can include more than 2 GPS points along the trace. The geometry field follows the WKT format.
https://en.wikipedia.org/wiki/Well-known_text_representation_of_geometry
-
Output file description
File agent.csv describes the most-likely path for each agent based on input trajectories.
Features:
1: The grid size is dynamically calculated based on the number of nodes per cell. 2: To avoid complex data folder settings, please always first assume work on the current directory.
Challenges:
1: The boundary identification might still have issues. 2: Outputing matched time and delay information is needed for traffic performance evaluation.
Reference:
This code is implemented based on a published paper in Journal of Transportation Research Part C:
Estimating the most likely space–time paths, dwell times and path uncertainties from vehicle trajectory data: A time geographic method
https://www.sciencedirect.com/science/article/pii/S0968090X15003150
