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.     

Bounding Optimal Expected Revenues for Assortment Optimization under Mixtures of Multinomial Logits

We consider assortment problems under a mixture of multinomial logit models. There is a fixed revenue associated with each product. There are multiple customer types. Customers of different types choose according to different multinomial logit models whose parameters depend on the type of the customer. The goal is to find a set of products to offer so as to maximize the expected revenue obtained over all customer types. This assortment problem under the multinomial logit model with multiple customer types is NP‐complete. Although there are heuristics to find good assortments, it is difficult to verify the optimality gap of the heuristics. In this study, motivated by the difficulty of finding optimal solutions and verifying the optimality gap of heuristics, we develop an approach to construct an upper bound on the optimal expected revenue. Our approach can quickly provide upper bounds and these upper bounds can be quite tight. In our computational experiments, over a large set of randomly generated problem instances, the upper bounds provided by our approach deviate from the optimal expected revenues by 0.15% on average and by less than one percent in the worst case. By using our upper bounds, we are able to verify the optimality gaps of a greedy heuristic accurately, even when optimal solutions are not available.     

Dynamic Pricing to Minimize Maximum Regret

We consider a dynamic pricing problem that involves selling a given inventory of a single product over a short, two‐period selling season. There is insufficient time to replenish inventory during this season, hence sales are made entirely from inventory. The demand for the product is a stochastic, nonincreasing function of price. We assume interval uncertainty for demand, that is, knowledge of upper and lower bounds but not a probability distribution, with no correlation between the two periods. We minimize the maximum total regret over the two periods that results from the pricing decisions. We consider a dynamic model where the decision maker chooses the price for each period contingent on the remaining inventory at the beginning of the period, and a static model where the decision maker chooses the prices for both periods at the beginning of the first period. Both models can be solved by a polynomial time algorithm that solves systems of linear inequalities. Our computational study demonstrates that the prices generated by both our models are insensitive to errors in estimating the demand intervals. Our dynamic model outperforms our static model and two classical approaches that do not use demand probability distributions, when evaluated by maximum regret, average relative regret, variability, and risk measures. Further, our dynamic model generates a total expected revenue which closely approximates that of a maximum expected revenue approach which requires demand probability distributions.     

Assortment Optimization under the Multinomial Logit Model with Random Choice Parameters

We consider assortment optimization problems under the multinomial logit model, where the parameters of the choice model are random. The randomness in the choice model parameters is motivated by the fact that there are multiple customer segments, each with different preferences for the products, and the segment of each customer is unknown to the firm when the customer makes a purchase. This choice model is also called the mixture‐of‐logits model. The goal of the firm is to choose an assortment of products to offer that maximizes the expected revenue per customer, across all customer segments. We establish that the problem is NP complete even when there are just two customer segments. Motivated by this complexity result, we focus on assortments consisting of products with the highest revenues, which we refer to as revenue‐ordered assortments. We identify specially structured cases of the problem where revenue‐ordered assortments are optimal. When the randomness in the choice model parameters does not follow a special structure, we derive tight approximation guarantees for revenue‐ordered assortments. We extend our model to the multi‐period capacity allocation problem, and prove that, when restricted to the revenue‐ordered assortments, the mixture‐of‐logits model possesses the nesting‐by‐fare‐order property. This result implies that revenue‐ordered assortments can be incorporated into existing revenue management systems through nested protection levels. Numerical experiments show that revenue‐ordered assortments perform remarkably well, generally yielding profits that are within a fraction of a percent of the optimal.     

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.     

Pricing,Allocation, and Overbooking in Dynamic Service Network Competition When Demand Is Uncertain

We study the problem of combined pricing, resource allocation, and overbooking by service providers involved in dynamic noncooperative oligopolistic competition on a network that represents the relationships of the providers to one another and to their customers when service demand is uncertain. We propose, analyze, and compute solutions for a model that is more general than other models reported in the revenue management literature to date. In particular, previous models typically consider only three or four of five key revenue management features that we have purposely built into our model: (1) pricing, (2) resource allocation, (3) dynamic competition, (4) an explicit network, and (5) uncertain demand. Illustrative realizations of the abstract problem we study are those of airline revenue management and service provision by companies facing resource constraints. Under fairly general regularity conditions, we prove existence and uniqueness of a pure strategy Nash equilibrium for dynamic oligopolistic service network competition described by our model. We also show, for an appropriate notion of regularity, that competition leads to the underpricing of network services, a finding numerically illustrated by an example of intermediate size. Our proposed algorithm can be implemented using well‐known off‐the‐shelf commercial software.     

