Bicriterion shortest path problem with a general nonadditive cost

A bicriterion shortest path problem with a general nonadditive cost seeks to optimize a combination of two path costs, one of which is evaluated by a nonlinear function. This paper first identifies a number of emerging transportation applications for which such a shortest path problem might be considered a core subproblem. We propose to first approximate the general nonlinear cost function with a piecewise linear counterpart, and then solve each linear subproblem sequentially. A specialized algorithm is developed to solve the subproblems, which makes use of the efficient path set (or the convex hull) to update upper and lower bounds of the original problem. Conditions under which the solution to a subproblem must belong to the efficient path set are specified. Accordingly, we show that the optimal path must be efficient if the nonlinear cost function is concave. If the optimal path to a subproblem is not efficient, partial path enumeration, implemented using a simple K-shortest path ranking procedure, is conducted to close the gap. The proposed algorithm includes strategies aiming to expedite path enumeration by using upper bounds derived from the efficient path set. Numerical experiments are conducted to demonstrate correctness and effectiveness of the proposed algorithm.     

Short-term travel time prediction

Effective prediction of travel times is central to many advanced traveler information and transportation management systems. In this paper we propose a method to predict freeway travel times using a linear model in which the coefficients vary as smooth functions of the departure time. The method is straightforward to implement, computationally efficient and applicable to widely available freeway sensor data.We demonstrate the effectiveness of the proposed method by applying the method to two real-life loop detector data sets. The first data set––on I-880––is relatively small in scale, but very high in quality, containing information from probe vehicles and double loop detectors. On this data set the prediction error ranges from 5% for a trip leaving immediately to 10% for a trip leaving 30 min or more in the future. Having obtained encouraging results from the small data set, we move on to apply the method to a data set on a much larger spatial scale, from Caltrans District 12 in Los Angeles. On this data set, our errors range from about 8% at zero lag to 13% at a time lag of 30 min or more. We also investigate several extensions to the original method in the context of this larger data set.     

Vehicle reidentification and travel time measurement across freeway junctions using the existing detector infrastructure

Conventional vehicle detectors are capable of monitoring discrete points along the freeway but do not provide information about conditions on the link between detectors. Knowledge of conditions on the link is useful to operating agencies for enabling timely decisions in response to various delay causing events and hence to reduce the resulting congestion of the freeway system. This paper presents an approach that matches vehicle measurements between detector stations to provide information on the conditions over the link between the detectors rather than relying strictly on the aggregate point measurements from the detectors. In particular this work reidentifies measurements from distinct vehicles using the existing loop detector infrastructure. Here the distinct vehicles are the long vehicles, but depending on the vehicle population or type of detector used, one might chose to use some other reproducible feature.This new methodology represents an important advancement over preceding loop based vehicle reidentification, as illustrated herein, it enables vehicle reidentification across a major diverge and a major merge. The examples include a case where the reidentification algorithm responded to delay between two detector stations an hour before the delay was locally observable at either of the stations used for reidentification. While previous loop based reidentification work was limited to dual loop detectors, the present effort also extends the methodology to single loop detectors; thereby making it more widely applicable. Although the research uses loop detector data, the algorithm would be equally applicable to data obtained from many other traffic detectors that provide reproducible vehicle features.     

Hybrid model of taxonomy and genetic algorithms for finding shortest path in transportation systems

This is research is aimed at elaborating a new methodology of shortest path finding by utilizing the methods of taxonomy and genetic algorithms. Combination of the two is developed and called Genetic Taxonomy Evaluator (GTE) which is expected to be an alternative tool to solve shortest path finding problems within the transportation networks While keeping the properties of transportation networks Taxonomy Reconstructor (TR) transforms the network representation into taxonomic structure, which is hierarchically shaped, based on problem to be solved. In the process TR also creates classification of nodes in the network. This classification provides facilities to isolate the problem to the core, and the criteria that can be inserted in the Genetic Algorithm (GA). A package program for GTE is then developed in C-Language and performance of model is analyzed upon a medium scale of Sioux-Falls City Network. In conclusion, it is found that to achieve fairly quick convergence of GTE computation several optimal parameters of GA should be determined prior to searching for the shortest paths. And since GTE has only been applied to limited case, it is suggested that the findings could be a threshold for further researches.     

On the dual approach to the traffic assignment problem

This paper attempts to explore the possibility of solving the traffic assignment problem with elastic demands by way of its dual problem. It is shown that the dual problem can be formulated as a nonsmooth convex optimization problem of which the objective function values and subgradients are conveniently calculated by solving shortest path problems associated with the transportation network. A subgradient algorithm to solve the dual problem is presented and limited computational experience is reported. The computational results are encouraging enough to demonstrate the effectiveness of the proposed approach.     

