When a vehicle performs a pickup job or delivery job we set how much time it will take - setPickupServiceTime.
But the while the cost for picking up one item is say 5, the cost for picking up 10 might only increase to say 6 not 20.
Over a larger number of concurrent pickups the PickupServiceTime becomes hours which is not realistic.
Im trying to work out how to consolidate the time-on-site cost when a vehicle is picking up multiple jobs from a single site at the same time.
I imagine it has to be done dynamically using something like a hard constraint but it seems that these constraints measure and respond as a good/bad result whereas this would be altering the job properties. But then my experience of constraints is very basic and I don’t know where to start.
It seems to me that this must be a common need. Can someone please share their experience on this ?
Service time has a cost, and cost influences the solution similar to clustering. You also have the details of the jobs and the distance/time matrix beforehand. I would handle with pre-processing if possible rather than complicate the routing heuristic further.
Similar to what @roganjosh says, you could improve things by manipulating the travel time matrix, and adding saying 10 minutes for every visit to the pickup location. So if you have 2 consecutive visits to the same pickup location, this 10 minutes is only added once because you only visit the location once. You could then model pickup time as say 10 minutes + 1 minute per item. I did something similar recently in ODL Studio (not main branch yet), where I applied an additional travel cost only between non-identical locations, to encourage multiple pickups at the same location to be grouped together.
Another way to put it; are five jobs with a customer/service in the same general time slot and same location really 5 jobs at all in terms of routing ? Routing problems scale badly with problem size - I would always seek to minimise the problem definition, not add constraints on the problem.
That’s not to say you can always do such things, or at all, but consider it. There might be necessary restrictions on different types of vehicles required in a particular location etc.
I unfortunately cannot tell you in detail how you might go about dealing with this kind of thing, and it possibly wouldn’t be a good fit for your business. Make a distinction between what is a routing problem and what is a pre/post-processing problem. Make use of soft data as best you can otherwise you rely on the heuristic to naively discover it itself through increased restrictions that only serve to complicate each iteration.
Nice one roganjosh. Your comments have helped solve the problem completely without changing the travel time etc.
We went back to the drawing board and redefined what we were trying to achieve. To keep a long story short, this is what we did:
Instead of calculating the Pickup TimeOnSite based on how many orders needed to be collected we based it on the weight of the orders. This means that smaller orders will load quickly and larger (say pallets) will take longer.
We tried this out and Voila it produced a really sensible solution.
At first we thought we should have a minimum pickup time and if the Kg*TimePerKg < MinPickupTime then use the MinPickupTime time. But we realised that it is not necessary because we are picking up lots of orders from a depot. There will always be lots of orders and so the TimeOnSite will always make sense (more than a nominal amount).
So thanks Roganjosh - your solution was “To think differently about the problem” and that worked.
If I understand Grant’s implementation correctly, it is not done dynamically at all. On that theme, I would ask why you need to do this dynamically? The answers from myself and @PGWelch kinda boil down to; you can push the algorithm to sensible solutions by simple manipulations (be it matrix manipulation or fudging of service times) outside of jsprit that guide the solution to contain something you knew you wanted all along without implementing complicated constraints. It’s not always wise to jam this logic into the flow of the main algorithm when it can be neatly examined and handled elsewhere.
Sorry for the delayed response - I have been away.
Roganjosh is correct in that I was looking for a dynamic solution, however following his advice and rethinking that actual need, realised that it was not necessary for our situation. I was looking to adjust the pickup time for multiple jobs at the same location at the same time by the same vehicle with a fixed fleet of about 5 vehicles. The suggestions to adjust the travel time do work technically but do not work (for us) from a “business outcomes” POV because it obscures information important to us in gaining an ongoing time/motion understanding of the business.
Everything I looked at for dynamic calculation proved either unrealistic or just too hard.
So instead of calculating time on site as a factor of the number of items being loaded we did it as a factor of weight. For our environment that was actually a better outcome and did not need to be calculated dynamically.
We set a nominal time in seconds per kg loaded (typically about 30 parcels each of a range around 10kg onto each truck). We then set the TOS at pickup as the job is added to the problem set using (weight * rate).
Early testing is showing this to, ostensibly, be a realistic estimation model. A benefit of this approach is that the TOS variance caused by heavier items is automatically allowed for.
Production testing mode in a few weeks will be the proof of the pudding.
If you need some help considering models/methods then post a bit of a synopsis of your situation. I am not an expert but am willing to ponder it.
Not a problem and thanks for the response @grantm009.
I’m working at a local logistics company in Ecuador that took notice of this framework. The problem that had arisen was that as your problem proposed, it was ludicrous to pile up durations of different activities on the same spot. What I had in mind was a way to squash the duration time of “chained” activities in the same spot by the same driver at a similar time.
Let’s say each task may take 5 minutes from parking to arriving at the place, and 1 minute of actual “delivering”. But 3 similar deliveries should take 8 minutes instead of 18 minutes.
That’s the inconvenience I was dealing with. I’m thinking in using ActivityCosts with a counter cache in which based on time, location, and driver increases time with a flat estimated setup time on first hit and only “delivery” time on each following hit.
Interesting situation. Have you considered that the three parcels might take 18 minutes if they are bigger/heavier and therefore require the driver to return to the vehicle to get each of the packages ? That was a challenge that I faced. The “boxes” being delivered hold different quantities and different items for each customer and therefore they weigh differently. Of course this may also apply for three deliveries to the same customer. For example 2 boxes each weighing 5KG could be carried into the delivery point from the vehicle then a return to the vehicle to get the third item which weighs 13kg.
Also bear in mind that it will never be accurate. Some drivers work/walk faster than others, can lift more/less than others. Sometimes the vehicle can park directly at the delivery door but sometimes might have to park further away and of course traffic conditions make a difference.
So it can only ever be a “guide”. Therefore using the weight of the items in your situation might work just as well, be less complicated and more consistent.
Activity costs might work but sounds hard to implement. Having said that Im not an expert.
Hahaha yeah, I’m well aware it will never be completely accurate.
I have one question about the weights approach. How do you handle extreme cases, as too light few packages and too many heavy packages. The heavy ones case sounds like it is handled by itself but if I’m delivering something light like a pizza which has a really low weight and since it’s a single item the problem would interpret the delivery taking place in e.g. 10 seconds.
I understand this particular case does not fit your business model but from what you tested with a minimum pickup time, did you find that approach good enough?
For us the weight model works because the truck is always picking up a significant number of items to be delivered. So even items that weigh 1KG are ok because they are part of the bigger picture. I can see that the model might not suit picking up a single item of very small weight. But then If you are delivering take away food you are probably not concerned with weight or qty for TOS calculation but rather walking time from vehicle to door.
Perhaps it would be an idea to run a test. Put a walking tracker on a number of delivery people and track the time from vehicle to door for a while to build up some base line data. Once you have that you can get some idea as to the actual range of data and whether it could be added as a fixed amount or needs to be dynamic. Dynamic for home delivery of takeaway foods is not going to be easy. Perhaps not even worth it.
I’m suggesting that you go out with a driver and make observations about how everything runs. Also look at past customer habits in relation to these observations. Find a scaling model that fits those observations, rather than trying to scale linearly (which I assume is what is happening if you talk about it going down to 10 secs).