Introduction

Revenue management deals with the problem of effectively using perishable resources or products in industries or markets with high fixed cost and low margins, which are price-segmentable (see Cross 1997; McGill and van Ryzin 1999; Talluri and van Ryzin 2004). Revenue management is a complex problem which has to be supported by sophisticated forecasting methods/systems and optimization methods/systems.

Revenue management has its origin and has found broad application in the airline business, and here especially in passenger flight revenue management. Today almost all airline passenger revenues of over US $310 billion p.a. are actively managed through revenue management, and the industry claims to have generated as much as US $500 million in additional profits from the early 1980s onward (see Pompeo and Sapountzis 2002). Only recently, the concepts which have been developed for the passenger sector have been adequately modified and transferred to the cargo sector. As demonstrated later in this paper, an immediate transfer of the concepts developed for passenger airlines to the cargo airlines is not feasible since the two kinds of business, although at first sight offering a similar kind of transportation service, face differences in product type and in production which have consequences for scheduling and capacity planning as well as revenue management.

While the practice of revenue management is well-established in the passenger airline industry, and there is a vast amount of literature on concepts, methods, and implementations, the revenue management concept is underdeveloped in the cargo industry and there is only a small number of publications focussing on this application.

Kasilingam (1996) and Billings et al. (2003) analyze the major differences between passenger and cargo revenue management. While our approach is assuming a pure cargo airline with certain and fixed capacities, Kasilingam (1996) is concerned with the integrated management of the available belly space after accommodating passengers which in addition to forecasting cargo market demand requires to forecast capacity available for cargo sale. Slager and Kapteijns (2004) describe the implementation of cargo revenue management at KLM, which is based on calculating for every request a contribution margin, i.e., the revenue minus the variable costs related to handling, fuel etc., which is then checked against a minimum required margin, the so-called contract entry condition. These conditions are adjusted by route managers on a daily basis using information on historic and current booking profiles, current capacities and the market knowledge of the manager. This paradigm, which is called margin management principle, is very much in the flavor of the bid-pricing policy which is widely used in passenger revenue management.

Kleywegt and Papastavrou (1998, 2001) propose to model the cargo revenue management problem as dynamic stochastic knapsack problem. Yet, the approach allows only one capacity restriction and becomes computational intractable if extended to the two dimensional capacity situation in cargo revenue management. Pak and Dekker (2004) describe a bid-price acceptance policy for cargo revenue management which is based on (approximatively) solving a multidimensional on-line knapsack problem. This approach respects the multi-dimensionality of cargo capacity and demand, yet, it does assume that for each booking request the itinerary, i.e. the flights its uses is uniquely defined. With this assumption the flexibility (and also some of the complexity) of cargo routing versus passenger routing is neglected.

Our approach is different from all the above mentioned in so far, as it does not treat revenue management as an isolated problem, but respects that the decisions or alternatives at this operational level are constrained through structural decisions and capacity allocations made already on a higher and earlier management level: tactical planning, and, that the decisions made on these two levels should be driven through the same goal and coordinated.

In any airline, market-oriented planning on the tactival level requires the design of a profitable schedule and the allocation of resources like airplanes, staff, ground capacities etc. Here the objective is to maximize contribution to profit which is achieved by generating schedules and assigning airplanes allowing high load factors. When solving this complex design and decision problem highly sophisticated market-models are used to estimate market demand. The results of such forecasts are then used as data for schedule design and resource allocation.

Etschmeier and Matheisel (1985) describe the concept of an iterative schedule planning process based on two phases: schedule construction and schedule evaluation. In schedule construction, a central scheduling department develops a draft schedule, and in schedule evaluation, this schedule is evaluated by various operating departments in terms of feasibility, cost, and economic value. Based on these evaluations, the draft schedule is revised and a modified schedule is generated for a new evaluation.

