Driver breaks: Is there best practice? + My proposed solution.

[j.pi...@gmail.com]

Hello,

 

I note that the discussion about driver breaks fizzled out (https://github.com/jsprit/jsprit/issues/99) but I find it hard to believe that people are not encountering this all the time. As such, is there an established work-around that is best practice or do people know what has the most success? I'll list the problems I'm having and my proposed approach.

 

I define the break as a job that is equidistant to all other locations and is of a unique package type that each vehicle can only hold one of, with set delivery times. Note: Defining near-zero distance/time to this location causes drivers to actively use the break as a wormhole. From this point on it's fire fighting with multiple drivers.

 

If I define my whole fleet, I need to define an equal number of break objects. Thus, my entire fleet is deployed even if the optimal solution is not to use all vehicles. This causes some drivers to only work up to the point of their break, and stop, whilst other drivers sit around waiting for their break to happen and then start deliveries after their break. I tried making it extremely expensive to return to the warehouse from the break location to try prompt the necessary vehicles to stay deployed. However, since they're all already deployed, this penalty goes across the board, keeping them all deployed. I can't think how to put hard constraints in here because there may be times that similar behaviour to this is actually required as a solution. We have varying delivery time windows, so it's possible I need to deploy more vehicles in the afternoon.

 

I don't want to go down the route of adding hard constraints to create two working time windows either. Our drivers are given a window in which to take their break, so it makes sense to maintain this flexibility.

 

What I am thinking:

Iteratively make new break locations between 1 and total fleet size . Each new break location is further away from all locations (except the warehouse) than the previous one, making it drastically more expensive for each new driver to do anything other than return to the warehouse. Does this seem viable? I imagine that to secure success, these distances need to scale rapidly for each new object and be on a different magnitude than real delivery distances. Might this have implications on the algorithm's ability to solve the problem? Might it just stop assigning break objects? Any implications I might not have thought about?

 

The next problem is different vehicle types with different running costs (the fleet is homogeneous atm thankfully). I either make a single break object type that can be juggled around the whole fleet (requiring lots of iterations to find a global optimum) or new break object types for each type of vehicle. Undecided, but I think it would need to be different types.

 

I have problems of different shifts etc. to deal with on top, plus getting real route statistics back from this mess, so I'd just like some assurance that what I am doing is viable and logical before I get stuck in J

 

Thanks.

[in...@opendoorlogistics.com]

How about creating a break stop at every location in the problem, for every vehicle  (so nlocations x nvehicles), still with the constraint that a vehicle can only hold one of them? This wouldn't solve all the problems but would at least stop problems with distances / wormholes.

Philip Welch

Open Door Logistics Limited

Specialists in open source solutions for transport logistics.

Email: in...@opendoorlogistics.com

Linkedin:  http://uk.linkedin.com/in/welchphilip

Skype: opendoorlogistics

Tel:  +44 (0) 20 8144 4009

Website:  http://www.opendoorlogistics.com

---- On Wed, 22 Jul 2015 18:18:30 +0100 j.pi...@gmail.com wrote ----

--
You received this message because you are subscribed to the Google Groups "jsprit-mailing-list" group.
To unsubscribe from this group and stop receiving emails from it, send an email to jsprit-mailing-...@googlegroups.com.
To post to this group, send email to jsprit-ma...@googlegroups.com.
Visit this group at http://groups.google.com/group/jsprit-mailing-list.
For more options, visit https://groups.google.com/d/optout.

[in...@opendoorlogistics.com]

...Ensuring you create them at the depot as well - so an empty route doesn't move anywhere.

The solver would be nvehicles slower i believe  - i.e. slower but probably still manageable. You probably need to turn regret off though.

Philip Welch

Open Door Logistics Limited

Specialists in open source solutions for transport logistics.

Email: in...@opendoorlogistics.com

Linkedin:  http://uk.linkedin.com/in/welchphilip

Skype: opendoorlogistics

Tel:  +44 (0) 20 8144 4009

Website:  http://www.opendoorlogistics.com

---- On Wed, 22 Jul 2015 18:18:30 +0100 j.pi...@gmail.com wrote ----

--

[j.pi...@gmail.com]

Hi Philip,

Thanks for the suggestions. The wormholes are actually rather easy to solve (at least from the bits I tested). I use a real road matrix, so all distances/times are explicitly defined. All I then have to do is say that it is an unreasonable distance to the single break location (hundreds of miles each way) and it takes 0 time to get there, 15 minutes to get back from there. The 15 minutes is a temporary, hard-coded attempt to say that even though the break location is in another dimension, to driver still needs time to get from wherever they are to the next job. Now it slots nicely into cost minimisation. I then just need to subtract the miles back out of the cost calculation when I want the statistics. I saw something similar to zero distance/time suggested somewhere, so I really just mentioned it to clarify that it has to have real, BIG, values in the cost calculation.

My concerns are really about my proposed solution. Intuitively, I feel that having exponentially growing costs to get to each new break location that is added (which is in an attempt to still arrive at the minimal number of drivers for a solution) will have some impact on the solution. I feel it, but I cannot think of evidence for it. Something about the ruin and recreate side make me think that gigantic costs for a break location completely skew the solution.

Josh  

[j.pi...@gmail.com]

Quick clarification that popped into my mind:

I realise that by defining my whole vehicle fleet as "x" that I also need to define x number of breaks. This will always deploy my entire fleet, even if it isn't needed. What I am trying to do with exponentially-more-expensive breaks is to push all deliveries to the minimum no. drivers. The idea then is to find the drivers that do: leave warehouse --> break location --> warehouse and just delete their route from my solution before it comes out of my script. I just want to create an un-level playing field in my fleet that forces the solution back down to the minimum number of drivers. My concern in my previous message still stands. 

On Wednesday, 22 July 2015 18:18:31 UTC+1, j.pi...@gmail.com wrote:

[j.pi...@gmail.com]

Hi Philip,

Would you mind elaborating on your idea a bit more please? I understand partially – it would allow the algorithm access to a real distance/time matrix. However, I'd be left with bigger problems I think. Now I say each driver has 1 object that could be delivered to n locations, but only 1 of them. This object has to carry a "service time" of the break duration. The location that it actually delivers to has to be one that is serviced within a specified time window (lunch break window), and the identity of the actual location is dynamic based on each iteration of the route. I can't get my head around the implementation, have I misunderstood?

I see now that my solution to the wormhole problem is only partially complete. As long as you make the break more expensive than any actual route (bump up the miles to compensate for zero time), it is never preferable to arrange the route such that the lunch break bridges the most expensive route between two real locations (... I think). That's fine, it just obeys the time window and doesn't affect any other journey. But my hard-coded 15 minutes sends everything out of whack. I thought I could do this dynamically but my solution is cosmetic: I could only correct the times in the solution print out. Meanwhile, the algorithm is internally unaware that it could be breaking delivery time windows all over the place because it's still under the assumption of 15 minutes.

To take my idea forward, I'm thinking of a hard constraint but I don't know if it's possible. That is to say that if the current location is an instance of a "break", the driving time to the next location is equal to (next location – previous location) from the cost matrix. Might something like that be possible i.e. overriding the cost matrix or defining this section of the cost matrix dynamically?

At first I couldn't understand why this wasn't a feature. Now I see that the practical implementation is horrible!

Regards,

Josh

On Wednesday, 22 July 2015 18:18:31 UTC+1, j.pi...@gmail.com wrote:

[in...@opendoorlogistics.com]

Hi Josh,

Basically you'd create a 'break-stop' for every location, for every vehicle (so a location A has break-stops bs-locationA-vehicle1, bs-locationA-vehicle2, bs-locationA-vehicle3, etc...), but only allow a vehicle to load one break-stop. If you serviced stop A around the middle of the day, when you need to take a break, then the optimal solution would use the break-stop with the same location as stop A and place this before or after stop A (so there's no movement between the two). This is the kind of route you'd want.

