Modified bus scheduling problem question in ortools

Has been crossposted in stackoverflow. I want to solve the bus scheduling problem using ortools with some minor modifications. In my case, the max number of drivers is known. The modifications I would like to have in the code are:

1. Shifts can overlap, i.e. drivers can work in parallel

2. Shifts must be consecutive

3. Breaks of drivers cannot overlap

4. Max, min driving and max working time are the same as in predefined fixed duty

TL;DR: The range of working hours is from 07:00 am to 24:00 (midnight). If we have 2 bus drivers for this schedule, I would accept an allocation to cover 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 break)

We can see that shifts can be covered by both drivers and 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.

Here's the code I am using:

# Copyright 2010-2018 Google LLC
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#
# Unless required by applicable law or agreed to in writing, software
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
"""This model implements a bus driver scheduling problem.

Constraints:
- max driving time per driver <= 12h
- max working time per driver <= 12h
- min working time per driver >= 12h (soft)
- 30 min break after each 4h of driving time per driver
- 10 min preparation time before the first shift
- 15 min cleaning time after the last shift
- 2 min waiting time after each shift for passenger boarding and alighting
"""

import collections
import math

from absl import app
from absl import flags
from ortools.sat.python import cp_model

FLAGS = flags.FLAGS

flags.DEFINE_string('output_proto', '',
'Output file to write the cp_model proto to.')
flags.DEFINE_string('params', 'num_search_workers:8,log_search_progress:true',
'Sat solver parameters.')
flags.DEFINE_integer('instance', 1, 'Instance to select (1, 2, 3).', 1, 3)

