multiple breaks for vehicles

[Lodyman]

Hi there!

Just like spoken in the graphhopper-forums i post here an issue for the feature "multiple breaks". This could help people plan routes for multiple days/weeks/months, what is just what I and also may other people need :)

Thanks

Patrick

[oblonski]

Would you need an AND or OR connection between multiple breaks. When it comes to multiple time windows, it is an OR connection, e.g. either time window A or time window B.

[Lodyman]

Hi!

In my problem I would need an AND connection between the breaks. I would use this in the following context:

Every break is an timewindow that the vehicle dont need to work. I want to plan tours for a long time (week, month, maybe year...) and i get some information about initial routes and about vacation. Normaly vehicles shouldnt work at sunday so i would give this vehicles a 8h(or working time) break. Some could work saturday, some could work a half day and so on. If someone has vacation, i´ll give him also a break so he will not be planed this day.

I thought about making this problem to another. I had an idea that i would make some "dummy" services that represent the "break" and give the vehicle and the service an unique skill so that i have to say "sorry little algorithm, only vehicle2 can make at this day the service2 because the service requires skill "break_mrBean1" and this skill has only vehicle2."

But multiple breaks with and AND connection would be a little bit better :)

[Simbu1988]

Hi, We have a application similar to SolomonWithSkillsExample and i am trying to leverage this example to use in my application. 1 . Is it possible to add multiple breaks for a vehicle in SolomonWithSkillsExample?

2. I was able to add only one break to the vehicles defined in SolomonWithSkillsExample. The results looks like the break was assigned to only one of the vehicle in the example not for all the vehicles in that example even though i am assigning breaks for all the vehicles.

What could be the reason for this?

Attaching the results of that example with the breaks defined.but the break was assigned to only one of the vehicle -skill1_vehicle_2

solomon_with_skills - Copy.txt

[oblonski]

@Simbu1988 How did you define your breaks?

[Simbu1988]

This is how i define my breaks. SolomonReader:

Break sBreak = Break.Builder.newInstance("Lunch") .setTimeWindow(TimeWindow.newInstance(200, 200)).setServiceTime(20).build(); VehicleImpl vehicle = VehicleImpl.Builder.newInstance("solomonVehicle").setEarliestStart(start).setLatestArrival(end) .setStartLocation(Location.Builder.newInstance().setId(customerId) .setCoordinate(coord).build()).setType(vehicleType).setBreak(sBreak).build(); vrpBuilder.addVehicle(vehicle);

SolomonWithSkillsExample:

VehicleImpl skill1Vehicle = VehicleImpl.Builder.newInstance("skill1_vehicle_" + i).addSkill("skill1") .setStartLocation(Location.Builder.newInstance().setId(solomonVehicle.getStartLocation().getId()).setCoordinate(solomonVehicle.getStartLocation().getCoordinate()).build()) .setEarliestStart(solomonVehicle.getEarliestDeparture()) .setBreak(solomonVehicle.getBreak()) .setType(newType).build(); VehicleImpl skill2Vehicle = VehicleImpl.Builder.newInstance("skill2_vehicle_" + i).addSkill("skill2") .setStartLocation(Location.Builder.newInstance().setId(solomonVehicle.getStartLocation().getId()) .setCoordinate(solomonVehicle.getStartLocation().getCoordinate()).build()) .setEarliestStart(solomonVehicle.getEarliestDeparture()) .setBreak(solomonVehicle.getBreak()) .setType(newType).build(); skillProblemBuilder.addVehicle(skill1Vehicle).addVehicle(skill2Vehicle);

[oblonski]

hmm. try to assign unique break objects to your vehicles such as "skill1VehicleBreak", "skill2VehicleBreak". probably you just defined one break object and assigned it to several vehicles, however each vehicle requires its own break object.

we should make the problem builder throw an exception in case a single break object is assigned to several vehicles.

[Simbu1988]

It worked after creating a unique break object.However in the same example , without any breaks all the jobs are assigned to a vehicle.but after adding the breaks to all the vehicle 1 job was unassigned. why does this happening so?

I have a another question also. In our application we define multiple breaks for a vehicle.How to add those?

[oblonski]

Maybe your time constraints are too tight (operation time of driver) ?

Multiple breaks are not possible yet (see discussion above).

BTW: Would you mind to ask latter kind of question in the forum? Great. Thanks.

[t0r0id]

Hi, I'm trying to solve a problem with AND conditions between multiple breaks for vehicle, is there a way to implement such constraint yet?

[61508060]

Hi, we need this feature as well to model multiple day vehicle routing in which each vehicle has different (multiple) break times during the whole time horizon for rest, maintenance, etc.

Really appreciate it.

[stefan--]

Any chance that this feature Driving time dependent break scheduling - beta release will be available in jsprit?

