Solving a dial-a-flight problem using composite variables

Abstract

A dial-a-flight problem (DAFP) is described as experienced by a tourist airline operating in Botswana. Typically, a daily schedule is drawn up manually by a team of experienced schedulers a few days before the day in question. In this research, the problem is modeled and optimized using a composite variable formulation of a multi-commodity network flow model. The method takes many of the problem constraints into account at the variable creation stage, reducing the problem size in terms of variables and constraints. As such the method is mostly suitable for highly constrained problems. Six daily lists of booking requests were supplied by the airline, and these were set up and solved. The results are compared with the actual costs incurred by the airline on the day in question. Additional ten lists of booking requests of various sizes were created and solved, and the results compared to results from an integer linear programming (ILP) formulation.

Appendices

Appendix A: Example data, results of our model, and map

See Tables 5, 6, 7, and Fig. 3 in Appendix.

Table 5 Instance I3 (98-size) booking list

Table 6 Actual schedule—instance I3

Table 7 Composite variable schedule—instance I3

Fig. 3

Map of the Okavango Swamps and Eastern Botswana Sefofane marketing brochure (2008), Google earth (2012)

Appendix B: ILP formulation

The objective is to minimize costs:

$$\begin{aligned} \text {minimize} \quad \sum _{x \in X} C_{x} x_{ijf}, \end{aligned}$$

(6)

where $C_{x}$ is the cost associated with the flight variable x, i.e., the cost of executing the flight leg. It is calculated as the aircraft type hourly cost in Rands times the flight distance in kilometers divided by the aircraft-type flight speed in km/h.

Constraints must ensure conservation of fleet flow and passenger group flow at every node. For fleets:

$$\begin{aligned} \left( incoming \; aircraft \right) = \left( outgoing \; aircraft \right) . \end{aligned}$$

Therefore:

$$\begin{aligned} \left( \sum _{i \in N} x_{inf} + s_{(n-1)nf} \right) - \left( \sum _{j \in N} x_{njf} + s_{n(n+1)f} \right) = 0, \quad \forall n\in N,\quad \forall f \in F, \end{aligned}$$

(7)

where nodes n are numbered sequentially at each location. Therefore, $s_{(n-1)nf}$ refers to the ground arc leading from the preceding node $(n-1)$ to the subsequent node n, and, likewise, $s_{n(n+1)f}$ refers to the ground arc leading from the preceding node n to the subsequent node $n+1$.

For passengers:

$$\begin{aligned} \left( \sum _{i \in N} y_{x_{inf} g} + t_{(n-1)ng} \right) - \left( \sum _{j \in N} y_{x_{njf} g} + t_{n(n+1)g} \right) = 0, \quad \forall n\in N, \quad \forall g \in G. \end{aligned}$$

(8)

The passenger networks and the fleet networks are bound by the aircraft capacity constraints as follows:

$$\begin{aligned} \sum _{y \in Y} y_{x g} \quad GrpSize_{g} \le x \; Cap_{x}, \quad \forall x \in X, \end{aligned}$$

(9)

where $GrpSize_{g}$ is the number of people making up group g. $Cap_{x}$ is the passenger capacity of the aircraft type associated with x.

Additional constraints are needed to ensure that the number of aircraft of each fleet type is correct at each location at day start and day end, and that the number available is not exceeded. Therefore, at the starting node for each location u in set of all locations C, the ground arc s for each fleet f must be set equal to the number of aircraft of that fleet type positioned there at day start:

$$\begin{aligned} s_{n_{i} f} = v_{u f}, \quad \forall f \in F, \quad \forall u \in C, \end{aligned}$$

(10)

where $s_{n_{i} f}$ is the ground arc for fleet type f going into the first node (i.e., earliest time) of location u. $v_{u f}$ is the number of aircraft of fleet type f at location u at the start of the day.

Note that this constraint must be used for all locations where there are no aircrafts of some fleet type, in which case $v_{u f}=0$. This is to ensure that the correct number of aircraft is used in the model.

In the case where the aircrafts need to be at certain locations at day end, the ground arc s for each fleet type f leaving the final node at each location u must be set to the required number of aircraft of the appropriate fleet type:

$$\begin{aligned} s_{n_{o} f} = v_{u f}, \quad \forall f \in F, \quad \forall u \in C, \end{aligned}$$

(11)

where $s_{n_{o} f}$ is the ground arc for fleet type f going out of the last node (i.e., latest time) of location u. $v_{u f}$ is the number of aircraft of fleet type f at location u at the end of the day. This constraint could be used only for locations where aircraft are required at the end of the day if necessary and not all locations.

A similar constraint is required to ensure the correct number of each passenger group in the problem. This can be done by setting the passenger ground arc into the earliest node at each location (i.e., at day start) to either one if that location matches the group origin, or zero otherwise. This is achieved as follows:

$$\begin{aligned} t_{n_{i} g} = b_{ug}, \quad \forall g \in G, \quad \forall u \in C, \end{aligned}$$

(12)

where $t_{n_{i} g}$ is the passenger group ground arc with end node corresponding to the first node at location u and $b_{ug}$ is either one or zero, depending on whether u is the origin for g.

Constraints must be included to ensure that passenger groups are at the correct locations at the group EDT and LAT of each day to ensure that demand is met and time windows enforced. For the EDT, the passenger ground arcs t for every passenger group g into the correct node of each location u must be set to a value of 1:

$$\begin{aligned} t_{n_{e} g} = 1, \quad \forall g \in G, \end{aligned}$$

(13)

where $t_{n_{e} g}$ is the passenger group ground arc with end node corresponding to EDT and origin location for passenger group g.

Similarly, the passenger ground arcs out of the LAT nodes at each location must be set to 1 for each passenger group:

$$\begin{aligned} t_{n_{l} g} = 1, \quad \forall g \in G, \end{aligned}$$

(14)

where $t_{n_{l} g}$ is the passenger group ground arc with start node corresponding to LAT and destination location for passenger group g.

A constraint was introduced to constrain intra-journey ground waiting time. This constraint was formulated to limit the amount of ground arc time endured when the group was not at either their origin or their destination, as follows:

$$\begin{aligned} \sum _{t \in \{T:g^{c}_{od}\}} t \le 4, \quad \forall g \in G. \end{aligned}$$

(15)

In Eq. (15), set $\{T:g^{c}_{od}\}$ is a subset of passenger ground arcs T which includes only ground arcs which are not situated at either the passenger group g origin or destination. This will cause every group to only need to endure ground waiting times of a maximum of 10 min at each stop, plus $4 \times 10 = 40~\hbox {min}$, i.e., 50 min (10 min being the size of the time discretizations, TDs). Replacing the 4 by a 0 causes the passenger groups to only have ground waiting times of 10 min per stop during a journey.