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.     

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.     

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.     

Doubly uncertain transportation network: Degradable capacity and stochastic demand

This study developed a methodology to model doubly uncertain transportation network with stochastic link capacity degradation and stochastic demand. We consider that the total travel demand comprises of two parts, infrequent travelers and commuters. The traffic volume of infrequent travelers is stochastic, which adds to the network traffic in a random manner based on fixed route choice proportions. On the other hand, the traffic volume of commuters is stable or deterministic. Commuters acquire the network travel time variability from past experiences, factor them into their route choice considerations, and settle into a long-term habitual route choice equilibrium in which they have no incentive of switching away. To define this equilibrium, we introduce the notion of “travel time budget” to relate commuters’ risk aversion on route choices in the presence of travel time variability. The travel time budget varies among commuters according to their degrees of risk aversion and requirements on punctual arrivals. We then developed a mixed-equilibrium formulation to capture these stochastic considerations and illustrated its properties through some numerical studies.     

An MPEC formulation and its cutting constraint algorithm for continuous network design problem with multi-user classes

Continuous network design problem (CNDP) is to determine the set of link capacity expansions and the corresponding equilibrium flows for which the measures of performance index for the network is optimal. Conventionally, CNDP assumed users to be homogeneous, that is, all travelers on the same link of the network are identical insofar as congestion effect and they have the same value of time (VOT). In fact, it does not accord with the real situation that all have the same VOT. So, multiple user classes with different VOT should be considered. This paper examines the CNDP with different VOT for multiple user classes, which is generally expressed as a mathematical programming with equilibrium constraint (MPEC). Then, the cut constraint algorithm (CCA) is presented to solve the problem. The numerical experiments on the examples from the literature are illustrated to demonstrate that our model and algorithm are feasible.     

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.     

Traffic assignment model with fuzzy level of travel demand: An efficient algorithm based on quasi-Logit formulas

The place of fuzzy concepts in traffic assignment (TA) models has been studied in recent literature. Keeping fuzzy level of travel demand in mind, we propose a new TA model in which the travel costs of links are depended on their congestion. From the results of such fuzzy TA model, network planners are able to estimate the number of travelers on network links. By using zero–one variables, the proposed model is transformed into a crisp mixed-integer problem with respect to path-flow variables. In order to produce the Logit flows from this problem, Damberg et al. algorithm is modified. Then, the level of certainty is maximized and perceived travel delays are minimized. For a fixed certainty degree, the obtained solution, which is named the fuzzy equilibrium flow, satisfies a quasi-Logit formula similar to ordinary expression of the Logit route choice model. Eventually, we examine the quality of different path enumeration techniques in the proposed model.     

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.     

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

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

路段容量约束弹性需求交通均衡分配近似算法

本文研究了带路段容量约束弹性需求用户均衡交通分配问题及其近似解法.采用超需求模型将弹性需求转化为固定需求,提出了一种带路段容量约束弹性需求用户均衡交通分配近似算法.该算法在迭代过程中,通过不断自适应调节排队延误因子、误差因子来近似真实路段行驶时间,使路段流量逐步满足约束条件,最终达到广义用户均衡.这种方法克服了容量约束弹性需求用户均衡分配计算量大及随机分配法要求枚举所有路径的困难.随后证明了算法的收敛性,并对一个小型路网进行了数值试验.     

On the Single-Source Unsplittable Flow Problem

be a capacitated directed graph with a source s and k terminals with demands , . We would like to concurrently route every demand on a single path from s to the corresponding terminal without violating the capacities. There are several interesting and important variations of this unsplittable flow problem. If the necessary cut condition is satisfied, we show how to compute an unsplittable flow satisfying the demands such that the total flow through any edge exceeds its capacity by at most the maximum demand. For graphs in which all capacities are at least the maximum demand, we therefore obtain an unsplittable flow with congestion at most 2, and this result is best possible. Furthermore, we show that all demands can be routed unsplittably in 5 rounds, i.e., all demands can be collectively satisfied by the union of 5 unsplittable flows. Finally, we show that 22.6% of the total demand can be satisfied unsplittably. These results are extended to the case when the cut condition is not necessarily satisfied. We derive a 2-approximation algorithm for congestion, a 5-approximation algorithm for the number of rounds and a -approximation algorithm for the maximum routable demand. Received: July 12, 1998     

Survivable capacitated network design problem: new formulation and Lagrangean relaxation

This work is focused on the analysis of the survivable capacitated network design problem. This problem can be stated as follows: Given a supply network with point-to-point traffic demands, specific survivability requirements, a set of available capacity ranges and their corresponding discrete costs for each arc, find minimum cost capacity expansions such that these demands can be met even if a network component fails. Solving this problem consists of selecting the links and their capacity, as well as the routings for each demand in every failure situation. This type of problem can be shown to be NP-hard. A new linear mixed-integer mathematical programming formulation is presented. An effective solution procedure based on Lagrangean relaxation is developed. Comparison heuristics and improvement heuristics are also described. Computational results using these procedures on different sizes of randomly generated networks are reported.     

