A Dynamic Disaggregation Approach to Approximate Linear Programs for Network Revenue Management

The linear programming approach to approximate dynamic programming has received considerable attention in the recent network revenue management (RM) literature. A major challenge of the approach lies in solving the resulting approximate linear programs (ALPs), which often have a huge number of constraints and/or variables. Starting from a recently developed compact affine ALP for network RM, we develop a novel dynamic disaggregation algorithm to solve the problem, which combines column and constraint generation and exploits the structure of the underlying problem. We show that the formulation can be further tightened by considering structural properties satisfied by an optimal solution. We prove that the sum of dynamic bid‐prices across resources is concave over time. We also give a counterexample to demonstrate that the dynamic bid‐prices of individual resources are not concave in general. Numerical experiments demonstrate that dynamic disaggregation is often orders of magnitude faster than existing algorithms in the literature for problem instances with and without choice. In addition, adding the concavity constraints can further speed up the algorithm, often by an order of magnitude, for problem instances with choice.     

A Nonatomic‐Game Approach to Dynamic Pricing under Competition

We study a revenue management problem involving competing firms. We assume the presence of a continuum of infinitesimal firms where no individual firm has any discernable influence over the evolution of the overall market condition. Under this nonatomic‐game approach, the unanimous adoption of an equilibrium pricing policy by all firms will yield a market‐condition process that in turn will elicit the said policy as one of the best individual responses. For both deterministic‐ and stochastic‐demand cases, we show the existence of equilibrium pricing policies that exhibit well‐behaving monotone trends. Our computational study reveals many useful insights, including the fact that only a reasonable number of firms are needed for our approach to produce near‐rational pricing policies.     

A New Dynamic Programming Decomposition Method for the Network Revenue Management Problem with Customer Choice Behavior

In this paper, we propose a new dynamic programming decomposition method for the network revenue management problem with customer choice behavior. The fundamental idea behind our dynamic programming decomposition method is to allocate the revenue associated with an itinerary among the different flight legs and to solve a single‐leg revenue management problem for each flight leg in the airline network. The novel aspect of our approach is that it chooses the revenue allocations by solving an auxiliary optimization problem that takes the probabilistic nature of the customer choices into consideration. We compare our approach with two standard benchmark methods. The first benchmark method uses a deterministic linear programming formulation. The second benchmark method is a dynamic programming decomposition idea that is similar to our approach, but it chooses the revenue allocations in an ad hoc manner. We establish that our approach provides an upper bound on the optimal total expected revenue, and this upper bound is tighter than the ones obtained by the two benchmark methods. Computational experiments indicate that our approach provides significant improvements over the performances of the benchmark methods.     

Competitive Pricing in a Multi‐Product Multi‐Attribute Environment

We address the problem of simultaneous pricing of a line of several products, both complementary products and substitutes, with a number of distinct price differentiation classes for each product (e.g., volume discounts, different distribution channels, and customer segments) in both monopolistic and oligopolistic settings. We provide a generic framework to tackle this problem, consider several families of demand models, and focus on a real‐world case‐study example. We propose an iterative relaxation algorithm, and state sufficient conditions for convergence of the algorithm. Using historical sales and price data from a retailer, we apply our solution algorithm to suggest optimal pricing, and report on numerical results.     

Up Then Down: Bid‐Price Trends in Revenue Management

In the classic revenue management (RM) problem of selling a fixed quantity of perishable inventories to price‐sensitive non‐strategic consumers over a finite horizon, the optimal pricing decision at any time depends on two important factors: consumer valuation and bid price. The former is determined exogenously by the demand side, while the latter is determined jointly by the inventory level on the supply side and the consumer valuations in the time remaining within the selling horizon. Because of the importance of bid prices in theory and practice of RM, this study aims to enhance the understanding of the intertemporal behavior of bid prices in dynamic RM environments. We provide a probabilistic characterization of the optimal policies from the perspective of bid‐price processes. We show that an optimal bid‐price process has an upward trend over time before the inventory level falls to one and then has a downward trend. This intertemporal up‐then‐down pattern of bid‐price processes is related to two fundamental static properties of the optimal bid prices: (i) At any given time, a lower inventory level yields a higher optimal bid price, which is referred to as the resource scarcity effect; (ii) Given any inventory level, the optimal bid price decreases with time; that is referred to as the resource perishability effect. The demonstrated upward trend implies that the optimal bid‐price process is mainly driven by the resource scarcity effect, while the downward trend implies that the bid‐price process is mainly driven by the resource perishability effect. We also demonstrate how optimal bid price and consumer valuation, as two competing forces, interact over time to drive the optimal‐price process. The results are also extended to the network RM problems.     

Scalable Dynamic Bid Prices for Network Revenue Management in Continuous Time

