A probabilistic map matching method for smartphone GPS data

Smartphones have the capability of recording various kinds of data from built-in sensors such as GPS in a non-intrusive, systematic way. In transportation studies, such as route choice modeling, the discrete sequences of GPS data need to be associated with the transportation network to generate meaningful paths. The poor quality of GPS data collected from smartphones precludes the use of state of the art map matching methods. In this paper, we propose a probabilistic map matching approach. It generates a set of potential true paths, and associates a likelihood with each of them. Both spatial (GPS coordinates) and temporal information (speed and time) is used to calculate the likelihood of the data for a specific path. Applications and analyses on real trips illustrate the robustness and effectiveness of the proposed approach. Also, as an application example, a Path-Size Logit model is estimated based on a sample of real observations. The estimation results show the viability of applying the proposed method in a real route choice modeling context.     

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.     

Revenue allocation methods for integrated transit systems

Revenue allocation in the context of an integrated transit system involves the splitting of joint revenues derived from passengers taking system trips, that is, trips that involve a transfer between properties of two or more of the participants in an integrated system. The general nature of the revenue allocation problem is first reviewed. Next, a framework for constructing and assessing revenue allocation models is developed. A macroprocess model is described; categories of variables that merit consideration for inclusion in revenue/cost allocation formulas are discussed; and criteria for evaluation of models are examined. After doing this, five general approaches to the problem of allocating joint revenues are discussed and evaluated. Finally, a general revenue-sharing model based on ridership is developed. The model is then used to examine several relevant issues in pricing system trips and fare collection.     

The electric vehicle touring problem

The increasing concern over global warming has led to the rapid development of the electric vehicle industry. Electric vehicles (EVs) have the potential to reduce the greenhouse effect and facilitate more efficient use of energy resources. In this paper, we study several EV route planning problems that take into consideration possible battery charging or swapping operations. Given a road network, the objective is to determine the shortest (travel time) route that a vehicle with a given battery capacity can take to travel between a pair of vertices or to visit a set of vertices with several stops, if necessary, at battery switch stations. We present polynomial time algorithms for the EV shortest travel time path problem and the fixed tour EV touring problem, where the fixed tour problem requires visiting a set of vertices in a given order. Based on the result, we also propose constant factor approximation algorithms for the EV touring problem, which is a generalization of the traveling salesman problem.     

Where do cyclists ride? A route choice model developed with revealed preference GPS data

To better understand bicyclists’ preferences for facility types, GPS units were used to observe the behavior of 164 cyclists in Portland, Oregon, USA for several days each. Trip purpose and several other trip-level variables recorded by the cyclists, and the resulting trips were coded to a highly detailed bicycle network. The authors used the 1449 non-exercise, utilitarian trips to estimate a bicycle route choice model. The model used a choice set generation algorithm based on multiple permutations of path attributes and was formulated to account for overlapping route alternatives. The findings suggest that cyclists are sensitive to the effects of distance, turn frequency, slope, intersection control (e.g. presence or absence of traffic signals), and traffic volumes. In addition, cyclists appear to place relatively high value on off-street bike paths, enhanced neighborhood bikeways with traffic calming features (aka “bicycle boulevards”), and bridge facilities. Bike lanes more or less exactly offset the negative effects of adjacent traffic, but were no more or less attractive than a basic low traffic volume street. Finally, route preferences differ between commute and other utilitarian trips; cyclists were more sensitive to distance and less sensitive to other infrastructure characteristics for commute trips.     

Application of Lagrangian relaxation approach to α-reliable path finding in stochastic networks with correlated link travel times

This study investigates the important problem of determining a reliable path in a stochastic network with correlated link travel times. First, the distribution of path travel time is quantified by using trip records from GPS probe vehicles. Second, the spatial correlation of link travel time is explicitly considered by using a correlation coefficient matrix, which is incorporated into the α-reliable path problem by Cholesky decomposition. Third, the Lagrangian relaxation based framework is used to handle the α-reliable path problem, by which the intractable problem with a non-linear and non-additive structure can be decomposed into several easy-to-solve problems. Finally, the path-finding performance of this approach is tested on a real-world network. The results show that 15 iterations of calculation can yield a small relative gap between upper and lower bounds of the optimal solution and the average running time is about 5 s for most OD settings. The applicability of α-reliable path finding is validated by a case study.     

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.     

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.     

