Map-matching poor-quality GPS data in urban environments: the pgMapMatch package

Global Positioning System (GPS) data have become ubiquitous in many areas of transportation planning and research. The usefulness of GPS data often depends on the points being matched to the true sequence of edges on the underlying street network – a process known as ‘map matching.’ This paper presents a new map-matching algorithm that is designed for use with poor-quality GPS traces in urban environments, where drivers may circle for parking and GPS quality may be affected by underground parking and tall buildings. The paper is accompanied by open-source Python code that is designed to work with a PostGIS spatial database. In a test dataset that includes many poor-quality traces, our new algorithm accurately matches about one-third more traces than a widely available alternative. Our algorithm also provides a ‘match score’ that evaluates the likelihood that the match for an individual trace is correct, reducing the need for manual inspection.     

Determining structural route components from GPS traces

Analysis of GPS traces shows that people often do not use the least cost path through the transportation network while making trips. This leads to the question which structural path characteristics can be used to construct realistic route choice sets for use in traffic simulation models. In this paper, we investigate the hypothesis that, for utilitarian trips, the route between origin and destination consists of a small number of concatenated least cost paths. The hypothesis is verified by analyzing routes extracted from large sets of recorded GPS traces which constitute revealed preference information. Trips have been extracted from the traces and for each trip the path in the transportation network is determined by map matching. This is followed by a path decomposition phase for which the algorithm constitutes the first contribution of this paper. There are multiple ways to split a given path in a directed graph into a minimal number of subpaths of minimal cost. By calculating two specific path splittings, it is possible to identify subsets of the vertices (splitVertexSuites) that can be used to generate every possible minimum path splitting by taking one vertex from each such subset. As a second contribution, we show how the extracted information is used in microscopic travel simulation. The distribution for the size of the minimum decomposition, extracted from the GPS traces, can be used in constrained enumeration methods for route choice set generation. The sets of vertices that can act as boundary vertices separating consecutive route parts contain way points (landmarks) having a particular meaning to their user. The paper explains the theoretical aspects of route splitting as well as the process to extract splitVertexSuites from big data. It reports statistical distributions extracted from sets of GPS traces for both multimodal person movements and unimodal car trips.     

Analysis of consumer response to fuel price fluctuations applying sample selection model to GPS panel data: Dynamics in individuals’ car use

The effects of fuel price increases on people’s car use have been widely discussed during the last few decades in travel behavior research. It is well recognized that fuel price has significant effects on driving distance and driving efficiency. However, most of this research assumed that these effects are invariant across individuals and weather conditions. Moreover, intrinsic variability in people’s preferences has not been given much attention due to the difficulty of collecting the necessary data. In this paper, we collected detailed travel behavior data of 276 respondents in the Netherlands, spanning a time period between one week and three months using GPS logs. These GPS data were fused with weather data, allowing us to estimate both exogenous (such as weather and fuel price) and endogenous effects (inertia and activity plans) on individual’s car use behavior. To further understand the effects of fuel price on the environment, we estimated the effects of fuel price fluctuation on CO₂ emissions by car. The results show a significant degree of inertia in car use behavior in response to increased fuel prices. Weather and fuel price showed significant effects on individual’s car using behavior. Moreover, fuel price shows two-week lagged effects on individual’s travel duration by car.     

Vehicular Ad-Hoc Networks sampling protocols for traffic monitoring and incident detection in Intelligent Transportation Systems

Vehicular Ad-Hoc Networks (VANETs) are an emerging technology soon to be brought to everyday life. Many Intelligent Transport Systems (ITS) services that are nowadays performed with expensive infrastructure, like reliable traffic monitoring and car accident detection, can be enhanced and even entirely provided through this technology. In this paper, we propose and assess how to use VANETs for collecting vehicular traffic measurements. We provide two VANET sampling protocols, named SAME and TOME, and we design and implement an application for one of them, to perform real time incident detection. The proposed framework is validated through simulations of both vehicular micro-mobility and communications on the 68 km highway that surrounds Rome, Italy. Vehicular traffic is generated based on a large real GPS traces set measured on the same highway, involving about ten thousand vehicles over many days. We show that the sampling monitoring protocol, SAME, collects data in few seconds with relative errors less than 10%, whereas the exhaustive protocol TOME allows almost fully accurate estimates within few tens of seconds. We also investigate the effect of a limited deployment of the VANET technology on board of vehicles. Both traffic monitoring and incident detection are shown to still be feasible with just 50% of equipped vehicles.     

