Transit Map-Matching algorithm#
Map-matching transit routes to a roadway network is not a new concept, and it has been incorporated in commercial modelling platforms, as well as integrated modeling frameworks such as Polaris and MATSim.
The potential impact of model the map-matching results in the traditional modeling is substantially different than it is with integrated modeling, as interactions between transit vehicles and other vehicles traversing the network may cause substantial additional issues during model run.
It is also odd that the algorithms currently available in the network focus on complete networks rather modeling ones, which are usually simplified by removing most local links, including many through which transit services are routed.
Additionally, the treatment of transit routes that go beyond the network at hand is also omitted in the algorithms currently available, which hinders their application to the modeling of regions connected to outside areas through long-distance transit lines, particularly rail.
Existing algorithms also require only one stop per link, which is unrealistic in the outskirts of modeling areas where the networks tend to be very sparse and links very long.
Methodology#
The methodology proposed here is similar to Poletti (2017) & Li (2012), as it leverages path computation through the network to connect successive stops alongside the route while trying to minimize the total length of the map-matched route and its connectivity.
Building the graph#
Other researchers have tackled the map-matching problem by focusing on an abstract graph composed by the road network and transit stops, but they have stopped short from breaking the network to introduce access points through which each stop would “access” the network, choosing to treat the underlying network links as monolithic elements.
As we will need in the experiment results when we analyse the computational time of each one of the algorithm components, breaking links at each stop’s projection point is extremely expensive, rivaling the time consumed for the path-computation part of the algorithm, normally the most computationally expensive part of the algorithms currently available in the literature.
MENTION NON-LINEAR DISTANCE FOR CONNECTORS AND POTENTIAL FOR CALIBRATION
Minimum total cost principle#
As stated by Li (2012) and echoed by Poletti et al(2017), it is reasonable to assume that a stop that, given its location, could be in reality located along different links, would most likely be located off the link that minimizes the total length of the route.
Map-matching algorithm#
1. Apply discounts to the graph corresponding to the most likely links (particularly important when we have the shape of the routes from the GTFS feed)
Starting from the first stop
2.a. Identify all “access points” AP to the stop n+1 on the route 2.b. Compute the shortest path tree with origin in the previous stop 2.c. Record the distance from the previous stop to each point p in AP 2.d. Compute the path from each access point p in AP to stop n+2 2.e. Compute the composite distance CD for each access point p in AP as the distance from stop n to p plus distance from p to stop n+2 2.f. Define path from stop n to stop n+1 as the path through connection p corresponding to the minimum distance in CD.
Computational efficiency tricks#
Caching the graph to disk for repeated applications (hash-checking)
Memory-caching shortest path trees
Results#
INCLUDE SOME IMAGES (AND METRICS?)
References#
Poletti, F.; Bösch, P.M.; Ciari, F.; Axhausen, K.W. Public Transit Route Mapping for Large-Scale Multimodal Networks. ISPRS Int. J. Geo-Inf. 2017, 6, 268. https://doi.org/10.3390/ijgi6090268
Li, Jing-Quan; Match bus stops to a digital road network by the shortest path model. Transportation Research Part C: Emerging Technologies. Volume 22, June 2012, Pages 119-131