Keywords

1 Introduction

Airlines traditionally prevent high fare paying passengers from buying down into lower fare classes by associating restrictions to each fare level. They make different fares correspond to different products whose characteristics fit the needs of only one class of customers. This fare policy is reasonable in presence, for each class, of a product-oriented demand, interested to a specific fare product and independent of the availability of cheaper services [25]. The emergence of low-cost carriers shows that this assumption of independent demand segments is becoming more and more unrealistic. Indeed, low-cost carriers offer a single type of product to price-oriented passengers that ignore ticketing restrictions and purchase solely on price [6]. Also, these passengers typically exploit the potentiality of the Internet-based distribution channels to compare the fares of several different airlines.

Precise modelling of customer choice behaviour has been a subject of growing interest in recent years [7, 16]. In fact, the application of pricing algorithms that assume independent demand to a non-segmented market gives rise to the spiral-down effect: customers willing to pay a higher fare but accepting a lower one if available are recorded as lower fare demand when the cheaper product is available. Then, forecasts built on these cheaper product sales underestimate demand for higher fare levels and more low fare products than necessary are made available and, consequently, revenues spiral down [10]. To contrast such an effect, the recent literature proposes pricing policies based on Revenue Management (RM) approaches that segment passengers according to their willingness to pay instead of their compliance to restrictions [27].

In the present work we study the application of these RM techniques to the air cargo industry. Specifically, we propose and analyse the performances of two bid-price based heuristic approaches to tackle a stochastic price-oriented demand of cargo shipments.

The RM approaches are essential tools for cargo shipment as the demand in this industry is in general price-oriented, although some segmentation of the demand by offered product still exists. The same shipment may be charged differently depending on the guaranteed delivery time (express delivery vs. standard delivery). In addition, some airlines, e.g., Lufthansa and American Airlines, offer further optional product features that include boarding priority, pick-up time and location at destination.