A Trip Reconstruction Tool for GPS-based Personal Travel Surveys

ABSTRACT

This article reports on the development of a trip reconstruction software tool for use in GPS-based personal travel surveys. Specifically, the tool enables the automatic processing of GPS traces of individual survey respondents in order to identify the road links traveled and modes used by each respondent for individual trips. Identifying the links is based on a conventional GIS-based map-matching algorithm and identifying the modes is a rule-based algorithm using attributes of four modes (walk, bicycle, bus and passenger-car). The tool was evaluated using GPS travel data collected for the study and a multi-modal transportation network model of downtown Toronto. The results show that the tool correctly detected about 79% of all links traveled and 92% of all trip modes.     

Within day rescheduling microsimulation combined with macrosimulated traffic

The concept of rescheduling is essential to activity-based modeling in order to calculate effects of both unexpected incidents and adaptation of individuals to traffic demand management measures. When collaboration between individuals is involved or timetable based public transportation modes are chosen, rescheduling becomes complex. This paper describes a new framework to investigate algorithms for rescheduling at a large scale. The framework allows to explicitly model the information flow between traffic information services and travelers. It combines macroscopic traffic assignment with microscopic simulation of agents adapting their schedules. Perception filtering is introduced to allow for traveler specific interpretation of perceived macroscopic data and for information going unnoticed; perception filters feed person specific short term predictions about the environment required for schedule adaptation. Individuals are assumed to maximize schedule utility. Initial agendas are created by the FEATHERS activity-based schedule generator for mutually independent individuals using an undisturbed loaded transportation network. The new framework allows both actor behavior and external phenomena to influence the transportation network state; individuals interpret the state changes via perception filtering and start adapting their schedules, again affecting the network via updated traffic demand. The first rescheduling mechanism that has been investigated uses marginal utility that monotonically decreases with activity duration and a monotonically converging relaxation algorithm to efficiently determine the new activity timing. The current framework implementation is aimed to support re-timing, re-location and activity re-sequencing; re-routing at the level of the individual however, requires microscopic travel simulation.     

Time of day intervals partition for bus schedule using GPS data

Time of day partition of bus operating hours is a prerequisite of bus schedule design. Reasonable partition plan is essential to improve the punctuality and level of service. In most mega cities, bus vehicles have been equipped with global positioning system (GPS) devices, which is convenient for transit agency to monitor bus operations. In this paper, a new algorithm is developed based on GPS data to partition bus operating hours into time of day intervals. Firstly, the impacts of passenger demand and network traffic state on bus operational performance are analyzed. Then bus dwell time at stops and inter-stop travel time, which can be attained based on GPS data, are selected as partition indexes. For buses clustered in the same time-of-day interval, threshold values of differences in dwell time at stops and inter-stop travel time are determined. The buses in the same time-of-day interval should have adjacent dispatching numbers, which is set as a constraint. Consequently, a partition algorithm with three steps is developed. Finally, a bus route in Suzhou China is taken as an example to validate the algorithm. Three partition schemes are given by setting different threshold values for the two partition indexes. The present scheme in practice is compared with the three proposed schemes. To balance the number of ToD intervals and partition precision, a Benefit Evaluation Index is proposed, for a better time-of-day interval plan.     

Large-scale transit market segmentation with spatial-behavioural features

