Yehua Wei

We study a discrete-time dynamic multiway matching model. There are finitely many agent types that arrive stochastically and wait to be matched. State-of-the-art dynamic matching policies in the literature require the knowledge of all system parameters to determine an optimal basis of the fluid relaxation, and focus on controlling the number of waiting agents using only matches within the optimal basis. In this paper, we propose a primal-dual policy that schedules matches for future arrivals based on an estimator for the dual solution. Our policy does not require the knowledge of the arrival rates and operates with greater flexibility as it does not restrict matches to only the match types within an optimal basis. We show that our policy is the first to achieve constant regret at all times under unknown arrival rates, and when the arrival rates are known, it achieves the optimal scaling. Furthermore, when the arrival rates are known, the primal-dual policy significantly outperforms alternative dynamic matching policies in several numerical simulations. This paper was accepted by Baris Ata, stochastic models and simulation. Funding: J. Xu is supported in part by the National Science Foundation [Grant CCF-1856424 and NSF CAREER award CCF-2144593]. S. H. Yu is supported in part by the National Science Foundation [Grant CCF-1856424]. Supplemental Material: The online appendix and data files are available at https://doi.org/10.1287/mnsc.2023.01668 .

Studying How Inventory Placement Shapes Online Fulfillment Performance A growing share of e-commerce operations involves deciding not only how to fulfill incoming orders, but also where to position inventory beforehand. In “Online Demand Fulfillment Problem with Initial Inventory Placement: A Regret Analysis,” Arlotto, Keskin, and Wei examine how these two decisions interact. The authors introduce a joint regret framework that evaluates the performance of a fulfillment policy together with the initial allocation of inventory across warehouses. Their analysis shows that probabilistic fulfillment inevitably accumulates regret that grows with the length of the planning horizon, regardless of how inventory is initially placed. By contrast, when combined with an appropriate offline inventory placement, the score-based approach achieves a regret bound that remains stable over time and scales only with the size of the system. The study offers insight into the role of initial placement in shaping fulfillment policy performance.

In this work, we revisit the multi-item order fulfillment model introduced by Jasin and Sinha (2015). Specifically, we study a dynamic setting in which an e-commerce platform (or online retailer) with multiple warehouses and finite inventory faces the problem of fulfilling orders that may contain multiple items. The platform’s goal is to minimize the expected cost incurred from the fulfillment process, subject to warehouses’ inventory constraints. Differing from the classical literature on multi-item fulfillment, we use the method-based formulation to design a class of dynamic policies that combine ideas from randomized fulfillment, prophet inequalities, and subgradient methods for the general multi-item fulfillment model. Specifically, by establishing connections between the fulfillment and prophet inequality literature, we prove that our algorithm has strong approximation guarantees in nonasymptotic settings, which also happens to be asymptotically optimal. Our result shows that there is a simple and near-optimal procedure for solving multi-item fulfillment problems once the online retailer has enough inventory, independent of other problem parameters. To the best of our knowledge, this is the first result of this type in the context of multi-item order fulfillment. In addition, and of independent interest, our analysis also leads to new asymptotically optimal bounds for network revenue management problems. This paper was accepted by Omar Besbes, market design, platform, and demand analytics. Supplemental Material: The online appendix and data files are available at https://doi.org/10.1287/mnsc.2023.00357 .

Self-interested customers’ form of reasoning and its consequences for system performance affect the planning decisions of service providers. We study procedurally rational customers—customers who make decisions based on a sample containing anecdotes of the system times experienced by other customers. Specifically, we consider procedurally rational customers in two-station service networks with open routing, that is, customers can choose the order in which to visit the stations. Because some actions may be less represented in the population, a given customer may not succeed in obtaining anecdotes about all possible actions. We introduce a novel sampling framework that extends the procedurally rational framework to incorporate the possibility that a customer may not receive any anecdotes for one of the actions; in this case, the customer uses a prior point estimate in lieu of the missing anecdotes. Under this framework, we study the procedurally rational equilibrium in open routing. We show first that as the sample size grows large, customers’ estimates become more accurate, and the procedurally rational equilibrium converges to the fully rational equilibrium (which is also socially optimal). We then uncover two main findings. First, we obtain bounds on the distance between the procedurally rational and fully rational equilibrium, aiding operational planning and showing the rate of convergence to the fully rational outcome as the sample size of anecdotes of each individual customer grows. Second, if customers obtain anecdotes of both actions with high probability, then the equilibrium will approximate the fully rational outcome, despite the sampling error inherent to procedural rationality.

In this work, we revisit the multi-item order fulfillment model introduced by [Jasin and Sinha 2015]. Specifically, we study a dynamic setting in which an e-commerce platform (or online retailer) with multiple warehouses and finite inventory is faced with the problem of fulfilling orders that may contain multiple items. The platform's goal is to minimize the expected cost incurred from the fulfillment process, subject to warehouses' inventory constraints. Unlike the classical literature on multi-item fulfillment, we propose an alternative offline formulation of the problem. In particular, in our model, the platform sequentially selects methods to fulfill the arriving orders. A method consists of a set of facilities that will determine which warehouses the items will ship from and, more importantly, whether multi-item orders will be split. Under this formulation, we design a class of dynamic policies that combine ideas from randomized fulfillment, prophet inequalities and subgradient methods for the general multi-item fulfillment model. Specifically, by establishing connections between the fulfillment and prophet inequality literature, we prove that our algorithm is both asymptotically optimal and has strong approximation guarantees in non-asymptotic settings. Our result shows that there is a simple and near-optimal procedure for solving multi-item fulfillment problems once the online retailer has enough inventory, independently of other problem parameters. To the best of our knowledge, this is the first result of this type in the context of multi-item order fulfillment. In addition, and of independent interest, our analysis also leads to new asymptotically optimal bounds for network revenue management problems.