The use of GIS and relational database management systems to improve the scheduling operations of paratransit

The scheduling operations of many paratransit agencies in the United States are undertaken manually. Those customers who are eligible to travel call in their requests the day before the trip is needed. As the trip requests are received, they are entered into a list of unscheduled trips. In order to schedule these trips, the scheduler must first determine the number of drivers and shuttle buses that are available as well as the time of availability of each. The scheduler must then try to match the rides that are in “similar” areas around the “same” time to place together on the driver's schedule. As new trip requests are made, the schedulers must adjust the trips that are already scheduled to try and schedule as many trips as possible in the most efficient way.

By developing a system that would improve the scheduling system operations of, in this case, DART (Delaware Administration for Regional Transit) First State Paratransit, customers can expect to receive better service that will improve their ability to travel throughout the community. Some devices that could also improve the operations of paratransit agencies are described in this paper, such as satellite‐based Global Positioning System (GPS), radio communication systems, mobile computers, radio frequency‐based data communication systems, internet web pages, automated paratransit information systems, and card‐based data storage and transfer media. However, because paratransit systems are difficult to operate cost‐efficiently, the optimum and most cost‐efficient device must be selected. The system chosen for DART First State Paratransit includes the use of a relational database management system (RDMS) and a transportation Geographic Information System (GIS). RDMS keeps track of the database information as well as the scheduled trips and the GIS is ideal for analyzing both geographic and temporal data. This system is shown to be superior to the manual system.     

On some traffic equilibrium theory paradoxes

We consider the asymmetric equilibrium problem with fixed demands in a transportation network where the travel cost on each link may depend on the flow on this as well as other links of the network and we study how the travellers' cost is affected by changes in the travel demand or addition of new routes. Assuming that the travel cost functions are strongly monotone, we derive formulas which express, under certain conditions, how a change in travel demand associated with a particular origin-destination (O / D) pair will affect the travelers' cost for any O / D pair. We then use these formulas to show that an increase in the travel demand associated with a particular O / D pair (all other remaining fixed) always results in an increase in the travelers' cost on that O / D pair, however, the travelers' cost on other O / D pairs may decrease. We then derive formulas yielding, under certain conditions, the change in travelers' cost on every O / D pair induced by the addition of a new path. These can be used to determine, whether Braess' paradox occurs in the network. We then show that when a new path is added, the travelers' cost associated with the particular O / D pair joined by this path will decrease (hence Braess' paradox does not occur) if a test matrix is positive semidefinite.     

Boundedly rational user equilibria (BRUE): Mathematical formulation and solution sets

Boundedly rational user equilibria (BRUE) represent traffic flow distribution patterns where travellers can take any route whose travel cost is within an ‘indifference band’ of the shortest path cost. Those traffic flow patterns satisfying the above condition constitute a set, named the BRUE solution set. It is important to obtain all the BRUE flow patterns, because it can help predict the variation of the link flow pattern in a traffic network under the boundedly rational behavior assumption. However, the methodology of constructing the BRUE set has been lacking in the established literature. This paper fills the gap by constructing the BRUE solution set on traffic networks with fixed demands. After defining ε-BRUE, where ε is the indifference band for the perceived travel cost, we formulate the ε-BRUE problem as a nonlinear complementarity problem (NCP), so that a BRUE solution can be obtained by solving a BRUE–NCP formulation. To obtain the BRUE solution set encompassing all BRUE flow patterns, we propose a methodology of generating acceptable path set which may be utilized under the boundedly rational behavior assumption. We show that with the increase of the indifference band, the acceptable path set that contains boundedly rational equilibrium flows will be augmented, and the critical values of indifference band to augment these path sets can be identified by solving a family of mathematical programs with equilibrium constraints (MPEC) sequentially. The BRUE solution set can then be obtained by assigning all traffic demands to the acceptable path set. Various numerical examples are given to illustrate our findings.     

