5 A Crew Allocation Problem

Problem Specification

A small air-line has to assign their 20 flight attendants to 10 flights. Each flight has to be accompanied by a certain number of cabin crew (see Table 5.1) that has to meet a couple of constraints. First, to serve the needs of international clients the cabin crew has to be able to speak German, Spanish, and French (see Table 5.2). Further, a minimal number of stewardesses resp. stewards have to attend a flight (see Table 5.3). Finally, every cabin crew member has two flights off after an attended flight.


flight #

# of cabin staff

1

4

2

4

3

5

4

5

5

6

flight #

# of cabin staff

6

4

7

4

8

5

9

5

10

6

Table 5.1: Cabin crew per flight.



flight #

French

Spanish

German

1

1

1

1

2

1

1

1

3

1

1

1

4

2

2

1

5

2

2

1

6

1

1

1

7

1

1

1

8

1

1

1

9

1

1

1

10

1

1

1

Table 5.2: Cabin crew speaking foreign language per flight.



flight #

male

female

1

1

1

2

1

1

3

1

1

4

2

2

5

3

2

flight #

male

female

6

1

1

7

1

1

8

1

1

9

1

1

10

1

1

Table 5.3: Male resp. female cabin crew per flight.


Model

The cabin crew for every flight is represented as a set. The constraints on cabin crews of individual flights are modeled in terms of constraints on the cardinality of the intersection of the cabin crew set of that flight with the sets associated with particular restrictions. Therefore the following subsets of the cabin crew are introduced: male, female, Spanish-speaking, French-speaking, and German-speaking cabin crew. The constraint that a crew member has two flights off after an attended flight is expressed by the disjointness of the appropriate sets representing a crew per flight.

Solver

The function AssignCrew returns a solver configured according to its arguments FlightData and Crew. As previously mentioned, the constraints on the cabin crew of a flight are expressed in terms of sets of crew members meeting these constraints. For that reason the following variables are defined:

Procedure TeamConstraint imposes the abovementioned constraints on the individual flight cabin crew sets intersecting them with appropriate sets (FS.intersection), and constrains the intersection's cardinality according to Table 5.1, Table 5.2, and Table 5.3 (using FS.card and >=:).

The procedure SequenceDisjoint is responsible to ensure that every crew member may enjoy a two-flight break between two flights. It is a recursive procedure imposing FS.disjoint upon every 3 subsequent sets.

The actual solver declares the local variable Flights that contains the list of sets representing the individual crew assignments. Then, the constraints of the procedure TeamConstraint are imposed on Flights by the Map loop, by mapping the data provided by FlightData to Flights. The distribution is straightforward and has no particularities.

Dealing with sets of literals

Often real-life applications deal with sets of names, descriptions and the like rather than integers, which can be represented by Oz literals. The functions SetOfLiterals, Lits2Ints, and Ints2Lits allow to model sets of literals. The function SetOfLiterals returns an abstract data structure that enables Lits2Ints and Ints2Lits to map literals to integers and vice versa. The last line of the solver procedure converts the internal solution to a representation corresponding to the format of AssignCrew's argument Crew (see below).

declare 
 
local 
   Lit2Int = {NewName}
   Int2Lit = {NewName}
in 
   fun {SetOfLiterals Lits}
      sol(Lit2Int:
             {NewChunk
              {List.toRecord l2i
               {List.mapInd Lits fun {$ I L}
                                    L#I
                                 end}}}
          Int2Lit:
             {NewChunk
              {List.toRecord i2l
               {List.mapInd Lits fun {$ I L}
                                    I#L
                                 end}}})
   end 
    
   fun {Lits2Ints SetOfLiterals Literals}
      {Map Literals fun {$ Lit}
                       SetOfLiterals.Lit2Int.Lit
                    end}
   end 
    
   fun {Ints2Lits SetOfLiterals Ints}
      {Map Ints fun {$ Int}
                   SetOfLiterals.Int2Lit.Int
                end}
   end 
end 
 
