Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

multiple breaks for vehicles #211

Open
Lodyman opened this issue Jan 26, 2016 · 25 comments

Comments

Projects
None yet
@Lodyman
Copy link

commented Jan 26, 2016

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 oblonski added the feature label Jan 29, 2016

@oblonski

This comment has been minimized.

Copy link
Member

commented Jan 29, 2016

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

This comment has been minimized.

Copy link
Author

commented Jan 29, 2016

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

This comment has been minimized.

Copy link

commented Feb 1, 2016

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

This comment has been minimized.

Copy link
Member

commented Feb 2, 2016

@Simbu1988 How did you define your breaks?

@Simbu1988

This comment has been minimized.

Copy link

commented Feb 2, 2016

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

This comment has been minimized.

Copy link
Member

commented Feb 2, 2016

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

This comment has been minimized.

Copy link

commented Feb 2, 2016

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

This comment has been minimized.

Copy link
Member

commented Feb 2, 2016

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.

@oblonski oblonski referenced this issue Feb 3, 2016

Closed

driver breaks #170

@optimaster69

This comment has been minimized.

Copy link

commented Jun 8, 2016

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

This comment has been minimized.

Copy link

commented Aug 10, 2016

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

This comment has been minimized.

Copy link

commented Jan 3, 2017

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

@seriouscoderone

This comment has been minimized.

Copy link

commented Sep 22, 2017

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

This comment has been minimized.

Copy link

commented Oct 13, 2017

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

This comment has been minimized.

Copy link

commented Oct 13, 2017

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

This comment has been minimized.

Copy link
Contributor

commented Oct 13, 2017

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

@mikeppp

This comment has been minimized.

Copy link

commented Oct 13, 2017

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

@mikeppp

This comment has been minimized.

Copy link

commented Oct 13, 2017

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

This comment has been minimized.

Copy link

commented Oct 13, 2017

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 comment has been minimized.

Copy link

commented Nov 9, 2017

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

This comment has been minimized.

Copy link

commented Feb 23, 2018

Has anyone found a solution for this?

@lukes

This comment has been minimized.

Copy link

commented Aug 22, 2018

+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

This comment has been minimized.

Copy link

commented Jan 7, 2019

+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.

@emersonl91

This comment has been minimized.

Copy link

commented Mar 13, 2019

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

@grantm009

This comment has been minimized.

Copy link

commented Jun 20, 2019

Hi @emersonl91

Did you make any progress with this ?

@PGWelch

This comment has been minimized.

Copy link
Contributor

commented Jun 20, 2019

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.