[CP] Driver scheduling (public transportation): enforcing 30 min break after 4 h of driving time

[Manuel Cantele]

Hi,

We're struggling with some aspects of the following problem:

• a public transportation bus timetable consists of shifts (~ track sections) each with fixed start and end times
• bus drivers need to be assigned to each of those shifts
• [constraint in question] legal regulations demand that each bus driver takes a 30 min break after 4 hours of driving (i.e. after driving a certain number of shifts)
• put differently, a driver accrues driving time when driving shifts that must not exceed 4h unless the driver takes a 30 min break in which case the accrued time is "reset to zero"

This type of constraint does not seem to appear in other archetypical assignment / scheduling problems:

• job shop problems are not comparable, because shifts (tasks) can be moved arbitrarily in job shop problems
• nurse / staff scheduling don't care about specific "sequences of shifts" but focus on staff preferences or forbidden assignments
• timetabling problems care mostly about avoiding specific combinations of shifts but again don't take specific "sequences of shifts" into account

In summary, we need to track the accrued driving time of each driver in order to suppress shift assignments to enforce the 30 min break.

So my question is, how to best model the above constraint in a constraint problem with the or-tools?

Thanks in advance!

[Laurent Perron]

So you need 1 circuit constraint per driver.

Arcs correspond to transition between shifts.

Each arc is attached to a Boolean literal.

After each shift, you need to create a dummy shift corresponding to a 30 minutes break.

Then you accumulate worked hours, in a variable bounded at 240 minutes. Then the transition going out of a break resets the variable to 0.

See https://github.com/google/or-tools/blob/stable/examples/contrib/scheduling_with_transitions_sat.py

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

De : Manuel Cantele <manuel....@gmail.com>
Date : sam. 18 mai 2019 à 14:09
À : or-tools-discuss

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/361ff0c3-bcb2-473a-a68e-c0fc64693eaa%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Manuel Cantele]

Hi Laurent,

Thanks for the advice, got it!

I got a followup question though...

I took a look at

• scheduling_with_transitions_sat.py
• single_machine_scheduling_with_setup_release_due_dates_sat.py
• jobshop_ft06_distance_sat.py

and I'm trying to figure out how to combine intervals with assignments.

The examples above dynamically schedule intervals (~shifts) on a time dimension; the shifts are already statically pre-assigned to machines (~drivers).
However I need it the other way round: I got a set of constant intervals (fixed starts/ends) that need to be dynamically assigned to drivers.

So conceptually I'd approach it like this:

1. create a bunch of constant intervals for my shifts, e.g. NewIntervalVar(100, 40, 140, 'shift_10')
2. create some link between drivers and shifts, e.g. NewBoolVar('x[%i,%i]' % (driver_id, shift_id))
3. create no-overlap and circuit constraints for shifts per driver only for the subset of shifts assigned to the driver

Now, step 2 linking intervals to drivers obviously does not work.

So is this approach possible at all?

Thanks,

Manuel

On Saturday, May 18, 2019 at 11:26:07 PM UTC+2, Laurent Perron wrote:

So you need 1 circuit constraint per driver.

Arcs correspond to transition between shifts.

Each arc is attached to a Boolean literal.

After each shift, you need to create a dummy shift corresponding to a 30 minutes break.

Then you accumulate worked hours, in a variable bounded at 240 minutes. Then the transition going out of a break resets the variable to 0.

See https://github.com/google/or-tools/blob/stable/examples/contrib/scheduling_with_transitions_sat.py

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

De : Manuel Cantele <manuel...@gmail.com>

Date : sam. 18 mai 2019 à 14:09
À : or-tools-discuss

Hi,

We're struggling with some aspects of the following problem:

• a public transportation bus timetable consists of shifts (~ track sections) each with fixed start and end times
• bus drivers need to be assigned to each of those shifts
• [constraint in question] legal regulations demand that each bus driver takes a 30 min break after 4 hours of driving (i.e. after driving a certain number of shifts)
• put differently, a driver accrues driving time when driving shifts that must not exceed 4h unless the driver takes a 30 min break in which case the accrued time is "reset to zero"

This type of constraint does not seem to appear in other archetypical assignment / scheduling problems:

• job shop problems are not comparable, because shifts (tasks) can be moved arbitrarily in job shop problems
• nurse / staff scheduling don't care about specific "sequences of shifts" but focus on staff preferences or forbidden assignments
• timetabling problems care mostly about avoiding specific combinations of shifts but again don't take specific "sequences of shifts" into account

In summary, we need to track the accrued driving time of each driver in order to suppress shift assignments to enforce the 30 min break.

So my question is, how to best model the above constraint in a constraint problem with the or-tools?

Thanks in advance!

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools...@googlegroups.com.

[Laurent Perron]

