Solving the Dynamic User Optimal Assignment Problem Considering Queue Spillback

This paper studies the dynamic user optimal (DUO) traffic assignment problem considering simultaneous route and departure time choice. The DUO problem is formulated as a discrete variational inequality (DVI), with an embeded LWR-consistent mesoscopic dynamic network loading (DNL) model to encapsulate traffic dynamics. The presented DNL model is capable of capturing realistic traffic phenomena such as queue spillback. Various VI solution algorithms, particularly those based on feasible directions and a line search, are applied to solve the formulated DUO problem. Two examples are constructed to check equilibrium solutions obtained from numerical algorithms, to compare the performance of the algorithms, and to study the impacts of traffic interacts across multiple links on equilibrium solutions.     

Dynamic User Equilibrium Model for Combined Activity-Travel Choices Using Activity-Travel Supernetwork Representation

Integrated urban transportation models have several benefits over sequential models including consistent solutions, quicker convergence, and more realistic representation of behavior. Static models have been integrated using the concept of Supernetworks. However integrated dynamic transport models are less common. In this paper, activity location, time of participation, duration, and route choice decisions are jointly modeled in a single unified dynamic framework referred to as Activity-Travel Networks (ATNs). ATNs is a type of Supernetwork where virtual links representing activity choices are added to augment the travel network to represent additional choice dimensions. Each route in the augmented network represents a set of travel and activity arcs. Therefore, choosing a route is analogous to choosing an activity location, duration, time of participation, and travel route. A cell-based transmission model (CTM) is embedded to capture the traffic flow dynamics. The dynamic user equilibrium (DUE) behavior requires that all used routes (activity-travel sequences) provide equal and greater utility compared to unused routes. An equivalent variational inequality problem is obtained. A solution method based on route-swapping algorithm is tested on a hypothetical network under different demand levels and parameter assumptions.     

A Reliability-Based Stochastic Traffic Assignment Model for Network with Multiple User Classes under Uncertainty in Demand

This paper presents a novel reliability-based stochastic user equilibrium traffic assignment model in view of the day-to-day demand fluctuations for multi-class transportation networks. In the model, each class of travelers has a different safety margin for on-time arrival in response to the stochastic travel times raised from demand variations. Travelers' perception errors on travel time are also considered in the model. This model is formulated as an equivalent variational inequality problem, which is solved by the proposed heuristic solution algorithm. Numerical examples are presented to illustrate the applications of the proposed model and the efficiency of solution algorithm.     

Allocation of freeway ramp metering volumes to optimize corridor performance

A simple macroscopic freeway traffic corridor model is formulated for the purpose of developing optimal allocations of freeway on-ramp metering volumes. The model represents a freeway and a single parallel "equivalent surface street," both unidirectional, which are interconnected by freeway on-ramps. Since a choice of routes is included in the problem formulation, the fairly standard methodology of "traffic assignment" is employed to predict how drivers will react to the on-ramp metering. An explicit traffic assignment algorithm which includes ramp queueing is developed. Both the corridor and traffic assignment models are restricted to stationary traffic patterns. Two specific corridor performance criteria, freeway travel rate and total travel-time rate, are formulated in terms of the model variables. Then the problem of choosing ramp metering volumes to optimize a performance criterion is posed. A computationally efficient suboptimal dynamic programming scheme is developed and illustrated by an example.     

基于路段元胞传输模型的动态用户最优配流问题

利用基于路段的元胞传输模型进行模拟, 给出了一种计算实际路段出行阻抗的方法, 并在此基础上构造了基于路段变量的动态用户最优变分不等式模型. 模型采用针对迄节点的路段变量, 在每一个小时段都能给出路段流入率、流出率、路段流量和实际路段阻抗, 为用户提供较为全面的诱导信息打下了较好的理论基础. 采用了修正投影算法来进行求解. 数值算例表明模型具有的实用性和优越性, 使道路交通流宏观模型与动态网络交通配流问题得到较好的结合.     

考虑网络流量的最优路径求解模型和算法