Transit market segmentation enables transit providers to comprehend the commonalities and heterogeneities among different groups of passengers, so that they can cater for individual transit riders’ mobility needs. The problem has recently been attracting a great interest with the proliferation of automated data collection systems such as Smart Card Automated Fare Collection (AFC), which allow researchers to observe individual travel behaviours over a long time period. However, there is a need for an integrated market segmentation method that incorporating both spatial and behavioural features of individual transit passengers. This algorithm also needs to be efficient for large-scale implementation. This paper proposes a new algorithm named Spatial Affinity Propagation (SAP) based on the classical Affinity Propagation algorithm (AP) to enable large-scale spatial transit market segmentation with spatial-behavioural features. SAP segments transit passengers using spatial geodetic coordinates, where passengers from the same segment are located within immediate walking distance; and using behavioural features mined from AFC data. The comparison with AP and popular algorithms in literature shows that SAP provides nearly as good clustering performance as AP while being 52% more efficient in computation time. This efficient framework would enable transit operators to leverage the availability of AFC data to understand the commonalities and heterogeneities among different groups of passengers.     

Classifying the purpose of stopped truck events: An application of entropy to GPS data

This paper applies the concept of entropy to mine large volumes of global positioning system (GPS) data in order to determine the purpose of stopped truck events. Typical GPS data does not provide detailed activity information for a given stop or vehicle movement. We categorize stop events into two types: (1) primary stops where goods are transferred and (2) secondary stops where vehicle and driver needs are met, such as rest stations. The proposed entropy technique measures the diversity of truck carriers with trucks that dwell for 15 min or longer at a given location. Larger entropy arises from a greater variety of carriers and an even distribution of stop events among these carriers. An analysis confirms our initial hypothesis that the stop locations used for secondary purposes such as fuel refills and rest breaks tend to have higher entropy, reflecting the diversity of trucks and carriers that use these facilities. Conversely, primary shipping depots and other locations where goods are transferred tend to have lower entropy due to the lower variety of carriers that utilize such locations.     

Travel mode estimation for multi-modal journey planner

For route planning and tracking, it is sometimes necessary to know if the user is walking or using some other mode of transport. In most cases, the GPS data can be acquired from the user device. It is possible to estimate user’s transportation mode based on a GPS trace at a sampling rate of once per minute. There has been little prior work on the selection of a set of features from a large number of proposed features, especially for sparse GPS data. This article considers characteristics of distribution, auto- and cross-correlations, and spectral features of speed and acceleration as possible features, and presents an approach to selecting the most significant, non-correlating features from among those. Both speed and acceleration are inferred from changes in location and time between data points. Using GPS traces of buses in the city of Tampere, and of walking, biking and driving from the OpenStreetMap and Microsoft GeoLife projects, spectral bins were found to be among the most significant non-correlating features for differentiating between walking, bicycle, bus and driving, and were used to train classifiers with a fair accuracy. Auto- and cross-correlations, kurtoses and skewnesses were found to be of no use in the classification task. Useful features were found to have a fairly large (>0.4) correlation with each other.     

Validation of an agent based model using a participatory simulation gaming approach: The case of city logistics

Agent-based modeling is used for simulating the actions and interactions of autonomous entities aiming to assessing their effects on the system as a whole. At an abstract level, an agent-based model (ABM) is a representation of the many simple agents and interactions among them. The decision making of the agents is based on the rules given to them. In an ABM, the model output is the result of internal decision-making and may differ with alteration in the decision path. On the contrary, with the set of rules embedded in agents, their behavior is modeled to take a ‘certain action’ in a ‘certain situation’. It suggests that the internal decision making behavior of agents is truly responsible for the model output and thus it cannot be ignored while validating ABMs. This research article focuses on the validating agents’ behavior by evaluating decision-making processes of agents. For this purpose, we propose a validation framework based on a participatory simulation game. Using this framework we engage a human player (i.e. a domain stakeholder) to allow us to collect information about choices and validate the behavior of an individual agent. A proof-of-concept game is developed for a city logistics ABM to test the framework.     

Assuring finite moments for willingness to pay in random coefficient models

