python - ortools中修正的总线调度问题

Question

我要修改bus scheduling problem from ortools因此每个司机的轮类在插槽方面是连续的，如果需要，司机可以同时共享一个类次。
例如，假设我们有以下半小时类次(格式类似于来自 ortools 的原始 bus_scheduling_problem):

shifts = [
[0, '07:00', '07:30', 420, 450, 30],
[1, '07:30', '08:00', 450, 480, 30],
[2, '08:00', '08:30', 480, 510, 30],
[3, '08:30', '09:00', 510, 540, 30],
[4, '09:00', '09:30', 540, 570, 30],
[5, '09:30', '10:00', 570, 600, 30],
[6, '10:00', '10:30', 600, 630, 30],
[7, '10:30', '11:00', 630, 660, 30],
[8, '11:00', '11:30', 660, 690, 30],
[9, '11:30', '12:00', 690, 720, 30],
[10, '12:00', '12:30', 720, 750, 30],
[11, '12:30', '13:00', 750, 780, 30],
[12, '13:00', '13:30', 780, 810, 30],
[13, '13:30', '14:00', 810, 840, 30],
[14, '14:00', '14:30', 840, 870, 30],
[15, '14:30', '15:00', 870, 900, 30],
[16, '15:00', '15:30', 900, 930, 30],
[17, '15:30', '16:00', 930, 960, 30],
[18, '16:00', '16:30', 960, 990, 30],
[19, '16:30', '17:00', 990, 1020, 30],
[20, '17:00', '17:30', 1020, 1050, 30],
[21, '17:30', '18:00', 1050, 1080, 30],
[22, '18:00', '18:30', 1080, 1110, 30],
[23, '18:30', '19:00', 1110, 1140, 30],
[24, '19:00', '19:30', 1140, 1170, 30],
[25, '19:30', '20:00', 1170, 1200, 30],
[26, '20:00', '20:30', 1200, 1230, 30],
[27, '20:30', '21:00', 1230, 1260, 30],
[28, '21:00', '21:30', 1260, 1290, 30],
[29, '21:30', '22:00', 1290, 1320, 30],
[30, '22:00', '22:30', 1320, 1350, 30],
[31, '22:30', '23:00', 1350, 1380, 30],
[32, '23:00', '23:30', 1380, 1410, 30],
[33, '23:30', '24:00', 1410, 1440, 30]
]

我成功执行了 this version of the bus_scheduling code我发现我需要 2 个司机来满足上述时间表的需求。工作时间范围从 07:00 am to 24:00 (midnight) .
因此，如果我们有 2 名巴士司机来安排这个时间表，我更愿意根据 12 小时司机轮类来涵盖每日值类的分配如下:

