Browsing by Author "Wei, Yehua"

This dissertation explores the development and analysis of new algorithms for sequential decision-making under uncertainty, with a focus on optimizing operations and resource allocations within online marketplaces such as e-commerce and rental platforms. The research initially revisits and expands upon the multi-item order fulfillment model, introducing dynamic policies that combine randomized fulfillment strategies, prophet inequalities, and subgradient methods. Our approaches not only achieve asymptotic optimality and strong approximation guarantees in the multi-item fulfillment setting, but also provide insights on how to construct robust policies in scenarios where you have limited resources. The findings in this dissertation introduce a novel approach to the management of resources in complex environments, presenting a nearly optimal framework for developing policies tailored to the complexities of multi-item order fulfillment. Moreover, our analysis can be extended into the domain of rental operations, showcasing the flexibility and broad applicability of our proposed solutions.

In addition, the dissertation addresses the complexities of online recommendation systems through a contextual bandit framework, examining both full-feedback and bandit-feedback settings. By formulating the problem to accommodate arbitrary mappings from user contexts to product feature values, this research provides new online algorithms that effectively minimize regret. The analysis extends to general policy classes, revealing an inherent trade-off between approximation accuracy and statistical error for a given policy class.

Collectively, this work advances theoretical knowledge in sequential decision-making and algorithm design, providing actionable strategies for improving decision-making processes such as fulfillment and recommendations in online marketplaces.

This dissertation studies the optimal design and performance evaluation of large-scale supply chain systems with graphical structures such as assemble-to-order (ATO) systems and e-commerce fulfillment networks. It consists of three essays.

The first essay studies the design of effective operational policies in the assemble-to-order (ATO) systems. We consider continuous-review ATO systems with general bills of materials (BOM) and general leadtimes. First, we characterize the asymptotically optimal policy for the M-system. The policy consists of a periodic review priority (PRP) allocation rule and a coordinated base-stock (CBS) replenishment policy. We then construct heuristic policies using insights from the asymptotically optimal policy. In particular, we adopt the PRP allocation rule and develop a decomposition approach for inventory replenishment. This approach decomposes a general system into a set of assembly subsystems and constructs a linear program to compute the optimal policy parameters. However, both the CBS and the assembly decomposition approach are limited to simple systems. We then consider a second approach, which decomposes a system into a set of distribution subsystems and each subsystem has a straightforward optimal solution, which is similar to the newsvendor problem. Finally, in a numeral test, we find that the assembly decomposition is very effective but computationally expensive and thus only good for small-scale systems; the distribution decomposition performs as effective as the optimal independent base-stock (IBS) policy, but is highly scalable than finding the optimal IBS policy for large-scale systems.

The second essay focuses on optimizing the operational decision at one layer of the supply chain network when some operational decisions at another layer are unknown to the decision-maker. More specifically, we consider the transportation network design problem for the e-commerce marketplace. A salient feature in this problem is decentralized decision-making. While the middle-mile manager decides the network configuration on a weekly or bi-weekly basis, the real-time flows of millions of packages on any given network configuration (which we call the flow response) are controlled by a fulfillment policy employed by a different decision entity. Thus, we face a fixed-cost network design problem with unknown flow response. To meet this challenge, we first develop a predictive model for the unknown response leveraging observed shipment data and machine learning techniques. Apart from the most natural network-level predictive model, we find that the more parsimonious destination-level and arc-level predictive models are more effective. We then embed the predictive model to the original network design problem and characterize this transformed problem as a c-supermodular minimization problem. We develop a linear-time algorithm with an approximation guarantee that depends on c. We demonstrate that this algorithm is scalable and effective in a numerical study.

