基于路段元胞传输模型的动态用户最优配流问题

利用基于路段的元胞传输模型进行模拟, 给出了一种计算实际路段出行阻抗的方法, 并在此基础上构造了基于路段变量的动态用户最优变分不等式模型. 模型采用针对迄节点的路段变量, 在每一个小时段都能给出路段流入率、流出率、路段流量和实际路段阻抗, 为用户提供较为全面的诱导信息打下了较好的理论基础. 采用了修正投影算法来进行求解. 数值算例表明模型具有的实用性和优越性, 使道路交通流宏观模型与动态网络交通配流问题得到较好的结合.     

交叉口有交通信号控制时用户最优动态配流模型

针对智能交通系统（ＴＴＳ）基础上中主要基础理论之一的动态交通分配问题,在现有研究成果的基础上,提出了更接近真实路网的多起点多旋点交叉口设置有交通信号控制（Ｔｒａｆｆｉｃ Ｓｉｇｎａｌ Ｃｏｎｔｒｏｌ）时的动态配流模型,给出了对现有的通过Ｆｒａｎｋ Ｗｏｉｆｅ算法所得的ＤＵＯ配流解进行修正的原则,最后的算例表明由修正后的模型和算法所得到的ＤＵＯ配流解满足ＴＳＣ约束。     

Comparison of Methods for Path Flow Reassignment for Dynamic User Equilibrium

Models to describe or predict of time-varying traffic flows and travel times on road networks are usually referred to as dynamic traffic assignment (DTA) models or dynamic user equilibrium (DUE) models. The most common form of algorithms for DUE consists of iterating between two components namely dynamic network loading (DNL) and path inflow reassignment or route choice. The DNL components in these algorithms have been investigated in many papers but in comparison the path inflow reassignment component has been relatively neglected. In view of that, we investigate various methods for path inflow reassignment that have been used in the literature. We compare them numerically by embedding them in a DUE algorithm and applying the algorithm to solve DUE problems for various simple network scenarios. We find that the choice of inflow reassignment method makes a huge difference to the speed of convergence of the algorithms and, in particular, find that ??travel time responsive?? reassignment methods converge much faster than the other methods. We also investigate how speed of convergence is affected by the extent of congestion on the network, by higher demand or lower capacity. There appears to be much scope for further improving path inflow reassignment methods.     

Combined Activity/Travel Choice Models: Time-Dependent and Dynamic Versions

To fully understand and predict travel demand and traffic flow, it is necessary to investigate what drives people to travel. The analysis should examine why, where and when various activities are engaged in, and how activity engagement is related to the spatial and institutional organization of an urban area. In view of this, two combined activity/travel choice models are presented in this paper. The first one is a time-dependent (quasi-dynamic) model for long-term transport planning such as travel demand forecasting, while the other one is a dynamic model for short-term traffic management such as instantaneous flow analysis. The time-dependent model is formulated as a mathematical programming problem for modeling the multinomial logit activity/destination choice and the user equilibrium route choice behavior. It can further be converted to a variational inequality problem. On the other hand, the dynamic model is aimed to find a solution for equilibrium activity location, travel route and departure time choices in queuing networks with multiple commuter classes. It is formulated as a discrete-time, finite-dimensional variational inequality and then converted to an equivalent zero-extreme value minimization problem. Solution algorithms are proposed for these two models and numerical example is presented for the latter. It is shown that the proposed modeling approaches, either based on time-dependent or dynamic traffic assignment principles, provide powerful tools to a wide variety of activity/travel choice problems in dynamic domain.     

Linear Programming Models for the User and System Optimal Dynamic Network Design Problem: Formulations,Comparisons and Extensions

