A biased random-key genetic algorithm for road congestion minimization

One of the main goals in transportation planning is to achieve solutions for two classical problems, the traffic assignment and toll pricing problems. The traffic assignment problem aims to minimize total travel delay among all travelers. Based on data derived from the first problem, the toll pricing problem determines the set of tolls and corresponding tariffs that would collectively benefit all travelers and would lead to a user equilibrium solution. Obtaining high-quality solutions for this framework is a challenge for large networks. In this paper, we propose an approach to solve the two problems jointly, making use of a biased random-key genetic algorithm for the optimization of transportation network performance by strategically allocating tolls on some of the links of the road network. Since a transportation network may have thousands of intersections and hundreds of road segments, our algorithm takes advantage of mechanisms for speeding up shortest-path algorithms.     

Applications of sensitivity analysis for probit stochastic network equilibrium

Network equilibrium models are widely used by traffic practitioners to aid them in making decisions concerning the operation and management of traffic networks. The common practice is to test a prescribed range of hypothetical changes or policy measures through adjustments to the input data, namely the trip demands, the arc performance (travel time) functions, and policy variables such as tolls or signal timings. Relatively little use is made, however, of the full implicit relationship between model inputs and outputs inherent in these models. By exploiting the representation of such models as an equivalent optimisation problem, classical results on the sensitivity analysis of non-linear programs may be applied, to produce linear relationships between input data perturbations and model outputs. We specifically focus on recent results relating to the probit Stochastic User Equilibrium (PSUE) model, which has the advantage of greater behavioural realism and flexibility relative to the conventional Wardrop user equilibrium and logit SUE models. The paper goes on to explore four applications of these sensitivity expressions in gaining insight into the operation of road traffic networks. These applications are namely: identification of sensitive, ‘critical’ parameters; computation of approximate, re-equilibrated solutions following a change (post-optimisation); robustness analysis of model forecasts to input data errors, in the form of confidence interval estimation; and the solution of problems of the bi-level, optimal network design variety. Finally, numerical experiments applying these methods are reported.     

A non-smooth model for signalized road network design problems

A signalized road network is considered where the set of link capacity expansions and signal setting variables are simultaneously determined. This paper addresses a new optimization scheme for a signalized road network design problem (SRNDP). A SRNDP can be formulated as a mathematical program with equilibrium constraints (MPEC) where user equilibrium is expressed as a variational inequality problem. Due to non-differentiability of the perturbed solutions in equilibrium constraints, a non-smooth model is established. A bundle subgradient projection (BSP) method is presented with global convergence. Numerical calculations are conducted on a real data city road network and large-scale grid networks where promising results are obtained.     

有限多类别交通网络的扩展Wardrop均衡

研究有容量约束的交通网络中有限多类别用户的扩展Wardrop均衡.证明扩展Wardrop均衡定义的4种等价形式;并利用凸集分离定理得到在一定条件下.定义中A(v)的存在性.A(v)可以看作是一种收费,因而得到了有限多类别的交通网络中收费的存在性.     

A subgradient optimization model for continuous road network design problem

This paper addresses a subgradient optimization model for a well-known continuous network design problem (CNDP). A continuous network design problem can be formulated as a mathematical program with equilibrium constraints (MPEC) where the user equilibrium flows are considered. By contrast to previous studies, in this paper, a conjugate subgradient projection method is presented to efficiently solve the continuous network design problem with global convergence. Numerical calculations are conducted on a real data of road network and various grid-size networks where encouraging results are reported when compared to earlier studies.     

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.     

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.     

A hybrid optimization algorithm for area traffic control problem

For an area traffic control road network subject to equilibrium flows, the maximum possible increase in travel demands is considered while total delays for travellers are minimized with respect to the common cycle time, the starts and durations of green times and the offsets. 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. In this paper, we present a hybrid optimization algorithm to simultaneously solve the maximum increase in travel demands and minimizing total delays of travellers. Numerical computations are made for the values of performance index and the reserve capacity achieved at various sets of initial signal settings on a variety of signal-controlled networks. Encouraging results are obtained when compared with other alternatives.     

A turning restriction design problem in urban road networks