Robust vehicle routing problem with deadlines and travel time/demand uncertainty

In this article, we investigate the vehicle routing problem with deadlines, whose goal is to satisfy the requirements of a given number of customers with minimum travel distances while respecting both of the deadlines of the customers and vehicle capacity. It is assumed that the travel time between any two customers and the demands of the customer are uncertain. Two types of uncertainty sets with adjustable parameters are considered for the possible realizations of travel time and demand. The robustness of a solution against the uncertain data can be achieved by making the solution feasible for any travel time and demand defined in the uncertainty sets. We propose a Dantzig-Wolfe decomposition approach, which enables the uncertainty of the data to be encapsulated in the column generation subproblem. A dynamic programming algorithm is proposed to solve the subproblem with data uncertainty. The results of computational experiments involving two well-known test problems show that the robustness of the solution can be greatly improved.     

双模式网络停车限制交通需求管理模型与方法研究

在轨道网和公路网并存的双模式交通网络, 合理设计出行终点的停车容量可优化汽车出行需求, 改善路网交通环境。本文通过分析私家车与城市轨道两种交通模式的出行需求, 并考虑私家车模式的终点停车收费服务, 建立了一种带路段环境容量和终点停车需求容量共同约束的交通需求管理模型。模型中路网使用者的出行模式采用二元Logit模型来计算, 而私家车的路线选择行为服从Logit随机用户均衡, 因此该模型是一个带不动点约束的数学规划问题。针对模型求解困难, 文中采用灵敏度分析来获取各路段流量和需求量关于终点容量波动的梯度信息, 进而设计了一种新的灵敏度分析求解算法.最后通过数值仿真实验, 验证了算法的有效性, 同时分析了不同停车收费参数对模型各指标变化趋势的影响。     

A worst-case analysis for the split delivery vehicle routing problem with minimum delivery amounts

In the vehicle routing problem (VRP), a fleet of vehicles must service the demands of customers in a least-cost way. In the split delivery vehicle routing problem (SDVRP), multiple vehicles can service the same customer by splitting the deliveries. By allowing split deliveries, savings in travel costs of up to 50 % are possible, and this bound is tight. Recently, a variant of the SDVRP, the split delivery vehicle routing problem with minimum delivery amounts (SDVRP-MDA), has been introduced. In the SDVRP-MDA, split deliveries are allowed only if at least a minimum fraction of a customer’s demand is delivered by each visiting vehicle. We perform a worst-case analysis on the SDVRP-MDA to determine tight bounds on the maximum possible savings.     

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.     

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 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.     

A continuous whole-link travel time model with occupancy constraint

The continuous dynamic network loading problem (CDNLP) aims to compute link travel times and path travel times on a congested network, given time-dependent path flow rates for a given time period. A crucial element of CDNLP is a model of the link performance. Two main modeling frameworks have been used in link loading models: The so-called whole-link travel time (WTT) models and the kinematic wave model of Lighthill–Whitham–Richards (LWR) for traffic flow.In this paper, we reformulate a well-known whole-link model in which the link travel time, for traffic entering a time t, is a function of the number of vehicles on link. This formulation does not require the satisfying of the FIFO (first in, first out) condition. An extension of the basic WTT model is proposed in order to take explicitly into account the maximum number of vehicles that the link can accommodate (occupancy constraint). A solution scheme for the proposed WTT model is derived.Several numerical examples are given to illustrate that the FIFO condition is not respected for the WTT model and to compare the travel time predictions effected by LWR and WTT models.     

Heuristics for Distribution Network Design in Telecommunication

A distribution network problem arises in a lower level of an hierarchical modeling approach for telecommunication network planning. This paper describes a model and proposes a lagrangian heuristic for designing a distribution network. Our model is a complex extension of a capacitated single commodity network design problem. We are given a network containing a set of sources with maximum available supply, a set of sinks with required demands, and a set of transshipment points. We need to install adequate capacities on the arcs to route the required flow to each sink, that may be an intermediate or a terminal node of an arborescence. Capacity can only be installed in discrete levels, i.e., cables are available only in certain standard capacities. Economies of scale induce the use of a unique higher capacity cable instead of an equivalent set of lower capacity cables to cover the flow requirements of any link. A path from a source to a terminal node requires a lower flow in the measure that we are closer to the terminal node, since many nodes in the path may be intermediate sinks. On the other hand, the reduction of cable capacity levels across any path is inhibited by splicing costs. The objective is to minimize the total cost of the network, given by the sum of the arc capacity (cables) costs plus the splicing costs along the nodes. In addition to the limited supply and the node demand requirements, the model incorporates constraints on the number of cables installed on each edge and the maximum number of splices at each node. The model is a NP-hard combinatorial optimization problem because it is an extension of the Steiner problem in graphs. Moreover, the discrete levels of cable capacity and the need to consider splicing costs increase the complexity of the problem. We include some computational results of the lagrangian heuristics that works well in the practice of computer aided distribution network design.