Download
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.
%
%
% From
% """
% 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"];