A note on the turn and arrival likelihood algorithms of traffic assignments

This note illustrates by means of examples that two of the three modifications of Dial's assignment algorithm suggested recently by Tobin (1977) should be subject to further research prior to implementation. Three potential problems with these algorithms are shown to be significant for small contrived networks.     

Some remarks on Wilson's gravity model and a slight generalization of it

The aim of this note is to establish some connections between Wilson's gravity model, Jaynes' principle of maximum entropy, Kullback's divergence, Watanabe's measure of connection, the minimum information principle of Snickars and Weibull and Guiasu's principle of minimum interdependence as a special form of Kullback's minimum divergence. A slight generalization of Wilson's gravity model is proposed.     

Dynamic location: an iconic model to synchronize temporal and spatial transportation data

This paper describes a model to synchronize the management and query of temporal and spatially referenced transportation data in geographic information systems (GIS). The model employs a method referred to as dynamic location, which facilitates spatial intersect queries from geographic shapes without the use of topological relationships. This is the inverse of how dynamic segmentation works in GIS. In contrast to dynamic segmentation, dynamic location stores geometry as an object within a single database field. This is an efficient, precise iconic model superseding the need for data decomposition into a complex set of tables. As an object model, the dynamic location process lends itself to high performance in an Internet, data-intensive, enterprise environment. Linear events are stored as {x, y} features, and not referenced to any route system. Route systems are built from {x, y, m} values (m for measure) and serve as number lines for mathematical operations. Any {x, y} object can then be referenced to either the Cartesian grid or any selected number line. This method offers the benefits of linear referencing, while making full use of a stable geodetic datum. Combinations of any {x, y} events may be placed over any {x, y, m} number line (route) and an intersect determined by looking through stacked {x, y, m} vertices of the coincident shapes. Since both geometry and shape reside in the same record, the use of “begin” and “end” dates facilitates full spatial and temporal version control. From a business process perspective, this creates a spatially enabled database, pulling GIS business functions back into the information technology mainstream.     

Developing an enhanced weight-based topological map-matching algorithm for intelligent transport systems

Map-matching (MM) algorithms integrate positioning data from a Global Positioning System (or a number of other positioning sensors) with a spatial road map with the aim of identifying the road segment on which a user (or a vehicle) is travelling and the location on that segment. Amongst the family of MM algorithms consisting of geometric, topological, probabilistic and advanced, topological MM (tMM) algorithms are relatively simple, easy and quick, enabling them to be implemented in real-time. Therefore, a tMM algorithm is used in many navigation devices manufactured by industry. However, existing tMM algorithms have a number of limitations which affect their performance relative to advanced MM algorithms. This paper demonstrates that it is possible by addressing these issues to significantly improve the performance of a tMM algorithm. This paper describes the development of an enhanced weight-based tMM algorithm in which the weights are determined from real-world field data using an optimisation technique. Two new weights for turn-restriction at junctions and link connectivity are introduced to improve the performance of matching, especially at junctions. A new procedure is developed for the initial map-matching process. Two consistency checks are introduced to minimise mismatches. The enhanced map-matching algorithm was tested using field data from dense urban areas and suburban areas. The algorithm identified 96.8% and 95.93% of the links correctly for positioning data collected in urban areas of central London and Washington, DC, respectively. In case of suburban area, in the west of London, the algorithm succeeded with 96.71% correct link identification with a horizontal accuracy of 9.81 m (2σ). This is superior to most existing topological MM algorithms and has the potential to support the navigation modules of many Intelligent Transport System (ITS) services.     

Consistent link flow estimation from counts

Partly because of counting errors and partly because counts may be carried out on different days, traffic counts on links of a network are unlikely to satisfy the flow conservation constraint “flow IN = flow out” at every node of the network. Van Zuylen and Willumsen (1980) have described a method of eliminating inconsistencies in traffic counts when a single count is available for each link in the network. In this paper, the method is extended to the case when more than one count is available on some links of the network. In addition, an algorithm is described for application of the method.     

