首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
We consider a network design problem (NDP) under random demand with unknown distribution for which only a small number of observations are known. We design arc capacities in the first stage and optimize single-commodity network flows after realizing the demand in the second stage. The objective is to minimize the total cost of allocating arc capacities, flowing commodities, and penalty for unmet demand. We formulate a distributionally robust NDP (DR-NDP) by constructing an ambiguity set of the unknown demand distribution based on marginal moment information, to minimize the worst-case total cost over all possible distributions. Approximating polynomials with piecewise-linear functions, we reformulate DR-NDP as a mixed-integer linear program optimized via a cutting-plane algorithm. We test diverse network instances to compare DR-NDP with a stochastic programming approach, a deterministic benchmark model, and a robust NDP formulation. Our results demonstrate adequate robustness of optimal DR-NDP solutions and how they perform under varying demand, modeling parameter, network, and cost settings. The results highlight potential niche uses of DR-NDP in data-scarce contexts.  相似文献   

2.
The transportation network design problem (NDP) with multiple objectives and demand uncertainty was originally formulated as a spectrum of stochastic multi-objective programming models in a bi-level programming framework. Solving these stochastic multi-objective NDP (SMONDP) models directly requires generating a family of optimal solutions known as the Pareto-optimal set. For practical implementation, only a good solution that meets the goals of different stakeholders is required. In view of this, we adopt a goal programming (GP) approach to solve the SMONDP models. The GP approach explicitly considers the user-defined goals and priority structure among the multiple objectives in the NDP decision process. Considering different modeling purposes, we provide three stochastic GP models with different philosophies to model planners’ NDP decision under demand uncertainty, i.e., the expected value GP model, chance-constrained GP model, and dependent-chance GP model. Meanwhile, a unified simulation-based genetic algorithm (SGA) solution procedure is developed to solve all three stochastic GP models. Numerical examples are also presented to illustrate the practicability of the GP approach in solving the SMONDP models as well as the robustness of the SGA solution procedure.  相似文献   

3.
Transportation system analysis must rely on predictions of the future that, by their very nature, contain substantial uncertainty. Future demand, demographics, and network capacities are only a few of the parameters that must be accounted for in both the planning and every day operations of transportation networks. While many repercussions of uncertainty exist, a primary concern in traffic operations is to develop efficient traffic signal designs that satisfy certain measures of short term future system performance while accounting for the different possible realizations of traffic state. As a result,uncertainty has to be incorporated in the design of traffic signal systems. Current dynamic traffic equilibrium models accounting for signal design, however, are not suitable for quantifying network performance over the range of possible scenarios and in analyzing the robust performance of the system. The purpose of this paper is to propose a new approach—robust system optimal signal control model; a supply-side within day operational transportation model where future transportation demand is assumed to be uncertain. A robust dynamic system optimal model with an embedded cell transmission model is formulated. Numerical analysis are performed on a test network to illustrate the benefits of accounting for uncertainty and robustness.  相似文献   

4.
This paper describes a robust optimization approach for a network design problem explicitly incorporating traffic dynamics and demand uncertainty. In particular, we consider a cell transmission model based network design problem of the linear programming type and use box uncertainty sets to characterize the demand uncertainty. The major contribution of this paper is to formulate such a robust network design problem as a tractable linear programming model and demonstrate the model robustness by comparing its solution performance with the nominal solution from the corresponding deterministic model. The results of the numerical experiments justify the modeling advantage of the robust optimization approach and provide useful managerial insights for enacting capacity expansion policies under demand uncertainty.  相似文献   

5.
城市交通噪声环境承载力分析模型及算法   总被引:1,自引:0,他引:1  
以城市噪声环境容量为约束条件计算城市区域路网最大交通承载力。分析模型是一个双层优化问题,其中上层是噪声环境容量约束下的最大路网交通流量模型;下层是道路网上的用户均衡分配模型。应用遗传算法进行求解,仿真示例表明该模型和算法是可行的、有效的,可以为城市交通可持续发展的规划和需求管理提供依据。  相似文献   

6.
The problem of estimating origin-destination travel demands from partial observations of traffic conditions has often been formulated as a network design problem (NDP) with a bi-level structure. The upper level problem in such a formulation minimizes a distance metric between measured and estimated traffic conditions, and the lower level enforces user-equilibrium traffic conditions in the network. Since bi-level problems are usually challenging to solve numerically, especially for large-scale networks, we proposed, in an earlier effort (Nie et al., Transp Res, 39B:497–518, 2005), a decoupling scheme that transforms the O–D estimation problem into a single-level optimization problem. In this paper, a novel formulation is proposed to relax the user equilibrium conditions while taking users’ route choice behavior into account. This relaxation approach allows the development of efficient solution procedures that can handle large-scale problems, and makes the integration of other inputs, such as path travel times and historical O–Ds rather straightforward. An algorithm based on column generation is devised to solve the relaxed formulation and its convergence is proved. Using a benchmark example, we compare the estimation results obtained from bi-level, decoupled and relaxed formulations, and conduct various sensitivity analysis. A large example is also provided to illustrate the efficiency of the relaxation method.  相似文献   

