Driver break discussion about vrp HOT 15 CLOSED

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)

from vrp.

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.

from vrp.

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?

from vrp.

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?

from vrp.

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

from vrp.

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.

from vrp.

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?

from vrp.

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.

from vrp.

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.

from vrp.

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.

from vrp.

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

from vrp.

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

from vrp.

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

from vrp.

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

from vrp.

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

from vrp.