“Local background” levels of carbon monoxide in an urban area

The objective of this study was to obtain a better understanding of carbon monoxide (CO) concentrations immediately upwind of urban roadways, the “local background” values, and how these concentrations depend upon the surrounding traffic and the general meteorology. Measurements were made at seven sites in Seattle, WA during the winter of 1993. Local background CO concentrations were characterized by an absence of short term fluctuations, a steady buildup during the 3 p.m. to 11 p.m. period, and a lack of spatial gradients in the 8-h average values. Distinctly different log-normal distributions of the 8-h averages were observed for “trafficked” sites versus “urban park” sites, with mean values of 1.6 and 1.0 ppm respectively. A simple regression model was developed to predict the local background CO that includes distance from roadway, average daily traffic of nearby roadways, and the frequency of occurrence of low wind speeds (R² = 0.74; F = 170).     

Vehicle reidentification and travel time measurement on congested freeways

The paper presents an algorithm for matching individual vehicles measured at a freeway detector with the vehicles’ corresponding measurements taken earlier at another detector located upstream. Although this algorithm is potentially compatible with many vehicle detector technologies, the paper illustrates the method using existing dual-loop detectors to measure vehicle lengths. This detector technology has seen widespread deployment for velocity measurement. Since the detectors were not developed to measure vehicle length, these measurements can include significant errors. To overcome this problem, the algorithm exploits drivers’ tendencies to retain their positions within dense platoons. The otherwise complicated task of vehicle reidentification is carried out by matching these platoons rather than individual vehicles. Of course once a vehicle has been matched across neighboring detector stations, the difference in its arrival time at each station defines the vehicle’s travel time on the intervening segment.Findings from an application of the algorithm over a 1/3 mile long segment are presented herein and they indicate that a sufficient number of vehicles can be matched for the purpose of traffic surveillance. As such, the algorithm extracts travel time data without requiring the deployment of new detector technologies. In addition to the immediate impacts on traffic monitoring, the work provides a means to quantify the potential benefits of emerging detector technologies that promise to extract more detailed information from individual vehicles.     

An equilibration scheme for the traffic assignment problem with elastic demands

This note presents an algorithm for the solution of the traffic assignment problem with elastic demands. The algorithm is based on the concept of “equilibration operator” introduced by Dafermos and Sparrow (1969) for the solution of the traffic assignment problem with fixed demands. Computational experience is provided for linear and nonlinear problems for both the algorithm proposed here and the Dafermos-Sparrow algorithm applied to the “excess-demand” reformulations of the problems.     

Algorithms for logit-based stochastic user equilibrium assignment

The paper proposes an efficient algorithm for determining the stochastic user equilibrium solution for logit-based loading. The commonly used Method of Successive Averages typically has a very slow convergence rate. The new algorithm described here uses Williams’ result [ Williams, (1977) On the formation of travel demand models and economic evaluation measures of user benefit. Environment and Planning 9A(3), 285–344] which enables the expected value of the perceived travel costs S_rs to be readily calculated for any flow vector x. This enables the value of the Sheffi and Powell, 1982 objective function [Sheffi, Y. and Powell, W. B. (1982) An algorithm for the equilibrium assignment problem with random link times. Networks 12(2), 191–207], and its gradient in any specified search direction, to be calculated. It is then shown how, at each iteration, an optimal step length along the search direction can be easily estimated, rather than using the pre-set step lengths, thus giving much faster convergence. The basic algorithm uses the standard search direction (towards the auxiliary solution). In addition the performance of two further versions of the algorithm are investigated, both of which use an optimal step length but alternative search directions, based on the Davidon–Fletcher–Powell function minimisation method. The first is an unconstrained and the second a constrained version. Comparisons are made of all three versions of the algorithm, using a number of test networks ranging from a simple three-link network to one with almost 3000 links. It is found that for all but the smallest network the version using the standard search direction gives the fastest rate of convergence. Extensions to allow for multiple user classes and elastic demand are also possible.     

