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.     

The dual of the traffic assignment problem with elastic demands

This article is concerned with the dual of the traffic assignment problem, and of the combined generation, distribution, and assignment problem. The duals, and duality relations, for the arc-chain and node-arc formulations of the problem are derived using only the Kuhn-Tucker conditions for convex programs. This has the advantage of being more familiar to most readers than the conjugate function presentation which has been used elsewhere.     

A modified Frank-Wolfe algorithm for solving the traffic assignment problem

This paper presents a very simple modification of the Frank-Wolfe algorithm for the solution of the traffic assignment problem. It is shown that the modified algorithm can be implemented without much increase in computational effort over the original one. Convergence of the algorithm is proved and computational results are reported to demonstrate the validity of the modification.     

An equilibrium algorithm for the spatial aggregation problem of traffic assignment

Present traffic assignment methods require that all possible origins and destinations of trips taking place within a study area be represented as if they were taking place to and from a small set of points or centroids. Each centroid is supposed to represent the location of all trip-ends within a given zone, and this necessarily misrepresents points located at the edges of the zone.In order to alleviate this problem (which we refer to as the spatial aggregation problem) one could use smaller zones and more centroids, but existing traffic assignment algorithms cannot efficiently handle many centroids.This paper introduces an algorithm procedure which is designed to handle a substantially larger number of centroids. In the paper that follows, the technique is further developed to take into account a continuous distribution of population.     

A cell-based Merchant-Nemhauser model for the system optimum dynamic traffic assignment problem

A cell-based variant of the Merchant-Nemhauser (M-N) model is proposed for the system optimum (SO) dynamic traffic assignment (DTA) problem. Once linearized and augmented with additional constraints to capture cross-cell interactions, the model becomes a linear program that embeds a relaxed cell transmission model (CTM) to propagate traffic. As a result, we show that CTM-type traffic dynamics can be derived from the original M-N model, when the exit-flow function is properly selected and discretized. The proposed cell-based M-N model has a simple constraint structure and cell network representation because all intersections and cells are treated uniformly. Path marginal costs are defined using a recursive formula that involves a subset of multipliers from the linear program. This definition is then employed to interpret the necessary condition, which is a dynamic extension of the Wardrop’s second principle. An algorithm is presented to solve the flow holding back problem that is known to exist in many discrete SO-DTA models. A numerical experiment is conducted to verify the proposed model and algorithm.     

General stochastic user equilibrium traffic assignment problem with link capacity constraints

This paper addresses a general stochastic user equilibrium (SUE) traffic assignment problem with link capacity constraints. It first proposes a novel linearly constrained minimization model in terms of path flows and then shows that any of its local minimums satisfies the generalized SUE conditions. As the objective function of the proposed model involves path‐specific delay functions without explicit mathematical expressions, its Lagrangian dual formulation is analyzed. On the basis of the Lagrangian dual model, a convergent Lagrangian dual method with a predetermined step size sequence is developed. This solution method merely invokes a subroutine at each iteration to perform a conventional SUE traffic assignment excluding link capacity constraints. Finally, two numerical examples are used to illustrate the proposed model and solution method.     

The existence of an equilibrium solution to the traffic assignment problem when there are junction interactions

We consider a network with interactions and capacity constraints at each junction. We give conditions on the interactions and constraints which, if satisfied at each separate junction, ensure that any feasible assignment problem has an equilibrium solution. Two illustrative examples are provided; the first arises naturally and does not satisfy our conditions, while the second does satisfy our conditions but is somewhat unnatural.     

Network representation,continuum approximations and a solution to the spatial aggregation problem of traffic assignment

This paper complements the preceding one, which showed how one could modify equilibrium traffic assignment algorithms for networks with many centroids. In this one it is shown how one can substitute centroids by zones with continuous population densities. The technique, which is mathematically guaranteed to approximate a flow pattern in accordance with Wardrop's user equilibrium criterion, requires some geometrical calculations which can be handled off-line. With the suggested approach, it is possible to represent the spatial distribution of trip ends more realistically and this allows traffic assignment models to capture the effects of short and intrazonal trips in a way previously impossible. The method is shown to be computationally feasible.     

Some developments in equilibrium traffic assignment

A network optimization problem is formulated which yields a probabilistic equilibrated traffic assignment incorporating congestion effects and which as a special case, reduces to a user optimized equilibrium solution. In the resulting model, path choice is determined by a logit formula in which path costs are functions of the assigned flows. The article also demonstrates the similarity between some fixed demand incremental methods of traffic assignment and the minimization problem associated with computing the user equilibrium assignment.     

The dynamics of traffic assignment and traffic control: A theoretical study

The paper considers traffic assignment, with traffic controls, in an increasingly dynamic way. First, a natural way of introducing the responsive policy, P_o, into steady state traffic assignment is presented. Then it is shown that natural stability results follow within a dynamical version of this static equilibrium model (still with a constant demand). We are able to obtain similar stability results when queues are explicitly allowed for, provided demand is constant. Finally we allow demand to vary with time; we consider the dynamic assignment problem with signal-settings now fixed. Here we assume that vehicles are very short and that deterministic queueing theory applies, and show that the time-dependent queueing delay at the bottleneck at the end of a link is a monotone function of the time-dependent input profile to the bottleneck. We have been unable to obtain results when dynamic demand and responsive signal control are combined.     

