# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

**151**> 152 153 154 155 .. 156 >> Next

The crew scheduler can ask the computer to evaluate the set of rotations from a cost (or other performance figures) point of view, as a function of the number of crews employed. He can fix some subset of rotations, and he can ask to evaluate how much this fact penalizes him. He can add some information or constraints which are difficult to code within the program. He can monitor the improvements with time of the performance figure. In other words, his productivity and, as a consequence, the economics of the process can be greatly improved. In particular, he retains control over the algorithm, adapting it to his needs and stopping and directing it according to his experience in the field.

Figure 14.1 shows, in a synthetic way, a possible procedure based on the previous algorithm using it in an interactive mode.

(A) is a direct approach, that is a procedure such that the users intervention is restricted to the introduction of the initial conditions and to the recording of the results.

(B) shows the direction to follow for an interactive approach, and makes use of some aspects of the algorithm shown in the preceding sections and based on the m-TSP.

The method starts with the input of the flights and of the union regulations (see Section 14.1).

The Crew Scheduling Problem: A Travelling Salesman Approach

405

Figure 14.1(a)

406 Franco Giannessi and Bernardo Nicoletti

Figure 14.1(b)

The Crew Scheduling Problem: A Travelling Salesman Approach 407

Figure 14.1(c)

The approach is made more flexible with the introduction of some tests, besides the optimality tests requested by any resolutive approach, which are careful and precise choices the user must operate to make the program more suitable to solve his specific problem.

As a second choice, the user must decide whether or not he wants to obtain a first feasible solution by the rule of the nearest unvisited vertex (utilizing the algorithm of Section 14.7).

If not, he can utilize another technique, but in both cases this step is followed by a check of the union regulations.

An initial lower bound is then computed which is useful for the optimality test (C).

At steps (D) and (H) appears one of the interactive variables of the approach of this paper, that is matrix a (see Section 14.4), where a is the matrix of the paths, that is = 1 means flight j is paired after flight i, while otij = 0 means the opposite. Hence the operator can force a sequence of flights, if he so wishes.

A positive action may be taken by the operator if he thinks that the cuts introduced by some prefixed values of a are better than the corresponding ones of the dual algorithm, or this action can be dictated for example by a specific need of substituting a certain crew. This step is followed by a test of

408

Franco Giannessi and Bernardo Nicoletti

the union regulations (E). If the regulations are satisfied, the procedure stops and gives the best solution found; otherwise a new cut is made if possible, and the process repeated.

The step marked with (F) is just the application of the algorithm of Section 14.3 (the dual method), for discarding solutions not better than the current one.

Every time this technique is utilized, one gets a reduction of the domain inside which one searches for the optimal solution (that is, the discarding of certain nonsuitable rotations), and a consequent updating of the lower bound (G).

In the case where the set of the discarded solutions coincides with the totality of the remaining solutions, the algorithm terminates with the best solution; otherwise a new possibility is offered to the user to force a(H). Then a feasible solution is chosen inside the new restricted domain, (I), and the choice acts in such a way that, if the objective function of the new solution is not better than the best one already found, this new solution is abandoned and control comes back to (F) where other solutions are discarded, till a feasible solution is found.

Next, there is a further check performed by the analysis of the union regulations. If the test is negative, control returns to (F), otherwise there is an updating of the current solution and an optimality check that stops the procedure and the displaying of the solution, in the case where the lower bound coincides with the best value of the solutions met till now.

In the opposite case, the program is interrupted, (L), by a programmed clock of the computer, at intervals fixed in advance or from time to time.

In this way the user can see (M) the degree of optimality already reached. He must also decide whether to give some more CPU time or not.

References

Arabeyre, J. P., J. Feanley, F. C. Steiger, and W. Teather (1969). The Airline Scheduling Problem: A Survey. Trans. Sci., 3, 140-163.

Cavanagh, R. A. (1975). Airline Crew Scheduling. Presented at XII TIMS Inter-

national Meeting, Kyoto, Japan, July, 1975.

Gavish, B. (1976). A Note on The Formulation of the m-salesman Traveling

Salesman Problem. Manag. Science, 22, 704-705.

**151**> 152 153 154 155 .. 156 >> Next