Optimal freeway ramp metering using the asymmetric cell transmission model

The onramp metering control problem is posed using a cell transmission-like model called the asymmetric cell transmission model (ACTM). The problem formulation captures both freeflow and congested conditions, and includes upper bounds on the metering rates and on the onramp queue lengths. It is shown that a near-global solution to the resulting nonlinear optimization problem can be found by solving a single linear program, whenever certain conditions are met. The most restrictive of these conditions requires the congestion on the mainline not to back up onto the onramps whenever optimal metering is used. The technique is tested numerically using data from a severely congested stretch of freeway in southern California. Simulation results predict a 17.3% reduction in delay when queue constraints are enforced.     

Automated detection of lane-blocking freeway incidents using artificial neural networks

A major source of urban freeway delay in the U.S. is non-recurring congestion caused by incidents. The automated detection of incidents is an important function of a freeway traffic management center. A number of incident detection algorithms, using inductive loop data as input, have been developed over the past several decades, and a few of them are being deployed at urban freeway systems in major cities. These algorithms have shown varying degrees of success in their detection performance. In this paper, we present a new incident detection technique based on artificial neural networks (ANNs). Three types of neural network models, namely the multi-layer feedforward (MLF), the self-organizing feature map (SOFM) and adaptive resonance theory 2 (ART2), were developed to classify traffic surveillance data obtained from loop detectors, with the objective of using the classified output to detect lane-blocking freeway incidents. The models were developed with simulation data from a study site and tested with both simulation and field data at the same site. The MLF was found to have the highest potential, among the three ANNs, to achieve a better incident detection performance. The MLF was also tested with limited field data collected from three other freeway locations to explore its transferability. Our results and analyzes with data from the study site as well as the three test sites have shown that the MLF consistently detected most of the lane-blocking incidents and typically gave a false alarm rate lower than the California, McMaster and Minnesota algorithms currently in use.     

Network sensor health problem

Many existing studies on the sensor health problem determine an individual sensor’s health status based on the statistical characteristics of collected data by the sensor. In this research, we study the sensor health problem at the network level, which is referred to as the network sensor health problem. First, based on the conservation principle of daily flows in a network, we separate all links into base links and non-base links, such that the flows on the latter can be calculated from those on the former. In reality, the network flow conservation principle can be violated due to the existence of unhealthy sensors. Then we define the least inconsistent base set of links as those that minimize the sum of squares of the differences between observed and calculated flows on non-base links. But such least inconsistent base sets may not be unique in a general road network. Finally we define the health index of an individual sensor as the frequency that it appears in all of the least inconsistent base sets. Intuitively, a lower health index suggests that the corresponding sensor is more likely to be unhealthy. We present the brute force method to find all least inconsistent base sets and calculate the health indices. We also propose a greedy search algorithm to calculate the approximate health indices more efficiently. We solve the network sensor health problem for a real-world example with 16 nodes and 30 links, among which 18 links are monitored with loop detectors. Using daily traffic count data from the Caltrans Performance Measurement System (PeMS) database, we use both the brute-force and greedy search methods to calculate the health indices for all the sensors. We find that all the four sensors flagged as unhealthy (high value) by PeMS have the lowest health indices. This confirms that a sensor with a lower health index is more likely to be unhealthy. Therefore, we can use such health indices to determine the relative reliability of different sensors’ data and prioritize the maintenance of sensors.     

Traffic state estimation and uncertainty quantification based on heterogeneous data sources: A three detector approach

This study focuses on how to use multiple data sources, including loop detector counts, AVI Bluetooth travel time readings and GPS location samples, to estimate macroscopic traffic states on a homogeneous freeway segment. With a generalized least square estimation framework, this research constructs a number of linear equations that map the traffic measurements as functions of cumulative vehicle counts on both ends of a traffic segment. We extend Newell’s method to solve a stochastic three-detector problem, where the mean and variance estimates of cell-based density and flow can be analytically derived through a multinomial probit model and an innovative use of Clark’s approximation method. An information measure is further introduced to quantify the value of heterogeneous traffic measurements for improving traffic state estimation on a freeway segment.     

Innovative detector layout for automated traffic turning volume counting

Because of many advantages, loop detectors are the most common practice for obtaining data to control intersections. However, they have some drawbacks, including the fact that multiple detectors are usually required to monitor a location. The current practice in many cities is to install four consecutive loop detectors per lane, or two at the stop bar and one as an advanced detector. In some cities, there are also departure detectors. All these configurations have some practical problems and do not produce accurate counts especially in shared lanes. In this paper, a new placement configuration for departure detectors is proposed and named the mid‐intersection detector (MID). In this configuration, departure detectors are moved back to the middle of the intersection in such a way that they can be activated by more than one movement at different times. In some cases, departure detectors lack equations for calculating turning movements, a problem solved by MIDs because each movement passes more detectors along its path (without increasing the number of loops), and therefore they can produce more accurate and reliable data for obtaining turning movement counts. Copyright © 2017 John Wiley & Sons, Ltd.     

