Information Technology Reference
In-Depth Information
the objective function is linear. For solving the model standard MIP/IP-solvers
like CPLEX or GUROBI are available. Note that the dimension of the model is
determined by the cardinality of
P
and
I
. With these cardinalities being around
15 and 7, respectively, instances can be solved in milliseconds of CPU-time which
is an essential property if problem instances with a large number of flights have
to be (re-) optimized in a daily run. We will report computational experience in
Section 4.
The models presented so far are designed for optimizing independent flights.
They are not intended for revenue management on connecting flights. German-
wings, for instance, started to offer connecting flight services in 2007. Thus RM
for complex not only point-to-point flight networks becomes necessary. Here our
model offers a straightforward modification.
In a complex flight network we have to distinguish between two concepts:
flights and legs. Here a
leg
is a direct connection between two airports while a
general
flight
may be composed from a sequence of legs.
Now, while the price schema for the connecting flight may be specified inde-
pendently from the schemata of the basic single leg flights, the price offered for
a connecting flight has to be based on the booking situation of the associated
legs. For instance, the relevant fare classes for the (two) single leg flights are
compared and the higher fare class is chosen for the connecting flight. Then the
airline offers the price which is assigned to this fare class in the pricing schema
of the connecting flight. If the price is accepted, i.e., the customer topics the con-
necting flight then in the reservation system both single leg flights are booked.
Figure 3 displays an example for this procedure. Note that with this and any
alternative logic quite undesirable pricing decisions may occur, i.e., the price of
the connecting flight may be higher than the sum of the two single leg prices.
Leg 1
class price state
4
Leg 2
class price state
4
Connecting flight
class
price
→
79.99 open
149.99 open
4
199.99
3
49.99 open
3
99.99 open
3
129.99
2
39.99 open
2
69.99 closed
2
99.99
1
19.99 closed
1
39.99 closed
1
59.99
Fig. 3.
Conversion from connecting flight booking into two direct flight bookings
In the occurrence of connecting flights, different flights compete for leg ca-
pacities and we cannot partition the optimization by flights. Thus, in our model
we have to determine prices and capacities for all flights simultaneously. Note
that based on the structure of the flight network there may be a decomposi-
tion into leg-disjoint subsets possible. For the following we assume that such a
decomposition has already been performed on a higher level.
Model LPCF (linear problem for connecting flights) for (re-)optimizing the
entire network is an immediate extension of our first model. Let
F
be the set of
flights offered and
L
the set of legs which are flown. Again,
P
denotes the set of