[seriouscoderone]

We need multiple breaks per vehicle as well.

If it is difficult to program for multiple breaks, would it be easier if you could use a Service with no Location? Does that make sense? @oblonski

[peterdn1]

could use a Service with no Location I think this should work when optimizing for single vehicle. When working with multiple vehicles add skill for both service and vehicle unique for each worker. For each break create a service that reflects the time windows in which a break can occur. Set break service as high priority. When the distance matrix is produced add 0 travel times for each break to each non break location.

Let Jsprit optimize this, then remove the no location breaks from the routing request, after the routing request returns add the breaks back and adjust the arrival time to the places where the breaks were inserted in the optimized solution. Any thought on this approach before I give it a try?

[mikeppp]

As per the comment above, we are doing the following and it seems to be working:

a. Create a skill for each vehicle called "break" b. Each break would be a service with an empty location (0,0) and a required skill of break c. In the matrix, i.e. whatever extends AbstractForwardVehicleRoutingTransportCosts implements TransportDistance; just return 0 in getDistance, getTransportCost, and getTransportTime when one of the locations is your break service d. If the break is fixed such as lunch give it a high priority e. 2 other floating breaks one in the am one in the pm f. The solution produced looks good actually and seems to make sense g. When submitting to the router, remove the dummy services and just add the break time to the stopover time

here is an example solution result with the above breaks:

+--------------------------------------------------------------------------------------------------------------------------------+ | detailed solution | +---------+----------------------+-----------------------+-----------------+-----------------+-----------------+-----------------+ | route | vehicle | activity | job | arrTime | endTime | costs | +---------+----------------------+-----------------------+-----------------+-----------------+-----------------+-----------------+ | 1 | 56 | start | - | undef | 0 | 0 | | 1 | 56 | service | 255918 | 21 | 41 | 21 | | 1 | 56 | service | 255924 | 45 | 65 | 25 | | 1 | 56 | service | break:56:floating_am | 65 | 80 | 25 | | 1 | 56 | service | 255937 | 80 | 100 | 25 | | 1 | 56 | service | 255936 | 101 | 121 | 26 | | 1 | 56 | service | 255929 | 124 | 144 | 29 | | 1 | 56 | service | 255921 | 155 | 175 | 40 | | 1 | 56 | service | 255837 | 178 | 198 | 43 | | 1 | 56 | service | 255926 | 200 | 220 | 45 | | 1 | 56 | service | 255932 | 224 | 244 | 49 | | 1 | 56 | service | 255834 | 250 | 270 | 55 | | 1 | 56 | service | break:56:lunch | 270 | 300 | 55 | | 1 | 56 | service | 255831 | 300 | 320 | 55 | | 1 | 56 | service | 255946 | 352 | 372 | 87 | | 1 | 56 | service | 255943 | 372 | 392 | 87 | | 1 | 56 | service | break:56:floating_pm | 392 | 407 | 87 | | 1 | 56 | service | 255803 | 407 | 427 | 87 | | 1 | 56 | end | - | 455 | undef | 115 | +--------------------------------------------------------------------------------------------------------------------------------+

Again once the breaks are removed and the it is routed, the gpx produced is valid and reasonable!

[PGWelch]

Doesn't this mean you can teleport between locations by going via a break? I suspect this would distort routes in the optimiser.

[mikeppp]

Yes that is correct actually. However until jsprit supports more than one break its the best solution...

[mikeppp]

Also in our case distances are fairly all close together and time windows are not that long. our HARD requirements are: a. floating break am; b. fixed lunch; c. floating pm break

If anyone has a better solution please ket me know!

[peterdn1]

PGWelch -agree.

What if costing function added an additional argument that was the previous service.
So 3 services A- service B- break C -service The time from the A to B would be 0 The time from B to C would time from A to C

I think this would address your observation of teleportation using breaks, but unfortunately would involve changing core. Any other suggestions?

[CalebRoyer]

This is huge for us. +1

If you only needed to route for one vehicle, would it be possible to string along "fictional" vehicles to pick up where the previous vehicle left off, as a temporary hack?

[LCenteleghe]

Has anyone found a solution for this?

[lukes]

+1 We would like to be able to define multiple breaks for a vehicle. This fulfils New Zealand employment law, where a 9-hour shift legally needs to have two 15 minute breaks and one 30 minute break.

[jmartin127]

+1 This would be a very beneficial feature. The "teleportation" issue mentioned above, makes the suggested solution of using services as breaks non-viable for us.

[bolodecenouracomcafe]

I'm interested in developing this feature. Anyone interested in discussing the implementation of the solution?

[grantm009]

Hi @emersonl91

Did you make any progress with this ?

[PGWelch]

