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.     

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.     

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

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

A heuristic method for the minimum toll booth problem

This paper addresses the toll pricing problem in which the objective is to minimize the number of required toll facilities in a traffic network. The problem is shown to be NP-hard. To obtain a solution in a reasonable time, an effective metaheuristic algorithm is developed. The algorithm uses a local search technique in which the neighborhood function employs the dynamic slope scaling procedure to deal with the fixed charge nature of the objective function. Numerical results from 50 randomly generated and three real networks are reported.     

Using ACCPM in a simplicial decomposition algorithm for the traffic assignment problem

The purpose of the traffic assignment problem is to obtain a traffic flow pattern given a set of origin-destination travel demands and flow dependent link performance functions of a road network. In the general case, the traffic assignment problem can be formulated as a variational inequality, and several algorithms have been devised for its efficient solution. In this work we propose a new approach that combines two existing procedures: the master problem of a simplicial decomposition algorithm is solved through the analytic center cutting plane method. Four variants are considered for solving the master problem. The third and fourth ones, which heuristically compute an appropriate initial point, provided the best results. The computational experience reported in the solution of real large-scale diagonal and difficult asymmetric problems—including a subset of the transportation networks of Madrid and Barcelona—show the effectiveness of the approach.     

出行量预测不确定下基于灵敏度分析的拥挤收费定价模型

拥挤收费是改善城市交通的有效手段.对拥挤收费定价的研究方法之一,就是针对固定的出行量进行收费设计.由于出行量预测不确定的因素,应针对长期出行量预测不确定的情况,利用灵敏度分析的方法,对拥挤收费定价的问题进行研究.首先研究了出行者出行的广义费用,然后考虑出行者的出行决策及出行量预测不确定的因素,给出一个拥挤收费定价模型,为交通管理者提供理论依据.     

An MPEC approach to second-best toll pricing

This paper addresses two second-best toll pricing problems, one with fixed and the other with elastic travel demands, as mathematical programs with equilibrium constraints. Several equivalent nonlinear programming formulations for the two problems are discussed. One formulation leads to properties that are of interest to transportation economists. Another produces an algorithm that is capable of solving large problems and easy to implement with existing software for linear and nonlinear programming problems. Numerical results using transportation networks from the literature are also presented.This research was partially supported by NSF grants DMI-9978642 and DMI-0300316.     

Simultaneously optimizing link tolls and signal settings in a road network

The problem of determining link tolls to reduce traffic congestion is often referred as a toll design problem. In this paper, optimal tolls are determined for signal-controlled junctions in urban traffic road networks where the rerouting traffic is properly taken into account. This problem can be formulated as a mathematical program with equilibrium constraints (MPEC) where the user equilibrium is expressed as a variational inequality problem. Due to the non-differentiability of the equilibrium problem, an efficient convergent solution scheme is established. Numerical calculations are conducted on a variety of example road networks and comparisons are made with earlier methods.     

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.     

结点有约束的交通网络最短路径模型

结点有约束的网络是一类特殊的网络，如具有禁止通行限制信息的交通路网等，由于最短路径的求解是有后效性的，经典的Dijkstra算法等不能直接用来求解该问题，本文提出了一种结点有约束的交通网络最短路径建模方法，该方法所建模型为一般网络模型，可用任一传统高效的算法求其最短路径，从根本上降低了问题的复杂性，为很好地解决交通、通信等领域中的此类问题提供了有益的方法。     

Highway toll pricing

For a tolled highway where consecutive segments allow vehicles to enter and exit unrestrictedly, we propose a simple toll pricing method. It is shown that the method is the unique method satisfying the classical axioms of Additivity and Dummy in the cost sharing literature, and the axioms of Toll Upper Bound for Local Traffic and Routing-proofness. We also show that the toll pricing method is the only method satisfying Routing-proofness Axiom and Cost Recovery Axiom. The main axiom in the characterizations is Routing-proofness which says that no vehicle can reduce its toll charges by exiting and re-entering intermediately. In the special case when there is only one unit of traffic (vehicle) for each (feasible) pair of entrance and exit, we show that our toll pricing method is the Shapley value of an associated game to the problem. In the case when there is one unit of traffic entering at each entrance but they all exit at the last exit, our toll pricing method coincides with the well-known airport landing fee solution-the Sequential Equal Contribution rule of Littlechild and Owen (1973).     