考虑长期运力合同的班轮收益管理运输路径优化模型

基于收益管理的方法,文章对随机需求环境下班轮运力分配和路径优化问题进行了定量研究。首先针对海运收益管理的特征,建立了考虑长期运力合同、空箱调运的轮运力分配和路径选择随机规划模型,然后应用稳健优化方法对此模型进行求解。最后,通过数值仿真得到了优化的舱位分配方案,比较发现稳健优化模型取得了较确定性规划模型更好的收益,显示了模型和方法对于集装箱海运企业的收益管理问题具有应用价值。     

Revenue Management with End‐of‐Period Discounts in the Presence of Customer Learning

Consider a firm that sells identical products over a series of selling periods (e.g., weekly all‐inclusive vacations at the same resort). To stimulate demand and enhance revenue, in some periods, the firm may choose to offer a part of its available inventory at a discount. As customers learn to expect such discounts, a fraction may wait rather than purchase at a regular price. A problem the firm faces is how to incorporate this waiting and learning into its revenue management decisions. To address this problem we summarize two types of learning behaviors and propose a general model that allows for both stochastic consumer demand and stochastic waiting. For the case with two customer classes, we develop a novel solution approach to the resulting dynamic program. We then examine two simplified models, where either the demand or the waiting behavior are deterministic, and present the solution in a closed form. We extend the model to incorporate three customer classes and discuss the effects of overselling the capacity and bumping customers. Through numerical simulations we study the value of offering end‐of‐period deals optimally and analyze how this value changes under different consumer behavior and demand scenarios.     

Revenue Management vs. Newsvendor Decisions: Does Behavioral Response Mirror Normative Equivalence?

We study and compare decision‐making behavior under the newsvendor and the two‐class revenue management models, in an experimental setting. We observe that, under both problems, decision makers deviate significantly from normative benchmarks. Furthermore, revenue management decisions are consistently higher compared to the newsvendor order quantities. In the face of increasing demand variability, revenue managers increase allocations; this behavior is consistent with normative patterns when the ratio of the selling prices of the two customer segments is less than 1/2, but is its exact opposite when this ratio is greater than 1/2. Newsvendors' behavior with respect to changing demand variability, on the other hand, is consistent with normative trends. We also observe that losses due to leftovers weigh more in newsvendor decisions compared to the revenue management model; we argue that overage cost is more salient in the newsvendor problem because it is perceived as a direct loss, and propose this as the driver of the differences in behavior observed under the two problems.     

Piecewise linear approximations for the static–dynamic uncertainty strategy in stochastic lot-sizing

In this paper, we develop a unified mixed integer linear modelling approach to compute near-optimal policy parameters for the non-stationary stochastic lot sizing problem under static–dynamic uncertainty strategy. The proposed approach applies to settings in which unmet demand is backordered or lost; and it can accommodate variants of the problem for which the quality of service is captured by means of backorder penalty costs, non-stockout probabilities, or fill rate constraints. This approach has a number of advantages with respect to existing methods in the literature: it enables seamless modelling of different variants of the stochastic lot sizing problem, some of which have been previously tackled via ad hoc solution methods and some others that have not yet been addressed in the literature; and it produces an accurate estimation of the expected total cost, expressed in terms of upper and lower bounds based on piecewise linearisation of the first order loss function. We illustrate the effectiveness and flexibility of the proposed approach by means of a computational study.     

Revenue Management of Reusable Resources with Advanced Reservations

We consider a revenue management problem wherein the seller is endowed with a single type resource with a finite capacity and the resource can be repeatedly used to serve customers. There are multiple classes of customers arriving according to a multi‐class Poisson process. Each customer, upon arrival, submits a service request that specifies his service start time and end time. Our model allows customer advanced reservation times and services times in each class to be arbitrarily distributed and correlated. Upon arrival of each customer, the seller must instantaneously decide whether to accept this customer's service request. A customer whose request is denied leaves the system. A customer whose request is accepted is allocated with a specific item of the resource at his service start time. The resource unit occupied by a customer becomes available to other customers after serving this customer. The seller aims to design an admission control policy that maximizes her expected long‐run average revenue. We propose a policy called the ε‐perturbation class selection policy (ε‐CSP), based on the optimal solution in the fluid setting wherein customers are infinitesimal and customer arrival processes are deterministic, under the restriction that the seller can utilize at most (1 − ε) of her capacity for any ε ∈ (0, 1). We prove that the ε‐CSP is near‐optimal. More precisely, we develop an upper bound of the performance loss of the ε‐CSP relative to the seller's optimal revenue, and show that it converges to zero with a square‐root convergence rate in the asymptotic regime wherein the arrival rates and the capacity grow up proportionally and the capacity buffer level ε decays to zero.     

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.     

