Approximate dynamic programming for capacity allocation in the service industry

We consider a problem where different classes of customers can book different types of service in advance and the service company has to respond immediately to the booking request confirming or rejecting it. The objective of the service company is to maximize profit made of class-type specific revenues, refunds for cancellations or no-shows as well as cost of overtime. For the calculation of the latter, information on the underlying appointment schedule is required. In contrast to most models in the literature we assume that the service time of clients is stochastic and that clients might be unpunctual. Throughout the paper we will relate the problem to capacity allocation in radiology services. The problem is modeled as a continuous-time Markov decision process and solved using simulation-based approximate dynamic programming (ADP) combined with a discrete event simulation of the service period. We employ an adapted heuristic ADP algorithm from the literature and investigate on the benefits of applying ADP to this type of problem. First, we study a simplified problem with deterministic service times and punctual arrival of clients and compare the solution from the ADP algorithm to the optimal solution. We find that the heuristic ADP algorithm performs very well in terms of objective function value, solution time, and memory requirements. Second, we study the problem with stochastic service times and unpunctuality. It is then shown that the resulting policy constitutes a large improvement over an “optimal” policy that is deduced using restrictive, simplifying assumptions.     

Outpatient appointment scheduling given individual day-dependent no-show predictions

This paper examines the combined use of predictive analytics, optimization, and overbooking to schedule outpatient appointments in the presence of no-shows. We tackle the problem of optimally overbooking appointments given no-show predictions that depend on the individual appointment characteristics and on the appointment day. The goal is maximizing the number of patients seen while minimizing waiting time and overtime. Our analysis leads to the definition of a near-optimal and simple heuristic which consists of giving same-day appointments to likely shows and future-day appointments to likely no-shows. We validate our findings by performing extensive simulation tests based on an empirical data set of nearly fifty thousand appointments from a real outpatient clinic. The results suggest that our heuristic can lead to a substantial increase in performance and that it should be preferred to open access under most parameter configurations. Our paper will be of great interest to practitioners who want to improve their clinic performance by using individual no-show predictions to guide appointment scheduling.     

Analysis of seat allocation and overbooking decisions with hybrid information

We investigate a single-leg airline revenue management problem where an airline has limited demand information and uncensored no-show information. To use such hybrid information for simultaneous overbooking and booking control decisions, we combine expected overbooking cost with revenue. Then we take a robust optimization approach with a regret-based criterion. While the criterion is defined on a myriad of possible demand scenarios, we show that only a small number of them are necessary to compute the objective. We also prove that nested booking control policies are optimal among all deterministic ones. We further develop an effective computational method to find the optimal policy and compare our policy to others proposed in the literature.     

基于机票超售模型的高校图书馆网上预约管理策略

由于图书预约管理体制的不完善,预约借书成功率不高,大量预约登记图书滞留,严重影响图书的流通,因此合理可行的预约管理方案是各高校图书馆共同的迫切需求.基于机票超售模型,结合高校图书馆的实际情况,根据预约者是否按时来图书馆领取预约图书,总体分析复本数、预约期限、预约成功率与图书滞留天数的关系,应用Matlab7.0求解最佳的预约方案来减少预约服务造成的图书滞留.并且以天津大学图书馆为例验证模型效果,以图书滞留天数衡量预约图书流通情况,应用高校图书预约模型对预约方案进行改进,使得预约图书滞留天数明显减少,成功达到提高预约图书流通率,更好地为高校师生服务的目的.     

考虑存在取消预约情形的门诊预约能力分配策略

在现实的门诊预约问题中,已经预约的患者在接收医疗服务之前,有可能取消先前的预约,这会对医院的收益造成负面影响,如何在考虑患者存在取消预约的情形下,设计合理有效的能力分配策略来保证医院的收益,是一个值得研究的问题.本文针对具有提前预约和当天预约的门诊预约能力分配问题,在考虑提前预约患者可能存在取消预约行为的情形下,提出了一种提前预约患者和当天预约患者的最优能力分配策略。文中首先以医院的期望收益最大作为决策目标,建立了存在取消预约患者的医疗预约问题的马尔科夫过程模型,并给出了该模型的相关性质;基于所建立模型的特征,证明了对于任意的提前预约时段,存在提前预约患者的最佳数量,进而给出了提前预约患者和当天预约患者的最优能力分配策略以及确定该策略的精确算法;最后,通过数值试验说明了本文所提出的能力分配策略的适用性和有效性。     

Two-dimensional cargo overbooking models

