Each of Braneast’s crews lives in either New York or Chicago.
Each day a crew must fly one New York-Chicago flight and one Chicago-New York flight with at least one-hour of downtime between flights.
For example, a Chicago-based crew could fly the 9-13 Chicago-New York flight and return on the 14-16 New York-Chicago flight.
This would incur a downtime of one hour. Braneast wants to schedule crews so as to cover all flight and minimize total downtime.
Solution
The trick is to set this up as an assignment model. Because there are seven flights in each direction, we need seven crews.
Each of the seven crews will be based in either Chicago or New York.
We do not know at this point how many of each there will be, but this information will be an output of the model.
There are two sets of nodes and arcs, one for crews based in Chicago and one for the crews based in New York.
Solution – continued
Each such crew will be assigned two flights, the first stating in Chicago, and the second starting in New York.
Furthermore, such an assignment is possible only if the flight from New York leaves at least one hour after the flight from Chicago arrives in New York.
With this in mind, we can imagine an origin node corresponding to the flight from Chicago, a destination node corresponding to the flight from New York, and an arc between them from origin to destination.
Solution – continued
If the flow on this node is 1, a Chicago-based crew is assigned to this pair of flights.
Of course, similar statements can be made for crews based in New York.
Enter inputs. Enter the given flight information in the ranges B6:C12 and F6:G12. Because we plan to use this information with lookup functions later on, we have named the ranges A6:C12 and E6:G12 as C_Ltable and NY_Ltable. The labels in columns A and E serve only to identify the various flights.
Find feasible assignments. To fill in the Chicago-based crews section, find each early flight leaving from Chicago that can be paired with a later flight leaving from New York such that there is at least one hour of downtime in between. Then enter the flight codes of all such pairs of flights in columns A and B. Then do the same for the pairs that could be handled by New York-based crews. Note that all this information is entered in manually – there are no formulas involved.
Developing the Model – continued
Downtimes for feasible assignments. Calculate the downtime for each feasible pair of flights by using lookup functions to extract the information form the flight schedules. Specifically, enter the formula =VLOOKUP(B17,NY_Ltable,2)-VLOOKUP(A17,C_Ltable,3) in cell C17 and copy it down for other flight pairs starting in Chicago. This simply subtracts the beginning time of the second flight in the pair from the ending time of the first flight in the pair. Similarly, enter the formula =VLOOKUP(B28,C_Ltable,2)-VLOOKUP(A28,NY_Ltable,3) in cell C28 and copy it down for other flight pairs in New York.
Flows. Enter any flows in the Flows1 and Flows2 ranges in column D. Remember that these will eventually be set at 0’s and 1’s, indicating that an assignments is either made or it isn’t.
Developing the Model – continued
Flow balance constraints. There is a node in the network for each flight and a flow balance constraint for each node – hence 14 flow balance constraints. However, things get a bit tricky because each flight could be either the first or second flight in a given flight pair. For example, consider flight 3C. The network representation involving this flight appears here.
Developing the Model – continued
Flight 3C is the later flight for the top two arrows, and it is the earlier flight for the bottom arrow. Now comes the key observation for this particular model. We require that flight 3C be flown exactly once, so exactly one of these arrows must have flow 1 and the others must have flow 0. Therefore, we add this node’s total inflow to its total outflow and constrain this sum to be 1. To implement this in the spreadsheet, enter the formulas =SUMIF(Origins1,F17,Flows1) and =SUMIF(Dests2,F17,Flows2) in cells G17 and H17, and copy them to the range G18:H23 to take care of the flights leaving from Chicago. Then enter the formulas =SUMIF(Origins2,F24,Flows2) and =SUMIF(Dests1,F24,Flows1) in cells G24 and H24, and copy them to the range G25:H30 to take care of the flights leaving form New York.
Developing the Model – continued
Finally, add these inflows and outflows in column I. As the spreadsheet model indicates, we will eventually constrain these sums to be 1.
Total downtime. Calculate the total downtime in the TotDowntime cell with the formula =SUMPRODUCT(Downtimes1,Flows1)+SUMPRODUCT(Downtimes2,Flows2).
Using Solver – The Solver dialog box should appear as shown on the next slide. Note that the only constraints are that the total flow into and out of each node must be 1.
Developing the Model – continued
This, plus the fact that network models with integer inputs automatically have integer solutions, implies that the flows on all arcs will be 0 or 1.
Solution – continued
The optimal solution that was shown indicates that there should be two Chicago-based crews and five New York-based crews.
This is because there are two 1’s in the Flows1 range and five 1’s in the Flows2 range. These 1’s indicate the crew assignments.
For example, one Chicago-based crew flies the 1C and 4NY flights, and other flies the 2C and 7NY flights. The total downtime for all seven crews in 26 hours.
Sensitivity Analysis
The only inputs to Braneast’s model are the flight times, so we consider one possible sensitivity analysis involving these flight times.
Suppose the 1C flight from Chicago is delayed by one or more hours. How will this affect the optimal solution?
The original flight times are entered in cells L6 and M6, a flight delay is entered in cell L9, and formulas are entered in cells B6 and C8.
Sensitivity Analysis – continued
After running SolverTable, allowing the delay to vary from 0 to 3 in increments of 1 and keeping track of the total downtime and the numbers of crews based in each city, we obtain the results in the table below.
Sensitivity Analysis – continued
But there is a subtle problem we forgot to take care of.
The problem is that when we delay flight 1C, one or more flight pairings that had at least one hour of downtime originally might no longer have this minimal required downtime.
In fact, Solver solution when the delay is 3 hours schedules a crew to the pairing 1C-4NY. But this is infeasible – the 1C flight gets into New York at times 13, and the 4NY flight leaves New York at time 12.
Sensitivity Analysis – continued
So the SolverTable solution reported for delays of 3 correspond to infeasible schedules.
Unfortunately there is no easy fix for running this sensitivity analysis. Recall that we manually entered the pairings.
To run this sensitivity analysis with SolverTable correctly, we would need to modify the original model so that Solver gets to choose from all possible pairings, with the constraint that a pairing can be chosen only if its downtime is at least 1.
The model would grow larger and somewhat more complex, but it could be done.
