Mat540 Southwest Airlines
mmaone
assignmentweek8.docxSTRAYER UNIVERSITY
SUMMER QUARTER 2014
MAT 540
PROBLEM FOR WEEK 8 ASSIGNMENT
SOUTHWEST AIRWAYS needs to assign its crews to cover all its upcoming flights. We will focus on the problem of assigning three crews based in San Francisco to the flights listed in the first column of the following Table. The other 12 columns show the 12 feasible sequences of flights for a crew. (The numbers in each column indicate the order of the flights.) Exactly three of the sequences need to be chosen (one per crew) in such a way that every flight is covered. It is permissible to have than one crew on a flight, where the extra crew would fly as passengers, but union contracts require that the extra crews would still need to be paid for their time as if they were working.) The cost of assigning a crew to a particular sequence of flights is given (in thousands of dollars) in the bottom row of the Table. The objective is to minimize the total cost of the three crew assignments that cover all the flights.
TABLE . Data for Southwest Airways
|
|
Feasible Sequence of Flights |
|||||||||||
|
Flight |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
1. San Francisco to Los Angeles |
1 |
|
|
1 |
|
|
1 |
|
|
1 |
|
|
|
2. San Francisco to Denver |
|
1 |
|
|
1 |
|
|
1 |
|
|
1 |
|
|
3. San Francisco to Seattle |
|
|
1 |
|
|
1 |
|
|
1 |
|
|
1 |
|
4. Los Angeles to Chicago |
|
|
|
2 |
|
|
2 |
|
3 |
2 |
|
3 |
|
5. Los Angeles to San Francisco |
2 |
|
|
|
|
3 |
|
|
|
5 |
5 |
|
|
6. Chicago to Denver |
|
|
|
3 |
3 |
|
|
|
4 |
|
|
|
|
7. Chicago to Seattle |
|
|
|
|
|
|
3 |
3 |
|
3 |
3 |
4 |
|
8. Denver to San Francisco |
|
2 |
|
4 |
4 |
|
|
|
5 |
|
|
|
|
9. Denver to Chicago |
|
|
|
|
2 |
|
|
2 |
|
|
2 |
|
|
10. Seattle to San Francisco |
|
|
2 |
|
|
|
4 |
4 |
|
|
|
5 |
|
11. Seattle to Los Angeles |
|
|
|
|
|
2 |
|
|
2 |
4 |
4 |
2 |
|
Cost, $1,000’s |
2 |
3 |
4 |
6 |
7 |
5 |
7 |
8 |
9 |
9 |
8 |
9 |
FORMULATION WITH BINARY VARIABLES
With 12 feasible sequences of flights, we have 12 yes-or-no decisions:
Should sequence j be assigned to a crew? (j=1, 2, …, 12)
Therefore, we use 12 binary variables to represent these respective decisions:
Xj = 1 if sequence j is assigned to a crew
Xj = 0 otherwise
The most interesting part of this formulation is the nature of each that ensures that a corresponding flight is covered. For example, consider the last flight in the Table (Seattle to Los Angeles]. Five sequences (namely, sequences 6, 9, 10, 11, and 12) include this flight. Therefore, at least one of these five sequences must be chosen. The resulting constraint is
X6 + X9+ X10 +X11 + X12
Using similar constraints for the other 10 flights, the complete binary integer programming model is
Minimize Z = 2X1 + 3X2 + 4X3 + 6X4 + 7X5 + 5X6 + 7X7 + 8X8 + 9X9 + 9X10 + 8X11 + 9X12
Subject to
|
X1 + X4 + X7+ X10 ≥ 1 |
(San Francisco to Los Angeles) |
|
X2 + X5 + X8+ X11 ≥ 1 |
(San Francisco to Denver) |
|
X3 + X6 + X9+ X12 ≥ 1 |
(San Francisco to Seattle) |
|
X4 + X7 + X9+ X10 + X12 ≥ 1 |
(Los Angeles to Chicago) |
|
X1 + X6 + X10+ X11 ≥ 1 |
(Los Angeles to San Francisco) |
|
X4 + X5 + X9 ≥ 1 |
(Chicago to Denver) |
|
X7 + X8 + X10+ X11 + X12 ≥ 1 |
(Chicago to Seattle) |
|
X2 + X4 + X5+ X9 ≥ 1 |
(Denver to San Francisco) |
|
X5 + X8 + X11 ≥ 1 |
(Denver to Chicago) |
|
X3 + X7 + X8+ X12 ≥ 1 |
(Seattle to San Francisco) |
|
X6 + X9 + X10+ X11 + X12 ≥ 1 |
(Seattle to Los Angeles) |
|
|
(Assign three crews) |
And
Xj is binary , for j = 1, 2, … , 12.
The model is already formulated. You need to use binary integer programming to solve for the minimum cost and present the optimal solution.
There are 8 criteria specified in the course guide that you follow. The level of grade for each criterion is also specified in the course guide. DO YOUR BEST!
