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 first Table) 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 second Table). Further, a minimal number of stewardesses resp. stewards have to attend a flight (see third Table). Finally, every cabin crew member has two flights off after an attended flight.

flight# #of cabin staff flight# #of cabin staff

1 4 6 4

2 4 7 4

3 5 8 5

4 5 9 5

5 6 10 6

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

flight# male female flight# male female

1 1 1 6 1 1

2 1 1 7 1 1

3 1 1 8 1 1

4 2 2 9 1 1

5 3 2 10 1 1

Viewpoint and Constraints

The cabin crew for every flight is represented as a set with domain 1#20. 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.

Script

The function assignCrew returns a solver configured according to its arguments flights 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:

• stewards (male cabin crew members),
• stewardesses (female cabin crew members),
• french, german, and spanish (French-, German-, resp. Spanish-speaking cabin crew members).

val maxValue = (valOf (Int.maxInt))div 2

type crewrec = {french : int list, german : int list,
                spanish : int list,stewardesses : int list, 
                stewards : int list}
                
type flightrec = {crew : int, french : int, german : int,
                  no : int,spanish : int,stewardesses : int,
                  stewards : int}
                  
val crew = {stewards = [1,2,3,4,5,6,7,8,9,10],
            stewardesses = [11,12,13,14,15,16,17,18,19,20],
            french = [6,17,18,20],
            german = [1,3,9,16,20],
            spanish = [5,6,7,9,14,17,19]}
     
val flights = [{no = 1,crew = 4,stewards = 1,stewardesses = 1,
                french = 1, spanish = 1,german = 1},
               {no = 2,crew = 5,stewards = 1,stewardesses = 1,
               french = 1, spanish = 1,german = 1},
               {no = 3,crew = 5,stewards = 1,stewardesses = 1,
               french = 1, spanish = 1,german = 1},
               {no = 4,crew = 6,stewards = 2,stewardesses = 2,
               french = 1, spanish = 1,german = 1},
               {no = 5,crew = 7,stewards = 3,stewardesses = 3,
               french = 1, spanish = 1,german = 1},
               {no = 6,crew = 4,stewards = 1,stewardesses = 1,
               french = 1, spanish = 1,german = 1},
               {no = 7,crew = 5,stewards = 1,stewardesses = 1,
               french = 1, spanish = 1,german = 1},
               {no = 8,crew = 6,stewards = 1,stewardesses = 1,
               french = 1, spanish = 1,german = 1},
               {no = 9,crew = 6,stewards = 2,stewardesses = 2,
               french = 1, spanish = 1,german = 1},
               {no = 10,crew = 7,stewards = 3,stewardesses = 3,
               french = 1, spanish = 1,german = 1}]

fun assignCrew flights (crew:crewrec) space =
    let
       val stewards = FS.Value.make(space,
                      FD.domainFromList(#stewards(crew)))
       val stewardesses = FS.Value.make(space,
                      FD.domainFromList(#stewardesses(crew)))
       val french = FS.Value.make(space,
                      FD.domainFromList(#french(crew)))
       val german = FS.Value.make(space,
                      FD.domainFromList(#german(crew)))
       val spanish = FS.Value.make(space,
                      FD.domainFromList(#spanish(crew)))
       fun teamConstraint(team,flight:flightrec)=
           let
              val n = #crew(flight)
              val nstew = #stewards(flight)
              val nhost = #stewardesses(flight)
              val ngerm = #german(flight)
              val nspan = #spanish(flight)
              val nfren = #french(flight)
              fun cardOp(nb,setv)= 
                  let
                     val tmp1 = FS.setvar space
                     val tmp2 = FD.range(space,(1,maxValue))
                  in
                     FS.relOp(space,team,FS.INTER,setv,
                              FS.SEQ,tmp1);
                     FS.cardinality(space,tmp1,tmp2);
                     post(space,FD(tmp2) `>= `nb,FD.DOM)
                  end
            in
               FS.cardRange(space,n,n,team);
               Vector.app(fn(x,y)=>cardOp(x,y))
               (#[(nstew,stewards),(nhost,stewardesses),
                  (ngerm,german),(nspan,spanish),(nfren,french)])
            end
       fun sequenceDisjoint(x::y::nil)= FS.rel(space,x,FS.DISJ,y)
         | sequenceDisjoint(x::y::z::xs)= 
                          (FS.rel(space,x,FS.DISJ,y);
                           FS.rel(space,x,FS.DISJ,z);
                           sequenceDisjoint(y::z::xs))         
       val crewlist = List.tabulate(List.length flights,fn x =>
                                    FS.upperBound(space,#[(1,20)]))         
    in
       List.app(fn(x,y)=> teamConstraint(y,x))
               (ListPair.zip(flights,crewlist));
       sequenceDisjoint(crewlist);
       FS.setvarbranch(space,Vector.fromList crewlist,
                       FS.FSB_NONE,FS.FSB_MIN); 
       crewlist
    end

The procedure teamConstraint imposes the abovementioned constraints on the individual flight cabin crew sets intersecting them with appropriate sets by FS.relOp with the set operation FS.INTER, and constrains the intersection's cardinality according to Table 11.5.1(using FS.cardinality and post).

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.rel with the set operation FS.DISJ upon every 3 subsequent sets.

The actual solver declares the local variable crewlist that contains the list of sets representing the individual crew assignments. Then, the constraints of the procedure teamConstraint are imposed on crewlist by the List.app procedure, applying the data provided by flights to crewlist. The branching is straightforward and has no particularities.

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

fun name 1 = "tom"
  | name 2 = "david"
  | name 3 = "jeremy"
  | name 4 = "ron"
  | name 5 = "joe"
  | name 6 = "bill"
  | name 7 = "fred"
  | name 8 = "bob"
  | name 9 = "mario"
  | name 10 = "ed"
  | name 11 = "carol"
  | name 12 = "janet"
  | name 13 = "tracy"
  | name 14 = "marilyn"
  | name 15 = "carolyn"
  | name 16 = "cathy"
  | name 17 = "inez"
  | name 18 = "jean"
  | name 19 = "heather"
  | name 20 = "juliet";

let 
    val (s,r) = valOf(Search.searchOne(assignCrew flights crew))
in  
    List.map(fn x => List.map(fn y => name y)x)
      (List.map(fn y=> domainToList y)(List.map(fn x => 
                            FS.Reflect.upperBound(s,x))(r)))
end