大规模客运专线网络运营优化模型与求解算法

本文在分析铁路运营优化模型的研究进展的基础上,提出了一个适合大规模客运专线网络运营的优化模型,并提出了求解此模型的列生成算法和启发式快速算法。目的是将客运专线网路的开行方案优化与动态收益优化问题结合起来,解决更大、更复杂的客运网络运营优化问题。模型以列车运营总收益最大化为目标。用随机生成数据进行的模型试验表明,模型及算法可以在较短的时间内求解较大规模的收益管理优化问题。     

Allocation of Returned Products among Different Recovery Options through an Opportunity Cost–Based Dynamic Approach*

In a make‐to‐order product recovery environment, we consider the allocation decision for returned products decision under stochastic demand of a firm with three options: refurbishing to resell, parts harvesting, and recycling. We formulate the problem as a multiperiod Markov decision process (MDP) and present a linear programming (LP) approximation that provides an upper bound on the optimal objective function value of the MDP model. We then present two solution approaches to the MDP using the LP solution: a static approach that uses the LP solution directly and a dynamic approach that adopts a revenue management perspective and employs bid‐price controls technique where the LP is resolved after each demand arrival. We calculate the bid prices based on the shadow price interpretation of the dual variables for the inventory constraints and accept a demand if the marginal value is higher than the bid price. Since the need for solving the LP at each demand arrival requires a very efficient solution procedure, we present a transportation problem formulation of the LP via variable redefinitions and develop a one‐pass optimal solution procedure for it. We carry out an extensive numerical analysis to compare the two approaches and find that the dynamic approach provides better performance in all of the tested scenarios. Furthermore, the solutions obtained are within 2% of the upper bound on the optimal objective function value of the MDP model.     

Management of school locations allowing for free school choice

Nearly without exception, we find in literature (school) location models with exogenously given demand. Indeed, we know from a large number of empirical studies that this assumption is unrealistic. Therefore, we propose a discrete location model for school network planning with free school choice that is based on simulated utility values for a large average sample. The objective is to maximize the standardized expected utility of all students taking into account capacity constraints and a given budget for the school network. The utility values of each student for the schools are derived from a random utility model (RUM). The proposed approach is general in terms of the RUM used. Moreover, we do not have to make assumptions about the functional form of the demand function. Our approach, which combines econometric and mathematical methods, is a linear 0–1 program although we consider endogenous demand by a highly non-linear function. The proposed program enables practicing managers to consider student demand adequately within their decision making. By a numerical investigation we show that this approach enables us to solve instances of real size optimally – or at least close to optimality – within few minutes using GAMS/Cplex.     

An Enhanced Concave Program Relaxation for Choice Network Revenue Management

The network choice revenue management problem models customers as choosing from an offer set, and the firm decides the best subset to offer at any given moment to maximize expected revenue. The resulting dynamic program for the firm is intractable and approximated by a deterministic linear program called the CDLP which has an exponential number of columns. However, under the choice‐set paradigm when the segment consideration sets overlap, the CDLP is difficult to solve. Column generation has been proposed but finding an entering column has been shown to be NP‐hard. In this study, starting with a concave program formulation called SDCP that is based on segment‐level consideration sets, we add a class of constraints called product constraints (σPC), that project onto subsets of intersections. In addition, we propose a natural direct tightening of the SDCP called , and compare the performance of both methods on the benchmark data sets in the literature. In our computational testing on the data sets, 2PC achieves the CDLP value at a fraction of the CPU time taken by column generation. For a large network our 2PC procedure runs under 70 seconds to come within 0.02% of the CDLP value, while column generation takes around 1 hour; for an even larger network with 68 legs, column generation does not converge even in 10 hours for most of the scenarios while 2PC runs under 9 minutes. Thus we believe our approach is very promising for quickly approximating CDLP when segment consideration sets overlap and the consideration sets themselves are relatively small.     

