Estimation of population origin–interchange–destination flows on multimodal transit networks

Previous research has combined automated fare-collection (AFC) and automated vehicle-location (AVL) data to infer the times and locations of passenger origins, interchanges (transfers), and destinations on multimodal transit networks. The resultant origin–interchange–destination flows (and the origin–destination (OD) matrices that comprise those flows), however, represent only a sample of total ridership, as they contain only those journeys made using the AFC payment method that have been successfully recorded or inferred. This paper presents a method for scaling passenger-journey flows (i.e., linked-trip flows) using additional information from passenger counts at each station gate and bus farebox, thereby estimating the flows of non-AFC passengers and of AFC passengers whose journeys were not successfully inferred.The proposed method is applied to a hypothetical test network and to AFC and AVL data from London’s multimodal public transit network. Because London requires AFC transactions upon both entry and exit for rail trips, a rail-only OD matrix is extracted from the estimated multimodal linked-trip flows, and is compared to a rail OD matrix generated using the iterative proportional fitting method.     

Some comments on origin–destination matrix estimation

Estimation of origin–destination (O–D) matrices from link count data is considered. This problem is challenging because the number of parameters to be estimated is typically larger than the number of network links. As a result, it is (usually) impossible to identify a unique optimal estimate of the O–D matrix from mean link traffic counts. However, information from the covariance matrix of link count data collected over a sequence of days can relieve this problem of indeterminacy. This fact is illustrated through a simple example. The use of second-order statistical properties of the data in O–D matrix estimation is then explored, and a class of estimators proposed. Practical problems of model mis-specification are discussed and some avenues for future research outlined.     

Vehicle identification sensor models for origin–destination estimation

The traditional approach to origin–destination (OD) estimation based on data surveys is highly expensive. Therefore, researchers have attempted to develop reasonable low-cost approaches to estimating the OD vector, such as OD estimation based on traffic sensor data. In this estimation approach, the location problem for the sensors is critical. One type of sensor that can be used for this purpose, on which this paper focuses, is vehicle identification sensors. The information collected by these sensors that can be employed for OD estimation is discussed in this paper. We use data gathered by vehicle identification sensors that include an ID for each vehicle and the time at which the sensor detected it. Based on these data, the subset of sensors that detected a given vehicle and the order in which they detected it are available. In this paper, four location models are proposed, all of which consider the order of the sensors. The first model always yields the minimum number of sensors to ensure the uniqueness of path flows. The second model yields the maximum number of uniquely observed paths given a budget constraint on the sensors. The third model always yields the minimum number of sensors to ensure the uniqueness of OD flows. Finally, the fourth model yields the maximum number of uniquely observed OD flows given a budget constraint on the sensors. For several numerical examples, these four models were solved using the GAMS software. These numerical examples include several medium-sized examples, including an example of a real-world large-scale transportation network in Mashhad.     

A distributed origin–destination demand estimation approach for real-time traffic network management

Abstract

This paper describes a distributed recursive heuristic approach for the origin–destination demand estimation problem for real-time traffic network management applications. The distributed nature of the heuristic enables its parallelization and hence reduces significantly its processing time. Furthermore, the heuristic reduces dependency on historical data that are typically used to map the observed link flows to their corresponding origin–destination pairs. In addition, the heuristic allows the incorporation of any available partial information on the demand distribution in the study area to improve the overall estimation accuracy. The heuristic is implemented following a hierarchal multi-threading mechanism. Dividing the study area into a set of subareas, the demand of every two adjacent subareas is merged in a separate thread. The merging operations continue until the demand for the entire study area is estimated. Experiments are conducted to examine the performance of the heuristic using hypothetical and real networks. The obtained results illustrate that the heuristic can achieve reasonable demand estimation accuracy while maintaining superiority in terms of processing time.     

A generalized sensor location model for the estimation of network origin–destination matrices

This study examined the network sensor location problem by using heterogeneous sensor information to estimate link-based network origin–destination (O–D) demands. The proposed generalized sensor location model enables different sensors’ traffic monitoring capabilities to be used efficiently and the optimal number and deployment locations of both passive- and active-type sensors to be determined simultaneously without path enumeration. The proposed sensor location model was applied to solve the network O–D demand estimation problem. One unique aspect of the proposed model and solution algorithms is that they provide satisfactory network O–D demand estimates without requiring unreasonable assumptions of known prior information on O–D demands, turning proportions, or route choice probabilities. Therefore, the proposed model and solution algorithms can be practically used in numerous offline transportation planning and online traffic operation applications.     

A zone design methodology for national freight origin–destination data and transportation modeling

