A revenue management approach to address a truck rental problem

This paper describes an application of revenue management techniques and policies in the field of logistics and distribution. In particular, the problem of transportation operators, who offer products for hire, is considered. A product is a truck of a given capacity, which can be rented for one or several time periods, throughout a multi-period planning horizon. The logistic operator can satisfy the demand of a given product with trucks with a capacity greater than that initially required, that is an ‘upgrade’ can take place. In this context, the logistic operator has to decide whether to accept or reject a request and which type of truck should be used to address it. For this purpose, a dynamic programming (DP) formulation of the problem under consideration is devised. The ‘course of dimensionality’ leads to the necessity of introducing different mathematical programming models to represent the problem. The mathematical models we presented are an extension of the well-known approximations for the DP of traditional network capacity management analysis. Based on these models and exploiting revenue management concepts, primal and dual acceptance policies are developed and compared in a computational study.     

Integrated revenue management approaches for capacity control with planned upgrades

In many service industries, firms offer a portfolio of similar products based on different types of resources. Mismatches between demand and capacity can therefore often be managed by using product upgrades. Clearly, it is desirable to consider this possibility in the revenue management systems that are used to decide on the acceptance of requests. To incorporate upgrades, we build upon different dynamic programming formulations from the literature and gain several new structural insights that facilitate the control process under certain conditions. We then propose two dynamic programming decomposition approaches that extend the traditional decomposition for capacity control by simultaneously considering upgrades as well as capacity control decisions. While the first approach is specifically suited for the multi-day capacity control problem faced, for example, by hotels and car rental companies, the second one is more general and can be applied in arbitrary network revenue management settings that allow upgrading. Both approaches are formally derived and analytically related to each other. It is shown that they give tighter upper bounds on the optimal solution of the original dynamic program than the well-known deterministic linear program. Using data from a major car rental company, we perform computational experiments that show that the proposed approaches are tractable for real-world problem sizes and outperform those disaggregated, successive planning approaches that are used in revenue management practice today.     

考虑顾客使用行为的汽车租赁容量分配策略研究

随着物联网技术的发展, 租赁公司通过智能技术可以实时监测顾客的使用行为, 因此可以根据顾客使用行为设计补贴策略以激励顾客在使用过程中保持良好的行为习惯。本文将租赁价格作为顾客行为的函数, 构建随机动态规划模型, 研究了多产品、多周期下汽车租赁公司的容量分配决策和补贴机制。考虑到所构建模型的状态变量维度较高, 因此提出两种近似算法对模型进行求解, 并通过数值仿真验证了模型的相关性质。在考虑顾客行为可以转变的前提下, 得到相关结论:租赁公司以机会成本作为容量分配决策的重要依据;当所需等级汽车缺货时, 由于低等级汽车的机会成本低于高等级汽车的机会成本, 因此满足升级条件时, 租赁公司总是按照等级顺序进行升级;在合理的补贴策略下, 公司的总收益将会随着补贴的增加而增加。     

Capacity allocation for demand of different customer-product-combinations with cancellations, no-shows, and overbooking when there is a sequential delivery of service

We consider a problem where different classes of customers can book different types of services in advance and the service company has to respond immediately to the booking request confirming or rejecting it. Due to the possibility of cancellations before the day of service, or no-shows at the day of service, overbooking the given capacity is a viable decision. 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 the cost of overtime. For the calculation of the latter, information of the underlying appointment schedule is required. Throughout the paper we will relate the problem to capacity allocation in radiology services. Drawing upon ideas from revenue management, overbooking, and appointment scheduling we model the problem as a Markov decision process in discrete time which due to proper aggregation can be optimally solved with an iterative stochastic dynamic programming approach. In an experimental study we successfully apply the approach to a real world problem with data from the radiology department of a hospital. Furthermore, we compare the optimal policy to four heuristic policies, of whom one is currently in use. We can show that the optimal policy significantly improves the currently used policy and that a nested booking limit type policy closely approximates the optimal policy and is thus recommended for use in practice.     

Dynamic simultaneous fare proration for large-scale network revenue management

Network revenue management is concerned with managing demand for products that require inventory from one or several resources by controlling product availability and/or prices in order to maximize expected revenues subject to the available resource capacities. One can tackle this problem by decomposing it into resource-level subproblems that can be solved efficiently, for example by dynamic programming. We propose a new dynamic fare proration method specifically having large-scale applications in mind. It decomposes the network problem by fare proration and solves the resource-level dynamic programs simultaneously using simple, endogenously obtained dynamic marginal capacity value estimates to update fare prorations over time. An extensive numerical simulation study demonstrates that the method results in tightened upper bounds on the optimal expected revenue, and that the obtained policies are very effective with regard to achieved revenues and required runtime.     