SAMPLE_SHIFTS_SMALL = [
#
# column description:
# - shift id
# - shift start time as hh:mm string (for logging and readability purposes)
# - shift end time as hh:mm string (for logging and readability purposes)
# - shift start minute
# - shift end minute
# - shift duration in minutes
#
[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', '19: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', 1320, 1350, 30],
[30, '22:00', '22:30', 1350, 1380, 30],
[31, '22:30', '23:00', 1410, 1440, 30],
[32, '23:00', '23:30', 1440, 1470, 30],
[33, '23:30', '24:00', 1470, 1500, 30]
]  # yapf:disable

# pytype: disable=wrong-arg-types

def bus_driver_scheduling(minimize_drivers, max_num_drivers):
"""Optimize the bus driver scheduling problem.

This model has two modes.

If minimize_drivers == True, the objective will be to find the minimal
number of drivers, independently of the working times of each drivers.

Otherwise, will will create max_num_drivers non optional drivers, and
minimize the sum of working times of these drivers.

Args:
minimize_drivers: A Boolean parameter specifying the objective of the
problem. If True, it tries to minimize the number of used drivers. If
false, it minimizes the sum of working times per workers.
max_num_drivers: This number specifies the exact number of non optional
drivers to use. This is only used if 'minimize_drivers' is False.

Returns:
The objective value of the model.
"""
shifts = None
if FLAGS.instance == 1:
shifts = SAMPLE_SHIFTS_SMALL

num_shifts = len(shifts)

# All durations are in minutes.
max_driving_time = 720  # 12 hours.
max_driving_time_without_pauses = 720
min_pause_after_4h = 30
max_pause_after_4h = 30
min_delay_between_shifts = 0
max_working_time = 720
min_working_time = 720  # 12 hours
setup_time = 0
cleanup_time = 0

# Computed data.
total_driving_time = sum(shift[5] for shift in shifts)
min_num_drivers = int(math.ceil(total_driving_time * 1.0 /
max_driving_time))
num_drivers = 2 * min_num_drivers if minimize_drivers else max_num_drivers
min_start_time = min(shift[3] for shift in shifts)
max_end_time = max(shift[4] for shift in shifts)

print('Bus driver scheduling')
print('  num shifts =', num_shifts)
print('  total driving time =', total_driving_time, 'minutes')
print('  min num drivers =', min_num_drivers)
print('  num drivers =', num_drivers)
print('  min start time =', min_start_time)
print('  max end time =', max_end_time)

model = cp_model.CpModel()

# For each driver and each shift, we store:
#   - the total driving time including this shift
#   - the acrued driving time since the last 30 minute break
# Special arcs have the following effect:
#   - 'from source to shift' sets the starting time and accumulate the first
#      shift
#   - 'from shift to end' sets the ending time, and fill the driving_times
#      variable
# Arcs between two shifts have the following impact
#   - add the duration of the shift to the total driving time
#   - reset the accumulated driving time if the distance between the two
#     shifts is more than 30 minutes, add the duration of the shift to the
#     accumulated driving time since the last break otherwise

# Per (driver, node) info (driving time, performed,
# driving time since break)
total_driving = {}
no_break_driving = {}
performed = {}
starting_shifts = {}

# Per driver info (start, end, driving times, is working)
start_times = []
end_times = []
driving_times = []
working_drivers = []
working_times = []

# Weighted objective
delay_literals = []
delay_weights = []

# Used to propagate more between drivers
shared_incoming_literals = collections.defaultdict(list)
shared_outgoing_literals = collections.defaultdict(list)

for d in range(num_drivers):
start_times.append(
model.NewIntVar(min_start_time - setup_time, max_end_time,
'start_%i' % d))
end_times.append(
model.NewIntVar(min_start_time, max_end_time + cleanup_time,
'end_%i' % d))
driving_times.append(
model.NewIntVar(0, max_driving_time, 'driving_%i' % d))
working_times.append(
model.NewIntVar(0, max_working_time, 'working_times_%i' % d))

incoming_literals = collections.defaultdict(list)
outgoing_literals = collections.defaultdict(list)
outgoing_source_literals = []
incoming_sink_literals = []

# Create all the shift variables before iterating on the transitions
# between these shifts.
for s in range(num_shifts):
total_driving[d, s] = model.NewIntVar(0, max_driving_time,
'dr_%i_%i' % (d, s))
no_break_driving[d, s] = model.NewIntVar(
0, max_driving_time_without_pauses, 'mdr_%i_%i' % (d, s))
performed[d, s] = model.NewBoolVar('performed_%i_%i' % (d, s))

for s in range(num_shifts):
shift = shifts[s]
duration = shift[5]

# Arc from source to shift.
#    - set the start time of the driver
#    - increase driving time and driving time since break
source_lit = model.NewBoolVar('%i from source to %i' % (d, s))
outgoing_source_literals.append(source_lit)
incoming_literals[s].append(source_lit)
shared_incoming_literals[s].append(source_lit)
setup_time).OnlyEnforceIf(source_lit)
s] == duration).OnlyEnforceIf(source_lit)
starting_shifts[d, s] = source_lit

# Arc from shift to sink
#    - set the end time of the driver
#    - set the driving times of the driver
sink_lit = model.NewBoolVar('%i from %i to sink' % (d, s))
outgoing_literals[s].append(sink_lit)
shared_outgoing_literals[s].append(sink_lit)
incoming_sink_literals.append(sink_lit)
cleanup_time).OnlyEnforceIf(sink_lit)
driving_times[d] == total_driving[d, s]).OnlyEnforceIf(sink_lit)

# Node not performed
#    - set both driving times to 0
#    - add a looping arc on the node
s] == 0).OnlyEnforceIf(performed[d,
s].Not())
performed[d, s].Not())
incoming_literals[s].append(performed[d, s].Not())
outgoing_literals[s].append(performed[d, s].Not())
# Not adding to the shared lists, because, globally, each node will have
# one incoming literal, and one outgoing literal.

# Node performed:
#    - add upper bound on start_time
#    - add lower bound on end_times
performed[d, s])
performed[d, s])

for o in range(num_shifts):
other = shifts[o]
delay = other[3] - shift[4]
if delay < min_delay_between_shifts:
continue
lit = model.NewBoolVar('%i from %i to %i' % (d, s, o))

# Increase driving time
model.Add(total_driving[d, o] == total_driving[d, s] +
other[5]).OnlyEnforceIf(lit)