An algorithm for local continuous optimization of traffic signals

In this paper, an algorithm for sensitivity analysis for equilibrium traffic network flows with link interferences is proposed. Based on this sensitivity analysis algorithm, a general algorithm is provided for solving the optimal design and management problems for traffic networks. In particular, this algorithm is applied to the optimal traffic signal setting problem. A numerical example is given to demonstrate the effectiveness of our algorithm.     

Pavement rehabilitation scheduling and toll pricing under different regulatory regimes

This paper addresses the highway pavement rehabilitation scheduling and toll pricing issues over a planning horizon. In the highway system concerned, two types of agents are considered, namely highway operator and road users. Two models, which account for different highway regulatory regimes (i.e. public and private), are proposed. In the public regulatory model, the government aims to maximize total discounted social welfare of the transportation system over the planning horizon by determining the optimal pavement rehabilitation schedule and toll level. In the private regulatory regime, a profit-driven private operator seeks to optimize the pavement rehabilitation schedule and toll level to maximize its own discounted net profit over the planning horizon. The proposed models treat the interactions between the highway operator and the road users in the system as a bi-level hierarchical problem in which the upper level is a multi-period pavement rehabilitation scheduling and toll pricing problem, while the lower level is a multi-period route choice equilibrium problem. A heuristic solution algorithm that combines a greedy approach and a sensitivity analysis based approach is developed to solve the proposed bi-level multi-period optimization models. An illustrative example is used to show the applications of the proposed models. The findings show that the highway regulatory regime, pavement deterioration parameter and the roughness-induced vehicle operating cost can significantly affect the pavement rehabilitation schedules and the toll level as well as the performance of transportation system in terms of total life-cycle travel demand, net profit and social welfare.     

Solving the bicriteria traffic equilibrium problem with variable demand and nonlinear path costs

In this paper, we present an algorithm for solving the bicriteria traffic equilibrium problem with variable demand and nonlinear path costs. The path cost function considered is comprised of two attributes, travel time and toll, that are combined into a nonlinear generalized cost. Travel demand is determined endogenously according to a travel disutility function. Travelers choose routes with the minimum overall generalized costs. The algorithm involves two components: a bicriteria shortest path routine to implicitly generate the set of non-dominated paths and a projection and contraction method to solve the nonlinear complementarity problem (NCP) describing the traffic equilibrium problem. Numerical experiments are conducted to demonstrate the feasibility of the algorithm to this class of traffic equilibrium problems.     

平衡和不平衡运输问题与分配问题的通用迭代算法

将不平衡运输问题转化成网络最短路问题,利用Floyd算法规则,给出了一种既可以解平衡和不平衡运输问题,又可以解平衡和不平衡分配问题的通用迭代算法。与专门用于解运输问题的闭合回路法和专门用于解分配问题的匈牙利法相比,这种算法不但具有通用的优点,而且更便于在计算机上运行。     

Parking Capacity and Pricing in Park'n Ride Trips: A Continuous Equilibrium Network Design Problem

In this paper we consider the problem of designing parking facilities for park'n ride trips. We present a new continuous equilibrium network design problem to decide the capacity and fare of these parking lots at a tactical level. We assume that the parking facilities have already been located and other topological decisions have already been taken.The modeling approach proposed is mathematical programming with equilibrium constraints. In the outer optimization problem, a central Authority evaluates the performance of the transport network for each network design decision. In the inner problem a multimodal traffic assignment with combined modes, formulated as a variational inequality problem, generates the share demand for modes of transportation, and for parking facilities as a function of the design variables of the parking lots. The objective is to make optimal parking investment and pricing decisions in order to minimize the total travel cost in a subnetwork of the multimodal transportation system.We present a new development in model formulation based on the use of generalized parking link cost as a design variable.The bilevel model is solved by a simulated annealing algorithm applied to the continuous and non-negative design decision variables. Numerical tests are reported in order to illustrate the use of the model, and the ability of the approach to solve applications of moderate size.     