基于顾客信任的网络商店显示价格对比性信息的策略研究

是否应显示竞争对手的价格对比性信息一直是困扰网络商店的一个问题。考虑到网络商店显示竞争对手的价格信息对顾客信任以及顾客信任对消费者效用的影响,本文以商店声誉、商品价格和顾客信任为变量建立消费者效用模型,运用博弈方法进行模型分析,探讨网络商店是否应显示竞争对手价格对比性信息的策略选择问题。研究发现,不同经营导向和不同声誉的网络商店应选择不同的显示策略,即:以市场份额为导向时,同质商店可以维持现有显示策略;而异质商店可根据现有显示情况做出策略调整;以商店收益为导向时,同质商店都倾向于显示的策略,异质商店倾向于在各自需求优势下定相对较高价格的策略;以消费者剩余为导向时,同质商店可维持现有显示策略,异质商店中具有声誉优势的一方和不具有声誉优势的一方分别倾向于双方都显示和只有一方显示的策略。     

Managing Inventory with Cash Register Information: Sales Recorded but Not Demands

Inventory inaccuracy is common in many businesses. While retailers employ cash registers to enter incoming orders and outgoing sales, inaccuracy arises because they do not record invisible demand such as spoilage, damage, pilferage, or returns. This setting results in incomplete inventory and demand information. An important inventory control problem therefore is to maximize the total expected discounted profit under this setting. Allowing for dependence between demand and invisible demand, we obtain the associated dynamic programming equation with an infinite‐dimensional state space, and reduce it to a simpler form by employing the concept of unnormalized probability. We develop an analytical upper bound on the optimal profit as well as an iterative algorithm for an approximate solution of the problem. We compare profits of the iterative solution and the myopic solution, and then to the upper bound. We see that the iterative solution performs better than the myopic solution, and significantly so in many cases. Furthermore, it gives a profit not far from the upper bound, and is therefore close to optimal. Using our results, we also discuss meeting inventory service levels.     

On the fair optimization of cost and customer service level in a supply chain under disruption risks

This paper presents a new decision-making problem of a fair optimization with respect to the two equally important conflicting objective functions: cost and customer service level, in the presence of supply chain disruption risks. Given a set of customer orders for products, the decision maker needs to select suppliers of parts required to complete the orders, allocate the demand for parts among the selected suppliers, and schedule the orders over the planning horizon, to equitably optimize expected cost and expected customer service level. The supplies of parts are subject to independent random local and regional disruptions. The fair decision-making aims at achieving the normalized expected cost and customer service level values as much close to each other as possible. The obtained combinatorial stochastic optimization problem is formulated as a stochastic mixed integer program with the ordered weighted averaging aggregation of the two conflicting objective functions. Numerical examples and computational results, in particular comparison with the weighted-sum aggregation of the two objective functions are presented and some managerial insights are reported. The findings indicate that for the minimum cost objective the cheapest supplier is usually selected, and for the maximum service level objective a subset of most reliable and most expensive suppliers is usually chosen, whereas the equitably efficient supply portfolio usually combines the most reliable and the cheapest suppliers. While the minimum cost objective function leads to the largest expected unfulfilled demand and the expected production schedule for the maximum service level follows the customer demand with the smallest expected unfulfilled demand, the equitably efficient solution ensures a reasonable value of expected unfulfilled demand.     

DEMAND MANAGEMENT: THE EVALUATION OF PRICE AND DUE DATE NEGOTIATION STRATEGIES USING SIMULATION

The research considers the problem of demand management in a firm where the firm's historical delivery service level reputation influences the number of quotation requests from its potential customers. Customers have a maximum and the firm has a minimum net price to due date tradeoff curve for each job. The demand management function bargains with the customer over price and promised due date. Bargaining finishes either with an agreed price and delivery date or with the customer refusing the firm's bid and placing the order elsewhere. The firm's objective is to maximize its long-term net revenue. The firm's demand management negotiation strategy guides this bidding process. The research demonstrates the use of simulation to test different demand management bidding and negotiation strategies for different market and firm scenarios. The demonstration uses 16 scenarios to test the different demand management negotiation strategies with a model of a classical job shop in a classical market. The investigation examines finite scheduling-based due date estimation methods, as well as the more traditional parameter-based methods. This demonstration shows that it is possible to test different bidding policies, using a simulation model of a firm and its customers, and to obtain usable results.