Driver break discussion

[roganjoshp]

Hi. Firstly, apologies if this belongs on a mailing list (I looked but couldn’t find one) but I wanted to have a discussion about the handling of driver breaks.

I’ve used jsprit now for various projects for the last 6 years and I kicked off the discussion originally that got the first iteration of breaks running there. I’m running on the assumption that you have some familiarity with jsprit given the setup of this library, and it looks like you’re making great progress in some of the shortfalls experienced there.

The one thing that causes no end of problems is driver breaks and it appears that you’ve taken the same default as jsprit did - the break inherits the location of the previous, tangible job and your own docs

The problem with this is that breaks are non-trivial in the solution itself. Because of things like EU regulations it simply isn’t good enough in a solution to have them modelled as soft constraints because the solution breaks the law if the break jobs get kicked out. Across jsprit, OR-Tools (broken for ages), VROOM and this library, I cannot find an implementation that can adequately address this.

Fundamentally, this falls down on the location inheritance. If I need to travel 5 hours from the north of the UK down to Cornwall, on a 9-5 shift (for argument’s sake), with a break in the middle, it’s totally impossible for a solution to ever do this job unless there is some stepping-stone job on the way. Tough luck if you're dispatching a full truck for a single order. The stark reality is that vehicles will park up to satisfy the Tachograph at an intermediate location, but this is not possible either with a forward- or a backward-looking location inheritance.

This has led me down all sorts of paths, with instantaneous services at the warehouse immediately before a break just to try fudge this location inheritance, amongst other hacks. They never properly work. I think we need to move away from breaks being considered as a job that can be inserted into a route and, instead, have something time-based.

I’m engaged with a number of large logistics clients with complex constraints, and I have a wrapper library that calls custom and open-source solvers interchangeably, so I can test a number of very different scenarios. Given that you’re so active in your development at the moment and the fact that you’re addressing issues with the solvers that came before, I’d love to assist in testing if you have any ideas on how this long-standing problem can be fixed. Have you had any thoughts in this space and is this something you’d like to explore?

Thanks,

Josh

[reinterpretcat]

Hi,

I don't have mailing list, but github has discussions.

Regarding jsprit - yes, I'm familiar with the project and I even have some MR to fix break location issue (still opened, probably outdated):

https://github.com/graphhopper/jsprit/pull/440

If I understand correctly, you need breaks which could happen in the middle of the journey from one job (warehouse) to another if it is required legally after specific time. I don't have any immediate solution on top of my mind. I can only think about some preprocessing step which will analyze problem definition to find such long route legs and insert some artificial optional jobs (yes, except start/end, everything is a job). Anyway it is interesting requirement.

Some info about current break implementation and why breaks might be skipped in some cases. In general, breaks are hard for implementation using insertion heuristics: you start from empty route and insert activities one by one. But break cannot be inserted in the beginning:

• it is too early in case of legal break (e.g. break after some working time)
• no locations in the tour for break without specific location
• inserting break early might constraint the search too much.

At the moment, I see two strategies to enforce break in such cases:

• make objective function aware about it:
  • on local level - guide job insertion during constructing/recreating phase
  • on global level - make solutions with more breaks assigned more preferable (implemented via optional parameter in minimize-unassigned objective)
• remove routes without breaks. This can be done:
  • on post processing (client responsibility)
  • after each reconstruction phase

My current implementation interprets breaks as soft constraints and has violations property to highlight when break was not assigned.

[jpilkingtonpeak]

Thank you for your reply :)

Your interpretation of my break requirement is correct; "you need breaks which could happen in the middle of the journey from one job (warehouse) to another if it is required legally after specific time". The point I'm making is that this isn't my need, but at least a legal requirement for everyone in Europe (if not further abroad). The only sensible way for breaks to work here would be to be able to split a single leg journey prevAct to nextAct in jsprit with a pause mid-way.

That isn't possible in jsprit but if the algorithm is looking at absolute time units, it might be possible in this implementation? Local insertion should be able to see when a time threshold for a break is being crossed and add that on the arrival time for the next, actual job?

[jpilkingtonpeak]

If you track the "slack" time in downstream jobs from the point of insertion, and you detect that you've crossed a threshold where a break is needed, then you might still be able to see that this insertion is invalid without parsing the entire route on every insertion position candidate?

[jpilkingtonpeak]

Sorry, just realised I switched github accounts in the meantime :/

[reinterpretcat]

The main problem is to find generic solution: we shouldn't make assumption that long time commute happens only at the beginning. If it is in the middle of the route, then any changes done naturally by metaheuristic, will invalidate previous state and the whole recalculation is needed.

