Entropy weighted average method for the determination of a single representative path flow solution for the static user equilibrium traffic assignment problem

The formulation of the static user equilibrium traffic assignment problem (UETAP) under some simplifying assumptions has a unique solution in terms of link flows but not in terms of path flows. Large variations are possible in the path flows obtained using different UETAP solution algorithms. Many transportation planning and management applications entail the need for path flows. This raises the issue of generating a meaningful path flow solution in practice. Past studies have sought to determine a single path flow solution using the maximum entropy concept. This study proposes an alternate approach to determine a single path flow solution that represents the entropy weighted average of the UETAP path flow solution space. It has the minimum expected Euclidean distance from all other path flow solution vectors of the UETAP. The mathematical model of the proposed entropy weighted average method is derived and its solution stability is proved. The model is easy to interpret and generalizes the proportionality condition of Bar-Gera and Boyce (1999). Results of numerical experiments using networks of different sizes suggest that the path flow solutions for the UETAP using the proposed method are about identical to those obtained using the maximum entropy approach. The entropy weighted average method requires low computational effort and is easier to implement, and can therefore serve as a potential alternative to the maximum entropy approach in practice.     

Eco-system optimal time-dependent flow assignment in a congested network

This research addresses the eco-system optimal dynamic traffic assignment (ESODTA) problem which aims to find system optimal eco-routing or green routing flows that minimize total vehicular emission in a congested network. We propose a generic agent-based ESODTA model and a simplified queueing model (SQM) that is able to clearly distinguish vehicles’ speed in free-flow and congested conditions for multi-scale emission analysis, and facilitates analyzing the relationship between link emission and delay. Based on the SQM, an expanded space-time network is constructed to formulate the ESODTA with constant bottleneck discharge capacities. The resulting integer linear model of the ESODTA is solved by a Lagrangian relaxation-based algorithm. For the simulation-based ESODTA, we present the column-generation-based heuristic, which requires link and path marginal emissions in the embedded time-dependent least-cost path algorithm and the gradient-projection-based descent direction method. We derive a formula of marginal emission which encompasses the marginal travel time as a special case, and develop an algorithm for evaluating path marginal emissions in a congested network. Numerical experiments are conducted to demonstrate that the proposed algorithm is able to effectively obtain coordinated route flows that minimize the system-wide vehicular emission for large-scale networks.     

Path-constrained traffic assignment: A trip chain analysis under range anxiety

This paper proposes and analyzes a distance-constrained traffic assignment problem with trip chains embedded in equilibrium network flows. The purpose of studying this problem is to develop an appropriate modeling tool for characterizing traffic flow patterns in emerging transportation networks that serve a massive adoption of plug-in electric vehicles. This need arises from the facts that electric vehicles suffer from the “range anxiety” issue caused by the unavailability or insufficiency of public electricity-charging infrastructures and the far-below-expectation battery capacity. It is suggested that if range anxiety makes any impact on travel behaviors, it more likely occurs on the trip chain level rather than the trip level, where a trip chain here is defined as a series of trips between two possible charging opportunities (Tamor et al., 2013). The focus of this paper is thus given to the development of the modeling and solution methods for the proposed traffic assignment problem. In this modeling paradigm, given that trip chains are the basic modeling unit for individual decision making, any traveler’s combined travel route and activity location choices under the distance limit results in a distance-constrained, node-sequenced shortest path problem. A cascading labeling algorithm is developed for this shortest path problem and embedded into a linear approximation framework for equilibrium network solutions. The numerical result derived from an illustrative example clearly shows the mechanism and magnitude of the distance limit and trip chain settings in reshaping network flows from the simple case characterized merely by user equilibrium.     

Traffic assignment by paired alternative segments

The static user-equilibrium (UE) traffic assignment model is widely used in practice. One main computational challenge in this model is to obtain sufficiently precise solutions suitable for scenario comparisons, as quickly as possible. An additional computational challenge stems from the need in practice to perform analyses based on route flows, which are not uniquely determined by the UE condition. Past research focused mainly on the first aspect. The purpose of this paper is to describe an algorithm that addresses both issues. The traffic assignment by paired alternative segments (TAPAS) algorithm, focuses on pairs of alternative segments as the key building block to the UE solution. A condition of proportionality, which is practically equivalent to entropy maximization, is used to choose one stable route flow solution. Numerical results for five publicly available networks, including two large-scale realistic networks, show that the algorithm can identify highly precise solutions that maintain proportionality in relatively short computation times.     

