An official website of the United States government
We study the problem of maximizing payoff generated over a period of time in a general class of closed queueing networks with a finite, fixed number of supply units that circulate in the system. Demand arrives stochastically, and serving a demand unit (customer) causes a supply unit to relocate from the “origin” to the “destination” of the customer. The key challenge is to manage the distribution of supply in the network. We consider general controls including customer entry control, pricing, and assignment. Motivating applications include shared transportation platforms and scrip systems. Inspired by the mirror descent algorithm for optimization and the backpressure policy for network control, we introduce a rich family of mirror backpressure (MBP) control policies. The MBP policies are simple and practical and crucially do not need any statistical knowledge of the demand (customer) arrival rates (these rates are permitted to vary in time). Under mild conditions, we propose MBP policies that are provably near optimal. Specifically, our policies lose at most [Formula: see text] payoff per customer relative to the optimal policy that knows the demand arrival rates, where K is the number of supply units, T is the total number of customers over the time horizon, and η is the demand process’ average rate of change per customer arrival. An adaptation of MBP is found to perform well in numerical experiments based on data from NYC Cab. This paper was accepted by Gabriel Weintraub, revenue management and market analytics. Funding: Y. Kanoria was supported by the National Science Foundation’s Division of Civil, Mechanical, and Manufacturing Innovation [Grant CMMI-1653477]. Supplemental Material: The data files and online appendices are available at https://doi.org/10.1287/mnsc.2023.4934 .
more »
« less
State Dependent Control of Closed Queueing Networks
We study the design of state dependent control for a closed queueing network model, inspired by shared transportation systems such as ridesharing. In particular, we focus on the design of assignment policies, wherein the platform can choose which supply unit to dispatch to meet an incoming customer request. The supply unit subsequently becomes available at the destination after dropping the customer. We consider the proportion of dropped demand in steady state as the performance measure. We propose a family of simple and explicit state dependent policies called Scaled MaxWeight (SMW) policies and prove that under the complete resource pooling (CRP) condition (analogous to a strict version of Hall's condition for bipartite matchings), any SMW policy induces an exponential decay of demand-dropping probability as the number of supply units scales to infinity. Furthermore, we show that there is an SMW policy that achieves the optimal exponent among all assignment policies, and analytically specify this policy in terms of the matrix of customer-request arrival rates. The optimal SMW policy protects structurally under-supplied locations.
more »
« less
- Award ID(s):
- 1653477
- PAR ID:
- 10061491
- Date Published:
- Journal Name:
- SIGMETRICS '18 Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems
- Page Range / eLocation ID:
- 2 to 4
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Problem definition: Inspired by new developments in dynamic spectrum access, we study the dynamic pricing of wireless Internet access when demand and capacity (bandwidth) are stochastic. Academic/practical relevance: The demand for wireless Internet access has increased enormously. However, the spectrum available to wireless service providers is limited. The industry has, thus, altered conventional license-based spectrum access policies through unlicensed spectrum operations. The additional spectrum obtained through these operations has stochastic capacity. Thus, the pricing of this service by the service provider has novel challenges. The problem considered in this paper is, therefore, of high practical relevance and new to the academic literature. Methodology: We study this pricing problem using a Markov decision process model in which customers are posted dynamic prices based on their bandwidth requirement and the available capacity. Results: We characterize the structure of the optimal pricing policy as a function of the system state and of the input parameters. Because it is impossible to solve this problem for practically large state spaces, we propose a heuristic dynamic pricing policy that performs very well, particularly when the ratio of capacity to demand rate is low. Managerial implications: We demonstrate the value of using a dynamic heuristic pricing policy compared with the myopic and optimal static policies. The previous literature has studied similar systems with fixed capacity and has characterized conditions under which myopic policies perform well. In contrast, our setting has dynamic (stochastic) capacity, and we find that identifying good state-dependent heuristic pricing policies is of greater importance. Our heuristic policy is computationally more tractable and easier to implement than the optimal dynamic and static pricing policies. It also provides a significant performance improvement relative to the myopic and optimal static policies when capacity is scarce, a condition that holds for the practical setting that motivated this research.more » « less
-
Gentry, E; Ju, F; Liu, X (Ed.)This research investigates optimal pricing strategies in a service-providing queueing system where customers may renege before service completion. Prices are quoted upon customer arrivals and the incoming customers join the system if their willingness to pay exceeds the quoted price. While waiting in line or during service, customers may get impatient and leave without service, incurring an abandonment cost. There is also a per-unit time per-customer holding cost. Our objective is to maximize the long-run average profit through optimal pricing policies. We model the problem as a Markov decision process and identify the optimal pricing using policy iteration. We also study the structure of the optimal pricing policy. Furthermore, we show that under mild assumptions, the optimal price increases as the number of customers in the system increases. When those assumptions do not hold, optimal price decreases and then increases as the number of customers in the system grows.more » « less
-
Gentry, E; Ju, F; Liu, X (Ed.)This research investigates optimal pricing strategies in a service-providing queueing system where customers may renege before service completion. Prices are quoted upon customer arrivals and the incoming customers join the system if their willingness to pay exceeds the quoted price. While waiting in line or during service, customers may get impatient and leave without service, incurring an abandonment cost. There is also a per-unit time per-customer holding cost. Our objective is to maximize the long-run average profit through optimal pricing policies. We model the problem as a Markov decision process and identify the optimal pricing using policy iteration. We also study the structure of the optimal pricing policy. Furthermore, we show that under mild assumptions, the optimal price increases as the number of customers in the system increases. When those assumptions do not hold, optimal price decreases and then increases as the number of customers in the system grows.more » « less
-
Reverse logistics has been gaining recognition in practice (and theory) for helping companies better match supply with demand, and thus reduce costs in their supply chains. In this paper, we study reverse logistics from the perspective of a supply chain in which each location can initiate multiple flows of product. Our first objective is to jointly optimize ordering decisions pertaining to regular, reverse and expedited flows of product in a stochastic, multi-stage inventory model of a logistics supply chain, in which the physical transformation of the product is completed at the most upstream location in the system. Due to those multiple flows of product, the feasible region for the problem acquires multi-dimensional boundaries that lead to the curse of dimensionality. To address this challenge, we develop a different solution method that allows us to reduce the dimensionality of the feasible region and, subsequently, identify the structure of the optimal policy. We refer to this policy as a nested echelon base-stock policy, as decisions for different product flows are sequentially nested within each other. We show that this policy renders the model analytically and numerically tractable. Our results provide actionable policies for firms to jointly manage three different product flows in their supply chains, and allow us arrive at insights regarding the main drivers of the value of reverse logistics. One of our key findings is that, when it comes to the value generated by reverse logistics, demand variability (i.e., demand uncertainty across periods) matters more than demand volatility (i.e., demand uncertainty within each period). This is because, in the absence of demand variability, it is effectively never optimal to return product upstream, regardless of the level of inherent demand volatility. Our second objective is to extend our analysis to product transforming-supply chains, in which product transformation is allowed to occur at each location. In such a system, it becomes necessary to keep track of both the location and stage of completion of each unit of inventory, so that the number of state and decisions variables increases with the square of the number of locations in the system. To analyze such a supply chain, we first identify a policy that provides a lower bound on the total cost. Then, we establish a special decomposition of the objective cost function that allows us to propose a novel heuristic policy. We find that the performance gap of our heuristic policy relative to the lower-bounding policy averages less than 5% across a range of parameters and supply chain lengths.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1145/3219617.3219619
