Mathematical programming models for revenue management under customer choice

We study a network airline revenue management problem with discrete customer choice behavior. We discuss a choice model based on the concept of preference orders, in which customers can be grouped according to a list of options in decreasing order of preference. If a customer’s preferred option is not available, the customer moves to the next choice on the list with some probability. If that option is not available, the customer moves to the third choice on the list with some probability, and so forth until either the customer has no other choice but to leave or his/her request is accepted. Using this choice model as an input, we propose some mathematical programs to determine seat allocations. We also propose a post-optimization heuristic to refine the allocation suggested by the optimization model. Simulation results are presented to illustrate the effectiveness of our method, including comparisons with other models.     

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.     

The impact of customer behavior models on revenue management systems

Computational Management Science - Revenue management (RM) can be considered an application of operations research in the transportation industry. For these service companies, it is a difficult...     

Mathematical programming for network revenue management revisited

Mathematical programming models for airline seat inventory control provide booking limits and bid-prices for all itineraries and fare classes. E.L. Williamson [Airline network seat inventory control: methodologies and revenue impacts, Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MA, 1992] finds that simple deterministic approximation methods based on average demand often outperform more advanced probabilistic heuristics. We argue that this phenomenon is due to a booking process that includes nesting of the fare classes, which is ignored in the modeling phase. The differences in the performance between these approximations are studied using a stochastic programming model that includes the deterministic model as a special case. Our study carefully examines the trade-off between computation time and the aggregation level of demand uncertainty with examples of a multi-leg flight and a single-hub network.     

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.     

A new neural network for solving linear programming problems

We propose and analyse a new class of neural network models for solving linear programming (LP) problems in real time. We introduce a novel energy function that transforms linear programming into a system of nonlinear differential equations. This system of differential equations can be solved on-line by a simplified low-cost analog neural network containing only one single artificial neuron with adaptive synaptic weights. The network architecture is suitable for currently available CMOS VLSI implementations. An important feature of the proposed neural network architecture is its flexibility and universality. The correctness and performance of the proposed neural network is illustrated by extensive computer simulation experiments.     

A modelling framework for solving restricted planar location problems using phi-objects

This paper presents a general modelling framework for restricted facility location problems with arbitrarily shaped forbidden regions or barriers, where regions are modelled using phi-objects. Phi-objects are an efficient tool in mathematical modelling of 2D and 3D geometric optimization problems, and are widely used in cutting and packing problems and covering problems. The paper shows that the proposed modelling framework can be applied to both median and centre facility location problems, either with barriers or forbidden regions. The resulting models are either mixed-integer linear or non-linear programming formulations, depending on the shape of the restricted region and the considered distance measure. Using the new framework, all instances from the existing literature for this class of problems are solved to optimality. The paper also introduces and optimally solves a realistic multi-facility problem instance derived from an archipelago vulnerable to earthquakes. This problem instance is significantly more complex than any other instance described in the literature.     

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.     

An optimization framework for solving capacitated multi-level lot-sizing problems with backlogging

This paper proposes two new mixed integer programming models for capacitated multi-level lot-sizing problems with backlogging, whose linear programming relaxations provide good lower bounds on the optimal solution value. We show that both of these strong formulations yield the same lower bounds. In addition to these theoretical results, we propose a new, effective optimization framework that achieves high quality solutions in reasonable computational time. Computational results show that the proposed optimization framework is superior to other well-known approaches on several important performance dimensions.     

A hybrid algorithm for solving convex separable network flow problems

Based on computational experiments with different approaches to convex separable network flow problems a hybrid algorithm is developed and implemented. Phase one of the algorithm uses a rapidly converging series of piecewise linear secant approximations in order to determine a good solution within some distance of the optimum. Starting from this solution, a feasible direction method, based on reduced Newton directions, is used in the second phase of the algorithm to determine the optimal solution. Since nonlinear network flow problems tend to be degenerate, special emphasis is put on the construction of a basis that yields a strictly positive step length at the beginning of phase two of the hybrid algorithm.A number of test problems have been solved successfully. It is expected that the approach can be extended to solve large-scale problems with convex separable objective functions. Details of the implementation and computational results are presented.

---

Zusammenfassung Ausgehend von experimentellen Ergebnissen mit unterschiedlichen Lösungsverfahren für separable Netzwerkflußprobleme wurde ein zweistufiges Verfahren entwickelt und implementiert. Auf der ersten Stufe wird in einem iterativen Prozeß das zu lösende Problem mehrfach stückweise linearisiert. Man erhält eine bereits sehr gute Lösung. Mit dieser wird ein Richtungsverfahren initialisiert, das unter Verwendung reduzierter Newton Richtungen die optimale Lösung bestimmt. Das Richtungsverfahren bildet die zweite Stufe des Verfahrens. Da nichtlineare Netzwerkflußprobleme im allgemeinen stark entartet sind, wird zu Beginn der zweiten Stufe des beschriebenen Verfahrens eine Basis konstruiert, die eine positive Schrittlänge zuläßt.Es wurden zahlreiche Testprobleme mit bis zu 600 Knoten und 1400 Kanten mit dem beschriebenen Verfahren erfolgreich gelöst. Es wird erwartet, daß das Verfahren auch auf sehr viel größere Probleme mit konvexer, separabler Zielfunktion angewendet werden kann. Es wird auf Fragen zur Implementation eingegangen und es werden numerische Ergebnisse diskutiert.

     

An agent-based simulation of customer multi-channel choice behavior

Central European Journal of Operations Research - Experimenting with multi-channel operations in reality is both costly and risky, because it can severely affect a firm’s revenues,...     

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.     