In this paper we formulate a network design model in which the traffic flows satisfy dynamic user equilibrium conditions for a single destination. The model presented here incorporates the Cell Transmission Model (CTM); a traffic flow model capable of capturing shockwaves and link spillovers. Comparisons are made between the properties of the Dynamic User equilibrium Network Design Problem (DUE NDP) and an existing Dynamic System Optimal (DSO) NDP formulation. Both network design models have different objective functions with similar constraint sets which are linear and convex. Numerical demonstrations are made on multiple networks to demonstrate the efficacy of the model and demonstrate important differences between the DUE and DSO NDP approaches. In addition, the flexibility of the approach is demonstrated by extending the formulation to account for demand uncertainty. This is formulated as a stochastic programming problem and initial test results are demonstrated on test networks. It is observed that not accounting for demand uncertainty explicitly, provides sub-optimal solution to the DUE NDP problem.     

基于Overlay Network的网格虚拟端到端带宽分配问题研究

提出了基于Overlay Network的服务网格（SGON）的概念,以此来生成和部署网络增值服务.带宽分配问题是在Overlay Grid上部署和运行增值服务的关键问题,为了解决这个问题,Overlay Grid在已存在的数据传输网络的上部建立了一个逻辑的端到端的服务传输基础,通过双边的服务水平协议（SLA）,提供QoS约束的带宽.给出了包含SLA、服务QoS、流量需求分布、开销等因素的带宽分配问题的模型,同时提供了静态和动态带宽分配问题的分析模型和近似解,最后设计了一种启发式自适应在线动态带宽分配算法.实验仿真结果表明,该算法是可行的.     

Study on continuous network design problem using simulated annealing and genetic algorithm

In general, a continuous network design problem (CNDP) is formulated as a bi-level program. The objective function at the upper level is defined as the total travel time on the network, plus total investment costs of link capacity expansions. The lower level problem is formulated as a certain traffic assignment model. It is well known that such bi-level program is non-convex and non-differentiable and algorithms for finding global optimal solutions are preferable to be used in solving it. Simulated annealing (SA) and genetic algorithm (GA) are two global methods and can then be used to determine the optimal solution of CNDP. Since application of SA and GA on continuous network design on real transportation network requires solving traffic assignment model many times at each iteration of the algorithm, computation time needed is tremendous. It is important to compare the efficacy of the two methods and choose the more efficient one as reference method in practice. In this paper, the continuous network design problem has been studied using SA and GA on a simulated network. The lower level program is formulated as user equilibrium traffic assignment model and Frank–Wolf method is used to solve it. It is found that when demand is large, SA is more efficient than GA in solving CNDP, and much more computational effort is needed for GA to achieve the same optimal solution as SA. However, when demand is light, GA can reach a more optimal solution at the expense of more computation time. It is also found that increasing the iteration number at each temperature in SA does not necessarily improve solution. The finding in this example is different from [Karoonsoontawong, A., & Waller, S. T. (2006). Dynamic continuous network design problem – Linear bilevel programming and metaheuristic approaches. Network Modeling 2006 Transportation Research Record (1964) (pp. 104–117)]. The reason might be the bi-level model in this example is nonlinear while the bi-level model in their study is linear.     

Optimization of a nonlinear area traffic control system with elastic demand

An area traffic control network system is considered in this paper. Optimal signal settings can be determined while trip rates and network flow are in equilibrium. This problem can be formulated as a nonlinear mathematical program with equilibrium constraints. For the objective function, the system performance can be defined as a function of signal setting variables. For the constraint set, a user equilibrium traffic assignment with elastic demand obeying Wardrop’s first principle is formulated as a variational inequality problem. Due to the nonlinearity and non-differentiability of the perturbed solutions in equilibrium constraints, a non-smooth approach is investigated in this paper. Numerical tests are performed using a variety of example road networks to quantify the effectiveness and robustness of the proposed method.     

Market signaling: An example of a two-person decision problem with dynamic information structure

An economic model of the job market is formulated as a two-person decision problem with dynamic information structure. The role of the decentralized information is investigated in terms of finding equilibrium solutions and properties of these solutions, such as stability, multiple solutions, and threshold effects of signaling cost and noise.     

多用户动态交通分配和信号优化的组合研究