Node modeling for congested urban road networks

First-order network flow models are coupled systems of differential equations which describe the build-up and dissipation of congestion along network road segments, known as link models. Models describing flows across network junctions, referred to as node models, play the role of the coupling between the link models and are responsible for capturing the propagation of traffic dynamics through the network. Node models are typically stated as optimization problems, so that the coupling between the link dynamics is not known explicitly. This renders network flow models analytically intractable. This paper examines the properties of node models for urban networks. Solutions to node models that are free of traffic holding, referred to as holding-free solutions, are formally defined and it is shown that flow maximization is only a sufficient condition for holding-free solutions. A simple greedy algorithm is shown to produce holding-free solutions while also respecting the invariance principle. Staging movements through nodes in a manner that prevents conflicting flows from proceeding through the nodes simultaneously is shown to simplify the node models considerably and promote unique solutions. The staging also models intersection capacities in a more realistic way by preventing unrealistically large flows when there is ample supply in the downstream and preventing artificial blocking when some of the downstream supplies are restricted.     

Optimization models for differentiating quality of service levels in probabilistic network capacity design problems

This paper develops various chance-constrained models for optimizing the probabilistic network design problem (PNDP), where we differentiate the quality of service (QoS) and measure the related network performance under uncertain demand. The upper level problem of PNDP designs continuous/discrete link capacities shared by multi-commodity flows, and the lower level problem differentiates the corresponding QoS for demand satisfaction, to prioritize customers and/or commodities. We consider PNDP variants that have either fixed flows (formulated at the upper level) or recourse flows (at the lower level) according to different applications. We transform each probabilistic model into a mixed-integer program, and derive polynomial-time algorithms for special cases with single-row chance constraints. The paper formulates benchmark stochastic programming models by either enforcing to meet all demand or penalizing unmet demand via a linear penalty function. We compare different models and approaches by testing randomly generated network instances and an instance built on the Sioux–Falls network. Numerical results demonstrate the computational efficacy of the solution approaches and derive managerial insights.     

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.     

Preferences for travel time under risk and ambiguity: Implications in path selection and network equilibrium

In this paper, we study the preferences for uncertain travel times in which probability distributions may not be fully characterized. In evaluating an uncertain travel time, we explicitly distinguish between risk, where the probability distribution is precisely known, and ambiguity, where it is not. In particular, we propose a new criterion called ambiguity-aware CARA travel time (ACT) for evaluating uncertain travel times under various attitudes of risk and ambiguity, which is a preference based on blending the Hurwicz criterion and Constant Absolute Risk Aversion (CARA). More importantly, we show that when the uncertain link travel times are independently distributed, finding the path that minimizes travel time under the ACT criterion is essentially a shortest path problem. We also study the implications on Network Equilibrium (NE) model where travelers on the traffic network are characterized by their knowledge of the network uncertainty as well as their risk and ambiguity attitudes under the ACT. We derive and analyze the existence and uniqueness of solutions under NE. Finally, we obtain the Price of Anarchy that characterizes the inefficiency of this new equilibrium. The computational study suggests that as uncertainty increases, the influence of selfishness on inefficiency diminishes.     

Approximate network loading and dual-time-scale dynamic user equilibrium

In this paper we present a dual-time-scale formulation of dynamic user equilibrium (DUE) with demand evolution. Our formulation belongs to the problem class that Pang and Stewart (2008) refer to as differential variational inequalities. It combines the within-day time scale for which route and departure time choices fluctuate in continuous time with the day-to-day time scale for which demand evolves in discrete time steps. Our formulation is consistent with the often told story that drivers adjust their travel demands at the end of every day based on their congestion experience during one or more previous days. We show that analysis of the within-day assignment model is tremendously simplified by expressing dynamic user equilibrium as a differential variational inequality. We also show there is a class of day-to-day demand growth models that allow the dual-time-scale formulation to be decomposed by time-stepping to yield a sequence of continuous time, single-day, dynamic user equilibrium problems. To solve the single-day DUE problems arising during time-stepping, it is necessary to repeatedly solve a dynamic network loading problem. We observe that the network loading phase of DUE computation generally constitutes a differential algebraic equation (DAE) system, and we show that the DAE system for network loading based on the link delay model (LDM) of Friesz et al. (1993) may be approximated by a system of ordinary differential equations (ODEs). That system of ODEs, as we demonstrate, may be efficiently solved using traditional numerical methods for such problems. To compute an actual dynamic user equilibrium, we introduce a continuous time fixed-point algorithm and prove its convergence for effective path delay operators that allow a limited type of nonmonotone path delay. We show that our DUE algorithm is compatible with network loading based on the LDM and the cell transmission model (CTM) due to Daganzo (1995). We provide a numerical example based on the much studied Sioux Falls network.     

