An optimal dimension-down iterative algorithm （DDIA） is proposed for solving a mixed （continuous/ discrete） transportation network design problem （MNDP）, which is generally expressed as a mathematical programmin...An optimal dimension-down iterative algorithm （DDIA） is proposed for solving a mixed （continuous/ discrete） transportation network design problem （MNDP）, which is generally expressed as a mathematical programming with equilibrium constraints （MPEC）. The upper level of the MNDP aims to optimize the network performance via both the expansion of existing links and the addition of new candidate links, whereas the lower level is a traditional Wardrop user equilibrium （UE） model. The idea of the proposed DDIA is to reduce the dimensions of the problem. A group of variables （discrete/continuous） are fixed to altemately optimize another group of variables （continuous/discrete）. Some continuous network design problems （CNDPs） and discrete network design problems （DNDPs） are solved repeatedly until the optimal solution is obtained. A numerical example is given to demonstrate the efficiency of the proposed algorithm.展开更多
This study investigated a water supply recovery problem involving municipal water service piping. The problem consisted in recovering full service after network failure, in order to rapidly satisfy all urgent citywide...This study investigated a water supply recovery problem involving municipal water service piping. The problem consisted in recovering full service after network failure, in order to rapidly satisfy all urgent citywide demands. The optimal recovery solution was achieved through the application of so-called network design problems （NDPs）, which are a form of combinatorial optimization problem. However, a conventional NDP is not suitable for addressing urgent situations because （1） it does not utilize the non-failure arcs in the network, and （2） it is solely concerned with stable costs such as flow costs. Therefore, to adapt the technique to such urgent situations, the conventional NDP is here modified to deal with the specified water supply problem. In addition, a numerical illustration using the Sendai water network is presented.展开更多
This paper studies a new form of transportation network design problem. In urban transportation network, unreasonable phenomenon can occur in certain traffic period （e.g. on/off duty period）, which demonstrates that...This paper studies a new form of transportation network design problem. In urban transportation network, unreasonable phenomenon can occur in certain traffic period （e.g. on/off duty period）, which demonstrates that the flows of opposite directions on a two-way road are seriously asymmetric; one traffic link of a two-way road congest heavily but the other is hardly used. In order to reduce transportation congestion and make full use of the existing road resources, we propose a lane reallocating approach in peak period, and establish a discrete hi-level programming model for the decision-making. Then, based on particle swarm optimization （PSO） technique, a heuristic solution algorithm for the hi-level model is designed. Finally, the lane reallocating approach is demonstrated through a simple transportation network.展开更多
Network design problems （NDPs） have long been regarded as one of the most challenging problems in the field of transportation planning due to the intrinsic non-convexity of their bi-level programming form. Furthermo...Network design problems （NDPs） have long been regarded as one of the most challenging problems in the field of transportation planning due to the intrinsic non-convexity of their bi-level programming form. Furthermore, a mixture of continuous/discrete decision variables makes the mixed network design problem （MNDP） more complicated and difficult to solve. We adopt a surrogate-based optimization （SBO） framework to solve three featured categories of NDPs （continuous, discrete, and mixed-integer）. We prove that the method is asymptotically completely convergent when solving continuous NDPs, guaranteeing a global optimum with probability one through an indefinitely long run. To demonstrate the practical performance of the proposed framework, numerical examples are provided to compare SBO with some existing solving algorithms and other heuristics in the literature for NDP. The results show that SBO is one of the best algorithms in terms of both accuracy and efficiency, and it is efficient for solving large-scale problems with more than 20 decision variables. The SBO approach presented in this paper is a general algorithm of solving other optimization problems in the transportation field.展开更多
We study the generalizedk-median version of the warehouse-retailer network design problem(kWRND).We formulate the k-WRND as a binary integer program and propose a 6-approximation randomized algorithm based on Lagrangi...We study the generalizedk-median version of the warehouse-retailer network design problem(kWRND).We formulate the k-WRND as a binary integer program and propose a 6-approximation randomized algorithm based on Lagrangian relaxation.展开更多
A chaotic algorithm for providing a solution to the bi-level Discrete Equilibrium Network Design Problem （NDP） is discussed following an introduction of the Discrete Network Design Problem （DNDP） model and Chaos O...A chaotic algorithm for providing a solution to the bi-level Discrete Equilibrium Network Design Problem （NDP） is discussed following an introduction of the Discrete Network Design Problem （DNDP） model and Chaos Optimization Algorithms （COA）. A description of the chaotic approach for the DNDP model is described in details. Then a numerical example for the DNDP is carried out to investigate the chaotic approach. The results have been encouraging, indicating that the chaotic approach has great potential ability in finding the optimal solution of DNDP models.展开更多
In this paper, a bi-level formulation of the continuous network design problem (NDP) is proposed on the basis of logit stochastic user equilibrium (SUE) assignment with elastic demand. The model determines the link ca...In this paper, a bi-level formulation of the continuous network design problem (NDP) is proposed on the basis of logit stochastic user equilibrium (SUE) assignment with elastic demand. The model determines the link capacity improvements by maximizing net economic benefit while considering changes in demand and traffic distribution in network. The derivatives of equilibrium link flows and objective function with respect to capacity expansion variables, which are analytically derived, can be computed without having to first find path choice information. These derivatives are employed to develop a quasi Newton algorithm with the BFG S (Broyden- Fletcher- Goldfarb-Shanno) formula for solving the nonlinear, nonconvex but differentiable SUE-constrained network design problem. The SUE assignment with elastic demand is solved by using the method of successive averages in conjunction with Bell’s matrix inversion logit assignment method. Simple and complex example networks are presented to illustrate the model and the algorithm.展开更多
This paper presents the design of a computational software system that enables solutions of multi-phase and multi-scale problems in mechanics. It demonstrated how mechanicians can design “process-driven” software sy...This paper presents the design of a computational software system that enables solutions of multi-phase and multi-scale problems in mechanics. It demonstrated how mechanicians can design “process-driven” software systems directly, and that such efforts are more suitable in solving multi-phase or multi-scale problems, rather than utilizing the “data-driven” approaches of legacy network systems. Specifically, this paper demonstrates how this approach can be used to solve problems in flexible dynamics. Then it suggests a view of mechanics algorithms as ‘state equilibrium’ enforcers residing as servers, rather than as computer programs that solve field equations. It puts forth the need for identical input/output files to ensure widespread deployment on laptops. Then it presents an assessment of the laptop platform. A software system such as the one presented here can also be used to supply virtual environments, animations and entertainment/education software with physics.展开更多
基金The National Natural Science Foundation of China(No. 50908235 )China Postdoctoral Science Foundation (No.201003520)
文摘An optimal dimension-down iterative algorithm （DDIA） is proposed for solving a mixed （continuous/ discrete） transportation network design problem （MNDP）, which is generally expressed as a mathematical programming with equilibrium constraints （MPEC）. The upper level of the MNDP aims to optimize the network performance via both the expansion of existing links and the addition of new candidate links, whereas the lower level is a traditional Wardrop user equilibrium （UE） model. The idea of the proposed DDIA is to reduce the dimensions of the problem. A group of variables （discrete/continuous） are fixed to altemately optimize another group of variables （continuous/discrete）. Some continuous network design problems （CNDPs） and discrete network design problems （DNDPs） are solved repeatedly until the optimal solution is obtained. A numerical example is given to demonstrate the efficiency of the proposed algorithm.
文摘This study investigated a water supply recovery problem involving municipal water service piping. The problem consisted in recovering full service after network failure, in order to rapidly satisfy all urgent citywide demands. The optimal recovery solution was achieved through the application of so-called network design problems （NDPs）, which are a form of combinatorial optimization problem. However, a conventional NDP is not suitable for addressing urgent situations because （1） it does not utilize the non-failure arcs in the network, and （2） it is solely concerned with stable costs such as flow costs. Therefore, to adapt the technique to such urgent situations, the conventional NDP is here modified to deal with the specified water supply problem. In addition, a numerical illustration using the Sendai water network is presented.
基金This work was supported in part by National Natural Science Foundation of China under Grant Nos. 70631001, 70481088 and 7067.1008, and by Doctoral Station Grant No.（20050004005） of Ministry of Education, China.
文摘This paper studies a new form of transportation network design problem. In urban transportation network, unreasonable phenomenon can occur in certain traffic period （e.g. on/off duty period）, which demonstrates that the flows of opposite directions on a two-way road are seriously asymmetric; one traffic link of a two-way road congest heavily but the other is hardly used. In order to reduce transportation congestion and make full use of the existing road resources, we propose a lane reallocating approach in peak period, and establish a discrete hi-level programming model for the decision-making. Then, based on particle swarm optimization （PSO） technique, a heuristic solution algorithm for the hi-level model is designed. Finally, the lane reallocating approach is demonstrated through a simple transportation network.
基金Project supported by the Zhejiang Provincial Natural Science Foundation of China （No. LR17E080002）, the National Natural Science Foundation of China （Nos. 51508505, 71771198, 51338008, and 51378298）, the Fundamental Research Funds for the Central Universities, China （No. 2017QNA4025）, and the Key Research and Development Program of Zhejiang Province, China （No. 2018C01007）
文摘Network design problems （NDPs） have long been regarded as one of the most challenging problems in the field of transportation planning due to the intrinsic non-convexity of their bi-level programming form. Furthermore, a mixture of continuous/discrete decision variables makes the mixed network design problem （MNDP） more complicated and difficult to solve. We adopt a surrogate-based optimization （SBO） framework to solve three featured categories of NDPs （continuous, discrete, and mixed-integer）. We prove that the method is asymptotically completely convergent when solving continuous NDPs, guaranteeing a global optimum with probability one through an indefinitely long run. To demonstrate the practical performance of the proposed framework, numerical examples are provided to compare SBO with some existing solving algorithms and other heuristics in the literature for NDP. The results show that SBO is one of the best algorithms in terms of both accuracy and efficiency, and it is efficient for solving large-scale problems with more than 20 decision variables. The SBO approach presented in this paper is a general algorithm of solving other optimization problems in the transportation field.
基金supported by National Basic Research Program of China(973 Program)(Grant No.2010CB732501)National Natural Science Foundation of China(Grant No.11071268)China Scholarship Council Scientific Research Common Program of Beijing Municipal Commission of Education(Grant No.KM201210005033)
文摘We study the generalizedk-median version of the warehouse-retailer network design problem(kWRND).We formulate the k-WRND as a binary integer program and propose a 6-approximation randomized algorithm based on Lagrangian relaxation.
基金This project is supported partly by National 0utstanding Young Investigation of National Natural Science Foundation of China（70225005,70471088,70501004 and 70501005）, the Special Research Found for Doctoral Programs in State Education Ministry （20050004005）, the 211 Project of Discipline Construction of Beijing Jiaotong University and Rencai Foundation of Beijing Jiaotong University （2003RC010）
文摘A chaotic algorithm for providing a solution to the bi-level Discrete Equilibrium Network Design Problem （NDP） is discussed following an introduction of the Discrete Network Design Problem （DNDP） model and Chaos Optimization Algorithms （COA）. A description of the chaotic approach for the DNDP model is described in details. Then a numerical example for the DNDP is carried out to investigate the chaotic approach. The results have been encouraging, indicating that the chaotic approach has great potential ability in finding the optimal solution of DNDP models.
基金Huang gratefully acknowledges the National Natural Science Foundation of China(Grant No. 79825001)and the Ministry of Educatio
文摘In this paper, a bi-level formulation of the continuous network design problem (NDP) is proposed on the basis of logit stochastic user equilibrium (SUE) assignment with elastic demand. The model determines the link capacity improvements by maximizing net economic benefit while considering changes in demand and traffic distribution in network. The derivatives of equilibrium link flows and objective function with respect to capacity expansion variables, which are analytically derived, can be computed without having to first find path choice information. These derivatives are employed to develop a quasi Newton algorithm with the BFG S (Broyden- Fletcher- Goldfarb-Shanno) formula for solving the nonlinear, nonconvex but differentiable SUE-constrained network design problem. The SUE assignment with elastic demand is solved by using the method of successive averages in conjunction with Bell’s matrix inversion logit assignment method. Simple and complex example networks are presented to illustrate the model and the algorithm.
文摘This paper presents the design of a computational software system that enables solutions of multi-phase and multi-scale problems in mechanics. It demonstrated how mechanicians can design “process-driven” software systems directly, and that such efforts are more suitable in solving multi-phase or multi-scale problems, rather than utilizing the “data-driven” approaches of legacy network systems. Specifically, this paper demonstrates how this approach can be used to solve problems in flexible dynamics. Then it suggests a view of mechanics algorithms as ‘state equilibrium’ enforcers residing as servers, rather than as computer programs that solve field equations. It puts forth the need for identical input/output files to ensure widespread deployment on laptops. Then it presents an assessment of the laptop platform. A software system such as the one presented here can also be used to supply virtual environments, animations and entertainment/education software with physics.