The recoverable robust facility location problem

This work deals with a facility location problem in which location and allocation (transportation) policy is defined in two stages such that a first-stage solution should be robust against the possible realizations (scenarios) of the input data that can only be revealed in a second stage. This solution should be robust enough so that it can be recovered promptly and at low cost in the second stage. In contrast to some related modeling approaches from the literature, this new recoverable robust model is more general in terms of the considered data uncertainty; it can address situations in which uncertainty may be present in any of the following four categories: provider-side uncertainty, receiver-side uncertainty, uncertainty in-between, and uncertainty with respect to the cost parameters.For this novel problem, a sophisticated branch-and-cut framework based on Benders decomposition is designed and complemented by several non-trivial enhancements, including scenario sorting, dual lifting, branching priorities, matheuristics and zero-half cuts. Two large sets of instances that incorporate spatial and demographic information of countries such as Germany and US (transportation) and Bangladesh and the Philippines (disaster management) are introduced. They are used to analyze in detail the characteristics of the proposed model and the obtained solutions as well as the effectiveness, behavior and limitations of the designed algorithm.     

A statistical approach to the traveling salesman problem

A statistical approach is shown to be adaptable to the N-city traveling salesman problem by considering route distances to be random variables which are continuous and normally distributed. A solution to the shortest route distance and path can be approximated by utilizing a Monte Carlo simulation to obtain a representative sample of possible journeys. The approach involves recursive statistical inference which is used to select next-city visits leading to the most probable minimum route path. A statistical selection of the minimum route path is computationally efficient and computer run time increases in proportion to the square of the number of cities as opposed to an (N - 1)! increase for a deterministic approach. The accuracy of the statistical approach is directly proportional to the number of Monte Carlo simulations.     

Making mode detection transferable: extracting activity and travel episodes from GPS data using the multinomial logit model and Python

The increasing popularity of global positioning systems (GPSs) has prompted transportation researchers to develop methods that can automatically extract and classify episodes from GPS data. This paper presents a transferable and efficient method of extracting and classifying activity episodes from GPS data, without additional information. The proposed method, developed using Python®, introduces the use of the multinomial logit (MNL) model in classifying extracted episodes into different types: stop, car, walk, bus, and other (travel) episodes. The proposed method is demonstrated using a GPS dataset from the Space-Time Activity Research project in Halifax, Canada. The GPS data consisted of 5127 person-days (about 47 million points). With input requirements directly derived from GPS data and the efficiency provided by the MNL model, the proposed method looks promising as a transferable and efficient method of extracting activity and travel episodes from GPS data.     

Assessing the accuracy of the Sydney Household Travel Survey with GPS

Over the past few years, GPS has been used in a number of surveys in the US to assess the accuracy of household travel surveys. The results have been somewhat alarming in that most of these exercises have shown that the standard trip-based CATI survey conducted in the US under-reports travel by about 20–25%. It was decided to use GPS to assess the accuracy of the Sydney Household Travel Survey, a continuous survey conducted by face-to-face interviewing. The procedure used was for the interviewers to recruit households for the household travel survey in the normal manner, and then, if the household met certain criteria, to endeavour to recruit the household to also undertake a GPS survey. A small sample of about 50 households was obtained, and GPS devices successfully retrieved that measured data on the same day as the travel diary was completed. In addition, participants in the GPS survey completed a prompted recall survey a week or two later, using maps and tabulations of travel obtained from the GPS devices, to identify mode, purpose and occupancy for trips measured by the GPS, and also to check for accuracy in defining trip ends and total number of trips. Based on the analysis of the GPS compared to the diary results, it was found that respondents under-reported their travel by about 7%, which is much less than in the US CATI results. Respondents were also found to under-report travel distances and over-report travel times. There was also a high incidence of non-reporting for VKT.

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.     