The zone system used for freight data collection and the geographic resolution of published data has a significant impact on analysis and planning. The majority of existing freight model zones are created in an ad hoc way. In this paper, a new model-based design method is introduced to develop freight zones for the continental USA. It focuses on two methodology issues: (1) the criteria that represent the desired properties of a zone system and (2) the constraints that govern the shape, size, and continuity of zones. The method is applied to the continental USA by optimizing an interzonal travel distance weighted by freight flows using county-level freight data. Several optimal national-level freight zone systems with different numbers of zones are developed. The results indicate that a 300-zone system provides a balance between the number of zones and optimization measures where the currently available public freight data are provided with approximately 100 zones.     

Towards a generic benchmarking platform for origin–destination flows estimation/updating algorithms: Design,demonstration and validation

Estimation/updating of Origin–Destination (OD) flows and other traffic state parameters is a classical, widely adopted procedure in transport engineering, both in off-line and in on-line contexts. Notwithstanding numerous approaches proposed in the literature, there is still room for considerable improvements, also leveraging the unprecedented opportunity offered by information and communication technologies and big data. A key issue relates to the unobservability of OD flows in real networks – except from closed highway systems – thus leading to inherent difficulties in measuring performance of OD flows estimation/updating methods and algorithms. Starting from these premises, the paper proposes a common evaluation and benchmarking framework, providing a synthetic test bed, which enables implementation and comparison of OD estimation/updating algorithms and methodologies under “standardized” conditions. The framework, implemented in a platform available to interested parties upon request, has been flexibly designed and allows comparing a variety of approaches under various settings and conditions. Specifically, the structure and the key features of the framework are presented, along with a detailed experimental design for the application of different dynamic OD flow estimation algorithms. By way of example, applications to both off-line/planning and on-line algorithms are presented, together with a demonstration of the extensibility of the presented framework to accommodate additional data sources.     

Data dependent input control for origin–destination demand estimation using observability analysis

In this paper, we address the observability issue of static O–D estimation based on link counts. Unlike most classic observability analyses that relied only on network topological relationships, our analysis incorporates the actual values of input parameters, thus including network operational relations as well. We first analyze possible mathematical properties of an O–D estimation problem with different data input. We then propose a modeling approach based on mixed-integer program for selecting model input that ensures observability and estimation quality. Through establishing a stronger connection between observability analysis and the corresponding estimation problem, the proposed method aims to improve estimation quality while reducing reliance on erroneous data.     

The treatment of uncertainty in the dynamic origin–destination estimation problem using a fuzzy approach

Regardless of existing types of transportation and traffic model and their applications, the essential input to these models is travel demand, which is usually described using origin–destination (OD) matrices. Due to the high cost and time required for the direct development of such matrices, they are sometimes estimated indirectly from traffic measurements recorded from the transportation network. Based on an assumed demand profile, OD estimation problems can be categorized into static or dynamic groups. Dynamic OD demand provides valuable information on the within-day fluctuation of traffic, which can be employed to analyse congestion dissipation. In addition, OD estimates are essential inputs to dynamic traffic assignment (DTA) models. This study presents a fuzzy approach to dynamic OD estimation problems. The problems are approached using a two-level model in which demand is estimated in the upper level and the lower level performs DTA via traffic simulation. Using fuzzy rules and the fuzzy C-Mean clustering approach, the proposed method treats uncertainty in historical OD demand and observed link counts. The approach employs expert knowledge to model fitted link counts and to set boundaries for the optimization problem by defining functions in the fuzzification process. The same operation is performed on the simulation outputs, and the entire process enables different types of optimization algorithm to be employed. The Box-complex method is utilized as an optimization algorithm in the implementation of the approach. Empirical case studies are performed on two networks to evaluate the validity and accuracy of the approach. The study results for a synthetic network and a real network demonstrate the robust performance of the proposed method even when using low-quality historical demand data.     

c-SPSA: Cluster-wise simultaneous perturbation stochastic approximation algorithm and its application to dynamic origin–destination matrix estimation

The simultaneous perturbation stochastic approximation (SPSA) algorithm has been used in the literature for the solution of the dynamic origin–destination (OD) estimation problem. Its main advantage is that it allows quite general formulations of the problem that can include a wide range of sensor measurements. While SPSA is relatively simple to implement, its performance depends on a set of parameters that need to be properly determined. As a result, especially in cases where the gradient of the objective function changes quickly, SPSA may not be as stable and even diverge. A modification of the SPSA algorithm, referred to as c-SPSA, is proposed which applies the simultaneous perturbation approximation of the gradient within a small number of carefully constructed “homogeneous” clusters one at a time, as opposed to all elements at once. The paper establishes the theoretical properties of the new algorithm with an upper bound for the bias of the gradient estimate and shows that it is lower than the corresponding SPSA bias. It also proposes a systematic approach, based on the k-means algorithm, to identify appropriate clusters. The performance of c-SPSA, with alternative implementation strategies, is evaluated in the context of estimating OD flows in an actual urban network. The results demonstrate the efficiency of the proposed c-SPSA algorithm in finding better OD estimates and achieve faster convergence and more robust performance compared to SPSA with fewer overall number of function evaluations.     