A path-based user-equilibrium traffic assignment algorithm that obviates path storage and enumeration

This paper presents a novel user-equilibrium (UE) traffic assignment algorithm, which under conventional assumptions, promises to compute UE arc flows to acceptable precision, regardless of the network’s topology, size or congestion:

• The algorithm takes the simple approach of shifting flow from a costliest path to a cheapest path until the costs of all used paths are within a given of the cheapest.

• Because of being path-based, it avoids tailing.

• In spite of being path-based, it neither stores nor enumerates paths.

• These efficiencies derive from decomposing the problem into a sequence of easy single-origin problems on acyclic sub-networks.

Solutions to this sequence of sub-network flows converge rapidly to a sharp practical estimate of UE arc flows—as is amply demonstrated by tests using the Chicago region’s 40,000-arc network model.     

Evaluating the assumption of independent turning probabilities

Several urban traffic models make the convenient assumption that turning probabilities are independent, meaning that the probability of turning right (or left or going straight through) at the downstream intersection is the same for all travelers on that roadway, regardless of their origin or destination. In reality most travelers make turns according to planned routes from origins to destinations. The research reported here identifies and quantifies the deviations that result from this assumption of independent turning probabilities.An analysis of this type requires a set of reasonably realistic “original” route flows, which were obtained by a static user-equilibrium traffic assignment and an entropy maximization condition for most likely route flows. These flows are compared with those route flows resulting from the Assumption of Independent Turning Probabilities (ITP). A small subnetwork of 3 km by 5 km in Tucson, Arizona, was chosen as a case study. An overall “typical ratio” of 2.2 between original route flows and ITP route flows was obtained. Aggregating route flows to origin–destination flows led to an overall “typical ratio” of 1.7. Such deviations are particularly high for routes that go back-and-forth, reaching a ratio of more than 3 in certain time periods. Substantial deviations for origins and destinations that are on the same border of the subnetwork are also observed in the analyses. In addition, under the ITP assumption, morning rush hour traffic peaking is the same in all directions, while in the original flows some directions do not exhibit a peak in the morning rush hour period. Overall, the conclusion of the paper is that the assumption of independent turning probabilities leads to substantial deviations both at the route level and at the origin–destination level, even for such a small network of the case study. These deviations are particularly detrimental when a network is being modeled and studied for route-based measures of effectiveness such as the number and types of routes passing a point – for monitoring specified vehicles and/or managing detouring strategies.     

Spillback congestion in dynamic traffic assignment: A macroscopic flow model with time-varying bottlenecks

In this paper, we propose a new model for the within-day Dynamic Traffic Assignment (DTA) on road networks where the simulation of queue spillovers is explicitly addressed, and a user equilibrium is expressed as a fixed-point problem in terms of arc flow temporal profiles, i.e., in the infinite dimension space of time’s functions. The model integrates spillback congestion into an existing formulation of the DTA based on continuous-time variables and implicit path enumeration, which is capable of explicitly representing the formation and dispersion of vehicle queues on road links, but allows them to exceed the arc length. The propagation of congestion among adjacent arcs will be achieved through the introduction of time-varying exit and entry capacities that limit the inflow on downstream arcs in such a way that their storage capacities are never exceeded. Determining the temporal profile of these capacity constraints requires solving a system of spatially non-separable macroscopic flow models on the supply side of the DTA based on the theory of kinematic waves, which describe the dynamic of the spillback phenomenon and yield consistent network performances for given arc flows. We also devise a numerical solution algorithm of the proposed continuous-time formulation allowing for “long time intervals” of several minutes, and give an empirical evidence of its convergence. Finally, we carry out a thorough experimentation in order to estimate the relevance of spillback modeling in the context of the DTA, compare the proposed model in terms of effectiveness with the Cell Transmission Model, and assess the efficiency of the proposed algorithm and its applicability to real instances with large networks.     

