Heuristic Method for Costs Minimization

The above figure shows a problem of assigning 35 units between nodes a and f at minimum cost.

• Identify all possible paths between nodes having a transport demand (all paths between a and f). Order these paths by their cost, from the least to the most expensive (1).
• Take the least expensive path and assign all the traffic that the link having the weakest capacity can support (2).  Subtract this number to the capacity of every link of the path. This subtraction cannot be lower than 0. The result of this subtraction is the remaining capacity of each link of the path (2).
• Repeat by increasing order of path cost until all the demand is assigned (3 and 4). If all the demand can not be assigned, the problem cannot be solved.