Models and algorithms for the optimization of signal settings on urban networks with stochastic assignment models

In this paper models and algorithms for the optimization of signal settings on urban networks are proposed. Two different approaches to the solution of the problem may be identified: a global approach (optimization of intersection signal settings on the whole network) and a local approach (optimization of signal settings intersection by intersection). For each approach a different optimization model and some solution algorithms are proposed; both models and algorithms are based on the assumptions of within-day static system and stochastic user equilibrium assignment models. The paper includes numerical results on test networks and a comparison between the two approaches.     

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.     

A meta-heuristic approach for solving the Urban Network Design Problem

This paper proposes an optimisation model and a meta-heuristic algorithm for solving the urban network design problem. The problem consists in optimising the layout of an urban road network by designing directions of existing roads and signal settings at intersections. A non-linear constrained optimisation model for solving this problem is formulated, adopting a bi-level approach in order to reduce the complexity of solution methods and the computation times. A Scatter Search algorithm based on a random descent method is proposed and tested on a real dimension network. Initial results show that the proposed approach allows local optimal solutions to be obtained in reasonable computation times.     

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 Multi-Class Dynamic User Equilibrium Model for Queuing Networks with Advanced Traveler Information Systems

This paper presents a formulation and solution algorithm for a composite dynamic user-equilibrium assignment problem with multi-user classes, in order to assess the impacts of Advanced Traveler Information Systems (ATIS) in general networks with queues. Suppose that users equipped with ATIS will receive complete information and hence be able to choose the best departure times and routes in a deterministic manner, while users not equipped with ATIS will have incomplete information and hence may make decisions on departure times and routes in a stochastic manner. This paper proposes a discrete-time, finite-dimensional variational inequality formulation that involves two criteria regarding the route and departure time choice behaviors, i.e., the deterministic dynamic user equilibrium and the nested logit-based stochastic dynamic user equilibrium. The formulation is then converted to an equivalent “zero-extreme value” minimization problem. A heuristic algorithm based on route/time-swapping process is proposed, which iteratively adjusts the route and departure time choices to reach closely to an extreme point of the minimization problem. A numerical example is used to demonstrate the effectiveness of the proposed approach for assessing the ATIS impacts such as changes in individual travel costs, departure times, route inflows, queuing peaks and total network travel cost. This revised version was published online in July 2006 with corrections to the Cover Date.     

An Ant Colony Optimization Algorithm for the Minimum Weight Vertex Cover Problem

Given an undirected graph and a weighting function defined on the vertex set, the minimum weight vertex cover problem is to find a vertex subset whose total weight is minimum subject to the premise that the selected vertices cover all edges in the graph. In this paper, we introduce a meta-heuristic based upon the Ant Colony Optimization (ACO) approach, to find approximate solutions to the minimum weight vertex cover problem. In the literature, the ACO approach has been successfully applied to several well-known combinatorial optimization problems whose solutions might be in the form of paths on the associated graphs. A solution to the minimum weight vertex cover problem however needs not to constitute a path. The ACO algorithm proposed in this paper incorporates several new features so as to select vertices out of the vertex set whereas the total weight can be minimized as much as possible. Computational experiments are designed and conducted to study the performance of our proposed approach. Numerical results evince that the ACO algorithm demonstrates significant effectiveness and robustness in solving the minimum weight vertex cover problem.     

Estimation of Transit Origin–Destination Matrices from Passenger Counts Using a Frequency-Based Approach

This paper investigates the transit passenger origin–destination (O–D) estimation problem in congested transit networks where updated passenger counts and outdated O–D matrices are available. The bi-level programming approach is used for the transit passenger O–D estimation problem. The upper level minimizes the sum of error measurements in passenger counts and O–D matrices, and the lower level is a new frequency-based stochastic user equilibrium (SUE) assignment model that can determine simultaneously the passenger overload delays and passenger route choices in congested transit network together with the resultant transit line frequencies. The lower-level problem can be formulated as either a logit-type or probit-type SUE transit assignment problem. A heuristic solution algorithm is developed for solving the proposed bi-level programming model which is applicable to congested transit networks. Finally, a case study on a simplified transit network connecting Kowloon urban area and the Hong Kong International Airport is provided to illustrate the applications of the proposed bi-level programming model and solution algorithm. This revised version was published online in July 2006 with corrections to the Cover Date.     

Optimal cycle for a signalized intersection using Global Optimization and Complementarity