The break-stops get time windows between 12:00 and 14:00 or similar.

This kind of technique means you could work with a normal distance matrix, with no worries about wormholes or otherwise screwing the distances up in some way. Distances and travel just work in a completely normal way.

For the alternative you suggest, I suspect the changes required to the code to skip a location in the distance matrix calculation so "the driving time to the next location is equal to (next location – previous location) from the cost matrix" could be significant, as this logic probably crops up in a few places (time windows, driving costs, clustered ruin heuristics etc...)

The optimiser probably also wouldn't be that much slower, as you'd only load nvehicles more stops at time and when you're trying to insert all the break-stops, you'd quickly hit the route-level constraint. On the downside, this kind of technique would drive the optimiser towards becoming stuck in local minima and so make it harder to optimise - it's really something that you've got to try and see how it performs.

Some of the problems you mentioned wouldn't go away with this technique - e.g. drivers taking their break as the very first or last stop. However for the optimal solution this would tend to be the break which is co-located with the depot, so in this case you would just completely ignore this break (ignore it as a post-processing stop, after you've got the solution out of jsprit).

Best regards

Phil

Philip Welch

Open Door Logistics Limited

Specialists in open source solutions for transport logistics.

Email: in...@opendoorlogistics.com

Linkedin:  http://uk.linkedin.com/in/welchphilip

Skype: opendoorlogistics

Tel:  +44 (0) 20 8144 4009

Website:  http://www.opendoorlogistics.com

---- On Thu, 23 Jul 2015 16:23:59 +0100 <j.pi...@gmail.com> wrote ----

--

[j.pi...@gmail.com]

Hi Philip,

 

Thank you so much for your detailed explanation, I love this idea even if it's bending my mind a bit! There's a lot of basic supporting code involved (kicking break stops out of the unassigned job list etc.) so it will take time for me to give proper feedback on this.

 

I think the implementation would have to be slightly different than you suggested. In much the same way as my initial idea, the whole fleet is now mobilised to deliver breaks. The "optimal" solution could then be very bizarre because if I had as many vehicles as total deliveries, each vehicle would carry one break and the corresponding actual delivery for which there is a zero distance/time penalty between them (disregarding time window constraints for the thought experiment). I've set it an impossible task to deliver all the breaks, but it seeks to deliver as many as possible. Crunching it down to more "actual" deliveries than vehicles, I imagine this could be a very undesirable type of clustering.

 