本文旨在解决交通网络中群体车辆的路径选择问题．即为每个车辆寻求最优行驶路径．使之在起迄点间的旅行时间最短．考虑到网络流量对路段旅行时间的影响，先进行流量分配，再同时为各个车辆寻求最短路径．为此，首先给出了考虑流量影响的网络模型，然后建立了基于路段的用于流量分配的变分不等式模型．该模型的解给出了车辆按照最优路径行驶时分配到各路段上的车辆数目．由于该模型是完全基于路段的，从而克服了基于路径方法必须进行路径穷举的缺陷．最后给出了最优路径选择算法，并证明了算法的正确性．本文给出的模型和算法适用于交通畅通、交通拥挤等各种情况．实验结果表明本文提出的模型和算法是非常有效的．     

Linear Programming Formulation for Strategic Dynamic Traffic Assignment

This work introduces a novel formulation of system optimal dynamic traffic assignment that captures strategic route choice in users under demand uncertainty. We define strategic route choice to be that users choose a path prior to knowing the true travel demand which will be experienced (therefore users consider the full set of possible demand scenarios). The problem is formulated based on previous work by Ziliaskopoulos (Transp Sci 34(1):37–49, 2000). The resulting novel formulation requires substantial enhancement to account for path-based flows and scenario-based stochastic demands. Further, a numerical demonstration is presented on a network with different demand loading profiles. Finally, model complexity, implications on scalability and future research directions are discussed.     

Non-expected Route Choice Model under Risk on Stochastic Traffic Networks

In this paper, we propose a novel non-expected route travel time (NERTT) model, which belong to the rank-dependent expected utility model. The NERTT consists of two parts, which are the route travel time distribution and the distortion function. With the strictly increasing and strictly concave distortion function, we can prove that the route travel time in the proposed model is risk-averse, which is the main focus of this paper. We show two different reduction methods from the NERTT model to the travel time budget model and mean-excess travel time model. One method is based on the properly selected distortion functions and the other one is based on a general distortion function. Besides, the behavioral inconsistency of the expected utility model in the route choice can be overcome with the proposed model. The NERTT model can also be generalized to the non-expected disutility (NED) model, and some relationship between the NED model and the route choice model based on the cumulative prospect theory can be shown. This indicates that the proposed model has some generality. Finally, we develop a non-expected risk-averse user equilibrium model and formulate it as a variational inequality (VI) problem. A heuristic gradient projection algorithm with column generation is used to solve the VI. The proposed model and algorithm are tested on some hypothetical traffic networks and on some large-scale traffic networks.     

基于有限理性的弹性需求随机用户均衡交通分配模型*

为了同时考虑路网的随机变化特征和出行者的感知误差,在有限理性框架下基于累积前景理论建立了一个弹性需求随机用户均衡模型,给出了等价的变分不等式,设计了求解算法并通过算例进行了验证,结合参数敏感性对均衡状态出行者的认知和心理特征进行了分析。结果表明,OD出行需求和网络均衡态具有显著的参照点依赖效应,出行者对路况满意度越高OD出行需求越大,对路况熟悉程度越高OD出行需求越小。模型及算法可以加深对出行行为的理解,改进传统模型理论假设及适用性的局限,更加精确描述交通流的实际分布形态。     

Pedestrian Travel Behavior Modeling

This paper presents a dynamic mixed discrete-continuous choice approach to modeling pedestrian travel and activity choice behavior in public facilities. The approach views revealed behavior as a manifestation of pedestrians’ preferences by assuming that pedestrians choose the alternative that maximizes expected (subjective) utility, while taking into account the uncertainty in expected traffic conditions. The choice dimensions are trajectories between origin and subsequent destinations, areas where activities are performed (multiple vs. fixed destination), execution of discretionary activities, and finally activities completion times and order.The disutility of a trajectory determines the trajectory choice of the traveler. Destination area choice is included in the modeling by determining time-dependent and destination-specific arrival costs. Furthermore, penalties for not executing a planned activity are introduced into the modeling framework. The resulting modeling approach has a clear analogy with stochastic control theory and dynamic programming in continuous time and space.The main innovations presented here is the relaxation of the assumption that routes are discrete sets of travel links. The approach relaxes the need to build a discrete network, while routes (trajectories) are continuous functions in time and space. At the same time, destination choice is included in the modeling framework.     