Bayesian inference for day-to-day dynamic traffic models

There is significant current interest in the development of models to describe the day-to-day evolution of traffic flows over a network. We consider the problem of statistical inference for such models based on daily observations of traffic counts on a subset of network links. Like other inference problems for network-based models, the critical difficulty lies in the underdetermined nature of the linear system of equations that relates link flows to the latent path flows. In particular, Bayesian inference implemented using Markov chain Monte Carlo methods requires that we sample from the set of route flows consistent with the observed link flows, but enumeration of this set is usually computationally infeasible.We show how two existing conditional route flow samplers can be adapted and extended for use with day-to-day dynamic traffic. The first sampler employs an iterative route-by-route acceptance–rejection algorithm for path flows, while the second employs a simple Markov model for traveller behaviour to generate candidate entire route flow patterns when the network has a tree structure. We illustrate the application of these methods for estimation of parameters that describe traveller behaviour based on daily link count data alone.     

The dynamic shortest path problem with time-dependent stochastic disruptions

The dynamic shortest path problem with time-dependent stochastic disruptions consists of finding a route with a minimum expected travel time from an origin to a destination using both historical and real-time information. The problem is formulated as a discrete time finite horizon Markov decision process and it is solved by a hybrid Approximate Dynamic Programming (ADP) algorithm with a clustering approach using a deterministic lookahead policy and value function approximation. The algorithm is tested on a number of network configurations which represent different network sizes and disruption levels. Computational results reveal that the proposed hybrid ADP algorithm provides high quality solutions with a reduced computational effort.     

Norm approximation method for handling traffic count inconsistencies in path flow estimator

Path flow estimator (PFE) is a one-stage network observer proposed to estimate path flows and hence origin–destination (O–D) flows from traffic counts in a transportation network. Although PFE does not require traffic counts to be collected on all network links when inferring unmeasured traffic conditions, it does require all available counts to be reasonably consistent. This requirement is difficult to fulfill in practice due to errors inherited in data collection and processing. The original PFE model handles this issue by relaxing the requirement of perfect replication of traffic counts through the specification of error bounds. This method enhances the flexibility of PFE by allowing the incorporation of local knowledge, regarding the traffic conditions and the nature of traffic data, into the estimation process. However, specifying appropriate error bounds for all observed links in real networks turns out to be a difficult and time-consuming task. In addition, improper specification of the error bounds could lead to a biased estimation of total travel demand in the network. This paper therefore proposes the norm approximation method capable of internally handling inconsistent traffic counts in PFE. Specifically, three norm approximation criteria are adopted to formulate three L_p-PFE models for estimating consistent path flows and O–D flows that simultaneously minimize the deviation between the estimated and observed link volumes. A partial linearization algorithm embedded with an iterative balancing scheme and a column generation procedure is developed to solve the three L_p-PFE models. In addition, the proposed L_p-PFE models are illustrated with numerical examples and the characteristics of solutions obtained by these models are discussed.     

The impact of speed limits on traffic equilibrium and system performance in networks

Speed limits are usually imposed on roads in an attempt to enhance safety and sometimes serve the purpose of reducing fuel consumption and vehicular emissions as well. Most previous studies up to date focus on investigation of the effects of speed limits from a local perspective, while network-wide traffic reallocation effects are overlooked. This paper makes the first attempt to investigate how a link-specific speed limit law reallocates traffic flow in an equilibrium manner at a macroscopic network level. We find that, although the link travel time–flow relationship is altered after a speed limit is imposed, the standard traffic assignment method still applies. With the commonly adopted assumptions, the uniqueness of link travel times at user equilibrium (UE) remains valid, and the UE flows on links with non-binding speed limits are still unique. The UE flows on other links with binding speed limits may not be unique but can be explicitly characterized by a polyhedron or a linear system of equalities and inequalities. Furthermore, taking into account the traffic reallocation effects of speed limits, we compare the capability of speed limits and road pricing for decentralizing desirable network flow patterns. Although from a different perspective for regulating traffic flows with a different mechanism, a speed limit law may play the same role as a toll charge scheme and perform better than some negative (rebate) toll schemes under certain conditions for network flow management.     

