crew.cs

//
// Copyright 2012 Hakan Kjellerstrand
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

using System;
using System.Collections;
using System.IO;
using System.Linq;
using System.Text.RegularExpressions;
using Google.OrTools.ConstraintSolver;

public class Crew
{
    /**
     *
     * Crew allocation problem  in Google CP Solver.
     *
     * From Gecode example crew
     * examples/crew.cc
     * """
     * Example: Airline crew allocation
     *
     * Assign 20 flight attendants to 10 flights. Each flight needs a certain
     * number of cabin crew, and they have to speak certain languages.
     * Every cabin crew member has two flights off after an attended flight.
     * """
     *
     * Also see http://www.hakank.org/or-tools/crew.pl
     *
     */
    private static void Solve(int sols = 1, int minimize = 0)
    {
        Solver solver = new Solver("Crew");

        //
        // Data
        //
        string[] names = { "Tom",     "David", "Jeremy", "Ron",   "Joe",     "Bill",  "Fred",
                           "Bob",     "Mario", "Ed",     "Carol", "Janet",   "Tracy", "Marilyn",
                           "Carolyn", "Cathy", "Inez",   "Jean",  "Heather", "Juliet" };

        int num_persons = names.Length;

        //
        // Attributes of the crew
        //
        int[,] attributes = {
            // steward, hostess, french, spanish, german
            { 1, 0, 0, 0, 1 }, // Tom     = 0
            { 1, 0, 0, 0, 0 }, // David   = 1
            { 1, 0, 0, 0, 1 }, // Jeremy  = 2
            { 1, 0, 0, 0, 0 }, // Ron     = 3
            { 1, 0, 0, 1, 0 }, // Joe     = 4
            { 1, 0, 1, 1, 0 }, // Bill    = 5
            { 1, 0, 0, 1, 0 }, // Fred    = 6
            { 1, 0, 0, 0, 0 }, // Bob     = 7
            { 1, 0, 0, 1, 1 }, // Mario   = 8
            { 1, 0, 0, 0, 0 }, // Ed      = 9
            { 0, 1, 0, 0, 0 }, // Carol   = 10
            { 0, 1, 0, 0, 0 }, // Janet   = 11
            { 0, 1, 0, 0, 0 }, // Tracy   = 12
            { 0, 1, 0, 1, 1 }, // Marilyn = 13
            { 0, 1, 0, 0, 0 }, // Carolyn = 14
            { 0, 1, 0, 0, 0 }, // Cathy   = 15
            { 0, 1, 1, 1, 1 }, // Inez    = 16
            { 0, 1, 1, 0, 0 }, // Jean    = 17
            { 0, 1, 0, 1, 1 }, // Heather = 18
            { 0, 1, 1, 0, 0 }  // Juliet  = 19
        };

        //
        // Required number of crew members.
        //
        // The columns are in the following order:
        // staff     : Overall number of cabin crew needed
        // stewards  : How many stewards are required
        // hostesses : How many hostesses are required
        // french    : How many French speaking employees are required
        // spanish   : How many Spanish speaking employees are required
        // german    : How many German speaking employees are required
        //
        int[,] required_crew = {
            { 4, 1, 1, 1, 1, 1 }, // Flight 1
            { 5, 1, 1, 1, 1, 1 }, // Flight 2
            { 5, 1, 1, 1, 1, 1 }, // ..
            { 6, 2, 2, 1, 1, 1 }, { 7, 3, 3, 1, 1, 1 }, { 4, 1, 1, 1, 1, 1 },
            { 5, 1, 1, 1, 1, 1 }, { 6, 1, 1, 1, 1, 1 }, { 6, 2, 2, 1, 1, 1 }, // ...
            { 7, 3, 3, 1, 1, 1 }                                              // Flight 10
        };

        int num_flights = required_crew.GetLength(0);

        //
        // Decision variables
        //
        IntVar[,] crew = solver.MakeIntVarMatrix(num_flights, num_persons, 0, 1, "crew");
        IntVar[] crew_flat = crew.Flatten();

        // number of working persons
        IntVar num_working = solver.MakeIntVar(1, num_persons, "num_working");

        //
        // Constraints
        //

        // number of working persons
        IntVar[] nw = new IntVar[num_persons];
        for (int p = 0; p < num_persons; p++)
        {
            IntVar[] tmp = new IntVar[num_flights];
            for (int f = 0; f < num_flights; f++)
            {
                tmp[f] = crew[f, p];
            }
            nw[p] = tmp.Sum() > 0;
        }
        solver.Add(nw.Sum() == num_working);

        for (int f = 0; f < num_flights; f++)
        {
            // size of crew
            IntVar[] tmp = new IntVar[num_persons];
            for (int p = 0; p < num_persons; p++)
            {
                tmp[p] = crew[f, p];
            }
            solver.Add(tmp.Sum() == required_crew[f, 0]);

            // attributes and requirements
            for (int a = 0; a < 5; a++)
            {
                IntVar[] tmp2 = new IntVar[num_persons];
                for (int p = 0; p < num_persons; p++)
                {
                    tmp2[p] = (crew[f, p] * attributes[p, a]).Var();
                }
                solver.Add(tmp2.Sum() >= required_crew[f, a + 1]);
            }
        }

        // after a flight, break for at least two flights
        for (int f = 0; f < num_flights - 2; f++)
        {
            for (int i = 0; i < num_persons; i++)
            {
                solver.Add(crew[f, i] + crew[f + 1, i] + crew[f + 2, i] <= 1);
            }
        }

        // extra contraint: all must work at least two of the flights
        /*
        for(int p = 0; p < num_persons; p++) {
          IntVar[] tmp = new IntVar[num_flights];
          for(int f = 0; f < num_flights; f++) {
            tmp[f] = crew[f,p];
          }
          solver.Add(tmp.Sum() >= 2);
        }
        */

        //
        // Search
        //
        DecisionBuilder db = solver.MakePhase(crew_flat, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);

        if (minimize > 0)
        {
            OptimizeVar obj = num_working.Minimize(1);
            solver.NewSearch(db, obj);
        }
        else
        {
            solver.NewSearch(db);
        }

        int num_solutions = 0;
        while (solver.NextSolution())
        {
            num_solutions++;
            Console.WriteLine("Solution #{0}", num_solutions);
            Console.WriteLine("Number working: {0}", num_working.Value());

            for (int f = 0; f < num_flights; f++)
            {
                for (int p = 0; p < num_persons; p++)
                {
                    Console.Write(crew[f, p].Value() + " ");
                }
                Console.WriteLine();
            }
            Console.WriteLine("\nFlights: ");
            for (int f = 0; f < num_flights; f++)
            {
                Console.Write("Flight #{0}: ", f);
                for (int p = 0; p < num_persons; p++)
                {
                    if (crew[f, p].Value() == 1)
                    {
                        Console.Write(names[p] + " ");
                    }
                }
                Console.WriteLine();
            }

            Console.WriteLine("\nCrew:");
            for (int p = 0; p < num_persons; p++)
            {
                Console.Write("{0,-10}", names[p]);
                for (int f = 0; f < num_flights; f++)
                {
                    if (crew[f, p].Value() == 1)
                    {
                        Console.Write(f + " ");
                    }
                }
                Console.WriteLine();
            }

            Console.WriteLine();

            if (num_solutions >= sols)
            {
                break;
            }
        }

        Console.WriteLine("\nSolutions: {0}", solver.Solutions());
        Console.WriteLine("WallTime: {0}ms", solver.WallTime());
        Console.WriteLine("Failures: {0}", solver.Failures());
        Console.WriteLine("Branches: {0} ", solver.Branches());

        solver.EndSearch();
    }

    public static void Main(String[] args)
    {
        int n = 1;
        int min = 0; // > 0 -> minimize num_working
        if (args.Length > 0)
        {
            n = Convert.ToInt32(args[0]);
        }

        if (args.Length > 1)
        {
            min = Convert.ToInt32(args[1]);
        }

        Solve(n, min);
    }
}