The existence, uniqueness and computation of an arc-based dynamic network user equilibrium formulation

In this paper, a dynamic user equilibrium traffic assignment model with simultaneous departure time/route choices and elastic demands is formulated as an arc-based nonlinear complementarity problem on congested traffic networks. The four objectives of this paper are (1) to develop an arc-based formulation which obviates the use of path-specific variables, (2) to establish existence of a dynamic user equilibrium solution to the model using Brouwer's fixed-point theorem, (3) to show that the vectors of total arc inflows and associated minimum unit travel costs are unique by imposing strict monotonicity conditions on the arc travel cost and demand functions along with a smoothness condition on the equilibria, and (4) to develop a heuristic algorithm that requires neither a path enumeration nor a storage of path-specific flow and cost information. Computational results are presented for a simple test network with 4 arcs, 3 nodes, and 2 origin–destination pairs over the time interval of 120 periods.     

Regulating hazardous materials transportation by dual toll pricing

We investigate dual-toll setting as a policy tool to mitigate the risk of hazardous material (hazmat) shipment in road networks. We formulate the dual-toll problem as a bi-level program wherein the upper level aims at minimizing the risk, and the lower level explores the user equilibrium decision of the regular vehicles and hazmat carriers given the toll. When the upper level objective is to minimize the risk and all links are tollable, we decompose the formulation into first-stage and second-stage, and suggest a computational method to solve each stage. Our two-stage solution methodology guarantees nonnegative valid dual tolls regardless of the solution accuracy of the first-stage problem. We also consider a general dual-toll setting problem where the regulator rather wishes to minimize a combination of risk and the paid tolls and/or some links are untollable. To solve this truly bilevel problem, we provide heuristic algorithms that decompose the problem into subproblems each being solved by a line search. Case studies based on the Sioux Falls network illustrate the insights on the dual-toll policies.     

A time series analysis of monthly ridership for an urban rail rapid transit line

This paper presents two time series regression models, one in linear form and the other in logarithmic form, to estimate the monthly ridership of a single urban rail rapid transit line. The model was calibrated for a time period of about six and a half years (from 1978–1984) based on ridership data provided by a transit authority, gasoline prices provided by a state energy department, and other data.The major findings from these models are: (1) seasonal variations of ridership are –6.26%, or –6.20% for the summer period, and 4.77%, or 4.62% for the October period; (2) ridership loss due to a station closure is 2.46% or 2.41%; and (3) elasticities of monthly ridership are –0.233 or –0.245 with respect to real fare, 0.113 or 0.112 with respect to real gasoline price, and 0.167 or 0.185 with respect to real bridge tolls for the competing automobile trips. Such route specific application results of this inexpensive approach provide significant implications for policymaking of individual programs in pricing, train operation, budgeting, system changes, etc., as they are in the case reported herein and would be in many other cities.     

Path-differentiated pricing in congestion mitigation

Instead of charging tolls on individual links, this paper considers doing the same on paths. Path and link tolls are “valid” if they encourage motorists to use routes that collectively lead to a target distribution, e.g., one that minimizes travel delay. Because the numbers of valid link and path tolls are typically infinite, an objective in pricing tolls is to find a set of valid tolls that yields the least revenue to lessen the financial burden on motorists.Path tolls are generally more flexible than link tolls and this paper shows that this flexibility can substantially reduce the financial burden on motorists. Additionally, valid path tolls yielding the least revenue possess characteristics with interesting policy implications. To determine these path tolls, it is natural to formulate the problem as a mathematical program with complementarity constraints. However, this paper also investigates alternative formulations that highlight the problem’s complexity and suggest ways to solve the problem efficiently.     

A multi-commodity flow network design problem

There exist systems which can be usefully described by a network containingarcs through which a commodity of one type flows. This paper is concerned with finding a solution procedure for a particular multi-commodity flow network design problem. The problem is to identify a set of arcs in the network such that if travel is prohibited in them all flow travels by feasible paths and its total cost is minimal. The total flow in each arc may not exced its capacity, which is a known constant. Each arc and each node of the network has a non-negative constant unit traversal cost. Between each pair of distinct nodes there is a given non-negative rate of flow from the first vertex to the second which may be split up among a number of paths according to some constant traversal cost flow assignment process. The optimality criterion is the total traversal cost of all flow, which is to be minimized. Previous work on network design problems of this type is surveyed. The principal contribution of this paper is the presentation of a solution procedure for the above problem based on branch and bound enumeration. An illustrative numerical example is included. Computational experience gained in using the procedure with a FORTRAN IV program on an IBM 370 is favourable.     

Liner shipping network design with emission control areas: A genetic algorithm-based approach

