Sensitivity analysis for the asymmetric network equilibrium problem

We consider the asymmetric continuous traffic equilibrium network model with fixed demands where the travel cost on each link of the transportation network may depend on the flow on this as well as other links of the network and we perform stability and sensitivity analysis. Assuming that the travel cost functions are monotone we first show that the traffic equlibrium pattern depends continuously upon the assigned travel demands and travel cost functions. We then focus on the delicate question of predicting the direction of the change in the traffic pattern and the incurred travel costs resulting from changes in the travel cost functions and travel demands and attempt to elucidate certain counter intuitive phenomena such as ‘Braess' paradox’. Our analysis depends crucially on the fact that the governing equilibrium conditions can be formulated as a variational inequality. This work was supported by the Program of University Research, U.S. Department of Transportation (Project number DTRS 5680-C-00007).     

Evaluation and optimization of urban public transportation networks

So far, not much attention has been given to the problem of improving public transportation networks. In many cities these networks have been built sequentially and do not fit to the needs of the users any more. The results are long travel times and an unnecessarily high number of people who have to transfer. Compared to other investments for improving the service level of public transportation systems, the costs of rerouting the public vehicles are low and can, yet, highly improve the performance of the system.To evaluate a public transportation network, the shortest distance and the shortest route from node x to node y, taking the waiting times for a vehicle into account, must be known.It is shown in this paper, how to compute distances and routes efficiently for large networks. Using this algorithm it is described how to evaluate the average transportation cost of the passengers in a public transportation network.In the second part of the paper a heuristic algorithm is stated that improves a public transportation network using the average transportation cost as the objective.Finally, some experiences with real world problems are reported.     

Travel Distance Through Transportation Terminals on a Rectangular Grid

The number of terminals used in a transportation network affects inventory, transportation and overhead costs. With few terminals, overhead and inventory costs tend to be small, but average travel distance through terminals is large. With many terminals, overhead and inventory costs are large, but average travel distance is small. As a first step toward analyzing this trade-off, this paper develops equations that quantify the relation between number of terminals and average travel distance. These equations are verified by applying them to an example involving the 37 largest cities in the United States. Average travel distance is shown to decrease slowly as the number of terminals increases, declining by no more than one third. Although adding terminals decreases travel distance somewhat, the marginal travel distance reduction quickly becomes quite small.     

基于鲁棒优化的随机时变网络最优路径研究

交通事故、恶劣天气以及偶发的交通拥堵等都会导致道路交通网络中行程时间的不确定性,极大地影响了道路交通系统的可靠性,同时给日常生活中出行计划的制定以及出行路径的选择带来了不便。因此,本次研究将综合考虑道路交通网络中由于交通流量的全天变化所导致的路径行程时间的时变特征,以及由于事故、天气等不确定因素所导致的路径行程时间的随机特征,并以此作为路网环境的假设条件,对出行路径选择问题进行研究。具体地,首先建立行程时间的动态随机变量,并在此基础上模拟构建了随机时变网络。随后,定义了该网络环境下路径选择过程中所考虑的成本费用,并通过鲁棒优化的方法,将成本费用鲁棒性最强的路径视为最优路径。随后,在随机一致性条件下,通过数学推导证明了该模型可以简化为解决一个确定性时变网络中的最短路径问题。最终,具有多项式时间计算复杂度的改进Dijkstra算法被应用到模型的求解中,并通过小型算例验证模型及算法的有效性。结果表明,本研究中所提出的方法可以被高效率算法所求解,并且不依赖于先验行程时间概率分布的获取,因此对后续的大规模实际城市道路网络应用提供了良好的理论基础。此外,由于具有行程时间随机时变特征的交通网络更接近实际道路情况,因此本次研究的研究成果具有较高的实际意义和应用价值。     

Partial Geometric Regularity of Some Optimal Connected Transportation Networks

We consider a continuous optimization model of a one-dimensional connected transportation network under the assumption that the cost of transportation with the use of network is negligible in comparison with the cost of transportation without it. We investigate the connections between this problem and its important special case, the minimization of the average distance functional. For the average distance minimization problem we formulate a number of conditions for the partial geometric regularity of a solution in ℝⁿ with an arbitrary dimension n ⩾ 2. The corresponding results are applied to solutions to the general optimization problem. Bibliography: 26 titles. Illustrations: 1 Figure. __________ Translated from Problemy Matematicheskogo Analiza, No. 31, 2005, pp. 129–157.     

Estimation of Travel Times in Multiple Mode Systems<Superscript>†</Superscript>

This paper describes a procedure for generating estimates of the minimum travel times (shortest distances, least cost routes) between pairs of points on a standard map. The procedure exhibits substantial improvements in accuracy over the traditional generation methods involving simple orthogonal and vector-directed distance metrics. These improvements are achieved by combining the traditional methods with algorithms which find shortest routes in networks. The new procedure is particularly appropriate to the analysis of transportation or distribution systems which entail "multiple-mode travel", e.g. surface road vs. expressway travel, or railway vs. air travel. The advantages of the procedure are illustrated with empirical evidence from a simulation study of travel times in a large urban area. Finally, the generality of this procedure to a wide class of problems is discussed.     