I think I could get away with just creating one set of break locations to mirror all real locations, but create one break location at the warehouse for each vehicle. Perhaps what I would need to do is *massively* inflate the distance from the warehouse (plus warehouse break) to every other location by a constant factor but keep the travel time the same. Otherwise, every vehicle is fair game to be assigned deliveries, which would result in lower man-hour costs. I have to mitigate this somehow, I've lost fixed costs as a limiter to the number of drivers.

 

I need to think more on this and then actually start testing bits out. Many thanks again with the base suggestion, I have a feeling it's a lot more solid than what I was planning. If you have any further thoughts going forward, I'd love to hear them. I'll be sure to report back once I have something more concrete.

 

Regards,

 

Josh

[in...@opendoorlogistics.com]

Use the depot-to-any-other-stop travel cost to simulate a fixed cost per vehicle? Cunning! I like it.

Best of luck - I look forward to hearing how well this works.

Philip Welch

Open Door Logistics Limited

Specialists in open source solutions for transport logistics.

Email: in...@opendoorlogistics.com

Linkedin:  http://uk.linkedin.com/in/welchphilip

Skype: opendoorlogistics

Tel:  +44 (0) 20 8144 4009

Website:  http://www.opendoorlogistics.com

---- On Thu, 23 Jul 2015 18:19:01 +0100 <j.pi...@gmail.com> wrote ----

[j.pi...@gmail.com]

Feedback: Jsprit can indeed be used to support driver breaks! :)

The end solution is an amalgamation of Philip's suggestion and my alterations. The most simple implementation, to summarise from the blocks of text above:

1) Define all of the deliveries to unique locations (e.g. 1, 2, 3..., n) with size index "0". 

2) Define a second set of deliveries at every location (1, 2, 3,...n again) with size index "1" and a unique ID number. The time window of these deliveries is the acceptable range of time to *start* taking a break e.g. 1-1:15pm. The service time of the break delivery is the duration of the break e.g. 45 minutes. 

3) maximumDriverFleetSize = x. Create x lunch breaks at the warehouse in the same manner as above. I called these "nullbreaks". 

4) All drivers can only carry 1 item of index "1"

5) In my example, location "0" is the warehouse. Modify the distance matrix such that the journey 0 --> anywhere and anywhere --> 0 is huge e.g. for mine it's realDistance+1500 km but the travel time is still the real value. I could use less distance, but I want to be sure that fuel costs always overwhelm any reduced man-hour cost by deploying everything. I can confirm my concern that without this step, it will tend to distribute orders across the whole fleet even if not all vehicles are necessary.

6) Keep the rest of the distance matrix the same.

7) Modify the "unassigned" job list such that if JobID > n, ignore it. Otherwise the unassigned job list is flooded with breaks. 

I think that's it. The driver will always pick the most suitable "break" location in their route. The purpose of the nullbreaks is to force all non-essential vehicles to remain stuck at the warehouse. Some form of post-processing is required to invalidate their route. However, they can still be called into action if they are needed at some point in the day. 

If you want to make different break times for different shifts, then you need to add a new size index, and repeat the procedure above.

Thanks again Phil, that was actually relatively painless but I'm not sure I would have seen it in the first place.

Regards,

Josh

[in...@opendoorlogistics.com]

That's really good - well done! Have you got any feel for how efficient the routes are? The only downside of the procedure is i suspect it will make the solver more likely to get stuck in local sub-optimal solutions. i.e. If you run the same problem ten times with ten different random number seeds what kind of variation in cost do you see?

Philip Welch

Open Door Logistics Limited

Specialists in open source solutions for transport logistics.

Email: in...@opendoorlogistics.com

Linkedin:  http://uk.linkedin.com/in/welchphilip

Skype: opendoorlogistics

Tel:  +44 (0) 20 8144 4009

Website:  http://www.opendoorlogistics.com

---- On Sun, 26 Jul 2015 17:32:59 +0100 j.pi...@gmail.com wrote ----

[j.pi...@gmail.com]

Team effort! :)

 

Sorry for the long email, I'll try and be as comprehensive as possible. 

 

Benchmarking is my next stop. The unfortunate thing is that I receive everything via a JSON string from our servers and it makes it hard to keep consistency. This means that a) my code is set to parse the data from a string b) the deliveries at any one time are (slightly) variable c) we're still working on booting locations out of the JSON string if graphhopper cannot find them (turns out it wasn't just me creating wormholes).

I'm really pushed to get the system up and running without faults at the moment so I am not going to have much time to get proper benchmarks set. I will say this; whilst breaks seem relatively insignificant in the optimisation problem, it was causing havoc with our routes, so it's a good feature to have. Customers are getting increasingly demanding on arrival time accuracy and precision; clients might start demanding this feature from ODL. We're seeing some +/- 30 minutes prediction demands (!), so reputationally this is a mine-field. 

 

I will try use some of ODL's fake data for consistent benchmarking – if I'm successful setting it up, I will mail you that full script. On the flip side, if you look into this more yourself, I'd really appreciate feedback.

