GraphHopper.com | Forum | GitHub | Maps | Blog

Shipment Pooling


#1

I’m trying to model shipment pooling in my route optimization implementation and am currently just trying to find upper-level ideas as to how to do this. The use case I’m trying to address is the following:

There exist several small packages in a small cluster of locations that need to travel to the same destination across a very large distance (say from the East coast to the West coast of the US). These could be modeled as several shipments; however, the optimal solution would involve modelling each trip a package must take as two shipments. The first shipment could take the package to a common point (the pool point), and the second from the pool point to the final destination.

I’m wondering if anyone can give me any direction as to how to implement this. For every shipment that we route through the pool point, we’re actually creating two shipments where the second shipment can only be picked up after the first. Is there a way to implement a constraint to model this relationship like this between shipments when they won’t necessarily be on the same route (I expect this to be the case most of the time).

Another solution we could take, though not as elegant, is to set the time windows in such a way that the end of the first shipment must come before the beginning of the second shipment. I’m not thrilled with this solution as it requires estimating when a shipment will arrive and may overconstrain the problem. Additionally, if the problem is set up such that any one of the legs the package must travel is unserviceable, then they must all be unserviceable.

That’s where I’m at right now. Does anyone have any suggestions how to proceed?