Random coefficient models such as mixed logit are increasingly being used to allow for random heterogeneity in willingness to pay (WTP) measures. In the most commonly used specifications, the distribution of WTP for an attribute is derived from the distribution of the ratio of individual coefficients. Since the cost coefficient enters the denominator, its distribution plays a major role in the distribution of WTP. Depending on the choice of distribution for the cost coefficient, and its implied range, the distribution of WTP may or may not have finite moments. In this paper, we identify a criterion to determine whether, with a given distribution for the cost coefficient, the distribution of WTP has finite moments. Using this criterion, we show that some popular distributions used for the cost coefficient in random coefficient models, including normal, truncated normal, uniform and triangular, imply infinite moments for the distribution of WTP, even if truncated or bounded at zero. We also point out that relying on simulation approaches to obtain moments of WTP from the estimated distribution of the cost and attribute coefficients can mask the issue by giving finite moments when the true ones are infinite.     

Does a high level of multimodality mean less car use? An exploration of multimodality trends in England

Some existing studies have suggested that a higher level of multimodality—the use of more than one transport mode within a given period of time—may be desirable to achieve societies less dependent on cars. The aim of this study was to investigate the trends in individual multimodality in England. In addition, we explored whether these trends were homogenous, i.e. similar between socio-economic characteristics, and whether changes in multimodality corresponded with changes in car use and the use of other transport modes. Our analyses showed that in contrast to reported trends in existing research, the level of multimodality in England decreased between 1995 and 2015. These trends stratified by income were diverging, which may imply that inequality in transport opportunities may be increasing. In contrast, the trends for age and gender were converging. In addition, we found that the car mode share remained fairly stable and absolute car use decreased since 2004, whilst multimodality decreased. This suggests that there is no necessary relationship between aggregate levels of car use and the average individual level of multimodality. Moreover, our analyses showed that these trends were very similarly independent of which indicator was applied. This indicates that for analysing trends in multimodality, the choice of indicator may not be that important, and indicators that are elementary to calculate and easy to interpret, e.g. number of modes used, highlight trends that are highly consistent with more sophisticated metrics. This paper finishes with a discussion of the implications of these findings.

     

Gender differences in activity participation,time-of-day and duration choices: new evidence from Calgary

To date only limited research has quantified differences between female and male activity patterns, and analyses at an individual activity level are scarce. Past research has focused on investigating gender differences in mobility levels based on observed travel patterns, especially those related to commuting. This article reports new evidence based on analyses of a household activity survey data-set collected from a Canadian city – Calgary – in 2001. Results show that contemporary females and males have a very similar activity participation pattern. On the other hand, analyses applied to activity starting times support the view that there are minor gender differences in time-of-day choices. In addition, duration and survival analyses through log-rank and Wilcoxon tests show that women and men tend to spend more or less time on some of the 10 weekend/weekday activities, and thus indicate that they share different domestic and societal responsibilities: males tend to spend longer time for out-of-home activities, such as work, school, social, and out-of-town; whereas females contribute more to domestic work, including shopping, eating, and religious activity. In general, this article contributes new evidence to gender differences in activity participation, time-of-day, and duration choices at the individual activity level. Such differences may influence travelers’ time, mode, and location choices and thus have important implications for the complexity of an activity-based modeling framework. These implications are discussed along with recommendations for incorporating gender differences in an activity-based modeling framework.     

Tracking the position of neighboring vehicles using wireless communications

We investigate four communication schemes for Cooperative Active Safety System (CASS) and compare their performance with application level reliability metrics. The four schemes are periodic communication, periodic communication with model, variable communication, and variable communication with repetition. CASS uses information communicated from neighboring vehicles via wireless network in order to actively evaluate driving situations and provide warnings or other forms of assistance to drivers. In CASS, we assume that vehicles are equipped with a GPS receiver, a Dedicated Short Range Communications (DSRC) transceiver, and in-vehicle sensors. The messages exchanged between vehicles convey position, speed, heading, and other vehicle kinematics. This information is broadcast to all neighbors within a specified communication range. Existing literature surmises that in order for CASS to be effective, it may need a vehicle to broadcast messages periodically as often as every 100 ms. In this paper, we introduce the concept of running a kinematic model in-between message transmissions as a means of reducing the communication rate. We use traffic and network simulators to compare the performance of the four schemes. Our performance measure metrics include communication losses as well as average position errors.     