I think adding some extra time for long commute with a break can be also an alternative solution to break as a job approach. However, what would be location then? We leave that for the driver to decide and don't include it in the tour? Also this approach is not easy to implement if break must have specific location.

[jpilkingtonpeak]

we shouldn't make assumption that long time commute happens only at the beginning

Absolutely. I misspoke, sorry. This can happen at any time during a route, not just the first leg of the journey.

However, what would be location then?

Fundamentally, it doesn't need one, because there isn't one. It just needs to see that prevAct + getTravelTime(nextAct) crosses the threshold of a break start, and then add the time duration of the break on. The problem comes with the knock-on effect on downstream jobs in the route, which is why you'd need to track the "slack", or excess time flexibility, of jobs later in the route. In my head this is just array subtraction; I've added 45 minutes to all subsequent arrival times - does that exceed the available slack of any downstream jobs?

If you have the slack stored in a state manager, will this explode the complexity of your insertion heuristic?

[jpilkingtonpeak]

In that scenario, I'm implementing a break as a "job" during the recreate phase, but it only adds its duration, not travel to/from it. Ideally, it should never be in the unassigned pool in the first place. In jsprit, I forbid the ruining of break jobs in the first place and give them priority 1 - they get inserted and that's that.

[reinterpretcat]

yes, there is some state which is associated with the route context. It is used to store some pre-cached values to speedup insertion analysis.

If we accept that such breaks don't have locations, then the next question would be about representing break in the solution. Need to think about it.

Regarding internal api: I would say it is not really ready for extension by code. I put more efforts to support more use cases using pragmatic format and implement them as part of the project.

[reinterpretcat]

maybe this special break, which happens only during traveling, can be implemented as separate feature. But it should be mutual exclusive with current one and the user should have full control on them.

[jpilkingtonpeak]

But it should be mutual exclusive with current one and the user should have full control on them.

Totally agree.

I'm just really happy that you're thinking about it in general. I waffled a bit, but this is a major barrier to implementing the open-source solutions to any business that deals with these legal compliance issues. I'll help in any way I can. I'm trying to learn more rust in the meantime

[reinterpretcat]

At the moment, adding such break as extra time to traveling duration when necessary seems a possible solution. Besides actual implementation, I see the following challenges:

• design consistent json based api (problem and solution models)
• make it work smoothly with existing, job-based breaks
• adjust affected solution checker rules

[reinterpretcat]

Thought about it over night and I think there is some potentially simple way to implement this with some constraints:

• if we constraint that break happens only at exact time (e.g. at 12:00), then implementation goes to wrapping few classes without changing their signature
• if exact time couldn't be defined as break should happen after specific working time, then it is a bit more complicated, but still, potentially doable
• no location for the break in both cases

[jpilkingtonpeak]

This sounds good, I really appreciate you taking time to think it over. I have a couple of things that have bitten me in the past when trying to handle this that might be useful to at least mention (possibly not all relevant):

1. When breaks are modelled as jobs (and possibly when they're just a time inflation) this tends to dispatch the whole fleet because they have jobs to do. This erodes the fixed cost parameter so we risk having more vehicles than necessary released into the solution. Effectively, every driver has a skill-locked job. In the past, I countered this by inflating the distance matrix from the depot to every location by 1000km to approximate a fixed cost. This works for single-day problems, but if I start simulating multiple days with interim stops at the depot, once the dispatched vehicle returns, it's fair game the next day for a totally different vehicle to be dispatched (that currently wasn't needed the previous day) because it's cost-indifferent to using the vehicle from the day before - both would get the same 1000km penalty

2. Back-to-back breaks are a challenge for local insertion heuristics (just looking at prevAct, newAct, nextAct). You can get an indefinitely long chain of absent locations, especially when initialising a solution. So one would want to be mindful of this

3. Having a completely hard, fixed start time for this new type of break, it might start introducing a lot of waiting time. One job could be traveled to and completed in 21 minutes, but the break starts in 20. So it becomes cheaper to sit around for 20 mins waiting for the break to start (extreme example). It’s hard to estimate how bad this problem could get until it’s run on some real data, but I anticipate it as a concern

[reinterpretcat]

Thanks for info! I might try to prototype very basic implementation which supposed to add break time to traveling time when necessary. However, I want first to finish my current task (heuristic refactoring)

[jpilkingtonpeak]

Please don't let me derail your existing plans; I'm glad you've taken an interest in this problem (and feel free to migrate to a discussion if that's possible; we don't have that tab internally so I didn't know it was a thing with git, sorry!). In the meantime, I'm going to try wrap this library on my side too (which will take me some time anyway) so that I can start running on some real data and give real-world feedback on prototypes. Certain details I won't be able to share, but I'm hopeful we can get to some working middle ground. It'd be awesome to close this long-standing issue