护士调度 CpSolver 卡在某些解决方案中
Nurse scheduling CpSolver stuck in some solutions
我正在实施一个复杂的护士调度问题。
我希望护士连续轮班工作,并匹配每个班次所需的最少护士。
具体来说,问题是我得到了可行但卡住的解决方案,例如:
Solution 0
Day 0
Nurse 0 works from shift 0 to 3
Nurse 1 works from shift 4 to 7
Solution 1
Day 0
Nurse 0 works from shift 0 to 3
Nurse 1 works from shift 4 to 7
cp_model.CpSolver 刚刚给了我 200 次相同的解决方案。
我希望我的解决方案是这样的:
Solution 0
Day 0
Nurse 0 works from shift 0 to 3
Nurse 1 works from shift 4 to 7
Solution 1
Day 0
Nurse 0 works from shift 0 to 2
Nurse 1 works from shift 2 to 7
Solution 2
Day 0
Nurse 0 works from shift 5 to 7
Nurse 1 works from shift 0 to 5
以及更多其他可行的解决方案。
我已经看过关于 cp_model 和 cp_model.CpSolver cp_model.py 的文档
reference.md
但是上面的none提到了使用CpSolver时的一些选择。
我想知道在使用 CpSolver 时是否可以选择一些方法?
或者我错过了什么?
这是我的代码:
from ortools.sat.python import cp_model
num_nurses = 2
num_shifts = 8
num_days = 1
all_nurses = list(range(num_nurses))
all_shifts = list(range(num_shifts))
all_days = list(range(num_days))
start_shift = list(range(num_shifts))
end_shift = list(range(num_shifts))
RESEARCH_model = cp_model.CpModel()
# Creates shift variables.
RESEARCH_shifts = {}
for n in all_nurses:
for d in all_days:
for start in start_shift:
for end in end_shift:
RESEARCH_shifts[(n, d, start, end)] =\
RESEARCH_model.NewBoolVar('shift_n{}d{}start{}end{}'.format(n,
d, start, end))
# constraint with minimum required nurse equal to 1
for d in all_days:
for s in all_shifts:
RESEARCH_model.Add(sum(RESEARCH_shifts[(n, d, start, end)]
for n in all_nurses
for start in start_shift for end in range(start , num_shifts )
if start <= s <= end) == 1)
# constraint with continuous shifts
for d in all_days:
for n in all_nurses:
RESEARCH_model.Add(sum(RESEARCH_shifts[(n, d, start, end)]
for start in start_shift
for end in range(start, num_shifts )
if 0 <= (end - start + 1) <= 8 ) <= 1)
# the callback
class RESEARCH_NursesPartialSolutionPrinter(cp_model.CpSolverSolutionCallback):
"""Print intermediate solutions."""
def __init__(self, shifts, num_nurses, num_days, num_shifts ,start_shift, end_shift, sols):
cp_model.CpSolverSolutionCallback.__init__(self)
self._shifts = shifts
self._num_nurses = num_nurses
self._num_days = num_days
self._num_shifts = num_shifts
self._solutions = set(sols)
self._solution_count = 0
self._start_shift = start_shift
self._end_shift = end_shift
def on_solution_callback(self):
self._solution_count += 1
if self._solution_count in self._solutions:
print('Solution %i' % self._solution_count)
for d in range(self._num_days):
print(' Day {}'.format(d))
for n in range(self._num_nurses):
for start in self._start_shift:
for end in range(start, self._num_shifts):
if self.Value(self._shifts[(n, d, start, end)]) == True:
print(' Nurse {} works from shift {} to {}'.format(n, start, end))
# create solver and solve it.
solver = cp_model.CpSolver()
# Display the first n solutions.
a_few_solutions = range(200)
RESEARCH_solution_printer = RESEARCH_NursesPartialSolutionPrinter(RESEARCH_shifts,
num_nurses,
num_days,
num_shifts,
start_shift,
end_shift,
a_few_solutions)
solver.parameters.max_time_in_seconds = 2.0
solver.SearchForAllSolutions(RESEARCH_model, RESEARCH_solution_printer)
我希望输出如下:
Solution 0
Day 0
Nurse 0 works from shift 0 to 3
Nurse 1 works from shift 4 to 7
Solution 1
Day 0
Nurse 0 works from shift 0 to 2
Nurse 1 works from shift 3 to 7
Solution 2
Day 0
Nurse 0 works from shift 6 to 7
Nurse 1 works from shift 0 to 5
但我得到的输出如下:
Solution 0
Day 0
Nurse 0 works from shift 0 to 3
Nurse 1 works from shift 4 to 7
Solution 1
Day 0
Nurse 0 works from shift 0 to 3
Nurse 1 works from shift 4 to 7
Solution 2
Day 0
Nurse 0 works from shift 0 to 3
Nurse 1 works from shift 4 to 7
这不是我想要的。
解决方案已在 github
上给出
https://github.com/google/or-tools/issues/1300
问题是这段代码创建了很多不受约束的布尔变量。
枚举所有解决方案时,您正在探索这些变量的所有 2^n 组合。
我正在实施一个复杂的护士调度问题。 我希望护士连续轮班工作,并匹配每个班次所需的最少护士。
具体来说,问题是我得到了可行但卡住的解决方案,例如:
Solution 0
Day 0
Nurse 0 works from shift 0 to 3
Nurse 1 works from shift 4 to 7
Solution 1
Day 0
Nurse 0 works from shift 0 to 3
Nurse 1 works from shift 4 to 7
cp_model.CpSolver 刚刚给了我 200 次相同的解决方案。
我希望我的解决方案是这样的:
Solution 0
Day 0
Nurse 0 works from shift 0 to 3
Nurse 1 works from shift 4 to 7
Solution 1
Day 0
Nurse 0 works from shift 0 to 2
Nurse 1 works from shift 2 to 7
Solution 2
Day 0
Nurse 0 works from shift 5 to 7
Nurse 1 works from shift 0 to 5
以及更多其他可行的解决方案。
我已经看过关于 cp_model 和 cp_model.CpSolver cp_model.py 的文档 reference.md
但是上面的none提到了使用CpSolver时的一些选择。 我想知道在使用 CpSolver 时是否可以选择一些方法? 或者我错过了什么?
这是我的代码:
from ortools.sat.python import cp_model
num_nurses = 2
num_shifts = 8
num_days = 1
all_nurses = list(range(num_nurses))
all_shifts = list(range(num_shifts))
all_days = list(range(num_days))
start_shift = list(range(num_shifts))
end_shift = list(range(num_shifts))
RESEARCH_model = cp_model.CpModel()
# Creates shift variables.
RESEARCH_shifts = {}
for n in all_nurses:
for d in all_days:
for start in start_shift:
for end in end_shift:
RESEARCH_shifts[(n, d, start, end)] =\
RESEARCH_model.NewBoolVar('shift_n{}d{}start{}end{}'.format(n,
d, start, end))
# constraint with minimum required nurse equal to 1
for d in all_days:
for s in all_shifts:
RESEARCH_model.Add(sum(RESEARCH_shifts[(n, d, start, end)]
for n in all_nurses
for start in start_shift for end in range(start , num_shifts )
if start <= s <= end) == 1)
# constraint with continuous shifts
for d in all_days:
for n in all_nurses:
RESEARCH_model.Add(sum(RESEARCH_shifts[(n, d, start, end)]
for start in start_shift
for end in range(start, num_shifts )
if 0 <= (end - start + 1) <= 8 ) <= 1)
# the callback
class RESEARCH_NursesPartialSolutionPrinter(cp_model.CpSolverSolutionCallback):
"""Print intermediate solutions."""
def __init__(self, shifts, num_nurses, num_days, num_shifts ,start_shift, end_shift, sols):
cp_model.CpSolverSolutionCallback.__init__(self)
self._shifts = shifts
self._num_nurses = num_nurses
self._num_days = num_days
self._num_shifts = num_shifts
self._solutions = set(sols)
self._solution_count = 0
self._start_shift = start_shift
self._end_shift = end_shift
def on_solution_callback(self):
self._solution_count += 1
if self._solution_count in self._solutions:
print('Solution %i' % self._solution_count)
for d in range(self._num_days):
print(' Day {}'.format(d))
for n in range(self._num_nurses):
for start in self._start_shift:
for end in range(start, self._num_shifts):
if self.Value(self._shifts[(n, d, start, end)]) == True:
print(' Nurse {} works from shift {} to {}'.format(n, start, end))
# create solver and solve it.
solver = cp_model.CpSolver()
# Display the first n solutions.
a_few_solutions = range(200)
RESEARCH_solution_printer = RESEARCH_NursesPartialSolutionPrinter(RESEARCH_shifts,
num_nurses,
num_days,
num_shifts,
start_shift,
end_shift,
a_few_solutions)
solver.parameters.max_time_in_seconds = 2.0
solver.SearchForAllSolutions(RESEARCH_model, RESEARCH_solution_printer)
我希望输出如下:
Solution 0
Day 0
Nurse 0 works from shift 0 to 3
Nurse 1 works from shift 4 to 7
Solution 1
Day 0
Nurse 0 works from shift 0 to 2
Nurse 1 works from shift 3 to 7
Solution 2
Day 0
Nurse 0 works from shift 6 to 7
Nurse 1 works from shift 0 to 5
但我得到的输出如下:
Solution 0
Day 0
Nurse 0 works from shift 0 to 3
Nurse 1 works from shift 4 to 7
Solution 1
Day 0
Nurse 0 works from shift 0 to 3
Nurse 1 works from shift 4 to 7
Solution 2
Day 0
Nurse 0 works from shift 0 to 3
Nurse 1 works from shift 4 to 7
这不是我想要的。
解决方案已在 github
上给出https://github.com/google/or-tools/issues/1300
问题是这段代码创建了很多不受约束的布尔变量。 枚举所有解决方案时,您正在探索这些变量的所有 2^n 组合。