This study develops an approximate optimal control problem to produce time‐dependent bid prices for the airline network revenue management problem. The main contributions of our study are the analysis of time‐dependent bid prices in continuous time and the use of splines to modify the problem into an approximate second‐order cone program (ASOCP). The spline representation of bid prices permits the number of variables to depend solely on the number of resources and not on the size of the booking horizon. The advantage of this framework is the ASOCP's scalability, which we demonstrate by solving for bid prices on an industrial‐sized network. The numerical experiments highlight the ASOCP's ability to solve industrial sized problems in seconds.     

易逝品降价时点设定问题的Cournot博弈模型

本文基于Gallego和van Ryzin的两级价格策略,构建了两种竞争性易逝品降价时点设定问题的Cournot博弈模型,应用图解法求得Cournot均衡点,得出在竞争环境下先动企业会推迟降价时点而后动企业会提前降价的结论,通过实例分析验证了这一结论,同时指出了转移概率对均衡结果的影响.研究结果可为竞争环境下易逝性产品降价策略的制定提供决策支持.     

竞争环境下基于顾客策略行为的易逝品动态定价研究

在两个提供相同易逝品的零售商折线竞争下,从顾客策略行为出发,研究竞争环境下两零售商的动态定价策略。首先建立供大于求的情况下两零售商动态定价模型,给出了均衡价格满足的条件,并探讨了在一些特殊情况下均衡价格的特性。然后将这一模型扩展到供小于求的情形,探讨模型的求解方法。算例分析了在折线竞争模式下零售商在面对顾客策略行为时,如何动态的决定价格。同时发现,在供大于求的情况下,顾客策略行为导致零售商的收益降低;在供小于求的情况下,一定程度的顾客策略行为可以使零售商获得更高的期望收益。     

Dynamic Pricing with Constant Demand Elasticity

The celebrated model of Gallego and van Ryzin is specialized to the case of constant elasticity of demand. A closed form is developed, which has an even simpler form than that arising with exponential demand and which possesses an excellent approximation. In this environment, monopoly is efficient, which means that all the behavior usually attributed to monopoly pricing is actually a consequence of efficient pricing and would arise even in a perfectly competitive environment. If the initial supply is not too large, consumers have no incentive to delay their purchases to get a lower price at the average inventory prevailing at any time.     

Static and Dynamic Pricing of Excess Capacity in a Make‐to‐Order Environment

We consider a make‐to‐order manufacturer that serves two customer classes: core customers who pay a fixed negotiated price, and “fill‐in” customers who make submittal decisions based on the current price set by the firm. Using a Markovian queueing model, we determine how much the firm can gain by explicitly accounting for the status of its production facility in making pricing decisions. Specifically, we examine three pricing policies: (1) static, state‐independent pricing, (2) constant pricing up to a cutoff state, and (3) general state‐dependent pricing. We determine properties of each policy, and illustrate numerically the financial gains that the firm can achieve by following each policy as compared with simpler policies. Our main result is that constant pricing up to a cutoff state can dramatically outperform a state‐independent policy, while at the same time achieving most of the increase in revenue achievable from general state‐dependent pricing. Thus, we find that constant pricing up to a cutoff state presents an attractive tradeoff between ease of implementation and revenue gain. When the costs of policy design and implementation are taken into account, this simple heuristic may actually out‐perform general state‐dependent pricing in some settings.     

最优交易策略问题的动态求解方法

资产配置包括资产在空间和时间上的配置。现代投资组合理论为资产在空间上的配置提供了比较完备的模型和应用框架,但是资产在时间上的配置问题,学者们的研究甚少。资产在时间上的配置的核心问题是在不同时间对不同资产做出合理的买进、持有和卖出决策,即交易策略设计。本文应用动态规划的原理,分别讨论了存在和不存在最大交易次数限制的情况下,基于总收益率最大的交易策略的求解算法,并利用香港股票市场的数据进行实例分析。本文提出的算法是关于交易的时间跨度和资产数量的多项式算法,计算量和存储空间不因二者的增大而过度增大,在解决大规模问题时也是非常有效的。     

Customer Behavior Modeling in Revenue Management and Auctions: A Review and New Research Opportunities

Customer behavior modeling has been gaining increasing attention in the operations management community. In this paper we review current models of customer behavior in the revenue management and auction literatures and suggest several future research directions.     

航空客运平行航班动态定价模型

航空公司在同一航线上,提供多个不同时刻起飞的航班,我们称这样的航班为平行航班。本文应用随机控制理论建立了两个平行航班动态定价连续时间数学模型,证明了最优策略的性质,得到了最优动态定价综合策略,并给出了最优控制的时间阈值点。数值实验结果表明,这种时间阈值点的综合控制策略不仅易于实施,而且,应用该优化模型得到的总收入比两个平行航班独立决策时得到的总收入大。     

基于晶格场理论和动态规划的国债期货定价研究

