An efficient algorithm for computing traffic equilibria using TRANSYT model

Computing traffic equilibria with signal settings using TRANSYT model for an area traffic control road system is considered in this paper. Following Wardrop’s first principle, this problem can be formulated as a variational inequality problem. In this paper, we propose a novel algorithm to efficiently solve this equilibrium traffic assignment with global convergence. Numerical calculations are conducted on a grid-size road network. As it shows, the proposed method achieved greater savings in computational overheads than did those conventional methods for solving traffic equilibria when signal settings are particularly taken into account.     

A novel algorithm for area traffic capacity control with elastic travel demands

A non-linear area traffic control system with limited capacity is considered in this paper. Optimal signal settings and link capacity expansions can be determined while trip distribution and network flow are in equilibrium. This problem can be formulated as a non-linear mathematical program with equilibrium constraints. For the objective function a non-linear constrained optimization program for signal settings and link capacity expansion is determined. For the constraint set the elastic user equilibrium traffic assignment obeying Wardrop’s first principle can be formulated as a variational inequality. Since the constrained optimization problem is non-convex, only local optima can be obtained. In this paper, a novel algorithm using a non-smooth trust region approach is proposed. Numerical tests are performed using a real data city network and various example test networks in which the effectiveness and robustness of the proposed method are confirmed as compared to other well-known solution methods.     

Reserve capacity of signal-controlled road network

For a signal control road network subject to equilibrium flows, the maximum possible increase in travel demands is considered in this paper. Using the concept of reserve capacity of signal-controlled junctions, the problem of finding the maximum increase in traffic demands can be formulated as a mathematical program with equilibrium constraints (MPEC). In this paper, we present a projected gradient approach to obtain the maximum increase in travel demands based on the TRANSYT traffic model. Numerical computations are made on a grid network where good results are obtained.     

A hybrid approach for optimal design of signalized road network

For a signalized road network with expansions of link capacity, the maximum possible increase in travel demands is considered while total delays for travelers are minimized. Using the concept of reserve capacity of signal-controlled junctions, the problem of finding the maximum possible increase in travel demand and determining optimal link capacity expansions can be formulated as optimization programs. In this paper, we present a new solution approach for simultaneously solving the maximum increase in travel demands and minimizing total delays of travelers. A projected Quasi-Newton method is proposed to effectively solve this problem to the KKT points. Numerical computations and comparisons are made on real data signal-controlled networks where obtained results outperform traditional methods.     

An exact penalty function algorithm for optimal control problems with control and terminal equality constraints,part 1

The presence of control constraints, because they are nondifferentiable in the space of control functions, makes it difficult to cope with terminal equality constraints in optimal control problems. Gradient-projection algorithms, for example, cannot be employed easily. These difficulties are overcome in this paper by employing an exact penalty function to handle the cost and terminal equality constraints and using the control constraints to define the space of permissible search directions in the search-direction subalgorithm. The search-direction subalgorithm is, therefore, more complex than the usual linear program employed in feasible-directions algorithms. The subalgorithm approximately solves a convex optimal control problem to determine the search direction; in the implementable version of the algorithm, the accuracy of the approximation is automatically increased to ensure convergence.This work was supported by the United Kingdom Science Research Council, by the US Army Research Office, Contract No. DAAG-29-73-C-0025, and by the National Science Foundation, Grant No. ENG-73-08214-A01.     

An exact penalty function algorithm for optimal control problems with control and terminal equality constraints,part 2

In Part 1 of this paper, implementable and conceptual versions of an algorithm for optimal control problems with control constraints and terminal equality constraints were presented. It was shown that anyL accumulation points of control sequences generated by the algorithms satisfy necessary conditions of optimality. Since such accumulation points need not exist, it is shown in this paper that control sequences generated by the algorithms always have accumulation points in the sense of control measure, and these accumulation points satisfy optimality conditions for the corresponding relaxed control problem.This work was supported by the United Kingdom Science Research Council, by the US Army Research Office, Contract No. DAA-29-73-C-0025, and by the National Science Foundation, Grant No. ENG-73-08214-A01.     

Sequential gradient-restoration algorithm for optimal control problems with general boundary conditions

