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.     

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.     

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

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

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.     

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

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

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

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

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.     

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.     

Optimal control of road freight flows by route choice inducement: A case from Mexico

Contrasting with much of the research in freight transportation around the impacts to transport operators, this work focuses on the Road Planner providing the infrastructure. This viewpoint, seeking minimal repair costs and other payments generally conflicts with the carriers’ view, looking for the best hauling route.On a random utility frame, the user-planner interaction is modelled on a partially tolled road network, considering two types of costs: (a) lorries’ trip cost guiding the route choice, and affected by planners’ actions, and (b) planners’ road repair costs, depending on the traffic, the vehicles’ type and the control implementation. A Monte Carlo simulation bases the stochastic assignment on the network, determining optimal subsidies that divert traffic to tolled roads. On a portion of the Mexican Paved network optimal subsidies are found, increasing the toll roads’ use and reducing traffic on the non-charged roads, generally having weaker pavements and higher maintenance costs.     

New formulations and valid inequalities for a bilevel pricing problem

Consider the problem of maximizing the toll revenue collected on a multi-commodity transportation network. This fits a bilevel framework where a leader sets tolls, while users respond by selecting cheapest paths to their destination. We propose novel formulations of the problem, together with valid inequalities yielding improved algorithms.     

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.     

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

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

Pricing and logit-based mode choice models of a transit and highway system with elastic demand

The objective of this paper is to enhance the insights into transport pricing mechanism and the corresponding mode choice behavior in a simple bi-modal transportation system with elastic demand. This system comprises a mass transit parallel to a bottleneck-constrained highway between a residential area and a workplace. We derive and compare three pricing schemes: the arbitrarily fixed pricing, the first-best pricing for a social optimum of the system, and the second-best pricing in the case of incapability of road toll. It is shown that the first-best pricing requires to implement a road toll and a transit fare simultaneously, and the optimal transit fare for the second-best solution should be set to be a weighted sum of the marginal external costs between auto and transit commuters. A numerical example is presented to illustrate how the pricing policies affect the demand implementation, the mode choice behavior and the efficiency of the whole transportation system.     

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.     

The single vehicle routing problem with toll-by-weight scheme: A branch-and-bound approach

Expressways in China make use of the toll-by-weight scheme, in which expressway tolls are collected based on the weight and traveling distance of the vehicle. Most vehicle routing models assume that the cost of traversing each edge is equivalent to edge length or some constant; as a result, such models cannot be practically applied to the Chinese expressway transportation system. This study addresses a new single vehicle routing problem that takes the vehicle’s (laden and unladen) weight into account. To solve this problem exactly, we provide a branch-and-bound algorithm with a provably valid lower bound measure, along with five dominance checkers for additional pruning. We analyze our algorithm using instances generated from standard TSP test cases, as well as two new sets of test cases based on real expressway information from the Gansu and Jiangxi provinces in China. The algorithm can be applied to any toll scheme in which the toll per unit distance monotonically increases with weight, even if the toll function is non-linear.     

Existence and computation of optimal tolls in multiclass network equilibrium problems

In this work we provide a simple proof of the existence of optimal tolls for multiclass network equilibrium problems where the value-of-time parameter varies continuously throughout the population. The main argument, based on a finite-dimensional reformulation of the problem, also allows us to determine in a simple fashion revenue minimizing link toll vectors.     

Models and algorithms for the 2-dimensional cell suppression problem in statistical disclosure control

Lagrangean dualization and subgradient optimization techniques are frequently used within the field of computational optimization for finding approximate solutions to large, structured optimization problems. The dual subgradient scheme does not automatically produce primal feasible solutions; there is an abundance of techniques for computing such solutions (via penalty functions, tangential approximation schemes, or the solution of auxiliary primal programs), all of which require a fair amount of computational effort. We consider a subgradient optimization scheme applied to a Lagrangean dual formulation of a convex program, and construct, at minor cost, an ergodic sequence of subproblem solutions which converges to the primal solution set. Numerical experiments performed on a traffic equilibrium assignment problem under road pricing show that the computation of the ergodic sequence results in a considerable improvement in the quality of the primal solutions obtained, compared to those generated in the basic subgradient scheme. Received February 11, 1997 / Revised version received June 19, 1998?Published online June 28, 1999     

基于畅通可靠性的开放小区交通流分配及优化决策

开放小区内部道路可增加城市道路网的密度和可达性,从而达到缓解城市道路拥堵的目的。通过对出行者进行问卷调查,得知其路径选择行为主要考虑出行时间及时间波动性两方面因素,基于此对CONTRAM费用函数进行改进,得到适用于小区开放后的广义出行费用,该费用考虑了畅通可靠性对路径选择的影响;结合小区开放后出行者选择准则,建立考虑广义出行费用的随机用户最优模型(SUO),并采用逐次平均算法(MSA)进行求解,从而得到更为精确的路段交通流量;基于小区道路开放后需承担的交通量,结合城市道路规划相关规范,对横断面、出入口等方面提出开放小区内部道路规划的建议。     

The auction algorithm for the transportation problem

The auction algorithm is a parallel relaxation method for solving the classical assignment problem. It resembles a competitive bidding process whereby unassigned persons bid simultaneously for objects, thereby raising their prices. Once all bids are in, objects are awarded to the highest bidder. This paper generalizes the auction algorithm to solve linear transportation problems. The idea is to convert the transportation problem into an assignment problem, and then to modify the auction algorithm to exploit the special structure of this problem. Computational results show that this modified version of the auction algorithm is very efficient for certain types of transportation problems.