Handle breaks

[jcoupey]

Now that we have support for timing constraints, we should handle drivers breaks. To some extent, there are already some options to do that:

1. Hard-code working hours using one vehicle per time window (possibly with the same vehicle id). Downside: requires to impose the break location as end/start of the time windows, offers no flexibility with regard to timing (e.g. won't allow a small break shift past the time window end to handle one more job).
2. Define the break as a regular job with service time and time window. This is better in term of flexibility but still requires a fixed location, and offers no guarantee that the "break job" won't end up unassigned.

I want to define a break as some kind of "location-less" job. It should be movable forward or backward in time depending on surrounding jobs to solve the flexibility problem described above.

On the API side, we could add a breaks array for each vehicle, containing objects with a service and time_window key (not sure if there is a point in specifying several time windows for a given break?).

As far as I can tell for the solving side, this would require to:

• fill empty routes with breaks in the tw_route ctor to make sure they're mandatory
• apply the job time margin logic to breaks in tw_route to allow temporal moves while more jobs are added
• add some cost evaluation trick so that reaching from or to a break costs 0
• make sure breaks stay in place during the local search phase

There is probably some tricky stuff involved for operators gain evaluation and validity checks.

[krypt-n]

Two things to consider that I encountered:

• Sometimes a break is only necessary if the vehicle "works" more than N hours. E.g. if the route of a vehicle is only 5:30h there doesn't need to be a break, but if it is 6:00h or longer it needs to include a break.

• Some requirements allow multiple breaks per day as an alternative to a single break.

[jcoupey]

@krypt-n thanks for your input! The implementation sketch above does not take into account this kind of regulation subtleties. The difficulty with these is that the break length(s) and position(s) would have to be decided dynamically at every step depending on the route characteristics. So for every tiny route modification, we'd be introducing a whole new range of combinatorial choices.

The approach I described does assume that breaks are "hard-coded" in input which is kind of limiting, though already allowing temporal flexibility. But I think it's a good first step that's already enough for many use-cases.

[jcoupey]

I just merged #303 so this should now be fully functional on master. Any feedback appreciated!