Junction interactions and monotonicity in traffic assignment

We consider the traffic equilibrium problem when the travel demand is inelastic and stationary in time. Junction interactions, which abound in urban road networks, are permitted. We prove that the set of equilibria (solutions to the assignment problem) is convex when certain monotonicity and continuity conditions are statisfied at each junction.     

On a link-based day-to-day traffic assignment model

In this paper, we perform a rigorous analysis on a link-based day-to-day traffic assignment model recently proposed in He et al. (2010). Several properties, including the invariance set and the constrained stability, of this dynamical process are established. An extension of the model to the asymmetric case is investigated and the stability result is also established under slightly more restrictive assumptions. Numerical experiments are conducted to demonstrate the findings.     

More paradoxes in the equilibrium assignment problem

The sensitivity of travel costs to changes in input flows in the Wardrop equilibrium problem is studied. Examples are given showing that both origin to destination and global travel costs may decrease as a result of an increase in input flows. Other examples show that, in the two-mode equilibrium assignment problem transit origin to destination travel costs may decrease as a result of an increase in automobile input flows.     

A dynamic traffic assignment model for the assessment of moving bottlenecks

Moving bottlenecks in highway traffic are defined as a situation in which a slow-moving vehicle, be it a truck hauling heavy equipment or an oversized vehicle, or a long convey, disrupts the continuous flow of the general traffic. The effect of moving bottlenecks on traffic flow is an important factor in the evaluation of network performance. This effect, though, cannot be assessed properly by existing transportation tools, especially when the bottleneck travels relatively long distances in the network.This paper develops a dynamic traffic assignment (DTA) model that can evaluate the effects of moving bottlenecks on network performance in terms of both travel times and traveling paths. The model assumes that the characteristics of the moving bottleneck, such as traveling path, physical dimensions, and desired speed, are predefined and, therefore, suitable for planned conveys.The DTA model is based on a mesoscopic simulation network-loading procedure with unique features that allow assessing the special dynamic characteristics of a moving bottleneck. By permitting traffic density and speed to vary along a link, the simulation can capture the queue caused by the moving bottleneck while preserving the causality principles of traffic dynamics.     

Accessibility, entropy and the distribution and assignment of traffic revisited

An optimizing model which minimizes average generalised trip cost subject to constraints on the entropy was given in a previous paper. In this note the model is placed in a planning context.     

Dynamic system-optimal traffic assignment using a state space model

We propose a new mathematical formulation for the problem of optimal traffic assignment in dynamic networks with multiple origins and destinations. This problem is motivated by route guidance issues that arise in an Intelligent Vehicle-Highway Systems (IVHS) environment. We assume that the network is subject to known time-varying demands for travel between its origins and destinations during a given time horizon. The objective is to assign the vehicles to links over time so as to minimize the total travel time experienced by all the vehicles using the network. We model the traffic network over the time horizon as a discrete-time dynamical system. The system state at each time instant is defined in a way that, without loss of optimality, avoids complete microscopic detail by grouping vehicles into platoons irrespective of origin node and time of entry to network. Moreover, the formulation contains no explicit path enumeration. The state transition function can model link travel times by either impedance functions, link outflow functions, or by a combination of both. Two versions (with different boundary conditions) of the problem of optimal traffic assignment are studied in the context of this model. These optimization problems are optimal control problems for nonlinear discrete-time dynamical systems, and thus they are amenable to algorithmic solutions based on dynamic programming. The computational challenges associated with the exact solution of these problems are discussed and some heuristics are proposed.     

Dynamic user optimal traffic assignment on congested multidestination networks

An equivalent continuous time optimal control problem is formulated to predict the temporal evolution of traffic flow pattern on a congested multiple origin-destination network, corresponding to a dynamic generalization of Wardropian user equilibrium. Optimality conditions are derived using the Pontryagin minimum principle and given economic interpretations, which are generalizations of similar results previously reported for single-destination networks. Analyses of sufficient conditions for optimality and of singular controls are also given. Under the steady-state assumptions, the model is shown to be a proper dynamic extension of Beckmann's mathematical programming problem for a static user equilibrium traffic assignment.     

Convergence of the Frank-Wolfe method for certain bounded variable traffic assignment problems

In two recent papers published in Transportation Research, Daganzo presented a modification of the Frank-Wolfe algorithm to solve certain link capacitated traffic assignment problems satisfying certain conditions. In order to show convergence of the modified algorithm, the assumption was made that the integral of the volume delay formula for each link tends to infinity as the link flow approaches the link capacity. In this paper we give a Theorem which establishes convergence of the modified algorithm under much weaker conditions. This result is then used to show convergence if the objective function of the assignment model is sufficiently large (not necessarily infinite) when the link flows are at capacity. Thus the modified method is applicable to a broader class of assignment problems. Two numerical examples illustrate (a) when the method converges and when it does not, and (b) that our Theorem provides a weaker condition for convergence of the method.     

An algorithm for the combined distribution and assignment problem

Much interest has recently been shown in the combination of the distribution and assignment models. In this paper we adopt a generalized Benders' decomposition to solve this combined problem for a system optimized assignment with linear link costs and explicit capacity constraints on link flows. The master problem which is generated is used to show that the combined problem can be viewed as a modified distribution problem, of gravity form, with a minimax instead of a linear objective function. An algorithm for solving the master problem is discussed, and some computational results presented.