Turning restriction is one of the commonest traffic management techniques and an effective low cost traffic improvement strategy in urban road networks. However, the literature has not paid much attention to the turning restriction design problem (TRDP), which aims to determine a set of intersections where turning restrictions should be implemented. In this paper, a bi-level programming model is proposed to formulate the TRDP. The upper level problem is to minimize the total travel cost from the viewpoint of traffic managers, and the lower level problem is to depict travelers’ route choice behavior based on stochastic user equilibrium (SUE) theory. We propose a branch and bound method (BBM), based on the sensitivity analysis algorithm (SAA), to find the optimal turning restriction strategy. A branch strategy and a bound strategy are applied to accelerate the solution process of the TRDP. The computational experiments give promising results, showing that the optimal turning restriction strategy can obviously reduce system congestion and are robust to the variations of both the dispersion parameter of the SUE problem and the level of demand.     

Fast paths in large-scale dynamic road networks

Efficiently computing fast paths in large-scale dynamic road networks (where dynamic traffic information is known over a part of the network) is a practical problem faced by traffic information service providers who wish to offer a realistic fast path computation to GPS terminal enabled vehicles. The heuristic solution method we propose is based on a highway hierarchy-based shortest path algorithm for static large-scale networks; we maintain a static highway hierarchy and perform each query on the dynamically evaluated network, using a simple algorithm to propagate available dynamic traffic information over a larger part of the road network. We provide computational results that show the efficacy of our approach.     

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.     

Solving the minimum toll revenue problem in real transportation networks

As a means to relieve traffic congestion, toll pricing has recently received significant attention by transportation planners. Inappropriate use of transportation networks is one of the major causes of network congestion. Toll pricing is a method of traffic management in which traffic flow is guided to proper time and path in order to reduce the total delay in the network. This article investigates a method for solving the minimum toll revenue problem in real and large-scale transportation networks. The objective of this problem is to find link tolls that simultaneously cause users to efficiently use the transportation network and to minimize the total toll revenues to be collected. Although this model is linear, excessive number of variables and constraints make it very difficult to solve for large-scale networks. In this paper, a path-generation algorithm is proposed for solving the model. Implementation of this algorithm for different networks indicates that this method can achieve the optimal solution after a few iterations and a proper CPU time.     

Sensitivity Analysis Based Method for Optimal Road Network Pricing

Road pricing is an important economic measure for optimal management of transportation networks. The optimization objectives can be the total travel time or total cost incurred by all the travelers, or some other environmental objective such as minimum emission of dioxide, an so on. Suppose a certain toll is posed on some link on the network, this will give an impact on flows over the whole network and brings about a new equilibrium state. An equilibrium state is a state of traffic network at which no traveler could decrease the perceived travel cost by unilaterally changing the route. The aim of the toll setting is to achieve such an equilibrium state that a certain objective function is optimized. The problem can be formulated as a mathematical program with equilibrium constraints (MPEC). A key step for solving such a MPEC problem is the sensitivity analysis of traffic flows with respect to the change of link characteristics such as the toll prices. In this paper a sensitivity analysis based method is proposed for solving optimal road pricing problems.     

Solution approach to infinite linear programming problem with capacity constraints

The purpose of this article is to investigate a kind of infinite linear programming problem (ILPP) arising from infinite multiclass network equilibrium problems. In several cases, we construct special feasible solutions to the ILPP. By virtue of the nature of network, we prove that the solutions are optimal. Marcotte and Zhu (Oper Res Lett 37:211?C214, 2009) proved the existence of the valid tolls for the infinite multiclass network equilibrium problems. Based on this, we analyze the property of the tolls vector, i.e., the relationship between breakpoints and the tolls. We also consider the solutions in the network where origin-destination pairs may differ in their probability density functions.     

An N-path user equilibrium for transportation networks