This paper introduces two-dimensional (weight and volume) overbooking problems arising mainly in the cargo revenue management, and compares them with one-dimensional problems. It considers capacity spoilage and cargo offloading costs, and minimizes their sum. For one-dimensional problems, it shows that the optimal overbooking limit does not change with the magnitude of the booking requests. In two-dimensional problems, the overbooking limit is replaced by a curve. The curve, along with the volume and weight axes, encircles the acceptance region. The booking requests are accepted if they fall within this region. We present Curve (Cab) and Rectangle (Rab) models. The boundary of the acceptance region in the Cab (resp. Rab) model is a curve (resp. rectangle). The optimal curve for the Cab model is shown to be unique and continuous. Moreover, it can be obtained by solving a series of simple equations. Finding the optimal rectangle for the Rab model is more challenging, so we propose an approximate rectangle. The approximate rectangle is a limiting solution in the sense that it converges to the optimal rectangle as the booking requests increase. The approximate rectangle is numerically shown to yield costs that are very close to the optimal costs.     

随机服务时间下异质患者门诊预约调度优化

考虑随机服务时间与行为特征互不相同的异质患者,建立随机混合整数规划模型对门诊预约调度问题展开研究。首先在给定服务顺序的假设下求解了两个患者的预约调度问题;在此基础上,设计启发式算法对多个患者预约方案和服务顺序同时进行优化。数值结果表明:当患者服务时间为独立同分布的随机变量时,患者预约时间间隔呈现先增加后减少的圆顶形状;当患者服务时间服从不同分布时,通过与样本平均近似方法对比,验证了启发式算法的计算效率和有效性。     

Clinic scheduling models with overbooking for patients with heterogeneous no-show probabilities

Clinical overbooking is intended to reduce the negative impact of patient no-shows on clinic operations and performance. In this paper, we study the clinical scheduling problem with overbooking for heterogeneous patients, i.e. patients who have different no-show probabilities. We consider the objective of maximizing expected profit, which includes revenue from patients and costs associated with patient waiting times and physician overtime. We show that the objective function with homogeneous patients, i.e. patients with the same no-show probability, is multimodular. We also show that this property does not hold when patients are heterogeneous. We identify properties of an optimal schedule with heterogeneous patients and propose a local search algorithm to find local optimal schedules. Then, we extend our results to sequential scheduling and propose two sequential scheduling procedures. Finally, we perform a set of numerical experiments and provide managerial insights for health care practitioners.     

Dynamic overbooking scheduling system to improve patient access

Patient no-show has long been a recognized problem in modern outpatient health-care delivery systems. The common impacts are reduced clinic efficiency and provider productivity, wasted medical resources, increased health-care cost and limited patient access to care. The main goal of this research is to develop an effective dynamic overbooking policy into any scheduling system that accounts for the predictive probability of no-shows for any given patient. This policy increases the quality of patient care in terms of wait time and access to care while minimizing the clinic's costs. This proposed model is also illustrated to be more cost-effective than overbooking patients evenly throughout a clinic session. This paper also suggests that overbooking should be performed at better patient flow and higher no-show rate so that the costs are minimized. Consequently, this research improves the outpatient experience for both patients and medical providers.     

Risk-averse decision making in overbooking problem

Traditional literature studying overbooking problems focuses on risk-neutral decision makers. In this paper, we propose a multi-period overbooking model incorporating risk-aversion and extend well-known structural results (the 3-region policy) under the risk-neutral case to the risk-averse one on the basis of an exponential utility function. We also show that the optimal policy for the risk-neutral decision maker can be obtained by letting the risk-aversion parameter approach to zero under the risk-averse case. Therefore, the extant results under the risk-neutral case can be interpreted as a special case of ours. We also investigate how the optimal policy changes with some cost parameters and the decision maker's degree of risk-aversion. Numerical results suggest that the optimal bounds in the 3-region policy may increase or decrease with the decision maker's degree of risk-aversion.     

全渠道服务商在线上自助服务技术背景下的定价策略研究

在线上自助服务技术兴起的背景下,研究餐饮业服务商整合全渠道的定价策略。分析归纳了三种提供服务的渠道(线下取号排队、线上取号排队、线上预定);利用排队论以及依据消费者效用对服务系统进行理论建模,并结合数值分析,为服务商如何应对不同的消费者与市场环境指明了方向。研究发现:(1)给出了三种服务渠道的最优定价模型表示,并结合市场情况分析不同的定价策略,如在服务高峰期可以采取歧视定价策略;(2)指明了线上取号与线上预定两种渠道不宜同时提供,并给出了最优的线上预定的预留容量比例,对商家设计渠道具有指导意义;(3)发现了不管线下消费者比例如何,服务商营收曲线必定经过同一点,对服务商采取措施引流具有启发意义。本文对服务商全渠道理论建模具有启发意义。     

A Markov model for single-leg air cargo revenue management under a bid-price policy

In this paper, we consider the capacity allocation problem in single-leg air cargo revenue management. We assume that each cargo booking request is endowed with a random weight, volume and profit rate and propose a Markovian model for the booking request/acceptance/rejection process. The decision on whether to accept the booking request or to reserve the capacity for future bookings follows a bid-price control policy. In particular, a cargo will be accepted only when the revenue from accepting it exceeds the opportunity cost, which is calculated based on bid prices. Optimal solutions are derived by maximizing a reward function of a Markov chain. Numerical comparisons between the proposed approach and two existing static single-leg air cargo capacity allocation policies are presented.     