An integrated modelling approach for the bicriterion vehicle routing and scheduling problem with environmental considerations

The consideration of pollution in routing decisions gives rise to a new routing framework where measures of the environmental implications are traded off with business performance measures. To address this type of routing decisions, we formulate and solve a bi-objective time, load and path-dependent vehicle routing problem with time windows (BTL-VRPTW). The proposed formulation incorporates a travel time model representing realistically time varying traffic conditions. A key feature of the problem under consideration is the need to address simultaneously routing and path finding decisions. To cope with the computational burden arising from this property of the problem we propose a network reduction approach. Computational tests on the effect of the network reduction approach on determining non-dominated solutions are reported. A generic solution framework is proposed to address the BTL-VRPTW. The proposed framework combines any technique that creates capacity-feasible routes with a routing and scheduling method that aims to convert the identified routes to problem solutions. We show that transforming a set of routes to BTL-VRPTW solutions is equivalent to solving a bi-objective time dependent shortest path problem on a specially structured graph. We propose a backward label setting technique to solve the emerging problem that takes advantage of the special structure of the graph. The proposed generic solution framework is implemented by integrating the routing and scheduling method into an Ant Colony System algorithm. The accuracy of the proposed algorithm was assessed on the basis of its capability to determine minimum travel time and fuel consumption solutions. Although the computational results are encouraging, there is ample room for future research in algorithmic advances on addressing the proposed problem.     

Transport network criticality metrics: a comparative analysis and a guideline for selection

ABSTRACT

Transport network criticality analysis aims at ranking transport infrastructure elements based on their contribution to the performance of the overall infrastructure network. Despite the wide variety of transport network criticality metrics, little guidance is available on selecting metrics that are fit for the specific purpose of a study. To address this gap, this study reviews, evaluates and compares seventeen criticality metrics. First, we conceptually evaluate these metrics in terms of the functionality of the transport system that the metrics try to represent (either maintaining connectivity, reducing travel cost, or improving accessibility), the underlying ethical principles (either utilitarianism or egalitarianism), and the spatial aggregation considered by the metrics (either network-wide or localised). Next, we empirically compare the metrics by calculating them for eight transport networks. We define the empirical similarity between two metrics as the degree to which they yield similar rankings of infrastructure elements. Pairs of metrics that have high empirical similarity highlight the same set of transport infrastructure elements as critical. We find that empirical similarity is partly dependent on the network’s topology. We also observe that metrics that are conceptually similar do not necessarily have high empirical similarity. Based on the insights from the conceptual and empirical comparison, we propose a five-step guideline for transport authorities and analysts to identify the set of criticality metrics to use which best aligns with the nature of their policy questions.     

Generating lane-based intersection maps from crowdsourcing big trace data

Lane-based road information plays a critical role in transportation systems, a lane-based intersection map is the most important component in a detailed road map of the transportation infrastructure. Researchers have developed various algorithms to detect the spatial layout of intersections based on sensor data such as high-definition images/videos, laser point cloud data, and GPS traces, which can recognize intersections and road segments; however, most approaches do not automatically generate Lane-based Intersection Maps (LIMs). The objective of our study is to generate LIMs automatically from crowdsourced big trace data using a multi-hierarchy feature extraction strategy. The LIM automatic generation method proposed in this paper consists of the initial recognition of road intersections, intersection layout detection, and lane-based intersection map-generation. The initial recognition process identifies intersection and non-intersection areas using spatial clustering algorithms based on the similarity of angle and distance. The intersection layout is composed of exit and entry points, obtained by combining trajectory integration algorithms and turn rules at road intersections. The LIM generation step is finally derived from the intersection layout detection results and lane-based road information, based on geometric matching algorithms. The effectiveness of our proposed LIM generation method is demonstrated using crowdsourced vehicle traces. Additional comparisons and analysis are also conducted to confirm recognition results. Experiments show that the proposed method saves time and facilitates LIM refinement from crowdsourced traces more efficiently than methods based on other types of sensor data.     