To curb emissions, containerized shipping lines face the traditional trade-off between cost and emissions (CO₂ and SO_x) reduction. This paper considers this element in the context of liner service design and proposes a mixed integer linear programming (MILP) model based on a multi-commodity pickup and delivery arc-flow formulation. The objective is to maximize the profit by selecting the ports to be visited, the sequence of port visit, the cargo flows between ports, as well as the number/operating speeds of vessels on each arc of the selected route. The problem also considers that Emission Control Areas (ECAs) exist in the liner network and accounts for the vessel carrying capacity. In addition to using the MILP solver of CPLEX, we develop in the paper a specific genetic algorithm (GA) based heuristic and show that it gives the possibility to reach an optimal solution when solving large size instances.     

Towards marginal cost pricing: A comparison of alternative pricing systems

European urban areas are marred by the problems of congestion and environmental degradation due to the prevailing levels of car use. Strong arguments have thus been put forward in support of a policy based on marginal cost pricing (European Commission 1996). Such policy measures – which would force private consumers to pay for a public service that was previously provided "for free" – are, however, notoriously unpopular with the general public and hence also with their elected representatives – the politicians. There is thus an obvious tension between economic theory, which suggests that marginal cost pricing is the welfare maximising solution to urban transport problems, and practical experience, which suggests that such pricing measures are unwanted by the affected population and hence hard to implement through democratic processes. The AFFORD Project for the European Commission has aimed to investigate this paradox and its possible solutions, through a combination of economic analysis, predictive modelling, attitudinal surveys, and an assessment of fiscal and financial measures within a number of case study cities in Europe. In this paper the methodology and results obtained for the Edinburgh case study are reported in detail. The study analyses alternative road pricing instruments and compares their performance against the theoretical first best situation. It discusses the effect of coverage, location, charging mechanism and interaction with other instruments. The paper shows that limited coverage in one mode may lead to a deviation from the user pays principle in other modes, that location is as important as charge levels and that assumptions about the use of revenues are critical in determining the effect on equity and acceptability. Finally the results show that a relatively simple smart card system can come close to providing the economic first best solution, but that this result should be viewed in the context of the model assumptions.     

Travel mental budgeting under road toll: An investigation based on user equilibrium

With the approach of introducing the conceptions of mental account and mental budgeting into the process of travelers’ route choice, we try to identify why the usages of tolled roads are often overestimated. Assuming that every traveler sets a mental account for his/her travel to keep track of their expense and keep out-of-pocket spending under control, it addresses these questions such that “How much money can I spend on the travel?” and “What if I spend too much?”. Route tolls that exceed the budget are much more unacceptable compared to those within budget due to the non-fungibility of money between different accounts. A simple network with two nodes and two routes is analyzed firstly, the analytical solutions are obtained and the optimal road tolls supporting the user equilibrium as a system optimum are also derived. The proposed model is then extended to a generalized network. The multiclass user equilibrium conditions with travel mental budgeting are formulated into an equivalent variational inequality (VI) problem and an equivalent minimization problem. Through analyses with numerical examples, it is found that the main reason that the usages of high tolled roads are often overestimated is due to the fact that travelers with low and moderate out-of-pocket travel budget perceive a much higher travel cost than their actual cost on the high tolled roads.     

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.     

On the convergence of iterative methods for the distribution balancing problem

A general distribution balancing problem, specified by the given outflows and inflows and the factorial form of its solution, is formulated. Solution uniqueness and boundedness is discussed—primarily in graph theoretical terms. An entropy maximisation problem, subject to general linear constraints, is transformed into an unconstrained optimisation problem by application of standard duality theory, and a relevant general convergence theorem for iterative solution methods is given. The optimum solution in a special case is identified with the flow solution. When expressed in flow variables, the dual objective has a unique and bounded optimum solution and is an appropriate unifying concept for measuring the rate of convergence of different solution methods. By regarding the balancing procedure as an iterative optimisation method, a new and simple proof of its convergence is given, together with some asymptotic results, which are also compared with those of Newton's method. It is pointed out that there are two different forms of Newton's method, according to the choice of variables—untransformed or transformed— in the original distribution balancing problem. When Newton's method is applied to the whole system of equations simultaneously, the trajectory of iterates is observed to depend on this variable choice. For the transformed variables it is noticed that the convergence with the balancing procedure is quicker than with Newton's method applied to the outflow- and inflow- equations, alternately. To guarantee global convergence with Newton's method and to increase the rate a supplementary linear search routine is recommended.     

Solving the Pareto-improving toll problem via manifold suboptimization

Congestion tolls are considered to be Pareto-improving if they reduce travel delay or improve social benefit and ensure that, when compared to the situation without any tolling intervention, no user is worse off in terms of travel cost measured, e.g., in units of time. The problem of finding Pareto-improving tolls can be formulated as a mathematical program with complementarity constraints, a class of optimization problems difficult to solve. Using concepts from manifold suboptimization, we propose a new algorithm that converges to a strongly stationary solution in a finite number of iterations. The algorithm is also applicable to the problem of finding approximate Pareto-improving tolls and can address the cases where demands are either fixed or elastic. Numerical results using networks from the literature are also given.     