提出了一种饱和路网中考虑多用户行为下的动态交通分配和交通信号优化的组合模型。模型采用广义双层规划来表示。模型的上层是信号控制优化,下层是考虑多用户路径选择条件下的动态交通分配,进行交通网络流的配置。同时,模型中采用具有物理排队的动态网络模型,从而考虑了饱和路网中物理排队对基于路段的网络条件的影响。通过仿真说明了饱和路网中考虑多用户行为下的动态交通分配和交通信号优化的组合模型可以实现交通信号的优化配置和交通网络流的优化,并反映了排队的物理效应。     

Symbolic-numerical methods for searching equilibrium states in a restricted four-body problem

Algorithms for searching equilibrium solutions of the circular restricted four-body problem formulated on the basis of the triangular Lagrange solutions of the three-body problem are discussed. An algorithm is proposed for calculating the bifurcation curve in the plane of system parameters that separates domains of the eight and ten equilibrium solutions. For the parameter values corresponding to the bifurcation curve, the system has nine equilibrium solutions. In the neighborhood of the bifurcation points, the equilibrium solutions are found in the form of power series in terms of a small parameter. The dependence of these solutions on the system parameters is studied numerically. Codes of algorithms implemented in the computer algebra system Mathematica are presented.     

Symbolic-numerical analysis of equilibrium solutions in a restricted four-body problem

Algorithms for searching equilibrium solutions of the circular restricted four-body problem formulated on the basis of triangular Lagrange solutions of the three-body problem are discussed. For small values of one of the two system parameters, equilibrium solutions are found in the form of power series. For large values of this parameter, an algorithm for numerical solution is presented. The proposed algorithms are implemented in the computer algebra system Mathematica.     

动态平衡运量配流问题及其稳态伴随解算法

动态平衡运量配流问题的建模和求解是发展智能车辆导驶系统的理论基础.本文对多起点单讫点交通网络建立了连续时间最优控制模型,该模型的最优解对应于动态用户平衡解.文中提出的稳态伴随解算法避免了解复杂的两点边界值问题,可以获得原问题的近似解.该算法利用了交通网络和计算机网络的结构特性,计算速度较高,可用于城市交通流的实时控制.     

Path Flow Estimator in an Entropy Model Using a Nonlinear L-Shaped Algorithm

The general problem of estimating origin-destination matrices in congested traffic networks is formulated as a mathematical program with equilibrium constraints. In this paper a path flow entropy model based on an equilibrium assignment approach is presented. It is assumed the flows on links are disaggregated due to some external reasons. Using the L-shaped algorithm the problem is transformed into a problem with less constraints. Then applying the lagrangian dual function the original problem is reduced to a nonlinear convex problem with only one linear constraint.     

Multicast Algorithms for Hypercube Multiprocessors

Depending on different switching technologies, the multicast communication problem has been formulated as three different graph theoretical problems: the Steiner tree problem, the multicast tree problem, and the multicast path problem. Our efforts in this paper are to reduce the communication traffic of multicast in hypercube multiprocessors. We propose three heuristic algorithms for the three problem models. Our multicast path algorithm is distributed, our Steiner tree algorithm is centralized, and our multicast tree algorithm is hybrid. Compared with the previous results by simulation, each of our heuristic algorithms improves the communication traffic in the corresponding multicast problem model.     

A Branch and Bound Algorithm for Bi-level Discrete Network Design Problem

Discrete network design problem (DNDP) is generally formulated as a bi-level programming. Because of non-convexity of bi-level formulation of DNDP which stems from the equilibrium conditions, finding global optimal solutions are very demanding. In this paper, a new branch and bound algorithm being able to find exact solution of the problem is presented. A lower bound for the upper-level objective and its computation method are developed. Numerical experiments show that our algorithm is superior to previous algorithms in terms of both computation time and solution quality. The conducted experiments indicate that in most cases the first incumbent solution which is obtained within a few seconds is superior to the final solution of some of previous algorithms.     

A framework for and empirical study of algorithms for traffic assignment

