A simplicial decomposition algorithm for solving the variational inequality formulation of the general traffic assignment problem for large scale networks

Summary The class of simplicial decomposition methods has been shown to constitute efficient tools for the solution of the variational inequality formulation of the general traffic assignment problem. This paper presents a particular implementation of such an algorithm, with emphasis on its ability to solve large scale problems efficiently. The convergence of the algorithm is monitored by the primal gap function, which arises naturally in simplicial decomposition schemes. The gap function also serves as an instrument for maintaining a reasonable subproblem size, through its use in column dropping criteria. The small dimension and special structure of the subproblems also allows for the use of very efficient algorithms; several algorithms in the class of linearization methods are presented. When restricting the number of retained extremal flows in a simplicial decomposition scheme, the number of major iterations tends to increase. For large networks the shortest path calculations, leading to new extremal flow generation, require a large amount of the total computation time. A special study is therefore made in order to choose the most efficient extremal flow generation technique. Computational results on symmetric problems are presented for networks of some large cities, and on asymmetric problems for some of the networks used in the literature. Computational results for bimodal models of some large cities leading to asymmetric problems are also discussed.     

An anisotropic continuum model for traffic assignment in mixed transportation networks

This work deals with a two-dimensional continuum model for the problem of congested traffic assignment in an urban transportation system consisting of a set of freeways superimposed over a dense street network. The formulation leads to a system of non-linear differential equations whose unknowns are given by the travel times from arbitrary points of the network to the corresponding destinations. The governing equations are appropriately solved by means of the Finite Element Method. Then, traffic flow on every link of the network can be obtained. Numerical examples are given in order to demonstrate the efficiency of the developed model.     

An in-core/out-of-core method for solving large scale assignment problems

We describe how the shortest augmenting path method can be used as basis for a so called in-core/out-of-core approach for solving large assignment problems in which the data cannot be kept in central memory of a computer. Here we start by solving the assignment problem on a sparse subgraph and then we introduce the remaining edges in an outpricing/reoptimization phase. We introduce several strategies which enable to keep the working subgraph sparse throughout the procedure and even lead to an all in-core code which is faster than the basic shortest augmenting path code.

---

Zusammenfassung Wir beschreiben einen sogenannten In-Core/Out-of-Core Ansatz auf der Basis der kürzesten erweiternden Wege Methode für die Lösung gro\er Zuordnungsprobleme, für die die gesamte Kostenmatrix nicht im Zentralspeicher des Rechners gehalten werden kann. Bei diesem Ansatz wird in einer ersten Phase ein Zuordnungsproblem über einem dünnen Teilgraph optimal gelöst. In einer zweiten Phase werden dann die nicht berücksichtigen Kanten mittels der optimalen Duallösung bewertet (outpricing) und gegebenenfalls eine Reoptimierung durchgeführt. Durch Anwendung spezieller Strategien wird es möglich, während der gesamten Lösung den im Zentralspeicher abzuspeichernden Teilgraphen dünn zu halten. Weiterhin zeigt sich, da\ dieser Ansatz zu einem neuen Verfahren führt, das der zugrunde liegenden kürzesten erweiternden Wege Methode überlegen ist.

     

Parallel optimization for traffic assignment

Most large-scale optimization problems exhibit structures that allow the possibility of attack via algorithms that exhibit a high level of parallelism. The emphasis of this paper is the development of parallel optimization algorithms for a class of convex, block-structured problems. Computational experience is cited for some large-scale problems arising from traffic assignment applications. The algorithms considered here have the property that they allow such problems to be decomposed into a set of smaller optimization problems at each major iteration. These smaller problems correspond to linear single-commodity networks in the traffic assignment case, and they may be solved in parallel. Results are given for the distributed solution of such problems on the CRYSTAL multicomputer.This research was supported in part by NSF grant CCR-8709952 and AFOSR grant AFOSR-86-0194.     

System optimal and user equilibrium time-dependent traffic assignment in congested networks

This paper formulates two dynamic network traffic assignment models in which O-D desires for the planning horizon are assumed known a priori: the system optimal (SO) and the user equilibrium (UE) time-dependent traffic assignment formulations. Solution algorithms developed and implemented for these models incorporate a traffic simulation model within an overall iterative search framework. Experiments conducted on a test network provide the basis for a comparative analysis of system performance under the SO and UE models.     