This paper considers the numerical solution of two classes of optimal control problems, called Problem P1 and Problem P2 for easy identification.Problem P1 involves a functionalI subject to differential constraints and general boundary conditions. It consists of finding the statex(t), the controlu(t), and the parameter so that the functionalI is minimized, while the constraints and the boundary conditions are satisfied to a predetermined accuracy. Problem P2 extends Problem P1 to include nondifferential constraints to be satisfied everywhere along the interval of integration. Algorithms are developed for both Problem P1 and Problem P2.The approach taken is a sequence of two-phase cycles, composed of a gradient phase and a restoration phase. The gradient phase involves one iteration and is designed to decrease the value of the functional, while the constraints are satisfied to first order. The restoration phase involves one or more iterations and is designed to force constraint satisfaction to a predetermined accuracy, while the norm squared of the variations of the control, the parameter, and the missing components of the initial state is minimized.The principal property of both algorithms is that they produce a sequence of feasible suboptimal solutions: the functions obtained at the end of each cycle satisfy the constraints to a predetermined accuracy. Therefore, the values of the functionalI corresponding to any two elements of the sequence are comparable.The stepsize of the gradient phase is determined by a one-dimensional search on the augmented functionalJ, while the stepsize of the restoration phase is obtained by a one-dimensional search on the constraint errorP. The gradient stepsize and the restoration stepsize are chosen so that the restoration phase preserves the descent property of the gradient phase. Therefore, the value of the functionalI at the end of any complete gradient-restoration cycle is smaller than the value of the same functional at the beginning of that cycle.The algorithms presented here differ from those of Refs. 1 and 2, in that it is not required that the state vector be given at the initial point. Instead, the initial conditions can be absolutely general. In analogy with Refs. 1 and 2, the present algorithms are capable of handling general final conditions; therefore, they are suited for the solution of optimal control problems with general boundary conditions. Their importance lies in the fact that many optimal control problems involve initial conditions of the type considered here.Six numerical examples are presented in order to illustrate the performance of the algorithms associated with Problem P1 and Problem P2. The numerical results show the feasibility as well as the convergence characteristics of these algorithms.This research was supported by the Office of Scientific Research, Office of Aerospace Research, United States Air Force, Grant No. AF-AFOSR-76-3075. Partial support for S. Gonzalez was provided by CONACYT, Consejo Nacional de Ciencia y Tecnologia, Mexico City, Mexico.     

Computational algorithm for a distributed optimal control problem of parabolic type with terminal inequality constraints

A computational algorithm for optimal control problems with control and terminal inequality constraints involving first boundary-value problems of parabolic type is presented. The convergence properties are also studied.This work, which was partly supported by the Australian Research Grants Committee, was done during the period when Z. S. Wu was an Honorary Visiting Fellow in the School of Mathematics at the University of New South Wales, Australia.     

Computational algorithm for a distributed optimal control problem of parabolic type with terminal inequality constraints

A corrigendum to Ref. 1 is given.     

Dynamic programming—neural network real-time traffic adaptive signal control algorithm

In this paper, an “intelligent” isolated intersection control system was developed. The developed “intelligent” system makes “real time” decisions as to whether to extend (and how much) current green time. The model developed is based on the combination of the dynamic programming and neural networks. Many tests show that the outcome (the extension of the green time) of the proposed neural network is nearly equal to the best solution. Practically negligible CPU times were achieved, and were thus absolutely acceptable for the “real time” application of the developed algorithm.     

An efficient genetic algorithm for the traveling salesman problem with precedence constraints

The traveling salesman problem with precedence constraints (TSPPC) is one of the most difficult combinatorial optimization problems. In this paper, an efficient genetic algorithm (GA) to solve the TSPPC is presented. The key concept of the proposed GA is a topological sort (TS), which is defined as an ordering of vertices in a directed graph. Also, a new crossover operation is developed for the proposed GA. The results of numerical experiments show that the proposed GA produces an optimal solution and shows superior performance compared to the traditional algorithms.     

A path-based double projection method for solving the asymmetric traffic network equilibrium problem

In this paper we propose a new iterative method for solving the asymmetric traffic equilibrium problem when formulated as a variational inequality whose variables are the path flows. The path formulation leads to a decomposable structure of the constraints set and allows us to obtain highly accurate solutions. The proposed method is a column generation scheme based on a variant of the Khobotov’s extragradient method for solving variational inequalities. Computational experiments have been carried out on several networks of a medium-large scale. The results obtained are promising and show the applicability of the method for solving large-scale equilibrium problems. This work has been supported by the National Research Program FIRB/RBNE01WBBBB on Large Scale Nonlinear Optimization.     

Convergence of a feasible directions algorithm for a distributed optimal control problem of parabolic type with terminal inequality constraints

In this paper, we consider a class of optimal control problems with control and terminal inequality constraints, where the system dynamics is governed by a linear second-order parabolic partial differential equation with first boundary condition. A feasible direction algorithm for solving this class of optimal control problems has already been obtained in the literature. The aim of this paper is to improve the convergence result by using a topology arising in the study of relaxed controls.     

An Ant Colony Optimisation algorithm for solving the asymmetric traffic assignment problem

In this paper we propose an Ant Colony Optimisation (ACO) algorithm for defining the signal settings on urban networks following a local approach. This consists in optimising the signal settings of each intersection of an urban network as a function only of traffic flows at the accesses to the same intersection, taking account of the effects of signal settings on costs and on user route choices. This problem, also known as Local Optimisation of Signal Settings (LOSS), has been widely studied in the literature and can be formulated as an asymmetric assignment problem. The proposed ACO algorithm is based on two kinds of behaviour of artificial ants which allow the LOSS problem to be solved: traditional behaviour based on the response to pheromones for simulating user route choice, and innovative behaviour based on the pressure of an ant stream for solving the signal setting definition problem. Our results on real-scale networks show that the proposed approach allows the solution to be obtained in less time but with the same accuracy as in traditional MSA (Method of Successive Averages) approaches.     

