1 // 2 // Copyright 2012 Hakan Kjellerstrand 3 // 4 // Licensed under the Apache License, Version 2.0 (the "License"); 5 // you may not use this file except in compliance with the License. 6 // You may obtain a copy of the License at 7 // 8 // http://www.apache.org/licenses/LICENSE-2.0 9 // 10 // Unless required by applicable law or agreed to in writing, software 11 // distributed under the License is distributed on an "AS IS" BASIS, 12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 // See the License for the specific language governing permissions and 14 // limitations under the License. 15 16 using System; 17 using System.Collections; 18 using System.IO; 19 using System.Linq; 20 using System.Text.RegularExpressions; 21 using Google.OrTools.ConstraintSolver; 22 23 public class Crew 24 { 25 /** 26 * 27 * Crew allocation problem in Google CP Solver. 28 * 29 * From Gecode example crew 30 * examples/crew.cc 31 * """ 32 * Example: Airline crew allocation 33 * 34 * Assign 20 flight attendants to 10 flights. Each flight needs a certain 35 * number of cabin crew, and they have to speak certain languages. 36 * Every cabin crew member has two flights off after an attended flight. 37 * """ 38 * 39 * Also see http://www.hakank.org/or-tools/crew.pl 40 * 41 */ Solve(int sols = 1, int minimize = 0)42 private static void Solve(int sols = 1, int minimize = 0) 43 { 44 Solver solver = new Solver("Crew"); 45 46 // 47 // Data 48 // 49 string[] names = { "Tom", "David", "Jeremy", "Ron", "Joe", "Bill", "Fred", 50 "Bob", "Mario", "Ed", "Carol", "Janet", "Tracy", "Marilyn", 51 "Carolyn", "Cathy", "Inez", "Jean", "Heather", "Juliet" }; 52 53 int num_persons = names.Length; 54 55 // 56 // Attributes of the crew 57 // 58 int[,] attributes = { 59 // steward, hostess, french, spanish, german 60 { 1, 0, 0, 0, 1 }, // Tom = 0 61 { 1, 0, 0, 0, 0 }, // David = 1 62 { 1, 0, 0, 0, 1 }, // Jeremy = 2 63 { 1, 0, 0, 0, 0 }, // Ron = 3 64 { 1, 0, 0, 1, 0 }, // Joe = 4 65 { 1, 0, 1, 1, 0 }, // Bill = 5 66 { 1, 0, 0, 1, 0 }, // Fred = 6 67 { 1, 0, 0, 0, 0 }, // Bob = 7 68 { 1, 0, 0, 1, 1 }, // Mario = 8 69 { 1, 0, 0, 0, 0 }, // Ed = 9 70 { 0, 1, 0, 0, 0 }, // Carol = 10 71 { 0, 1, 0, 0, 0 }, // Janet = 11 72 { 0, 1, 0, 0, 0 }, // Tracy = 12 73 { 0, 1, 0, 1, 1 }, // Marilyn = 13 74 { 0, 1, 0, 0, 0 }, // Carolyn = 14 75 { 0, 1, 0, 0, 0 }, // Cathy = 15 76 { 0, 1, 1, 1, 1 }, // Inez = 16 77 { 0, 1, 1, 0, 0 }, // Jean = 17 78 { 0, 1, 0, 1, 1 }, // Heather = 18 79 { 0, 1, 1, 0, 0 } // Juliet = 19 80 }; 81 82 // 83 // Required number of crew members. 84 // 85 // The columns are in the following order: 86 // staff : Overall number of cabin crew needed 87 // stewards : How many stewards are required 88 // hostesses : How many hostesses are required 89 // french : How many French speaking employees are required 90 // spanish : How many Spanish speaking employees are required 91 // german : How many German speaking employees are required 92 // 93 int[,] required_crew = { 94 { 4, 1, 1, 1, 1, 1 }, // Flight 1 95 { 5, 1, 1, 1, 1, 1 }, // Flight 2 96 { 5, 1, 1, 1, 1, 1 }, // .. 97 { 6, 2, 2, 1, 1, 1 }, { 7, 3, 3, 1, 1, 1 }, { 4, 1, 1, 1, 1, 1 }, 98 { 5, 1, 1, 1, 1, 1 }, { 6, 1, 1, 1, 1, 1 }, { 6, 2, 2, 1, 1, 1 }, // ... 99 { 7, 3, 3, 1, 1, 1 } // Flight 10 100 }; 101 102 int num_flights = required_crew.GetLength(0); 103 104 // 105 // Decision variables 106 // 107 IntVar[,] crew = solver.MakeIntVarMatrix(num_flights, num_persons, 0, 1, "crew"); 108 IntVar[] crew_flat = crew.Flatten(); 109 110 // number of working persons 111 IntVar num_working = solver.MakeIntVar(1, num_persons, "num_working"); 112 113 // 114 // Constraints 115 // 116 117 // number of working persons 118 IntVar[] nw = new IntVar[num_persons]; 119 for (int p = 0; p < num_persons; p++) 120 { 121 IntVar[] tmp = new IntVar[num_flights]; 122 for (int f = 0; f < num_flights; f++) 123 { 124 tmp[f] = crew[f, p]; 125 } 126 nw[p] = tmp.Sum() > 0; 127 } 128 solver.Add(nw.Sum() == num_working); 129 130 for (int f = 0; f < num_flights; f++) 131 { 132 // size of crew 133 IntVar[] tmp = new IntVar[num_persons]; 134 for (int p = 0; p < num_persons; p++) 135 { 136 tmp[p] = crew[f, p]; 137 } 138 solver.Add(tmp.Sum() == required_crew[f, 0]); 139 140 // attributes and requirements 141 for (int a = 0; a < 5; a++) 142 { 143 IntVar[] tmp2 = new IntVar[num_persons]; 144 for (int p = 0; p < num_persons; p++) 145 { 146 tmp2[p] = (crew[f, p] * attributes[p, a]).Var(); 147 } 148 solver.Add(tmp2.Sum() >= required_crew[f, a + 1]); 149 } 150 } 151 152 // after a flight, break for at least two flights 153 for (int f = 0; f < num_flights - 2; f++) 154 { 155 for (int i = 0; i < num_persons; i++) 156 { 157 solver.Add(crew[f, i] + crew[f + 1, i] + crew[f + 2, i] <= 1); 158 } 159 } 160 161 // extra contraint: all must work at least two of the flights 162 /* 163 for(int p = 0; p < num_persons; p++) { 164 IntVar[] tmp = new IntVar[num_flights]; 165 for(int f = 0; f < num_flights; f++) { 166 tmp[f] = crew[f,p]; 167 } 168 solver.Add(tmp.Sum() >= 2); 169 } 170 */ 171 172 // 173 // Search 174 // 175 DecisionBuilder db = solver.MakePhase(crew_flat, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE); 176 177 if (minimize > 0) 178 { 179 OptimizeVar obj = num_working.Minimize(1); 180 solver.NewSearch(db, obj); 181 } 182 else 183 { 184 solver.NewSearch(db); 185 } 186 187 int num_solutions = 0; 188 while (solver.NextSolution()) 189 { 190 num_solutions++; 191 Console.WriteLine("Solution #{0}", num_solutions); 192 Console.WriteLine("Number working: {0}", num_working.Value()); 193 194 for (int f = 0; f < num_flights; f++) 195 { 196 for (int p = 0; p < num_persons; p++) 197 { 198 Console.Write(crew[f, p].Value() + " "); 199 } 200 Console.WriteLine(); 201 } 202 Console.WriteLine("\nFlights: "); 203 for (int f = 0; f < num_flights; f++) 204 { 205 Console.Write("Flight #{0}: ", f); 206 for (int p = 0; p < num_persons; p++) 207 { 208 if (crew[f, p].Value() == 1) 209 { 210 Console.Write(names[p] + " "); 211 } 212 } 213 Console.WriteLine(); 214 } 215 216 Console.WriteLine("\nCrew:"); 217 for (int p = 0; p < num_persons; p++) 218 { 219 Console.Write("{0,-10}", names[p]); 220 for (int f = 0; f < num_flights; f++) 221 { 222 if (crew[f, p].Value() == 1) 223 { 224 Console.Write(f + " "); 225 } 226 } 227 Console.WriteLine(); 228 } 229 230 Console.WriteLine(); 231 232 if (num_solutions >= sols) 233 { 234 break; 235 } 236 } 237 238 Console.WriteLine("\nSolutions: {0}", solver.Solutions()); 239 Console.WriteLine("WallTime: {0}ms", solver.WallTime()); 240 Console.WriteLine("Failures: {0}", solver.Failures()); 241 Console.WriteLine("Branches: {0} ", solver.Branches()); 242 243 solver.EndSearch(); 244 } 245 Main(String[] args)246 public static void Main(String[] args) 247 { 248 int n = 1; 249 int min = 0; // > 0 -> minimize num_working 250 if (args.Length > 0) 251 { 252 n = Convert.ToInt32(args[0]); 253 } 254 255 if (args.Length > 1) 256 { 257 min = Convert.ToInt32(args[1]); 258 } 259 260 Solve(n, min); 261 } 262 } 263