While this generic process is similar for all types of airlines, the evaluation of schedules is quite different for cargo airlines and requires a special approach. In Antes et al. (1998) we have developed a mathematical model for evaluating cargo schedules. The focus of our model is the determination of the contribution to profit, that will accrue from a given schedule. For that purpose the model calculates the so-called optimal freight flow considering yield and operating cost. Here a freight flow is the assignment of demand to the capacities (flights) of a given schedule. Thus, the planning problem is to “determine the freight flow with maximum contribution to profit with respect to fixed market demand”.

For passenger airlines, Berge and Hopperstad (1993) have proposed the “Demand Driven Dispatch”-concept. Here airplanes with different capacities but similar crew-requirements are assigned to flights, depending on the actual demand/booking situation to increase the load factor and contribution to profit. For this purpose so-called swap-potentials for resources have to be evaluated in a pro-active manner by (re-)solving fleet assignment problems and aircraft routing problems. This concept has been generalized by Gershkoff (1998). Yet, the problem with these just-in-time scheduling concepts is the complexity of identifying feasible changes/feasible schedules, for instance with respect to maintenance constraints etc., in nearly “real time” and the actual lead times to implement proposed changes in day-to-day operations.

Hence in operational control the schedule and the capacity allocation is assumed to be fixed, and the problem is to adequately respond to bookings, e.g. the actual market demand such that the yield obtained from the schedule is maximized. At this point changes in the schedule and/or capacities are possible only at a marginal level, and the dominant instruments for controlling efficiency are prizing (and over-) booking strategies. Thus, conceptually thinking, the operational problem in cargo revenue management is to “re-optimize freight-flows due to bookings and price-changes”. And as we will show, this problem can be tackled by the same model and method which has been developed for schedule evaluation on the tactical planning level.

Thus, in this paper we propose the application of the model and methods which we have developed for medium term tactical planning to the short term operational problem of revenue management. The motivation of this proposal and study is twofold: First, we think that operational control and tactical planning should be governed and guided by the same concepts and factors: objectives, constraints, and data to minimize loss of profit potential during implementation and increase the efficiency of the planning process. Secondly, as will be demonstrated in this paper, the planning methods are functional on the operational level, too.

A conceptual model of air cargo transportation

A cargo airline offers the conceptually simple service to transport a certain amount of goods from an origin to a destination within a certain time interval at a given price. For this purpose the airline keeps and/or leases capacities for transporting goods to, from, and between airports. The tactical planning problem of such airlines is to design a (weekly) flight schedule of so-called legs which allows the most profitable service of the estimated market demand for the next period (half a year, say). Then, on the operational level booking requests have to be assigned to specific flights of the fixed flight schedule.

There are several differences between the situation in passenger transportation and cargo transportation which make the development of concepts, models and systems for planning as well as revenue management more complex in the cargo environment:

  1. a)

    While the demand in the passenger sector is one dimensional (seat) and kind of smooth, the demand in the air cargo sector is heterogenous and lumpy with completely different capacity requirements for single booking requests (compare for instance volume requirements for documents versus industrial aggregates). This leads to a multi-dimensional characterization (weight, volume, classification, handling needs etc.) of cargo units.

  2. b)

    While passengers usually book return-flights, cargo demand is one-way in general which leads to geographically unbalanced transportation patterns with respect to structure and volume of cargo.

  3. c)

    Yet, the most subtle difference is that passengers are booking so-called itineraries, e.g. specific sequences of flight connections, so-called legs leading the passenger from the origin to the destination of their journey. Thus, a passenger booking a flight from Cologne (CGN) to Chicago (ORD) via Frankfurt (FRA) and New York (JFK) on a given date, has to be given a seat reservation on three specific flights (CGN, FRA), (FRA, JFK) and (JFK, ORD). In the cargo business customers book a transportation capacity from an origin to a destination, with a certain service level, e.g. within a certain time-window. In general, the cargo customer is not interested in the specific routing of his package. Hence the airline has some degree of freedom how and when to assign requests to specific flights and this difference leads to different planning models.