Risk minimising strategies for revenue management problems with target values

Consider a risk-averse decision maker in the setting of a single-leg dynamic revenue management problem with revenue controlled by limiting capacity for a fixed set of prices. Instead of focussing on maximising the expected revenue, the decision maker has the main objective of minimising the risk of failing to achieve a given target revenue. Interpreting the revenue management problem in the framework of finite Markov decision processes, we augment the state space of the risk-neutral problem definition and change the objective function to the probability of failing a certain specified target revenue. This enables us to obtain a dynamic programming solution that generates the policy minimising the risk of not attaining this target revenue. We compare this solution with recently proposed risk-sensitive policies in a numerical study and discuss advantages and limitations.     

Strategic and operational decisions in restaurant revenue management

The paper addresses restaurant revenue management from both a strategic and an operational point of view. Strategic decisions in restaurants are mainly related to defining the most profitable combination of tables that will constitute the restaurant. We propose new formulations of the so-called “Tables Mix Problem” by taking into account several features of the real setting. We compare the proposed models in a computational study showing that restaurants, with the capacity of managing tables as renewable resources and of combining different-sized tables, can improve expected revenue performances. Operational decisions are mainly concerned with the more profitable assignment of tables to customers. Indeed, the “Parties Mix Problem” consists of deciding on accepting or denying a booking request from different groups of customers, with the aim of maximizing the total expected revenue. A dynamic formulation of the “Parties Mix Problem” is presented together with a linear programming approximation, whose solutions can be used to define capacity control policies based on booking limits and bid prices. Computational results compare the proposed policies and show that they lead to higher revenues than the traditional strategies used to support decision makers.     

基于需求分类和乘客升级购买行为的航空公司收益管理模型

研究了基于乘客分类的航空客运库存控制与动态定价策略.模型中,航空公司以提供折扣票的方式将乘客分为两类,并针对购买折扣票的乘客存在升级购买行为,通过动态的控制折扣票的销售和对机票实施动态定价来最大化自身的期望收益.应用动态规划建立了相应的收益管理模型,讨论了最优定价应满足的关系式,并得到了接受或拒绝乘客购买折扣票的阈值.最后,通过算例分析了升级购买概率对阈值、机票的价格及期望收益的影响.     

基于粒子群算法的汽车租赁短期车辆配置问题研究

合理的车辆配置与调度是租车公司运营管理考虑的主要问题之一,也是提高租车公司的租车率和收益的有效途径。针对目前我国租车公司普遍缺乏历史数据、预定提前期短、租期短、门店间距离短等主要运营特点,本文将租车公司运营中频繁而复杂的短期车辆配置问题作为研究对象,提出单日的车辆配置方法,构建随机期望模型,并采用合理的方法分解模型,选择粒子群算法对子模型进行求解,并用数值算例验证了该方法的可行性与效果。该方法能够帮助租车公司管理者做出正确的决策,在提升顾客满意度的同时,提高租车率和租车公司的收益。     

Improved bid prices for choice-based network revenue management

One of the latest developments in network revenue management (RM) is the incorporation of customer purchase behavior via discrete choice models. Many authors presented control policies for the booking process that are expressed in terms of which combination of products to offer at a given point in time and given resource inventories. However, in many implemented RM systems—most notably in the hotel industry—bid price control is being used, and this entails the problem that the recommended combination of products as identified by these policies might not be representable through bid price control. If demand were independent from available product alternatives, an optimal choice of bid prices is to use the marginal value of capacity for each resource in the network. But under dependent demand, this is not necessarily the case. In fact, it seems that these bid prices are typically not restrictive enough and result in buy-down effects.We propose (1) a simple and fast heuristic that iteratively improves on an initial guess for the bid price vector; this first guess could be, for example, dynamic estimates of the marginal value of capacity. Moreover, (2) we demonstrate that using these dynamic marginal capacity values directly as bid prices can lead to significant revenue loss as compared to using our heuristic to improve them. Finally, (3) we investigate numerically how much revenue performance is lost due to the confinement to product combinations that can be represented by a bid price.The heuristic is not restricted to a particular choice model and can be combined with any method that provides us with estimates of the marginal values of capacity. In our numerical experiments, we test the heuristic on some popular networks examples taken from peer literature. We use a multinomial logit choice model which allows customers from different segments to have products in common that they consider to purchase. In most problem instances, our heuristic policy results in significant revenue gains over some currently available alternatives at low computational cost.     