The traditional trip-based approach to transportation modeling has been employed for the past decade. The last step of the trip-based modeling approach is traffic assignment, which has been typically formulated as a user equilibrium (UE) problem. In the conventional perspective, the definition of UE traffic assignment is the condition that no road user can unilaterally change routes to reduce their travel time. An equivalent definition is that the travel times of all the used paths between any given origin–destination pair are equal and less than those of the unused paths. The underlying assumption of the UE definition is that road users have full information on the available transportation paths and can potentially use any path if the currently used path is overly congested. However, a more practical scenario is that each road user has a limited path set within which she/he can choose routes from. In this new scenario, we call the resulting user equilibrium an N-path user equilibrium (NPUE), in which each road user has only N paths to select from when making route choices in the network. We introduce a new formulation of the NPUE and derive optimality conditions based on this formulation. Different from traditional modeling framework, the constraints of the proposed model are of linear form, which makes it possible to solve the problem with conventional convex programming techniques. We also show that the traditional UE is a special case of an NPUE and prove the uniqueness of the resulting flow pattern of the NPUE. To efficiently solve this problem, we devise path-based and link-based solution algorithms. The proposed solution algorithms are empirically applied to networks of various sizes to examine the impact of constrained user path sets. Numerical results demonstrate that NPUE results can differ significantly from UE results depending on the number of paths available to road users. In addition, we observed an interesting phenomenon, where increasing the number of paths available to road users can sometimes decrease the overall system performance due to their selfish routing behaviors. This paradox demonstrates that network information should be provided with caution, as such information can do more harm than good in certain transportation systems.     

Computation of the optimal tolls on the traffic network

The present paper is devoted to the computation of optimal tolls on a traffic network that is described as fuzzy bilevel optimization problem. As a fuzzy bilevel optimization problem we consider bilinear optimization problem with crisp upper level and fuzzy lower level. An effective algorithm for computation optimal tolls for the upper level decision-maker is developed under assumption that the lower level decision-maker chooses the optimal solution as well. The algorithm is based on the membership function approach. This algorithm provides us with a global optimal solution of the fuzzy bilevel optimization problem.     

加权马尔可夫模型在道路交通受伤人数预测中的应用

为提高交通事故预测的可靠性,首先应用有序聚类的方法建立交通受伤人数的分级标准;然后针对事故受伤人数为相依随机变量的特点,采取以规范化的各阶自相关系数为权重,用加权的马尔可夫链模型来预测未来交通事故受伤人数的升降变化状况;最后以北京市1970-2010年共41年的事故受伤人数为例对该方法进行了具体应用,取得了较为满意的结果,为交通事故受伤人数的预测分析提供了新的途径.     

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.     

ATIS和道路收费下的混合随机用户均衡的效率损失

在ATIS作用下的交通网络中,用户在交通信息的接受程度上是异质的;考虑到装有ATIS的用户并不总是遵循ATIS的建议,因此,引入信息遵从率这一参数,将所有用户分为三类:安装并遵从信息、安装但不遵从信息和不安装的用户;均按照随机用户均衡的方式进行择路,但对出行时间有不同的感知。同时考虑存在道路收费的情形下,用户在时间价值上是异质的。综合考虑交通信息与道路收费的影响,基于用户两方面的异质性,对其进行合理分类,构建了多用户多准则的混合随机均衡模型及其等价的变分不等式;当收费不作为系统总成本的一部分时,建立了时间准则与费用准则下的系统最优模型;在此基础之上,分别研究了两种准则下混合均衡相对于系统最优的效率损失,给出了效率损失上界,并进一步分析了效率损失上界与各参数间的关系;交通管理者可以从道路收费策略的实施、信息诱导系统的完善等角度进行路网的改造和优化设计。     

A modified Physarum-inspired model for the user equilibrium traffic assignment problem

The user equilibrium traffic assignment principle is very important in the traffic assignment problem. Mathematical programming models are designed to solve the user equilibrium problem in traditional algorithms. Recently, the Physarum shows the ability to address the user equilibrium and system optimization traffic assignment problems. However, the Physarum model are not efficient in real traffic networks with two-way traffic characteristics and multiple origin–destination pairs. In this article, a modified Physarum-inspired model for the user equilibrium problem is proposed. By decomposing traffic flux based on origin nodes, the traffic flux from different origin–destination pairs can be distinguished in the proposed model. The Physarum can obtain the equilibrium traffic flux when no shorter path can be discovered between each origin–destination pair. Finally, numerical examples demonstrate the rationality and convergence properties of the proposed model.