For schedule evaluation as well as revenue management the key problem is to “assign market demand to the schedule”. Market demand can be described as a set of estimated and/or booked service requests. And such a request has several attributes with the origin and destination airport being the dominant characteristic. Therefore, such transportation requests are commonly referred to as O&D’s or O&D pairs in the cargo airlines terminology. Conceptually, the object class OD of O&D’s can be modelled as a complex 5-ary recursive relationship type between the entity type AIRPORT, playing the role of an origin and destination respectively, TIME, playing the role of availability and due time respectively, and PRODUCT with attributes specifying the quantity (kg), the volume (m 3) and the yield/freight rate ($/kg) etc. The schedule on the other hand can be described as a set of so-called legs. The concept of a leg stems again from the airlines terminology, meaning a direct flight between two airports offered at the same time every week. Conceptually, we model the object class LEG as a 4-ary recursive relationship type between the entity type AIRPORT playing the role of an origin (from) and a destination (to) and TIME, playing the role of a departure and an arrival time, respectively, with attributes specifying the capacity of the leg (kg), the operating cost ($/kg) etc. The relevant information reflecting ground handling, that is the time and cost for import, export, and transfer of goods at the airports is modelled via a relationship type HANDLING associating the entity types AIRPORT and PRODUCT. Figure 1 gives the graphical representation of this conceptual schema, using the common symbols of the entity relationship model (cf. Elmasri and Navathe (2004)).

Fig. 1
figure 1

Conceptual schema for air cargo transportation

Full size image

Note that all attributes mentioned above are data for the decision model and have to be instantiated. Now, the decision problem in planning as well as revenue management, is captured in the relationship type/the association BOOKING between the entity types OD and LEG. More precisely the problem is to determine the values of its attribute “amount” for every (OD, LEG)-pair. Or, in the terminology of databases, the amount-attribute is a so-called “derived attribute” with the integrity constraints defining feasible values as well as the evaluation of different associations captured in a mathematical optimization model. In tactical planning one can think of initializing this model with no associations at all, i.e. the amount-values are zero and, given the data for the entire (expected) demand, we have to simultaneously “derive” optimal amount-values. When using this conceptual model in revenue management, one can think of initializing the model with an eventually large number of fixed associations, which represent bookings or which are derived from additional (expected) demand, and there is just one booking request which has to be evaluated and associated on top.

In the following two sections we will introduce the mathematical optimization models which represent and formalize this view of the decision problems associated with the two scenarios.

The model for O&D schedule planning

Every flight schedule defines a so-called time-space network G=(V, E) with V being the set of nodes representing the airports at a certain point of time. The arc set E is composed from two subsets, a set of flight arcs which represent the legs and connect the associated airports at departure and arrival time, respectively, and a set of ground arcs which connect two nodes representing the same airport at two consecutive points in time. Associated with every leg/arc e∈E is the weight capacity u e measured in kg, the volume capacity v e measured in m 3 and the operating cost c e measured in $ per kg.

Now the different O&D’s define different commodities which have to be routed through this network, and the so-called multi-commodity flow problem (see Ahuja et. al. (1993)) is the problem to determine optimal assignments of O&D’s/commodities to legs/arcs such that (part of) the demand is routed from origins to destinations. Figure 2 shows the representation of two specific itineraries connecting Cologne (CGN) with Chicago (ORD) via Frankfurt (FRA) and New York (JFK), and via Munich (MUC), respectively, in a time space network.

Fig. 2
figure 2

Itineraries in a time-space network

Full size image

In our models we use the symbol od for representing an O&D-commodity and OD as the set of all commodities/O&D’s. Associated with a commodity/O&D od∈OD is a specific demand b od measured in kg, a value d od giving the volume per kg and a freight rate or yield value y od measured in $ per unit of commodity od. For every leg e∈E let o(e) be the origin airport and d(e) be the destination airport. Also, let origin (od) be the origin and destination (od) be the destination of od∈OD, respectively.

The first formulation/mathematical model is the so-called arc-flow-model, a linear program which is the immediate implementation of the conceptual model presented in Fig. 1. Here we introduce decision variables x e, od giving the amount of commodity od∈OD which is transported over the arc e∈E. This leads to the mathematical formulation of the planning problem as an arc-flow multi-commodity flow model.