An efficient and safe framework for solving optimization problems

Interval methods have shown their ability to locate and prove the existence of a global optima in a safe and rigorous way. Unfortunately, these methods are rather slow. Efficient solvers for optimization problems are based on linear relaxations. However, the latter are unsafe, and thus may overestimate, or, worst, underestimate the very global minima. This paper introduces QuadOpt, an efficient and safe framework to rigorously bound the global optima as well as its location. QuadOpt uses consistency techniques to speed up the initial convergence of the interval narrowing algorithms. A lower bound is computed on a linear relaxation of the constraint system and the objective function. All these computations are based on a safe and rigorous implementation of linear programming techniques. First experimental results are very promising.     

An Agent-Based framework for modeling and solving location problems

The high relevance of location problems in the operations research literature arises from their wide spectrum of real applications, including decision optimization in industrial management, logistics, and territorial planning. Most of these optimization problems fall into the class of NP-hard problems, motivating the search for heuristic and approximated algorithms. Currently, a great interest is being devoted to those optimization approaches yielding a concrete integration with spatial analysis instruments (such as Geographical Information Systems) that provide the user with an easy visualization of input data and optimization results.     

A Lagrangian relaxation approach for network inventory control of stochastic revenue management with perishable commodities

Airline seat inventory control is the allocation of seats in the same cabin to different fare classes such that the total revenue is maximized. Seat allocation can be modelled as dynamic stochastic programs, which are computationally intractable in network settings. Deterministic and probabilistic mathematical programming models are therefore used to approximate dynamic stochastic programs. The probabilistic model, which is the focus of this paper, has a nonlinear objective function, which makes the solution of large-scale practical instances with off-the-shelf solvers prohibitively time consuming. In this paper, we propose a Lagrangian relaxation (LR) method for solving the probabilistic model by exploring the fact that LR problems are decomposable. We show that the solutions of the LR problems admit a simple analytical expression which can be resolved directly. Both the booking limit policy and the bid-price policy can be implemented using this method. Numerical simulations demonstrate the effectiveness of the proposed method.     

Experience with a framework for developing heuristics for solving rich vehicle routing problems

According to Cordeau et al. (J Oper Res Soc 53(5):512–522, 2002) a good VRP heuristic should fulfill four criteria: accuracy, speed, simplicity, and flexibility. In this paper we report experience with a heuristic framework for solving rich vehicle routing problems (RVRP), which is based on rather simple heuristics. This heuristic framework has been implemented as flexible software framework. The user-friendly design enables flexible customization of problem-specific solvers. Our computational study on five RVRP reveals that the heuristic approach is rather robust with respect to parameterization and that the solvers which have been customized from the framework can compete with state-of-the-art special purpose developments.     

A novel recurrent nonlinear neural network for solving quadratic programming problems

This paper presents a new neural network for solving quadratic programming problems. The new model has a simple form, furthermore it has a good convergence rate with a less number calculation operation than the old models. It converges very fast to exact solution of the dual problem and by substituting in a formulation, the optimal solution of the original problem is obtained. Neural network model with one of numerical method is solved. Finally, simple numerical examples are provided for more illustration.     

Structural properties of Markov modulated revenue management problems

The admission decision is one of the fundamental categories of demand-management decisions. In the dynamic model of the single-resource capacity control problem, the distribution of demand does not explicitly depend on external conditions. However, in reality, demand may depend on the current external environment which represents the prevailing economic, financial, social or other factors that affect customer behavior. We formulate a Markov Decision Process (MDP) to maximize expected revenues over a finite horizon that explicitly models the current environment. We derive some structural results of the optimal admission policy, including the existence of an environment-dependent thresholds and a comparison of threshold levels in different environments. We also present some computational results which illustrate these structural properties. Finally, we extend some of the results to a related dynamic pricing formulation.     

A generalized approximation framework for fractional network flow and packing problems

We generalize the fractional packing framework of Garg and Koenemann (SIAM J Comput 37(2):630–652, 2007) to the case of linear fractional packing problems over polyhedral cones. More precisely, we provide approximation algorithms for problems of the form \(\max \{c^T x : Ax \le b, x \in C \}\), where the matrix A contains no negative entries and C is a cone that is generated by a finite set S of non-negative vectors. While the cone is allowed to require an exponential-sized representation, we assume that we can access it via one of three types of oracles. For each of these oracles, we present positive results for the approximability of the packing problem. In contrast to other frameworks, the presented one allows the use of arbitrary linear objective functions and can be applied to a large class of packing problems without much effort. In particular, our framework instantly allows to derive fast and simple fully polynomial-time approximation algorithms (FPTASs) for a large set of network flow problems, such as budget-constrained versions of traditional network flows, multicommodity flows, or generalized flows. Some of these FPTASs represent the first ones of their kind, while others match existing results but offer a much simpler proof.     

Airline network revenue management by multistage stochastic programming

A multistage stochastic programming approach to airline network revenue management is presented. The objective is to determine seat protection levels for all itineraries, fare classes, points of sale of the airline network and all dcps of the booking horizon such that the expected revenue is maximized. While the passenger demand and cancelation rate processes are the stochastic inputs of the model, the stochastic protection level process represents its output and allows to control the booking process. The stochastic passenger demand and cancelation rate processes are approximated by a finite number of tree structured scenarios. The scenario tree is generated from historical data using a stability-based recursive scenario reduction scheme. Numerical results for a small hub-and-spoke network are reported. This research is supported by the DFG Research Center Matheon “Mathematics for key technologies” in Berlin.