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.     

A driving cycle detection approach using map service API

Following advancements in smartphone and portable global positioning system (GPS) data collection, wearable GPS data have realized extensive use in transportation surveys and studies. The task of detecting driving cycles (driving or car-mode trajectory segments) from wearable GPS data has been the subject of much research. Specifically, distinguishing driving cycles from other motorized trips (such as taking a bus) is the main research problem in this paper. Many mode detection methods only focus on raw GPS speed data while some studies apply additional information, such as geographic information system (GIS) data, to obtain better detection performance. Procuring and maintaining dedicated road GIS data are costly and not trivial, whereas the technical maturity and broad use of map service application program interface (API) queries offers opportunities for mode detection tasks. The proposed driving cycle detection method takes advantage of map service APIs to obtain high-quality car-mode API route information and uses a trajectory segmentation algorithm to find the best-matched API route. The car-mode API route data combined with the actual route information, including the actual mode information, are used to train a logistic regression machine learning model, which estimates car modes and non-car modes with probability rates. The experimental results show promise for the proposed method’s ability to detect vehicle mode accurately.     

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.     

Estimation of a route choice model for urban public transport using smart card data

This paper describes a logit model of route choice for urban public transport and explains how the archived data from a smart card-based fare payment system can be used for the choice set generation and model estimation. It demonstrates the feasibility and simplicity of applying a trip-chaining method to infer passenger journeys from smart card transactions data. Not only origins and destinations of passenger journeys can be inferred but also the interchanges between the segments of a linked journey can be recognised. The attributes of the corresponding routes, such as in-vehicle travel time, transfer walking time and to get from alighting stop to trip destination, the need to change, and the time headway of the first transportation line, can be determined by the combination of smart card data with other data sources, such as a street map and timetable. The smart card data represent a large volume of revealed preference data that allows travellers' behaviour to be modelled with higher accuracy than by using traditional survey data. A multinomial route choice model is proposed and estimated by the maximum likelihood method, using urban public transport in ?ilina, the Slovak Republic, as a case study     

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.     

Metropolis–Hastings sampling of paths

We consider the previously unsolved problem of sampling paths according to a given distribution from a general network. The problem is difficult because of the combinatorial number of alternatives, which prohibits a complete enumeration of all paths and hence also forbids to compute the normalizing constant of the sampling distribution. The problem is important because the ability to sample from a known distribution introduces mathematical rigor into many applications, including the estimation of choice models with sampling of alternatives that can be formalized as paths in a decision network (most obviously route choice), probabilistic map matching, dynamic traffic assignment, and route guidance.     

Route choice of cyclists in Zurich

This paper presents the first route choice model for bicyclists estimated from a large sample of GPS observations and overcomes the limitations inherent in the generally employed stated preference approach. It employs an improved mode detection algorithm for GPS post-processing to determine trips made by bicycle, which are map matched to an enriched street network. The alternatives are generated as a random sample from an exhaustive, but constrained search. Accounting for the similarity between the alternatives with the path-size factor the MNL estimates show that the elasticity with regards to trip length is nearly four times larger than that with respect to the share of bike paths. The elasticity with respect to the product of length and maximum gradient of the route is small. No other variable describing the routes had an impact. The heterogeneity of the cyclists is captured through interaction terms formulated on their average behaviour.     

Modeling heterogeneous risk-taking behavior in route choice: A stochastic dominance approach

This paper proposes a unified approach to modeling heterogonous risk-taking behavior in route choice based on the theory of stochastic dominance (SD). Specifically, the first-, second-, and third-order stochastic dominance (FSD, SSD, TSD) are respectively linked to insatiability, risk-aversion and ruin-aversion within the framework of utility maximization. The paths that may be selected by travelers of different risk-taking preferences can be obtained from the corresponding SD-admissible paths, which can be generated using general dynamic programming. This paper also analyzes the relationship between the SD-based approach and other route choice models that consider risk-taking behavior. These route choice models employ a variety of reliability indexes, which often make the problem of finding optimal paths intractable. We show that the optimal paths with respect to these reliability indexes often belong to one of the three SD-admissible path sets. This finding offers not only an interpretation of risk-taking behavior consistent with the SD theory for these route choice models, but also a unified and computationally viable solution approach through SD-admissible path sets, which are usually small and can be generated without having to enumerate all paths. A generic label-correcting algorithm is proposed to generate FSD-, SSD-, and TSD-admissible paths, and numerical experiments are conducted to test the algorithm and to verify the analytical results.     

