% % Bus driver scheduling problem (prob022 in CSPLib) in MiniZinc. % % http://www.csplib.org/Problems/prob022 % % From % http://www.csplib.org/Problems/prob022 % """ % 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 % (http://www.hakank.org/minizinc/bus_scheduling_csplib_t1.dzn) % 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: % http://www.hakank.org/minizinc/bus_scheduling_csplib_c1.dzn % http://www.hakank.org/minizinc/bus_scheduling_csplib_c1a.dzn % http://www.hakank.org/minizinc/bus_scheduling_csplib_c2.dzn % http://www.hakank.org/minizinc/bus_scheduling_csplib_r1.dzn % http://www.hakank.org/minizinc/bus_scheduling_csplib_r1a.dzn % http://www.hakank.org/minizinc/bus_scheduling_csplib_r2.dzn % http://www.hakank.org/minizinc/bus_scheduling_csplib_r3.dzn % http://www.hakank.org/minizinc/bus_scheduling_csplib_r4.dzn % http://www.hakank.org/minizinc/bus_scheduling_csplib_r5.dzn % http://www.hakank.org/minizinc/bus_scheduling_csplib_r5a.dzn % http://www.hakank.org/minizinc/bus_scheduling_csplib_t1.dzn % http://www.hakank.org/minizinc/bus_scheduling_csplib_t2.dzn % % 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"];