Postoptimizing equilibrium flows on large scale networks

In a large variety of applications, equilibrium traffic flows corresponding to a set of slightly modified input data must be computed sequentially. Until now, it is believed that only a disaggregate decomposition approach, that works explicitly on the path flow space, offers the postoptimization capability. This note proposes a new postoptimization method to deal with perturbations of the traffic demand input that does not require path information. Numerical experiments on practical size networks show a drastic reduction in the number of iterations with respect to the naive restart approach.     

Desynchronization of large scale delayed neural networks

We consider a ring of identical neurons with delayed nearest neighborhood inhibitory interaction. Under general conditions, such a network has a slowly oscillatory synchronous periodic solution which is completely characterized by a scalar delay differential equation with negative feedback. Despite the fact that the slowly oscillatory periodic solution of the scalar equation is stable, we show that the associated synchronous solution is unstable if the size of the network is large.

     

Finding optimal hyperpaths in large transit networks with realistic headway distributions

This paper implements and tests a label-setting algorithm for finding optimal hyperpaths in large transit networks with realistic headway distributions. It has been commonly assumed in the literature that headway is exponentially distributed. To validate this assumption, the empirical headway data archived by Chicago Transit Agency are fitted into various probabilistic distributions. The results suggest that the headway data fit much better with Loglogistic, Gamma and Erlang distributions than with the exponential distribution. Accordingly, we propose to model headway using the Erlang distribution in the proposed algorithm, because it best balances realism and tractability. When headway is not exponentially distributed, finding optimal hyperpaths may require enumerating all possible line combinations at each transfer stop, which is tractable only for a small number of alternative lines. To overcome this difficulty, a greedy method is implemented as a heuristic and compared to the brute-force enumeration method. The proposed algorithm is tested on a large scale CTA bus network that has over 10,000 stops. The results show that (1) the assumption of exponentially distributed headway may lead to sub-optimal route choices and (2) the heuristic greedy method provides near optimal solutions in all tested cases.     

Routing and capacity assignment in backbone communication networks under time varying traffic conditions

This paper studies the problem of assigning capacities to links in a backbone communication network and determining the routes used by messages for all communicating node pairs in the network under time varying traffic conditions. The best routes are to be chosen from among all possible routes in the network. Tradeoffs between link costs and response time to users are achieved by specifying an upper limit on the average link queueing delay in the network. The goal is to minimize total link fixed and variable costs. The topology of the network and the end-to-end traffic requirements during the different busy-hours are assumed to be known. The problem is formulated as a mathematical programming model. An efficient solution procedure based on a Lagrangian relaxation of the problem is developed. The results of extensive computational experiments across a variety of networks are reported. These results indicate that the solution procedure is effective for a wide range of traffic loads and cost structures.     

Heavy traffic approximations of large deviations of feedforward queueing networks

We consider a multi-class feedforward queueing network with first come first serve queueing discipline and deterministic services and routing. The large deviation asymptotics of tail probabilities of the distribution of the workload vector can be characterized by convex path space minimization problems with non-linear constraints. So far there exists no numerical algorithm which could solve such minimization problems in a general way. When the queueing network is heavily loaded it can be approximated by a reflected Brownian motion. The large deviation asymptotics of tail probabilities of the distribution of this heavy traffic limit can again be characterized by convex path space minimization problems with non-linear constraints. However, due to their less complicated structure there exist algorithms to solve such minimization problems. In this paper we show that, as the network tends to a heavy traffic limit, the solution of the large deviation minimization problems of the network approaches the solution of the corresponding minimization problems of a reflected Brownian motion. Stated otherwise, we show that large deviation and heavy traffic asymptotics can be interchanged. We prove this result in the case when the network is initially empty. Without proof we state the corresponding result in the stationary case. We present an illuminating example with two queues. This revised version was published online in June 2006 with corrections to the Cover Date.     

Capacitated transit assignment with loading priorities

