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.     

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.     

Locating replenishment stations for electric vehicles: application to Danish traffic data

Environment-friendly electric vehicles have gained popularity and increased attention in recent years. The deployment of a network of recharging stations is essential given their limited travel range. This paper considers the problem of locating electronic replenishment stations for electric vehicles on a traffic network with flow-based demand. The objective is to optimize the network performance, for example to maximize the flow covered by a prefixed number of stations or to minimize the number of stations needed to cover traffic flows. Two integer linear programming formulations are proposed to model the problem. These models are tested on real-life traffic data collected in Denmark.     

基于鲁棒优化的随机时变网络最优路径研究

交通事故、恶劣天气以及偶发的交通拥堵等都会导致道路交通网络中行程时间的不确定性,极大地影响了道路交通系统的可靠性,同时给日常生活中出行计划的制定以及出行路径的选择带来了不便。因此,本次研究将综合考虑道路交通网络中由于交通流量的全天变化所导致的路径行程时间的时变特征,以及由于事故、天气等不确定因素所导致的路径行程时间的随机特征,并以此作为路网环境的假设条件,对出行路径选择问题进行研究。具体地,首先建立行程时间的动态随机变量,并在此基础上模拟构建了随机时变网络。随后,定义了该网络环境下路径选择过程中所考虑的成本费用,并通过鲁棒优化的方法,将成本费用鲁棒性最强的路径视为最优路径。随后,在随机一致性条件下,通过数学推导证明了该模型可以简化为解决一个确定性时变网络中的最短路径问题。最终,具有多项式时间计算复杂度的改进Dijkstra算法被应用到模型的求解中,并通过小型算例验证模型及算法的有效性。结果表明,本研究中所提出的方法可以被高效率算法所求解,并且不依赖于先验行程时间概率分布的获取,因此对后续的大规模实际城市道路网络应用提供了良好的理论基础。此外,由于具有行程时间随机时变特征的交通网络更接近实际道路情况,因此本次研究的研究成果具有较高的实际意义和应用价值。     

Reconstructing freeway travel times with a simplified network flow model alternating the adopted fundamental diagram

The present study summarises the travel time reconstruction performance of a network flow model by explicitly analysing the adopted fundamental diagram relation under congested and un-congested traffic patterns. The incorporated network flow model uses a discrete meso-simulation approach in which the anisotropic property of traffic flow and the uniform acceleration of vehicle packets are explicitly considered. The flow performances on link-route dynamics have been derived by reasonably alternating the adopted two-phase, i.e., congested and un-congested, fundamental relation of traffic flow. The linear speed–density relation with the creeping speed assumption is substituted with the triangular flow–density relation in order to investigate the performance of the network flow model in varying flow patterns. Applying the anisotropic mesoscopic model, the measure of travel time is obtained as a link performance from a simplified dynamic network loading process. Travel time reconstruction performance of the network flow model is sought considering the actual measures that are obtained by a probe vehicle, in addition to reconstructions by a macroscopic network flow model. The main improvements on travel time reconstruction process are encountered in terms of the computation load within the explicit analyses by the alternation of adopted two-phase fundamental diagram. Although the accuracies of the flow model with the adoption of two different fundamental diagrams are hard to differentiate, the computational burden of the simulation process by the triangular fundamental diagram is found to be considerably different.     

Dynamic system optimal performances of shared autonomous and human vehicle system for heterogeneous travellers

ABSTRACT

Autonomous vehicles (AV) can solve vehicle relocation problems faced by traditional one-way vehicle-sharing systems. This paper explores the deterministic time-dependent system optimum of mixed shared AVs (SAV) and human vehicles (SHV) system to provide the benchmark for the situation of mixed vehicle flows. In such a system, the system planner determines vehicle-traveller assignment and optimal vehicle routing in transportation networks to serve predetermined travel demand of heterogeneous travellers. Due to large number of vehicles involved, travel time is considered endogenous with congestion. Using link transmission model (LTM) as a traffic flow model, the deterministic time-dependent system optimum is formulated as linear programming (LP) model to minimize the comprehensive cost including travellers’ travel time cost, waiting time cost and empty vehicle repositioning time cost. Numerical examples are conducted to show system performances and model effectiveness.     

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.     

多用户类多准则交通分配的势博弈与拥挤定价

交通管理者在解决路网拥挤问题时,并不知道出行者的出行效用,同时管理者难以对出行者的路径选择行为做出准确的观测.运用势博弈理论分析多用户类多准则交通行为的演化过程,得到了固定需求和弹性需求情形下的可容许动态(一种刻画出行者通过转换路径增加当前效用的近似调整行为的演化动态),证明当路段时间函数和逆需求函数为严格单调、连续、可微时,所对应的交通分配是势博弈问题的惟一Nash均衡点.进一步研究了固定需求下的可变拥挤道路收费问题,得到了在当前系统状态下实现系统最优交通分配的拥挤收费水平.     

Chaos in a dynamic model of urban transportation network flow based on user equilibrium states