A semi-analytical approach for solving the bottleneck model with general user heterogeneity

This paper proposes a novel semi-analytical approach for solving the dynamic user equilibrium (DUE) of a bottleneck model with general heterogeneous users. The proposed approach makes use of the analytical solutions from the bottleneck analysis to create an equivalent assignment problem that admits closed-form commute cost functions. The equivalent problem is a static and asymmetric traffic assignment problem, which can be formulated as a variational inequality problem (VIP). This approach provides a new tool to analyze the properties of the bottleneck model with general heterogeneity, and to design efficient solution methods. In particular, the existence and uniqueness of the DUE solution can be established using the P-property of the Jacobian matrix. Our numerical experiments show that a simple decomposition algorithm is able to quickly solve the equivalent VIP to high precision. The proposed VIP formation is also extended to address simultaneous departure time and route choice in a single O–D origin-destination network with multiple parallel routes.     

A dynamic shortest path algorithm using multi‐step ahead link travel time prediction

In this paper, a multi‐step ahead prediction algorithm of link travel speeds has been developed using a Kalman filtering technique in order to calculate a dynamic shortest path. The one‐step and the multi‐step ahead link travel time prediction models for the calculation of the dynamic shortest path have been applied to the directed test network that is composed of 16 nodes: 3 entrance nodes, 2 exit nodes and 11 internal nodes. Time‐varying traffic conditions such as flows and travel time data for the test network have been generated using the CORSIM model. The results show that the multi‐step ahead algorithm is compared more favorably for searching the dynamic shortest time path than the other algorithm.     

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.     

Freight Data Assembling and Modeling: Methodologies and Practice

Abstract

In comparison to personal travel, freight movements within large metropolitan areas are much less studied. Most conventional transportation models and planning analysis that disregarded freight flows have been criticized on the plausibility of their results and conclusions. To alleviate these problems, this study proposes a non-survey based approach to assemble and process freight data in a systematic way. A freight origin–destination (OD) matrix of freight flows can be developed using secondary data sources. The estimated freight flows can be loaded together with conventional passenger flows onto the regional highway network of a large metropolitan area. As a case study, this non-survey based approach was applied to build a freight OD and study the traffic flows in Los Angeles. It concluded that this approach can be used to analyze urban freight movement in a low-cost way in which planning agencies can overcome the common omission of freight flow information in their transportation plans.     

Aggregation effects on the network design problem

This article examines the effects of various network extraction schemes on the network design problem. Given an original network, many criteria can be used to identify subnetworks on which the network design problem is solved. For the purposes of this article, these subnetworks are obtained using an extraction algorithm which preserves the magnitude of the user equilibrium flows on the links of these subnetworks. The results of the implementation of the network design problem on the original and the extracted subnetworks are presented and compared. We conclude that very good solutions to the network design problem can be obtained from the use of highly aggregate networks.     

Quadratic approximation and convergence of some bush-based algorithms for the traffic assignment problem

This paper first shows that LUCE (Gentile, 2012), a recent addition to the family of bush-based algorithms, is closely related to OBA (Bar-Gera, 2002). LUCE’s promise comes mainly from its use of the greedy method for solving the quadratic approximation of node-based subproblems, which determines the search direction. While the greedy algorithm accelerates the solution of the subproblems and reduces the cost of line search, it unexpectedly disrupts the overall convergence performance in our experiments, which consistently show that LUCE failed to converge beyond certain threshold of relative gap. Our analysis suggests that the root cause to this interesting behavior is the inaccurate quadratic approximation constructed on faulty information of second-order derivatives. Because the quadratic approximations themselves are inaccurate, the search directions generated from them are sub-optimal. Unlike OBA, however, LUCE does not have a mechanism to correct these search directions through line search, which explains why its convergence performance suffers the observed breakdowns. We also attempt to improve LUCE using the ideas that have been experimented for the improvement of OBA. While these improvements do work, their effects are not enough to counteract the inability to adjust sub-optimal search directions. Importantly, the fact that the search direction has to be corrected in line search to ensure smooth convergence attests to the limitation of origin-based flow aggregation shared by both OBA and LUCE. These findings offer guidelines for the design of high performance traffic assignment algorithms.