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):

graphhopper/jsprit#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

[reinterpretcat]

I've slowly started prototyping the solution. At the moment, I decided to split breaks into two types:

https://github.com/reinterpretcat/vrp/blob/required_break/vrp-pragmatic/src/format/problem/model.rs#L431-L449

Required break will be a new type which allows to schedule a break at exact time or after exact working time. So far, I identified the following challenges:

• waiting time handling: break falls on time where driver waits for job's time window. Need to think about potential use cases and related problems here, e.g. do we count waiting time as break time?..
• other non-driving time handling, e.g. serving, reloading, etc.
• departure rescheduling: this functionality reschedules departure to reduce waiting time and it might push the break to the future in case of the second break time type. This is an implementation challenge, the simple solution would be just to disable the feature in case of such break (don't like this approach and will try to avoid it)
• solution representation: if break falls in the middle of the travel, how we represent it in the tour? I'm thinking about adding an extra stop with break activity between two stops, but location has to be specified for it. Probably I can just use location from previous or next stop.
• it won't cover scenarios like "shouldn't drive more than two hours without some break", my understanding that the need is more about total working time. Theoretically, just adding an extra duration to such route legs as preprocessing step and do postprocessing to expand it in the solution can be an alternative solution.

[jpilkingtonpeak]

Thanks for your detailed reply! I put your comments back to one of my colleagues (sbloor) who has drafted responses to each of your points internally, and we've just finished a lively discussion around some of the things you've raised; he's likely to raise his responses separately as we have slightly different views, which might aid in reasoning this out :)

waiting time handling: break falls on time where driver waits for job's time window. Need to think about potential use cases and related problems here, e.g. do we count waiting time as break time?..

I would personally consider this as nice-to-have (it totally makes sense, but I fear it could be a rabbit hole in implementation?). You have a cost-per-time parameter but is there a way to selectively penalise waiting time above and beyond regular working hours? That was the solution in jsprit and it gave a new degree of freedom to sacrifice mileage efficiency for more-sensible solutions.

other non-driving time handling, e.g. serving, reloading, etc.

I would need a bit more time to look at "reloading, etc." here in your implementation. Serving time I think definitely needs to be taken into account. If the driver needs to clock off at 12:00, we can't start a job at 11:59 that takes 45 minutes.

departure rescheduling: this functionality reschedules departure to reduce waiting time and it might push the break to the future in case of the second break time type. This is an implementation challenge, the simple solution would be just to disable the feature in case of such break (don't like this approach and will try to avoid it)

I completely agree with this. The variable departure time would be awesome, but for me it comes lower in the hierarchy of what is needed. I think the approach needs to obey the break insofar-as is possible and we can try clean things up in post-processing. Even with rigid start times, this is so much easier if the insertion criteria has some view of there needing to be dead time somewhere in the heuristic.

solution representation: if break falls in the middle of the travel, how we represent it in the tour? I'm thinking about adding an extra stop with break activity between two stops, but location has to be specified for it. Probably I can just use location from previous or next stop.

This is the one I'm most interested in clarification on. This is purely outside of the solution iterations and just for representation purposes on the final result? If it's for representation in the schedule, then it should be possible to have some default location id that is based on your library rather than anything specified in the problem setup? "Location 0" if you will. If you're referring to the iterations themselves, then it seems we're back at square one if we're inserting some kind of location object into the route. This was the most contentious point in my debate with my colleague so I'll wait for clarification on whether this is a "superficial" representation rather than something driving the optimiser.

it won't cover scenarios like "shouldn't drive more than two hours without some break", my understanding that the need is more about total working time. Theoretically, just adding an extra duration to such route legs as preprocessing step and do postprocessing to expand it in the solution can be an alternative solution.

Another nice-to-have. As long as the presence of the break is stable and reliable (i.e. it can't be kicked out as a soft constraint), this can be covered in pre-/post-processing.

Josh

[reinterpretcat]

This is purely outside of the solution iterations and just for representation purposes on the final result?

Yes, this is for final representation only. Internally, the core logic doesn't use concept of stop. So, the most challenging part is to make duration of a travel and an activity dynamic. I've just done some internal api changes, need to experiment a bit with actual implementation and see whether it can be stabilized or I missed something.

[sbloor]

Firstly, really appreciate you engaging with us on this @reinterpretcat!

I found this really interesting as it's basically what I'd been hoping for all along:

Theoretically, just adding an extra duration to such route legs as preprocessing step and do postprocessing to expand it in the solution can be an alternative solution.

As in, we have a Required break at 1200 for 1 hour, so any activity (driving, servicing) that spans this time automatically gets an additional hour long inflation added to the duration.

We were rubber ducking this scenario a little last week and, as Josh alluded to, we're still not completely clear on whether this is going to be completely extensible to all activities, as when a loading/unloading event spans this time frame it will look a little strange!

• Driver turns up at 1158 for a job with a 30 minute service time
• Driver does 2 minutes of loading, an hour break, 28 more minutes of loading

As service time is not 'drive time' (i.e. a tachometer would determine the vehicle as being stationary), this is still equivalent to accumulating 90 minutes of idle time, so perhaps the hands-off solution would be to keep it in this way and leave it to the driver's discretion...

So the final solution wouldn't be represented by:

11:58 - 12:00 loading time
12:00 - 13:00 break
13:00 - 13:28 loading time

but

11:58 - 13:28 loading time (1 hour break included)

which extends to drive time, etc. I guess this could be represented in a similar way to waiting time in the solution output?

Yes, this is for final representation only. Internally, the core logic doesn't use concept of stop. So, the most challenging part is to make duration of a travel and an activity dynamic. I've just done some internal api changes, need to experiment a bit with actual implementation and see whether it can be stabilized or I missed something.

This sounds really promising. Excited to see what you come up with!

[reinterpretcat]

So the final solution wouldn't be represented by:

To be honest, the plan is to keep such solutions possible:

• the solver doesn't know what kind of threshold makes sense for user
• when all durations are correct, it can be modified as post-processing steps on user side

This sounds really promising. Excited to see what you come up with!

At the moment, the main implementation problem is how to adjust internal caching logic which speed ups job insertion analysis:

https://github.com/reinterpretcat/vrp/blob/master/vrp-core/src/construction/constraints/transport.rs#L149-L166

Here, LATEST_ARRIVAL_KEY state is used to find the latest arrival time at next activity when analyzing a new job insertion:

https://github.com/reinterpretcat/vrp/blob/master/vrp-core/src/construction/constraints/transport.rs#L252

If it is solved, I would be pretty confident on the whole feature implementation.

[jpilkingtonpeak]

This is great, thanks! I'm trying to get resource on our end to properly wrap this so there'll be a lull on my end for a week or so too. l've got at least one person that wants to put their "initiative time" into forwarding this but it'll take a little bit of time to shuffle things round sorry

[reinterpretcat]

Hi, just decided to wrap up functionality I've built so far in the latest release: https://github.com/reinterpretcat/vrp/releases/tag/v1.16.0

It is experimental and has issues, but maybe good enough for some VRP variants. I've updated example here: https://reinterpretcat.github.io/vrp/examples/pragmatic/basics/break.html#required-break-experimental

[jpilkingtonpeak]

Hi, thanks for the update and sorry for the lack of responses recently. We've wrapped your VRP-CLI in a HTTP server and begun interfacing it with our Python entry point to our vehicle routing stack (it won't be a pyo3 interface because each solver in our stack is launched as a separate service). While the JSON bindings on our side are finalised there so we can start full testing, would you be interested in a PR for the server itself?

[reinterpretcat]

Hi, thanks for details! I think the server logic is out of scope as there are multiple ways to expose it. I even "sketched" one just for fun: https://github.com/reinterpretcat/vrp-experiments/tree/master/serverless-aws

[jpilkingtonpeak]

No worries, and I completely understand :) I will get back to you when we've got the API fully integrated our side and we can start playing with the new features properly!