In a transit network involving vehicles with rigid capacities, we advocate the use of strategies for describing consumer behavior. At each boarding node, a user sorts the transit lines in decreasing order of preference, and boards the first vehicle in this list whose residual capacity is nonzero. Since a users position in the queue varies from day to day, the delay experienced is stochastic. This leads to an equilibrium problem where, at a solution, users are assigned to strategies that minimize their expected delay. This situation is formulated as a variational inequality, whose cost mapping is discontinuous and strongly asymmetric, due to the priority of current passengers over incoming users. We prove that the solution set is nonempty and provide numerical results obtained by an efficient solution algorithm.This research was supported in part by the Natural Sciences and Engineering Research Council of Canada (NSERC) and by the Fonds pour la formation de chercheurs et laide à la recherche (FCAR).Mathematics Subject Classification (2000):20E28, 20G40, 20C20Accepted: December 20, 2003     

A framework for user equilibrium dynamic traffic assignment

Several analytic approaches have been developed to describe or predict traffic flows on networks with time-varying (dynamic) travel demands, flows and travel times. A key component of these models lies in modelling the flows and/or travel times on the individual links, but as this is made more realistic or accurate it tends to make the overall model less computationally tractable. To help overcome this, and for other reasons, we develop a bi-level user equilibrium (UE) framework that separates the assignment or loading of flows on the time–space network from the modelling of flows and trip times within individual links. We show that this model or framework satisfies appropriate definitions of UE satisfies a first-in-first-out (FIFO) property of road traffic, and has other desirable properties. The model can be solved by iterating between (a) a linear network-loading model that takes the lengths of time–space links as fixed (within narrow ranges), and (b) a set of link flow sub-models which update the link trip times to construct a new time–space network. This allows links to be processed sequentially or in parallel and avoids having to enumerate paths and compute path flows or travel times. We test and demonstrate the model and algorithms using example networks and find that the algorithm converges quickly and the solutions behave as expected. We show how to extend the model to handle elastic demands, multiple destinations and multiple traffic types, and traffic spillback within links and from link to link.     

A simplicial decomposition method for the transit equilibrium assignment problem

A transit equilibrium assignment problem assigns the passenger flows on to a congested transit (public transportation) network with asymmetric cost functions and a fixed origin-destination matrix. This problem which may be formulated in the space of hyperpath flows, is transformed into an equivalent problem in the space of total arc flows and an auxiliary variable. A simplicial decomposition algorithm is developed and its convergence is proved under the usual assumptions on the cost functions. The algorithm requires relatively little memory and its efficiency is demonstrated with computational results.     

Equitable transit charges for multiadministration telecommunications networks

We study a multi-administration telecommunications network that is an abstraction of an international network. The nodes represent separate telecommunications administrations that are linked such that alternately-routed calls go through one tandem administration. The cost of the group of circuits between a pair of administrations is borne by them; and when a call between the pair is alternately routed through the tandem node, then the two administrations share the call revenue and pay transit fees to the tandem administration. The numbers of circuits between the administrations are selected to yield a least-cost network that provides a desired level of service, in terms of blocking probabilities, over an entire day. We address the problem of determining transit charges for the alternately-routed calls that are equitable for all of the administrations. Our approach is to derive such charges by equating the system-optimal circuit group sizes to certain hypothetical administration-optimal circuit group sizes. This approach may be of use in other system design problems involving cost sharing among several companies.This research was supported in part by Grant AFOSR 84-0367.     

An equilibrium model for urban transit assignment based on game theory

The urban public transport system is portrayed as a special commodity market where passenger is consumer, transit operator is producer and the special goods is the service for passenger’s trip. The generalized Nash equilibrium game is applied to describe how passengers adjust their route choices and trip modes. We present a market equilibrium model for urban public transport system as a series of mathematical programmings and equations, which is to describe both the competitions among different transit operators and the interactive influences among passengers. The proposed model can simultaneously predict how passengers choose their optimal routes and trip modes. An algorithm is designed to obtain the equilibrium solution. Finally, a simple numerical example is given and some conclusions are drawn.     

Throughput-oriented channel assignment for opportunistic spectrum access networks

