An algorithm for solving asymmetric equilibrium problems with a continuous cost-flow function

The paper gives two user objective functions for the asymmetric assignment problem, and an algorithm of descent type. The algorithm produces a sequence of flows which converges to the set of equilibria if the cost-flow function is continuous.     

A network equilibrium approach for modelling activity-travel pattern scheduling problems in multi-modal transit networks with uncertainty

An understanding of the interaction between individuals’ activities and travel choice behaviour plays an important role in long-term transit service planning. In this paper, an activity-based network equilibrium model for scheduling daily activity-travel patterns (DATPs) in multi-modal transit networks under uncertainty is presented. In the proposed model, the DATP choice problem is transformed into a static traffic assignment problem by constructing a new super-network platform. With the use of the new super-network platform, individuals’ activity and travel choices such as time and space coordination, activity location, activity sequence and duration, and route/mode choices, can be simultaneously considered. In order to capture the stochastic characteristics of different activities, activity utilities are assumed in this study to be time-dependent and stochastic in relation to the activity types. A concept of DATP budget utility is proposed for modelling the uncertainty of activity utility. An efficient solution algorithm without prior enumeration of DATPs is developed for solving the DATP scheduling problem in multi-modal transit networks. Numerical examples are used to illustrate the application of the proposed model and the solution algorithm.     

Approximate algorithms for the discrete network design problem

The discrete network design problem is one of finding a set of feasible actions (projects) from among a collection of possible actions, that when implemented, optimizes some objective function(s). This is a combinatorial optimization problem that is very expensive to solve exactly. This paper proposes two algorithms for obtaining approximate solutions to the discrete network design problem with much less computational effeort. The computational savings are achieved by approximating the original problem with a new formulation which is easier to solve. The first algorithm proposed solves this approximate problem exactly, while the second is even more efficient, but provides only a near-optimal solution to the approximate problem. Experience with test problems indicates that these approximations can reduce the computational effort by a factor of 3–5, with little loss in solution accuracy.     

The stability of stochastic equilibrium in a two-link transportation network

Most research and applications of network equilibrium models are based on the assumption that traffic volumes on roadways are virtually certain to be at or near their equilibrium values if the equilibrium volumes exist and are unique. However, it has long been known that this assumption can be violated in deterministic models. This paper presents an investigation of the stability of stochastic equilibrium in a two-link network. The stability of deterministic equilibrium also is discussed briefly. Equilibrium is defined to be stable if it is unique and the link volumes converge over time to their equilibrium values regardless of the initial conditions. Three models of route choice decision-making over time are formulated, and the stability of equilibrium is investigated for each. It is shown that even when equilibrium is unique, link volumes may converge to their equilibrium values, oscillate about equilibrium perpetually, or converge to values that may be considerably different from the equilibrium ones, depending on the details of the route choice decision-making process. Moreover, even when convergence of link volumes to equilibrium is assured, the convergence may be too slow to justify the standard assumption that these volumes are usually at or near their equilibrium values. When link volumes converge to non-equilibrium values, the levels at which the volumes stabilize typically depend on the initial link volumes or perceptions of travel costs. Conditions sufficient to assure convergence to equilibrium in two of the three models of route choice decision-making are presented, and these conditions are interpreted in terms of the route choice decision-making process.     

Evaluation of network reliability using stochastic user equilibrium

When we evaluate the performance reliability of a network, it is necessary to describe user's behaviour in a partially degraded network. This paper shows that the Stochastic User Equilibrium (SUE) model assuming user's route choice behaviour under uncertain network conditions can be incorporated in the performance reliability model. The effects of providing information are analyzed using the SUE model with two different groups of route choice; informed drivers and non informed drivers. It is found that providing information generally increases network performance reliability. This depends, however, on the probability distribution of the network states.     

The structure of the solution set to network optimisation problems

This paper argues that both heuristic and non-heuristic algorithms for the road network optimisation problem would benefit from a greater understanding of the structure of the set of feasible solutions to such problems. In order to provide this, a comparative study of a number of spatial combinatorial problems was undertaken. The results show that the road network optimisation problem is rich in good sub-optimal solutions. The implications of this finding for the development of optimising and heuristic algorithms are discussed, and some suggestions made as to where future research on network optimisation problems could most fruitfully be directed.     

Heuristic ranking and selection procedures for network design problems

Two heuristic approaches to solving discrete non-linear network design problems and other subset selection problems are described and tested. These heuristics operate similarly to other add, delete and interchange heuristics that have been applied to network design problems. However, the selection criterion adopted here is the ratio of objective function change per unit of resource cost, which other authors have described as an effective gradient measure for zero-one integer programming problems. Optimal branch-and-bound algorithms previously developed and tested are reviewed, and those results serve as benchmarks with which to compare these heuristics described in this paper. The first heuristic ranks and deletes alternative network modifications from an entire set of candidate projects, such as new links or link improvements, until the subset of remaining projects fits within the constraint space. This method was found to achieve optimal or near-optimal solutions to each of the test cases, even when the number of candidate projects deleted in each iteration was increased from one to many. The quality of those results led us to investigate a constrained random sampling procedure in which candidate projects are ranked with regard to randomly generated networks, and a solution is then chosen on the basis of these rankings. This second approach was found to achieve solutions that were almost as good as those obtained with the rank and delete heuristic.     

On the convergence of the algorithm for bilevel programming problems by Clegg and Smith

