A continuous day-to-day traffic assignment model and the existence of a continuous dynamic user equilibrium

Suppose that a road network model is given, together with some given demand for travel by (say) car and that the demand for travel varies with time of day but not from day to day. Suppose that this demand is given in the form of specified total outflow rates from each origin headed towards each destination, for each origin-destination pair and for each time of day, and that some initial time-dependent routeinflow rates, meeting the given demand, are given. Finally, suppose that within-day time is represented by a continuous variable. This paper specifies a natural smooth day-to-day route-swapping procedure wherein drivers swap toward less expensive routes as day succeeds day, and shows that under reasonable conditions there is an equilibrium state of this dynamical system. If such a collection of route-inflows has arisen today, say, then there is no incentive for any route-inflow to change tomorrow, in the sense that at each moment of today each of today's route-inflows isalready on a route which today yielded the smallest travel cost. Such a set of no-incentive-to-change route-inflows is called adynamic equilibrium, or adynamic user-equilibrium, and may be regarded as a solution of the dynamic equilibrium traffic assignment problem. Thus, the paper introduces a smooth day-to-day dynamic assignment model and, using this model, shows that there is a dynamic user-equilibrium in a continuous time setting. The paper briefly considers the day-to-day stability of the route-swapping process, also in a continuous setting. Finally, the paper gives a simple dynamical example illustrating the stability of the route-swapping process in a simple two-route network when there is deterministic queueing at bottlenecks.     

Application of a simulation-based dynamic traffic assignment model

The evaluation of on-line intelligent transportation system (ITS) measures, such as adaptive route-guidance and traffic management systems, depends heavily on the use of faster than real time traffic simulation models. Off-line applications, such as the testing of ITS strategies and planning studies, are also best served by fast-running traffic models due to the repetitive or iterative nature of such investigations. This paper describes a simulation-based, iterative dynamic equilibrium traffic assignment model. The determination of time-dependent path flows is modeled as a master problem that is solved using the method of successive averages (MSA). The determination of path travel times for a given set of path flows is the network-loading sub-problem, which is solved using the space-time queuing approach of Mahut. This loading method has been shown to provide reasonably accurate results with very little computational effort. The model was applied to the Stockholm road network, which consists of 2100 links, 1191 nodes, 228 zones, representing and 4964 turns. The results show that this model is applicable to medium-size networks with a very reasonable computation time.     

Discrete-time dynamic traffic assignment models with periodic planning horizon: system optimum

This paper proposes a system optimal dynamic traffic assignment model that does not require the network to be empty at the beginning or at the end of the planning horizon. The model assumes that link travel times depend on traffic densities and uses a discretized planning horizon. The resulting formulation is a nonlinear program with binary variables and a time-expanded network structure. Under a relatively mild condition, the nonlinear program has a feasible solution. When necessary, constraints can be added to ensure that the solution satisfies the First-In-First-Out condition. Also included are approximation schemes based on linear integer programs that can provide solutions arbitrarily close to that of the original nonlinear problem.     

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.     

Simulating vehicular traffic in a network using dynamic routing

We present a new numerical code which solves the Lighthill – Whitham model, the classic macroscopic model for vehicular traffic flow, in a network with multi-destinations. We use a high-resolution shock-capturing scheme with approximate Riemann solver to solve the partial differential equations of the Lighthill – Whitham theory. These schemes are very efficient, robust and moreover well adapted to simulations of traffic flows. We develop a theory of dynamic routing including a procedure for traffic flow assignment at junctions which reproduces the correct propagation of irregularities and ensures at the same time conservation of the number of vehicles.     

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.     

An efficient algorithm for optimal design of area traffic control with network flows

An equilibrium network design (EQND) is a problem of finding the optimal design parameters while taking into account the route choice of users. This problem can be formulated as an optimization by taking the user equilibrium traffic assignment as a constraint. In this paper, the methods solving the EQND problem with signal settings are investigated via numerical calculations on two example road networks. An efficient algorithm is proposed in which improvement on a locally optimal search by combining the technique of parallel tangents with the gradient projection method is presented. As it shows, the method combines the locally optimal search and globally search heuristic achieved substantially better performance than did those other approaches.     

The equilibrium generalized assignment problem and genetic algorithm

The well-known generalized assignment problem (GAP) is to minimize the costs of assigning n jobs to m capacity constrained agents (or machines) such that each job is assigned to exactly one agent. This problem is known to be NP-hard and it is hard from a computational point of view as well. In this paper, follows from practical point of view in real systems, the GAP is extended to the equilibrium generalized assignment problem (EGAP) and the equilibrium constrained generalized assignment problem (ECGAP). A heuristic equilibrium strategy based genetic algorithm (GA) is designed for solving the proposed EGAP. Finally, to verify the computational efficiency of the designed GA, some numerical experiments are performed on some known benchmarks. The test results show that the designed GA is very valid for solving EGAP.     

A labeling method for dynamic driver-task assignment with uncertain task durations

