Flight No. 101 410 220 17 7 Origin Chicago New York New York Miami LA Chicago Miami Chicago LA Miami Destination Time of Day LA afternoon Chicago afternoon Miami night Chicago morning Chicago afternoon New York night New York morning Miami night Miami night LA afternoon 13 11 19 23 3 The Flight Operations Staff would like to set up a low cost crew assignment schedule. The basic problem is to determine the next flight, if any, that a crew operates after it completes one flight. A basic concept needed in understanding this problem is that of a tour. The characteristics of a tour are as follows: - A tour consists of from 1 to 3 connecting flights. - A tour has a cost of $2,000 if it termintates in its city of origin. - A tour which requires "deadheading", i.e., terminates in a city other than the origin city, costs $3,000. In airline parlance, a tour is frequently called a "pairing" or a "rotation". The following are examples of acceptable tours: Tour 17, 101, 23 220, 17, 101 410, 13 Cost $2,000 $3,000 $2,000 The first thing to do for this small problem is to enumerate all feasible tours. We do not consider a collection of flights which involve an intermediate layover a tour. There are 10 one-flight tours, and either 37 or 41 three flight tours depending upon whether on distinguishes the origin city on a nondead-heaing tour. These tours are indicated below: Two-flight tours Cost Three-flight tours Cost 11 One-flight tours (All costs $3,000) 1 101 2 410 3 220 17 12 25 26 27 28 13 14 5 15 29 7 13 6 30 16 17 11 3,000 2,000 3,000 3,000 2,000 3,000 3,000 3,000 3,000 2,000 3,000 3,000 25 101, 23 410, 13 410, 19 220, 17 220, 11 17, 101 7, 13 7,19 11, 410 19, 17 19, 11 23, 17 23, 11 3,23 600 v $ $ $ $ $ $ $ $ $ $ $ $ $ $ 8 19 18 23 9 10 19 20 31 32 33 28 101, 23, 17 $ 2,000 101, 23, 11 $ 3,000 410, 19, 17 $ 3,000 410, 19, 11 $ 2,000 220, 17, 101 $ 3,000 220, 11, 410 $ 3,000 17, 101, 23 $ 2,000 7, 19, 17 $ 3,000 7, 19, 11 $ 3,000 11, 417, 13 $ 3,000 11, 410, 19 $ 2,000 19, 17, 101 $ 3,000 19, 11, 410 $ 2,000 23, 17, 101 $ 2,000 23, 11, 410 $ 3,000 3, 23, 17 $ 3,000 3, 23, 11 $ 3,000 3 21 22 34 3,000 23 24 28 25 2,000 35 36 37 Formulate the problem to find the minimum cost of scheduling the crews to make sure every flight will be able to depart at the time scheduled. Hint: We do not distinguish the city of origin on nondeadheading three flight tours. That's why the tour with flights 101, 23, 17 is the same as 17, 101, 23. Flight No. 101 410 220 17 7 Origin Chicago New York New York Miami LA Chicago Miami Chicago LA Miami Destination Time of Day LA afternoon Chicago afternoon Miami night Chicago morning Chicago afternoon New York night New York morning Miami night Miami night LA afternoon 13 11 19 23 3 The Flight Operations Staff would like to set up a low cost crew assignment schedule. The basic problem is to determine the next flight, if any, that a crew operates after it completes one flight. A basic concept needed in understanding this problem is that of a tour. The characteristics of a tour are as follows: - A tour consists of from 1 to 3 connecting flights. - A tour has a cost of $2,000 if it termintates in its city of origin. - A tour which requires "deadheading", i.e., terminates in a city other than the origin city, costs $3,000. In airline parlance, a tour is frequently called a "pairing" or a "rotation". The following are examples of acceptable tours: Tour 17, 101, 23 220, 17, 101 410, 13 Cost $2,000 $3,000 $2,000 The first thing to do for this small problem is to enumerate all feasible tours. We do not consider a collection of flights which involve an intermediate layover a tour. There are 10 one-flight tours, and either 37 or 41 three flight tours depending upon whether on distinguishes the origin city on a nondead-heaing tour. These tours are indicated below: Two-flight tours Cost Three-flight tours Cost 11 One-flight tours (All costs $3,000) 1 101 2 410 3 220 17 12 25 26 27 28 13 14 5 15 29 7 13 6 30 16 17 11 3,000 2,000 3,000 3,000 2,000 3,000 3,000 3,000 3,000 2,000 3,000 3,000 25 101, 23 410, 13 410, 19 220, 17 220, 11 17, 101 7, 13 7,19 11, 410 19, 17 19, 11 23, 17 23, 11 3,23 600 v $ $ $ $ $ $ $ $ $ $ $ $ $ $ 8 19 18 23 9 10 19 20 31 32 33 28 101, 23, 17 $ 2,000 101, 23, 11 $ 3,000 410, 19, 17 $ 3,000 410, 19, 11 $ 2,000 220, 17, 101 $ 3,000 220, 11, 410 $ 3,000 17, 101, 23 $ 2,000 7, 19, 17 $ 3,000 7, 19, 11 $ 3,000 11, 417, 13 $ 3,000 11, 410, 19 $ 2,000 19, 17, 101 $ 3,000 19, 11, 410 $ 2,000 23, 17, 101 $ 2,000 23, 11, 410 $ 3,000 3, 23, 17 $ 3,000 3, 23, 11 $ 3,000 3 21 22 34 3,000 23 24 28 25 2,000 35 36 37 Formulate the problem to find the minimum cost of scheduling the crews to make sure every flight will be able to depart at the time scheduled. Hint: We do not distinguish the city of origin on nondeadheading three flight tours. That's why the tour with flights 101, 23, 17 is the same as 17, 101, 23