An empirical study of simulation-based dynamic traffic assignment procedures

Abstract

Under Intelligent Transportation Systems (ITS), real-time operations of traffic management measures depend on long-term planning results, such as the origin–destination (OD) trip distribution; however, results from current planning procedures are unable to provide fundamental data for dynamic analysis. In order to capture dynamic traffic characteristics, transportation planning models should play an important role to integrate basic data with real-time traffic management and control. In this paper, a heuristic algorithm is proposed to establish the linkage between daily OD trips and dynamic traffic assignment (DTA) procedures; thus results from transportation planning projects, in terms of daily OD trips, can be extended to estimate time-dependent OD trips. Field data from Taiwan are collected and applied in the calibration and validation processes. Dynamic Network Assignment-Simulation Model for Advanced Road Telematics (DYNASMART-P), a simulation-based DTA model, is applied to generate time-dependent flows. The results from the validation process show high agreement between actual flows from vehicle detectors (VDs) and simulated flows from DYNAMSART-P.     

Simulation model performance analysis of a multiple station shared vehicle system

As an alternative transportation paradigm, shared vehicle systems have become increasingly popular in recent years. Shared vehicle systems typically consist of a fleet of vehicles that are used several times each day by different users. One of the main advantages of shared vehicle systems is that they reduce the number of vehicles required to meet total travel demand. An added energy/emissions benefit comes when low-polluting (e.g., electric) vehicles are used in the system. In order to evaluate operational issues such as vehicle availability, vehicle distribution, and energy management, a unique shared vehicle system computer simulation model has been developed. As an initial case study, the model was applied to a resort community in Southern California. The simulation model has a number of input parameters that allow for the evaluation of numerous scenarios. Several measures of effectiveness have been determined and are calculated to characterize the overall system performance. For the case study, it was found that the most effective number of vehicles (in terms of satisfying customer wait time) is in the range of 3–6 vehicles per 100 trips in a 24 h day. On the other hand, if the number of relocations also is to be minimized, there should be approximately 18–24 vehicles per 100 trips. Various inputs to the model were varied to see the overall system response. The model shows that the shared vehicle system is most sensitive to the vehicle-to-trip ratio, the relocation algorithm used, and the charging scheme employed when electric vehicles are used. A preliminary cost analysis was also performed, showing that such a system can be very competitive with present transportation systems (e.g., rental cars, taxies, etc.).     

Uncertainty modeling for bus selection and allocation in a private transportation system

ABSTRACT

This paper describes the development of a probabilistic formulation that provides global optimum selection and allocation of a fleet of buses in a private transportation system of an organization where a third party is hired to provide transportation for its employees and their dependents. In this private transportation system, a fleet of buses is to be selected and allocated to serve employees and their independents on different prescheduled trips along different routes from the organization’s headquarters and residential compound where round-trip times of scheduled trips are subject to uncertainty due to random delays. We propose a probabilistic approach based on 0-1 integer programming for the selection and allocation to determine the optimal number and size of buses assigned to a set of prescheduled trips in a particular time interval. Examples and a case study are presented to illustrate the applicability and suitability of the proposed approach.     

Internalization of Transportation External Costs: Impact Analysis of Logistics Company Mode and Route Choices

Abstract

This study focuses on the mode and route choices of a logistics company in a situation involving intercity transportation with networks of surface roads, highways and a railway. A method of transportation network analysis is applied to construct a logistics company mode and route choice models with the objective of minimizing total distribution and external costs. This study also assumes that the fleet number and vehicle capacities are given. Freight distributed from a distribution center to given retailers or consumers via surface road/highway links or via intermodal transportation involving surface road/highway links and a railway. In terms of model construction, this study first explores the routing and sequence of the retailers and consumers served by each vehicle. Second, the study internalizes the external cost of air pollution into the total distribution cost, to analyze the influences of external cost burdens on a logistics company mode and route choices from a user charge perspective. Finally, the study designs a heuristic algorithm for solving the above models, and illuminates the modeling process using a numerical example.