Financial scenario generation for stochastic multi-stage decision processes as facility location problems

The quality of multi-stage stochastic optimization models as they appear in asset liability management, energy planning, transportation, supply chain management, and other applications depends heavily on the quality of the underlying scenario model, describing the uncertain processes influencing the profit/cost function, such as asset prices and liabilities, the energy demand process, demand for transportation, and the like. A common approach to generate scenarios is based on estimating an unknown distribution and matching its moments with moments of a discrete scenario model. This paper demonstrates that the problem of finding valuable scenario approximations can be viewed as the problem of optimally approximating a given distribution with some distance function. We show that for Lipschitz continuous cost/profit functions it is best to employ the Wasserstein distance. The resulting optimization problem can be viewed as a multi-dimensional facility location problem, for which at least good heuristic algorithms exist. For multi-stage problems, a scenario tree is constructed as a nested facility location problem. Numerical convergence results for financial mean-risk portfolio selection conclude the paper.     

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

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

Parking Capacity and Pricing in Park'n Ride Trips: A Continuous Equilibrium Network Design Problem

In this paper we consider the problem of designing parking facilities for park'n ride trips. We present a new continuous equilibrium network design problem to decide the capacity and fare of these parking lots at a tactical level. We assume that the parking facilities have already been located and other topological decisions have already been taken.The modeling approach proposed is mathematical programming with equilibrium constraints. In the outer optimization problem, a central Authority evaluates the performance of the transport network for each network design decision. In the inner problem a multimodal traffic assignment with combined modes, formulated as a variational inequality problem, generates the share demand for modes of transportation, and for parking facilities as a function of the design variables of the parking lots. The objective is to make optimal parking investment and pricing decisions in order to minimize the total travel cost in a subnetwork of the multimodal transportation system.We present a new development in model formulation based on the use of generalized parking link cost as a design variable.The bilevel model is solved by a simulated annealing algorithm applied to the continuous and non-negative design decision variables. Numerical tests are reported in order to illustrate the use of the model, and the ability of the approach to solve applications of moderate size.     

Location of a semi-obnoxious facility with elliptic maximin and network minisum objectives

This paper considers the problem of locating a single semi-obnoxious facility on a general network, so as to minimize the total transportation cost between the new facility and the demand points (minisum), and at the same time to minimize the undesirable effects of the new facility by maximizing its distance from the closest population center (maximin). The two objectives employ different distance metrics to reflect reality. Since vehicles move on the transportation network, the shortest path distance is suitable for the minisum objective. For the maximin objective, however, the elliptic distance metric is used to reflect the impact of wind in the distribution of pollution. An efficient algorithm is developed to find the nondominated set of the bi-objective model and is implemented on a numerical example. A simulation experiment is provided to find the average computational complexity of the algorithm.     

Integrating link-based discrete credit charging scheme into discrete network design problem

In this paper, we present an optimization model for integrating link-based discrete credit charging scheme into the discrete network design problem, to improve the transport performance from the perspectives of both transport network planning and travel demand management. The proposed model is a mixed-integer nonlinear bilevel programming problem, which includes an upper level problem for the transport authority and a lower level problem for the network users. The lower level sub-model is the traffic network user equilibrium (UE) formulation for a given network design strategy determined by the upper level problem. The network user at the lower level tries to minimize his/her own generalized travel cost (including both the travel time and the value of the credit charged for using the link) by choosing his/her route. While the transport authority at the upper level tries to find the optimal number of lanes and credit charging level with their locations to minimize the total system travel time (or maximize the transportation system performance). A genetic algorithm is used to solve the proposed mixed-integer nonlinear bilevel programming problem. Numerical experiments show the efficiency of the proposed model for traffic congestion mitigation, reveal that interaction effects across the tradable credit scheme and the discrete network design problem which amplify their individual effects. Moreover, the integrated model can achieve better performance than the sequential decision problems.     

不确定条件下的乡村中小学布局优化

学校的合理规划布局是实现教育资源优化配置、提高办学效益和推动教育均衡发展的重要途径。已有许多学者研究了学校的布局问题,但基本上都忽略了交通网络条件以及不确定因素对学校布局的影响。本研究将在前人研究基础上,重点考虑交通网络对乡村中小学选址的影响,并假设旅行时间具有不确定性,从而以最小化学生旅行成本、学校建设、道路修建和道路升级成本为目标,构建不确定条件下的设施区位设计模型。在算法求解方面提出混合模拟退火算法,用于确定新建学校的最佳位置,以及新道路的修建和原有道路的升级情况。最后,将提出的模型和算法应用到实际案例中。     

Terminal Location Problem: A Case Study Supporting the <Emphasis Type="Italic">Status Quo</Emphasis>

This paper applies a single-facility location model to the distribution network covered by the Brantford, Ontario branch of Thibodeau-Finch Transport Ltd. The model is used to determine whether or not the present terminal location should be maintained for the current demand structure and for a projected demand structure. Optimal locations are obtained for both demand structures using a distance function that is tailored to the actual road network over which the firm's vehicles travel. It is found that the transportation costs associated with the optimal locations are sufficiently close to those with the present location to conclude that Thibodeau-Finch should not consider relocation among its strategic options. The paper includes relevant data for verifying the conclusions drawn in support of the status quo.     

