To determine the global cost of each route, the cost of travel and the travel time between each customer and the depot must be known. To achieve this, our original graph is transformed into one where the vertices represent the customers and depots, and the arcs represent the routes between them. On the original road network, each arc has the lowest cost between the two points. Since shortest path problems are relatively simple to solve, this is not a difficult task. The original sparse graph is transformed into a complete one.

According to wikipedia, The VRP has many direct applications in industry. In fact, the use of computer optimization programs can give savings of 5% to a company as transportation is usually a significant component of the cost of a product (10%) – indeed, the transportation sector makes up 10% of the EU’s GDP. Consequently, any savings created by the VRP, even less than 5%, are significant.