A discrete-convex programming approach to the simultaneous optimization of land use and transportation

Three design problems are discussed in this article. First, it is shown that the network design problem with congestion reduces to an all-or nothing traffic assignment problem under some assumptions on the congestion function and the investment cost function. Second, the land use design problem is formulated as an extension of the Koopmans-Beckmann problem and a heuristic is proposed to solve this problem. Third, it is shown that the seemingly more complex problem of designing jointly a land-use plan and a transportation network reduces to a pure land-use design problem. All that is needed to solve the joint optimization problem is a shortest path algorithm and a heuristic to solve the land use design problem. Computational experience is reported for each algorithm.     

A network model for gate assignment

In this research we developed a network model that will help the airport authorities assign flights to gates both efficiently and effectively. The model was formulated as a multi-commodity network flow problem. An algorithm based on the Lagrangian relaxation, with subgradient methods, accompanied by a shortest path algorithm and a Lagrangian heuristic was developed to solve the problem. The model was tested using data from Chiang Chiek-Shek Airport.     

On the equivalence of common rearrangements for sum constrained travel estimation problems

This paper examines the problem of estimating the parameters of nonlinear sum constrained models by use of rearrangements to permit linear estimation methods. Over the years a number of different, and sometimes ingenious, techniques have been proposed but a remaining difficulty arises from the fact that different rearrangements lead to different parameter estimates. In this paper it is shown that while ordinary least squares certainly results in different estimates, generalised least squares leads to identical parameter estimates provided convergence to the true maximum likelihood estimates is achieved. In particular it is seen that estimates are invariant with choice of base or deletion of one equation and identical for the single base, multinominal logit, geometric mean and link constant versions. The findings of this paper apply to any sum-constrained model and in transportation these occur very frequently as mode choice problems, singly-constrained gravity models, and as route choice models in path assignment. While we develop all results in this paper in the context of an intercity passenger modal market share model, the transferability of these results to other problems should be recognised.     

A predictive dynamic traffic assignment model in congested capacity-constrained road networks

In this paper, a predictive dynamic traffic assignment model in congested capacity-constrained road networks is formulated. A traffic simulator is developed to incrementally load the traffic demand onto the network, and updates the traffic conditions dynamically. A time-dependent shortest path algorithm is also given to determine the paths with minimum actual travel time from an origin to all the destinations. The traffic simulator and time-dependent shortest path algorithm are employed in a method of successive averages to solve the dynamic equilibrium solution of the problem. A numerical example is given to illustrate the effectiveness of the proposed method.     

Properties of a well-defined macroscopic fundamental diagram for urban traffic

A field experiment in Yokohama (Japan) revealed that a macroscopic fundamental diagram (MFD) linking space-mean flow, density and speed exists on a large urban area. It was observed that when the highly scattered plots of flow vs. density from individual fixed detectors were aggregated the scatter nearly disappeared and points grouped along a well defined curve. Despite these and other recent findings for the existence of well-defined MFDs for urban areas, these MFDs should not be universally expected. In this paper we investigate what are the properties that a network should satisfy, so that an MFD with low scatter exists. We show that the spatial distribution of vehicle density in the network is one of the key components that affect the scatter of an MFD and its shape. We also propose an analytical derivation of the spatial distribution of congestion that considers correlation between adjacent links. We investigate the scatter of an MFD in terms of errors in the probability density function of spatial link occupancy and errors of individual links’ fundamental diagram (FD). Later, using real data from detectors for an urban arterial and a freeway network we validate the proposed derivations and we show that an MFD is not well defined in freeway networks as hysteresis effects are present. The datasets in this paper consist of flow and occupancy measures from 500 fixed sensors in the Yokohama downtown area in Japan and 600 loop detectors in the Twin Cities Metropolitan Area Freeway network in Minnesota, USA.     

Parametric search for the bi-attribute concave shortest path problem

