An official website of the United States government
We consider a fundamental pricing model in which a fixed number of units of a reusable resource are used to serve customers. Customers arrive to the system according to a stochastic process and, upon arrival, decide whether to purchase the service, depending on their willingness to pay and the current price. The service time during which the resource is used by the customer is stochastic, and the firm may incur a service cost. This model represents various markets for reusable resources, such as cloud computing, shared vehicles, rotable parts, and hotel rooms. In the present paper, we analyze this pricing problem when the firm attempts to maximize a weighted combination of three central metrics: profit, market share, and service level. Under Poisson arrivals, exponential service times, and standard assumptions on the willingness-to-pay distribution, we establish a series of results that characterize the performance of static pricing in such environments. In particular, although an optimal policy is fully dynamic in such a context, we prove that a static pricing policy simultaneously guarantees 78.9% of the profit, market share, and service level from the optimal policy. Notably, this result holds for any service rate and number of units the firm operates. Our proof technique relies on a judicious construction of a static price that is derived directly from the optimal dynamic pricing policy. In the special case in which there are two units and the induced demand is linear, we also prove that the static policy guarantees 95.5% of the profit from the optimal policy. Our numerical findings on a large test bed of instances suggest that the latter result is quite indicative of the profit obtained by the static pricing policy across all parameters.
more »
« less
This content will become publicly available on March 5, 2026
Joint Placement, Delivery Promise, and Fulfillment in Online Retail
We consider the placement, delivery promise, and fulfillment decisions of an online retailer. We have a set of products with given numbers of units to be placed at capacitated fulfillment centers. Once we make the placement decisions, we face demands for the products arriving from different demand regions randomly over time. In response to each demand, we pick a delivery promise to offer, which determines the probability that the demand converts into sales as well as choose a fulfillment center to use to serve the demand. Our goal is to decide where to place the units at the beginning of the selling horizon and to find a policy to make delivery promise and fulfillment decisions over the selling horizon so that we maximize the total expected profit. We give an approximation strategy to obtain solutions with performance guarantees for this joint placement, delivery promise, and fulfillment problem. In our approximation strategy, we construct a bounding function that upper bounds the total expected profit from the delivery promise and fulfillment policy when viewed as a function of the placement decisions. To make the placement decisions, we maximize the bounding function subject to the capacity constraints at the fulfillment centers. To make the delivery promise and fulfillment decisions, we construct a policy that obtains a constant fraction of the bounding function. Using our approximation strategy with appropriate bounding functions, we obtain a solution with a constant factor performance guarantee, but if the size of the system, measured by the numbers of units that we need to place and capacities of the fulfillment centers, is large, then we get an asymptotically optimal solution. We compare our approximation strategy with approaches that ignore the interactions between the placement, delivery promise, and fulfillment decisions as well as heuristics that are based on Lagrangian relaxation, demonstrating that our approximation strategy compares quite favorably.
more »
« less
- Award ID(s):
- 2226900
- PAR ID:
- 10592344
- Publisher / Repository:
- INFORMS (Institute for Operations Research and the Management Sciences)
- Date Published:
- Journal Name:
- Management Science
- ISSN:
- 0025-1909
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We propose a new algorithmic framework for traffic-optimal virtual network function (VNF) placement and migration for policy-preserving data centers (PPDCs). As dy- namic virtual machine (VM) traffic must traverse a sequence of VNFs in PPDCs, it generates more network traffic, consumes higher bandwidth, and causes additional traffic delays than a traditional data center. We design optimal, approximation, and heuristic traffic-aware VNF placement and migration algorithms to minimize the total network traffic in the PPDC. In particular, we propose the first traffic-aware constant-factor approximation algorithm for VNF placement, a Pareto-optimal solution for VNF migration, and a suite of efficient dynamic-programming (DP)-based heuristics that further improves the approximation solution. At the core of our framework are two new graph- theoretical problems that have not been studied. Using flow characteristics found in production data centers and realistic traffic patterns, we show that a) our VNF migration techniques are effective in mitigating dynamic traffic in PPDCs, reducing the total traffic cost by up to 73%, b) our VNF placement algorithms yield traffic costs 56% to 64% smaller than those by existing techniques, and c) our VNF migration algorithms outperform the state-of-the-art VM migration algorithms by up to 63% in reducing dynamic network traffic.more » « less
-
null (Ed.)We study the dynamic assortment planning problem, where for each arriving customer, the seller offers an assortment of substitutable products and the customer makes the purchase among offered products according to an uncapacitated multinomial logit (MNL) model. Because all the utility parameters of the MNL model are unknown, the seller needs to simultaneously learn customers’ choice behavior and make dynamic decisions on assortments based on the current knowledge. The goal of the seller is to maximize the expected revenue, or, equivalently, to minimize the expected regret. Although dynamic assortment planning problem has received an increasing attention in revenue management, most existing policies require the estimation of mean utility for each product and the final regret usually involves the number of products [Formula: see text]. The optimal regret of the dynamic assortment planning problem under the most basic and popular choice model—the MNL model—is still open. By carefully analyzing a revenue potential function, we develop a trisection-based policy combined with adaptive confidence bound construction, which achieves an item-independent regret bound of [Formula: see text], where [Formula: see text] is the length of selling horizon. We further establish the matching lower bound result to show the optimality of our policy. There are two major advantages of the proposed policy. First, the regret of all our policies has no dependence on [Formula: see text]. Second, our policies are almost assumption-free: there is no assumption on mean utility nor any “separability” condition on the expected revenues for different assortments. We also extend our trisection search algorithm to capacitated MNL models and obtain the optimal regret [Formula: see text] (up to logrithmic factors) without any assumption on the mean utility parameters of items.more » « less
-
Problem definition: We consider network revenue management problems with flexible products. We have a network of resources with limited capacities. To each customer arriving into the system, we offer an assortment of products. The customer chooses a product within the offered assortment or decides to leave without a purchase. The products are flexible in the sense that there are multiple possible combinations of resources that we can use to serve a customer with a purchase for a particular product. We refer to each such combination of resources as a route. The service provider chooses the route to serve a customer with a purchase for a particular product. Such flexible products occur, for example, when customers book at-home cleaning services but leave the timing of service to the company that provides the service. Our goal is to find a policy to decide which assortment of products to offer to each customer to maximize the total expected revenue, making sure that there are always feasible route assignments for the customers with purchased products. Methodology/results: We start by considering the case in which we make the route assignments at the end of the selling horizon. The dynamic programming formulation of the problem is significantly different from its analogue without flexible products as the state variable keeps track of the number of purchases for each product rather than the remaining capacity of each resource. Letting L be the maximum number of resources in a route, we give a policy that obtains at least [Formula: see text] fraction of the optimal total expected revenue. We extend our policy to the case in which we make the route assignments periodically over the selling horizon. Managerial implications: To our knowledge, the policy that we develop is the first with a performance guarantee under flexible products. Thus, our work constructs policies that can be implemented in practice under flexible products, also providing performance guarantees. Funding: The work of H. Topaloglu was partly funded by the National Science Foundation [Grant CMMI-1825406]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2022.0583 .more » « less
-
Amidst the COVID-19 pandemic, restaurants become more reliant on no-contact pick-up or delivery ways for serving customers. As a result, they need to make tactical planning decisions such as whether to partner with online platforms, to form their own delivery team, or both. In this paper, we develop an integrated prediction-decision model to analyze the profit of combining the two approaches and to decide the needed number of drivers under stochastic demand. We first use the susceptible-infected-recovered (SIR) model to forecast future infected cases in a given region and then construct an autoregressive-moving-average (ARMA) regression model to predict food-ordering demand. Using predicted demand samples, we formulate a stochastic integer program to optimize food delivery plans. We conduct numerical studies using COVID-19 data and food-ordering demand data collected from local restaurants in Nuevo Leon, Mexico, from April to October 2020, to show results for helping restaurants build contingency plans under rapid market changes. Our method can be used under unexpected demand surges, various infection/vaccination status, and demand patterns. Our results show that a restaurant can benefit from partnering with third-party delivery platforms when (i) the subscription fee is low, (ii) customers can flexibly decide whether to order from platforms or from restaurants directly, (iii) customers require more efficient delivery, (iv) average delivery distance is long, or (v) demand variance is high.more » « less
