mortar board
Vehicle Routing #001

Research and Practise.com

All you need to know, all in one place

The scientific and industrial communities are often unaware of the work of each other. We aim to provide a service where you can find all the information you require, for a specicific specialisation, all on the same web site. We would welcome suggestions for other areas.

Your advert could be here - take a look at our advertising rates
Your advert could be here - take a look at our advertising rates

What is Vehicle Routing?

The Vehicle Routing Problem (VRP) can be found in many real-world scenarios. For example, if you order goods, online, from a supermarket they must deliver your groceries, along with their many other customers. To do this they have to decide what routes their vans will take and what particular van your goods will be assigned to. In doing this, the supermarket needs to take many factors into account. Perhaps they will offer you a two hour time window so they need to make sure that the van arrives in that timeslot. The vans will have a capacity, so there is only a certain amount of groceries that can be asigned to a certain van. The company also has to ensure that the driver can deliver all the goods in their allocated work day (say, 7 hours). They will probably also want to keep the number of miles/kilometers driven to a minimum to save on fuel and maintenance costs. As you can imagine, the scheduling of orders to vans, drivers to vans and vans to routes is a complex task. And this is just a simple example of the Vehicle Routing Problem. The actual problem faced by supermarkes will be much more complex.

Of course, the problem is not just faced by supermarkets. Courier companies (such as UPS), service companies (gas, electric, water, electrical repair companies etc.), home health care (nurses, meals on wheels), dial-a-ride etc. are just some of the other industries that have to solve vehicle routing problems on a daily basis.

In its simplest form the vehicle routing problem can be stated as follows:

  • There are a number of vehicles, each with an identical capacity.
  • There is a single depot, where each vehicle must start and end.
  • There are a number of customers, each in a different location.
  • Each customer has a certain demand, which has to be satisfied by a delivery from just one of the vehicles.
  • We know the distance between each customer, as well as the distance between the depot and each customer.
  • Each customer can only be visited by one van.
  • Each vehicle must visit a number of customers, starting and finsihing at the depot.
  • The total demands for the customers visited by one vehicle cannot exceed the capacity of the vehicle.

The aim is to devise a route for each vehicle so that the overall distance is minimized, ensuring that all the customers receive their stated demand.

The following figure shows a solution to a small Vehicle Routing Problem. The depot is shown in the middle, with the customers distributed around it (labeled A to O).

Vehicle Routing Solution

In this example, we have four vehicles available, and thus four routes.

The next figure shows EAXCTLY the same problem, but we have added the demand for each customer.

Vehicle Routing Solution

We could also add the distance between each customer to the figure, but it gets a little cluttered. Therefore, we have provided a handout, which can be downloaded from here, which gives you all the information you need. Looking at this handout, we can make the following observations.

  • Each van is allowed to carry a maximum of 100kg (i.e. the capacity of each van).
  • There are 4 vans available.
  • The distance traveled by the vehicle delivering to A, B, C, D is 55.76km (let's assume kilometres, but the units are irrelevant when describing the problem). This distance is calculated (see sheet 2 of the handout) as Depot to A (15.81), A to B (7.07), B to C (7.07), C to D (10.00) and D to Depot (15.81). Therefore, the distance traveled by the first van is (15.81 + 7.07 + 7.07 + 10.00 + 15.81) 55.76km.
    This first van would be carrying goods weighing (24 + 19 + 34 + 23) 100kg (again, let's assume kilograms, but the units do not really matter).
  • The distance traveled by the vehicle delivering to E, F, G is 45.56km. This van would be carrying goods weighing 98kg.
  • The distance traveled by the vehicle delivering to H, I, J is 64.96km. This van would be carrying goods weighing 84kg.
  • The distance traveled by the vehicle delivering to K, L, M, N, O is 68.68km. This van would be carrying goods weighing 100kg.
  • The overall distance is (55.76 + 45.56 + 74.96 + 68.68) 234.96km

You can verfiy the distances and weights carried by the second, third and fourth vehicles by referencing the handout.

You will notice that the handout contains all the information you need for this vehicle routing problem.

  • On the first page all the parameters are provided. That is, the capacity of the vehicles, how many vehicles are available (and thus the number of routes allowed), the x, y coordiantes of the depot and customers and the demand for each customer.
  • On the second page is the distance matrix. That is, the distance between each location and every other location. We assume that the distances are symmetric, so that the distance from location p to location q is the same as the distance from location q to location p. The distances are calculated as straight line distances. This is given by the following formula:

  • distpq = SQRT((px - qx)2 + (py - qy)2)

    where px and qx are the x coordinates of locations p and q and, similarly, py and qy are the y coordinates.
  • On the third page is a map of the depot and the customers. While not critical to solving the problem, it is useful to be able to see the problem represented graphically.

Finally, to make it easier to process the data it is provided in two CSV (Comma Separated Variable) files, as well as a PDF file. This contains all the relevant details, as well as a pictorial view of this problem.

  • Parameter file for RAP-CVRP-0015-001
  • Distance file for RAP-CVRP-0015-001
  • PDF file containing all the relevant details for this instance

We leave it as an exercise for you to see if you can find a better (shorter distance) solution than 244.96km, which does not exceed the capacity (100kg) of any vehicle.

If you find this interesting, we have provided some details about other datasets on the datasets page. We are also working on some other CVRP instances similar to the one we have described above.

We hope you found this page useful and we welcome your feedback. If you have any comments, please email us at admin@researchandpractise.com.

If you would like to be informed when changes are made to these pages please join our mailing list.