The air cargo industry accounts for tens of millions of dollars a year in revenue and, according to the International Air Transport Association (IATA), has stabilised and even shown some weak signs of reprise in certain markets (http://www.iata.org/pressroom) after the recession following the 2008 crisis.

Price oriented demand has been a much explored field of study in RM in recent years. In particular, Westermann [27] describes how to integrate revenue management and dynamic pricing concepts based on willingness to pay at airlines with different fare structures. Hopperstad and Belobaba [12] introduce seat inventory control schemas in the single-leg case when demand is not independent from fare class. They forecast the total demand at the lowest fare and repartition it to the different higher fare classes by taking into account the passengers’ willingness to pay higher fares. Thus they are in the position to compute the booking limits using traditional algorithms. Fiig et al. [11] address the coexistence of restricted and unrestricted fare structures in markets sharing the same leg(s) on a network. Using simulations, Cléaz-Savoyen [9] shows that the simultaneous application of the approaches described in Fiig et al. [11] and Hopperstad and Belobaba [12] allows a partial mitigation of the spiral down effect in certain markets. Unfortunately, RM approaches used for passenger flights cannot be directly applied to cargo flights. Indeed, Kasilingam [14], Billings et al. [5] and Slager and Kapteijns [22] point out that the structure of demand and services in the two industries present many differences. For example, each passenger requires just one seat, while each cargo shipment consumes capacity in terms of both weight and volume. Passenger demand presents seasonality patterns while the cargo one is usually more erratic, hence the former is easier to forecast than the latter. The number of passenger customers is usually greater than cargo customers. However, the latter ones make larger bookings, so the behaviour of few of them can significantly influence the prices paid by other customers, a condition which is generally not true for passengers.

In bid-price RM policies, threshold, or "bid", prices are set for each unit of resource. This kind of price setting was first introduced for airlines’ seat booking by Smith and Penn [23] and Simpson [21]. Since then, they have become widely used due to their conceptual simplicity and easiness of implementation. Talluri and van Ryzin [24] give a comprehensive overview of bid-price techniques pointing out the difficulties arising in determining the right bid. Generally speaking determining the optimal bids may be computational cumbersome, even because they may change dynamically as the flight departure times approach. For this reason, Adelman [1] proposes to compute dynamic bid-prices through a Linear Programming (LP) approximate model. A drawback of this approach is that the number of variables grows exponentially. Bijvank et al. [4] aim at improving robustness towards uncertainty in the demand. To this end, they propose three heuristics that exploit scenario-based stochastic programming methods. Pricing policies for a price-oriented demand are also determined through dynamic programming approaches. As an example, Zhang [28] introduces a dynamic programming decomposition approach and shows that it outperforms static bid-fares one even when bids are frequently recomputed. Popescu et al. [19] use a dynamic programming approach to determine the bid-prices in presence of large shipments. Differently, in presence of small shipments they use a bid-price approach whose bids are obtained by approximating the booking requests with passenger arrival models.

Different authors discuss the consequences of imprecise demand models or incomplete demand data in the air cargo industry. Totamane et al. [26] point out that imprecise demand forecasting causes most cargo airlines to operate at an average ratio between the utilized capacity and the total capacity, the so-called load factor, of 50–70 %. To overcome this limit, they propose a learning algorithm, based on a producer/consumer model, which is able to deliver a 9 % revenue improvement. Luo et al. [17] address the problem of defining overbooking policies that take into account that most booking reservation systems do not keep track of unfulfilled requests. In this framework, they develop an overbooking model that, under appropriate assumptions, they prove providing the optimal overbooking limits. Amaruchkul et al. [3] study the role of asymmetrical information on customers’ demand, operating cost, margin and reservation profit. They investigate under which conditions the maximum combined profit of the involved agents can be obtained in the presence of such an asymmetry. The same authors, in a previous work [2], address uncertainty in package volume, whereas Huang and Hsu [13] and Chew et al. [8] deal with uncertainty in the supplied capacity.

The remainder of this paper is organised as follows. In Sect. 2, we formulate the problem of interest using dynamic programming. In Sect. 3, we introduce two heuristic bid price-based approaches. In Sect. 4, we describe the experiments we carried out to compare the performances of the algorithms and we address the analysis of the results. Finally, in Sect. 5, we draw some conclusions.

2 Dynamic Programming Formulation

In this section, we formulate the problem that a revenue manager faces when he tries to maximise a cargo flight expected revenues as a dynamic programming problem.

The revenue manager works within a single user-class framework, i.e., demand is not segmented or restricted. We assume that there exists a finite set F of M fares F = {f 1 , …, f M } which are unknown to the customer. The revenue manager has to decide which of the M fares to propose to the customer, and this decision is taken a posteriori, i.e., after having known the size of the shipment, and within the limits set by the following marketing rules that we assume to hold:

2.1 Assumptions

  1. 1.

    A shipment can be accepted only if the flight has residual capacity in terms of volume and weight to accommodate it.

  2. 2.

    A shipment must be charged proportionally to its weight, so that the revenue for a shipment is computed as its weight times the paid fare.

  3. 3.

    The company discourages last minute opportunistic behaviour, hence the succession of fares displayed to the users must be non-decreasing as time approaches flight departures.

  4. 4.

    No price negotiation is allowed.

  5. 5.

    Customers are served one at a time.

We observe that Assumption 2 may sound quite simplistic. However, the results that we present in this work generalize trivially when more complex cost functions are considered.

We also stress the following consequences of the above assumptions. Assumptions 1 and 4 imply that a customer is lost if the displayed fare does not satisfy his willingness to pay or if there is not enough weight and volume capacity to accommodate his shipment. Also, the revenue manager will always display no more than one fare at a time, since customers are price-oriented and hence always purchase the necessary capacity for their shipments at the lowest available fare that is not higher than their willingness to pay.

Hereafter, we denote by:

  • {0, 1, …, t, t + 1, …, T} the set of the time instants at which customers can arrive and be served, 0 is flight reservation opening and T is the closing time;

  • t k ∈ {0, …, T} the arrival time of the k customer;

  • ϕ t the probability a customer shows up at time t;

  • f the generic fare;

  • C w and C v the flight storage capacities in weight and volume, respectively;

  • (ω, υ) the size of the generic shipment, where ω and υ are its weight and its volume, respectively; both are integer values less than or equal to (C w , C v );

  • p km the customer k willingness to pay toward a fare f m  ∈ M, that is the probability that a customer arriving at time t is willing to pay f m ω to send a package of size (ω, υ);

  • q ωυ the probability that a shipment has size (ω, υ);

  • J m (t, w, v) the function that returns the expected optimal revenues from time t on under the hypothesis that the revenue manager displays in t a fare f m and there are residual capacities w in weight and v in volume.

At each time t, being w and v the residual capacities, the revenue manager faces the following dynamic programming problem:

$$ \begin{aligned} J_{m} (t,w,v) = [(1 - \phi_{t} ) + \phi_{t} \sum\nolimits_{{_{{\left( {\omega \upsilon } \right) > \left( {w,v} \right)}}}} q_{\omega \upsilon } {} ]\,J_{m} (t + 1,w,v) \\ \quad + \phi_{t} \sum\nolimits_{{_{{\left( {\omega \upsilon } \right) \leq \left( {w,v} \right)}} }}q_{\omega \upsilon } {\text max}_{j > m} {\{ p_{kj} (f_{j} \omega + \, J_{j} (t + 1,w - \omega ,v - \upsilon )) + ( 1- p_{kj} )J_{j} (t + 1,w,v)\} } \\ \end{aligned} $$
(1)

with final conditions: J m (T, w, v) = J m (T, 0, v) = J m (T, w, 0) = 0 for all 0 ≤ w ≤ C w and 0 ≤ v ≤ C v .

The first term of Eq. (1) r.h.s. states that the expected revenues from t on coincide with the expected revenues from t + 1, when no customer shows up in t, or if the size of the shipment exceeds the available capacity, when a customer shows up in t. Differently, the second term states that, when a customer shows up, the revenue manager must choose the fare to display after having seen the size of the shipment. In this situation, the expected revenues in t are given by the sum of the revenues from the current customer (stage revenues) and the expected revenues from t + 1 on (revenues to go). In presence of a customer and being displayed a fare f j , two situations may occur:

  • with probability p kj the current customer accepts f j , then the stage revenues are equal to f j ω and the next customer finds (w − ω) and (v − υ) as available capacities;

  • with probability (1 − p kj ) the current customer refuses f j , then stage revenues are 0 and the next customer finds w and v as available capacities.

We conclude this section observing that the difference J m (t, w, v)–J m (t, w − ω, v − υ) represents the opportunity cost at fare f m of a shipment of size (ω, υ) making a request at time t when capacities w in weight and v in volume are still available, i.e., it is the expected loss in future revenue from using the capacity now rather than reserving it for future use [25]. Accordingly, if J m (t, w, v) is differentiable then ∂J m (t, w, v)/∂w and ∂J m (t, w, v)/∂v are the weight marginal opportunity cost and volume marginal opportunity cost, respectively.

3 Bid-Price Heuristics

Solving problem (1) is, in general, impractical from a computational point of view. For this reason, in this section, we present two heuristics based on threshold values called bid-prices. The rationale behind these heuristics is the following. An optimal policy, solution of (1), accepts a shipment if and only if the revenue it generates is larger or equal to its opportunity cost and bid-prices can be fixed as approximate estimations of the marginal opportunity costs. On the base of this property, bid-price heuristic policies accept a shipment if its revenue is greater or equal to the estimation of its opportunity cost that can be derived from the bid-prices [25]. More formally, we denote by πw(w, t) and πv(v, t) the bid-prices for weight and volume, respectively, when capacities w in weight and v in volume are still available at time t. Then, the opportunity costs of such a request are approximated by πw(w, t)ω + πv(v, t)υ. Hence a booking request generating revenues r is accepted if and only if [18]:

$$ r = f\upomega \ge \pi_{w} (w,t)\upomega + \pi_{v} (v,t)\upupsilon , $$
(2)

where f is the fare applied.

3.1 Static BP Heuristic (SBP)

We define bid-prices as static if they are fixed at the beginning of the booking period, i.e., they do not change over time and do not depend on the remaining capacity: π w (w, t) = π w and π v (v, t) = π v .

Once the bid-prices are chosen, our heuristic fixes a same fare f for all customers. Specifically, f is set equal to the first accepted shipment’s minimum available fare such that the acceptance rule (2) is almost surely respected; that is

$$ f = \hbox{min} \{ f_{j} :f_{j} \upomega_{h} \ge \uppi_{w} \upomega_{h} + \uppi_{v} \upupsilon_{h} \,{\text{and}}\,p_{hj} = 1\} $$

where, h denotes the first customer for which a fare f j  ∈ F satisfying the above condition exists. The uniqueness of f trivially guarantees that the displayed fares do not decrease over time. However, an evident drawback of this choice is that actual generated revenues depend on the willingness to pay of the first accepted customer k. Heuristic SBP may perform poorly when demand is inverse, especially if bid-price values are low. This performance problem holds true for static bid-price approaches in general since they accept a request as long as its revenues are higher than the computed threshold, without taking into account that the marginal value of the remaining capacity increases over time. A common solution to this is to recalculate bid-prices at pre-defined time intervals (which become smaller as flight booking closure grows closer) in order to take into account the increased marginal value of remaining capacity.

To fix the values of the static bid-prices our heuristic averages the optimal static bid-prices of a set of training instances (possibly based on historical data). Specifically, paralleling the work in Pak and Dekker [18], we combine the findings in Lenstra et al. [15] and in Rinnooy Kan et al. [20], and we observe that, if the demand is known in advance, the choice of accepting shipments of size (ω k , υ k ) generating (potential) revenue r k  = f *ω k , where f * is the maximum fare that customer k is willing to pay, can be made by solving a multi-dimensional knapsack problem. Then, we compute the bid-prices for each training instance by solving the associated knapsack problem through the following greedy algorithm.

Greedy algorithm. For each customer k we define the ratio

$$ \updelta_{k} = r_{k} /(\uplambda \upomega_{k} + \, \upmu \upupsilon_{k} ) $$

where λ and μ are appropriate positive multipliers. The ratio δ k is a measure of the revenue for unit of the overall resources used by shipment k. The multipliers λ and μ are necessary to express volume and weight capacity requirements as single resource consumption. Items are then ordered by decreasing values of δ k and accordingly inserted into the knapsack as long as there is available capacity. Clearly, the choice of the multipliers may affect the sequence of shipments entering the knapsack and thus the associated final revenues. However, Rinnooy Kan et al. [20] prove that there exists a pair of multipliers λ*and μ* maximising the revenues that can be computed in O(n 3logn), where n is the number of shipments.

Let δ* be the ratio value associated to the last shipment inserted in the knapsack when the multipliers are λ* and μ*. We define the instance optimal static bid-prices as:

$$ \uppi_{w} = \updelta^{*} \uplambda^{*} \quad \uppi_{v} = \updelta^{*} \upmu^{*} . $$

Indeed, is trivial to observe that, in the above procedure, the shipment of a customer k is inserted into the knapsack if and only if δ k  ≥ δ* and there is enough capacity. Under these circumstances, condition (2) is met, as r k  ≥ δ* (λ*ω k  + μ*υ k ) = π w ω k  + π v υ k . □

3.2 Dynamic BP Heuristic (DBP)

In our dynamic bid-price heuristic bid-prices are updated as the requests arrive, in order to capture and exploit the increasing willingness to pay of the demand. Let L k and M k be the weight and volume (dynamic) bid-price values, respectively. Hence the acceptance rule at time t k is r k  ≥ L k ω k  + M k υ k .

After each accepted request, static bid-prices are calculated by running SBP on the remaining capacity and demand. Let π w (w, t) and π v (v, t) be the weight and volume bid-prices respectively, when SBP is run on N − k + 1 customers with remaining capacities w and v.

Initially, we set: L 1 = π w (C w , t 1), M 1 = π v (C v , t 1). Then we update the dynamic bid-prices according to the following policy:

  • L k+1 = L k , M k+1 = M k : if request k is rejected or if one or both static bid-prices turn out to be lower than or equal to current values of L k or M k , that is, either π w (w, t k+1) ≤ L k or π v (v, t k+1) ≤ M k .

  • L k+1 = π w (w, t k+1), M k+1 = π v (v, t k+1) if request k is accepted and static bid-prices turn out to be greater than or equal to current values of L k or M k , that is π w (w, t k+1) > L k and π v (v, t k+1) > M k .

Finally, we choose the fare to display to customer k as f = min{f j : f j ω k  ≥ L k ω k  + M k υ k and p kj  = 1}. If no fare satisfies this last condition, customer k is rejected.

The rationale behind the choice of updating dynamic bid-prices only when both SBP bid-prices simultaneously increase is three-fold. First, in this way, at each update, the threshold given by the pair (L k+1, M k+1) is the optimal one for the remaining capacity and demand, according to the SBP algorithm. Second, we cannot update both the bid-prices to lower SBP bid-prices values as otherwise we could not guarantee that the displayed fare does not decrease over time. Third, we cannot update a single bid-price to a higher value when only one SBP bid-price is greater than the current dynamic bid-prices as otherwise we obtain a too selective policy. Indeed, the acceptance threshold increases very rapidly over time since it is updated whenever at least one bid-price augments.

We finally point out that the choice to consider updating dynamic bid-prices only after a request is accepted, and not after any request, is due to reducing computational time.

4 Experimental Results

In this section, we assess the quality of the heuristics introduced in the previous section. The revenues obtained with the two heuristics are then compared also with the ones obtained solving problem (1) under the assumption that the number of customers and their characteristics, in terms of both arrival times and the shipment sizes, are known in advance. In fact, under this (relaxed although unrealistic) assumption, problem (1) becomes computational tractable and provides an upper bound for the optimal expected revenues J 1 (0, C w , C v ). Hereafter, we indicate this last kind of revenues as obtained through dynamic programming (DYM).

4.1 Experiment Design

Each shipment is characterised by three attributes: weight, volume and willingness to pay of its owner; they are expressed in kilos (Kg), cubic meters (m3) and US dollars ($), respectively. As it is common practice within the air cargo industry, we distinguish between small and large shipments: small when its weight is between 2 and 45 kg and large when it is between 46 and 500 kg. This distinction is generally applied because of the different weight and volume capacities reserved on the aircraft and the dissimilar fares applied by the carriers. In principle, fares per unit of weight decrease as the weight increases and roughly depend on the distance to be flown. Since in this work all the customers book for the same single-leg flight, we can neglect the dependence on the distance.

Hence, fares are only related to the shipment weight category and to the time of the booking request. We considered four different fares (f 1 < f 2 < f 3 < f 4) for both small and large shipments. As anticipated, fares are non-decreasing over time and only one fare is available at each time instant.

In order to deal with uncertainty regarding shipment volume [2, 22], it is usual practice within airlines to associate an average volume for a given weight, i.e., a shipment k of weight ω k has an average volume γω k where γ is a constant. We set γ = 0.00581 as in Pak and Dekker [18]. To add variability to the volume, its value υ k is randomly chosen in an interval centred in γω k whose length becomes larger as the weight of the shipment increases.

Tests are run with willingness to pay of the demand either random or inverse. In the former case, the willingness to pay is stationary over the time. Indeed the willingness to pay of customer k is chosen randomly in the interval [f 1ω k  − l m , f 4ω k  + l M ] with l m  = 0.92 and l M  = 2.26 for small shipments and l m  = 16.56 and l M  = 21.26 for large shipments. In the latter case (i.e., inverse demand), we introduce a dummy fare f 0 < f 1 and we divide the N potential customers in four intervals of approximately equal length. Each customer in interval i, (i = 1, 2, 3, 4) randomly chooses between fare f i−1 and fare f i with equal probability p = 0.5.

By averaging the values presented by airlines on their websites, we fixed the relevant data as reported in Table 1.

Table 1 Experiment parameters
Full size table

4.2 Computational Results

We distinguish four different scenarios in accordance with the four different sets of instances used as input demand. Tables 2 and 3 present the average values obtained over the same set of \( \varLambda \) instances by the different heuristics for each scenario.

Table 2 Results for random demand (average values)
Full size table
Table 3 Results for inverse demand (average values)
Full size table

Average execution time refers to the training instances for SBP and DBP. The testing instances simply need to check at each booking request whether the threshold is respected or not, which is a very quick operation.

On the other hand, the DYM algorithm does not require a training phase, so the testing instances are optimally solved through dynamic programming and average execution time refers to these latter.

The results provided shows that, at least for the instances considered, both the heuristics are reasonable. Here, we recall that the DYM results are upper bounds on the optimal ones that a revenue manager could obtain solving (1) without a priori deterministically knowing the demand. Static bid-price heuristic DBP, as expected performs better than SBP with inverse demand. Differently, SBP outperforms DBP when the demand is random. This latter observation is not surprising as, given the non-decreasing assumption, the DBP tries to increase the revenues becoming more and more selective. However, in the case of random demand, the willingness to pay of the customers does not increase over time and then the DBP may reject too many customers. Indeed, in presence of a stationary demand, it may be reasonable to become less selective when we approach the flight closing time. Unfortunately, the implementation of a similar policy could induce an opportunistic behaviour in the demand and modify its statistics.

5 Conclusions

In the present work we introduced the problems that can arise in RM from an imprecise forecast of customer demand. In this context, we focused on customer’s willingness to pay as a proven robust measure on which to build capacity management algorithms. Referring to a bi-dimensional capacity scenario (i.e., weight and volume, which is the case of air cargo) and considering demand as deterministic at the time of booking, we first introduced an optimal Dynamic Programming model. Then we proposed two bid-prices based algorithms, one, static and one dynamic, and showed through computational tests their performances in terms of average revenues and computational times.

Future development of this work may address further improvements to the BP policies and comparison to DP based heuristics, another solving approach that has drawn a wide interest in literature.