Optimal tolls for multi-class traffic: Analytical formulations and policy implications

This paper puts together an analytical formulation to compute optimal tolls for multi-class traffic. The formulation is comprised of two major modules. The first one is an optimization component aimed at computing optimal tolls assuming a Stackelberg game in which the toll agency sets the tolls, and the equilibrating traffic plays the role of the followers. The optimization component is supported by a set of cost models that estimate the externalities as a function of a multivariate vector of traffic flows. These models were estimated using Taylor series expansions of the output obtained from traffic simulations of a hypothetical test case. Of importance to the paper is the total travel time function estimated using this approach that expresses total travel time as a multivariate function of the traffic volumes. The formulation presented in the paper is then applied to a variety of scenarios to gain insight into the optimality of current toll policies. The optimal tolls are computed for two different cases: independent tolls, and tolls proportional to passenger car equivalencies (PCE).The numerical results clearly show that setting tolls proportional to PCEs leads to lower values of welfare that are on average 15% lower than when using independent tolls, though, in some cases the total welfare could be up to 33% lower. This is a consequence of two factors. First, the case of independent tolls has more degrees of freedom than the case of tolls proportional to PCEs. Second, tolls proportional to PCEs do not account for externalities other than congestion, which is likely to lead to lower welfare values.The analytical formulations and numerical results indicate that, because the total travel time is a non-linear function of the traffic volumes, the marginal social costs and thus the optimal congestion tolls also depend on the traffic volumes for each vehicle class. As a result of this, for the relatively low volumes of truck traffic observed in real life, the optimal congestion tolls for trucks could indeed be either lower or about the same as for passenger cars. This stand in sharp contrast with what is implied in the use of PCEs, i.e., that the contribution to congestion are constant. This latter assumption leads to optimal truck congestion tolls that are always proportional to the PCE values.The comparison of the toll ratios (truck tolls divided by passenger car tolls) for both observed and optimal conditions suggests that the tolls for small trucks are about the right level, maybe a slightly lower than optimal. However, the analysis of the toll ratio for large trucks seems to indicate a significant overcharge. The estimates show that the average observed toll ratio for large trucks is even higher than the maximum optimal toll ratio found in the numerical experiments. This suggests that the tolls for large trucks are set on the basis of revenue generation principles while the passenger car tolls are being set based on a mild form of welfare maximization. This leads to a suboptimal cross-subsidization of passenger car traffic in detriment of an important sector of the economy.     

A comparative analysis of US toll policy

In the US, there is a long tradition of toll roads, beginning with the Lancaster Turnpike that was built at the end of the 18th century connecting Philadelphia and Lancaster. There are currently more than 300 toll facilities in the US, which is probably the largest number of toll facilities in the world. These facilities represent a wide range of conditions, from hypercongested facilities in large metropolitan areas such as New York City to toll highways in rural areas. The toll structures are equally diverse, ranging from multi-tier price structures with frequent user, carpool, and time of day discounts; to simpler structures in which the only differentiation is made on the basis of the number of axles per vehicle. The toll rates are typically set by the agencies that operate or own the toll facilities. The rules or formulas by which these tolls are determined are not generally available to the public, though it is safe to say that toll decisions are made taking into account technical considerations, as well as the all important criterion of political acceptability. However, data on toll rates and how they change by vehicle types and by some other attributes are readily available.The overall objective of this paper is to analyze the toll data from various facilities across the US to gain insight into the overall factors affecting the tolls. A more specific objective is to assess—though in a rather approximate fashion—if the tolls by vehicle type, relative to each other, are appropriate and consistent with economic theory. This is achieved by comparing tolls to approximate indicators of road space consumption and pavement deterioration. The literature review confirmed that this is the first time such research has been conducted which is an important first step toward an analysis of the efficiency of current toll policies.The analyses in this paper are based on a random sample of all toll facilities across the US. The toll dataset, which include toll rates for passenger cars, busses, and three different truck types, is assembled mainly from the available information on the web sites of various toll agencies. After cleaning the data, the authors used econometric modeling to estimate a set of ordinary least squares (OLS) regression models that express tolls as functions of independent variables. Three families of models were estimated: linear models, models based on expansions of Taylor series, and models based on piece-wise linear approximations to non-linear effects. The resulting models were analyzed to identify the salient features of current toll policies towards different vehicle types.     

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

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

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

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

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

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

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

Dynamic system‐optimal traffic assignment for a city using the continuum modeling approach

