Initial Challenges
Mathematical Formulation where ci(f) are cost coefficients, ri(f) are
requested parameters, xi(f) are actual values, and yi(f) are the changes in values; 1 = track,
2 = level, and 3 = time. For example, r2(f) and x2(f) are the requested flight level and the
actual flight level, respectively, for flight f. y2(f) is the resulting difference between the
two values.
The formulation above is very typical of a linear or integer programming
problem; there is a cost function that must be minimized over a feasible solution space described
by the listed constraints. The first set of constraints are the upper and lower bounds for the
departure level and time. With regard to the departure level, the integers 1 through 4 correspond
with outbound levels (these are the even altitudes described in the "Background and Motivation"
section). Similarly, the integers 5 through 8 correspond with the inbound levels (the aforementioned
odd altitudes). The upper and lower bounds applied as constraints ensure that if a plane requests
an inbound level, for example, it will be assigned an inbound level in the optimal schedule.
The final set of bounds apply to the departure time of every flight. Intuitively, a flight cannot
take off before it has requested to take off, and by convention the scheduling algorithm will not
allow a flight to be delayed by more than twenty minutes.
The second cluster of constraints define the "change" variables of the model.
For example, y1(f) is the difference between flight f's requested track and the track that it was
actually assigned by the algorithm. Because the difference in requests and actuality can be both
positive and negative for track and level, we must employ the concept of absolute value for these
two values (however, because a flight cannot take off before it requests to take off, we do not need
absolute value for the final constraint of this section). HOWEVER, these instances of absolute value
are very problematic, as they keep our model from being a linear model as it is written. My first
task in reformulating this problem was to examine linear alternatives to absolute value for these
definitions and for other instances of absolute value in the formulation above.
The final constraint is the most complex; it is the separation constraint. As
mentioned previously, all flights in the same track must be separated by either a level or twenty
minutes of flight time. The separation constraint enforces the idea of a safe following distance.
As is typical of linear (and more, specifically, integer) programming problems,
the final set of constraints are what are known as "simple constraints." These constraints place
restrictions on the decision variables. In this case, all of the variables are restricted to be
nonnegative integers.
Armed with the above concept of the problem, my next task was to generate code in
XPress to solve it.
Because I was given this problem as a continuation
of work done for a masters thesis, I had a working version of the scheduling algorithm given to
me at the outset. This version including a linear equivalent of absolute value for the difference
in level between two flights (for the purposes of the separation constraint), but not for the
difference in time necessary for the separation constraint. Nor did this original code provide
for track changes as a viable alternative to resolving conflicts. I was challenged to add both
of these concepts, and to try out different approaches to representing absolute value.
The use of absolute value in defining both y1(f) and y2(f) can be replaced
comparatively easily. Because both values are minimized via the objective function, the equation
is equivalent to the system
so that, effectively,
The same is true of the change in level for flight f, y2(f). And, as we mentioned earlier, because the change in departure time is always nonnegative, we don't need to jump through these hoops for the definition of y3(f). Take a look at the separation constraint. It would be useful to compute values
difftrack(f,ff), difflevel(f,ff), and difftime(f,ff) to use in the separation constraint. (Note
that the formulation above only describes difflevel and difftime; the addition of difftrack,
multiplied by the same coefficient as is multiplied by difflevel, is a simple inclusion.) Because
none of these contrived values are minimized by the objective function, the replacement of their
use of absolute value is much more tricky. In the original version of the code that I was given, the
definition
was replaced by the system
where M is a penalty larger than any possible difference in level between two conflicting flights (for our purposes, we have used M = 5), and y(f,ff) is a binary "switch" variable. In a similar fashion, I proposed the following set of inequalities to replace
the nonlinear definition of difflevel:
Here, both lev1(f,ff) and lev2(f,ff) are transitional variables used to capture the (positive) value of difflevel(f,ff). By auditioning different formulations for the absolute value, and for modeling the separation constraint in different ways, I created several different versions of the scheduling algorithm over the course of the summer. Where time permitted, I ran each version several times to get a feel for the processing time necessary. Because it is important to generate an optimal schedule quickly, the processing times for the different versions were used to evaluate and compare them. I summarized my preliminary progress at our first round of presentations. My Powerpoint document outlines the work that I have just explained. The next section outlines and summarizes my conclusions. Next Section: Results and ConclusionsBack to Home |