The newsvendor problem with an in-season price adjustment

Consider a retailer stocking a seasonal item facing a stochastic demand where information about the demand becomes more accurate as the selling season progresses. The retailer places orders before the start of the season and in-season reorders are not possible. This article extends the classical newsvendor model by allowing the retailer to make an in-season price adjustment after conducting a review and using the realized demand to obtain an accurate estimate of the remaining demand. Our results include answers to the following questions. What price should the retailer choose? How much should the retailer have ordered at the start of the season given the option of adjusting prices in-season? This model was motivated by a problem in car rental revenue management and has applications in perishable assets revenue management (PARM), where price adjustments are needed towards the end of the selling season.     

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.     

Heuristic algorithms for the operator-based relocation problem in one-way electric carsharing systems

This paper addresses an Electric Vehicle Relocation Problem (E-VReP), in one-way carsharing systems, based on operators who use folding bicycles to facilitate vehicle relocation. In order to calculate the economic sustainability of this relocation approach, a revenue associated with each relocation request satisfied and a cost associated with each operator used are introduced. The new optimization objective maximizes the total profit. To overcome the drawback of the high CPU time required by the Mixed Integer Linear Programming formulation of the E-VReP, two heuristic algorithms, based on the general properties of the feasible solutions, are designed. Their effectiveness is tested on two sets of realistic instances. In the first, all the requests have the same revenue, while, in the second, the revenue of each request has a variable component related to the user’s rent-time and a fixed part related to customer satisfaction. Finally, a sensitivity analysis is carried out on both the number of requests and the fixed revenue component.     

Stochastic vs deterministic programming in water management: the value of flexibility

In the paper we develop a two stage scenario-based stochastic programming model for water management in the Indus Basin Irrigation System (IBIS). We present a comparison between the deterministic and scenario-based stochastic programming model. Our model takes stochastic inputs on hydrologic data i.e. inflow and rainfall. We divide the basin into three rainfall zones which overlap on 44 canal commands. Data on crop characteristics are taken on canal command levels. We then use ten-daily and monthly time intervals to analyze the policies. This system has two major reservoirs and a complex network of rivers, canal head works, canals, sub canals and distributaries. All the decisions on hydrologic aspects are governed by irrigation and agricultural development policies. Storage levels are maintained within the minimum and maximum bounds for every time interval according to a power generation policy. The objective function is to maximize the expected revenue from crops production. We discuss the flexibility of two stochastic optimization models with varying time horizon.     

Intelligent parking systems

The basic concepts of the parking reservation system and parking revenue management system are discussed in this paper. The proposed “intelligent” parking space inventory control system that is based on a combination of fuzzy logic and integer programming techniques makes “on line” decisions whether to accept or reject a new driver’s request for parking. In the first step of the proposed model, the best parking strategies are developed for many different patterns of vehicle arrivals. These parking strategies are developed using integer programming approach. In the second step, learning from the best strategies, specific rules are defined. The uniqueness of the proposed approach is that the rules are derived from the set of chosen examples assuming that the future traffic arrival patterns are known. The results were found to be close to the best solution assuming that the future arrival pattern is known.     

Network revenue management with inventory-sensitive bid prices and customer choice

We develop an approximate dynamic programming approach to network revenue management models with customer choice that approximates the value function of the Markov decision process with a non-linear function which is separable across resource inventory levels. This approximation can exhibit significantly improved accuracy compared to currently available methods. It further allows for arbitrary aggregation of inventory units and thereby reduction of computational workload, yields upper bounds on the optimal expected revenue that are provably at least as tight as those obtained from previous approaches. Computational experiments for the multinomial logit choice model with distinct consideration sets show that policies derived from our approach can outperform some recently proposed alternatives, and we demonstrate how aggregation can be used to balance solution quality and runtime.     

Dynamic cruise ship revenue management

