Vehicle routing problem: Difference between revisions

Revision as of 17:43, 28 May 2025

Revision as of 17:44, 28 May 2025

Line 14:

The road network can be described using a [[Graph (discrete mathematics)|graph]] where the [[directed edge|arcs]] are roads and vertices are junctions between them. The arcs may be directed or undirected due to the possible presence of one way streets or different costs in each direction. Each arc has an associated cost which is generally its length or travel time which may be dependent on vehicle type.<ref name=toth />

To know the global cost of each route, the travel cost and the travel time between each customer and the depot must be known. To do this our original graph is transformed into one where the vertices are the customers and depot, and the arcs are the roads between them. The cost on each arc is the lowest cost between the two points on the original road network. This is easy to do as [[shortest path problems]] are relatively easy to solve. This transforms the sparse original graph into a [[complete graph]]. For each ordered pair of vertices ''i'' and ''j'', there exists an arc ''(i,j)'' of the complete graph whose cost is written as <math>C_{ij}</math> and is defined to be the cost of shortest path from ''i'' to ''j''. The travel time <math>t_{ij}</math> is the sum of the travel times of the arcs on the shortest path from ''i'' to ''j'' on the original road graph.

Sometimes it is impossible to satisfy all of a customer's demands and in such cases solvers may reduce some customers' demands or leave some customers unserved. To deal with these situations a priority variable for each customer can be introduced or associated penalties for the partial or lack of service for each customer given <ref name=toth/>