A practical concern about the relevance of alternative-specific constants for new alternatives in simple logit models

When a “new” alternative is introduced, post-estimation, into a logit model, analysis initially exclude an ASC or occasionally assume a correspondence with an existing alternative. Using a recent data set for mode and route choice, the paper highlights the forecasting implications of ignoring the ASC in the utility expression of a “new” alternative, and how sensitive the market shares are to the inclusion/ exclusion of the ASC.     

Modeling measurement errors and missing initial values in freeway dynamic origin–destination estimation systems

Most existing dynamic origin–destination (O–D) estimation approaches are grounded on the assumption that a reliable initial O–D set is available and traffic volume data from detectors are accurate. However, in most traffic systems, both types of critical information are either not available or subjected to some level of measurement errors such as traffic counts and speed measurement from sensors. To contend with those critical issues, this study presents two robust algorithms, one for estimation of an initial O–D set and the other for tackling the input measurement errors with an extended estimation algorithm. The core concept of the initial O–D estimation algorithm is to decompose the target network in a number of sub-networks based on proposed rules, and then execute the estimation of the initial O–D set iteratively with the observable information at the first time interval. To contend with the inevitable detector measurement error, this study proposes an interval-based estimation algorithm that converts each model input data as an interval with its boundaries being set based on some prior knowledge. The performance of both proposed algorithms has been tested with a simulated system, the I-95 freeway corridor between I-495 and I-695, and the results are quite promising.     

Reverse time-restricted shortest paths: Application to air traffic management

In this paper, we consider a particular class of network flow problems that seeks a shortest path, if it exists, between a source node s and a destination node d in a connected digraph, such that we arrive at node d at a specified time τ while leaving node s no earlier than a lower-bounding time LB, and where the availability of each network link is time-dependent in the sense that it can be traversed only during specified intervals of time. We refer to this problem as the reverse time-restricted shortest path problem (RTSP), and it arises, for example, in the context of generating flight plans within air traffic management approaches under severe convective weather conditions. We show that this problem is NP-hard in general, but is polynomially solvable under a special regularity condition. A pseudo-polynomial time dynamic programming algorithm is developed to solve Problem RTSP, along with an effective heap implementation strategy. Computational results using real flight generation test cases as well as random simulated problems are presented.     

A route-based solution algorithm for dynamic user equilibrium assignments

The aim of this study is to establish a method to calculate good quality user equilibrium assignments under time varying conditions. For this purpose, it introduces a dynamic network loading method that can maintain correct flow propagation as well as flow conservation, and it shows a novel route-based solution algorithm. This novel algorithm turns out to be convenient and logically plausible compared to the conventional [Frank, M., Wolfe, P., 1956. An algorithm for quadratic programming. Naval Research Logistics Quarterly 3, 95–110] algorithm, because the former does not require evaluation of an objective function and it finds solutions maintaining correct flow propagation in the time-varying network conditions. The application of novel dynamic network loading method and solution algorithm to test networks shows that we can find high quality dynamic user equilibrium assignment. This is illustrated in an example network using the deterministic queuing model for a link performance function and associating costs and flows in a predictive way in discrete time.     

Energy-efficient operation of rail vehicles