7.
We present a heuristic to solve the NP-hard bi-level network design problem (NDP). The heuristic is developed based on the Dantzig-Wolfe decomposition principle such that it iteratively solves a master problem and a pricing problem. The master problem is the budget allocation linear program solved by CPLEX to determine the budget allocation and construct a modified cell transmission network for the pricing problem. The pricing problem is the user-optimal dynamic traffic assignment (UODTA) solved by an existing combinatorial algorithm. To facilitate the decomposition principle, we propose a backward connectivity algorithm and complementary slackness procedures to efficiently approximate the required dual variables from the UODTA solution. The dual variables are then employed to augment a new column in the master program in each iteration. The iterative process repeats until a stopping criterion is met. Numerical experiments are conducted on two test networks. Encouraging results demonstrate the applicability of the heuristic scheme on solving large-scale NDP. Though a single destination problem is considered in this paper, the proposed scheme can be extended to solve multi-destination problems as well.  相似文献   

8.
Networks and Spatial Economics - Dynamic user equilibrium (DUE) is a Nash-like solution concept describing an equilibrium in dynamic traffic systems over a fixed planning period. DUE is a...  相似文献   

9.
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.  相似文献   

10.
Dynamic congestion pricing has become an important research topic because of its practical implications. In this paper, we formulate dynamic second-best toll pricing (DSBTP) on general networks as a bilevel problem: the upper level is to minimize the total weighted system travel time and the lower level is to capture motorists’ route choice behavior. Different from most of existing DSBTP models, our formulation is in discrete-time, which has very distinct properties comparing with its continuous-time counterpart. Solution existence condition of the proposed model is established independent of the actual formulation of the underlying dynamic user equilibrium (DUE). To solve the bilevel DSBTP model, we adopt a relaxation scheme. For this purpose, we convert the bilevel formulation into a single level nonlinear programming problem by applying a link-node based nonlinear complementarity formulation for DUE. The single level problem is solved iteratively by first relaxing the strick complementarity by a relaxation parameter, which is then progressively reduced. Numerical results are also provided in this paper to illustrate the proposed model and algorithm. In particular, we show that by varying travel time weights on different links, DSBTP can help traffic management agencies better achieve certain system objectives. Examples are given on how changes of the weights impact the optimal tolls and associated objective function values.
Henry X. LiuEmail:
  相似文献   

11.
This paper develops a path-based traffic assignment algorithm for solving the elastic demand traffic assignment problem (EDTAP). A modified path-based gradient projection (GP) method combined with a column generation is suggested for solving the equivalent excess-demand reformulation of the problem in which the elastic demand problem is reformulated as a fixed demand problem through an appropriate modification of network representation. Numerical results using a set of real transportation networks are provided to demonstrate the efficiency of the modified GP algorithm for solving the excess-demand formulation of the EDTAP. In addition, a sensitivity analysis is conducted to examine the effects of the scaling parameter used in the elastic demand function on the estimated total demand, number of generated paths, number of used paths, and computational efforts of the modified GP algorithm.  相似文献   

12.
Dynamic networks are characterized by transit times on edges. Dynamic flow problems consider transshipment problems in dynamic networks. We introduce a new version of dynamic flow problems, called bridge problem. The bridge problem has practical importance and raises interesting theoretical issues. We show that the bridge problem is NP-complete. Traditional static flow techniques for solving dynamic flow problems do not extend to the new problem. We give a linear programming formulation for the bridge problem which is based on the time-expanded network of the original dynamic network.  相似文献   

13.
Wireless body area networks are wireless sensor networks whose adoption has recently emerged and spread in important healthcare applications, such as the remote monitoring of health conditions of patients. A major issue associated with the deployment of such networks is represented by energy consumption: in general, the batteries of the sensors cannot be easily replaced and recharged, so containing the usage of energy by a rational design of the network and of the routing is crucial. Another issue is represented by traffic uncertainty: body sensors may produce data at a variable rate that is not exactly known in advance, for example because the generation of data is event-driven. Neglecting traffic uncertainty may lead to wrong design and routing decisions, which may compromise the functionality of the network and have very bad effects on the health of the patients. In order to address these issues, in this work we propose the first robust optimization model for jointly optimizing the topology and the routing in body area networks under traffic uncertainty. Since the problem may result challenging even for a state-of-the-art optimization solver, we propose an original optimization algorithm that exploits suitable linear relaxations to guide a randomized fixing of the variables, supported by an exact large variable neighborhood search. Experiments on realistic instances indicate that our algorithm performs better than a state-of-the-art solver, fast producing solutions associated with improved optimality gaps.  相似文献   