A bi-attribute concave shortest path (BC-SP) problem seeks to find an optimal path in a bi-attribute network that minimizes a linear combination of two path costs, one of which is evaluated by a nondecreasing concave function. Due to the nonadditivity of its objective function, Bellman’s principle of optimality does not hold. This paper proposes a parametric search method to solve the BC-SP problem, which only needs to solve a series of shortest path problems, i.e., the parameterized subproblems (PSPs). Several techniques are developed to reduce both the number of PSPs and the computation time for these PSPs. Specifically, we first identify two properties of the BC-SP problem to guide the parametric search using the gradient and concavity of its objective function. Based on the properties, a monotonic descent search (MDS) and an intersection point search (IPS) are proposed. Second, we design a speedup label correcting (LC) algorithm, which uses optimal solutions of previously solved PSPs to reduce the number of labeling operations for subsequent PSPs. The MDS, IPS and speedup LC techniques are embedded into a branch-and-bound based interval search to guarantee optimality. The performance of the proposed method is tested on the mean-standard deviation shortest path problem and the route choice problem with a quadratic disutility function. Experiments on both real transportation networks and grid networks show that the proposed method reduces the computation time of existing algorithms by one to two orders of magnitude.     

A recursive, cell processing model for predicting freeway travel times

Travel time information influences driver behaviour and can contribute to reducing congestion and improving network efficiency. Consequently many road authorities disseminate travel time information on road side signs, web sites and radio traffic broadcasts. Operational systems commonly rely on speed data obtained from inductive loop detectors and estimate travel times using simple algorithms that are known to provide poor predictions particularly on either side of the peak period. This paper presents a new macroscopic model for predicting freeway travel times which overcomes the limitations of operational ‘instantaneous’ speed models by drawing on queuing theory to model the processing of vehicles in sections or cells of the freeway. The model draws on real-time speed, flow and occupancy data and is formulated to accommodate varying geometric conditions, the relative distribution of vehicles along the freeway, variations in speed limits, the impact of ramp flows and fixed or transient bottlenecks. Field validation of the new algorithm was undertaken using data from two operational freeways in Melbourne, Australia. Consistent with the results of simulation testing, the validation confirmed that the recursive model provided a substantial improvement in travel time predictions when compared to the model currently used to provide real-time travel time information to motorists in Melbourne.     

Finding the k reliable shortest paths under travel time uncertainty

This paper investigates the problem of finding the K reliable shortest paths (KRSP) in stochastic networks under travel time uncertainty. The KRSP problem extends the classical K loopless shortest paths problem to the stochastic networks by explicitly considering travel time reliability. In this study, a deviation path approach is established for finding K α-reliable paths in stochastic networks. A deviation path algorithm is proposed to exactly solve the KRSP problem in large-scale networks. The A^* technique is introduced to further improve the KRSP finding performance. A case study using real traffic information is performed to validate the proposed algorithm. The results indicate that the proposed algorithm can determine KRSP under various travel time reliability values within reasonable computational times. The introduced A^* technique can significantly improve KRSP finding performance.     

Heterogeneous sensor location model for path reconstruction

A new traffic sensor location problem is developed and solved by strategically placing both passive and active sensors in a transportation network for path reconstruction. Passive sensors simply count vehicles, while active sensors can recognize vehicle plates but are more expensive. We developed a two-stage heterogeneous sensor location model to determine the most cost-effective strategies for sensor deployment. The first stage of the model adopts the path reconstruction model defined by Castillo et al. (2008b) to determine the optimal locations of active sensors in the network. In the second stage, an algebraic framework is developed to strategically replace active sensors so that the total installation cost can be reduced while maintaining path flow observation quality. Within the algebraic framework, a scalar product operator is introduced to calculate path flows. An extension matrix is generated and used to determine if a replacement scheme is able to reconstruct all path flows. A graph model is then constructed to determine feasible replacement schemes. The problem of finding the optimal replacement scheme is addressed by utilizing the theory of maximum clique to obtain the upper bound of the number of replaced sensors and then revising this upper bound to generate the optimal replacement scheme. A polynomial-time algorithm is proposed to solve the maximum clique problem, and the optimal replacement scheme can be obtained accordingly. Three numerical experiments show that our proposed two-stage method can reduce the total costs of transportation surveillance systems without affecting the system monitor quality. The locations of the active sensors play a more critical role than the locations of the passive sensors in the number of reconstructed paths.     

An application of the CUSUM algorithm to freeway incident detection based on two contiguous detectors

The CUSUM (cumulative sum of log‐likelihood ratio) algorithm is a detection algorithm that shows potential for the improvement of incident detection algorithms because it is designed to minimize the mean detect delay for a given false alarm constraint and it can also detect changes with different patterns. In this study, the CUSUM algorithm was applied to freeway incident detection by integrating traffic measurements from two contiguous loop detectors and the non‐stationarity of traffic flows. The developed algorithm was tested based on incident data from the PATH program, with consideration given to the impact of different geometric conditions on algorithm performance. It was also compared with two existing algorithms, in order to address the influence of traffic patterns. The evaluation results show that the CUSUM incident detection algorithm can perform equally well in comparison with the selected algorithms.