Direct formulation and algorithms for the probit-based stochastic user equilibrium traffic assignment problem

This paper proposes simple and direct formulation and algorithms for the probit-based stochastic user equilibrium traffic assignment problem. It is only necessary to account for random variables independent of link flows by performing a simple transformation of the perceived link travel time with a normal distribution. At every iteration of a Monte-Carlo simulation procedure, the values of the random variables are sampled based on their probability distributions, and then a regular deterministic user equilibrium assignment is carried out to produce link flows. The link flows produced at each iteration of the Monte-Carlo simulation are averaged to yield the final flow pattern. Two test networks demonstrate that the proposed algorithms and the traditional algorithm (the Method of Successive Averages) produce similar results and that the proposed algorithms can be extended to the computation of the case in which the random error term depends on measured travel time.     

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 flow formulation for the traffic assignment problem

In order to improve cooperation between traffic management and travelers, traffic assignment is the key component to achieve the objectives of both traffic management and route choice decisions for travelers. Traffic assignment can be classified into two models based on the behavioral assumptions governing route choices: User Equilibrium (UE) and System Optimum (SO) traffic assignment. According to UE and SO traffic assignment, travelers usually compete to choose the least cost routes to minimize their own travel costs, while SO traffic assignment requires travelers to work cooperatively to minimize overall cost in the road network. Thus, the paradox of benefits between UE and SO indicates that both are not practical. Thus, a solution technique needs to be proposed to balance UE and SO models, which can compromise both sides and give more feasible traffic assignments. In this paper, Stackelberg game theory is introduced to the traffic assignment problem, which can achieve the trade-off process between traffic management and travelers. Since traditional traffic assignments have low convergence rates, the gradient projection algorithm is proposed to improve efficiency.     

Dynamic user equilibrium with side constraints for a traffic network: Theoretical development and numerical solution algorithm

This paper investigates a traffic volume control scheme for a dynamic traffic network model which aims to ensure that traffic volumes on specified links do not exceed preferred levels. The problem is formulated as a dynamic user equilibrium problem with side constraints (DUE-SC) in which the side constraints represent the restrictions on the traffic volumes. Travelers choose their departure times and routes to minimize their generalized travel costs, which include early/late arrival penalties. An infinite-dimensional variational inequality (VI) is formulated to model the DUE-SC. Based on this VI formulation, we establish an existence result for the DUE-SC by showing that the VI admits at least one solution. To analyze the necessary condition for the DUE-SC, we restate the VI as an equivalent optimal control problem. The Lagrange multipliers associated with the side constraints as derived from the optimality condition of the DUE-SC provide the traffic volume control scheme. The control scheme can be interpreted as additional travel delays (either tolls or access delays) imposed upon drivers for using the controlled links. This additional delay term derived from the Lagrange multiplier is compared with its counterpart in a static user equilibrium assignment model. If the side constraint is chosen as the storage capacity of a link, the additional delay can be viewed as the effort needed to prevent the link from spillback. Under this circumstance, it is found that the flow is incompressible when the link traffic volume is equal to its storage capacity. An algorithm based on Euler’s discretization scheme and nonlinear programming is proposed to solve the DUE-SC. Numerical examples are presented to illustrate the mechanism of the proposed traffic volume control scheme.     

Modeling and solving discrete network design problem with stochastic user equilibrium

In this paper, we address the discrete network design problem, which determines the addition of new roads to existing transportation network to optimize the transportation system performance. Road users are assumed to follow the traffic assignment principle of stochastic user equilibrium. A mixed‐integer nonlinear nonconvex problem is developed to model this discrete network design problem with stochastic user equilibrium. The original problem is relaxed into a convex mixed‐integer nonlinear program, whose solution provides a lower bound of the original problem. The relaxed problem is then embedded into two proposed global optimization solution algorithms to obtain the global optimal solution of the problem. Copyright © 2016 John Wiley & Sons, Ltd.     

Multi-class percentile user equilibrium with flow-dependent stochasticity