Things I need to test:

1) Repeatability / local minima. I feel that ruin+recreate is much more resilient than standard sim. annealing in this dept. to make this a really minimal concern, but that's just gut feeling atm.

2) What happens if you add a break time window that is long enough to accommodate two breaks? If it's undesirable, how best to stop repeat breaks? Hard code actual priorities? If we hard-code, how does it interact with the hierarchy of priority for real services? 

3) Do multiple shifts behave properly/predictably through using different item size indexes?

 

There is something slightly odd going on:

Unless you're really pushing the driver to the limit, I have found cases where he will wait, say, 50 minutes for his break time to open up, then take the break. Meanwhile, he could have continued delivering more items (for example, the next destination after his break was valid at any point in the day and would only have taken ~15 mins to service).

 

It could be that it helps save costs somewhere down the line instead of waiting elsewhere for a window to open up. Too early to say, but I can say that in the instances he behaves this way, he does so consistently.

 

What I want to do:

I want more control over break locations as separate entities. Thus, my delivery locations run 1 --> n and breaks run n+1 --> 2n. Then I want to say that distance/time 1 --> n+1 is 0, 2--> n+2 is 0, but distance to all other locations is slightly (or massively?) increased over reality. Thus, it should always be preferable to keep delivering until the time of the break, and have waiting periods elsewhere. That opens up more flexibility. For efficiency, maybe he is doing the right thing to put the dead-time before the break. Operationally, he should be mitigating the amount of damage a traffic jam could do by minimising the number of subsequent delivery times that would be affected. 

Any ideas on this? Is there an easier way to control this in bulk i.e. modifying penalties for average waiting time / number of instances of waiting time, rather than total waiting time?

 

Regards,

 

Josh

[Stefan Schroeder]

Hi Phil and Josh,

I really like your discussion about driver breaks, and love to see that you seem to find a solution for it. That is really great!

When it comes to waiting times, currently it is somewhat difficult to take them into account reasonably. However, this is what I am currently working at. In a few days you will be able to add waiting times to the optimization easily. Just by setting a vehicle type cost param much like .setCostPerDistance(..), e.g. .setCostPerWaitingTime(..). Additionally, you will be able to specify that vehicle departure times are variable. If so, the algorithm searches for a departure time that minimizes total waiting time of a route.

This way, you will probably solve the problem that drivers wait an hour for their breaks. Instead, they will server other customers, since minimizing total costs will be a trade-off between distance and waiting, e.g. one waiting time unit might be worth two distance units.

What keeps me working at it and is not yet solved is how I can locally estimate the total amount of waiting time a new customer adds to an existing route ...

Best,
Stefan

Am 26/07/15 um 20:49 schrieb j.pi...@gmail.com:

[in...@opendoorlogistics.com]

Hi Stefan,

that's fantastic - waiting time minimisation would be really good.

>> What keeps me working at it and is not yet solved is how I can locally estimate the total amount of waiting time 

>>a new customer adds to an existing route ...

This is I suspect, not very easy. In the case of single time windows a new customer should never increase waiting time later-on in the route, but may have waiting time itself (which should be relatively easy to calculate). It could always decrease waiting time later-on though, which you'd probably need to estimate too.

In the case of multiple time windows a customer insert could presumably shift later customers from an earlier time window to a later one though, thereby increasing waiting time?

I do wonder if for really complex costs / constraints like this, we should just accept that an insert will need an evaluation which involves parsing the whole route to update times etc and we should support an insertion evaluation method - which is only activated when strictly needed - which does this 'lazy' evaluation method of reparsing the entire route. Things like a maximum ridetime duration need it as well. Of course, this will be slow, but probably not so slow that we can't actually use it in practical circumstances, and we'd ensure it's only ever turned on for problems which need it.

You could add a calculateTimesOnEntireRoute method or similar to the JobInsertionContext, so only constraints which need it will call for it to be calculated and you can save the result in the JobInsertionContext, so its not calculated multiple times for different constraints?

Best regards

Phil

Philip Welch

Open Door Logistics Limited

Specialists in open source solutions for transport logistics.

Email: in...@opendoorlogistics.com

Linkedin:  http://uk.linkedin.com/in/welchphilip

Skype: opendoorlogistics

Tel:  +44 (0) 20 8144 4009

Website:  http://www.opendoorlogistics.com

---- On Mon, 27 Jul 2015 11:35:04 +0100 Stefan Schroeder<jsprit.vehi...@gmail.com> wrote ----

Hi Phil and Josh,

I really like your discussion about driver breaks, and love to see that you seem to find a solution for it. That is really great!

When it comes to waiting times, currently it is somewhat difficult to take them into account reasonably. However, this is what I am currently working at. In a few days you will be able to add waiting times to the optimization easily. Just by setting a vehicle type cost param much like .setCostPerDistance(..), e.g. .setCostPerWaitingTime(..). Additionally, you will be able to specify that vehicle departure times are variable. If so, the algorithm searches for a departure time that minimizes total waiting time of a route.

