10. Vehicule Routing Problems with constraints: the capacitated vehicle routing problem

The Vehicle Routing Problem (VRP) is a Routing Problem where you seek to service a number of customers with a fleet of (homogeneous or heterogeneous) vehicles starting from one depot. The basic idea is to service clients - represented by nodes in a graph - by the vehicles. Lots of theoric and industrial problems can be modelled as a VRP. The problem’s origins can be traced back to the fifties (see [Dantzig1959] for instance). It includes the TSP (a VRP with one vehicle) as a special case, and is, as such, a computationally complex problem.

    1. Dantzig and J. H. Ramser. The Truck Dispatching Problem, Management Science v. 6, pp 80-91, 1959.

We again use the excellent C++ ePiX library[1] to visualize VRP and CVRP solutions in TSPLIB format.

[1]The ePiX library uses the \text{\TeX/\LaTeX} engine to create beautiful graphics.


We first introduce the VRP and the TSPLIB instances for the Capacitated Routing Vehicle Problem. The TPSLIB instance format is the de facto format to represent CVRP instances in the scientific community. We then present a basic program to solve the bare VRP. To do so, we show how to interact directly with the underlying CP solver. Next, the CVRP is introduced and explained. Capacities are modelled with Dimensions. Finally, we discuss the multi-depots variant of the VRP in general and how to fix some parts of the routes while letting the CP solver assign the other clients to vehicles, i.e. how to complete the partial solution.



You can find the code in the directory documentation/tutorials/cplusplus/chap10.

The files in this directory are:

  • cvrp_data_generator.h: Contains the CVRPDataGenerator class that generates random CVRP instances.
  • cvrp_data_generator.cc: Generates random CVRP instances.
  • cvrp_data.h: Contains the CVRPData class used in this chapter to encode a CVRP instance.
  • cvrp_solution.h: Povides the CVRPSolution used to represent CVRP solutions.
  • cvrp_epix_data.h: Provides the helper functions to visualize CVRP solutions with the ePiX library.
  • vrp_solution_to_epix.cc: Permits the visualization of a VRP solution with the help of the ePiX library.
  • vrp.cc: A basic implementation to solve the VRP.
  • check_vrp_solution.cc: Checks if a VRP solution is feasible.
  • cvrp_basic.cc: A basic implementation to solve the CVRP.
  • cvrp_solution_to_epix.cc: Permits the visualization of a CVRP solution with the help of the ePiX library.
  • check_cvrp_solution.cc: Checks if a CVRP solution is feasible.
  • vrp_IO.cc: Simple program to apply and test the IO mechanism of the RL with a multi-VRP.
  • vrp_locks.cc: Simple program to apply and test locks in a multi-VRP.


Google or-tools
open source library

User's Manual

Google search



Tutorial examples


Part I: Basics
Part II: Customization
Part III: Routing
Part IV: Technicalities