Travelers often reserve a buffer time for trips sensitive to arrival time in order to hedge against the uncertainties in a transportation system. To model the effects of such behavior, travelers are assumed to choose routes to minimize the percentile travel time, i.e. the travel time budget that ensures their preferred probability of on-time arrival; in doing so, they drive the system to a percentile user equilibrium (UE), which can be viewed as an extension of the classic Wardrop equilibrium. The stochasticity in the supply of transportation are incorporated by modeling the service flow rate of each road segment as a random variable. Such stochasticity is flow-dependent in the sense that the probability density functions of these random variables, from which the distribution of link travel time are constructed, are specified endogenously with flow-dependent parameters. The percentile route travel time, obtained by directly convolving the link travel time distributions in this paper, is not available in closed form in general and has to be numerically evaluated. To reveal their structural properties, percentile UE solutions are examined in special cases and verified with numerical results. For the general multi-class percentile UE traffic assignment problem, a variational inequality formulation is given and solved using a route-based algorithm. The algorithm makes use of the diagonal elements in the Jacobian of percentile route travel time, which is approximated through recursive convolution. Preliminary numerical experiments indicate that the algorithm is able to achieve highly precise equilibrium solutions.     

Toll pricing framework under logit‐based stochastic user equilibrium constraints

This paper addresses the toll pricing framework for the first‐best pricing with logit‐based stochastic user equilibrium (SUE) constraints. The first‐best pricing is usually known as marginal‐cost toll, which can be obtained by solving a traffic assignment problem based on the marginal cost functions. The marginal‐cost toll, however, has rarely been implemented in practice, because it requires every specific link on the network to be charged. Thus, it is necessary to search for a substitute of the marginal cost pricing scheme, which can reduce the toll locations but still minimize the total travel time. The toll pricing framework is the set of all the substitute toll patterns of the marginal cost pricing. Assuming the users' route choice behavior following the logit‐based SUE principle, this paper has first derived a mathematical expression for the toll pricing framework. Then, by proposing an origin‐based variational inequality model for the logit‐based SUE problem, another toll pricing framework is built, which avoids path enumeration/storage. Finally, the numerical test shows that many alternative pricing patterns can inherently reduce the charging locations and total toll collected, while achieving the same equilibrium link flow pattern. Copyright © 2013 John Wiley & Sons, Ltd.     

Formulating the within-day dynamic stochastic traffic assignment problem from a Bayesian perspective

This study proposes a formulation of the within-day dynamic stochastic traffic assignment problem. Considering the stochastic nature of route choice behavior, we treat the solution to the assignment problem as the conditional joint distribution of route traffic, given that the network is in dynamic stochastic user equilibrium. We acquire the conditional joint probability distribution using Bayes’ theorem. A Metropolis–Hastings sampling scheme is developed to estimate the characteristics (e.g., mean and variance) of the route traffic. The proposed formulation has no special requirements for the traffic flow models and user behavior models, and so is easily implemented.     

Private road competition and equilibrium with traffic equilibrium constraints

Toll road competition is one of the important issues under a build-operate-transfer (BOT) scheme, which is being encountered nowadays in many cities. When there are two or more competing firms and each firm operates a competitive toll road, their profits are interrelated due to the competitors' choices and demand inter-dependence in the network. In this paper we develop game-theoretic approaches to the study of the road network, on which multiple toll roads are operated by competitive private firms. The strategic interactions and market equilibria among the private firms are analyzed both in determining their supply (road capacity) and price (toll level) over the network. The toll road competition problems in general traffic equilibrium networks are formulated as an equilibrium program with equilibrium constraints or bi-level variational inequalities. Heuristic solution methods are proposed and their convergences are demonstrated with simple network examples. It is shown that private pricing and competition can be both profitable and welfare-improving.     

Global optimization method for network design problem with stochastic user equilibrium

In this paper, we consider the continuous road network design problem with stochastic user equilibrium constraint that aims to optimize the network performance via road capacity expansion. The network flow pattern is subject to stochastic user equilibrium, specifically, the logit route choice model. The resulting formulation, a nonlinear nonconvex programming problem, is firstly transformed into a nonlinear program with only logarithmic functions as nonlinear terms, for which a tight linear programming relaxation is derived by using an outer-approximation technique. The linear programming relaxation is then embedded within a global optimization solution algorithm based on range reduction technique, and the proposed approach is proved to converge to a global optimum.     

An augmented Lagrangian origin‐based algorithm for link‐capacitated traffic assignment problem