Recently, it has been recognized that revenue management of cruise ships is different from that of airlines or hotels. Among the main differences is the presence of multiple capacity constraints in cruise ships, i.e., the number of cabins in different categories and the number of lifeboat seats, versus a single constraint in airlines and hotels (i.e., number of seats or rooms). We develop a discrete-time dynamic capacity control model for a cruise ship characterized by multiple constraints on cabin and lifeboat capacities. Customers (families) arrive sequentially according to a stochastic process and request one cabin of a certain category and one or more lifeboat seats. The cruise ship revenue manager decides which requests to accept based on the remaining cabin and lifeboat capacities at the time of an arrival as well as the type of the arrival. We show that the opportunity cost of accepting a customer is not always monotone in the reservation levels or time. This non-monotone behavior implies that “conventional” booking limits or critical time periods capacity control policies are not optimal. We provide analysis and insights justifying the non-monotone behavior in our cruise ship context. In the absence of monotonicity, and with the optimal solution requiring heavy storage for “large” (industry-size) problems, we develop several heuristics and thoroughly test their performance, via simulation, against the optimal solution, well-crafted upper bounds, and a first-come first-served lower bound. Our heuristics are based on rolling-up the multi-dimensional state space into one or two dimensions and solving the resulting dynamic program (DP). This is a strength of our approach since our DP-based heuristics are easy to understand, solve and analyze. We find that single-dimensional heuristics based on decoupling the cabins and lifeboat problems perform quite well in most cases.     

A single-resource revenue management problem with random resource consumptions

We study a single-resource multi-class revenue management problem where the resource consumption for each class is random and only revealed at departure. The model is motivated by cargo revenue management problems in the airline and other shipping industries. We study how random resource consumption distribution affects the optimal expected profit and identify a preference acceptance order on classes. For a special case where the resource consumption for each class follows the same distribution, we fully characterize the optimal control policy. We then propose two easily computable heuristics: (i) a class-independent heuristic through parameter scaling, and (ii) a decomposition heuristic that decomposes the dynamic programming formulation into a collection of one-dimensional problems. We conduct extensive numerical experiments to investigate the performance of the two heuristics and compared them with several widely studied heuristic policies. Our results show that both heuristics work very well, with class-independent heuristic slightly better between the two. In particular, they consistently outperform heuristics that ignore demand and/or resource consumption uncertainty. Our results demonstrate the importance of considering random resource consumption as another problem dimension in revenue management applications.     

基于航段需求计算网络竞价的近似动态规划方法

竞价控制是收益管理中广泛应用的一种存量控制方法.将网络存量控制问题描述为一个动态规划模型,通过状态向量的一个仿射函数近似动态规划的最优值函数,并且在航段水平上考虑随机需求,最终得到一个计算网络竞价所需的确定性线性规划(DLP),相对于标准的DLP,这个DLP得到了更接近于动态规划最优值的上界.给出了一个列生成算法用于求解这个DLP,并提供了模拟算例,计算结果表明可获得比标准的DLP方法更好的收益.     

Dynamic bidding strategies in search-based advertising

Search-based advertising allows the advertisers to run special campaigns targeted to different groups of potential consumers at low costs. Google, Yahoo and Microsoft advertising programs allow the advertisers to bid for an ad position on the result page of a user’s query when the user searches for a keyword that the advertiser relates to its products or services. The expected revenue generated by the ad depends on the ad position, and the ad positions of the advertisers are concurrently determined after an instantaneous auction based on the bids of the advertisers. The advertisers are charged only when their ads are clicked by the users. To avoid excessive ad expenditures due to sudden surges in the keyword-search activities, each advertiser reserves a fixed finite daily budget, and the ads are not shown in the remainder of the day when the budget is depleted. Arrival times of keyword-search instances, ad positions, ad selections, and sales generated by the ads are random. Therefore, an advertiser faces a dynamic stochastic total net revenue optimization problem subject to a strict budget constraint. Here we formulate and solve this problem using dynamic programming. We show that there is always an optimal dynamic bidding policy. We describe an iterative numerical approximation algorithm that uniformly converges to the optimal solution at an exponential rate of the number of iterations. We illustrate the algorithm on numerical examples. Because dynamic programing calculations of the optimal bidding policies are computationally demanding, we also propose both static and dynamic alternative bidding policies. We numerically compare the performances of optimal and alternative bidding policies by systematically changing each input parameter. The relative percentage total net revenue losses of the alternative bidding policies increases with the budget loading, but were never more than 3.5 % of maximum expected total net revenue. The best alternative to the optimal bidding policy turned out to be a static greedy bidding policy. Finally, statistical estimation of the model parameters is visited.