In this study, we investigate the dynamical behavior of network traffic flow. We first build a two-stage mathematical model to analyze the complex behavior of network flow, a dynamical model, which is based on the dynamical gravity model proposed by Dendrinos and Sonis [Dendrinos DS, Sonis M. Chaos and social-spatial dynamic. Berlin: Springer-Verlag; 1990] is used to estimate the number of trips. Considering the fact that the Origin–Destination (O–D) trip cost in the traffic network is hard to express as a functional form, in the second stage, the user equilibrium network assignment model was used to estimate the trip cost, which is the minimum cost of used path when user equilibrium (UE) conditions are satisfied. It is important to use UE to estimate the O–D cost, since a connection is built among link flow, path flow, and O–D flow. The dynamical model describes the variations of O–D flows over discrete time periods, such as each day and each week. It is shown that even in a system with dimensions equal to two, chaos phenomenon still exists. A “Chaos Propagation” phenomenon is found in the given model.     

Modelling dynamic network loading ontransportation networks through a continuous

The efforts spent by researchers in the last few years in traffic modelling have been focused on the modelization of dynamic behaviour of the several components making up a transportation system.In the field of traffic assignment, a large number of models and procedures have been proposed in order to perform Dynamic Network Loading (DNL), that is the reproduction of within-day variable link performances once a corresponding Origin/Destination (O/D) demand and users' choice model has been given. These models can be used both to evaluate traffic flows and, what is more relevant, to simulate the effects of regulation strategies on users' behaviour.

In this paper, after a brief review of the state of the art in this field, a continuous dynamic network loading model is proposed; it removes some of the drawbacks of other packet approach models proposed in literature and explicitly allows the en-route modification of the followed path. An algorithmic development of the model and a set of applications on text networks are also proposed.     

Locating Active Sensors on Traffic Networks

Sensors are used to monitor traffic in networks. For example, in transportation networks, they may be used to measure traffic volumes on given arcs and paths of the network. This paper refers to an active sensor when it reads identifications of vehicles, including their routes in the network, that the vehicles actively provide when they use the network. On the other hand, the conventional inductance loop detectors are passive sensors that mostly count vehicles at points in a network to obtain traffic volumes (e.g., vehicles per hour) on a lane or road of the network.This paper introduces a new set of network location problems that determine where to locate active sensors in order to monitor or manage particular classes of identified traffic streams. In particular, it focuses on the development of two generic locational decision models for active sensors, which seek to answer these questions: (1) “How many and where should such sensors be located to obtain sufficient information on flow volumes on specified paths?”, and (2) “Given that the traffic management planners have already located count detectors on some network arcs, how many and where should active sensors be located to get the maximum information on flow volumes on specified paths?”The problem is formulated and analyzed for three different scenarios depending on whether there are already count detectors on arcs and if so, whether all the arcs or a fraction of them have them. Location of an active sensor results in a set of linear equations in path flow variables, whose solution provide the path flows. The general problem, which is related to the set-covering problem, is shown to be NP-Hard, but special cases are devised, where an arc may carry only two routes, that are shown to be polynomially solvable. New graph theoretic models and theorems are obtained for the latter cases, including the introduction of the generalized edge-covering by nodes problem on the path intersection graph for these special cases. An exact algorithm for the special cases and an approximate one for the general case are presented.     

Un modelo de difusión anisótropa para el estudio del tráfico urbano

In order to design or redesign urban transportation networks, the employment of mathematical models is very useful for predicting the effects of possible modifications of implementing. Such models allow the determination of vehicular flows and travel times for every link of the network from the knowledge of its inherent features and the corresponding traffic demand. They are based on a phenomenological law of the social collective behavior of the drivers called Wardrop principle. It is an optimization problem, in general, very demanding from the computational point of view.In order to accelerate the computation process, in this paper, a continuum model for the urban traffic is proposed. The fundamental assumption behind this theory is that the variation of network properties is small in close regions when compared with the full system. Accordingly, it is possible to use continuous functions for representing travel times or vehicular flows. Essentially, the problem is formulated as a system of non-linear anisotropic diffusion (differential) equations that can be conveniently solved by means of the finite element method. The efficiency of the proposed model is studied by means of a comparison with results obtained with the classical optimization approach. As shown, the results are similar although the computation times are significantly reduced.     

Integrating link-based discrete credit charging scheme into discrete network design problem

In this paper, we present an optimization model for integrating link-based discrete credit charging scheme into the discrete network design problem, to improve the transport performance from the perspectives of both transport network planning and travel demand management. The proposed model is a mixed-integer nonlinear bilevel programming problem, which includes an upper level problem for the transport authority and a lower level problem for the network users. The lower level sub-model is the traffic network user equilibrium (UE) formulation for a given network design strategy determined by the upper level problem. The network user at the lower level tries to minimize his/her own generalized travel cost (including both the travel time and the value of the credit charged for using the link) by choosing his/her route. While the transport authority at the upper level tries to find the optimal number of lanes and credit charging level with their locations to minimize the total system travel time (or maximize the transportation system performance). A genetic algorithm is used to solve the proposed mixed-integer nonlinear bilevel programming problem. Numerical experiments show the efficiency of the proposed model for traffic congestion mitigation, reveal that interaction effects across the tradable credit scheme and the discrete network design problem which amplify their individual effects. Moreover, the integrated model can achieve better performance than the sequential decision problems.     