The origin‐based algorithm is embedded into the augmented Lagrangian method for the link‐capacitated traffic assignment problem. In order to solve the “nonexistence” problem due to the second partial derivatives of the augmented Lagrangian function at some specific points, the approximate expressions of the second partial derivatives are amended in the origin‐based algorithm. The graph of last common nodes is developed on the basis of the restricted single‐origin network. A method is proposed for finding n–1 last common nodes of the restricted single‐origin network, resulting in computational complexity of O(n²) in finding last common nodes. Numerical analysis on the Sioux Falls network and Chicago Sketch network demonstrated the effectiveness and characteristics of the proposed algorithm. Copyright © 2014 John Wiley & Sons, Ltd.     

Risk‐based stochastic equilibrium assignment model in augmented urban railway network

This study developed a methodology to model the passenger flow stochastic assignment in urban railway network (URN) with the considerations of risk attitude. Through the network augmentation technique, the urban railway system is represented by an augmented network in which the common traffic assignment method can be used directly similar to a generalized network form. Using the analysis of different cases including deterministic travel state, emergent event, peak travel, and completely stochastic state, we developed a stochastic equilibrium formulation to capture these stochastic considerations and give effects of risk aversion level on the URN performance, the passenger flow at transfer stations through numerical studies. Copyright © 2012 John Wiley & Sons, Ltd.     

Robust Wardrop’s user equilibrium assignment under stochastic demand and supply: Expected residual minimization approach

Various models of traffic assignment under stochastic environment have been proposed recently, mainly by assuming different travelers’ behavior against uncertainties. This paper focuses on the expected residual minimization (ERM) model to provide a robust traffic assignment with an emphasis on the planner’s perspective. The model is further extended to obtain a stochastic prediction of the traffic volumes by the technique of path choice approach. We show theoretically the existence and the robustness of the ERM solution. In addition, we employ an improved solution algorithm for solving the ERM model. Numerical experiments are carried out to illustrate the characteristics of the proposed model, by comparing with other existing models.     

Modeling absolute and relative cost differences in stochastic user equilibrium problem

This paper aims to develop a hybrid closed-form route choice model and the corresponding stochastic user equilibrium (SUE) to alleviate the drawbacks of both Logit and Weibit models by simultaneously considering absolute cost difference and relative cost difference in travelers’ route choice decisions. The model development is based on an observation that the issues of absolute and relative cost differences are analogous to the negative exponential and power impedance functions of the trip distribution gravity model. Some theoretical properties of the hybrid model are also examined, such as the probability relationship among the three models, independence from irrelevant alternatives, and direct and indirect elasticities. To consider the congestion effect, we provide a unified modeling framework to formulate the Logit, Weibit and hybrid SUE models with the same entropy maximization objective but with different total cost constraint specifications representing the modelers’ knowledge of the system. With this, there are two ways to interpret the dual variable associated with the cost constraint: shadow price representing the marginal change in the entropy level to a marginal change in the total cost, and dispersion/shape parameter representing the travelers’ perceptions of travel costs. To further consider the route overlapping effect, a path-size factor is incorporated into the hybrid SUE model. Numerical examples are also provided to illustrate the capability of the hybrid model in handling both absolute and relative cost differences as well as the route overlapping problem in travelers’ route choice decisions.     

On seat capacity in traffic assignment to a transit network

Seating or standing make distinct on‐board states to a transit rider, yielding distinct discomfort costs, with potential influence on the passenger route choice onto the transit network. The paper provides a transit assignment model that captures the seating capacity and its occupancy along any transit route. The main assumptions pertain to: the seat capacity by service route, selfish user behaviour, a seat allocation process with priority rules among the riders, according to their prior state either on‐board or at boarding. To each transit leg from access to egress station is associated a set of ‘service modes’, among which the riders are assigned in a probabilistic way, conditionally on their priority status and the ratio between the available capacity and the flow of them. Thus the leg cost is a random variable, with mean value to be included in the trip disutility. Computationally efficient algorithms are provided for, respectively, loading the leg flows and evaluating the leg costs along a transit line. At the network level, a hyperpath formulation is provided for supply‐demand equilibrium, together with a property of existence and an method of successive averages equilibration algorithm. It is shown that multiple equilibria may arise. Copyright © 2010 John Wiley & Sons, Ltd.     

Stochastic cell transmission model (SCTM): A stochastic dynamic traffic model for traffic state surveillance and assignment