Bike route choice modeling using GPS data without choice sets of paths

Concerned by the nuisances of motorized travel on urban life, policy makers are faced with the challenge of making cycling a more attractive alternative for everyday transportation. Route choice models can help achieve this objective by gaining insights into the trade-offs cyclists make when choosing their routes and by allowing the effect of infrastructure improvements to be analyzed. We estimate a link-based bike route choice model from a sample of GPS observations in the city of Eugene on a network comprising over 40,000 links. The so-called recursive logit (RL) model (Fosgerau et al., 2013) does not require to sample any choice set of paths. We show the advantages of this approach in the context of prediction by focusing on two applications of the model: link flows and accessibility measures. Compared to the path-based approach which requires to generate choice sets, the RL model proves to make significant gains in computational time and to avoid paradoxical accessibility measure results discussed in previous works, e.g. Nassir et al. (2014).     

Repeated anticipatory network traffic control using iterative optimization accounting for model bias correction

Anticipatory signal control in traffic networks adapts the signal timings with the aim of controlling the resulting (equilibrium) flows and route choice patterns in the network. This study investigates a method to support control decisions for successful applications in real traffic systems that operate repeatedly, for instance from day to day, month to month, etc. The route choice response to signal control is usually predicted through models; however this leads to suboptimality because of unavoidable prediction errors between model and reality. This paper proposes an iterative optimizing control method to drive the traffic network towards the real optimal performance by observing modeling errors and correcting for them. Theoretical analysis of this Iterative Optimizing Control with Model Bias Correction (IOCMBC) on matching properties between the modeled optimal solution and the real optimum is presented, and the advantages over conventional iterative schemes are demonstrated. A local convergence analysis is also elaborated to investigate conditions required for a convergent scheme. The main innovation is the calculation of the sensitivity (Jacobian) information of the real route choice behavior with respect to signal control variables. To avoid performing additional perturbations, we introduce a measurement-based implementation method for estimating the operational Jacobian that is associated with the reality. Numerical tests confirm the effectiveness of the proposed IOCMBC method in tackling modeling errors, as well as the influence of the optimization step size on the reality-tracking convergence.     

Development of a transit network from a street map database with spatial analysis and dynamic segmentation

This paper presents an integrated transit-oriented travel demand modeling procedure within the framework of geographic information systems (GIS). Focusing on transit network development, this paper presents both the procedure and algorithm for automatically generating both link and line data for transit demand modeling from the conventional street network data using spatial analysis and dynamic segmentation. For this purpose, transit stop digitizing, topology and route system building, and the conversion of route and stop data into link and line data sets are performed. Using spatial analysis, such as the functionality to search arcs nearest from a given node, the nearest stops are identified along the associated links of the transit line, while the topological relation between links and line data sets can also be computed using dynamic segmentation. The advantage of this approach is that street map databases represented by a centerline can be directly used along with the existing legacy urban transportation planning systems (UTPS) type travel modeling packages and existing GIS without incurring the additional cost of purchasing a full-blown transportation GIS package. A small test network is adopted to demonstrate the process and the results. The authors anticipate that the procedure set forth in this paper will be useful to many cities and regional transit agencies in their transit demand modeling process within the integrated GIS-based computing environment.     

Virtual 3D city model as a priori information source for vehicle localization system