带时空相关性分析的行车时间估计模型

基于流体动力学方程的行车时间估计模型不能很好地反映真实的行车时间,需要对其进行一定的改进.在对交通流进行流体动力学建模的基础之上,引入对高速公路路网中不同路段之间的行车时间相关性和同一路段不同季节、不同时段的行车时间相关性分析,建立了带时空相关性分析的时间估计模型,使用统计学的方法消除动力学模型的误差.     

行车时间估计与路径寻优问题

通过公路上安装的传感器采集数据,从而估算出车辆的行驶时间并求取最优路径,可以方便人们的出行.根据某段公路上传感器提供的数据分析了该段公路的交通状况,建立微分方程模型和关联度分析模型分析交通状况特征及相互影响,并利用ARIMA模型对速度进行了预测.通过对交通干线图进行分析,在假定各路段上的运行时间为独立的随机变量、考虑路段间的相互影响和根据给定的条件这三种情况下,分别建立模型用于估计跟路段通过时间和寻找最优路径,求解得到理想的结果.所建立模型有较强的实用性,有一定的参考作用.     

Modeling traffic flow interrupted by incidents

A steady-state M/M/c queueing system under batch service interruptions is introduced to model the traffic flow on a roadway link subject to incidents. When a traffic incident happens, either all lanes or part of a lane is closed to the traffic. As such, we model these interruptions either as complete service disruptions where none of the servers work or partial failures where servers work at a reduced service rate. We analyze this system in steady-state and present a scheme to obtain the stationary number of vehicles on a link. For those links with large c values, the closed-form solution of M/M/∞ queues under batch service interruptions can be used as an approximation. We present simulation results that show the validity of the queueing models in the computation of average travel times.     

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.     

Reliability-based user equilibrium in a transport network under the effects of speed limits and supply uncertainty

This study investigates the system-wide traffic flow re-allocation effect of speed limits in uncertain environments. Previous studies have only considered link capacity degradation, which is only one of the factors that lead to supply uncertainty. This study examines how imposing speed limits reallocates the traffic flows in a situation of general supply uncertainty with risk-averse travelers. The effects of imposing a link-specific speed limit on link driving speed and travel time are analyzed, given the link travel time distribution before imposing the speed limit. The expected travel time and travel time standard deviation of a link with a speed limit are derived from the link travel time distribution and are both continuous, monotone, and convex functions in terms of link flow. A distribution-free, reliability-based user equilibrium with speed limits is established, in which travelers are assumed to choose routes that minimize their own travel time budget. A variational inequality formulation for the equilibrium problem is proposed and the solution properties are provided. In this study, the inefficiency of a reliability-based user equilibrium flow pattern with speed limits is defined and found to be bounded above when supply uncertainty refers to capacity degradation. The upper bound depends on the level of risk aversion of travelers, a ratio related to the design and worst-case link capacities, and the highest power of all link performance functions.     

Discrete time dynamic traffic assignment models and solution algorithm for managed lanes

“Managed” lanes of highways usually refer to lanes that are not open to all types of vehicles, such as “High Occupancy Vehicles” (HOV) lanes and “High Occupancy Toll” (HOT) lanes, etc. The HOV lanes of highways are reserved only for vehicles with a driver and one or more passengers. Whereas, HOT lanes allow all vehicles but require tolls from the vehicles with no passenger except the driver. In this paper, we present a discrete-time traffic assignment system optimum model to predict the optimal traffic flows on managed lanes at various times in the entire planning horizon. This model minimizes the overall delay (travel time) and belongs to the class of dynamic traffic assignment (DTA) problems. When applied to general networks, DTA problems can be large and difficult to solve, but the problem is manageable when it is applied to a network with managed lanes. In particular, the DTA model in this paper for managed lanes is reduced to a mixed integer program for which several efficient heuristic algorithms exist. This paper also discusses the special properties of the discrete-time DTA model, based upon which a heuristic algorithm is proposed. Numerical results show that this algorithm is efficient for many cases of the managed lane problems.     

Calculation of traffic flow breakdown probability to optimize link throughput

Traffic breakdown phenomenon is prevalent in empirical traffic system observations. Traffic flow breakdown is usually defined as an amount of sudden drop in traffic flow speed when traffic demand exceeds capacity. Modeling and calculating traffic flow breakdown probability remains an important issue when analyzing the stability and reliability of transportation system. The breakdown mechanism is still mysterious to practitioners and researchers in varying manner. Treating breakdown as a random event, this paper use discrete time Markov chain (DTMC) to model traffic state transition path, as a result, a transition probability matrix can be generated from empirical observations. From empirical analysis of breakdown, we found this formulation of breakdown probability follows the Zipf distribution. Therefore, a connection from traffic flow breakdown probability to how many vehicles are occupying a certain freeway segment (e.g. a link) will be established. Following from the results, a quantitative measure of breakdown probability can be obtained to optimize ramp metering rates to achieve optimum system performance measures.