You do not need the scheduling part.

Create a state graph of all shifts with transitions if the second shift can follow the first one. 

Using this graph, create one circuit per driver. Accumulate worked time along the path.

I you can send me a small data set, I would like to write the example.

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/74d33625-05f6-47a5-ab37-13f367c1b04f%40googlegroups.com.

[Manuel Cantele]

Hi Laurent,

Thanks for the help!

I attached a sample data file.

Thanks,

Manuel

[Laurent Perron]

Thanks!

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/6a814f4f-a5da-42cc-8e86-d602b1875395%40googlegroups.com.

[Laurent Perron]

What are the additional constraints ?

Max driving time per driver

Max number of shifts per driver

Max waiting time between shifts

something else ?

Thanks

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

[Manuel Cantele]

Hi Laurent,

There is a distinction between:
- driving time = net time actually spent driving shifts (excluding breaks, idle times, waiting times etc.)
- working time = total work time that day including driving, breaks, idle/waiting times, preparation, cleaning etc.

Constraints for a given day:
- max driving time per driver <= 9h
- max working time per driver <= 12h
- min working time per driver >= 6.5h (driver may actually work less, but always gets paid for at least 6.5h)
- 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

Objective:
- min! the number of drivers
- or alternatively: min! the total working time of all drivers

Thanks!

Manuel

[Laurent Perron]

I guess the 10 and 15 minutes adds to working time and not to driving time.

What is the impact of the 2 minutes ? Min time between two shifts for the same driver ?

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/8be9dc89-0a39-4861-8074-f8376b7362ef%40googlegroups.com.

[Manuel Cantele]

Yes, the 10 / 15 minutes add only to the working time of each driver.

Yes, the 2 minutes are a min time between shifts for each driver during - the time needed for passengers to enter / leave the bus.

[Laurent Perron]

Here is a working code.

https://github.com/google/or-tools/blob/master/examples/python/bus_driver_scheduling_sat.py

It solves the problem in two phases, first computing the optimal number of drivers, then minimizing sum of working times.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/09f11588-8ad7-49f7-9296-ec916e3c364d%40googlegroups.com.

[Manuel Cantele]

Many thanks, Laurent!

[Manuel Cantele]

Hi Laurent,

bus_driver_scheduling_sat.py uses cp_model.LinearExpr.ScalProd

However cp_model does not seem to contain a LinearExpr class (only cp_model.LinearExpression)

I built ortools v7.1.6814 from source based on the master branch but I can't find the LinearExpr class.

What am I doing wrong here?

Thanks,

Manuel

[Laurent Perron]

This is API I added after 7.1

replace cp_model.LinearExpr.ScalProd(vars, coeffs) by sum(vars[i] * coeffs[i] for i in range(len(vars)))

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/1c0ecece-4b31-4dc0-944a-cd290fe612c0%40googlegroups.com.

[Manuel Cantele]

Hi Laurent,

I'm wondering if memory handling of the CP solver can be influenced somehow to avoid out-of-memory issues.

This is what happens:
- I'm on a machine with 252 GB of RAM
- I'm running a slightly modified version of bus_driver_scheduling_sat.py with 200+ shifts instead of 50
- The solution search starts correctly as far as I can tell (see log below)
- At some point all the available memory is used up and the process crashes silently (and the python kernel just restarts)

Can I somehow influence memory management or the solver e.g. by making it buffer data on disk / using less workers etc.?
Or does this particular problem just require a hard minimum amount of available RAM?

This is the solver log (I assume :-):

*** starting model expansion at 0.61s

*** starting model presolve at 1.98s
- 53514 affine relations were detected.
- 53509 variable equivalence relations were detected.
- rule 'at_most_one: duplicate literals' was applied 115297 times.
- rule 'at_most_one: removed literals' was applied 12909 times.
- rule 'at_most_one: satisfied' was applied 820 times.
- rule 'bool_and: always false' was applied 30 times.
- rule 'bool_and: non-reified.' was applied 2 times.
- rule 'bool_or: always true' was applied 728 times.
- rule 'bool_or: fixed literals' was applied 12587 times.
- rule 'bool_or: implications' was applied 411 times.
- rule 'bool_or: only one literal' was applied 652 times.
- rule 'bool_or: removed enforcement literal' was applied 79 times.
- rule 'false enforcement literal' was applied 103313 times.
- rule 'linear: always true' was applied 181 times.
- rule 'linear: divide by GCD' was applied 10 times.
- rule 'linear: empty' was applied 595 times.
- rule 'linear: extracted enforcement literal from constraint' was applied 10 times.
- rule 'linear: fixed or dup variables' was applied 1202 times.
- rule 'linear: infeasible' was applied 560 times.
- rule 'linear: positive equal one' was applied 32040 times.
- rule 'linear: remapped using affine relations' was applied 158 times.
- rule 'linear: simplified rhs' was applied 32275 times.
- rule 'linear: singleton column' was applied 17 times.
- rule 'linear: size one' was applied 1331 times.
- rule 'true enforcement literal' was applied 1086 times.
- rule 'variables: canonicalize affine domain' was applied 5 times.
Optimization model '':
#Variables: 812466 (77 in objective)
 - 1 in [0][16,240]
 - 1 in [0][16,540]
 - 781229 in [0,1]
 - 1 in [0,47]
 - 15460 in [0,240]
 - 15540 in [0,540]
 - 77 in [0,720]
 - 77 in [261,1504]
 - 77 in [271,1519]
 - 1 in [651,981]
 - 1 in [656,986]
 - 1 in [662,992]
