University of Twente Student Theses


Calibrating route set generation by map matching GPS data

Fafieanie, M.E. (2009) Calibrating route set generation by map matching GPS data.

[img] PDF
Abstract:Motivation Every person on earth is faced with the daily need of transportation. The enormously increasing travel demand results in traffic problems, like the daily congestion on the highways. Traffic models have been developed to support decision making, which is trying to solve these problems with transportation policy, planning, and engineering. One of the traffic models is the widely used four-step model. This model generates trips, distributes these trips, chooses a modal split and finally makes an assignment of the traffic throughout the model network. The route choice is modeled by generating a route choice set and then an application of a discrete choice model. The route choice set contains a set of “relevant” routes. For each OD-pair a choice set is constructed. The route choice set has to include all relevant routes, as routes that have not been created, cannot be chosen in the route choice. Also, it is not advisable to include all available routes, because this results in an enormous computation time and there is no route choice model that can deal correctly with large route choice sets. Therefore, we will calibrate the generation of route choice sets by using observed routes abstracted from GPS data. Problem definition The current problem is that we do not have insights in the performance of the route set generation. It is interesting to know whether the choice set includes all relevant routes between an OD-pair. The route set generation is relative complex and uses many different parameters. We want to find an “optimal” parameter set that includes as many as possible observed routes, but also takes care of the route set size and the inclusion of nonmotorway routes. Literature shows that non-motorway routes are often not included in a route set, even though these routes are often used to avoid congestion. The observed routes could also be used to determine why routes are not included and how the route set generation can be improved. All this will be investigated in this research. Methodology The research consists of two parts, first we have to obtain observed routes and thereafter the actual calibration will be performed. In order to obtain observed routes, we have to connect the GPS data with a model network. For this, a so-called map matching algorithm has to be implemented and calibrated. A literature study will be performed to investigate several map matching algorithms. Then a good algorithm will be selected based on the quality and calculation speed of the algorithm. The selected algorithm will be calibrated with a small portion of the GPS data to obtain a high matching quality and finally performed on all GPS data. The obtained map matched routes do not have to be relevant, therefore several filters are applied on this set of matched routes to create a set of relevant observed routes. iv The observed routes will be used in the second part of this research. We assume that all observed routes are relevant and have to be included in the generated route sets. The observed routes also represent other relevant routes, which are not part of the observed routes. The purpose is to find a parameter set that maximizes the number of observed routes in the generated route set. An observed route does not have to be exactly the same as a generated route, because small deviations on local roads are not considered important. Because of this, the generated routes are filtered after the route set generation and not all the relevant routes are included, as another relevant route may be almost the same. Besides the main parameters, two other criteria are used. At first, an average maximum of five routes per route set is allowed to prevent large route sets with the belonging disadvantages. In case that two parameter settings results in the same distance measure, the average number of routes is decisive. Another criterion is that ten important observed routes have been selected, which must be included in the final route set. Results The results will discussed in two parts, the map matching results and the calibration of the route set generation. The investigation of several map matching algorithms founds that Marchal (2004) is the most efficient and fastest algorithm (450 GPS points/s) to map match the GPS data. The purpose of the algorithm is to have a set of paths and choose the path that minimizes the distance between the GPS points and the matched route. The algorithm matches 89% of the routes correctly, which results in 2505 observed routes. These routes are investigated and finally 2136 routes are determined to be relevant for the calibration process. The calibration of the route set generations also consists of two parts. First, the route set generation filters are determined by using the observed routes. For this, we investigated the observed routes and set the filter parameter values such that they will not remove the observed routes. Second, the calibration of the route set resulted in two parameter combinations that have an equal value for the distance measure and for this the average number of routes is used to select the optimal parameter set. This parameter set results in a route set generation which includes 89% of the observed routes with an average of 5.03 routes per OD-pair. An investigation of the observed routes that are not included shows that most routes are filtered because of the maximum number of routes criterion. As it is, too many irrelevant routes are generated, resulting in large route sets, as the current filters still accept many irrelevant routes. Conclusions and recommendations This research presents a proper method to use observed routes to calibrate the route set generation. The implemented map match algorithm of Marchal satisfies the expectations and is considered as a proper method to map match GPS data efficient. One important improvement is performed and several improvements are suggested to achieve better map match results. A suggested improvement to reduce the calculation time is to use less GPS v points, because our investigations show no quality drawback when less GPS points are used. The performed calibration of the route set generation shows that even the “optimal” parameters cannot include all relevant routes. Several improvements are suggested, which could increase the match percentage. Most important is the use of distance instead of travel time for the filtering of routes. The travel time could not deal with different irrelevant routes on local roads and accepts these routes incorrectly. It is recommended to investigate the possibilities of using GPS data for the calibration of traffic models or parts of this (e.g. junction modeling) and maybe to be input for traffic models (e.g. replace the traffic movement questionnaires or trip generation). In theory, the steps of the four-step model could be replaced by observed routes if there are enough routes to represent the entire route set. For this case, a method to rescale these routes to coming traffic situations has to be developed (e.g. prediction for the year 2020). At last, GPS data could support traffic research by supplying information about travel times, speeds, departure times and bottlenecks in the network.
Item Type:Essay (Master)
Goudappel Coffeng
Faculty:ET: Engineering Technology
Subject:55 traffic technology, transport technology
Programme:Civil Engineering and Management MSc (60026)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page