State of art of the Capacitated Vehicle Rooting Problem
Generally, transport and distribution companies’ core business is to deliver products from one or more depots to meet the demand of their customers through sending drivers who will be traveling on a given route. These routes can be described using a graph where the customers are vertices and the roads are arcs and associated with each arc a cost that can be the length, the travel time or the amount of fuel that was used.
The figure 1 shows us that this modelization called VRP, which aims to reduce the total cost operated during themission of delivering while respecting the different constraints.
The goal is minimize the cost to serve a set of customers with goods stored in a depot. There is a fleet of vehicles that can serves the customers, each vehicle has maximum capacity that can not be exceeded. All the vehicles have the same starting point, the depot, and they transport the goods to different destinations in order to satisfy needs of customers. Each customer must be visited only once by one vehicle.In our case will define three constraint which are :
Each route begins and ends at the depot
Each customer is visited exactly once
The total demand of each route does not exceed the capacity of the vehicle
When the three constraints are verified, we can conclude that we are dealing with the Capacitated Vehicle Routing Problem (CVRP).
As the figure 2 below shows let G = (V,A) be a complete directed graph with V = {0,1,2,…,n} as the set of nodes and A = {(i, j) : i, j ∈ V,i , j} as the set of arcs, where node 0 represents the depot for a fleet of p vehicles with the same capacity Q and remaining n nodes represent geographically dispersed customers. Eachcustomeri∈V−{0}has a certain positive demand di≤ Q. The non negative travel cost ci,j is associated with each arc (i, j)∈ A
The formulation of the mathematical model of the CVRP :
Our mathematical model for the (CVRP) can be formulated as the follow
So the objective function (3.1) allows to minimize the total cost while respecting the constraints below that we explain them one by one .
The first constraint (3.2) forces us to go to a single client j and when we reach that client we must have arrived from a single node either the depot or the predecessor client i.
The second constraint (3.3) forces us to go to a single client i and when we reach that client we must have arrived from a single node either the depot or the predecessor client j.
For the constraint (3.4); if xi,j = 1 it means that we have a route already traveled from i to j,ui presents the cumulative demand towards the point i therefore if a vehicle goes from the node i to the next node j so the cumulative demand of this point j equal the preceding cumulative demand ui + the demand dj of the point j. Theconstraint(3.5)indicates that the cumulative demand must be less or equal to the capacity of vehicle Q.
The last constraint(3.6) indicates that the value of xi,j varies between 0 and 1 and as we motioned if a vehicle goes from i to j it means that we have a route and xi,j equal to 1 otherwise xi,j equal to 0.
References
Toth, P., Vigo, D.: The Vehicle Routing Problem. Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (2001)
Dantzing, G., Ramster, R.: The truck dispatching problem. Management Science 6 (1959) 80–91
Christodes, N., Mingozzi, A., Toth, P.: The Vehicle Routing Problem. In: Combinatorial Optimization. John Wiley (1979) 315–338
http://neo.lcc.uma.es/radi-aeb/WebVRP/index.html.
Golden, B., Wasil, E., Kelly, J., Chao, I.M.: The Impact of Metaheuristics on Solving the Vehicle Routing Problem: algorithms, problem sets, and computationalresults. In: FleetManagementandLogistics. Kluwer,Boston(1998)33–56
Toth, P., Vigo, D.: The granular tabu search and its application to the vehicle routing problem. INFORMS Journal on Computing 15 (2003) 333–346