In Clegg and Smith [Transportation Research B 35 (2001) 71–82] and Battye et al. [in: M. Patriksson, M. Labbe (Eds.), Transportation Planning – State of the Art, Proceedings of the 6th Meeting of the EURO Working Group on Transportation, Gothenburg, Sweden, September 9–11, 1998, Kluwer Academic Publishers, Dordrecht], Smith and colleagues present an algorithm for solving the bilevel programming problem. We show that the points reached by the algorithm are not stationary points of bilevel programs in general. We further show that, with a minor modification, this method can be expressed as an inexact penalty method for gap function-constrained bilevel programs.     

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.     

Dynamic network equilibrium for daily activity-trip chains of heterogeneous travelers: application to large-scale networks

Applications of dynamic network equilibrium models have, mostly, considered the unit of traffic demand either as one-way trip, or as multiple independent trips. However, individuals’ travel patterns typically follow a sequence of trips chained together. In this study we aim at developing a general simulation-based dynamic network equilibrium algorithm for assignment of activity-trip chain demand. The trip chain of each individual trip maker is defined by the departure time at origin, sequence of activity destination locations, including the location of their intermediate destinations and their final destination, and activity duration at each of the intermediate destinations. Spatial and temporal dependency of subsequent trips on each other necessitate time and memory consuming calculations and storage of node-to-node time-dependent least generalized cost path trees, which is not practical for very large metropolitan area networks. We first propose a reformulation of the trip-based demand gap function formulation for the variational inequality formulation of the Bi-criterion Dynamic User Equilibrium (BDUE) problem. Next, we propose a solution algorithm for solving the BDUE problem with daily chain of activity-trips. Implementation of the algorithm for very large networks circumvents the need to store memory-intensive node-to-node time-dependent shortest path trees by implementing a destination-based time-dependent least generalized cost path finding algorithm, while maintaining the spatial and temporal dependency of subsequent trips. Numerical results for a real-world large scale network suggest that recognizing the dependency of multiple trips of a chain, and maintaining the departure time consistency of subsequent trips provide sharper drops in gap values, hence, the convergence could be achieved faster (compared to when trips are considered independent of each other).     

Modeling intermodal equilibrium for bimodal transportation system design problems in a linear monocentric city

This paper investigates the intermodal equilibrium, road toll pricing, and bus system design issues in a congested highway corridor with two alternative modes - auto and bus - which share the same roadway along this corridor. On the basis of an in-depth analysis of the demand and supply sides of the bimodal transportation system, the mode choice equilibrium of travelers along the continuum corridor is first presented and formulated as an equivalent variational inequality problem. The solution properties of the bimodal continuum equilibrium formulation are analytically explored. Two models, which account for different infrastructure/system regulatory regimes (public and private), are then proposed. In the public regulatory model, the road toll location and charge level are simultaneously optimized together with the bus service fare and frequency. In the private regulatory model, the fare and frequency of bus services, which are operated by a profit-driven private operator, are optimized for exogenously given toll pricing schemes. Finally, an illustrative example is given to demonstrate the application of the proposed models. Sensitivity analysis of residential/household distribution along the corridor is carried out together with a comparison of four different toll pricing schemes (no toll, first best, distance based, and location based). Insightful findings are reported on the interrelationships among modal competition, market regulatory regimes, toll pricing schemes, and urban configurations as well as their implications in practice.     

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.     

Joint optimization of freight facility location and pavement infrastructure rehabilitation under network traffic equilibrium

Establishment of industry facilities often induces heavy vehicle traffic that exacerbates congestion and pavement deterioration in the neighboring highway network. While planning facility locations and land use developments, it is important to take into account the routing of freight vehicles, the impact on public traffic, as well as the planning of pavement rehabilitation. This paper presents an integrated facility location model that simultaneously considers traffic routing under congestion and pavement rehabilitation under deterioration. The objective is to minimize the total cost due to facility investment, transportation cost including traffic delay, and pavement life-cycle costs. Building upon analytical results on optimal pavement rehabilitation, the problem is formulated into a bi-level mixed-integer non-linear program (MINLP), with facility location, freight shipment routing and pavement rehabilitation decisions in the upper level and traffic equilibrium in the lower level. This problem is then reformulated into an equivalent single-level MINLP based on Karush–Kuhn–Tucker (KKT) conditions and approximation by piece-wise linear functions. Numerical experiments on hypothetical and empirical network examples are conducted to show performance of the proposed algorithm and to draw managerial insights.     

The use of equilibrium network models in logistics management: With application to the U.S. coal industry

This paper discusses the use in logistics management of the freight network equilibrium model, developed in Harker and Friesz (1985a, b), called the Generalized Spatial Price Equilibrium Model, or GSPEM. After this discussion, computational techniques for solving this model are presented. The application of GSPEM to the analysis of the U.S. coal economy is then presented and future extensions of this line of research are discussed.     

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.     

The design of electric vehicle charging network

The promotion of Electric Vehicles (EVs) has become a key measure of the governments in their attempt to reduce greenhouse gas emissions. However, range anxiety is a big barrier for drivers to choose EVs over traditional vehicles. Installing more charging stations in appropriate locations can relieve EV drivers’ range anxiety. To determine the locations of public charging stations, we propose two optimization models for two different charging modes - fast and slow charging, which aim at minimizing the total cost while satisfying certain coverage goal. Instead of using discrete points, we use geometric objects to represent charging demands. Importantly, to resolve the partial coverage problem (PCP) for networks, we extend the polygon overlay method to split the demands on the road network. After applying the models to Greater Toronto and Hamilton Area (GTHA) and to Downtown Toronto, we show that the proposed models are practical and effective in determining the locations of charging stations. Moreover, they can eliminate PCP and provide much more accurate results than the complementary partial coverage method (CP).     

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.