Studies On The Models And Algorithms Of Network Design Problem Based On Robust Optimization Approach

ABSTRACT:Network design problem is at the core of one of comprehensive urban planning, and is also a basic problem that contributes to the long-term, rapid, harmonious and stable development of the urban economics. Currently, with the rapid development of cities, urban traffic congestion is becoming increasingly serious, the contradiction of supplying and demand of traffic has risen, and congestion alleviation and prevention have become urgent tasks for urban development. On the other hand, a lot of uncertainties surround the urban traffic system. If these uncertainties are ignored in the network design problem, it may lead to the more serious traffic congestion. Therefore, the network design problem under uncertainty research is essential. Research methods in the network design problem under uncertainty are stochastic programming and robust optimization. The stochastic programming approach needs to assume the probability distribution of the uncertain parameter in advance. However, in reality, this assumptive distribution may be unavailable(inaccurate) as we may have no insufficient data to calibrate this distribution, and the robust optimization approach doesn't require known probability distribution of the uncertain parameter. Therefore, it has more practical meaning by using the robust optimization approach to study network design problem under uncertainty.The aim of this dissertation is to adopt the robust optimization approach to study network design problem under uncertainty, and develops the models and algorithms of the network design problem under uncertainty. The main contents of the dissertation are summarized as follows:(1) We consider the continuous network design problem under demand uncertainty based on user equilibrium by using the nolinear robust optimization approach, in which the uncertain demand is assumed to belong to an ellipsoid set. We reformulate the robust counterpart (RC) of continuous network design problem under demand uncertainty as a series of mathemtical progrms with complementarity problem(MPCC) by adopting the idea of robust opitmization and the sensitivity analysis, and applies a relax algorithm to solve this series of MPCC. In addition, we compare it with the robust counterpart (RC) by proposed Yin and Lawphonganich[1]. The number example results show that the our RC model is more flexible than, and no less conservative than the robust solution obtained by Yin and Lawphonganich [1]. (2) We develop the robust reliable traffic equilibrium problem under demand uncertainty, in which the model doesn't require known the probability distribution of the uncertain demand, while only needs to know its first-m moments. The robust percentile travel time (RPTT) and robust mean-excess travel time (RMETT) are defined by adopting the Worst-case Value-at-Risk (WVaR) and Worst-case Conditional Value-at-Risk measures (WCVaR)[2], and then the RPTT and RMETT are equal under general distribution are demonstrated. According to the two equivalent travel time, the robust percentile user equilibrium (RPUE) or robust mean-excess traffic equilibrium (RMETE) is proposed. The RPUE or RMETE model is formulated as a nonlinear complementarity problem (NCP) and the equivalence and existence of the equilibrium solution are demonstarted, and then is solved by a solution method based on the gap function. Furthermore, the network design problem with the distributionally robust joint chance constraints is developed based on the proposed equilibrium model. The distributionally robust joint chance constraints of network design problem are approximated as the nonlinear constraints based on the Bonferroni's inequalitiy. The active set algorithm are developed to solve the approximated model. The numerical example is depicted to examine the proposed network design model and the solution algorithm.(3) The cell transmission model-based (CTM)[3-4]single level dynamic network design problem under demand uncertainty is developed by applying the adjustable robust optimization approach. The model assumes that the demand belongs to a polyhedral set. The affinely adjustable robust counterpart (AARC) of the CTM-based single level dynamic network design problem under demand uncertainty is formulated through the affine decision rule and the duality of liner programming, and is compared with the robust counterpart of it. Numerical example shows that the adjustable robust solution of the CTM-based single level dynamic network design problem under demand uncertainty is more flexible than robust solution, and no less conservative than robust solution.(4) We propose a distributionally robust joint chance-constrained optimization model for the CTM-based single level dynamic network design problem under demand uncertainty, where the probability distribution of uncertain demand is unknown and only the mean and variance of uncertain demand are known. The distributionally robust joint chance constraints of the model are approximated as the Worst-Case Conditional Value-at-Risk (WCVaR) constraints, and then the Worst-Case Conditional Value-at-Risk (WCVaR) constraints are equivalently reformulated as the semidefinite programming (SDP) constraints. The SDP-based approximation are compared with the two other approximation approches based on the Bonferroni's inequalities and second order cone programming (SOCP). Numerical experiment is conducted to demonstrate that the SDP-based approximation is more flexible, no less conservative, superior to Bonferroni's inequality-based approximation and SOCP-based approximation.(5) The CTM-based two-level dynamic network design model under demand uncertainty is formulated by applying the WCVaR, in which the probability distribution of uncertain demand is assumed to belong to a polyhedral set that the known mean and variance of possible probability distribution composed. The CTM-based two-level dynamic network design model is equivalently reformulated as the mathematical programs with complementarity constraint (MPCC) based on the KKT condition of the low-level user optimal dynamic network design problem. A relaxed algorithm is developed to solve the MPCC. Numerical example is depicted to demonstrate the proposed model and the solution algorithm.