通过用一个二维量子场取代传统金融上的布朗运动,构建了可有效纳入国债远期利率在到期时间和日历时间两个维度上的不完全相关性的量子场理论模型,并离散化二维量子场,得到国债远期利率的晶格场理论模型,同时结合动态规划方法,将国债期货的所有交易交割规则纳入一个模型进行建模,实现在统一的模型框架下对国债期货及其内嵌的择时期权和质量期权进行定价。研究结果亦表明,所构建的国债期货定价模型的定价效果均显著优于传统的主流两因子HJM模型,且与真实市场结算价的贴合性均很强,特别地,在临近交割月份,其定价误差均降至0.05%以内。而各国债期货合约的质量期权价值都在其对应的国债期货面值的2%至6%之间,其择时期权价值大部分时间都在0附近徘徊,但随交割月份临近,择时期权价值开始迅速上升,最大时约为期货合约面值的0.6%。     

Revenue Management for Intermodal Transportation: The Role of Dynamic Forecasting

We study a joint capacity leasing and demand acceptance problem in intermodal transportation. The model features multiple sources of evolving supply and demand, and endogenizes the interplay of three levers—forecasting, leasing, and demand acceptance. We characterize the optimal policy, and show how dynamic forecasting coordinates leasing and acceptance. We find (i) the value of dynamic forecasting depends critically on scarcity, stochasticity, and volatility; (ii) traditional mean‐value equivalence approach performs poorly in volatile intermodal context; (iii) mean‐value‐based forecast may outperform stationary distribution‐based forecast. Our work enriches revenue management models and applications. It advances our understanding on when and how to use dynamic forecasting in intermodal revenue management.     

Inventory‐Based Dynamic Pricing with Costly Price Adjustment

We study an average‐cost stochastic inventory control problem in which the firm can replenish inventory and adjust the price at anytime. We establish the optimality to change the price from low to high in each replenishment cycle as inventory is depleted. With costly price adjustment, scale economies of inventory replenishment are reflected in the cycle time instead of lot size—An increased fixed ordering cost leads to an extended replenishment cycle but does not necessarily increase the order quantity. A reduced marginal cost of ordering calls for an increased order quantity, as well as speeding up product selling within a cycle. We derive useful properties of the profit function that allows for reducing computational complexity of the problem. For systems requiring short replenishment cycles, the optimal solution can be easily computed by applying these properties. For systems requiring long replenishment cycles, we further consider a relaxed problem that is computational tractable. Under this relaxation, the sum of fixed ordering cost and price adjustment cost is equal to (greater than, less than) the total inventory holding cost within a replenishment cycle when the inventory holding cost is linear (convex, concave) in the stock level. Moreover, under the optimal solution, the time‐average profit is the same across all price segments when the inventory holding cost is accounted properly. Through a numerical study, we demonstrate that inventory‐based dynamic pricing can lead to significant profit improvement compared with static pricing and limited price adjustment can yield a benefit that is close to unlimited price adjustment. To be able to enjoy the benefit of dynamic pricing, however, it is important to appropriately choose inventory levels at which the price is revised.     

On the Benefit of Inventory‐Based Dynamic Pricing Strategies

We study the optimal pricing and replenishment decisions in an inventory system with a price‐sensitive demand, focusing on the benefit of the inventory‐based dynamic pricing strategy. We find that demand variability impacts the benefit of dynamic pricing not only through the magnitude of the variability but also through its functional form (e.g., whether it is additive, multiplicative, or others). We provide an approach to quantify the profit improvement of dynamic pricing over static pricing without having to solve the dynamic pricing problem. We also demonstrate that dynamic pricing is most effective when it is jointly optimized with inventory replenishment decisions, and that its advantage can be mostly realized by using one or two price changes over a replenishment cycle.     

Optimal Dynamic Upgrading in Revenue Management

We consider a revenue management problem involving a two compartment aircraft flying a single leg, with no cancellations or over‐booking. We apply the practice of transforming a choice revenue management model into an independent demand model. Within this assumed independent model, there are two sets of demands, business and economy, each with multiple fare class products. A business passenger can only be accepted into business. An economy passenger can be accepted into economy or upgraded into business. We define a two‐dimensional dynamic program (DP) and show that the value function is sub‐modular and concave in seat availability in the two compartments. Thus the bid prices are non‐decreasing with respect to these state variables. We use this result to propose an exact algorithm to solve the DP. Our numerical investigation suggests that in contrast to standard backward induction, our method could be included in production revenue management systems. Further, when the economy compartment is capacity constrained, we observe a substantial monetary benefit from optimal dynamic upgrading compared to the static upgrading procedures currently used in practice.     

基于收益管理的邮轮客舱分配与定价模型

基于收益管理的思想对邮轮客舱分配与定价问题进行了研究。结合邮轮运营中的个性化特点，例如消费者团体人员构成多样、较长的预售周期以及救生位和儿童看护人员的数量限制等。在不失一般性的前提下，建立了整数规划模型用以确定在预售周期内的不同预售阶段中各种客舱类型的待售数量及其价格，以达到使邮轮公司收益最大化的目的。实验分析表明，该模型在实际应用中是有效的且呈现出显著的年增长趋势，可明显提高邮轮公司的收益。此外，设计了一种基于韦伯分布的EM算法用以解决模型中涉及到的需求量的无约束估计问题。数值算例研究表明，该算法收敛速度快且无约束估计过程可靠有效。