Sequential Optimization Under Uncertainty: Models, Algorithms, and Applications

Abstract

The primary focus of this dissertation is to develop mathematical models and solution approaches for sequential decision-making and optimization under uncertainty, with applications in transportation, logistics, and healthcare-related operations management. In real-world applications, system operators often need to make sequential decisions, that may involve both discrete and continuous variables under data uncertainties. These problems can be modeled by multistage stochastic integer programs (MS-SIP) that are, however, computationally intractable due to the well-known “curse of dimensionality” issue. MS-SIP assume that the distributions of uncertainty parameters are known and one has access to a finite number of samples of the distributions. In contrary to MS-SIP, multistage distributionally robust integer programs (MS-DRIP) make no assumption on distributions of uncertain parameters. Instead, the optimal solutions are sought for the worst-case probability distributions within a family of candidate distributions, namely, the ambiguity set. Compared to multistage sequential decision models, the two-stage counterparts, namely TS-SIP and TS-DRIP, are easier to solve, where planning decisions are made before uncertainty realizes. In this dissertation, we investigate the four models by developing highly efficient and scalable algorithms and recommend the most practical one in the context of designing and operating complex service systems.

Specifically, in Chapter 2, we first study MS-DRIP under endogenous uncertainty, where the probability distribution of stage-wise uncertainty depends on the decisions made in previous stages. We derive mixed-integer linear programming or mixed-integer semidefinite programming reformulations for the min-max Bellman equations, and for the latter we show how to obtain upper and lower bounds of the optimal objective value. We employ the Stochastic Dual Dynamic integer Programming method for solving the resultant MS-SIP. Our numerical results based on facility-location instances show the computational efficacy of our approaches and demonstrate the cost effectiveness of considering decision-dependent uncertainty in the dynamic risk-aware optimization framework.

In Chapter 3, we examine the gaps between MS-SIP and TS-SIP with facility-location instances. It remains an open question to bound the gap between these two models using risk-averse objective functions, which indicates at least how much benefits we can gain from solving a more complex multistage model. We provide tight lower bounds for the gaps between optimal objective values of risk-averse multistage stochastic facility location models and their two-stage counterparts using expected conditional risk measures. To speed up computation, two approximation algorithms are proposed to efficiently solve risk-averse TS-SIP and MS-SIP.

The aforementioned models and approaches can be applied to a wide range of applications, including smart transportation and mobility-as-a-service. In Chapter 4, we first consider integrated vehicle routing and service scheduling problems with either customer-imposed or self-imposed time windows. We propose TS-SIP to optimize vehicle routes and estimated arrival time or time windows to reduce customers’ waiting, vehicle idleness, and overtime. To fulfill real-time arrived service requests, we develop K-means clustering-based algorithms to dynamically update planned routes and schedules, which can quickly compute high-quality solutions for large-scale instances.

Finally, in Chapter 5, we extend the TS-SIP for vehicle routing and service scheduling to cover on-demand ride pooling requests, where we dynamically match available drivers to randomly arriving passengers and also decide pick-up and drop-off routes. We design a spatial-and-temporal decomposition scheme and apply Approximate Dynamic Programming (ADP) to improve computation. Our ADP approach reduces the unsatisfied demand rate dramatically compared to other benchmarks that do not incorporate future information or pooling options.