1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 | % % Bus driver scheduling problem (prob022 in CSPLib) in MiniZinc. % % http://www.cs.st-andrews.ac.uk/~ianm/CSPLib/prob/prob022/index.html % % From % http://www.cs.st-andrews.ac.uk/~ianm/CSPLib/prob/prob022/spec.html % """ % Specification % Bus driver scheduling can be formulated as a set paritioning problem. % We propose 12 set partitioning problems derived from small bus driver % scheduling problems. These consist of a given set of tasks (pieces of % work) to cover and a large set of possible shifts, where each shift % covers a subset of the tasks and has an associated cost. We must select % a subset of possible shifts that covers each piece of work once and % only once: this is called a partition. Further, % % In the driver scheduling (unlike air crew scheduling) the main aim is % to reduce the number of shifts used in the solution partition and the % total cost of the partition is secondary. To simplify the problem we have % made the cost of each shift the same. This means that the goal is to % minimise the number of shifts. % % The problems come from four different bus companies: % Reading (r1 to r5a), % CentreWest Ealing area (c1, c1a, c2), % the former London Transport (t1 and t2). % % The problems have differing regulations and features (e.g. urban and % short distance rural bus schedules can have very different features). Note % that r1 and r1a are the same problem, but have different numbers of % generated shifts. Similarly with the problems: c1, c1a and r5, r5a. % % Problems are presented in the same format as the set partitioning % examples in ORLIB. The first line gives the number of rows (pieces of work), % columns (shifts) and the minimum number of columns need for a partition. % Then each line after that corresponds to one column. It starts with % the cost (which is always 1 in our case) then the number of rows it % covers, followed by the rows it covers. % """ % % Note: This model skips the cost parameter. % % This is a MIP mode so the MIP solvers may also be used, e.g. % - MiniZinc's MIP solver % - ECLiPSe's eplex % % % Example, for the problem t1 % minizinc solver gives this solution: % % x: [0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1] % % {11, 18, 19, 20}{1, 2, 14, 15}{3, 4, 7}{5, 6, 12, 13}{8, 9, 16, 17}{10, 22, 23}{0, 21} % % Here are all data files: % % Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/ % % This MiniZinc model was created by Hakan Kjellerstrand, hakank@bonetmail.com % See also my MiniZinc page: http://www.hakank.org/minizinc % include "globals.mzn" ; int : num_work; int : num_shifts; int : min_num_shifts; array [1 .. num_shifts] of set of int : shifts; array [1 .. num_shifts] of var 0 .. 1: x; var 0 .. num_shifts: tot_shifts; % solve minimize tot_shifts; solve :: int_search( x ++ [tot_shifts], first_fail, indomain_min, complete) minimize tot_shifts; % satisfy; constraint tot_shifts = sum (x) /\ forall(j in 0 .. num_work - 1) ( sum (i in 1 .. num_shifts) (x[i]* bool2int (j in shifts[i])) = 1 ) /\ tot_shifts >= min_num_shifts % /\ % for solve satisfy (t1) % tot_shifts = 7 ; output [ "tot_shifts: " ++ show (tot_shifts) ++ "\n" ++ "x: " ++ show (x) ++ "\n" ] ++ [ if fix (x[i]) = 1 then show (shifts[i]) else "" endif | i in 1 .. num_shifts ] ++ [ "\n" ] ++ [ if fix (x[i]) = 1 then show (i) ++ " " else "" endif | i in 1 .. num_shifts ] ++ [ "\n" ]; |