A queueing system resulting from a signalised intersection regulated by pre-timed control in an urban traffic network is considered in this paper. Subsequently, we analyse the manner in which Global Optimisation and Complementarity may be used to determine the optimal cycle length and green split allocation for an isolated signalised intersection. The model in question has been formulated as a Mathematical Program with Equilibrium (or Complementarity) Constraints (MPEC). A?sequential complementarity algorithm for computing a global minimum for the MPEC is also subject to analysis in this paper. Furthermore, computational experience is included to demonstrate the efficiency of this method as an effective solution for the problem in question.     

Heuristics for urban road network design: Lane layout and signal settings

This paper concerns the urban road network design problem. In urban areas supply has usually been unable to keep pace with increasing demand: the only possibility is often to reorganise the current supply configuration in order to use existing resources efficiently. Thus, in urban areas signal settings and network topology (in particular lane layout) are the two major factors that can be handled by design models. Methods for the combined design of signal settings and topology are proposed in this paper. All the methods proceed in two stages: the first deals with integer variables (topology), while the second deals with continuous variables (signal settings). Some metaheuristics (Hill Climbing, Simulated Annealing, Tabu Search, Genetic Algorithms and Path Relinking) are specified for the topology design stage, and they are used singularly or jointly. The continuous part of the solution, with fixed topology is optimized through an algorithm for asymmetrical deterministic equilibrium assignment. This paper focuses on evaluating performances obtained by all the different algorithms proposed for the topology design stage. The algorithms are compared by applications to real networks, and some conclusions are drawn about their efficiency.     

Turning restriction design in traffic networks with a budget constraint

The restriction (prohibition) of certain turns at intersections is a very common task employed by the managers of urban traffic networks. Surprisingly, this approach has received little attention in the research literature. The turning restriction design problem (TRDP) involves finding a set of turning restrictions at intersections to promote flow in a congested urban traffic network. This article uses a successive linear approximation (SLA) method for identifying approximate solutions to a nonlinear model of the TRDP. It aims to adjust the current turning restriction regime in a given network in order to minimize total user travel cost when route choice is driven by user equilibrium principles. Novel features of the method include the facts that it is based on link capacity-based arc travel costs and there is a budget constraint on the total cost of all turning restriction alterations. It has been tested using standard network examples from the literature. One of the tests utilized a multi-start approach which improved the solutions produced by the SLA method. The method was also employed to identify turning restrictions for an actual medium-sized urban traffic network in Brazil. Computational experience with the proposed method is promising.     

Optimal infrastructure design and expansion of broadband wireless access networks

This paper investigates the important infrastructure design and expansion problem for broadband wireless access networks subject to user demand constraints and system capacity constraints. For the problem, an integer program is derived and a heuristic solution procedure is proposed based on Lagrangean relaxation. In the computational experiments, our Lagrangean relaxation based algorithm can solve this complex design and expansion problem quickly and near optimally. Based on the test results, it is suggested that the proposed algorithm may be practically used for the infrastructure design and expansion problem for broadband wireless access networks.     

Concave minimum cost network flow problems solved with a colony of ants

In this work we address the Single-Source Uncapacitated Minimum Cost Network Flow Problem with concave cost functions. This problem is NP-Hard, therefore we propose a hybrid heuristic to solve it. Our goal is not only to apply an ant colony optimization (ACO) algorithm to such a problem, but also to provide an insight on the behaviour of the parameters in the performance of the algorithm. The performance of the ACO algorithm is improved with the hybridization of a local search (LS) procedure. The core ACO procedure is used to mainly deal with the exploration of the search space, while the LS is incorporated to further cope with the exploitation of the best solutions found. The method we have developed has proven to be very efficient while solving both small and large size problem instances. The problems we have used to test the algorithm were previously solved by other authors using other population based heuristics. Our algorithm was able to improve upon some of their results in terms of solution quality, proving that the HACO algorithm is a very good alternative approach to solve these problems. In addition, our algorithm is substantially faster at achieving these improved solutions. Furthermore, the magnitude of the reduction of the computational requirements grows with problem size.     

考虑路网可靠性和空间公平性的次优拥挤收费模型

根据随机路网环境下出行者规避风险的路径选择行为,提出了一种考虑路网可靠性和空间公平性的次优拥挤收费双层规划模型。其中,上层模型以具有空间公平性约束条件下最大化路网的社会福利为目标,下层模型是实施拥挤收费条件下考虑行程时间可靠性的弹性需求用户平衡模型。鉴于双层规划模型的复杂性,设计了基于遗传算法和FrankWolfe算法的组合式算法来求解提出的模型。算例结果表明:考虑行程时间可靠性的次优拥挤收费会产生不同于传统次优拥挤收费的平衡流量分布模式,表明出行者的路径选择行为对拥挤收费结果会产生直接影响;此外,算例结果还说明遗传算法对参数设置具有很强的鲁棒性。     

A turning restriction design problem in urban road networks