This paper aims at demonstrating the usefulness of integrating virtual 3D models in vehicle localization systems. Usually, vehicle localization algorithms are based on multi-sensor data fusion. Global Navigation Satellite Systems GNSS, as Global Positioning System GPS, are used to provide measurements of the geographic location. Nevertheless, GNSS solutions suffer from signal attenuation and masking, multipath phenomena and lack of visibility, especially in urban areas. That leads to degradation or even a total loss of the positioning information and then unsatisfactory performances. Dead-reckoning and inertial sensors are then often added to back up GPS in case of inaccurate or unavailable measurements or if high frequency location estimation is required. However, the dead-reckoning localization may drift in the long term due to error accumulation. To back up GPS and compensate the drift of the dead reckoning sensors based localization, two approaches integrating a virtual 3D model are proposed in registered with respect to the scene perceived by an on-board sensor. From the real/virtual scenes matching, the transformation (rotation and translation) between the real sensor and the virtual sensor (whose position and orientation are known) can be computed. These two approaches lead to determine the pose of the real sensor embedded on the vehicle. In the first approach, the considered perception sensor is a camera and in the second approach, it is a laser scanner. The first approach is based on image matching between the virtual image extracted from the 3D city model and the real image acquired by the camera. The two major parts are: 1. Detection and matching of feature points in real and virtual images (three features points are compared: Harris corner detector, SIFT and SURF). 2. Pose computation using POSIT algorithm. The second approach is based on the on–board horizontal laser scanner that provides a set of distances between it and the environment. This set of distances is matched with depth information (virtual laser scan data), provided by the virtual 3D city model. The pose estimation provided by these two approaches can be integrated in data fusion formalism. In this paper the result of the first approach is integrated in IMM UKF data fusion formalism. Experimental results obtained using real data illustrate the feasibility and the performances of the proposed approaches.     

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.     

A portfolio theory of route choice

Although many individual route choice models have been proposed to incorporate travel time variability as a decision factor, they are typically still deterministic in the sense that the optimal strategy requires choosing one particular route that maximizes utility. In contrast, this study introduces an individual route choice model where choosing a portfolio of routes instead of a single route is the best strategy for a rational traveler who cares about both journey time and lateness when facing stochastic network conditions. The proposed model is compared with UE and SUE models and the difference in both behavioral foundation and model characteristics is highlighted. A numerical example is introduced to demonstrate how such model can be used in traffic assignment problem. The model is then tested with GPS data collected in metropolitan Minneapolis–St. Paul, Minnesota. Our data suggest there is no single dominant route (defined here as a route with the shortest travel time for a 15 day period) in 18% of cases when links travel times are correlated. This paper demonstrates that choosing a portfolio of routes could be the rational choice of a traveler who wants to optimize route decisions under variability.     

A new logit‐artificial neural network ensemble for mode choice modeling: a case study for border transport

Logit model is one of the statistical techniques commonly used for mode choice modeling, while artificial neural network (ANN) is a very popular type of artificial intelligence technique used for mode choice modeling. Ensemble learning has evolved to be very effective approach to enhance the performance for many applications through integration of different models. In spite of this advantage, the use of ANN‐based ensembles in mode choice modeling is under explored. The focus of this study is to investigate the use of aforementioned techniques for different number of transportation modes and predictor variables. This study proposes a logit‐ANN ensemble for mode choice modeling and investigates its efficiency in different situations. Travel between Khobar‐Dammam metropolitan area of Saudi Arabia and Kingdom of Bahrain is selected for mode choice modeling. The travel on this route can be performed mainly by air travel or private vehicle through King Fahd causeway. The results show that the proposed ensemble gives consistently better accuracies than single models for multinomial choice problems irrespective of number of input variables. Copyright © 2015 John Wiley & Sons, Ltd.     

A dual control approach for repeated anticipatory traffic control with estimation of network flow sensitivity

This paper investigates a strategic signal control, which anticipates travelers' route choice response and determines signal timings to optimize network‐wide objectives. In general traffic assignment models are used for anticipating this route choice response. However, model‐reality mismatch usually brings suboptimal solutions to the real system. A repeated anticipatory control resolves the suboptimality and addresses the modeling error by learning from information on model bias. This paper extends the repeated control approach and focuses on the estimation of flow sensitivity as well as its influence on control, which is a crucial issue in implementation of model bias correction. The main objective of this paper is first to analyze the estimation error in the real flow derivative that is estimated from noisy measurements. A dual control method is then presented, improving both optimization objective function and derivative estimation during the control process. The proposed dual algorithm is tested on a simple network as well as on a midsize network. Numerical examples confirm the reliable performance of the new reality‐tracking control strategy and its ability to identify (local) optimal solutions on real traffic networks. Copyright © 2016 John Wiley & Sons, Ltd.     

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.     

Sustainable urban transit network design

Sustainability is a requirement for modern public transportation networks, as these are expected to play a critical role in environment-friendly transportation systems. This paper focuses on developing an efficient model for solving a sustainable oriented variant of the Transit Route Network Design Problem. The model incorporates sustainable design objectives, considers emission-free (electric) vehicles and introduces a direct route design approach with route structure and directness control. An application in a real world case, highlights the performance and benefits of the proposed model.