This way, you will probably solve the problem that drivers wait an hour for their breaks. Instead, they will server other customers, since minimizing total costs will be a trade-off between distance and waiting, e.g. one waiting time unit might be worth two distance units.

What keeps me working at it and is not yet solved is how I can locally estimate the total amount of waiting time a new customer adds to an existing route ...

Best,
Stefan

Am 26/07/15 um 20:49 schrieb j.pi...@gmail.com:

6b-8ed9-4746-a7...@googlegroups.com" type="cite">

[j.pi...@gmail.com]

Hi Stefan and Phil,

Your future implementation seems like a great idea. Just like I have used distance to simulate fixed cost, any extra flexibility can also help solve abstract problems not associated with the main problem being addressed. 

This is a really ugly problem though that I can't see being solved by a lazy route parser. Any parse that isn't a full-blown heuristic could actively push against R&R and put you in a local minima. For example, I have three existing routes, one of which is:

1 – 2 – 3 – 4 

My parser tells me that job 5 is best is best inserted into the above route instead of the other two, but in order for it to be the best insertion, the configuration is:

1 – 5 – 3 – 2 – 4 

This is a bit of a disaster. The above route is only an evaluation, not resembling the existing route. So do you accept the parser and reconfigure the whole route as above? Or do you dump job 5 arbitrarily into the route and hope that R&R eventually finds something at least as good as the parser? You cannot simply insert it in the correct position because 1 - 3 is not a real journey in the actual route. If the parser isn't doing a thorough job, you might already have picked the wrong route from the start. It would appear as though the parser would need to be as good as the main algorithm, otherwise R&R is constantly cleaning up the parser's mess?

I see the overheads spiralling with this but perhaps you already deal with something similar elsewhere? I haven't yet managed to visualise the existing algorithm as a whole.

Regards,

Josh

[j.pi...@gmail.com]

I think I have a much simpler idea.

I can't see anything that doesn't cause the previous problem to grow exponentially. Driving distance and time is wonderful in that it's totally static. Waiting time is 100% dynamic based on the routes. Thus the minimisation of waiting time in the R&R region could just bump up the cost elsewhere. You'd have to be solving on a route-by-route and job-by-job level. Horrible.

Perhaps a better approach is an optional post-processing command distributeWait when invoking the solution algorithm. This seeks to take long periods of waiting in a route and tries to even it out between all deliveries whilst not impacting on time windows. Maybe the command needs a time-value associated with it i.e. do not push back any delivery that is already within 30 minutes of the end of the acceptable time window.

I think my initial desire was misguided. Crushing all of the orders as close together would mean that traffic has a bigger impact because I have no contingency time anywhere in the route. Ultimately this would force me to inflate the anticipated driving time by a constant factor e.g. 10%.

Meanwhile, I cannot think that waiting around has any truly tangible cost over that of the driver's working hours. If the route has already been solved for all deliveries and all drivers then it is already a minimum in total tangible costs. So, distributing waiting time around the route actually helps by building in contingency time for all deliveries, without me inflating driving time, which does actually increase tangible costs. 

Thoughts?

Regards,

Josh

[in...@opendoorlogistics.com]

I'm not sure I understood the last couple of messages! The post-processing should presumably work OK; it would depend what information you provide to your users - if you're going to effectively bump up travel time and you tell them that a drive takes 2 hours, which they know only takes 1 hour, you might get negative feedback. Alternatively if you gave them no travel time information, just a list of stops with approximate 'target' times, you'd probably be OK.

>> Meanwhile, I cannot think that waiting around has any truly tangible cost over that of the driver's working hours.

This could depend on the precise law regarding their breaks. Effectively if they're waiting an hour for their break, and then taking their break, they have an extra long break. Does this mean they should be able to start work again earlier (i.e. the waiting time should count as part of their break)? In which case they might be able to fit more work in (and reduce the number of drivers). In the EU, I think the law is something like a break every 4.5 hours, so if they took an early break they probably could start work again early.

Philip Welch

Open Door Logistics Limited

Specialists in open source solutions for transport logistics.

Email: in...@opendoorlogistics.com

Linkedin:  http://uk.linkedin.com/in/welchphilip

Skype: opendoorlogistics

Tel:  +44 (0) 20 8144 4009

Website:  http://www.opendoorlogistics.com

---- On Mon, 27 Jul 2015 16:33:10 +0100 <j.pi...@gmail.com> wrote ----

[j.pi...@gmail.com]

Hi Phil,

I guess some confusion comes from the fact that I was replying in a driver break thread, sorry. I was really addressing the complexity of Stefan's new implementation that seeks to globally minimise all aspects of waiting time (not breaks).

The quote you are replying to is something separate. With the solution I outlined, the driver always gets his full break. It is up to regional law whether this is paid or not, but he gets the full duration at the right time, regardless. Post-solution processing is applied as & when needed to account for this being paid/unpaid.

In ODL (if I recall correctly) you have Gantt charts that list periods of drivers sitting around doing nothing. This is not a break as such, it's a requirement that they do this in order to find a global minimum in operational costs across the entire fleet. My interpretation of Stefan's new feature is to minimise the occurrence of such things by giving them a greater cost than driving distance or time. 

