Vehicle routing problem

alt_text

In this tutorial we show you how to solve a vehicle routing problem, using XLOPTIM, the fastest and most reliable solver for Microsoft Excel.

Watch our video on the vehicle routing problem.

1. Problem description

The OptiRouting company produces, sells and distributes camping gear. They have 12 delivery trucks and a customer portfolio of 30 campsites. They must deliver at least once per month to each customer depending on demand.

The company would like to know which vehicles to use and which routes to take in order to minimize their total transport cost.

2. Data

To download the data for this example and the trial version of XLOPTIM, please click on the links below:

Download the data for the vehicle routing problem

Download the trial version

Vehicles

For each vehicle we have the following information available:

  • Cargo capacity, which may vary depending on the type of vehicle
  • Costs per kilometer, which can be calculated from several parameters such as fuel consumption, maintenance, depreciation, etc.
  • Fixed costs of use, which can be calculated for the use of certain vehicles on the basis of several parameters such as the leasing price, fixed salary costs, insurance, etc.
  • The departure time from the depot. The data is entered in a 24-hour format, i.e. between 0 and 24h. It is still possible to take into account a route over several days by selecting a numerical format. If a truck is available the next day at 8am, then the departure time cell should contain the number 32. In other words, 24+8.
  • The maximum number of hours for the route
  • The vehicle identifier (or vehicle label).

alt_text

(Cargo capacity, cost per km, fixed costs for use, departure time, maximum number of hours, vehicle ID)

Customers

For each customer we have the following information available:

  • The address. This will allow us to automatically generate the distances between each point in order to solve the problem.
  • The associated order volume.
  • The campsites' availability times.
  • The name associated with each client.

alt_text

3. SOLVING A VEHICLE ROUTING PROBLEM WITH XLOPTIM

alt_text

All deliveries can’t be done in time by a single vehicle. XLOPTIM allows the company to know which orders to allocate to the different available vehicles in order to fulfill customer requests, taking into account the constraints of the drivers (limited vehicle capacity, work time) and those of the customers (availability).

To model this problem and the constraints mentioned above, simply open the Routing dialog box.

In the **Vehicles **tab, the company can select different parameters regarding the vehicles to be taken into account in the model and specify the number of available trucks.

alt_text

In the Clients tab, the company will be able to specify some data related to the orders of the customers such as their available time slots and their number.

alt_text

Then, in the Distances tab, the company can select the addresses of both customers and depots. Note: in this example, all vehicles leave from a single depot (note that multi-depot is also possible in XLOPTIM).

You can also specify your own time and distance matrices between each point (address) or select the geographical coordinates of the clients.

alt_text

In the Options tab, they will be able to enter a limited resolution time as well as whether or not to display the routes on Google Maps.

After clicking on Start, XLOPTIM solves the problem and displays the results on a new sheet.

4. Interpreting the results

alt_text

The first table sums up the optimization. Then, information such as the cost, the duration or the total volume per vehicle and per tour is displayed.

This enables us to know which vehicle we can load with additional packages as well as which vehicles are available faster thanks to a shorter tour.

alt_text

For each vehicle, we display the touring order as well as a map enabling us to visualize the route that need to be taken by the vehicle. For more details, you can click on a google maps link in order to have a better idea of the tour.

alt_text

alt_text

CONCLUSION

Thanks to this tool, XLOPTIM can solve very complex problems with up to 1000 customers and as many as 100 vehicles. The interface is simple and intuitive, enabling us to take into consideration various operational constraints in order to considerably reduce your transport costs.

Do not hesitate to contact us if you have any questions following the use of our XLOPTIM® solver.