Arc-flow-Model

$$\begin{array}{*{20}c} {{\max {\sum\limits_{od \in OD} {{\left( {{\sum\limits_{{\mathop {e \in E}\limits_{o{\left( e \right)} = o{\left( {od} \right)}} }} {y^{{od}} } } \cdot x_{{e,od}} - {\sum\limits_{e \in E} {c_{e} \cdot x_{{e,od}} } }} \right)}} }}} \\ {{{\sum\limits_{{\mathop {e \in E}\limits_{0{\left( e \right)} = i} }} {x_{{e,od}} } } - {\sum\limits_{{\mathop {e \in E}\limits_{d{\left( e \right)} = i} }} {x_{{e,od}} } }\left\{ {\begin{array}{*{20}l} {{ \leqslant b^{{od}} } \hfill} & {{{\text{if }}i = o{\left( {od} \right)}} \hfill} \\ {{ \geqslant - b^{{od}} } \hfill} & {{{\text{if }}i = d{\left( {od} \right)}} \hfill} \\ {{ = 0} \hfill} & {{{\text{else}}} \hfill} \\\end{array} } \right.}} \\ {{{\text{for }}i \in V,od \in OD}} \\ {{{\sum\limits_{od \in OD} {x_{{e,od}} \leqslant u^{e} } }\quad {\text{for }}e \in E}} \\ {{{\sum\limits_{od \in OD} {d^{{od}} x_{{e,od}} \leqslant v^{e} } }\quad {\text{for }}e \in E}} \\ {{x_{{e,od}} \geqslant 0}} \\\end{array}$$

This model is not very well suited, neither for the planning situation nor for an adaption to revenue management. It does not capture the complex time-window constraints associated with the demand, it does not contain any constraints from ground handling etc. To be able to incorporate these and other constraints into the decision, the so-called path flow formulation should be used which can also be adapted rather nicely for use in revenue management.

The so-called path-flow model is based on the obvious fact that any unit transported from an origin to a destination has to be routed over a sequence of legs (possibly only one leg), a so-called path or itinerary connecting the origin node with the destination node in the network. A path or itinerary for an O&D/commodity od is a sequence p=(l 1,...,l r(p)) of legs l i ∈E, r(p)≥1 with the following properties

$$\begin{array}{*{20}c} {o{\left( {l_{1} } \right)} = origin{\left( {od} \right)}} \\ {d{\left( {l_{i} } \right)} = o{\left( {l_{{i + 1}} } \right)}\quad i = 1,...,r{\left( p \right)} - 1} \\ {d{\left( {r{\left( p \right)}} \right)} = destination{\left( {od} \right)}} \\ \end{array} .$$

Such a path p is called od-feasible if additional requirements are fulfilled which vary with the problem definition. Here we consider several types of constraints which concern due dates, transfer times and product compatibility. For every O&D/commodity od we denote by P od the set of od-feasible itineraries and by S we denote the union of all P od sets. A path may be feasible for many different O&D’s. In our model we have to distinguish these roles and consider multiple copies of the same path/the same legs assigned to different commodities/O&D’s. Then the relation between arcs/legs and itineraries is represented in a binary indicator δ: E×S→{0,1}

$$\delta _{e} {\left( p \right)}: = \left\{ {\begin{array}{*{20}l} {1 \hfill} & {{{\text{if leg }}e \in E\,\,{\text{is contained in path }}p} \hfill} \\ {0 \hfill} & {{{\text{else}}} \hfill} \\ \end{array} } \right..$$

Note that od-feasibility of paths can be checked algorithmically and, given an itinerary p∈P od, we can calculate \(c{\left( p \right)}: = {\sum\limits_{e \in E} {c_{e} \delta _{e} {\left( p \right)}} } = {\sum\limits_{e \in p} {c_{e} } }\) the operating cost as well as \(y^{{od}} {\left( p \right)}: = y^{{od}} - {\sum\limits_{e \in p} {c_{e} } }\) the contribution to profit per kg of commodity od which is transported over p. This calculation as well as the construction of the set P od is done outside our model using a module called “connection builder” and is then given to the model as input data. In the model we introduce a decision-variable f(p) for every p∈P od giving the amount (in kg) transported via p, and the problem is to select the optimal combination of paths giving maximal contribution to profit which again leads to a linear program.

Path-flow-model

$$\max {\sum\limits_{od \in OD} {{\sum\limits_{p \in P^{{od}} } {y^{{od}} {\left( p \right)}f{\left( p \right)}} }} }$$
(1)
$${\text{s}}{\text{.t}}{\text{. }}{\sum\limits_{od \in OD} {{\sum\limits_{p \in P^{{od}} } {\delta _{e} {\left( p \right)}f{\left( p \right)} \leqslant u_{e} } }\quad \forall e \in E} }$$
(2)
$${\sum\limits_{od \in OD} {{\sum\limits_{p \in P^{{od}} } {\delta _{e} {\left( p \right)}d^{{od}} f{\left( p \right)} \leqslant v_{e} \quad \forall e \in E} }} }$$
(3)
$${\sum\limits_{p \in P^{{od}} } {f{\left( p \right)} \leqslant b^{{od}} } }\quad \forall od \in OD$$
(4)
$$f{\left( p \right)} \geqslant 0\quad \forall od \in OD\quad \forall p \in P^{{od}} .$$
(5)

The advantage of the itinerary-based model over the leg-based model is the possibility to consider rather general and complicated constraints for feasibility of transportation during the path-construction phase in the connection builder. Keeping this complexity outside the optimization allows to apply the same standard (LP-)solution procedure and standard LP-solver for a wide range of models representing different planning situations.

Moreover, the path-flow-model allows for scaling, i.e. it is not necessary to construct all feasible paths beforehand. Working with a “promising subset” of paths only, reduces the size of the problem instance but may lead to solutions which although not optimal in general, are highly acceptable in quality. Finally, applying the delayed column generation technique allows to generate feasible paths on the run during optimization and thus keeps problem size manageable throughout the optimization process. This model and algorithmic approach is the basis for the system SYNOPSE (“System zur Netzoptimierung und Planung Strategischer Entscheidungen”, which translates in English as “System for Network Optimization and Planning of Strategic Decisions”), see Antes et al. (1998), an interactive decision support system for analyzing schedules. In Derigs and Zils (2001) we have applied the schedule planning model to the strategic problem of analyzing alliances of cargo airlines. In the following we will demonstrate how this concept and model can be transferred to the operational level, i.e. to the problem of revenue management.

The model for O&D revenue management

The model in Section 3 has been developed for the problem to optimally assign an expected demand to a fixed schedule. In revenue management, demand occurs over a longer time period, a year say, and the limited resources have to be “booked” sequentially. When a booking or reservation is made, the airline does not need to assign the O&D to a specific itinerary immediately, it only has to ensure that at operation time capacities are available, i.e. it has to ensure that at any time there exists a feasible routing for all booked O&D’s. This situation and requirement is captured in the following optimization model.

In this model we assume a set B of accepted bookings and we distinguish between

  1. –

    β k the demand which is already booked and

  2. –

    b k the additional forecasted future demand for k∈OD and

  3. –

    a single booking request r for a commodity k(r)∈OD with demand \(\widetilde{\beta }^{r} \),

and we assume an (expected) yield y k for every commodity k∈OD. The model can be used to evaluate the acceptability/profitability of a specific request r at a given price y r and for “dynamic pricing”, i.e. the determination of the minimum acceptable yield for request r.

Revenue-management-model RM (B, r)

$$\max {\sum\limits_{k \in OD} {{\sum\limits_{p \in P^{k} } {y^{k} {\left( p \right)}f{\left( p \right)}} }} }$$
(6)
$${\text{s}}{\text{.t}}{\text{. }}{\sum\limits_{k \in OD} {{\sum\limits_{p \in P^{k} } {\delta _{e} {\left( p \right)}f{\left( p \right)} \leqslant u_{e} \quad \forall e \in E} }} }$$
(7)
$${\sum\limits_{k \in OD} {{\sum\limits_{p \in P^{k} } {\delta _{e} {\left( p \right)}d^{k} f{\left( p \right)} \leqslant v_{e} \quad \forall e \in E} }} }$$
(8)
$${\sum\limits_{p \in P^{k} } {f{\left( p \right)} \leqslant b^{k} + \beta ^{k} } }\quad \forall k \in OD$$
(9)
$${\sum\limits_{p \in P^{k} } {f{\left( p \right)} \geqslant \beta ^{k} } }\quad \forall k \in OD\backslash {\left\{ {k{\left( r \right)}} \right\}}$$
(10)
$${\sum\limits_{p \in P^{r} } {f{\left( p \right)} \geqslant \beta ^{r} + \widetilde{\beta }^{r} } }$$
(11)
$$f{\left( p \right)} \geqslant 0\quad \forall p \in P^{k} ,k \in OD.$$
(12)

Note that the application of RM (B, r) is started with no booking, i.e. β k=0, k∈OD, and no request, which is equivalent to the planning model from Section 3. Then the set B is sequentially enlarged introducing accepted booking request. Thus at any time the booking model RM(B) which is obtained from RM(B, r) by omitting r and replacing inequality Eq. 11 by an additional inequality of type Eq. 10 for k=r is feasible and we can start the solution of RM(B, r) from the optimal solution of RM(B). Now the acceptability/profitability (and the option price) for request r depends on the difference between the optimal values of RM(B, r) and RM(B).

Note that when solving RM(B, r) already booked requests may be rescheduled, i.e. during the entire process booked commodities may be associated to different (sets of) paths. Thus the model and solution process makes use of this flexibility.

We will only outline here the general approach for solving RM(B, r), which is based on applying the column generation technique to the multi-commodity flow problem. Solving RM(B) by any LP-technique we obtain an optimal dual solution with values

  1. –

    w e for every constraint of type Eq. 7,

  2. –

    z e for every constraint of type Eq. 8, and

  3. –

    σ k for every constraint of type Eqs. 9, 10 and 11.

Based on these values the reduced cost for an itinerary p∈P k, k∈OD, is defined as

$$\overline{c} {\left( p \right)}: = y^{k} - {\sum\limits_{e \in p} {{\left( {c_{e} + w_{e} + d^{k} z_{e} } \right)} - \sigma ^{k} } }$$

Thus, if an itinerary p∈P k has positive reduced cost \(={c}{( p )}\) then transporting (one unit of) commodity k over this itinerary increases the contribution to profit.

Such a path can be found by determining p*, the shortest path from origin(k) to destination(k) with respect to the modified arc cost c e ′:=c e +w e +d k z e . If the length of p* exceeds y k−σ k then no path of positive reduced cost exists. Otherwise, sending flow over p* will increase the contribution to profit.

Yet, there is one problem remaining: The capacity δ of the shortest path p* will in general not be equal to \(\widetilde{\beta }^{r} \), the required amount of the current request r. If \(\delta \geqslant \widetilde{\beta }^{r} \), we will increase f (p*) by \(\widetilde{\beta }^{r} \) (and eventually introduce the column associated with p* into the constraint matrix) and we have solved RM (B, r). Otherwise, we can only tentatively increase f (p*) by δ, update \(\widetilde{\beta }^{r} : = \widetilde{\beta }^{r} - \delta \) and repeat the process, i.e. the search for another path with unused capacity. More information on the difficulties arising during the process and on several computationally effective strategies can be found in Bartodziej and Derigs (2004). In the following section we will describe the results from a simulation study which we have conducted for evaluating our approach.

A simulation study for evaluating the O&D revenue management approach

We have applied the model and method described in Section 4 to a set of benchmark instances. These instances were constructed from data obtained in a marketing study (cf. Zils (1998, 1999)). For several airlines O&D-matrices were estimated using a simple gravity model. This study was conducted to support the development and evaluation of models and systems for planning, and its results have been adapted for generating the scenarios of our revenue management simulation. From the different benchmark problems given in Zils (1999)] we have extracted three scenarios. The characterization of these three benchmark problem instances P10, P64, and P79 is illustrated in Figs. 3–5.

Fig. 3
figure 3

Characteristics of instance P10

Full size image
Fig. 4
figure 4

Characteristics of instance P64

Full size image
Fig. 5
figure 5

Characteristics of instance P79

Full size image

The data of an instance is maintained in three relations/tables. The schemata of these relations are given in Tables 1, 2, 3.

Table 1 Leg table (represents the schedule)
Full size table
Table 2 O&D table
Full size table
Table 3 Handling table
Full size table

Note that in the leg table we store information on rotations (i.e. the sequences of legs which are served by the same airplane). This information is necessary to calculate the handling cost. We do not go into more detail on this aspect here.

From this data instances for the schedule evaluation problem were generated and solved to optimality to serve as the starting solution for the revenue management process. During the revenue management process booking requests are generated and evaluated solving problems of type RM (B, r), and if accepted they initiate a modification of the production plan and updates of the forecast. This relation between planning and revenue management is reflected in Fig. 6.

Fig. 6
figure 6

Revenue management process

Full size image

In the revenue management simulation the (aggregate) O&D-quantities of the planning model have been broken down to the level of od-booking requests in the following way:

Let a od be an estimated total demand for a specific od∈OD then we generated a sequence α 1 od,...,α n (od) od with the following property:

$${\sum\limits_{i = 1}^{n{\left( {od} \right)}} {\alpha ^{{od}}_{i} } } = a^{{od}} \;{\text{and}}\;\frac{{a^{{od}} }}{{\gamma _{1} }} \leqslant \alpha ^{{od}}_{i} \leqslant \frac{{a^{{od}} }}{{\gamma _{2} }}\;{\text{for}}\;i = 1,...,n{\left( {od} \right)}\;{\text{with}}\;\gamma _{1} > \gamma _{2} \geqslant 1.$$

By this construction we ensure that the α i od’s are within a certain percentage interval with respect to a od. Then we applied a random perturbation to obtain the lumpy booking requests

$$\widetilde{\beta }^{{od}}_{i} : = {\left( {1 + \delta } \right)} \cdot \alpha ^{{od}}_{i} \,{\text{with}}\,\delta \in {\left[ { - \Delta ,\,\Delta } \right]}$$

and a random sequence of all generated bookings was generated. Then, this booking pattern of lumpy requests was used to define the \(\widetilde{\beta }^{r} \)-sequence and the RM (B,r)-problem instances to be solved.

As we have mentioned already, the effectivity of any revenue management method/system is not only driven by the optimization module, but is highly depending on the soundness of the forecasting information. In our computational study we could only simulate the influence of forecasting at a very rudimentary level. Obviously, in a more practical evaluation one would have to integrate the optimization model/system into an integrated environment containing forecasting and pricing modules. In our simulation study we used the following simple forecast-update: Since in every iteration the actual booking \(\widetilde{\beta }^{r} ,\,\widetilde{\beta }^{r} = \widetilde{\beta }^{{od}}_{j} \) say, represents part of the expected/forecasted demand b od of the associated O&D, we have to update the remaining/forecasted demand. Yet, we did not reduce the forecast by \(\widetilde{\beta }^{{od}}_{j} \) but by α j od to reflect the difference between initial forecast and real booking requests. Simple extensions of our simulation model could correlate the change of the remaining demand with the δ-perturbation of the request, and, also cancellations could easily be incorporated. In Fig. 7 the concept shown in Fig. 6 is presented on a more detailed level.

Fig. 7
figure 7

Concept of revenue management simulation

Full size image

The efficiency of our approach, i.e. its solution quality and its computational effort is highly dependent on the implementation. And here we have to distinguish between two main aspects which are strongly related and interdependent:

  1. –

    the implementation of the basic column generation technique, and,

  2. –

    the integration of the optimization into the revenue management process.

We have developed about a dozen different strategies for solving RM(B, r) based on different implementations of the column generation technique. In column generation there is a trade-off between quality and speed depending on the frequency of re-optimizing the master problem/calculating the actual dual prices. A detailed description of these computational aspects is beyond the scope of this paper. A computational study on these strategies is given in Bartodziej and Derigs (2004).

Another strategy to reduce the computational effort is to relax the on-line optimization requirement and to accept bookings, which are uncritical with respect to capacity and apparently profitable without evaluation and optimization, and to update the set of booked requests and construct a feasible freight flow using the model in a batch processing kind of mode. Similarly, one could give up the requirement to decide on the acceptance of requests sequentially one by one and to accumulate sequences S=(r 1, r 2,...) of requests to blocks or batches and then decide on which requests are accepted in one step. And here again one could follow two strategies: to decide on the acceptance of the requests in S based on the optimal dual prices for RM(B) or to re-optimize, i.e. to solve a variant of RM(B, r) obtained by adapting inequality Eq. 11:

$${\sum\limits_{p \in P^{r} } {f{\left( P \right)} \geqslant \beta ^{r} + \widetilde{\beta }^{r} \,{\text{for}}\,r \in S} }$$
(11’)

Especially, the running time for solving the LP’s becomes unacceptable high for problem instances of larger size. Thus in these realistic and time-critical environments additional means to reduce the size of the LP-master problems should be applied. Here one could reduce the number of paths in the search by eliminating the allowable number of legs per path. Another option would be to decompose the network. Then the first step in the revenue management decision would be to design every request to a suitable sub network.

The measurement of the quality of a (final) solution is quite difficult. An obvious measure would be the ratio between the yield potential and the realized yield. Yet, since it is a dynamic process and not a static problem, there is no natural definition for the maximum yield potential. Here, the value of the optimal solution of the planning model can only be an estimation or rational substitute. Using this value as a reference, one can observe rather significant differences among the different strategies with respect to quality.

In Fig. 8 we show the trade-off between quality and computational efficiency with respect to batching. Here, we display results for the following strategies

  1. –

    sequential evaluation/no batching

  2. –

    k-batching with blocksize “k”, k=5,10,100

Fig. 8
figure 8

Comparison of implementation strategies

Full size image

The results were obtained for a scenario generated with γ 1=5, γ 2 = 1 and Δ=0.1 leading to 2,533, 6,521 and 2,206 requests for problems P10, P64 and P79, respectively.

The contribution to profit is given as percentage of the contribution to profit of the optimal solution to the associated planning model. We have divided the total running time for a run by the total number of requests and compare the computational efficiency of the different approaches on the basis of processing time per request (given in CPU-ms). It turns out that the behavior is not monotone over all the examples. Yet, for every example/problem instance one can establish that there exist different “optimal batch sizes” for both measures, and thus an interval of effective batch sizes can be identified.

Final remarks

As cargo airlines (and shipping lines for this matter as well) are becoming increasingly under pressure, revenue management could help to improve the performance significantly. One cargo airline was able to increase yield by 5%, while the average industry yield fell by 15% in the same period, only by segmenting their products (express vs. standard) and reserving capacity on fixed routes for higher yield products (see Pompeo and Sapountzis (2002)). Assuming that even more intelligent cargo revenue management systems based on dynamic O&D assignment, as described above, could increase average yield by 1%, the industry could generated additional bottom-line profits of more than US $300 million p. a.

However, to be practical, the necessity to generate answers for booking requests in near real time is a demanding task for its own. For a leading cargo airline the number of O&D’s can easily reach more than 50.000 different O&D’s (incl. product categories), and over a week hundreds of individual bookings could be requested for a specific O&D. Not only is the use of extremely fast (constrained) shortest path algorithms which first try to use itineraries which are already in the solution an absolute must, moreover, strategies to combine single bookings into blocks which are then evaluated in one iteration seem to be a promising strategy.

After all one can say that using these advanced algorithmic ideas and high speed computers, O&D revenue management based on mathematical planning programs could be(come) feasible in practice and significantly improve the performance of cargo airlines (even if O&D management is only applied to a sub-set of their overall O&D’s and booking requests).