Development of origin–destination matrices using mobile phone call data

In this research, we propose a methodology to develop OD matrices using mobile phone Call Detail Records (CDR) and limited traffic counts. CDR, which consist of time stamped tower locations with caller IDs, are analyzed first and trips occurring within certain time windows are used to generate tower-to-tower transient OD matrices for different time periods. These are then associated with corresponding nodes of the traffic network and converted to node-to-node transient OD matrices. The actual OD matrices are derived by scaling up these node-to-node transient OD matrices. An optimization based approach, in conjunction with a microscopic traffic simulation platform, is used to determine the scaling factors that result best matches with the observed traffic counts. The methodology is demonstrated using CDR from 2.87 million users of Dhaka, Bangladesh over a month and traffic counts from 13 key locations over 3 days of that month. The applicability of the methodology is supported by a validation study.     

A complex network perspective for characterizing urban travel demand patterns: graph theoretical analysis of large-scale origin–destination demand networks

Urban travel demand, consisting of thousands or millions of origin–destination trips, can be viewed as a large-scale weighted directed graph. The paper applies a complex network-motivated approach to understand and characterize urban travel demand patterns through analysis of statistical properties of origin–destination demand networks. We compare selected network characteristics of travel demand patterns in two cities, presenting a comparative network-theoretic analysis of Chicago and Melbourne. The proposed approach develops an interdisciplinary and quantitative framework to understand mobility characteristics in urban areas. The paper explores statistical properties of the complex weighted network of urban trips of the selected cities. We show that travel demand networks exhibit similar properties despite their differences in topography and urban structure. Results provide a quantitative characterization of the network structure of origin–destination demand in cities, suggesting that the underlying dynamical processes in travel demand networks are similar and evolved by the distribution of activities and interaction between places in cities.     

A dynamic evacuation model for pedestrian–vehicle mixed-flow networks

In urban emergency evacuation, a potentially large number of evacuees may depend either on transit or other modes, or need to walk a long distance, to access their passenger cars. In the process of approaching the designated pick-up points or parking areas for evacuation, the massive number of pedestrians may cause tremendous burden to vehicles in the roadway network. Responsible agencies often need to contend with congestion incurred by massive vehicles emanating from parking garages, evacuation buses generated from bus stops, and the conflicts between evacuees and vehicles at intersections. Hence, an effective plan for such evacuation needs to concurrently address both the multi-modal traffic route assignment and the optimization of network signal controls for mixed traffic flows. This paper presents an integrated model to produce the optimal distribution of vehicle and pedestrian flows, and the responsive network signal plan for massive mixed pedestrian–vehicle flows within the evacuation zone. The proposed model features its effectiveness in accounting for multiple types of evacuation vehicles, the interdependent relations between pedestrian and vehicle flows via some conversion locations, and the inevitable conflicts between intersection turning vehicle and pedestrian flows. An illustrating example concerning an evacuation around the M&T stadium area has been presented, and the results indicate the promising properties of our proposed model, especially on reflecting the complex interactions between vehicle and pedestrian flows and the favorable use of high-occupancy vehicles for evacuation operations.     

Estimation of origin–destination matrices using link counts and partial path data

Transportation - After several decades of work by several talented researchers, estimation of the origin–destination matrix using traffic data has remained very challenging. This paper...     

A data-driven approach for origin–destination matrix construction from cellular network signalling data: a case study of Lyon region (France)

Transportation - Spatiotemporal data, and more specifically origin–destination matrices, are critical inputs to mobility studies for transportation planning and urban management purposes....     

Validating and improving public transport origin–destination estimation algorithm using smart card fare data

