Vehicle Routing Problem
The VRP was first introduced by Dantzig and Ramser in 1959. The classical VRP consists of determining several vehicle routes with minimum cost for serving a set of customers, whose geographical coordinates and demands are known in advance. Each customer is required to be visited only once by one vehicle. Typically, vehicles are homogeneous and have the same capacity restriction.
The classical VRP define on a connected graph G. Let G = (V, A) be a graph where V = {v0, v1, v2, …, vn} is a vertex set and A = {(vi, vj) │vi, vj ∈ V, i < j} is the set of arcs. Vertices v0 correspond to the depot at which K = {k0, k1, k2, …, kn} is a set homogeneous vehicles are based, and the remaining vertices denote the customers. Since the vehicles are homogeneous, then capacity for all vehicles is equal and denoted by Q. The total size of deliveries for customers assigned to each vehicle must not exceed the vehicle capacity (Qi). With every arc (i, j) is associated a non-negative distance matrix C = (cij), which represents the travel distance from vi to vj.
The classical VRP considered to be symmetric, i.e., cij = cji ; i, j = 0, 1, 2, … n. The problem is to construct a minimum travel cost, feasible set of routes - one for each vehicle. A route is a sequence of locations that a vehicle must visit a long with the indication of the service it provides. The vehicle must start and finish its tour at the depot. The VRP is a classical combinatorial optimization problem that has become a key component of distribution and logistics management.
The classical VRP is an NP-hard problem. As it is an NP-hard problem, the instances with a large number of customers cannot be solved in optimality within reasonable time. For this reason a large number of approximation techniques were proposed.
An example of combinatoril problem could be seen in: Benchmark
.