If it helps, I can share some information about how we implemented multiple breaks. We did this in ODL Live which started off as jsprit plus extra stuff mostly focused on realtime/dynamic route optimisation. ODL Live doesn't use any jsprit code now but at the time we implemented multiple breaks, it still used a significant proportion of jsprit code.

If I recall correctly, the current jsprit breaks implementation has an issue in that when a break is inserted, a coordinate is assigned to it (I.e. probably the previous / next stop coordinate). This increases the complexity of implementing multiple breaks, as you need to manage assigning coordinates to multiple breaks in a row when breaks are consecutive in a route. It also effects solution quality when you evaluate a new job insert, as an insert next to a break could be evaluated as infeasible or costly due to the fixed coordinate of the break, whereas in-reality the break coordinate could actually be changed to match the coordinate of the new insert job and the insert would be feasible. (I believe jsprit does optimise break assigned coordinate and position after an insert has been done, but not during the insertion evaluation, so it could miss good inserts). I'm also guessing this problem would be worse with multiple breaks.

Anyway, because of these issues we replaced jsprit breaks with our own implementation instead. In our implementation breaks aren't assigned a coordinate internally to the optimisation. Instead calculations related to travel are always calculated with the preceding stop, any number of breaks in-between and the next stop available together, so we can evaluate the impact of breaks knowing the coordinates both before and after the breaks, and without locking the breaks themselves down to a fixed coordinate. As we didn't want to repeat this logic, we also had to ensure all travel calculations were done centrally with the same bit of code. (I can’t really say any more publicly about how the implementation works but feel free to PM me).

This methodology does involve replacing substantial amounts of jsprit, so isn't quick to implement, but the end result is that it has no problems supporting multiple breaks, no teleporting issues and no impact on the reliability of the insertion heuristic.

[Rzpeg]

@PGWelch Given that you no longer use the jsprit in ODL, could you maybe opensource the solution for jsprit?

[Rzpeg]

@oblonski Hey. This is a really needed feature due to new EU regulations. Is there any progress on the feature?

[grantm009]

Hi folks This critical element still seems to be not getting any attention. It will render JSprit irrelevant in the near future if it can't handle multiple breaks. What can we do to move this along? What can I do to move this along?

[bolodecenouracomcafe]

Hi guys, sorry for the delay. I had no further progress because I changed employer and now I do not work with routing, but I am interested in helping with implementation. I did several tests, but I had difficulty understanding some concepts, especially in the VehicleDependentTimeWindowConstraints file. What do you think about creating a slack channel to strengthen communication?

[grantm009]

Hi @emersonl91

Lets go ahead and create that slack channel (whatever that is 👍 )

Im very keen to see this implemented as Im sure others are as well.

regards Grant

[joaoplay]

Hi everyone,

I already tried to implement the rest periods as stated in the EU regulations. Unfortunately, I didn't reach a 100% working solution. In some cases, the constraints got broken after the ruin process. Though I'm currently working on a different area, I'm still interested on a fully working solution for this problem.

Glad to know that the comunnity is considering creating a Slack channel to discuss this topic. You can count on me as well.

[grantm009]

When I clicked on the invite it said it was no longer active. Perhaps it is per person

[grantm009]

Hi @emersonl91

The channel link on slack does not work. Can you please create a new link

[andreylh]

@grantm009 Sorry, emersonl91 is no longer working in our company, so I believe that the channel on slack is dead.

[marcioaguiar]

@emersonl91 I see that you are working on this feature and that there's work still not commited to your fork: https://discuss.graphhopper.com/t/multiple-breaks-for-vehicles-feature-211/4213

Is there any way I can help? I don't have the much experience on jsprit source code, but I'm willing to learn and make tests.

[oblonski]

Modelling multiple breaks should now be possible with the latest master. It allows you to add an arbitrary number of services without locations which can represent breaks. However, the changes might break your code, i.e. you might need to adjust your own custom constraints as it was done here for example: https://github.com/graphhopper/jsprit/pull/491/commits/3b02e27c1a04effbae66e48dc38e0b9916c0b6d4

Here is an example: https://github.com/graphhopper/jsprit/blob/master/jsprit-examples/src/main/java/com/graphhopper/jsprit/examples/SimpleWithoutLocationExample2.java

Please let me know if you see things that can be improved immediately.

BTW: https://github.com/graphhopper/jsprit/releases/tag/v1.8 is the latest release before "Activities without location". It is already available on Maven Central.

[grantm009]

Hi @oblonski

This sounds great. I will finish my current task in a few days and will build this into a test version of our application. But is sounds exactly what we (and others) need.

Thanks for taking the time to do this. I trust you are safe and well in this challenging time. regards Grant

[nitinFareye1]

@grantm009 were you able to get correct solution for this?

[eltonramos]

@mikeppp Could you post a working example?