Bayesian ranking and selection models for discrete network design problems with uncertainties and multiple environmental objectives.

摘要

In this dissertation we develop a comprehensive Bayesian Ranking and Selection (R&S) modeling framework for single and multi-objective Network Design Problem with Uncertainty (NDPU). NPDU is a classical problem in transportation sciences and engineering. Due to the complex bi-level nature, NDPU is usually solved with heuristic algorithms where the objective value ofmany candidate solutions are "simulated" for evaluation. As the size of the transportation network can be large, the evaluation of objective values often become the computational bottleneck and should be kept to minimum numbers. On the other hand, most current formulations for (NDPU) characterize uncertainty as a discrete scenario set and tend not to fully explore the inherent correlations among alternatives. Therefore, we feel there is room for improving the efficiency of NDPU solution algorithms with a more rigorous statistical learning model. In Chapter 2, we formulate the NDPU problem as a Constrained Bayesian Ranking and Selection (R&S) problem with exact correlated beliefs. In this formulation, each solution to the NDPU problem represents an "alternative" and the corresponding objective value represents a "reward" we want to maximize. Uncertainties in the objective values are modeled by normal distributions of the rewards and constraints of the NDPU problem are utilized for pre-eliminating infeasible solutions. At each sampling iteration, we update our belief about the distribution of all alternative performances and use the cumulative sampling history to make the next sampling decision. We use a customized version of the Knowledge Gradient policy with Correlated Beliefs (KGCB) to account for constraints and unknown variances of the rewards. Case studies are conducted on transportation networks of different sizes, using popular heuristics such as Genetic Algorithm and Simulation Annealing as comparisons. Results show that the Bayesian R&S model generally provide better accuracy and convergence rate, particularly in scenarios with uncertainty and larger networks. In Chapter 3, we build upon our model Bayesian R&S model in Chapter 2 to improve its performance under large number of projects/alternatives. The new model features 1) a recursively updated linear approximation of the upper-level objective function using Gaussian-binary basis functions, and 2) A surrogateassisted knowledge gradient sampling policy which utilizes the optimal solution of the approximated surrogate objective function to constraint the scale of the expensive knowledge gradient calculation. With the two features the computational complexity of our algorithm is reduced to only a low degree (typically. 2) polynomial of the number of projects. Case studies are conducted on the Sioux Fall network and Anaheim network with as many as 20 projects and over 1,000,000 possible network configurations. Results showed that this parametric Bayesian R&S model is able to identify highly optimal solutions in only around 100 iterations, significantly outpacing our bench-marking Genetic Algorithmand Simulated Annealing Algorithm in both convergence speed and computational cost. Our new method provides a highly scalable framework for discreteNDPUwithout sacrificingmuch of the performance advantage of Bayesian R&S models. It also extends the Bayesian R&S model and the knowledge gradient sampling policies to generic large-scale discrete optimization problems, which provides valuable insights for a large class of similar optimization and learning problems. In Chapter 4, we further extend the Bayesian R&S model to the Multi- Objective discrete Network Design Problem with Uncertainty (MONDPU), an emerging area in transportation planning due to the need for sustainable transportation systems. In this formulation, we put independent parametric beliefs on the expected reward of each objective function like we did in Chapter 3 and update themin parallel through sequential samples. We define amulti-objective version of the Knowledge Gradient policy with Correlated Beliefs which use a crowding distance metric to ensure the diversity of the Pareto optimal front. Case studies are conducted on the Sioux Fall network and Anaheim network. Results showed that our multi-objective Bayesian R&S model is able to identify a very diverse set of highly optimal solutions under very limited budget, significantly out-performing the bench-marking NSGA-II algorithm in both solution quality and practicality. Our model is also the first to extend the Bayesian R&S model and the knowledge gradient sampling policies to generic multi-objective problems. In summary, the Bayesian R&S formulation is well-suited for NDPU and MONDPU due to its uncertainty management capabilities and the sampling efficiency of knowledge-gradient related policies. The models provide an innovative statistical learning perspective to NDPU, which has mainly been studied as an optimization problem. The new formulation is intuitive to understand and easily applicable to similar discrete optimization problems such as the Optimal Sensor Location problem, Uncapcitated Fixed Charge Facility Location problem, etc. We believe the models themselves as well as this unique statistical perspective is of great interest and value for transportation network modelers and simulation optimization practitioners.