An official website of the United States government
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
Blind Dynamic Resource Allocation in Closed Networks via Mirror Backpressure
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
- Award ID(s):
- 1653477
- PAR ID:
- 10471807
- Publisher / Repository:
- INFORMS
- Date Published:
- Journal Name:
- Management Science
- ISSN:
- 0025-1909
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We consider a long-term average profit–maximizing admission control problem in an M/M/1 queuing system with unknown service and arrival rates. With a fixed reward collected upon service completion and a cost per unit of time enforced on customers waiting in the queue, a dispatcher decides upon arrivals whether to admit the arriving customer or not based on the full history of observations of the queue length of the system. Naor [Naor P (1969) The regulation of queue size by levying tolls. Econometrica 37(1):15–24] shows that, if all the parameters of the model are known, then it is optimal to use a static threshold policy: admit if the queue length is less than a predetermined threshold and otherwise not. We propose a learning-based dispatching algorithm and characterize its regret with respect to optimal dispatch policies for the full-information model of Naor [Naor P (1969) The regulation of queue size by levying tolls. Econometrica 37(1):15–24]. We show that the algorithm achieves an O(1) regret when all optimal thresholds with full information are nonzero and achieves an [Formula: see text] regret for any specified [Formula: see text] in the case that an optimal threshold with full information is 0 (i.e., an optimal policy is to reject all arrivals), where N is the number of arrivals.more » « less
-
Motivated by a service platform, we study a two-sided network where heterogeneous demand (customers) and heterogeneous supply (workers) arrive randomly over time to get matched. Customers and workers arrive with a randomly sampled patience time (also known as reneging time in the literature) and are lost if forced to wait longer than that time to be matched. The system dynamics depend on the matching policy, which determines when to match a particular customer class with a particular worker class. Matches between classes use the head-of-line customer and worker from each class. Since customer and worker arrival processes can be very general counting processes, and the reneging times can be sampled from any finite mean distribution that is absolutely continuous, the state descriptor must track the age-in-system for every customer and worker waiting in order to be Markovian, as well as the time elapsed since the last arrival for every class. We develop a measure-valued fluid model that approximates the evolution of the discrete-event stochastic matching model and prove its solution is unique under a fixed matching policy. For a sequence of matching models, we establish a tightness result for the associated sequence of fluid-scaled state descriptors and show that any distributional limit point is a fluid model solution almost surely. When arrival rates are constant, we characterize the invariant states of the fluid model solution and show convergence to these invariant states as time becomes large. Finally, again when arrival rates are constant, we establish another tightness result for the sequence of fluid-scaled state descriptors distributed according to a stationary distribution and show that any subsequence converges to an invariant state. As a consequence, the fluid and time limits can be interchanged, which justifies regarding invariant states as first order approximations to stationary distributions.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
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1287/mnsc.2023.4934