The third essay investigates how to use the Graph Neural Network (GNN) model to predict the operational performances of supply chain networks. GNN is a newly developed machine learning tool to leverage the graphical structure information. It has demonstrated good prediction accuracy in various contexts, including social, bioinformatics and citation networks. Surprisingly, GNNs have not received much attention in supply chain systems despite the fact that many systems exhibit a graphical structure, such as assemble-to-order systems and process flexibility networks. To the best of our knowledge, we are the first to explore the application of GNN to supply chain problems. As operational performances of the entire network can often be decomposed into node-level or edge-level performances, we study both node-level and edge-level predictions. We find that while the existing GNN model can generate reasonable node-level predictions, special tailoring is needed for edge-level predictions of supply chain networks. A key contribution of our research is to develop a novel graph transformation approach, which allows an edge to learn from its neighborhood edges. Tested on different synthetic datasets from two different supply chain systems, we implement the GNN model with our proposed graph transformation and several benchmark methods, including an existing GNN model and the traditional machine learning methods, such as the convolutional neural network and random forest. The results indicate that our approach significantly outperforms the benchmarks in edge-level prediction. We also observe the importance of utilizing the graphical structure and edge directions. Our comparison reveals that it is beneficial to start with node-level or edge-level predictions and then aggregate them together for the graph-level prediction, instead of the direct graph-level prediction commonly used in other applications.

This dissertation studies operations management problems in service operations and supply chains, analyzing the impact of strategic customers and disruptive technologies. We investigate three problems, and insights from the study of each one illuminate the effect of information and/or strategic customer behavior on decision makers in operations management systems.

The first problem involves the strategic routing behavior of customers in a service network with multiple stations, when customers can choose the order of stations that they visit. We propose a two-station game with all customers present at the start of service and deterministic service times, and we find that strategic customers "herd," i.e., in equilibrium all customers choose the same route. For unobservable systems, we prove that the game is supermodular, and we then identify a broad class of learning rules---which includes both fictitious play and Cournot best-response---that converges to herding in finite time. By combining different theoretical and numerical analyses, we find that the herding behavior is prevalent in many other congested open-routing service networks, including those with arrivals over time, those with stochastic service times, and those with more than two stations. We also find that the system under herding performs very close to the first-best outcome in terms of cumulative system time.

The second problem relates to a disruptive, on-demand delivery platform who provides delivery from an independent sit-down restaurant. Food delivery platforms maintain a symbiotic relationship with the existing providers in their industry; rather than "stealing" demand from an established player, these platforms work with restaurants to connect customers with the restaurant's product by providing an additional purchase channel. We model the restaurant as a queueing system with customer waiting costs. First, we solve the revenue maximization problem faced by a monopolist who controls both the dine-in and delivery prices and receives all revenues from the system. These results are related to the priority queueing and pricing literature and are of independent interest. We also demonstrate that a coordination problem exists between the restaurant and platform. We then investigate means of coordinating this supply chain via different contracts between the restaurant and the platform. We find that a two-way revenue-sharing contract coordinates the supply chain.

Finally, our third problem is spawned from an industry collaboration aimed at improving the inventory planning decisions of a company that sells high-tech goods with short life cycles. We develop a novel heuristic based on a power approximation in the extant literature. The power approximation computes near-optimal (s,S) policies for infinite-horizon inventory problems. We propose a new form of this approximation, devised using real demand data from our industry partner, and a heuristic based on the approximation that updates the inventory policy as new demand forecasts are generated. We evaluate the performance of our heuristic---also on real demand data, though for a different time period and for different items than were used to fit our model---and find that it performs quite well.

In recent years, there has been an explosion of online platforms and E-commerce, which generate massive amounts of network data. For example, a friend link on Facebook represents a connection between users, and a rating on Amazon is a connection between a customer and a product. These network data contain extensive information on customers' behaviors and preferences. However, deriving meaningful insights from the data can be challenging. On the one hand, networks are often extremely large and have millions of nodes and billions of edges. On the other hand, the network can be sparse, given that some nodes interact only with a few other nodes with a significant amount of noise from missing or faulty connections. Thus, extracting valuable information from such noisy and vast amounts of data requires highly efficient approaches that can process a large amount of data and detect tenuous statistical signatures. As such, my thesis has developed along the following two interrelated streams.

