For any business that needs to both pickup and drop-off deliveries during the course of a route (as opposed to the classic model of delivering from a single starting depot), being able to plan routes that can correctly cater for intra-trip pickups and drop-offs is essential. This requirement is a becoming more and more important as large companies grapple with last mile delivery costs.
Last mile delivery companies tend to have numerous en-route pickup locations as well as drop-offs. This makes their route planning requirements far more dynamic (and complex) than more traditional multiple traveling salesman route optimization problems.
The issue is further exacerbated by the fact that most last mile delivery vehicles are small and light, giving them very limited carrying capacity. Route planning under these conditions requires you to be able to optimize for efficiency, while juggling carrying capacities. Let's take a look at a classic route plan involving only deliveries from a single starting depot and then contrast that to one that requires multiple intra-route pickups and drop-offs.
Deliveries Only
As you can see, this example uses two similar vehicles, each with their own carrying capacity and a handful of deliveries to make.
Looking closely, you can see that the Pallets load is 12 while the vehicle only has capacity for 10. In this instance we would expect the White Pickup to have to return to the depot and pick up the Pallets it was unable to carry on the first trip (and do this in the most efficient way).
Here's the result.
As expected you can see that the white Pickup took a single trip out to drop-off 5 Pallets at Hospital Cochin, then returned to the depot to pick up the remaining 7 Pallets for delivery.
Incidentally, if you're curious as to why the system chose to do it's deliveries in this specific order, the answer lies in the distance and time it takes to travel to each of the locations from the depot. As it turns out Hospital Cochin is closer than the other two locations so it made sense to minimize the distance of the additional trip in the tour (to avoid being forced to travel further for either of the alternative drop-offs).
Single Intra-Trip Pickup & Drop-off
Now let's tweak our schedule to instead drop-off some Pallets that need to picked up during a route. Here's the change.
Notice that this time the Drop off at Hopital Broussais is now specified as coming from one of the other locations, Plaisance, instead of the depot. Now, what we expect is that, whatever happens, the vehicle must go to Plaisance before it visits Hopital Broussais (because it can't drop off 4 Pallets it hasn't yet picked up).
What else do you expect? The carrying capacity of the Pallets is still over 10 (the White Pickup's carrying capacity), so will it still need to make multiple trips? Here's the solution.
Now, the vehicle has only made one trip. This is because it was able to drop-off some of the Pallets from the depot before it picked up the additional capacity at the intra-trip pickup point. In addition, you should be able to see that stop 6 on the route is Plaisance, our pickup point, and stop 8 is Hopital Broussais the drop-off location so we have correctly picked up those Pallets and dropped them off all while staying within the constraints of the White Pickup's carrying capacity.
Another point of interest here is that the White Pickup route in the second example worked out at around $20 cheaper. This is because it avoided having to do a costly trip back to the depot to be reloaded before returning back out to finish it's deliveries. This is an unusual situation arising from the fact that it is cheaper to avoid returning to the depot when your delivery locations are all quite far away.
More often than not, having intra-tour pickups and drop-offs will increase the cost of a route plan because it puts constraints on the solution that force it away from the optimal route (i.e. the route the vehicles could take if they had no deliveries or capacity constraints). This is because a pickup and drop-off creates a relationship between two points that order them in time (i.e. the pickup must come before the drop-off).
Optimizing a route with more and more of these pickup/drop-offs should naturally increase the cost of the overall route plan. But is this always the case?
Multiple Intra-Trip Pickup & Drop-off
Here's an example that changes one more delivery from the depot to a intra-route pickup.
Here we've altered the 5 Pallet drop off from the depot to a drop-off from a new location, Place d'italie, which is an en-route stop. Optimizing this yields the the following result:
Now the cost of the White Pickup's tour is $76.28. Ever so slightly cheaper than it was in the previous optimization. This is quite a strange result since we'd expect that with more constraints the route should become ever more expensive. However, this is only generally true and not always the case. In this instance Optergon was able to find a way for the White Pickup to get rid of carrying capacity in such a way as to speed up the route ever so slightly and reduce the overall costs accordingly.
Previously it was carrying Pallets from the depot so it had to get rid of at least one of these before pickup up any more. Once this capacity was changed to be picked up during the route the system had a bit more freedom to choose when it wanted to pick up and drop-off. And finally, as you can see, Place d'Italie is correctly placed earlier in the route than the drop-off point, Hospital Cochin (just so you know we're not cheating).