The paper proposes a first-order macroscopic stochastic dynamic traffic model, namely the stochastic cell transmission model (SCTM), to model traffic flow density on freeway segments with stochastic demand and supply. The SCTM consists of five operational modes corresponding to different congestion levels of the freeway segment. Each mode is formulated as a discrete time bilinear stochastic system. A set of probabilistic conditions is proposed to characterize the probability of occurrence of each mode. The overall effect of the five modes is estimated by the joint traffic density which is derived from the theory of finite mixture distribution. The SCTM captures not only the mean and standard deviation (SD) of density of the traffic flow, but also the propagation of SD over time and space. The SCTM is tested with a hypothetical freeway corridor simulation and an empirical study. The simulation results are compared against the means and SDs of traffic densities obtained from the Monte Carlo Simulation (MCS) of the modified cell transmission model (MCTM). An approximately two-miles freeway segment of Interstate 210 West (I-210W) in Los Ageles, Southern California, is chosen for the empirical study. Traffic data is obtained from the Performance Measurement System (PeMS). The stochastic parameters of the SCTM are calibrated against the flow-density empirical data of I-210W. Both the SCTM and the MCS of the MCTM are tested. A discussion of the computational efficiency and the accuracy issues of the two methods is provided based on the empirical results. Both the numerical simulation results and the empirical results confirm that the SCTM is capable of accurately estimating the means and SDs of the freeway densities as compared to the MCS.     

A path-size weibit stochastic user equilibrium model

The aim of this paper is to develop a path-size weibit (PSW) route choice model with an equivalent mathematical programming (MP) formulation under the stochastic user equilibrium (SUE) principle that can account for both route overlapping and route-specific perception variance problems. Specifically, the Weibull distributed random error term handles the identically distributed assumption such that the perception variance with respect to different trip lengths can be distinguished, and a path-size factor term is introduced to resolve the route overlapping issue by adjusting the choice probabilities for routes with strong couplings with other routes. A multiplicative Beckmann’s transformation (MBec) combined with an entropy term are used to develop the MP formulation for the PSW-SUE model. A path-based algorithm based on the partial linearization method is adopted for solving the PSW-SUE model. Numerical examples are also provided to illustrate features of the PSW-SUE model and its differences compared to some existing SUE models as well as its applicability on a real-size network.     

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.     

Distributed computing approaches for large‐scale probit‐based stochastic user equilibrium problems

Applications of probit‐based stochastic user equilibrium (SUE) principle on large‐scale networks have been largely limited because of the overwhelming computational burden in solving its stochastic network loading problem. A two‐stage Monte Carlo simulation method is recognized to have satisfactory accuracy level when solving this stochastic network loading. This paper thus works on the acceleration of the Monte Carlo simulation method via using distributed computing system. Three distributed computing approaches are then adopted on the workload partition of the Monte Carlo simulation method. Wherein, the first approach allocates each processor in the distributed computing system to solve each trial of the simulation in parallel and in turns, and the second approach assigns all the processors to solve the shortest‐path problems in one trial of the Monte Carlo simulation concurrently. The third approach is a combination of the first two, wherein both different trials of the Monte Carlo simulation as well as the shortest path problems in one trial are solved simultaneously. Performances of the three approaches are comprehensively tested by the Sioux‐Falls network and then a randomly generated network example. It shows that computational time for the probit‐based SUE problem can be largely reduced by any of these three approaches, and the first approach is found out to be superior to the other two. The first approach is then selected to calculate the probit‐based SUE problem on a large‐scale network example. Copyright © 2011 John Wiley & Sons, Ltd.     

Cost scaling based successive approximation algorithm for the traffic assignment problem

This paper presents a cost scaling based successive approximation algorithm, called ε-BA (ε-optimal bush algorithm), to solve the user equilibrium traffic assignment problem by successively refining ε-optimal flows. As ε reduces to zero, the user equilibrium solution is reached. The proposed method is a variant of bush-based algorithms, and also a variant of the min-mean cycle algorithm to solve the min-cost flow by successive approximation. In ε-BA, the restricted master problem, implying traffic equilibration restricted on a bush, is solved to ε-optimality by cost scaling before bush reconstruction. We show that ε-BA can reduce the number of flow operations substantially in contrast to Dial’s Algorithm B, as the former operates flows on a set of deliberately selected cycles whose mean values are sufficiently small. Further, the bushes can be constructed effectively even if the restricted master problem is not solved to a high level of convergence, by leveraging the ε-optimality condition. As a result, the algorithm can solve a highly precise solution with faster convergence on large-scale networks compared to our implementation of Dial’s Algorithm B.