The problem he will have is that to do this is that waiting time is completely dynamic. When you seek to insert jobs into a route (solving only for fuel cost and driver hours), you simply reference the distance/time matrix and everything is predictable. No such matrix is possible with waiting times. Thus, I assume the only way to do it is to assess every option before inserting the new job. I don't think this is computationally feasible. 

Hopefully my last messages make more sense now. 

Regards,

Josh

[Stefan Schroeder]

Hi Phil and Josh,

The problem he will have is that to do this is that waiting time is completely dynamic. When you seek to insert jobs into a route (solving only for fuel cost and driver hours), you simply reference the distance/time matrix and everything is predictable.

This is only half the truth. You are correct that day-time independent transport times/distances are static and can be predicted easily. However, there are already various state variables that can change once an activity has been inserted. For example, load or practical time windows (in contrary to theoretical time windows). Waiting times also change when adding a customer. The crucial question - when it comes to computational complexity - is whether the insertion costs of a new activity can be calculated locally, i.e. just by looking at the neighboring activities or whether it is required to always look at the whole route. As Phil wrote, a new activity does not add any further waiting times (when dealing with single time windows). However, it might postpone arrival and activity start times of subsequent activities and thus do not only reduce waiting time at the next but also at subsequent activities.

This makes it a bit difficult to include it, but not infeasible. One can always try to estimate the insertion effect on the whole route by for example providing a waiting time estimator for each activity or similar.

I let you know once I created a new branch for playing around with the feature.

Best,
Stefan

Hopefully my last messages make more sense now. 

Regards,

Josh

[j.pi...@gmail.com]

Hi Phil,

 

Apologies, I see now what you said here makes perfect sense, I went off topic. Why have a lunch break if you're waiting longer than the lunch break to take it (in an extreme case)? Yes, then I must caveat my work-around in that it's only stable when the driver is otherwise completely packed with work. The work-around guarantees a break, but that in itself opens a new set of problems. With the current tools, I guess we dead-end here. 

 

Something makes me a little uneasy about trying to actually estimate a cost penalty value on waiting time, in such a dynamic problem space, without skewing the solution in an unpredictable way. We'll have to wait and see, but I will be very active in testing it. I think for the sake of my sanity - previously having drivers opening wormholes or making them take their break in an alternate dimension - I'll put this issue to bed until then!

 

Best of luck on this one, Stefan. Thanks Both for this discussion.

 

Josh

[j.pi...@gmail.com]

Hi Stefan,

Ok, now I think I understand predicament much better. Initially I thought that driver time costs had a greater influence in the overall route than they really do. Playing around with very few deliveries, and introducing lots of waiting time to the extreme, I see that the solution only applies the time cost to the driving time. 

Thus, each iteration of the loop will always ignore any period of waiting time... the driver always moves to the next location and does his waiting there, and his arrival time is ignored in the chain, you just go off his departure from that location. In the desire to calculate waiting times locally, could you use a sigmoid function and reference the earliest time window available for the current activity? 

Listed below, without necessarily the actual variable names you use, I will demonstrate this. earliestDeliveryWindow is in regard to the current delivery that you are looking to insert (which can be directly referenced from the service builder table):

