ortools中修正的总线调度问题 [英] Modified bus scheduling problem in ortools
问题描述
我想修改 来自或工具，以便每个司机的轮班在插槽方面是连续的，如果需要，司机可以同时共享一个班次.
I want to modify the bus scheduling problem from ortools so as each driver's shift to be consecutive in terms of slots and drivers can share a shift at the same time if needed.
例如，假设我们有以下半小时班次(格式类似于来自ortools的原始bus_scheduling_problem):
For example, assuming that we have the following half-hour shifts (format similar to the original bus_scheduling_problem from ortools):
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]
]
我成功执行了这个版本的bus_scheduling代码，我发现我需要 2 个驱动程序来满足上述时间表的需求.工作时间范围为07:00 am to 24:00(午夜).
I successfully execute the this version of the bus_scheduling code and I find that I need 2 drivers to satisfy the needs for the above mentioned schedule. The range of working hours is from 07:00 am to 24:00 (midnight).
因此，如果我们有 2 名巴士司机用于此时间表，我更愿意根据 12 小时司机班次分配涵盖每日值班的分配如下:
As a result, if we have 2 bus drivers for this schedule, I would prefer an allocation that covers the daily duty based on 12-h driver shift as following:
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 应该不是可以接受的.具有更多驱动程序的解决方案还应确保休息时间不会重叠，以便并非所有驱动程序都在休息.此外，由于工作量大，休息槽可能会被堵塞.
What I mean by consecutive hours is that solutions that satisfy a 12-h driver shift solution in the form of 07:00-11:00 + 14:00-15:00 + 17:00-24:00 should not be acceptable. Solutions with more drivers should also make sure that breaks are not overlapping so as not all drivers are on break. Moreover, slots for breaks can be blocked due to high work load.
我在 or-tools 讨论 中得到一个 答案 说我需要在每个节点维护自轮班开始以来的总时间，但我编码有困难，假设它解决了我的问题.
I got an answer at the or-tools discussion saying that I need to maintain at each node the total time since the start of the shift, but I'm having difficulty in coding that assuming it solves my question.
推荐答案
对我来说，ortools 中的总线调度问题 对您的任务来说太过分了，因为您提到轮班持续时间总是 30 分钟，并且不需要设置/清理时间.此外，司机必须准确地工作 11 小时，并有连续的休息时间.相反，我们可以编写一个类似于护士排班问题的脚本，这可能更容易理解(对我来说，这是第一次用 or-tools 写东西，而且很清楚).
To me, bus scheduling problem from ortools is an overkill for your task since you mentioned that shift durations are always 30 minutes, and setup/cleanup time is not needed. Moreover, drivers must work exactly 11 hours and have a contiguous break. Instead, we could write a script similar to nurse scheduling problem that is probably easier to understand (for me, it was the first time writing something with or-tools and it was clear).
首先，总班次可以计算如下:
First, the total number of shifts can be calculated as below:
num_shifts = len(shifts)
所需的驱动程序数量:
num_drivers = ceil(float(num_shifts) / working_time)
在您的情况下，司机必须准确驾驶 11 小时，所以它是 22 个班次(每个班次固定为 30 分钟):
In your case, driver must drive exactly 11 hours, and so it's 22 shifts (each shift is fixed at 30 minutes):
working_time = 22
休息时间为 1 小时，所以:
Break is 1 hour so:
break_time = 2
正如您在评论中提到的，每位司机必须在驾驶 4 小时后休息，但不得迟于 8 小时后:
As you mentioned in the comment, each driver must take a break after 4 hours of driving, but not later than after 8 hours:
break_interval = [8, 16]
司机可以开始工作的最新班次:
The latest shift when a driver can start working:
latest_start_shift = num_shifts - working_time - break_time
真的，如果他/她晚点开始工作，那么司机就不会在整个工作时间内工作.
Really, if he/she starts working later, then the driver won't work off the full working time.
让我们为司机定义一个班次数组:
Let's define an array of shifts for 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_shifts[(d, s)] 等于 1 如果 shift s 分配给驱动程序 d，和 0 否则.
driver_shifts[(d, s)] equals 1 if shift s is assigned to driver d, and 0 otherwise.
另外，为司机创建一个开始班次的数组:
Additionally, create an array of start shifts 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))
start_time[(d, s)] 等于 1 如果司机 d 在班次 s 开始一个工作日> 和 0 否则.
start_time[(d, s)] equals 1 if driver d starts a working day at shift s, and 0 otherwise.
每位司机必须在一天内准确驾驶所需的驾驶时间:
Each driver must drive exactly the required driving time within the day:
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)
然而，这还不够，因为驱动程序必须连续进行，中间有一个休息时间.我们稍后会看到如何做到这一点.
However, it's not enough since the driver must do it contiguously with one break in between. We will see how to do this later.
每个班次必须由至少一名司机负责:
Each shift must be covered by at least one driving 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)
驱动程序连续驱动
这里是 start_time 发挥作用的地方.基本思想是，对于驱动程序的每个可能的开始时间，我们强制驱动程序在非工作时间工作(实际上，驱动程序每天只能开始工作一次！).
Driver drives contiguously
Here where start_time comes into play. The basic idea is that for each possible start time of driver, we enforce that the driver works off the time (physically, a driver can start working only once day!).
因此，驱动程序每天只能开始工作一次:
So, driver can start working only once per day:
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 each start time of the driver, the working time within consecutive working_time + break_time is 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 用于中断时间:
Break is contiguous
For this, we need an additional array break_ind[(d, s, b)] that denotes whether a given driver d with a given working shift start s takes a break at shift b. So, in this case, driver_shifts values should be 0 for the time of the break:
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)])
此外，司机每天只能休息一次:
Also, a driver can take a break only once a day:
model.Add(sum(break_ind[(driver_id, start_shift_id, s)] for s in range(l, r)) == 1)
完整代码
您可以查看下面的完整代码或这里(我添加了它以供参考将来).在那里，您还可以找到司机不休息的情况下的简化版本.
Full Code
You can check the full code below or here (I added it for reference in the future). There you can also find a simplified version for a case when drivers don't take a break.
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)
这篇关于ortools中修正的总线调度问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
