The Sayre-Priors Airline operates the following set of scheduled flights: Flight No. 101 410 220 17 7 13 11 19 23 3 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 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 alrine parlance, a tour is frequently called a "pairing" or a rotation". The following are examples of acceptable tours: + Tour Cost 17, 101,23 $2,000 220, 17, 101 $3,000 410, 13 $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: One-Hight tours All M 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 One-Right tours (All costs $3,000) 1 101 2 410 3 220 4 17 5 7 6 13 7 11 8 19 9 23 10 3 11 12 13 14 15 16 17 18 19 20 21 22 23 24 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 $ $ $ $ $ $ $ $ $ $ $ $ $ $ 3,000 2,000 3,000 3,000 2,000 3,000 3,000 3,000 3,000 2,000 3,000 3,000 3,000 2,000 25 26 27 28 29 30 25 31 32 33 28 34 28 25 35 36 37 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,2 $ 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 + Formulate the problem to find the minimum cost of scheduling the crews to make sure every flight will be able to departat 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 3 5 6