fun {CrewProb FlightData Crew}
   CabinStaff      = {Append Crew.stewards Crew.stewardesses}
   CrewSet         = {SetOfLiterals CabinStaff}
   Stewards        = {FS.value.make
                      {Lits2Ints CrewSet Crew.stewards}}
   Stewardesses    = {FS.value.make
                      {Lits2Ints CrewSet Crew.stewardesses}}
   FrenchSpeaking  = {FS.value.make
                      {Lits2Ints CrewSet Crew.frenchspeaking}}
   GermanSpeaking  = {FS.value.make
                      {Lits2Ints CrewSet Crew.germanspeaking}}
   SpanishSpeaking = {FS.value.make
                      {Lits2Ints CrewSet Crew.spanishspeaking}}
 
   proc {TeamConstraint Team Flight}
      flight(no:_ crew:N stewards:NStew stewardesses:NHost
             frenchspeaking:NFrench germanspeaking:NGerman
             spanishspeaking:NSpanish) = Flight
   in 
      {FS.card Team  N}
      {FS.card
       {FS.intersect Team Stewards}}        >=: NStew
      {FS.card
       {FS.intersect Team Stewardesses}}    >=: NHost
      {FS.card
       {FS.intersect Team FrenchSpeaking}}  >=: NFrench
      {FS.card
       {FS.intersect Team GermanSpeaking}}  >=: NGerman
      {FS.card
       {FS.intersect Team SpanishSpeaking}} >=: NSpanish
   end 
               
   proc {SequencedDisjoint L}
      case L of A|B|C|then 
         {FS.disjoint A B}
         {FS.disjoint A C}
         {SequencedDisjoint B|C|T}
      elseof A|B|nil then 
         {FS.disjoint A B}
      end 
   end 
in 
   proc {$ Sol}
      Flights = {FS.var.list.upperBound
                 {Length FlightData}
                 {Lits2Ints CrewSet CabinStaff}}
   in       
      {Map FlightData proc {$ D F}
                         {TeamConstraint F D}
                      end Flights}
                  
      {SequencedDisjoint Flights}
 
      {FS.distribute naive Flights}
 
      Sol = {Map Flights
             fun {$ F}
                {Ints2Lits CrewSet {FS.monitorIn F}}
             end}
   end 
end 

The following sample data can be used to test the solver:

declare 
Flights =
[flight(no: 1 crew:4 stewards:1 stewardesses:1
        frenchspeaking:1 spanishspeaking:1
        germanspeaking:1)
 flight(no: 2 crew:5 stewards:1 stewardesses:1
        frenchspeaking:1 spanishspeaking:1
        germanspeaking:1)
 flight(no: 3 crew:5 stewards:1 stewardesses:1
        frenchspeaking:1 spanishspeaking:1
        germanspeaking:1)
 flight(no: 4 crew:6 stewards:2 stewardesses:2
        frenchspeaking:1 spanishspeaking:1
        germanspeaking:1)
 flight(no: 5 crew:7 stewards:3 stewardesses:3
        frenchspeaking:1 spanishspeaking:1
        germanspeaking:1)
 flight(no: 6 crew:4 stewards:1 stewardesses:1
        frenchspeaking:1 spanishspeaking:1
        germanspeaking:1)
 flight(no: 7 crew:5 stewards:1 stewardesses:1
        frenchspeaking:1 spanishspeaking:1
        germanspeaking:1)
 flight(no: 8 crew:6 stewards:1 stewardesses:1
        frenchspeaking:1 spanishspeaking:1
        germanspeaking:1)
 flight(no: 9 crew:6 stewards:2 stewardesses:2
        frenchspeaking:1 spanishspeaking:1
        germanspeaking:1)
 flight(no:10 crew:7 stewards:3 stewardesses:3
        frenchspeaking:1 spanishspeaking:1
        germanspeaking:1)]
 
Crew =
crew(stewards:
        [tom david jeremy ron joe bill fred bob mario ed]
     stewardesses:
        [carol janet tracy marilyn carolyn cathy inez
         jean heather juliet]
     frenchspeaking:
        [inez bill jean juliet]
     germanspeaking:
        [tom jeremy mario cathy juliet]
     spanishspeaking:
        [bill fred joe mario marilyn inez heather])

Running the solver by {ExploreOne {AssignCrew Flights Crew}}. and invoking the Oz Browser on the solution node results in:

The flights are to be attended in the order they appear in the solution list. Each sublist denotes the assignment for an individual flight.


Tobias Müller
Version 1.4.0 (20080702)