Traffic congestion is an issue in most cities worldwide. Transportation engineers and urban planners develop various traffic management projects in order to solve this issue. One way to evaluate such projects is traffic assignment (TA). The goal of TA is to predict the behaviour of road users for a given period of time (morning and evening peaks, for example). Once such a model is created, it can be used to analyse the usage of a road network and to predict the impact of implementing a potential project. The most commonly used TA model is known as user equilibrium, which is based on the assumption that all drivers minimise their travel time or generalised cost. In this study, we consider the static deterministic user equilibrium TA model.The constant growth of road networks and the need of highly precise solutions (required for select link analysis, network design, etc.) motivate researchers to propose numerous methods to solve this problem. Our study aims to provide a recommendation on what methods are more suitable depending on available computational resources, time and requirements on the solution. In order to achieve this goal, we implement a flexible software framework that maximises the usage of common code and, hence, ensures comparison of algorithms on common ground. In order to identify similarities and differences of the methods, we analyse groups of algorithms that are based on common principles. In addition, we implement and compare several different methods for solving sub-problems and discuss issues related to accumulated numerical errors that might occur when highly accurate solutions are required.     

Sub-optimal solutions to track detection problem using graph theoretic concepts

This paper demonstrates how the problem of tracking targets, which appear as either straight or curved lines in two-dimensional display images (or data images) can be formulated in terms of a directed weighted graph model and how dynamic programming techniques can be efficiently applied to reach an optimal or sub-optimal solution. In general, track detection algorithms providing optimal solutions have good detective ability, but most of them suffer from the inability to detect discontinuous lines or to resolve efficiently pairs of crossing lines. A sub-optimal solution is provided that efficiently overcomes these weaknesses. We focus on modeling the track detection problem in terms of a graph, formulating fast sequential/parallel sub-optimal track detection algorithms and testing them on simulated data in order to show their detective ability. Moreover, we specify the conditions under which sub-optimal algorithms can perform at least as well as their corresponding optimal algorithms. This is significant for the track detection problem where fast, accurate and real-time detection is considered a necessity.     

Two parameter tuned multi-objective evolutionary algorithms for a bi-objective vendor managed inventory model with trapezoidal fuzzy demand

This paper presents a bi-objective vendor managed inventory (BOVMI) model for a supply chain problem with a single vendor and multiple retailers, in which the demand is fuzzy and the vendor manages the retailers’ inventory in a central warehouse. The vendor confronts two constraints: number of orders and available budget. In this model, the fuzzy demand is formulated using trapezoidal fuzzy number (TrFN) where the centroid defuzzification method is employed to defuzzify fuzzy output functions. Minimizing both the total inventory cost and the warehouse space are the two objectives of the model. Since the proposed model is formulated into a bi-objective integer nonlinear programming (INLP) problem, the multi-objective evolutionary algorithm (MOEA) of non-dominated sorting genetic algorithm-II (NSGA-II) is developed to find Pareto front solutions. Besides, since there is no benchmark available in the literature to validate the solutions obtained, another MOEA, namely the non-dominated ranking genetic algorithms (NRGA), is developed to solve the problem as well. To improve the performances of both algorithms, their parameters are calibrated using the Taguchi method. Finally, conclusions are made and future research works are recommended.     

Hierarchical multiobjective routing in Multiprotocol Label Switching networks with two service classes: a heuristic solution

Modern multiservice network routing functionalities have to deal with multiple, heterogeneous and multifaceted Quality of Service (QoS) requirements. A heuristic approach devised to find "good" solutions to a hierarchical multiobjective alternative routing optimization problem in Multiprotocol Label Switching networks with two service classes (and different types of traffic flows in each class), namely QoS and Best Effort services, formulated within a hierarchical network-wide optimization framework, is presented. This heuristic solution is based on a bi-objective constrained shortest path model and is applied to a test network used in a benchmarking case study. An experimental study based on analytic and discrete event simulation results is presented, allowing for an assessment of the quality of results obtained with this new heuristic solution for various traffic matrices. A dynamic version of the routing method is formulated and its performance with the same case study network is analysed.