Driver 1: 07:00 - 19:00 with a break at 13:00
Driver 2: 12:00 - 24:00 with a break at 14:00 (basically no overlap with Driver 1's break)

我所说的连续小时是指满足 的解决方案。 12小时司机以 07:00-11:00 + 14:00-15:00 + 17:00-24:00的形式转移解决方案应该 不是 可以接受。具有更多驱动程序的解决方案还应确保中断不会重叠，例如 不是 所有司机都在休息。此外，由于工作量大，休息槽可能会被堵塞。
我在 or-tools 讨论中得到了一个答案，说我需要在每个节点上维护自轮类开始以来的总时间，但是我在编码时遇到了困难，假设它解决了我的问题。

Answer 1

对我来说，bus scheduling problem from ortools对您的任务来说是一种矫枉过正，因为您提到轮类持续时间总是 30分钟，并且不需要设置/清理时间。此外，驱动程序必须完全正常工作 11小时，并有一个连续的休息时间。相反，我们可以编写一个类似于 nurse scheduling problem 的脚本。这可能更容易理解(对我来说，这是第一次用 或-tools 写东西，这很清楚)。
准备
首先，总类次可以计算如下:

num_shifts = len(shifts)

需要的驱动程序数量:

num_drivers = ceil(float(num_shifts) / working_time)

在您的情况下，司机必须准确驾驶 11小时，所以它是 22类次(每类固定在 30 分钟):

working_time = 22

中断是 1小时所以:

break_time = 2

正如你在评论中提到的，每个司机必须在 4之后休息一下。小时的驾驶，但不迟于之后 8小时:

break_interval = [8, 16]

司机可以开始工作的最新类次:

latest_start_shift = num_shifts - working_time - break_time

真的，如果他/她晚点开始工作，那么司机就不会在整个工作时间内工作。
构建模型
让我们为司机定义一个轮类数组:

driver_shifts = {}
for driver_id in range(num_drivers):
    for shift_id in range(num_shifts):
        driver_shifts[(driver_id, shift_id)] = model.NewBoolVar('driver%ishift%i' % (driver_id, shift_id))

driver_shifts[(d, s)]等于 1如果转移 s分配给驱动程序 d , 和 0除此以外。
此外，为司机创建一系列开始类次:

start_time = {}
for driver_id in range(num_drivers):
    for shift_id in range(latest_start_shift + 1):
        start_time[(driver_id, shift_id)] = model.NewBoolVar('driver%istart%i' % (driver_id, shift_id))

start_time[(d, s)]等于 1如果驱动程序 d值类开始工作日 s , 和 0除此以外。
司机每天开车正好 11 小时
每个司机必须在一天内准确驾驶所需的驾驶时间:

for driver_id in range(num_drivers):
    model.Add(sum(driver_shifts[(driver_id, shift_id)] for shift_id in range(num_shifts)) == working_time)

然而，这还不够，因为驱动程序必须连续进行，中间有一个休息时间。我们稍后会看到如何做到这一点。
所有类次均由司机负责
每个类次必须由至少一名司机负责:

for shift_id in range(num_shifts):
    model.Add(sum(driver_shifts[(driver_id, shift_id)] for driver_id in range(num_drivers)) >= 1)

驱动程序连续行驶
在这里 start_time发挥作用。基本思想是，对于驱动程序的每个可能的开始时间，我们强制驱动程序在非工作时间工作(实际上，驱动程序每天只能开始工作一次!)。
因此，驱动程序每天只能开始工作一次:

for driver_id in range(num_drivers):
    model.Add(sum(start_time[(driver_id, start_shift_id)] for start_shift_id in range(latest_start_shift + 1)) == 1)

驱动器每次启动时间，连续工作时间 working_time + break_time是 working_time

for driver_id in range(num_drivers):
     for start_shift_id in range(latest_start_shift + 1):
         model.Add(sum(driver_shifts[(driver_id, shift_id)] for shift_id in
                   range(start_shift_id, start_shift_id + working_time + break_time)) == working_time) \
             .OnlyEnforceIf(start_time[(driver_id, start_shift_id)]) 

中断是连续的
为此，我们需要一个额外的数组 break_ind[(d, s, b)]表示是否给定驱动程序 d以给定的工作类次开始 s轮类休息 b .所以，在这种情况下， driver_shifts值应该是 0休息时间:

     l = start_shift_id + break_interval[0]
     r = start_shift_id + break_interval[1]
     for s in range(l, r):
        break_ind[(driver_id, start_shift_id, s)] = model.NewBoolVar("d%is%is%i"%(driver_id, start_shift_id, s))
        model.Add(sum(driver_shifts[(driver_id, s1)] for s1 in range(s, s + break_time)) == 0)\
        .OnlyEnforceIf(start_time[(driver_id, start_shift_id)])\
        .OnlyEnforceIf(break_ind[(driver_id, start_shift_id, s)]) 

此外，司机每天只能休息一次:

model.Add(sum(break_ind[(driver_id, start_shift_id, s)] for s in range(l, r)) == 1)

完整代码
您可以查看下面的完整代码或 here (我添加它以供将来引用)。在那里，您还可以找到司机不休息的情况下的简化版本。

from ortools.sat.python import cp_model
from math import ceil

shifts = [
    [0, '07:00', '07:30', 420, 450, 30],
    [1, '07:30', '08:00', 450, 480, 30],
    [2, '08:00', '08:30', 480, 510, 30],
    [3, '08:30', '09:00', 510, 540, 30],
    [4, '09:00', '09:30', 540, 570, 30],
    [5, '09:30', '10:00', 570, 600, 30],
    [6, '10:00', '10:30', 600, 630, 30],
    [7, '10:30', '11:00', 630, 660, 30],
    [8, '11:00', '11:30', 660, 690, 30],
    [9, '11:30', '12:00', 690, 720, 30],
    [10, '12:00', '12:30', 720, 750, 30],
    [11, '12:30', '13:00', 750, 780, 30],
    [12, '13:00', '13:30', 780, 810, 30],
    [13, '13:30', '14:00', 810, 840, 30],
    [14, '14:00', '14:30', 840, 870, 30],
    [15, '14:30', '15:00', 870, 900, 30],
    [16, '15:00', '15:30', 900, 930, 30],
    [17, '15:30', '16:00', 930, 960, 30],
    [18, '16:00', '16:30', 960, 990, 30],
    [19, '16:30', '17:00', 990, 1020, 30],
    [20, '17:00', '17:30', 1020, 1050, 30],
    [21, '17:30', '18:00', 1050, 1080, 30],
    [22, '18:00', '18:30', 1080, 1110, 30],
    [23, '18:30', '19:00', 1110, 1140, 30],
    [24, '19:00', '19:30', 1140, 1170, 30],
    [25, '19:30', '20:00', 1170, 1200, 30],
    [26, '20:00', '20:30', 1200, 1230, 30],
    [27, '20:30', '21:00', 1230, 1260, 30],
    [28, '21:00', '21:30', 1260, 1290, 30],
    [29, '21:30', '22:00', 1290, 1320, 30],
    [30, '22:00', '22:30', 1320, 1350, 30],
    [31, '22:30', '23:00', 1350, 1380, 30],
    [32, '23:00', '23:30', 1380, 1410, 30],
    [33, '23:30', '24:00', 1410, 1440, 30]
]

class VarArraySolutionPrinter(cp_model.CpSolverSolutionCallback):
    def __init__(self, driver_shifts, num_drivers, num_shifts, solutions):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.driver_shifts = driver_shifts
        self.num_drivers = num_drivers
        self.num_shifts = num_shifts
        self.solutions = solutions
        self.solution_id = 0

    def on_solution_callback(self):
        if self.solution_id in self.solutions:
            self.solution_id += 1
            print ("Solution found!")
            for driver_id in range(self.num_drivers):
                print ("*************Driver#%s*************" % driver_id)
                for shift_id in range(self.num_shifts):
                    if (self.Value(self.driver_shifts[(driver_id, shift_id)])):
                        print('Shift from %s to %s' %
                              (shifts[shift_id][1],
                               shifts[shift_id][2]))
            print()

    def solution_count(self):
        return self.solution_id

solver = cp_model.CpSolver()
model = cp_model.CpModel()

num_shifts = len(shifts)

working_time = 22
break_time = 2

# when take a break within the working time
break_interval = [8, 16]

latest_start_shift = num_shifts - working_time - break_time
num_drivers = ceil(float(num_shifts) / working_time)

# create an array of assignments of drivers
driver_shifts = {}
for driver_id in range(num_drivers):
    for shift_id in range(num_shifts):
        driver_shifts[(driver_id, shift_id)] = model.NewBoolVar('driver%ishift%i' % (driver_id, shift_id))

# driver must work exactly {working_time} shifts
for driver_id in range(num_drivers):
    model.Add(sum(driver_shifts[(driver_id, shift_id)] for shift_id in range(num_shifts)) == working_time)

# each shift must be covered by at least one driver
for shift_id in range(num_shifts):
    model.Add(sum(driver_shifts[(driver_id, shift_id)] for driver_id in range(num_drivers)) >= 1)

# create an array of start times for drivers
start_time = {}
for driver_id in range(num_drivers):
    for shift_id in range(latest_start_shift + 1):
        start_time[(driver_id, shift_id)] = model.NewBoolVar('driver%istart%i' % (driver_id, shift_id))

break_ind = {}
for driver_id in range(num_drivers):
     for start_shift_id in range(latest_start_shift + 1):
         model.Add(sum(driver_shifts[(driver_id, shift_id)] for shift_id in
                   range(start_shift_id, start_shift_id + working_time + break_time)) == working_time) \
             .OnlyEnforceIf(start_time[(driver_id, start_shift_id)])

         l = start_shift_id + break_interval[0]
         r = start_shift_id + break_interval[1]
         for s in range(l, r):
            break_ind[(driver_id, start_shift_id, s)] = model.NewBoolVar("d%is%is%i"%(driver_id, start_shift_id, s))
            model.Add(sum(driver_shifts[(driver_id, s1)] for s1 in range(s, s + break_time)) == 0)\
            .OnlyEnforceIf(start_time[(driver_id, start_shift_id)])\
            .OnlyEnforceIf(break_ind[(driver_id, start_shift_id, s)])
         model.Add(sum(break_ind[(driver_id, start_shift_id, s)] for s in range(l, r)) == 1)

for driver_id in range(num_drivers):
    model.Add(sum(start_time[(driver_id, start_shift_id)] for start_shift_id in range(latest_start_shift + 1)) == 1)

solution_printer = VarArraySolutionPrinter(driver_shifts, num_drivers, num_shifts, range(2))
status = solver.SearchForAllSolutions(model, solution_printer)