Partial deliveries in the middle of the route

[bjtrounson]

Hi VROOM team,

I've currently got my problem modelled with shipments and a delivery assigned to each pickup which I have calculated before hand.

But I'm having an issue where I'm having partial deliveries happening in the middle of my route steps (for context we are transporting milk off farms and transporting them to a depot).

That fact that it is doing a deliveries in the middle of the route isn't an issue, but it only delivers 2,221 of the current 18,795 volume is kind of confusing to me as it makes more sense to drop off the full load since you wouldn't be caring around more weight if you continue.

I would assume what it is doing is dropping off two of my shipments off but not the rest.

Is there a better way to model this problem or any work around to either it deliver the full load or deliver only at the end of the route.

Here is the problem and solution files for context, I'm using Valhalla for the routing

Problem problem.json

Solution solution.json

Any help with this would be greatly appreciated, and I really appreciate this open source tool and all the work you guys have put into it.

If you need anymore information let me know :)

[jcoupey]

it only delivers 2,221 of the current 18,795

I think you're only accounting for the first delivery step here while there are several deliveries in a row at the same place:

$ jq '.routes[].steps[] | [.type, .load[0]] | @csv' solution.json 
"\"start\",0"
"\"pickup\",2586"
"\"pickup\",6653"
"\"pickup\",8319"
"\"pickup\",11853"
"\"pickup\",15093"
"\"pickup\",15510"
"\"pickup\",17314"
"\"pickup\",18795"
"\"delivery\",18378"
"\"delivery\",16574"
"\"delivery\",13988"
"\"delivery\",10748"
"\"delivery\",9082"
"\"delivery\",5015"
"\"delivery\",1481"
"\"delivery\",0"
"\"pickup\",4536"
"\"pickup\",7395"
"\"delivery\",2859"
"\"delivery\",0"
"\"end\",0"

If you look at the load at each step, you'll see that after the first round of deliveries the vehicle is empty before starting over for two other pickups.

[bjtrounson]

Oh wow, I'm blind sorry about that.

I had cut out a bit of information from my original problem file thinking it wouldn't impact it as it had our farm numbers and such in it. I had also remove all the other vehicles that wasn't being used in the route this seems to be what makes it do a partial delivery.

It seems to be doing it when I have all the vehicles we have in the problem file.

Here is the example.

"\"start\",0"
"\"pickup\",2586"
"\"pickup\",6653"
"\"pickup\",8319"
"\"pickup\",11853"
"\"pickup\",15093"
"\"pickup\",15510"
"\"pickup\",17314"
"\"pickup\",18795"
"\"delivery\",17314"
"\"pickup\",21850"
"\"pickup\",24709"
"\"delivery\",21850"
"\"delivery\",20046"
"\"delivery\",19629"
"\"delivery\",16389"
"\"delivery\",12855"
"\"delivery\",11189"
"\"delivery\",7122"
"\"delivery\",4536"
"\"delivery\",0"
"\"end\",0"

Problem problem.json

Solution solution.json

[jcoupey]

Thanks for the update, I can reproduce the problem. What happens here is that the "expected" solution with everything delivered before starting a new round of pickups has exactly the same cost than the one your get, since all deliveries happen at the same place. Internally we currently have no way to hint toward the more sensible solution.

This is similar to the problem described in #560, though here the solution is not strictly suboptimal (in the sense of our internal cost evaluation), just inconvenient. Fixing #560 would solve your problem as well.

[bjtrounson]

That makes sense, I did look at that issue and wondering if I was having that same related problem.

I was wondering whether you think this solution would influence the cost enough to provide the expected solution.

I was thinking of creating a custom matrix that calculated the current volume on the truck per pickup, but I feel like VROOM is already taking this into account and it will be the same cost as you mentioned.

My other thought was when parsing the solution when every I see a delivery in the route I would just assume that it is dropping off the whole load and ignore the delivery quantity.

I have tried this change but have found that is still does it in some scenarios unless I didn't compile it or apply is correct. Which is possible as I'm not much of a C programmer and mostly deal with web related tech.

I've tried switching to a <= in the criterion to update the best insertion here:

https://github.com/VROOM-Project/vroom/blob/58f74115bd9dbc5f4d9f682f4466ba8051b096cd/src/algorithms/heuristics/heuristics.cpp#L346