Cost = costPerTime * (earliestDeliveryWindow – (prevAct.getEndTime + transportTime)) * ( 1 / (1+ exp(-(earliestDeliveryWindow – (prevAct.getEndTime() + transportTime)))) + (costPerTime*transportTime)

If the driving cost per time was 2 and it took 10 units of time to get to the next delivery, at which there was no waiting time (i.e. it could be serviced immediately, and the earliest time window is actually in the past at the time of consideration... let's say the window opened 15 units before arriving), the cost would be:

Cost = 2*(-15)*(1/(1+ exp(-(-15)))) + (2*10)

= 2*(-15)*(1/( 1+exp(-(-15)))) + 20 = 19.99999

Now assume that the driver would incur a 10 unit wait at the current location in addition to the 10 unit travel time (both costed at 2/unit time):

Cost = 2*(10)*(1/(1+exp(-(10)))) + 10 = 39.99909

I see now that my previous comments about a whole-route parser were nonsense because I didn't understand how time costs were handled. I'm not sure how easy it would be to extrapolate the above to multiple delivery time windows, I don't know how you'd keep track of the potential for these to be broken by job insertion yet.

Perhaps you'd already thought of approaching it this way and it doesn't work, but I thought there was no harm in suggesting it just in case you hadn't.

Regards,

Josh

[j.pi...@gmail.com]

Apologies, this should be: Cost = 2*(10)*(1/(1+exp(-(10)))) + 20 = 39.99909

I was editing my example a lot.

Regards,

Josh

[Stefan Schröder]

You are correct. In this regards, I have created a branch called 'min-waiting-start-times'. Take a look at this example. If you run the example with .setWaitingTimeCosts(0.0) you will get the following solutions:

with a total wating time of 95.
If you set .setWaitingTimeCosts(1.0), you will get a solution where 13, 10, 11 and 14 will be served before 12 at the cost of more distance (dont know where img appears below or above). However, it saves waiting. Try it out by running the example :). I am still testing and struggling a bit with variable departure times. I will also take a look at your the function you suggested. Thanks a lot for your ideas.

[Stefan Schroeder]

Hi Josh,

I just plotted your waiting time cost function
(http://www.wolframalpha.com/input/?i=x+%2F+%281%2B+exp%28-x%29%29+%28x+from+0+to+10%29).

Where do you see the advantage of this

> Cost = costPerTime * (earliestDeliveryWindow – (prevAct.getEndTime +
> transportTime)) * ( 1 / (1+ exp(-(earliestDeliveryWindow –
> (prevAct.getEndTime() + transportTime)))) + (costPerTime*transportTime)

over

Cost = costPerTime * (waitingTime + transportTime)

?

Best
Stefan

[Stefan Schroeder]

Ok. I assume the advantage is for waitingTime < 0. So let me refine my
function:

Cost = costPerTime * (max{0,earliest - (prevAct.end + t(prevAct,thisAct))} + transportTime)



Am 03/08/15 um 12:43 schrieb Stefan Schroeder:

[j.pi...@gmail.com]

Hi Stefan,

Actually, that graph illustrates my implementation perfectly but it's for the opposite case than you are considering (unless "waiting time < 0" was meant to be "waiting time > 0"). It is almost linear. Therefore, waiting time is proportionally added to the travelling time with the correct weight/cost. 

I'm pretty sure your second message clarifies this, I'm just making sure I was clear. 

Your current solution incorporates only the costMatrix to determine the time costs by taking driving time. Although the equation looks excessive, it only calls 1 extra piece of information – the earliest possible time for delivering the service you are looking to insert into a route. It roughly breaks into two parts:

Cost = [some part that reduces to ~zero if there is no waiting time, or applies *almost* exactly the same time cost per unit time to each time unit of waiting] + [driving time cost]

I have been playing with your new implementation and there's lots of WARN: NearestNeighbourIterator issues. I haven't had any time to investigate the working in depth, but I imagine you're storing a lot of routes in memory to test waiting time? I'm not sure how this would scale to 100s of orders. My suggested implementation would not require any additional operations (I don't think so, anyway) as it just corrects the real cost of driver time when inserting a job. Equally I don't think the new function would add too much overhead, although exp is a little costly in computation time. You might need to put a fixed value into the exp e.g. exp(xyz +0.001) otherwise these numbers can get very small and cause a stack overflow, from my experience in Python at least. 

I'm not clear on the problem with variable starting times at the moment. In the current solutions I have, I am able to cosmetically separate waiting time and driving time from the solution print-out. So even though it shows the driver being deployed dead-on the start time, I'm able to make the distinction over when he should actually be leaving.

Regards,

Josh

[Stefan Schroeder]

Ignore the warnings. It just warns you, that ruin tries to remove more jobs than actually available (since I specified a min. number of jobs to be removed).

Am 03/08/15 um 13:20 schrieb j.pi...@gmail.com:

[Stefan Schroeder]

> Cost = [some part that reduces to ~zero if there is no waiting time,
> or applies *almost* exactly the same time cost per unit time to each
> time unit of waiting] + [driving time cost]

Ok. Thanks, Josh, for the clarification. Then I would always prefer this:

Cost = costPerTime * (max{0, waitingTime} + transportTime)

since it is not only easier to understand, but also way faster (5-6
times on my machine), even the latter is not that significant given the
complexity of entire algorithm (we writing about 3ms vs. 16ms for
10million calculations).

Generally, considering waiting time for a new customer i is only one
part of the equation, the other is how much waiting times can be saved
at all other customers in this route, since inserting i might delay the
arrival times of subsequent customers.

[j.pi...@gmail.com]

Hi Stefan,

Absolutely, your method is much faster. I approached this from my engineering side where we used sigmoid functions as on/off switches (we don't have the luxury of max(0,value) )! I think it's the simplest local estimator of waiting time.

In terms of global waiting time, I'm genuinely not sure how well this would function. What is your intended implementation: change the way time is handled across the board in jsprit or have waiting time considerations as an optional extra? 

Ignoring the headache of implementing waiting time with multiple time windows, I would always want to use this new method for estimating costs. When I have been artificially pushing a solution with very few orders, the route is terribly illogical with the existing handling of costs. I don't see this new approach as actively seeking to minimise all instances of waiting time, it simply incorporates realistic time costs; I like it a lot.

If the new function in your previous email is not used in the branch you shared with me this morning, please let me know when you've made the changes and I will re-download. I'm not confident to make this change accurately myself as the solution algorithm is very convoluted. I will test this extensively on real data; I also hope it makes the driver breaks implementation feasible. I will provide feedback on all aspects that I can.

Many thanks,

Josh

[Stefan Schroeder]

Hi Josh,

The whole approach of considering waiting times will looks like as follow:

For each insertion of act k in between act i and j, calc. following insertion cost:

newCosts = transportCosts(i,k) + transportCosts(k,j) + alpha * ( waitingCosts(k,arrivalTime_k)  + waitingCosts(j,arrivalTime_j)) + epsilon

oldCosts = transportCosts(i,j) + waitingCosts(j)

insertionCosts = newCosts - oldCosts

where alpha is a solutionCompletenessRatio defined betwee 0.5 and 1.0. It converges 1.0 the more ruined customers have already been inserted into the solution. This makes waitingCosts less important if a number of customers still have to be inserted, and more important if there are only a few customer to be inserted left.
spsilon is defined as the impact on the whole route and can be calculated as

epsilon = -1 * min{ futureWaiting, endTimeDelay_j } * cost_per_waitingTime_unit

where endTimeDelay_j is the delay of the end time of j due to inserting k. Thus, I assume that the end time delay can be used to reduce waiting time somewhere in the route. However, this reduction cannot be bigger than the existing futureWaiting time, i.e. the sum of waiting times at subsequent customers. Future waiting will always be re-calculated once a customer has actually been inserted into a route.

Does this sound reasonable?

I ll let you know once I merged it into master.

Thanks again for your thoughts.

Best
Stefan

btw: First tests show that this approach will add almost no overall computation time.

Am 03/08/15 um 14:16 schrieb j.pi...@gmail.com:

[j.pi...@gmail.com]

Hi Stefan,

Thanks for taking the time to write all of that out, I understand much better now :)

[ alpha * ( waitingCosts(k,arrivalTime_k)  + waitingCosts(j,arrivalTime_j)) ] + epsilon

I've spent a bit of time thinking about this part. My concern is that the bit in square brackets is antagonistic with epsilon but I'm not sure if this has a tangible impact or, even if it does, whether this impact will eventually be undone by further iterations. I'll list my thoughts anyway for reference.

You're mitigating the cost impact of waiting times of insertion of k using alpha, but any insertion of waiting times here has an unmitigated increase in epsilon (up to a maximum value) which is a negative cost. Equally, the service time of k increases epsilon. Could this be introducing a bias that a job with a long service time but, additionally, a waiting time before it could be seen as an attractive choice? 

It projects forward a powerful estimation about how this insertion could affect subsequent waiting times, but I wonder if this is too powerful as it can overpower the analysis of the present activity insertion. 

As I said, it might not have any impact over multiple iterations. But those two sections of the equation are not independent and are working antagonistically, which always makes me wonder.

Regards,

Josh 

[Stefan Schroeder]

Hi Josh,

Thanks for your reply. You are correct, alpha should also occur in epsilon or

[ alpha * ( waitingCosts(k,arrivalTime_k)  + waitingCosts(j,arrivalTime_j)) ] + epsilon

should be

alpha * ( waitingCosts(k,arrivalTime_k)  + waitingCosts(j,arrivalTime_j) + epsilon)

cost. Equally, the service time of k increases epsilon. Could this be introducing a bias that a job with a long service time but, additionally, a waiting time before it could be seen as an attractive choice?

Waiting time before is also a cost factor. Long service time ... hmm ... I know what you mean. One needs to test this.

It projects forward a powerful estimation about how this insertion could affect subsequent waiting times, but I wonder if this is too powerful as it can overpower the analysis of the present activity insertion.

This is what we should test also. I assume that alpha reduces this issue and we dont need to worry this so much. Furthermore one can and should find a reasonable balance between transport and waiting costs. If the cost per waiting time unit is greater than per transport unit, one definitely gets strange and zigzag results (since waiting is more expensive, the algorithm searches for long distances to avoid waiting).

Best,
Stefan

[Stefan Schroeder]

Hi,

I just separated the waiting time from the variable start time feature. The new branch is here.

Stefan

Am 03/08/15 um 17:29 schrieb j.pi...@gmail.com:

[j.pi...@gmail.com]

Hi Stefan,

 

I have got the new branch fully set up and integrated with my own data. Initial observation – it's working exactly as intended right out-of-the-box. Fantastic! I'll be starting proper benchmarks soon (on everything but computation time... I'm running this experimental branch on a virtual machine to avoid me accidentally damaging my existing setup). Even on the VM it's fast enough to not really see any difference. I'll then move on to trying to break it or pull out anomalies with fringe cases.

 

I'll probably be quiet for a while now while I collate all my tests and give feedback. But, at the very least you know one person has this running and testing it (and liking it a lot) :)

 

Great work on this one, Stefan. 

 

Josh

[Stefan Schroeder]

Perfect! Thanks a lot.

Good luck!

Best,
Stefan

Am 04/08/15 um 17:28 schrieb j.pi...@gmail.com:

--

[Stefan Schroeder]

Hi Josh and Phil,

Just created this: https://github.com/jsprit/jsprit/issues/170

Let us discuss waiting times (#169) and driver breaks (#170) further via the issue tracker.

@Josh: you then need a github account

I have created a prototype for driver breaks, i.e. I just put your GREAT ideas into code to avoid the overhead of the solution without coding (i.e. the massive multiplication of locations due to breaks). It seems to work well without adding significant computation time apart from some minor issue reported in #170.

Thanks again for the valuable discussions and your great ideas.

Best,
Stefan

Am 04/08/15 um 17:28 schrieb j.pi...@gmail.com:

Hi Stefan,

--