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.
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:
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).
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.
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.
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.
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.
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 email@example.com.
If you would like to be informed when changes are made to these pages please join our mailing list.