Rate control for communication networks: shadow prices,proportional fairness and stability

This paper analyses the stability and fairness of two classes of rate control algorithm for communication networks. The algorithms provide natural generalisations to large-scale networks of simple additive increase/multiplicative decrease schemes, and are shown to be stable about a system optimum characterised by a proportional fairness criterion. Stability is established by showing that, with an appropriate formulation of the overall optimisation problem, the network's implicit objective function provides a Lyapunov function for the dynamical system defined by the rate control algorithm. The network's optimisation problem may be cast in primal or dual form: this leads naturally to two classes of algorithm, which may be interpreted in terms of either congestion indication feedback signals or explicit rates based on shadow prices. Both classes of algorithm may be generalised to include routing control, and provide natural implementations of proportionally fair pricing.     

Multimodal K-shortest viable path problem in Tehran public transportation network and its solution applying ant colony and simulated annealing algorithms

This paper treats with K-shortest viable path problem in a transportation network including multiple modes. The considered modes are metro, rapid-bus, private and walking. In this network, a viable path is one that the number of mode changes is limited and the traverse time and also the walking, metro and private usage are restricted subjected to some constraints. The traverse time is defined dependent on congestion level. Because constrained shortest path is NP-hard, we extend two metaheuristic algorithms namely GASA and BACS for the given problem. GASA is a Greedy Algorithm Simulated Annealing and BACS is a bi-direction searching Ant Colony System made by two colonies of ants. We evaluate the validation of these algorithms applying several multimodal random networks. In addition, their results are compared with CPLEX 12.1. We find that GASA is appropriate for small networks and BACS has better performance in median and large-scale networks. Our results on Tehran network also demonstrate that BACS provides better objective values than BACS ones because Tehran public transportation is sparse.     

Optimum synthesis of discrete capacitated networks with multi-terminal commodity flow requirements

Network design problems arise in a wide range of applied areas including telecommunications, computer networks, and transportation. In this paper, we address the following discrete capacitated multi-terminal network design problem. Given a connected digraph G = (V,A), a set of L potential facilities to be installed on each arc, and a set of K multi-terminal (non-simultaneous) commodity flow requirements, the problem is to find a set of facilities to install in order to route the K nonsimultaneous flows while minimizing the total fixed plus variable costs. We describe an exact procedure for solving this problem based on Benders decomposition. Our algorithm includes several features that significantly improve the efficiency of the basic approach. Computational results attest to the efficacy of the proposed algorithm, which can solve medium- to large-scale problems to optimality.     

Development of the tree-based link labeling algorithm for optimal path-finding in urban transportation networks

The optimal path-finding algorithm which is an important module in developing route guidance systems and traffic control systems has to provide correct paths to consider U-turns, P-turns, and no-left-turns in urban transportation networks.Traditional methods which have been used to consider those regulations on urban transportation networks can be categorized into network representation and algorithmic methods like the vine-building algorithm. First, network representation methods use traditional optimal path-finding algorithms with modifications to the network structure: for example, just adding dummy nodes and links to the existing network allows constraint-search in the network. This method which creates large networks is hard to implement and introduces considerable difficulties in network coding. With the increased number of nodes and links, the memory requirement tremendously increases, which causes the processing speed to slow down. For these reasons, the method has not been widely accepted for incorporating turning regulations in optimal path-finding problems in transportation networks. Second, algorithmic methods, as they are mainly based on the vine-building algorithm, have been suggested for determining optimal path for networks with turn penalties and prohibitions. However, the algorithms, although they nicely reflect the characteristics of urban transportation networks, frequently provide infeasible or suboptimal solutions.The algorithm to be suggested in this research is a method which is basically based on Dijkstra's algorithm [1] and the tree-building algorithm used to construct optimal paths. Unlike the traditional node labeling algorithms which label each node with minimum estimated cost, this algorithm labels each link with minimum estimated cost.Comparison with the vine-building algorithm shows that the solution of the link-labeling algorithm is better than that of the vine-building algorithm which very frequently provides suboptimal solutions. As a result, the algorithm allows turning regulations, while providing an optimal solution within a reasonable time limit.