Modified quasilinearization algorithm for optimal control problems with nondifferential constraints and general boundary conditions

This paper considers the numerical solution of the problem of minimizing a functionalI, subject to differential constraints, nondifferential constraints, and general boundary conditions. It consists of finding the statex(t), the controlu(t), and the parameter so that the functionalI is minimized while the constraints are satisfied to a predetermined accuracy.The modified quasilinearization algorithm (MQA) is extended, so that it can be applied to the solution of optimal control problems with general boundary conditions, where the state is not explicitly given at the initial point.The algorithm presented here preserves the MQA descent property on the cumulative error. This error consists of the error in the optimality conditions and the error in the constraints.Three numerical examples are presented in order to illustrate the performance of the algorithm. The numerical results are discussed to show the feasibility as well as the convergence characteristics of the algorithm.This work was supported by the Electrical Research Institute of Mexico and by CONACYT, Consejo Nacional de Ciencia y Tecnologia, Mexico City, Mexico.     

A feasible directions algorithm for time-lag optimal control problems with control and terminal inequality constraints

A computational algorithm for a class of time-lag optimal control problems involving control and terminal inequality constraints is presented. The convergence properties of the algorithm is also investigated. To test the algorithm, an example is solved.This work was partially supported by the Australian Research Grant Committee.     

An approximation algorithm for network design problems with downwards-monotone demand functions

Building on an existing 2-approximate algorithm for the class of network design problems with downwards-monotone demand functions, many of which are NP-hard, we present an algorithm that produces solutions that are at least as good as and typically better than solutions produced by the existing algorithm.     

An efficient approximation algorithm for the survivable network design problem

The survivable network design problem (SNDP) is to construct a minimum-cost subgraph satisfying certain given edge-connectivity requirements. The first polynomial-time approximation algorithm was given by Williamson et al. (Combinatorica 15 (1995) 435–454). This paper gives an improved version that is more efficient. Consider a graph ofn vertices and connectivity requirements that are at mostk. Both algorithms find a solution that is within a factor 2k – 1 of optimal fork 2 and a factor 2 of optimal fork = 1. Our algorithm improves the time from O(k ³n⁴) to O ). Our algorithm shares features with those of Williamson et al. (Combinatorica 15 (1995) 435–454) but also differs from it at a high level, necessitating a different analysis of correctness and accuracy; our analysis is based on a combinatorial characterization of the redundant edges. Several other ideas are introduced to gain efficiency. These include a generalization of Padberg and Rao's characterization of minimum odd cuts, use of a representation of all minimum (s, t) cuts in a network, and a new priority queue system. The latter also improves the efficiency of the approximation algorithm of Goemans and Williamson (SIAM Journal on Computing 24 (1995) 296–317) for constrained forest problems such as minimum-weight matching, generalized Steiner trees and others. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.A preliminary version of this paper has appeared in the Proceedings of the Third Mathematical Programming Society Conference on Integer Programming and Combinatorial Optimization, 1993, pp. 57–74.Research supported in part by NSF Grant No. CCR-9215199 and AT & T Bell Laboratories.Research supported in part by Air Force contracts AFOSR-89-0271 and F49620-92-J-0125 and DARPA contracts N00014-89-J-1988 and N00014-92-1799.This research was performed while the author was a graduate student at MIT. Research supported by an NSF Graduate Fellowship, Air Force contract F49620-92-J-0125, DARPA contracts N00014-89-J-1988 and N00014-92-J-1799, and AT & T Bell Laboratories.     

A numerical algorithm for singular optimal LQ control systems

A numerical algorithm to obtain the consistent conditions satisfied by singular arcs for singular linear–quadratic optimal control problems is presented. The algorithm is based on the Presymplectic Constraint Algorithm (PCA) by Gotay-Nester (Gotay et al., J Math Phys 19:2388–2399, 1978; Volckaert and Aeyels 1999) that allows to solve presymplectic Hamiltonian systems and that provides a geometrical framework to the Dirac-Bergmann theory of constraints for singular Lagrangian systems (Dirac, Can J Math 2:129–148, 1950). The numerical implementation of the algorithm is based on the singular value decomposition that, on each step, allows to construct a semi-explicit system. Several examples and experiments are discussed, among them a family of arbitrary large singular LQ systems with index 2 and a family of examples of arbitrary large index, all of them exhibiting stable behaviour. Research partially supported by MEC grant MTM2004-07090-C03-03. SIMUMAT-CM, UC3M-MTM-05-028 and CCG06-UC3M/ESP-0850.