This paper presents a continuum dynamic traffic assignment model for a city in which the total cost of the traffic system is minimized: the travelers in the system are organized to choose the route to their destinations that minimizes the total cost of the system. Combined with the objective function, which defines the total cost and constraints such as certain physical and boundary conditions, a continuum model can be formulated as an optimization scheme with a feasible region in the function space. To obtain an admissible locally optimal solution to this problem, we first reformulate the optimization in discrete form and then introduce a heuristic method to solve it. This method converges rapidly with attractive computational cost. Numerical examples are used to demonstrate the effectiveness of the method. Copyright © 2013 John Wiley & Sons, Ltd.     

A chance-constrained based stochastic dynamic traffic assignment model: Analysis, formulation and solution algorithms

This paper is concerned with the system optimum-dynamic traffic assignment (SO-DTA) problem when the time-dependent demands are random variables with known probability distributions. The model is a stochastic extension of a deterministic linear programming formulation for SO-DTA introduced by Ziliaskopoulos (Ziliaskopoulos, A.K., 2000. A linear programming model for the single destination system optimum dynamic traffic assignment problem, Transportation Science, 34, 1–12). The proposed formulation is chance-constrained based and we demonstrate that it provides a robust SO solution with a user specified level of reliability. The model provides numerous insights and can be a useful tool in producing robust control and management strategies that account for uncertainty in applications where SO-DTA is relevant (e.g. evacuation modeling, computing alternate routes around freeway incidents and establishing lower bounds on network performance).     

Congestion pricing under operational,supply-side uncertainty

This paper is concerned with finding first-best tolls in static transportation networks with day-to-day variation in network capacity, as accounted for by changes in the volume-delay function. The key question in addressing this problem is that of information, namely, which agents have access to what information when making decisions. In this work, travelers are assumed to be either fully informed about network conditions before embarking on travel, or having no information except the probability distributions; likewise, the network manager (toll-setter) is either able to vary tolls in response to realized network conditions, or must apply the same tolls every day. Further, travelers’ preference for reliable travel is accounted for, representing risk aversion in the face of uncertainty. For each of the scenarios implied by combinations of these assumptions, we present methods to determine system-optimal link prices. A demonstration is provided, using the Sioux Falls test network, suggesting that attempts to incorporate uncertainty into nonresponsive tolls involve significantly higher prices.     

Integrating congestion pricing and transit investment planning

This paper develops a mathematical model and solution procedure to identify an optimal zonal pricing scheme for automobile traffic to incentivize the expanded use of transit as a mechanism to stem congestion and the social costs that arise from that congestion. The optimization model assumes that there is a homogenous collection of users whose behavior can be described as utility maximizers and for which their utility function is driven by monetary costs. These monetary costs are assumed to be the tolls in place, the per mile cost to drive, and the value of their time. We assume that there is a system owner who sets the toll prices, collects the proceeds from the tolls, and invests those funds in transit system improvements in the form of headway reductions. This yields a bi-level optimization model which we solve using an iterative procedure that is an integration of a genetic algorithm and the Frank–Wolfe method. The method and solution procedure is applied to an illustrative example.     

Constrained optimization and distributed computation based car following control of a connected and autonomous vehicle platoon

Motivated by the advancement in connected and autonomous vehicle technologies, this paper develops a novel car-following control scheme for a platoon of connected and autonomous vehicles on a straight highway. The platoon is modeled as an interconnected multi-agent dynamical system subject to physical and safety constraints, and it uses the global information structure such that each vehicle shares information with all the other vehicles. A constrained optimization based control scheme is proposed to ensure an entire platoon’s transient traffic smoothness and asymptotic dynamic performance. By exploiting the solution properties of the underlying optimization problem and using primal-dual formulation, this paper develops dual based distributed algorithms to compute optimal solutions with proven convergence. Furthermore, the asymptotic stability of the unconstrained linear closed-loop system is established. These stability analysis results provide a principle to select penalty weights in the underlying optimization problem to achieve the desired closed-loop performance for both the transient and the asymptotic dynamics. Extensive numerical simulations are conducted to validate the efficiency of the proposed algorithms.     

Continuous equilibrium network design models

It is known that the network design problem with the assumption of user optimal flows can be modeled as a 0–1 mixed integer programming problem. Instead, we formulate the network design problem with continuous investment variables subject to equilibrium assignment as a nonlinear optimization problem. We show that this optimization problem is equivalent to an unconstrained problem which we solve by direct search techniques. For convex investment cost functions, the performance of both Powell's method and the method of Hooke and Jeeves is approximately the same with respect to computational requirements for a 24 node, 76 arc network. For the case of concave investment functions, Hooke and Jeeves was superior. The solution to the concave continuous model was very similar to that of the 0–1 model. Furthermore, the required solution time was far less than that required by the corresponding discrete model of the same network. The advantages and disadvantages of the continuous approach as well as the computational requirements are discussed.