The first stream aims at developing the fundamental limits and designing simple and scalable algorithms for learning complex networks. We base our study upon the decision-theoretic framework wherein an unknown structure underlies the network data. We aim to detect and recover this hidden structure based on partial or noisy observation. In particular, we focus on the problem of graph matching (network alignment), which refers to finding the bijection between the vertex sets of the two graphs that maximizes the total number of common edges. We have initiated a statistical analysis of detection and recovery problems by matching two randomly generated graphs with an underlying vertex correspondence and correlated edges. We characterize the sharp fundamental limits for both problems and develop new algorithms that are the first to achieve detection and recovery with an explicit constant correlation for both sparse and dense regimes, which settled important open problems in this field.

The second stream focuses on improving network systems' decision-making efficiency under uncertainties and limited information. We study the dynamic matching problem in which a new agent enters the market randomly and waits to be matched, and the arrival rates for different types of agents are unknown. The goal is to maximize market efficiency and, at the same time, reduce the wait time for each participant in the system. This problem is inspired by the car-pooling platform, in which after they make a request, riders may have to wait on the platform for some time for potential matches with other riders traveling in the same direction based on their pick-up and drop-off locations. We develop hindsight-optimal primal-dual policies that achieve both constant regret and wait time for each type of agent on average at all times.

This dissertation considers complex operational settings with uncertain demand. We consider three classes of problems, and show that for each one, a well designed policy can give close to optimal performance for either cost or profit metrics. To prove our results we use a variety of techniques from the theory of optimization and applied probability.

First, we study assemble-to-order (ATO) problems, where a set of products are assembled from a set of common components. ATO problems with general structure and integrality constraints are well known to be difficult to solve, and we provide new insight into these issues by establishing worst-case approximation guarantees through various primal-dual analyses and LP rounding. First, we relax the one-period ATO problem using a natural newsvendor decomposition and use the dual solution for the relaxation to derive a lower bound on optimal cost, providing a tight approximation guarantee that grows with the maximum product size in the system. Then, we present LP rounding algorithms that achieve both asymptotic optimality as demand grows large, and a 1.8 approximation factor for any problem instance. Finally, we demonstrate that our one-period LP rounding results can be extended to analyze dynamic ATO problems. Specifically, we use our rounding scheme to develop an asymptotically optimal integral policy for dynamic ATO problems with backlogging and identical component lead-times.

In the second class of problems, we consider a two-sided market with heterogeneous and stochastic values of matches between different units of supply and demand (such as those embedded in a network). With limited resources, a service provider can only choose a subset of locations in the market where matches can be made, and wants to choose a subset maximizing the expected value of matches. This problem captures decisions in a wide range of application domains, including those faced by franchise service providers, transportation-service platforms, and online advertisers. We demonstrate that the problem is NP-hard to approximate with a factor better than 1.58, and that the objective function does not enjoy the classic submodularity property, which would allow the application of known approximation guarantees for submodular function maximization. To overcome these hurdles, we propose a generalization of submodularity, called cover modularity, which allows us to prove approximation guarantees of 3 and 2.31 for an exchange algorithm and greedy algorithm, respectively. In order to establish these results, we prove general approximation guarantees for cover modular functions.

For the final problem, we apply the classical operations management strategy of flexibility design to the context of online retailing fulfillment. More specifically, our method helps online retailers to make the strategic selection of a flexible fulfillment network and to improve their tactical decisions on which distribution center to use to fulfill online orders. To derive our results and insights, we use LP-based asymptotic analysis, stochastic programming, concepts from revenue management, and numerical simulations. We collaborate with a large online retailer to propose a data-driven online resource allocation model which captures the key features of the retailer's fulfillment network. We identify settings where the naive greedy policy performs poorly, and propose a spillover limit policy that is asymptotically optimal under a general setting. Finally, we use the spillover limit policy and a stochastic programming allocation policy to evaluate the benefit of a proposed flexible fulfillment network using data from our industrial collaborator. We estimate that our proposed flexible fulfillment network decreases the lost sales plus fulfillment costs by one percent, which equates to a profit improvement on the order of tens of millions of U.S. dollars.