Crowdsourced data for bicycling research and practice

ABSTRACT

Cities are promoting bicycling for transportation as an antidote to increased traffic congestion, obesity and related health issues, and air pollution. However, both research and practice have been stalled by lack of data on bicycling volumes, safety, infrastructure, and public attitudes. New technologies such as GPS-enabled smartphones, crowdsourcing tools, and social media are changing the potential sources for bicycling data. However, many of the developments are coming from data science and it can be difficult evaluate the strengths and limitations of crowdsourced data. In this narrative review we provide an overview and critique of crowdsourced data that are being used to fill gaps and advance bicycling behaviour and safety knowledge. We assess crowdsourced data used to map ridership (fitness, bike share, and GPS/accelerometer data), assess safety (web-map tools), map infrastructure (OpenStreetMap), and track attitudes (social media). For each category of data, we discuss the challenges and opportunities they offer for researchers and practitioners. Fitness app data can be used to model spatial variation in bicycling ridership volumes, and GPS/accelerometer data offer new potential to characterise route choice and origin-destination of bicycling trips; however, working with these data requires a high level of training in data science. New sources of safety and near miss data can be used to address underreporting and increase predictive capacity but require grassroots promotion and are often best used when combined with official reports. Crowdsourced bicycling infrastructure data can be timely and facilitate comparisons across multiple cities; however, such data must be assessed for consistency in route type labels. Using social media, it is possible to track reactions to bicycle policy and infrastructure changes, yet linking attitudes expressed on social media platforms with broader populations is a challenge. New data present opportunities for improving our understanding of bicycling and supporting decision making towards transportation options that are healthy and safe for all. However, there are challenges, such as who has data access and how data crowdsourced tools are funded, protection of individual privacy, representativeness of data and impact of biased data on equity in decision making, and stakeholder capacity to use data given the requirement for advanced data science skills. If cities are to benefit from these new data, methodological developments and tools and training for end-users will need to track with the momentum of crowdsourced data.     

Likelihood-based offline map matching of GPS recordings using global trace information

In batch map matching the objective is to derive from a time series of position data the sequence of road segments visited by the traveler for posterior analysis. Taking into account the limited accuracy of both the map and the measurement devices several different movements over network links may have generated the observed measurements. The set of candidate solutions can be reduced by adding assumptions about the traveller’s behavior (e.g. respecting speed limits, using shortest paths, etc.). The set of feasible assumptions however, is constrained by the intended posterior analysis of the link sequences produced by map matching. This paper proposes a method that only uses the spatio-temporal information contained in the input data (GPS recordings) not reduced by any additional assumption.The method partitions the trace of GPS recordings so that all recordings in a part are chronologically consecutive and match the same set of road segments. Each such trace part leads to a collection of partial routes that can be qualified by their likelihood to have generated the trace part. Since the trace parts are chronologically ordered, an acyclic directed graph can be used to find the best chain of partial routes. It is used to enumerate candidate solutions to the map matching problem.Qualification based on behavioral assumptions is added in a separate later stage. Separating the stages helps to make the underlying assumptions explicit and adaptable to the purpose of the map matched results. The proposed technique is a multi-hypothesis technique (MHT) that does not discard any hypothesized path until the second stage.A road network extracted from OpenStreetMap (OSM) is used. In order to validate the method, synthetic realistic GPS traces were generated from randomly generated routes for different combinations of device accuracy and recording period. Comparing the base truth to the map matched link sequences shows that the proposed technique achieves a state of the art accuracy level.