The paper “Approximate Submodularity in Network Design Problems” studies general network design problems where a firm strategically selects its network to better match supply and demand in the future. The paper observes that the arcs in network design problems are cover modular, i.e., approximately substitutes with each other, in the sense that local changes in the objective function can be used to bound global changes. The cover modularity is then applied to prove that a set of simple and intuitive heuristics achieve constant factor approximation guarantees in network design problems. Furthermore, the paper demonstrates cover modularity is also present in a general class of linear programming formulations.

We study a discrete-time dynamic multi-way matching model. There are finitely many agent types that arrive stochastically and wait to be matched. State-of-the-art dynamic matching policies in the literature require the knowledge of all system parameters to determine an optimal basis of the fluid relaxation, and focus on controlling the number of waiting agents using only matches in the optimal basis [4,6,7]. In this paper, we propose a primal-dual policy that schedule matches for future arrivals based on an estimator for the dual solution. Our policy does not require the knowledge of optimal bases, and is the first to achieve constant regret at all times under unknown arrival rates. In addition, we show that when the arrival rates are known, the primal-dual policy achieves the optimal scaling as the lower-bound described in [6,7]. Furthermore, we find that when the arrival rates are known, the primal-dual policy can significantly outperform alternative dynamic matching policies in numerical simulations.

We study a discrete-time dynamic multi-way matching model. There are finitely many agent types that arrive stochastically and wait to be matched. State-of-the-art dynamic matching policies in the literature require the knowledge of all system parameters to determine an optimal basis of the fluid relaxation, and focus on controlling the number of waiting agents using only matches in the optimal basis [4,6,7]. In this paper, we propose a primal-dual policy that schedule matches for future arrivals based on an estimator for the dual solution. Our policy does not require the knowledge of optimal bases, and is the first to achieve constant regret at all times under unknown arrival rates. In addition, we show that when the arrival rates are known, the primal-dual policy achieves the optimal scaling as the lower-bound described in [6,7]. Furthermore, we find that when the arrival rates are known, the primal-dual policy can significantly outperform alternative dynamic matching policies in numerical simulations.

Problem definition: Fulfillment flexibility, the ability of distribution centers (DCs) to fulfill demand originating from other DCs, can help e-retailers reduce lost sales and improve service quality. Because the cost of full flexibility is prohibitive, we seek to understand the value of partially flexible fulfillment networks under simple and effective fulfillment policies. Academic/practical relevance: We propose a general method for understanding the practical value of (partial) fulfillment flexibility using a data-driven model, theoretical analysis, and numerical simulations. Our method applies to settings with local fulfillment (i.e., order fulfillment from the originating DC) prioritization and possible customer abandonment, two features that are new to the fulfillment literature. We then apply this method for a large e-retailer. We also introduce a new class of spillover limit fulfillment policies with attractive theoretical and practical features. Methodology: Our analysis uses dynamic and stochastic optimization, applied probability, and numerical simulations. Results: We derive optimal fulfillment policies in stylized settings, as well as bounds on the performance under an optimal policy using theoretical analysis, to provide guidelines on which policies to test in numerical simulations. We then use simulations to estimate for our industrial partner that a proposed fulfillment network with additional flexibility equates to a profit improvement on the order of tens of millions of U.S. dollars. Managerial implications: We provide an approach for e-retailers to understand when fulfillment flexibility is most valuable. We find that fulfillment flexibility provides the most benefit for our collaborator when gross profits are high relative to fulfillment costs or centrally held inventory is low. Also, we identify the risks of myopic fulfillment with additional flexibility and demonstrate that an effective spillover limit policy mitigates these risks. History: This paper has been accepted as part of the 2019 Manufacturing & Service Operations Management Practice-Based Research Competition. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2021.0981 .

Motivated by logistical problems faced by a large supply chain software company, the paper, “A New Approach for Vehicle Routing with Stochastic Demand: Combining Route Assignment with Process Flexibility,” studies a vehicle routing problem where some routes are allowed to overlap. The paper proposes a class of simple and effective strategies to design overlapped routes with customer sharing, which combines ideas from the process flexibility in manufacturing and traditional vehicle routing literatures. Through theoretical analysis and numerical simulations, the paper illustrates the advantage of an overlapped routing strategy with a small amount of customer overlaps. In particular, it shows that such a strategy can provide consistent route assignments to drivers, while achieving a similar expected travel distance as the theoretical benchmark in the fully reoptimized setting. The strategy is in contrast to the traditional fixed routing strategy, which provides consistent route assignments to drivers, but incurs a much higher expected travel distance.