# Increase no_break_driving or reset it to 0 depending on the delay
if max_pause_after_4h >= delay >= min_pause_after_4h:
no_break_driving[d, o] == other[5]).OnlyEnforceIf(lit)
else:
model.Add(no_break_driving[d, o] == no_break_driving[d, s] +
other[5]).OnlyEnforceIf(lit)

outgoing_literals[s].append(lit)
shared_outgoing_literals[s].append(lit)
incoming_literals[o].append(lit)
shared_incoming_literals[o].append(lit)

# Cost part
delay_literals.append(lit)
delay_weights.append(delay)

if minimize_drivers:
# Driver is not working.
working = model.NewBoolVar('working_%i' % d)
working.Not())
working.Not())
working_drivers.append(working)
outgoing_source_literals.append(working.Not())
incoming_sink_literals.append(working.Not())
# Conditional working time constraints
working_times[d] >= min_working_time).OnlyEnforceIf(working)
else:
# Working time constraints

# Create circuit constraint.
for s in range(num_shifts):

# Each shift is covered.
for s in range(num_shifts):
model.Add(sum(performed[d, s] for d in range(num_drivers)) == 1)
# Globally, each node has one incoming and one outgoing literal

# Symmetry breaking

# The first 1 shift must be performed by 1 different drivers.
# Let's assign them to the first driver in sequence

if minimize_drivers:
# Push non working drivers to the end
for d in range(num_drivers - 1):
working_drivers[d + 1].Not())

# Redundant constraints: sum of driving times = sum of shift driving times
if not minimize_drivers:
cp_model.LinearExpr.Sum(working_times) == total_driving_time +
num_drivers * (setup_time + cleanup_time) +
cp_model.LinearExpr.ScalProd(delay_literals, delay_weights))

if minimize_drivers:
# Minimize the number of working drivers
model.Minimize(cp_model.LinearExpr.Sum(working_drivers))
else:
# Minimize the sum of delays between tasks, which in turns minimize the
# sum of working times as the total driving time is fixed
model.Minimize(
cp_model.LinearExpr.ScalProd(delay_literals, delay_weights))

if not minimize_drivers and FLAGS.output_proto:
print('Writing proto to %s' % FLAGS.output_proto)
with open(FLAGS.output_proto, 'w') as text_file:
text_file.write(str(model))

# Solve model.
solver = cp_model.CpSolver()
if FLAGS.params:
text_format.Parse(FLAGS.params, solver.parameters)

status = solver.Solve(model)

if status != cp_model.OPTIMAL and status != cp_model.FEASIBLE:
return -1

# Display solution
if minimize_drivers:
max_num_drivers = int(solver.ObjectiveValue())
print('minimal number of drivers =', max_num_drivers)
return max_num_drivers

for d in range(num_drivers):
print('Driver %i: ' % (d + 1))
print('  total driving time =', solver.Value(driving_times[d]))
print('  working time =',
solver.Value(working_times[d]) + setup_time + cleanup_time)

first = True
for s in range(num_shifts):
shift = shifts[s]

if not solver.BooleanValue(performed[d, s]):
continue

# Hack to detect if the waiting time between the last shift and
# this one exceeds 30 minutes. For this, we look at the
# no_break_driving which was reinitialized in that case.
if solver.Value(no_break_driving[d, s]) == shift[5] and not first:
print('    **break**')
print('    shift ', shift[0], ':', shift[1], '-', shift[2])
first = False

return int(solver.ObjectiveValue())

def main(_):
"""Optimize the bus driver allocation in two passes."""
print('----------- first pass: minimize the number of drivers')
num_drivers = bus_driver_scheduling(False, 2)
if num_drivers == -1:
print('no solution found, skipping the final step')
else:
print('----------- second pass: minimize the sum of working times')
bus_driver_scheduling(False, num_drivers)

if __name__ == '__main__':
app.run(main)

• please indicate when you crosspost (or-tools-discuss and or.stackexchange) – Laurent Perron Mar 26 at 15:25