14.
Vehicular networks are mobile networks designed for the domain of vehicles and pedestrians. These networks are an essential component of intelligent transportation systems and have the potential to ease traffic management, lower accident rates, and offer other solutions to smart cities. One of the most challenging aspects in the design of a vehicular network is the distribution of its infrastructure units, which are called roadside units (RSUs). In this work, we tackle the gamma deployment problem that consists of deploying the minimum number of RSUs in a vehicular network in accordance with a quality of service metric called gamma deployment. This metric defines a vehicle as covered if it connects to some RSUs at least once in a given time interval during its whole trip. Then, the metric parameterizes the minimum percentage of covered vehicles necessary to make a deployment acceptable or feasible. In this paper, we prove that the decision version of the gamma deployment problem in grids is NP‐complete. Moreover, we correct the multiflow integer linear programming formulation present in the literature and introduce a new formulation based on set covering that is at least as strong as the multiflow formulation. In experiments with a commercial solver, the set covering formulation widely outperforms the multiflow formulation with respect to running time and linear programming relaxation gap.  相似文献   

15.
Networks and Spatial Economics - Dynamic user equilibrium (DUE) is the most widely studied form of dynamic traffic assignment (DTA), in which road travelers engage in a non-cooperative Nash-like...  相似文献   

16.
This paper develops a multi-modal transport network model considering various travel modes including railway, bus, auto, and walking. Travellers are assumed to choose their multi-modal routes so as to minimise their perceived disutilities of travel following the Probit Stochastic User Equilibrium (SUE) condition. Factors influencing the disutility of a multi-modal route include actual travel times, discomfort on transit systems, expected waiting times, fares, and constants specific to transport modes. The paper then deals with the multi-modal network design problem (NDP). The paper employs the method of sensitivity analysis to define linear approximation functions between the Probit SUE link flows and the design parameters, which are then used as constraints in the sub-problem of the NDP instead of the original SUE condition. Based on this reformulated NDP, an efficient algorithm for solving the problem is proposed in the paper. Two instances of this general NDP formulation are then presented in the paper: the optimal frequency design problem for public transport services (FDP), and the anti-freezing admixture dispersion problem (AADP).  相似文献   

17.
城市路网设计问题就是研究如何用定量的方法在已有交通网络上添加或扩容某些路段的问题。本文提出一种基于遗传算法的城市混合型路网设计的双层优化模型,可求出最优的用于道路网新建或改善的交通建设投资决策方案,并利用一个算例进行仿真试验,结果表明,该模型和算法是可行的,可为城市路网设计提供借鉴。  相似文献   

18.
In this paper, a Dantzig-Wolfe decomposition based solution algorithm is developed for the linear programming formulation introduced by Ziliaskopoulos (2000) for System Optimal Dynamic Traffic Assignment problem. The algorithm takes advantage of the network structure in the constraint set of the formulation: the sub-problem is formulated as a minimum-cost-flow problem and the master as a simpler linear programming problem, which allows DTA to be solved more efficiently on meaningful networks. The algorithm is tested on an example network and its performance is analyzed.  相似文献   

19.
Shekhar  Appie  Deep   《Computer Networks》2009,53(15):2688-2702
Heterogeneous streams (due to issues such as disparate traffic characteristics of each stream, or competing customers’ traffic) raise the issue of whether to multiplex (some of) these streams. In an MPLS network, such multiplexing can be considered by putting different streams into a tunnel identified by a single label-switched path (LSP), assuming that the different LSPs are assigned a reserved share of the resources. This issue becomes even more important in the traffic engineering of a backbone network when a decision needs to be made on which streams to multiplex when there are constraints on tunneling and capacity along with routing requirements for tunnels. In this paper, we introduce a distortion factor due to heterogeneous streams in traffic engineering of MPLS backbone networks in the presence of tunneling and capacity constraints by formulating a distortion-aware non-linear discrete optimization problem. Furthermore, we present a two-phase heuristic approach to solve this formulation efficiently. In the first phase, the problem is decoupled into two subproblems and in the second phase we show how the non-linear problem (for one of the subproblems) can be simplified. We then present numerical results for both small and large networks to show where and how our approach helps to determine when and which streams to multiplex depending on whether the tunneling and/or capacity constraint is dominant; furthermore, by comparing our distortion-aware traffic engineering model with a distortion-ignorant traffic engineering model, we show the benefits of our approach.  相似文献   

20.
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.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号