Transport models for food banks

The current issue of the UK's Journal of the Operational Research Society includes an unusual transport problem.  There are numerous variations on the classic Vehicle Routing Problem (VRP), and this is an interesting one derived from an observation of a real-world problem.  The simple VRP is to devise routes for a fleet of vehicles to deliver goods from a base depot to customers.  Not only do you need the routes, but also the assignment of vehicles to those routes, subject to constraints on the capacity of the vehicle and the time/distance covered by a driver on each route.  It's the problem solved daily, by the large courier companies making home deliveries, as well as by heavier vehicles serving shops and businesses.

In their paper "A multi-start optimization-based heuristic for a food bank distribution problem", (JORS vol 69, no5, pp691-706) Mohammed Reihaneh and Ahmed Ghoniem look at the more difficult problem of choosing sites for transfer depots which will be used for part of the distribution.  So the base depot supplies transfer depots, and the customers go to the transfer depots for their goods.  This is intended to model the scenario where the customers time and travel costs are included in the overall cost of the distribution scheme.

Even with this simple explanation, the problem can be seen to be quite complex.  Even with one depot, three customers A, B, C and a possible depot D, you can consider the following:
Depot to A, B and C collect (separately) from A
Depot to A, B collects for B & C from A
Depot to A, C collects for B & C from A
Similarly for Depot to B and Depot to C
Depot to D, A, B & C each collect from D
Depot to D, a delivery visits A, B & C in turn from D
Depot to D, deliveries go to two of A, B & C and the third one collects from D

Now multiply by several more customers and several more transfer depots.

No wonder they have used a heuristic to find good, if not necessarily optimal, solutions!


Popular Posts