Cognitive radio (CR) is a revolutionary technology in wireless communications that enhances spectrum utilization by allowing opportunistic and dynamic spectrum access. One of the key challenges in this domain is how CR users cooperate to dynamically access the available spectrum opportunities in order to maximize the overall perceived throughput. In this paper, we consider the coordinated spectrum access problem in a multi-user single-transceiver CR network (CRN), where each CR user is equipped with only one half-duplex transceiver. We first formulate the dynamic spectrum access as a rate/power control and channel assignment optimization problem. Our objective is to maximize the sum-rate achieved by all contending CR users over all available spectrum opportunities under interference and hardware constraints. We first show that this problem can be formulated as a mixed integer nonlinear programming (MINLP) problem that is NP-hard, in general. By exploiting the fact that actual communication systems have a finite number of available channels, each with a given maximum transmission power, we transfer this MINLP into a binary linear programming problem (BLP). Due to its integrality nature, this BLP is expected to be NP-hard. However, we show that its constraint matrix satisfies the total unimodularity property, and hence our problem can be optimally solved in polynomial time using linear programming (LP). To execute the optimal assignment in a distributed manner, we then present a distributed CSMA/CA-based random access mechanism for CRNs. We compare the performance of our proposed mechanism with reference CSMA/CA channel access mechanisms designed for CRNs. Simulation results show that our proposed mechanism significantly improves the overall network throughput and preserves fairness.     

Equilibrium of prestressed networks

A general theory for small displacements superposed on finitedeformations of elastic networks is presented. The network isregarded as a surface formed by two continuously distributedfamilies of elastic fibres. The second variation of the potentialenergy is considered in detail and the Legendre-Hadamard inequalityassociated with a weak minimizer of the energy is examined.The theory is then specialized to the case of orthogonal fibresand applied to the solution of some simple problems.     

Optimization of transit route network,vehicle headways and timetables for large-scale transit networks

This paper presents a metaheuristic method for optimizing transit networks, including route network design, vehicle headway, and timetable assignment. Given information on transit demand, the street network of the transit service area, and total fleet size, the goal is to identify a transit network that minimizes a passenger cost function. Transit network optimization is a complex combinatorial problem due to huge search spaces of route network, vehicle headways, and timetables. The methodology described in this paper includes a representation of transit network variable search spaces (route network, headway, and timetable); a user cost function based on passenger random arrival times, route network, vehicle headways, and timetables; and a metaheuristic search scheme that combines simulated annealing, tabu, and greedy search methods. This methodology has been tested with problems reported in the existing literature, and applied to a large-scale realistic network optimization problem. The results show that the methodology is capable of producing improved solutions to large-scale transit network design problems in reasonable amounts of time and computing resources.     

Towards auction algorithms for large dense assignment problems

In this paper, we focus on the problem of solving large-scale instances of the linear sum assignment problem by auction algorithms. We introduce a modified auction algorithm, called look-back auction algorithm, which extends the forward auction algorithm by the ability of reusing information from previous bids. We show that it is able to reuse information from the previous bids with high efficiency for all tested types of input instances. We discuss then the design and implementation of a suite of sequential and distributed memory auction algorithms on a Linux cluster with the evaluation on several types of input instances of the linear sum assignment problem. Our results show that the look-back auction algorithm solves sequentially nearly all types of dense instances faster than other evaluated algorithms and it is more stable than the forward-reverse auction algorithm for sparse instances. Our distributed memory auction algorithms are fully memory scalable. This research has been supported by IGA CTU under grant CTU0308013 and under research program MSMT 6840770014.     

Passenger flow control strategies for urban rail transit networks

Urban rail traffic congestion is becoming increasingly serious due to the large traffic demands in modern cities. In order to ensure the safety and quality of station services in peak hours, it's necessary to adopt some reasonable and effective passenger flow control strategies. In this study, through considering the time-dependent passenger demands, a passenger flow control model based on the network-level system is explicitly developed. The passenger successive motion process is discretized by the modeling method. Systematically considering the coordinated relationship between traffic demands and strict capacity constraints (including station passing capacity, platform load capacity and train transport capacity), we establish a mixed integer linear programming model to minimize the total passenger waiting time (including passengers outside stations and on the platforms). The optimization software Cplex is adopted to solve the developed model, and a real network of Beijing urban railway is calibrated to verify the effectiveness of the suggested model. As a result, the proposed flow control strategies can provide detailed information about control stations, control durations and control intensities, and can effectively reduce the total waiting time and relieve the number of stranded passengers in the urban rail transit network.