This paper describes an analytical process that computes the optimal operating successions of a rail vehicle to minimize energy consumption. Rising energy prices and environmental concerns have made energy conservation a high priority for transportation operations. The cost of energy consumption makes up a large portion of the Operation and Maintenance (O&M) costs of transit especially rail transit systems. Energy conservation or reduction in energy cost may be one of the effective ways to reduce transit operating cost, therefore improve the efficiency of transit operations.From a theoretical point of view, the problem of energy efficient train control can be formulated as one of the functions of Optimal Control Theory. However, the classic numerical optimization methods such as discrete method of optimum programming are too slow to be used in an on-board computer even with the much improved computation power, today. The contribution of this particular research is the analytical solution that gives the sequence of optimal controls and equations to find the control change points. As a result, a calculation algorithm and a computer program for energy efficient train control has been developed. This program is also capable of developing energy efficient operating schedules by optimizing distributions of running time for an entire route or any part of rail systems.We see the major application of the proposed algorithms in fully or partially automated Train Control Systems. The modern train control systems, often referred as “positive” train control (PTC), have collected a large amount of information to ensure safety of train operations. The same data can be utilized to compute the optimum controls on-board to minimize energy consumption based on the algorithms proposed in this paper. Most of the input data, such as track plan, track profile, traction and braking characteristics, speed limits and required trip time are located in an on-board database and/or they can be transmitted via radio link to be processed by the proposed algorithm and program.     

Spatiotemporal evolution of China’s railway network in the 20th century: An accessibility approach

The interrelatedness of transportation development and economic growth has been a constant theme of geographic inquiries, particularly in economic and transportation geography. This paper analyzes the expansion of China’s railway network, the evolution of its spatial accessibility, and the impacts on economic growth and urban systems over a time span of about one century (1906–2000). First, major historical events and policies and their effects on railway development in China are reviewed and grouped into four major eras: preliminary construction, network skeleton, corridor building, and deep intensification. All four eras followed a path of “inland expansion.” Second, spatial distribution of accessibility and its evolution are analyzed. The spatial structure of China’s railway network is characterized by “concentric rings” with its major axis in North China and the most accessible city gradually migrating from Tianjin to Zhengzhou. Finally, the study indicates that railway network expansion has significantly improved economic development and heavily influenced the formation of urban systems in China.     

A simple algorithm for the estimation of road traffic space mean speeds from data available to most management centres

The control of the evolution of road traffic streams is highly related to productivity, safety, sustainability and, even, comfort. Although, nowadays, the findings from research efforts and the development of new technologies enable accurate traffic forecasts in almost any conditions, these calculations are usually limited by the data and the equipment available. Most traffic management centres depend on the data provided, at best, by double-loop detectors. These loops supply time means over different aggregation periods, which are indiscriminately used as the bases for subsequent estimations. Since space mean speeds are those needed in most applications (note the fundamental relationship between flow and density in traffic flow theory), most current practice begins with an error. This paper introduces a simple algorithm that the allows estimation of space mean speeds from the data provided by the loops without the need for any additional financial outlay, as long as the traffic in each time interval of aggregation is stationary and its speed distribution is log-normal. Specifically, it is focused on the calculation of the variance of the speeds with regard to the time mean, thus making possible to use the relationship between time mean speeds and space mean speeds defined by Rakha (2005). The results obtained with real data show that the algorithm behaves well if the calculation conditions help fulfil the initial hypotheses. The primary difficulties arise with transient traffic and, in this case, other specific methodologies should be used. Data fusion seems promising in this regard. Nevertheless, it cannot be denied that the improvement provided by the algorithm turns out to be highly beneficial both when used alone in the case of stationarity or as a part of a fusion.     

On the convergence of the algorithm for bilevel programming problems by Clegg and Smith

In Clegg and Smith [Transportation Research B 35 (2001) 71–82] and Battye et al. [in: M. Patriksson, M. Labbe (Eds.), Transportation Planning – State of the Art, Proceedings of the 6th Meeting of the EURO Working Group on Transportation, Gothenburg, Sweden, September 9–11, 1998, Kluwer Academic Publishers, Dordrecht], Smith and colleagues present an algorithm for solving the bilevel programming problem. We show that the points reached by the algorithm are not stationary points of bilevel programs in general. We further show that, with a minor modification, this method can be expressed as an inexact penalty method for gap function-constrained bilevel programs.