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.
| [Dantzig1959] |
|
We again use the excellent C++ ePiX library[1] to visualize VRP and CVRP solutions in TSPLIB format.
| [1] | The ePiX library uses the  engine to create beautiful graphics. |
Overview:
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.
Prerequisites:
- Basic knowledge of C++.
- Basic knowledge of Constraint Programming (see the chapter Introduction to constraint programming).
- Basic knowledge of the Constraint Programming Solver (see the chapter First steps with or-tools: cryptarithmetic puzzles).
- Basic knowledge of Local Search (see the chapter Local Search: the Job-Shop Problem).
- Basic knowledge of the Routing Library (see the chapter Travelling Salesman Problems with constraints: the TSP with time windows), especially:
- the section The Routing Library (RL) in a nutshell;
- the section The model behind the scenes: the main decision variables;
- the section The two phases approach.
Files:
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.
Content:
 |
Google or-tools |