東華大學圖書館 |

Sequential Optimization under Uncertainty : = Models, Algorithms, and Applications.

紀錄類型:	書目-電子資源 : Monograph/item
正題名/作者:	Sequential Optimization under Uncertainty :/
其他題名:	Models, Algorithms, and Applications.
作者:	Yu, Xian.
面頁冊數:	1 online resource (194 pages)
附註:	Source: Dissertations Abstracts International, Volume: 84-01, Section: B.
Contained By:	Dissertations Abstracts International84-01B.
標題:	Operations research. -
電子資源:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=29274940click for full text (PQDT)
ISBN:	9798438774860

Sequential Optimization under Uncertainty : = Models, Algorithms, and Applications.
Yu, Xian.

Sequential Optimization under Uncertainty :Models, Algorithms, and Applications. - 1 online resource (194 pages)

Source: Dissertations Abstracts International, Volume: 84-01, Section: B.

Thesis (Ph.D.)--University of Michigan, 2022.

Includes bibliographical references

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.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2023

Mode of access: World Wide Web

ISBN: 9798438774860Subjects--Topical Terms:

547123
Operations research.
Subjects--Index Terms:

Optimization under uncertaintyIndex Terms--Genre/Form:

542853
Electronic books.

Sequential Optimization under Uncertainty : = Models, Algorithms, and Applications.
LDR:05714nmm a2200469K 4500 001 2358494
005 20230814100730.5
006 m o d
007 cr mn ---uuuuu
008 241011s2022 xx obm 000 0 eng d
020 $a 9798438774860
035 $a (MiAaPQ)AAI29274940
035 $a (MiAaPQ)umichrackham004235
035 $a AAI29274940
040 $a MiAaPQ $b eng $c MiAaPQ $d NTU
100 1 $a Yu, Xian. $3 3699025
245 1 0 $a Sequential Optimization under Uncertainty : $b Models, Algorithms, and Applications.
264 0 $c 2022
300 $a 1 online resource (194 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertations Abstracts International, Volume: 84-01, Section: B.
500 $a Advisor: Shen, Siqian.
502 $a Thesis (Ph.D.)--University of Michigan, 2022.
504 $a Includes bibliographical references
520 $a 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.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2023
538 $a Mode of access: World Wide Web
650 4 $a Operations research. $3 547123
650 4 $a Industrial engineering. $3 526216
650 4 $a Mathematics. $3 515831
650 4 $a Computer science. $3 523869
650 4 $a Logic. $3 529544
650 4 $a Information science. $3 554358
653 $a Optimization under uncertainty
653 $a Multistage Sequential Decision-Making
653 $a Distributionally robust optimization
653 $a Stochastic programming
653 $a Dynamic programming
653 $a Mixed-integer semidefinite/linear programming
653 $a Sequential optimization
655 7 $a Electronic books. $2 lcsh $3 542853
690 $a 0796
690 $a 0546
690 $a 0984
690 $a 0723
690 $a 0405
690 $a 0395
710 2 $a ProQuest Information and Learning Co. $3 783688
710 2 $a University of Michigan. $b Industrial & Operations Engineering. $3 3344010
773 0 $t Dissertations Abstracts International $g 84-01B.
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=29274940 $z click for full text (PQDT)