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.     

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.     

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.     

基于Stackelberg博弈的时变双层交通分配模型

提出一个时变双层交通分配模型,其中上层网络管理者设立了一个路段的最大排队长度,其目标是使由网络流和排队长度定义的总出行时间最小.目标函数在离散时段内以路段流量和排队长度作为决策变量,同时考虑不同类型的信号交叉口延误的影响.下层网络用户的反应依赖于上层管理者的决策,其选择是使自身感知阻抗最小的路径,服从一个基于成对组合Logit的路径选择模型,构成一个成对组合Logit的均衡分配问题.结合了交通分配和流传播方法,将其表示为一个均衡约束下的双层数学规划问题,形成了一个Stackelberg非合作博弈.使用遗传算法求解该双层规划问题,并采用实证分析来表现模型的特征和算法的计算表现.结果表明路径重叠、路段流量、路段排队长度等因素对网络均衡流分布均有显著影响.     

A hybrid approach for optimal design of signalized road network

For a signalized road network with expansions of link capacity, the maximum possible increase in travel demands is considered while total delays for travelers are minimized. Using the concept of reserve capacity of signal-controlled junctions, the problem of finding the maximum possible increase in travel demand and determining optimal link capacity expansions can be formulated as optimization programs. In this paper, we present a new solution approach for simultaneously solving the maximum increase in travel demands and minimizing total delays of travelers. A projected Quasi-Newton method is proposed to effectively solve this problem to the KKT points. Numerical computations and comparisons are made on real data signal-controlled networks where obtained results outperform traditional methods.     

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.     

Resource Constrained Shortest Path Problems in Path Planning for Fleet Management

In the management and control of a vehicle fleet on a road network, the problem arises of finding the best route in relation to the mission of the fleet and to the typology of freight or users. Sometimes the route has to be adapted not only to current traffic conditions, but also to the physical, geometric and functional attributes of the roads, related to their urban location and environmental characteristics. This problem is approached here through an extension of the classic Shortest Path problem, named Resource Constrained Shortest Path problem (RCSP), where the resources are related to the road link attributes, assumed as relevant to the specific planning problem. A classification scheme of these attributes is first proposed and RCSP is described and reviewed. Next, a General Resource Constrained Shortest Path problem (GRCSP) is defined, which can be found in all cases where it is necessary to plan, statically or dynamically, the path of a vehicle and to respect a set of constraints expressed in terms of parameters and indices associated with the roads on the network. For this general problem a model has been formulated and a Branch and Cut solution approach is proposed. Computational results obtained on test and real networks during the experimentation of a fleet with low emission vehicles are also given. This revised version was published online in August 2006 with corrections to the Cover Date.     

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.     

A Model for Evaluation of Transport Policies in Multimodal Networks with Road and Parking Capacity Constraints

This paper presents a model for evaluation of transport policies in multimodal networks with road and parking capacity constraints. The proposed model simultaneously considers choices of travelers on route, parking location and mode between auto and transit. In the proposed model, it is assumed that auto drivers make a simultaneous route and parking location choice in a user equilibrium manner, and the modal split between auto and transit follows a multinomial logit formulation. A mathematical programming model with capacity constraints on road link and parking facilities is proposed that generates optimality conditions equivalent to the requirements for multimodal network equilibrium. An augmented Lagrangian dual algorithm embedded by partial linearization approach is developed to solve the proposed model. Numerical results on two example networks are presented to illustrate the proposed methodology. The results show that the service level of transit, parking charges, road link and parking capacities, and addition of a new parking location may bring significant impacts on travelers’ behavior and network performance. In addition, transport policies may result in paradoxical phenomenon.     

Smoothing approach to Nash equilibrium formulations for a class of equilibrium problems with shared complementarity constraints

The equilibrium problem with equilibrium constraints (EPEC) can be looked on as a generalization of Nash equilibrium problem (NEP) and the mathematical program with equilibrium constraints (MPEC) whose constraints contain a parametric variational inequality or complementarity system. In this paper, we particularly consider a special class of EPECs where a common parametric P-matrix linear complementarity system is contained in all players?? strategy sets. After reformulating the EPEC as an equivalent nonsmooth NEP, we use a smoothing method to construct a sequence of smoothed NEPs that approximate the original problem. We consider two solution concepts, global Nash equilibrium and stationary Nash equilibrium, and establish some results about the convergence of approximate Nash equilibria. Moreover we show some illustrative numerical examples.     

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.     

Evolutionary Quasi-Variational Inequalities and the Dynamic Multiclass Network Equilibrium Problem

