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

Vehicle Routing: VeRoLog Solver Challenge 2014

If you are interested in the Vehicle Routing Problem (although the actual problem being considered is called Swap-Body Vehicle Routing Problem (SB-VRP)), you might be interested in this competition.

Vehice RoutingThe deadline, to register, is the 31st Dec 2013 although the actual submission deadline is not until April, so you can register and still have plently of time to get your entry ready.

The competition is run by VeRoLog and full details are available here.

A brief descition of the competition (from their web site) is as follows:

VeRoLog, in collaboration with PTV group, is proud to announce the first edition of the VeRoLog Solver Challenge (VSC2014). This challenge is aimed at comparing on a specific variant of Vehicle Routing Problem (VRP), this year proposed by PTV, the computer codes implemented by the participants and submitted in executable form to the jury. The codes will be compared by considering the quality of the solutions obtained within a specific time limit on a set of test instances that will be defined by the jury. The declaration of the winners will take place at VeRoLog 2014 in Oslo, June 22-25, 2014.

The problem that is the subject of VSC2014 is called the Swap-Body VRP (SB-VRP) and is described in detail in the attached document. The participant teams have to pre-register BEFORE December 31, 2013 by sending an email to the jury at ewg.verolog@gmail.com indicating the name and affiliation of all team members and the name of the team leader.

This post also appeared on a University of Nottingham blog post.


Header image: Problema de rutas de vehículos (downloaded form Google 27 Dec 2013, labelled as free to reuse): http://es.wikipedia.org/wiki/Problema_de_rutas_de_veh%C3%ADculos

 

Vehicle Routing Datasets

For reasons which will become apparent in the fullness of time I have recently been trying to track down all the vehicle routing datasets that are out there; specifically the Capacitated Vehicle Routing Problem (CVRP).

I know that the problem was introduced in 1959 (with small instances being made available in that paper1) and I think I have tracked down the majority of datasets since then, but if anybody out there has a list (or a reference to a list) it would be helpful.

1 Dantzig, G.B., Ramser, J.H., 1959. The truck dispatching problem. Management Science 6, 80–91

Non-symmetric Vehicle Routing

For a while I have been thinking about Vehicle Routing (you can see a previous blog here). Most of the problems I come across (though I am happy to be corrected) assume that distances are symmetric. That is, the distance between location i and location j is the same as the distance between location j and location i. I know that there has been some work done on the asymmetric Traveling Salesman Problem, but I am not aware that the asymmetric VRP has received a similar amount of research attention.

It is not always the case, particularly in real world problems, that the distances are symmetric. For example, the driving distance between two locations might be different depending on the direction you are traveling.
I guess there are many reasons why symmetric distances are used. For example:

  • If we are storing the coordinates of each location we can calculate the distances algorithmically, as part of the pre-processing to the main optimisation algorithm.
  • We could ask if it really matters if we work with symmetric distances? Does it really affect the results that much, or make any difference to the conclusions we can draw about the algorithm we are using?

But I have been wondering if there is any mileage (sic) in looking at asymmetric distances, in the context of real world VRPs?

With these questions in mind I have recently (a couple of months back) been looking at Google Maps as a way of being able to collect data. Google actually provide a very nice API (Application Programming Interface) which is quite easy to use and there (as you would imagine) is a lot of information available.

I got to the point where I have a Google Maps application up and running, really just to prove to myself that what I wanted to do was possible. Then I had to abandon it for a while as I had other, more urgent things to do. However, it is still on my mind about the research that is possible and I plan to address some of them in the near future.

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.