“酒店+OTA”双渠道供应链超订策略研究

为解决市场需求不确定环境下,酒店和在线旅行网站(Online Travel Agency,OTA)合作时的能力超订量与在线房间预留量的决策问题,建立了基于佣金合作模式的数学模型,给出了实现酒店整体期望收益最大化的在线房间预留量与能力超订量。借助数值分析,进一步研究了佣金率与需求不确定性对最优决策的影响。结果表明,当佣金率与门店需求不确定性较小时,酒店采取双渠道策略并且实施超订;当佣金率与门店需求不确定性很大时,酒店采取门店单渠道策略但不实施超订。另外,在线房间预留量随着佣金率、门店需求不确定性的增大而减小。     

Service outsourcing under co-opetition and information asymmetry

Co-opetition refers to the phenomenon that firms simultaneously cooperate and compete in order to maximize their profits. This paper studies the contracting for an outsourcing supply chain (a user company vs. a service provider) in the presence of co-opetition and information asymmetry. The user company outsources part of his service capacity at a discount price to the service provider for sale. The service provider charges a commission for doing outsourcing work and competes with the user company for the service capacity to satisfy their respective demands. We solve for the service provider’s optimal commission decision and the user company’s optimal outsourcing decisions (outsourcing volume and price discount) when the user company has private information about his service capacity. Specifically, we highlight the following observations. For the service provider, a menu of two-part tariffs that consist of a fixed commission and a per-volume commission can reveal the true type of the user company’s capacity; the user company’s optimal outsourcing proportion is quasi-convex and the optimal price discount is non-decreasing in his capacity volume, which is counterintuitive.     

Optimal pricing,EOL (end of life) warranty,and spare parts manufacturing strategy amid product transition

We study firm’s strategy to determine its product price and warranty period, and plan the spare parts manufacturing so as to maximize its profit and at the same time to fulfill its commitment to providing the customer with the key part continuously over the relevant decision time horizon, i.e., the product’s life cycle plus its EOL service (warranty) period. To examine the research question, we develop and solve a two-stage optimal control theory model. From the numerical analysis, we infer as follows. It is not always true that the longer the EOL warranty period, the better for the company’s profitability, implying there exists an optimal EOL warranty period that balances all the relevant forces like market demand and cost structures. The relationship between optimal EOL warranty period and failure rate (defect rate) is concave: when the defect rate is moderate, the company has to increase its EOL warranty period as the defect rate increases so as to compensate for the deteriorating quality; but, when the defect rate is beyond a threshold level, the company needs to curtail its EOL warranty commitment as the defect rate increases in order to avoid excessive cost to service the failed parts. By depicting key dynamics in this managerial problem, this paper sheds light on how to make decision for optimal pricing and warranty when the product life cycle is finite and the company is obliged to provide after-sales services to customers for an extended period of time after the current product is no longer produced.     

机票预定问题的多阶段决策模型

本文讨论了机票预定的一种方法 .通过建立多阶段决策模型 ,将订票时期分成若干个阶段 ,在每一个阶段航空公司对乘客要求订票作出不同的反应 ,保证了检票时准备登机的人数与飞机上的座位数目相当接近     

Wireless network capacity management: A real options approach

This paper applies financial option valuation methods to new wireless network capacity investment decision timing. In particular, we consider the case of network capacity for cellular telephone service. Given a cluster of base stations (with a certain traffic capacity per base station), we determine when it is optimal to increase capacity for each of the base stations contained in the cluster. We express this in terms of the fraction of total cluster capacity in use, i.e. we calculate the optimal time to upgrade in terms of the ratio of observed usage to existing capacity. We study the optimal decision problem of adding new capacity in the presence of stochastic wireless demand for services. A four factor algorithm is developed, based on a real options formulation. Numerical examples are provided to illustrate various aspects of the model.     

Risk-sensitive capacity control in revenue management

Both the static and the dynamic single-leg revenue management problem are studied from the perspective of a risk-averse decision maker. Structural results well-known from the risk-neutral case are extended to the risk-averse case on the basis of an exponential utility function. In particular, using the closure properties of log-convex functions, it is shown that an optimal booking policy can be characterized by protection levels, depending on the actual booking class and the remaining time. Moreover, monotonicity of the protection levels with respect to the booking class and the remaining time are proven.     

An approach to optimize block surgical schedules

We provide an approach to optimize a block surgical schedule (BSS) that adheres to the block scheduling policy, using a new type of newsvendor-based model. We assume that strategic decisions assign a specialty to each Operating Room (OR) day and deal with BSS decisions that assign sub-specialties to time blocks, determining block duration as well as sequence in each OR each day with the objective of minimizing the sum of expected lateness and earliness costs. Our newsvendor approach prescribes the optimal duration of each block and the best permutation, obtained by solving the sequential newsvendor problem, determines the optimal block sequence. We obtain closed-form solutions for the case in which surgery durations follow the normal distribution. Furthermore, we give a closed-form solution for optimal block duration with no-shows.