We give an existence result to a class of evolutionary quasi-variational inequalities with adaptive set of feasible solutions, where the adaptivity is modeled by solution-dependent equality constraints. A fundamental role will be played by the concept of Mosco convergence related to set-valued applications. Finally, we apply our achievements to the dynamic multiclass network equilibrium problem and provide a numerical example.     

Quasi-variational equilibrium models for network flow problems

We consider a formulation of a network equilibrium problem given by a suitable quasi-variational inequality where the feasible flows are supposed to be dependent on the equilibrium solution of the model. The Karush–Kuhn–Tucker optimality conditions for this quasi-variational inequality allow us to consider dual variables, associated with the constraints of the feasible set, which may receive interesting interpretations in terms of the network, extending the classic ones existing in the literature.     

Time-dependent discrete road network design with both tactical and strategic decisions

This paper aims to model and investigate the discrete urban road network design problem, using a multi-objective time-dependent decision-making approach. Given a base network made up with two-way links, candidate link expansion projects, and candidate link construction projects, the problem determines the optimal combination of one-way and two-way links, the optimal selection of capacity expansion projects, and the optimal lane allocations on two-way links over a dual time scale. The problem considers both the total travel time and the total CO emissions as the two objective function measures. The problem is modelled using a time-dependent approach that considers a planning horizon of multiple years and both morning and evening peaks. Under this approach, the model allows determining the sequence of link construction, the expansion projects over a predetermined planning horizon, the configuration of street orientations, and the lane allocations for morning and evening peaks in each year of the planning horizon. This model is formulated as a mixed-integer programming problem with mathematical equilibrium constraints. In this regard, two multi-objective metaheuristics, including a modified non-dominated sorting genetic algorithm (NSGA-II) and a multi-objective B-cell algorithm, are proposed to solve the above-mentioned problem. Computational results for various test networks are also presented in this paper.     

A simplified recurrent neural network for pseudoconvex optimization subject to linear equality constraints

In this paper, the optimization techniques for solving pseudoconvex optimization problems are investigated. A simplified recurrent neural network is proposed according to the optimization problem. We prove that the optimal solution of the optimization problem is just the equilibrium point of the neural network, and vice versa if the equilibrium point satisfies the linear constraints. The proposed neural network is proven to be globally stable in the sense of Lyapunov and convergent to an exact optimal solution of the optimization problem. A numerical simulation is given to illustrate the global convergence of the neural network. Applications in business and chemistry are given to demonstrate the effectiveness of the neural network.     

Vector network equilibrium problems with capacity constraints of arcs and nonlinear scalarization methods

In this paper, a vector network equilibrium problem with capacity constraints of arcs is studied. By virtue of Fan-Browder’ fixed point theorem, an existence result of a (weak) vector equilibrium flow is derived. By using nonlinear scalarization methods, some sufficient and necessary conditions for a weak vector equilibrium flow are obtained.     

A novel algorithm for area traffic capacity control with elastic travel demands

A non-linear area traffic control system with limited capacity is considered in this paper. Optimal signal settings and link capacity expansions can be determined while trip distribution and network flow are in equilibrium. This problem can be formulated as a non-linear mathematical program with equilibrium constraints. For the objective function a non-linear constrained optimization program for signal settings and link capacity expansion is determined. For the constraint set the elastic user equilibrium traffic assignment obeying Wardrop’s first principle can be formulated as a variational inequality. Since the constrained optimization problem is non-convex, only local optima can be obtained. In this paper, a novel algorithm using a non-smooth trust region approach is proposed. Numerical tests are performed using a real data city network and various example test networks in which the effectiveness and robustness of the proposed method are confirmed as compared to other well-known solution methods.     

二层供应链网络均衡模型的研究

利用均衡理论和二层规划理论来研究供应链网络均衡问题。针对供应链网络中上下层成员之间具有的Stackelberg博弈特征以及同层成员之间具有的非合作博弈特征,构建了二层供应链网络的均衡模型,该模型实际上一个均衡约束的二层规划问题。此外,为了使得供应链网络在整体上实现最优,本文还在模型中引入回收契约以协调供应链网络。最后,利用罚函数法对模型进行了求解,算例分析说明了模型的合理性和有效性。     

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.     

Optimality Conditions for Nonsmooth Equilibrium Problems via Hadamard Directional Derivative

In this paper, we consider a mathematical program with equilibrium constraints (MPEC) formulated as a mathematical program with complementarity constraints. We obtain necessary conditions of Fritz John (FJ) and Karush-Kuhn-Tucker (KKT) types for a nonsmooth (MPEC) problem in terms of the lower Hadamard directional derivative. In particular sufficient conditions for MPECs are given where the involved functions have pseudoconvex sublevel sets. The functions with pseudoconvex sublevel sets is a class of generalized convex functions that include quasiconvex functions.