Smart card data are increasingly used for transit network planning, passengers’ behaviour analysis and network demand forecasting. Public transport origin–destination (O–D) estimation is a significant product of processing smart card data. In recent years, various O–D estimation methods using the trip-chaining approach have attracted much attention from both researchers and practitioners. However, the validity of these estimation methods has not been extensively investigated. This is mainly because these datasets usually lack data about passengers’ alighting, as passengers are often required to tap their smart cards only when boarding a public transport service. Thus, this paper has two main objectives. First, the paper reports on the implementation and validation of the existing O–D estimation method using the unique smart card dataset of the South-East Queensland public transport network which includes data on both boarding stops and alighting stops. Second, the paper improves the O–D estimation algorithm and empirically examines these improvements, relying on this unique dataset. The evaluation of the last destination assumption of the trip-chaining method shows a significant negative impact on the matching results of the differences between actual boarding/alighting times and the public transport schedules. The proposed changes to the algorithm improve the average distance between the actual and estimated alighting stops, as this distance is reduced from 806 m using the original algorithm to 530 m after applying the suggested improvements.     

A model of pedestrians’ intended waiting times for street crossings at signalized intersections

For the purposes of both traffic-light control and the design of roadway layouts, it is important to understand pedestrian street-crossing behavior because it is not only crucial for improving pedestrian safety but also helps to optimize vehicle flow. This paper explores the mechanism of pedestrian street crossings during the red-man phase of traffic light signals and proposes a model for pedestrians’ waiting times at signalized intersections. We start from a simplified scenario for a particular pedestrian under specific traffic conditions. Then we take into account the interaction between vehicles and pedestrians via statistical unconditioning. We show that this in general leads to a U-shaped distribution of the pedestrians’ intended waiting time. This U-shaped distribution characterizes the nature of pedestrian street-crossing behavior, showing that in general there are a large proportion of pedestrians who cross the street immediately after arriving at the crossing point, and a large proportion of pedestrians who are willing to wait for the entire red-man phase. The U-shaped distribution is shown to reduce to a J-shaped or L-shaped distribution for certain traffic scenarios. The proposed statistical model was applied to analyze real field data.     

Feasibility of using time–space prism to represent available opportunities and choice sets for destination choice models in the context of dynamic urban environments

H?gerstrand??s original framework of time geography and the subsequent time?Cspace prism computational methods form the foundation of a new computational method for potential path areas (PPA) in a realistic representation of dynamic urban environments. In this paper the time?Cspace prism framework is used to assess sensitivity of PPA size to different parameters and to build choice sets for regional destination choice models. We explain the implication of different parameters to choice set formation in a step-wise manner and illustrate not only the complexity of the idea and the high computational demand but also behavioral realism. In this context, this paper tests the feasibility of using constraint-based time?Cspace prism to find the choice sets for a large-scale destination choice model, and identifies a variety of implementation issues. Computational demand is estimated based on a household travel survey for the Southern California Association of Government, and the feasibility of using time?Cspace prisms for destination choice models is assessed with different levels of information on the network and destinations available. The implications of time of day effects and flexibility in scheduling on choice set development due to varying level of service on the network and availability of activity opportunities are discussed and numerically assessed.     

Estimating origin‐destination matrices from link volume counts: a simple intercity auto travel demand model for Sri Lanka

The cost of nation wide travel surveys is high. Hence in many developing countries, planners have found it difficult to develop intercity transportation plans due to the non availability of origin‐destination trip matrices. This paper will describe a method for the intercity auto travel estimation for Sri Lanka with link traffic volume data.

The paper outlines the rationale of selecting the district capitals of Sri Lanka as its “cities,” the methodology for selecting the intercity road network, determination of link travel times from express bus schedules and the location of link volume counting positions.

Initially, the total auto travel demand model is formulated with various trip purpose sub‐models. This model is finally modified to a simple demand model with district urban population and travel times between city pairs as the exogenous variables, to overcome statistical estimation difficulties. The final demand model has statistics within the acceptable regions.

The advantages of a simple model are discussed and possible extensions are proposed.     

Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on state–space–time network representations

Optimization of on-demand transportation systems and ride-sharing services involves solving a class of complex vehicle routing problems with pickup and delivery with time windows (VRPPDTW). This paper first proposes a new time-discretized multi-commodity network flow model for the VRPPDTW based on the integration of vehicles’ carrying states within space–time transportation networks, so as to allow a joint optimization of passenger-to-vehicle assignment and turn-by-turn routing in congested transportation networks. Our three-dimensional state–space–time network construct is able to comprehensively enumerate possible transportation states at any given time along vehicle space–time paths, and further allows a forward dynamic programming solution algorithm to solve the single vehicle VRPPDTW problem. By utilizing a Lagrangian relaxation approach, the primal multi-vehicle routing problem is decomposed to a sequence of single vehicle routing sub-problems, with Lagrangian multipliers for individual passengers’ requests being updated by sub-gradient-based algorithms. We further discuss a number of search space reduction strategies and test our algorithms, implemented through a specialized program in C++, on medium-scale and large-scale transportation networks, namely the Chicago sketch and Phoenix regional networks.