Christmas 2015: Advent calendar of research

In the run up to Christmas I have been posting each day that is (loosely) related to Research and Knowledge Exchange, and is also Christmas related.

I thought it worthwhile just summarsing them here so that you can take a look at them from from one easily accessible place.

  1. Deck the halls with research stories
  2. The Christmas Present Problem: It’s Hard – NP-Hard
  3. Packing Santa’s Sleigh
  4. How will Santa deliver all those presents this Christmas?
  5. The 12 days of Pascal’s triangular Christmas
  6. Brian Cox: Can Santa travel faster than the speed of light?
  7. Five tricks retailers will use to make you shop this Christmas
  8. Problems with your wi-fi? It could be your Christmas lights!
  9. Santa is really a Travelling Salesman
  10. How do Christmas TV adverts keep your attention
  11. Have a go at solving this Christmas cryptographic problem
  12. How does electricity usage change on Christmas day?
  13. Is your oven big enough for the turkey
  14. How will (retail) Christmas compare to 2014?
  15. Should shops open on Christmas day?
  16. Could your Christmas decorations be a hazard to planes?
  17. How Christmas lights helped guerrillas put down their guns
  18. Program your own Christmas Tree
  19. Festive spices and their intoxicating history
  20. What makes a Christmas gift good?
  21. The appeal of the Christmas song
  22. Buying Christmas presents is a real dilemma
  23. Wisdom of the Crowds at the Graduate School Christmas Party
  24. Magical Mathematics: The Mathematical Ideas That Animate Great Magic Tricks

Model Formulation: Vehicle Routing Problem (VRP)

If you are aware of the Vehicle Routing Problem (VRP), you will know that it is quite an easy problem to state, although it has many variations which make it one of the more complex standard models.

Here is a fairly standard description (model):

You are given:
– a set of customers (each one having a demand);
– the location for each customer (perhaps as x,y coordinates or, perhaps, as a distance matrix between each customer);
– a set vehicles, each with a given capacity (usually identical for all vehicles);
– a depot; where each vehicle must start and end.

Then the problem is to come up with a number of routes (the number of routes is usually the same as the number of vehicles) that

a) minimises the distance travelled and
b) ensures that a vehicle does not exceed its capacity taking into account the customers it visits and their demand.

And that is all well and good and a lot of excellent research has been carried out using this relatively simple model.

Of course, there are many variations. For example, trying to minimise the number of vehicles (routes), introducing the concept of backhauls (i.e. doing all the deliveries and then going back to each customer and picking things up) and having time windows (i.e. a customer has to be visited at a certain time).

However, even these variations (and there are many others) do not capture many real world issues that often need to be addressed. Take, for example, supermarkets that deliver to your door. It is usually a Vehicle Routing Problem with Time Windows (the supermarkets often give you a two hour slot when they will deliver). But what about other factors that might have to be considered? How about:
– Time might be an issue with respect to how long perishable goods can be in the delivery van.
– Perhaps the vehicle has to be packed in such a way that the deliveries which are delivered first have to be loaded last.
– Perhaps the vehicle can only carry a certain weight, in addition to a certain volume.
– Perhaps the weight has to be evenly distributed over the vehicle.
– What happens if there is a breakdown.
– When do you “pick” the goods from the shelves and when do you “dispatch” the vehicles.

Some of these may not actually be problems for the supermarket delivery problem but you can imagine these factors coming into play for other types of delivery problems.
And trying to take a standard vehicle routing model and developing it to model a real world problem is often far from easy.