Vehicle Routing: Case Study at EURO

I am at the EURO 2009 conference at the moment and have just been to a very interesting presentation (the picture was taken during the presentation).

A few days ago I wrote a blog on various formulations of the Vehicle Routing Problem (VRP) (see original post). This blog talked about the many variants of the VRP.

The talk (6th July 2009: 13:35) was entitled Vehicle Routing Problem: A Case Study in Local Government. It considered six different VRPs (eight if you also take into account the ones which do not transport people around (laundry and meal deliveries)) that Coventry City Council face.
They all have lots of constraints that you may not normally associate with the VRP. For example:

• They want people to spend as little time on the bus as possible;
• Usually the aim is to minimise the distance but in this case we want to minimise the time between locations (a subtle difference, and something I have been looking at recently with the help of Google Maps API - more on this later).
• They require pickups to be as efficent as possible (i.e. they want to pick up people who are close to one another in one go rather than back-tracking);
• etc.

Unfortunately, I don't have access to the slides which listed all the constraints, but it made interesting reading.

I hope the authors are able to publish this work as it would make a good case study paper

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.