Using fuzzy integral for evaluating subjectively perceived travel costs in a traffic assignment model

A good traffic assignment model can be a powerful tool to describe the characteristics of traffic behavior in a road network. The traffic assignment results often play an important role in transportation planning, e.g., an optimal and economical network design. Many traditional traffic assignment models rely heavily on the travel cost function established by Wardrop’s principles; however, the Wardrop’s travel cost function has been proven to be weak for explaining the uncertainty and interactivity of traffic among links. This study tries to construct a traffic assignment model that is different from Wardrop’s in many aspects. First, it considers the cross-effect among the links. Second, a fuzzy travel cost function is established based on the possibility concept instead of precise calculation of traffic volumes. Third, the techniques of fuzzy measure and fuzzy integral are applied to calculate the subjectively perceived travel costs during traffic assignment. Furthermore, in order to validate our model, a detailed network with 22 nodes and 36 links is used to illustrate it. Study results show that our model explains more interactivity and uncertainty of traffic among links when compared with the traditional model of Wardrop’s.     

A DC programming approach for solving multicast network design problems via the Nesterov smoothing technique

This paper continues our recent effort in applying continuous optimization techniques to study optimal multicast communication networks modeled as bilevel hierarchical clustering problems. Given a finite number of nodes, we consider two different models of multicast networks by identifying a certain number of nodes as cluster centers, and at the same time, locating a particular node that serves as a total center so as to minimize the total transportation cost throughout the network. The fact that the cluster centers and the total center have to be among the given nodes makes these problems discrete optimization problems. Our approach is to reformulate the discrete problems as continuous ones and to apply Nesterov’s smoothing approximation techniques on the Minkowski gauges that are used as distance measures. This approach enables us to propose two implementable DCA-based algorithms for solving the problems. Numerical results and practical applications are provided to illustrate our approach.     

Minimizing greenhouse gas emissions in intermodal freight transport: an application to rail service design

Freight transport has undesirable effects on the environment. The most prominent of these is greenhouse gas emissions. Intermodal freight transport, where freight is shipped from origin to destination by a sequence of at least two transportation modes, offers the possibility of shifting freight (either partially or in full) from one mode to another in the hope of reducing the greenhouse emissions by appropriately scheduling the services and routing the freight. Traditional planning methods for scheduling services in an intermodal transportation network usually focus on minimizing travel or time-related costs of transport. This article breaks away from such an approach by addressing the issue of incorporating environment-related costs (greenhouse gases, to be specific) into freight transportation planning and proposes an integer program in the form of a linear cost, multicommodity, capacitated network design formulation that minimizes the amount of greenhouse gas emissions of transportation activities. Computational results based on an application of the proposed approach on a real-life rail freight transportation network are presented.     

Location-allocation on a line with demand-dependent costs

This paper extends the location-allocation formulation by making the cost charged to users by a facility a function of the total number of users patronizing the facility. Users select their facility based on facility charges and transportation costs. We explore equilibria where each customer selects the least expensive facility (cost and transportation) and where the facility is at a point that minimizes travel costs for its customers. The problem in its general form is quite complex. An interesting special case is studied: facilities and customers are located on a finite line segment and demand is distributed on the line by a given density function.     

Locating semi-obnoxious facilities with expropriation: minisum criterion

This paper considers the problem of locating semi-obnoxious facilities assuming that demand points within a certain distance from an open facility are expropriated at a given price. The objective is to locate the facilities so as to minimize the total weighted transportation cost and expropriation cost. Models are developed for both single and multiple facilities. For the case of locating a single facility, finite dominating sets are determined for the problems on a plane and on a network. An efficient algorithm is developed for the problem on a network. For the case of locating multiple facilities, a branch-and-bound procedure using Lagrangian relaxation is proposed and its efficiency is tested with computational experiments.     

General transport problems with branched minimizers as functionals of 1-currents with prescribed boundary

A prominent model for transportation networks is branched transport, which seeks the optimal transportation scheme to move material from a given initial to a given final distribution. The cost of the scheme encodes a higher transport efficiency the more mass is moved together, which automatically leads to optimal transportation networks with a hierarchical branching structure. The two major existing model formulations use either mass fluxes (vector-valued measures, Eulerian formulation) or patterns (probabilities on the space of particle paths, Lagrangian formulation). In the branched transport problem the transportation cost is a fractional power of the transported mass. In this paper we instead analyse the much more general class of transport problems in which the transportation cost is merely a nonnegative increasing and subadditive function (in a certain sense this is the broadest possible generalization of branched transport). In particular, we address the problem of the equivalence of the above-mentioned formulations in this wider context. However, the newly-introduced class of transportation costs lacks strict concavity which complicates the analysis considerably. New ideas are required, in particular, it turns out convenient to state the problem via 1-currents. Our analysis also includes the well-posedness, some network properties, as well as a metrization and a length space property of the model cost, which were previously only known for branched transport. Some already existing arguments in that field are given a more concise and simpler form.