A Link-Node Discrete-Time Dynamic Second Best Toll Pricing Model with a Relaxation Solution Algorithm

Dynamic congestion pricing has become an important research topic because of its practical implications. In this paper, we formulate dynamic second-best toll pricing (DSBTP) on general networks as a bilevel problem: the upper level is to minimize the total weighted system travel time and the lower level is to capture motorists’ route choice behavior. Different from most of existing DSBTP models, our formulation is in discrete-time, which has very distinct properties comparing with its continuous-time counterpart. Solution existence condition of the proposed model is established independent of the actual formulation of the underlying dynamic user equilibrium (DUE). To solve the bilevel DSBTP model, we adopt a relaxation scheme. For this purpose, we convert the bilevel formulation into a single level nonlinear programming problem by applying a link-node based nonlinear complementarity formulation for DUE. The single level problem is solved iteratively by first relaxing the strick complementarity by a relaxation parameter, which is then progressively reduced. Numerical results are also provided in this paper to illustrate the proposed model and algorithm. In particular, we show that by varying travel time weights on different links, DSBTP can help traffic management agencies better achieve certain system objectives. Examples are given on how changes of the weights impact the optimal tolls and associated objective function values.

Link Travel Times II: Properties Derived from Traffic-Flow Models

We investigate the properties of travel times when the latter are derived from traffic-flow models. In particular we consider exit-flow models, which have been used to model time-varying flows on road networks, in dynamic traffic assignment (DTA). But we here define the class more widely to include, for example, models based on finite difference approximations to the LWR (Lighthill, Whitham and Richards) model of traffic flow, and large step versions of these. For the derived travel times we investigate the properties of existence, uniqueness, continuity, first-in-first-out (FIFO), causality and time-flow consistency (or intertemporal consistency). We assume a single traffic type and assume that time may be treated as continuous or as discrete, and for each case we obtain conditions under which the above properties are satisfied, and interrelations among the properties. For example, we find that FIFO is easily satisfied, but not strict causality, and find that if we redefine travel time to ensure strict causality then we lose time-flow consistency, and that neither of these conditions is strictly necessary or sufficient for FIFO. All of the models can be viewed as an approximation to a model that is continuous in time and space (the LWR model), and it seems that any loss of desirable properties is the price we pay for using such approximations. We also extend the exit-flow models and results to allow inhomogeneity over time (link capacity or other parameters changing over time), and show that FIFO is still ensured if the exit-flow function is defined appropriately.     

Adaptive Park-and-ride Choice on Time-dependent Stochastic Multimodal Transportation Network

In transportation networks with stochastic and dynamic travel times, park-and-ride decisions are often made adaptively considering the realized state of traffic. That is, users continue driving towards their destination if the congestion level is low, but may consider taking transit when the congestion level is high. This adaptive behavior determines whether and where people park-and-ride. We propose to use a Markov decision process to model the problem of commuters’ adaptive park-and-ride choice behavior in a transportation network with time-dependent and stochastic link travel times. The model evaluates a routing policy by minimizing the expected cost of travel that leverages the online information about the travel time on outgoing links in making park-and-ride decisions. We provide a case study of park-and-ride facilities located on freeway I-394 in Twin Cities, Minnesota. The results show a significant improvement in the travel time by the use of park-and-ride during congested conditions. It also reveals the time of departure, the state of the traffic, and the location from where park-and-ride becomes an attractive option to the commuters. Finally, we show the benefit of using online routing in comparison to an offline routing algorithm.

     

The Dynamics and Equilibria of Day-to-Day Assignment Models

Traffic network modelling is a field that has developed over a number of decades, largely from the economics of predicting equilibria across route travel choices, in consideration of the congestion levels on those routes. More recently, there has been a growing influence from the psychological and social science fields, leading to a greater interest in understanding behavioural mechanisms that underlie such travel choice decisions. The purpose of the present paper is to describe mathematical models which aim to reflect day-to-day dynamic adjustments in route choice behaviour in response to previous travel experiences. Particularly, the aim is to set these approaches in a common framework with the conventional economic equilibrium models. Starting from the analysis of economic equilibria under perturbations, the presentation moves onto deterministic dynamical system models and stochastic processes. Simple illustrative examples are used to introduce the modelling approaches. It is argued that while such dynamical approaches have appeal, in terms of the range of adaptive behavioural processes that can be incorporated, their estimation may not be trivial. In particular, the obvious solution technique (namely, explicit simulation of the dynamics) can lead to a rather complex problem of interpretation for the model-user, and that more analytical approximation techniques may be a better way forward.     