The problem of assigning drivers to cover tasks with service time windows and uncertain task durations is formulated as a dynamic stochastic decision model. We develop an adaptive labeling solution procedure that can incorporate various practical constraints and work rules. Experiments are conducted to evaluate the procedure's performance and compare the stochastic and deterministic formulations.     

A note on the minimum instantaneous cost path of the dynamic traffic assignment problem

We consider an example to show that the minimum instantaneous cost path principle, as suggested in Friesz et al. [1] for generalising Wardrop's first principle to the dynamic state, may cause some drivers' routes to loop. These looping routes traverse the same link more than once - indeed, in our example six times.The work reported in this paper has been partly funded by the Science and Engineering Research Council of the United Kingdom.     

A simple dual algorithm for the generalised assignment problem

A new algorithm for the generalised assignment problem is described in this paper. The dual-type algorithm uses a simple heuristic derived from a relaxation of the problem. The algorithm has been tested on generalised assignment problems of substantial size and compared to an exact integer programming approach and a well-established heuristic approach. Computational results look promising in terms of speed and solution quality.     

Fuzzy weighted equilibrium multi-job assignment problem and genetic algorithm

In this paper, the equilibrium optimization problem is proposed and the assignment problem is extended to the equilibrium multi-job assignment problem, equilibrium multi-job quadratic assignment problem and the minimum cost and equilibrium multi-job assignment problem. Furthermore, the mathematical models of the equilibrium multi-job assignment problem and the equilibrium multi-job quadratic assignment problem with fuzzy parameters are formulated. Finally, a genetic algorithm is designed for solving the proposed programming models and some numerical examples are given to verify the efficiency of the designed algorithm.     

The dynamic frequency assignment problem

In this paper, we consider a frequency assignment problem occurring in a military context. The main originality of the problem pertains to its dynamic dimension: new communications requiring frequency assignments need to be established throughout a battlefield deployment. The problem resolution framework decomposes into three phases: assignment of an initial kernel of communications, dynamic assignment of new communication links and a repair process when no assignment is possible. Different solution methods are proposed and extensive computational experiments are carried out on realistic instances.     

A new implementation of an algorithm for the optimal assignment problem: An improved version of Munkres' algorithm

Existing implementations of Munkres' algorithm for the optimal assignment problem are shown to requireO(n ⁴) time in the worstn×n case. A new implementation is presented which runs in worst-case timeO(n ³) and compares favorably in performance with the algorithm of Edmonds and Karp for this problem.The results of this paper were obtained by the author while at the Department of Computer Science, Cornell University. This work was supported in part by a Vanderbilt University Research Council Grant.     

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 note on optimal assignment of slack due-dates in single-machine scheduling

This paper extends T.C.E. Cheng's approach for optimal assignment of slack due-dates and sequencing in the single-machine shop to the case when preemption is allowed and there are precedence constraints and ready times of jobs. It is shown that under special conditions the presented algorithm may be used when preemption is not allowed.     

A simplex-based labelling algorithm for the linear fractional assignment problem

This paper constructs an algorithm to solve the fractional assignment problem. Algorithms that are currently used are mostly based on parametric approaches and must solve a sequence of optimization procedures. They also neglect the difficulties caused by degeneracy. The proposed algorithm performs optimization once and overcomes degeneracy. The main features of the algorithm are an effective initial heuristic approach, a simple labelling procedure and an implicit primal-dual schema. A numerical example is presented and demonstrates that the proposed algorithm is easy to apply. Computational results are compared with those from other developed methods. The results show that the proposed algorithm is efficient.     

Evaluation of the multiobjective ant colony algorithm performances on biobjective quadratic assignment problems

The difficulty of resolving the multiobjective combinatorial optimization problems with traditional methods has directed researchers to investigate new approaches which perform better. In recent years some algorithms based on ant colony optimization (ACO) metaheuristic have been suggested to solve these multiobjective problems. In this study these algorithms have been reported and programmed both to solve the biobjective quadratic assignment problem (BiQAP) instances and to evaluate the performances of these algorithms. The robust parameter sets for each 12 multiobjective ant colony optimization (MOACO) algorithms have been calculated and BiQAP instances in the literature have been solved within these parameter sets. The performances of the algorithms have been evaluated by comparing the Pareto fronts obtained from these algorithms. In the evaluation step, a multi significance test is used in a non hierarchical structure, and a performance metric (P metric) essential for this test is introduced. Through this study, decision makers will be able to put in the biobjective algorithms in an order according to the priority values calculated from the algorithms’ Pareto fronts. Moreover, this is the first time that MOACO algorithms have been compared by solving BiQAPs.     

A branch-and-bound algorithm for the singly constrained assignment problem

The singly constrained assignment problem (SCAP) is a linear assignment problem (LAP) with one extra side constraint, e.g., due to a time restriction. The SCAP is, in contrast to the LAP, difficult to solve. A branch-and-bound algorithm is presented to solve the SCAP to optimality. Lower bounds are obtained by Lagrangean relaxation. Computational results show that the algorithm is able to solve different types of SCAP instances up to size n = 1000 within short running times on a standard personal computer.     

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.