#kAtMostOne: 30916 (#literals: 3079349)
#kBoolAnd: 368 (#enforced: 368) (#literals: 368)
#kBoolOr: 30916 (#literals: 3079349)
#kLinear1: 815384 (#enforced: 815384)
#kLinear2: 794500 (#enforced: 794500)
#kLinearN: 78
*** starting parallel search at 41.40s with 10 workers: [ auto, lp_br, pseudo_cost, no_lp, max_lp, quick_restart, core, lns_1, lns_2, lns_3 ]

===> crash...

[Manuel Cantele]

Hi Laurent,

Sorry to bother you again.

Could you give me an indication whether we have a chance to somehow handle the memory requirements issue described above?

Just so I can decide what next steps to take with the implementation.

Thanks,

Manuel

[Laurent Perron]

Reducing memory, nothing concrete. 

You can split the data in 2 and solve 2 models.

Can you send me the large data set ?

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/0c99da05-5c9d-4ed0-b075-2c05ca663fab%40googlegroups.com.

[Manuel Cantele]

OK, I see!

I attached a file containing the aforementioned 200 shifts.

The final problem will actually consist of 1356 shifts, which I attached as well.

Thanks!

On Friday, June 14, 2019 at 10:04:58 AM UTC+2, Laurent Perron wrote:

Reducing memory, nothing concrete. 

You can split the data in 2 and solve 2 models.

Can you send me the large data set ?

[Manuel Cantele]

I saw that you added the two samples to bus_driver_scheduling_sat.py

So, the only possible approach is to split the shifts into subsets and schedule them separately, right?

Thanks,

Manuel

[Laurent Perron]

I will try to change the model.

In the meantime, yes. 

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/c20076c3-62aa-46df-b81a-043599803cc1%40googlegroups.com.

[Manuel Cantele]

Hi Laurent,

Do you maybe have any news regarding the changed version of the model?

We've been experimenting with optimizing different subsets of the shifts separately. And it works from a technical standpoint.

However, the solutions for each subset require more drivers than a naive scheduling heuristic that we use as a benchmark. (we used a time limit of 8 hours for the solver)

So this lets me assume that it's necessary to include as many shifts as possible in one optimization run.

Thanks,

Manuel

On Friday, June 14, 2019 at 2:34:42 PM UTC+2, Laurent Perron wrote:

I will try to change the model.

In the meantime, yes. 

[Laurent Perron]

Yes, I know. We are trying different ideas.

Note that you can hint the solution of the heuristics into the solver.

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/31288c66-6800-4e12-a5ef-efae55bdc3a6%40googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--

--Laurent

[George Lazaridis]

How would the code be modified if we wanted each driver's shifts to be consecutive and overlap at the same time?

[Laurent Perron]

how can they be consecutive and overlap ?

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/d06a8be8-0559-4763-964f-4ea3061e561cn%40googlegroups.com.

[George Lazaridis]

For example, assuming that we have the following shifts:

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', '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]
] 

The range of working hours is from 07:00 am to24: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)

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. 

[Laurent Perron]

so you need to maintain at each node the total time since the start of the shift.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/8d82b03b-ca37-4fd9-882c-6ecba4fc671dn%40googlegroups.com.

[George Lazaridis]

Could you please help me with that? I'm finding it rather difficult to decipher the code

[George Lazaridis]

Is there any example that this has been applied to?

[George Lazaridis]

Hi again, I'm trying to understand where the 'One slot performed per driver' constraint is imposed. If I can alleviate this, then my main problem, i.e. a slot can be performed by multiple drivers, will at least be solved.

All the best

George

[George Lazaridis]

Solved it using the negated_bounded_span() function from here

[George Lazaridis]

In the existing bus scheduling problem, how can we block slots from being assigned a break?

[Laurent Perron]

any arcs between two shifts longer that 30 minutes are considered breaks.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/fc4436df-3b7e-4743-a108-f55f6a263659n%40googlegroups.com.