A ‘complexity level’ analysis of immediate vision

This paper demonstrates how serious consideration of the deep complexity issues inherent in the design of a visual system can constrain the development of a theory of vision. We first show how the seemingly intractable problem of visual perception can be converted into a much simpler problem by the application of several physical and biological constraints. For this transformation, two guiding principles are used that are claimed to be critical in the development of any theory of perception. The first is that analysis at the complexity level is necessary to ensure that the basic space and performance constraints observed in human vision are satisfied by a proposed system architecture. Second, the maximum power/minimum cost principle ranks the many architectures that satisfy the complexity level and allows the choice of the best one. The best architecture chosen using this principle is completely compatible with the known architecture of the human visual system, and in addition, leads to several predictions. The analysis provides an argument for the computational necessity of attentive visual processes by exposing the computational limits of bottom-up early vision schemes. Further, this argues strongly for the validity of the computational approach to modeling the human visual system. Finally, a new explanation for the pop-out phenomenon so readily observed in visual search experiments, is proposed.     

Efficient Discretisation for Link Travel Time Models

In the literature, two different models have been used to compute link travel times in dynamic traffic assignment (DTA), and elsewhere we investigated how these are affected by discretising the link length. Here we consider discretising time as well as space (the link length). We vary the discretising of time with spatial discretisation held fixed, and vice versa, and also vary both together. The results show that coordinated discretisation is usually the most efficient in approximating the limit solution (continuous time, continuous space) and, even when it is not the most efficient, it has other advantages. The results have implications for algorithms for DTA and for the choice of discrete versus continuous time models. For example, refining the discretisation of time (without refining it for space) can make the solution less accurate, so that in the widely used whole-link models (i.e. without spatial discretisation) it is more efficient to use the largest feasible time steps, close to the link travel time.     

Optimization of a nonlinear area traffic control system with elastic demand

An area traffic control network system is considered in this paper. Optimal signal settings can be determined while trip rates and network flow are in equilibrium. This problem can be formulated as a nonlinear mathematical program with equilibrium constraints. For the objective function, the system performance can be defined as a function of signal setting variables. For the constraint set, a user equilibrium traffic assignment with elastic demand obeying Wardrop’s first principle is formulated as a variational inequality problem. Due to the nonlinearity and non-differentiability of the perturbed solutions in equilibrium constraints, a non-smooth approach is investigated in this paper. Numerical tests are performed using a variety of example road networks to quantify the effectiveness and robustness of the proposed method.     

Analytical Models of the Dynamic Traffic Assignment Problem

A review of analytical formulations of the dynamic traffic assignment problem is presented, focusing on the authors' experience with variational inequality approaches. Solution algorithms and computational issues requiring additional study are discussed.     

Improving the Solution of Variational Inequalities Based on the Optimization Approach

An optimization approach to solving a convex finite-dimensional variational inequality with nonpotential operator is examined. It is shown how to construct an optimization problem equivalent to the variational inequality in the space of the original variables. A first-order algorithm to solve variational inequalitieis is formulated based on this optimization problem.     

Solving Kirkman’s Schoolgirl Problem in a Few Seconds

The Social Golfer Problem has been extensively used by the constraint community in recent years as an example of a highly symmetric problem. It is an excellent problem for benchmarking symmetry breaking mechanisms such as SBDS or SBDD and for demonstrating the importance of the choice of the right model for one problem. We address in this paper a specific instance of the Golfer Problem well known as Kirkmans Schoolgirl Problem and list a collection of techniques and tricks to find efficiently all its unique solutions. In particular, we propose SBDD+, a generic improvement over SBDD which allows a deep pruning when a symmetry is detected during the search. Our implementation of the presented techniques improves previously published results by an order of magnitude for CPU time as well as for number of backtracks. It computes the seven unique solutions of Kirkmans problem in a few seconds.