Turning restriction is one of the commonest traffic management techniques and an effective low cost traffic improvement strategy in urban road networks. However, the literature has not paid much attention to the turning restriction design problem (TRDP), which aims to determine a set of intersections where turning restrictions should be implemented. In this paper, a bi-level programming model is proposed to formulate the TRDP. The upper level problem is to minimize the total travel cost from the viewpoint of traffic managers, and the lower level problem is to depict travelers’ route choice behavior based on stochastic user equilibrium (SUE) theory. We propose a branch and bound method (BBM), based on the sensitivity analysis algorithm (SAA), to find the optimal turning restriction strategy. A branch strategy and a bound strategy are applied to accelerate the solution process of the TRDP. The computational experiments give promising results, showing that the optimal turning restriction strategy can obviously reduce system congestion and are robust to the variations of both the dispersion parameter of the SUE problem and the level of demand.     

Incorporating transfer reliability into equilibrium analysis of railway passenger flow

Passenger’s transfer route choice behavior is one of the prominent research topics in the field of railway transportation. Existing traffic assignment approaches do not properly account for passenger’s expectation for transfer reliability. In this study, the transfer reliability is explicitly defined and a multi-class user equilibrium model is established, given which passengers choose the minimal-cost path based on their expected reliability thresholds. In particular, a path-based traffic assignment algorithm which combines a k-shortest path algorithm and the method of successive averages is proposed. The validity of the proposed approach is verified by an illustrative example. Using the proposed modeling approach, it is possible to determine the passenger’s collective route choice behavior based on the user equilibrium pattern. Moreover, the railway timetables can be evaluated and optimized based on the cost-based level of service estimation.     

A GREEDY ALGORITHM FOR SPARSE PRECISION MATRIX APPROXIMATION

Precision matrix estimation is an important problem in statistical data analysis.This paper proposes a sparse precision matrix estimation approach,based on CLIME estimator and an efficient algorithm GISSρ that was originally proposed for l1 sparse signal recov-ery in compressed sensing.The asymptotic convergence rate for sparse precision matrix estimation is analyzed with respect to the new stopping criteria of the proposed GISSρ algorithm.Finally,numerical comparison of GISSρ with other sparse recovery algorithms,such as ADMM and HTP in three settings of precision matrix estimation is provided and the numerical results show the advantages of the proposed algorithm.     

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.     

改进蚁群算法优化周期性车辆路径问题

周期性车辆路径问题(PVRP)是标准车辆路径问题(VRP)的扩展,PVRP将配送期由单一配送期延伸到T(T＞1)期,因此,PVRP需要优化每个配送期的顾客组合和配送路径。由于PVRP是一个内嵌VRP的问题,其比标准VRP问题更加复杂,难于求解。本文采用蚁群算法对PVRP进行求解,并提出采用两种改进措施——多维信息素的运用和基于扫描法的局部优化方法来提高算法的性能。最后,通过9个经典PVRP算例对该算法进行了数据实验,结果表明本文提出的改进蚁群算法求解PVRP问题是可行有效的,同时也表明两种改进措施可以显著提高算法的性能。     

多方式弹性需求下公交定价双层规划模型

为描述多方式城市交通网络下公交定价与出行选择行为的相互作用与影响,将出行方式选择与路径选择涵盖于同一网络,建立了上层模型分别以企业利润最大化、乘客出行成本最小化和社会福利最大化为目标函数,下层模型为多方式弹性需求随机用户配流模型的公交定价双层规划模型。运用改进遗传算法对模型整体进行求解,下层模型采用综合对角化算法和MSA算法的组合求解算法。最后,设计了一个算例以说明模型应用。结果表明:运用双层规划模型所确定的公交票价较传统静态票价可使政府、企业及出行者三方都获得更高收益,且上层模型以社会福利最大化为目标函数能代表社会群体中多数人利益,优化效果最为理想。     

A Stochastic Model for Combined Activity/Destination/Route Choice Problems

In travel behavior modeling, an important topic is to investigate what drives people to travel. A systematic 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, this paper presents a stochastic model for solving the combined activity/destination/route choice problem. It is a time-dependent model for long-term transport planning such as travel demand forecasting. The activity/destination choices are based on multinomial logit formulae and, the route choice is governed by stochastic user equilibrium principle. The solution algorithm is proposed together with a numerical example for demonstration. It is shown that the proposed modeling approach provides a powerful tool for fully understanding and predicting the complex travel behavior at strategic level. The work described in this paper was substantially supported by the grants from the National Natural Science Foundation of China (Project No. 79825101), the Chinese Academy of Sciences (MADIS Research Project) and the Research Grants Council of the Hong Kong Special Administrative Region (Project No. PolyU5077/97E).