Max. work time of a driver

[ciblinek]

Hello,

according the law it is possible work just limited amount of time and after that time must be a break. According to Czech (I guess also EU) law is possible work max. 4,5 hours in a row and after that must be 45 min in a row break. In the real life is possible use 45 min like a break during waiting period before customer open. Here is an example: Driver starts at 5 am that means that break must be at the latest at 9:30 am but when arrives at 8 to customer who open at 8:45 these 45 min could be possible use as a break and it is not necessary put next 45 min at 9:30 am. It is also possible split break to 15 + 30 min so if starts at 5 am and waiting time 1 is 15min and waiting time 2 is 30min there is not necessary put next break at 9:30.

It would be nice if this constrains could be part of JSPRIT solution. I hope that I explained it well if not please ask.

Thank you Jan

[PGWelch]

I'm not that familiar with jsprit but could you solve some of these constraints by treating a break as an artificial stop with zero travel distance to everywhere? You'd give it a time window to ensure it happened around roughly 4.5 hours and set-up a capacity constraint so you only have one per vehicle? 

Sent from Samsung Mobile

-------- Original message -------- From: ciblinek [email protected] Date:
To: jsprit/jsprit [email protected] Subject: [jsprit] Max. work time of a driver (#99)

Hello,

according the law it is possible work just limited amount of time and after that time must be a break. According to Czech (I guess also EU) law is possible work max. 4,5 hours in a row and after that must be 45 min in a row break. In the real life is possible use 45 min like a break during waiting period before customer open. Here is an example: Driver starts at 5 am that means that break must be at the latest at 9:30 am but when arrives at 8 to customer who open at 8:45 these 45 min could be possible use as a break and it is not necessary put next 45 min at 9:30 am. It is also possible split break to 15 + 30 min so if starts at 5 am and waiting time 1 is 15min and waiting time 2 is 30min there is not necessary put next break at 9:30.

It would be nice if this constrains could be part of JSPRIT solution. I hope that I explained it well if not please ask.

Thank you Jan

— Reply to this email directly or view it on GitHub.

[ciblinek]

It could be possible but disadvantage of this solution is that this will be apply always regardless of you have been waiting during previous stops or not.

Jan

[jsprit]

Seems to be a rather important feature.

I found the following publication: Kok, A. L.; Meyer, C. M.; Kopfer, H.; Schutten, J. M. J. (2010). A dynamic programming heuristic for the vehicle routing problem with time windows and European Community social legislation. Transportation science : the publication of the Transportation Science Section, Operation Research Society of America..

and a reference to a working copy of it: http://www.sfb637.uni-bremen.de/pubdb/repository/SFB637-B9-10-002-TR.pdf

This paper not only provides a very detailled overview on EU regulation but also suggests a solution to consider these regulations in a routing algorithm which seems to be also viable for jsprit (this is at least my first impression after running down the paper).

@PGWelch I understand the idea with the artificial stop which seems to be easy to implement. But I did not yet entirely understand what you mean with the capacity constraint. Could you explain it again? I tend to aggree with Jan, one probably looses optimization potential if breaks are scheduled that static. But still, it might be a first-and-fast-to-implement-solution.

[jsprit]

I added this milestone: BREAKS

[PGWelch]

If you did a quick-and-dirty 'artificial stop' solution, you need to ensure all break stops aren't loaded onto the same vehicle - hence you could set up a capacity constraint that each vehicle can have only one break, where number of breaks is another capacity dimension. 

I'm sure as you say, optimisation potential would be lost, but it may still be a 'good enough' solution for some circumstances. 

Presumably jsprit would still need a minor change for this to work as if an artificial break stop had zero travel distance to everywhere, then  you'd travel from the stop before the break, to the break, and then to the stop after without incurring any travel distance...

Best regards,  Phil

Sent from Samsung Mobile

-------- Original message -------- From: jsprit [email protected] Date:
To: jsprit/jsprit [email protected] Cc: PGWelch [email protected] Subject: Re: [jsprit] Max. work time of a driver (#99)

Seems to be a rather important feature.

I found the following publication: Kok, A. L.; Meyer, C. M.; Kopfer, H.; Schutten, J. M. J. (2010). A dynamic programming heuristic for the vehicle routing problem with time windows and European Community social legislation. Transportation science : the publication of the Transportation Science Section, Operation Research Society of America..

and a reference to a working copy of it: http://www.sfb637.uni-bremen.de/pubdb/repository/SFB637-B9-10-002-TR.pdf

This paper not only provides a very detailled overview about EU regulation but also suggests a solution to consider these regulations in a routing algorithm which seems to be also viable for jsprit (this is at least my first impression after running down the paper).

@PGWelch I understand the idea with the artificial stop which seems to be easy to implement. But I did not yet entirely understand what you mean with the capacity constraint. Could you explain it again? I tend to aggree with Jan, one probably looses optimization potential if breaks are scheduled that static. But still, it might be a first-and-fast-to-implement-solution.

— Reply to this email directly or view it on GitHub.

[pierredavidbelanger]

@PGWelch I like this approche! I will try this when I face the problem.

[jsprit]

@PGWelch Ahh, now I understand. Thanks a lot. I also like and will try it. Zero distance to everywhere is no problem. Give breaks a locationId, e.g. 'breakLocation' and extend AbstractForwardVehicleRoutingTransportCosts. Here you can specify what should happen when fromLoc or toLoc is a breakLocation.

[DFuster]

is an excellent choice to define breack in the route , but Could you give an example of how to use AbstractForwardVehicleRoutingTransportCosts, only one for route (infinite vehicles and service with time windows) , in our case is to check if the travel time is less than 4.5 hours do not need it, if the travel time is greater need lunch in a time range between 1 and 3 or if longer route also requires a dinner with 7 to 9

Thank you Dante

[jsprit]

@DFuster: This is basically what @ciblinek suggests and requests from jsprit. I ll give you an example once I implemented it (which can take some time since jsprit's task/request list is getting longer and longer which is great on the one hand, but rather time-consuming on the other). The comment on extending AbstractForwardVehicleRoutingTransportCosts referred to what @PGWelch proposed and on how to handle zero distances. When extending it, you need to implement two methods .getTransportTimes(from,to,...) and .getTransportCosts(from,to,...). Here you can specify what happens when the algorithm requests for example transportTimes from 'fromLocation' to 'breakLocation'. If you want it to be zero, let the method return zero.

[jsprit]

Look at https://github.com/jsprit/playground/wiki. It is not yet break-scheduling, but it is a first step towards operationalizing the driver (currently, a vehicle is sort of autonomous equipped only with a mock driver). With this you can optimize the departure time at the driver's depot and also consider maximum driver operation time (without considering breaks).

[DFuster]

I have problems with

• UpdateDepartureTimeAndPracticalTimeWindows
• TimeWindowConstraintWithDriverTime
• DepartureTimeReScheduler
• StateIds

from https://github.com/jsprit/playground/wiki. with the version jsprit 1.4, dont exist StateFactory public and StateManager.CreateStateId show error. is possible modify the code for add break.Scheduling time for lounch?

thanks

Dante Fuster

[jsprit]

Please read https://github.com/jsprit/jsprit/blob/master/CHANGELOG.md to change from 1.3.1 to 1.4. There is also a reference to an example that should make it even easier to make the necessary changes. If you do not use Maven, please read this to migrate to 1.4: https://groups.google.com/forum/#!topic/jsprit-mailing-list/Esh0xrPXnUQ

BTW: these files should illustrate how you can implement your own driver constraints. they were meant experimental and thus they are not maintained anymore. However, you are going to get these functionality out of the box with the next release (I am just working at including it).

[DFuster]

HI Ok, Realize the necessary changes and it's running properly, the link you gave me was very clear to modify the code, thanks

[renanmzmendes]

Doing a quick search I couldn't find if breaks are supported by jsprit's current version. Has there been a pull request to solve this?

[oblonski]

No, jsprit does not support breaks. It is on my ever growing to-implement-list.

Am 23.02.2015 um 22:43 schrieb renanmzmendes [email protected]:

Doing a quick search I couldn't find if breaks are supported by jsprit's current version. Has there been a pull request to solve this?

— Reply to this email directly or view it on GitHub.

[Rzpeg]

@oblonski This is really important due to EU Regulations. Relates to #211