Work out which parcel deliveries we ship ourselves and which we outsource

Question

Firstly, I hope I'm asking this in the right place. I work for a large online retailer in UK. We ship approaching 2000 orders each day and are growing very quickly.

We currently use multiple delivery firms to handle all our deliveries. We're planning to launch our own fleet of delivery vans soon for deliveries local to our distribution centre.

When we launch our own delivery fleet, one of the first tasks for the computer systems behind it will be to decide which parcels should be delivered by us and which parcels we should outsource the delivery of to one of our delivery partners. Once that has been worked out, we can worry about which parcels go onto which vans and in which order they will be delivered (the Vehicle Routing Problem (VRP)).

I looking for some advice here on the first part of that (which parcels we deliver ourselves and which we outsource). I'm not looking for help with the VRP at the moment (we're intending to build a system upon OSRM and Optaplanner and are comfortable with how that will work), although if you know of a good solution to solve both problems in one go, that would be great.

I have considered some fairly obvious things to determine the orders we deliver ourselves:

1. All deliveries within x miles radius of our distribution centre.
2. All deliveries within x minutes drive of our distribution centre.
3. All deliveries within x minutes drive of our distribution centre and then all deliveries within y minutes drive of any delivery we are going to. Recursively. With a maximum distance from our distribution centre (so we don't have a line of deliveries up the country and end up 500 miles away!)
4. As with number 3 but calculating x and y based on the cost of us using a 3rd party to make the delivery on our behalf (i.e. we'd be happy to send one of our vans further for a heavier/larger parcel).

I'm going to give it some more thought, but there has to be a better way than any of those options above. Does anyone have an experience with this as I'm totally new to it? Is there a name for this problem? Much like the names of Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP) which would aid my Googling? I'm sure there will be a way to use Optaplanner to come up with a good solution but I'm not sure how. Ideally we would factor into the decision process the cost of delivering the order with our cheapest delivery partner.

You can assume that we know the following for all parcels:

1. Lat/long for each delivery point.
2. The actual driving time and distance between any two delivery points (and/or our distribution centre).
3. The cost of using a 3rd party to make each delivery.

We use linux based systems and love open source projects (and have contributed fixes/improvements back to many). We're up for using open or closed source applications to make our life easier, and even things that only run on Windows if we really need to. We'd also happily code the entire thing in-house. If you know if any good packages to look at then please do say.

Thank you for your help.

Answer 1

What you need is something that does Linear Programming. The various variables you would be using are called "Decision Variables" in the context of these methods. Linear Programming is a very mature technique and there are many packages and platforms available. There are also legions of resources for learning the techniques behind it as well if you want to scratch build something.

There are various other methods of optimization you can use as well if linear methods prove insufficient. For instance, Stochastic Optimization covers cases where some or all of the variables are random.

Answer 2

This seems like a decision for business people to make, not developers. They do calculations and determine the rules by which your application will decide what parcel gets shipped by you, and what parcel gets shipped by third party.

If I was to implement it, here is how I would go about it:

1. Get quotes for each delivery company you can use.
2. Factor in your own estimates for your fleet. (Can be $/mile or $/hour).
3. Decide which one yields more profit.

This should probably be done offline, in some sort of processing queue so user doesn't wait for the decision.

Answer 3

Interesting problem….

Firstly a van/driver has a fixed cost for shift so you will wish to put enough items in the van to use up all the capacity you have.

Then if a driver is going to the same property often, they will be able to find it faster.

You have to take into account what you do if your customer is not in, for example I find it easy to pickup an item from the post office sorting office. You can build up history based on customerId, customerType, typeOfItem, to predict if someone will be in.

Clearly if a van is going to be driving past an address, you should take it into account – hence I am not convinced that you can separate “Vehicle Routing Problem” from choosing the parcels to handle yourself. (Likewise if a single parcel makes the vehicle routing hard, you should just not handle it yourself)

As the incremental cost of handing a parcel yourself depends on the other parcels you decide to handle “linear programming” is unlikely to cope.

Assuming you have nVans, you are trying to divide up your parcels into nVans+1 sets, such that.

• The set of parcels for each van can be delivered by that van in a day. (Hard constraint)
• The set of parcels that are outsourcing on a given day has the lowest possible delivery cost. (optimise for)
• That there are no parcels on the van, that have a margin cost (van running cost) that is more then what it would cost you to outsource them.
• Parcels can be clustered based on post code to reduce the size of the problem.
• Some parcels may have flexibility on the day they are delivered.

If you had unlimited CPU tine, you could run the above in Optaplanner, using a sub instance of Optaplanner to do the vehicle routing to check the hard constraint of what a van can do in a day. But making a NP complete problem the inner loop of anther NP complete problem is not going to work!!!

If you got some clusters of parcels when the saving of using your vans is a lot greater than other parcels, then you can divide these between your vans, add on as many other parcels as you can, one at a time, base on “closeness to current rout”, finding the best rout after adding each parcel.