Adaptive Optimization and Learning for Service Systems
Huiwen Jia · Deep Blue (University of Michigan) · 2022
The primary focus of this dissertation is to develop adaptive optimization and learning models and algorithms for decision-making problems under uncertainty arising in service systems. Thanks to the accessibility and analyzability of voluminous data, the uncertainties can be better controlled by adaptively incorporating real-time information. The common theme of the problems in different chapters of this thesis embraces the structures of (i) making adaptive decisions for accomplishing a learning task and (ii) learning the nature of the uncertainty for adaptively optimizing future decisions. Specifically, we apply and innovate machine learning and reinforcement learning techniques, including support vector machines (SVM), deep neural networks (DNN), and multi-armed bandits (MAB), to solve problems that arise in modern service systems, such as transportation, resource sharing/rental services. A well-designed and reliable route planner is central to a wide range of modern transportation applications. We consider two cases, providing route recommendations to several travel requests or a single request. Providing route recommendations to a fleet of vehicles under uncertainty always results in large-scale stochastic programs, of which the solving process is time-consuming even with sophisticated decomposition algorithms. Therefore, in Chapter 2, we propose a learning-enhanced Benders decomposition (LearnBD) algorithm to reduce the solving time for two-stage stochastic programs. This algorithm can also be used for solving general two-stage stochastic programs. In Chapter 3, we design and implement an approach for providing route recommendations to one origin-destination pair via a combination of the weighted shortest path problem and deep learning with real-world transportation data. Revenue management with reusable resources finds a wide range of service systems in today's economy, such as cloud computing services, ride-hailing services, and car/bicycle rental services. The service-providing firm aims to construct a dynamic pricing control to maximize the total revenue. The dynamic nature of reusable resources being committed over time makes this revenue management problem highly challenging, especially when the firm does not know the mappings between customer demand and the offered prices. Chapter 4 considers a single product and a single resource setting and Chapter 5 considers a multi-products multi-resource setting. We formulate the revenue management problem as a multi-armed bandits (MAB) problem and develop pricing algorithms by leveraging upper confidence bound (UCB) and Thompson sampling (TS) algorithms. Overall, the contributions of this dissertation are threefold. First, we develop a LearnBD algorithm to accelerate the solving process of two-stage stochastic programs, and our numerical results of diverse instances show that LearnBD can achieve better computational performance than transitional Benders decomposition. Second, we combine deep learning and the weighted shortest path problem to build a weight learning and context-aware route recommendation system. We use real historical request data that was collected from a ride-hailing company to train and test the proposed recommendation system. The computational results indicate that the routes suggested by this new system can achieve a high acceptance ratio. Third, we are among the first to study price-based revenue management problems with reusable resources under incomplete demand information. We develop new MAB algorithms for both single-product and multi-product multi-resource settings. A novel aspect of our proposed algorithmic framework is to bound the mixing time loss during transient states between price changes. We derive theoretical regret bounds that match the lower bound up to a logarithmic factor and demonstrate the numerical performances by experiments over various instances.